<aside> 🎯

Introduction to Predicate Logic (First-Order Logic), exploring how it extends propositional logic with sets, functions, relations, and quantifiers. Learn what constitutes a "world" in predicate logic and how to determine when formulas are satisfied.

</aside>

Topics covered:

• Review of soundness and completeness from propositional logic
• Why predicate logic is more expressive than propositional logic
• Components of a world in predicate logic: sets, functions, relations
• Quantifiers: universal (∀) and existential (∃)
• Syntax of predicate logic formulas
• Semantics: when a world models a formula (A ⊨ φ)
• Worked examples: analyzing injective functions, surjective functions, and reflexive relations
• Brief introduction to Gödel's incompleteness theorems

Review: Propositional Logic and Natural Deduction

Key Properties from Previous Lectures

Soundness:

• If we can prove something syntactically (Γ ⊢ φ), then we have semantic entailment (Γ ⊨ φ)
• Every time the premises are true, the conclusion will also be true
• A proof implies semantic entailment

Completeness:

• If we have semantic entailment (Γ ⊨ φ), then we can find a proof using natural deduction rules (Γ ⊢ φ)
• If an assignment of truth values makes all premises true and the conclusion true, we can construct a proof