Phil 2250 17JUN26
Shared on June 17, 2026
Lecture on the Metatheory of First‑Order Logic
Overview
The lecture explains how to determine whether a set of first‑order sentences is Q‑consistent, the role of true functional expansions in constructing models, and the fundamental metalogical properties of propositional and predicate logic: soundness, completeness, truth‑functional completeness, and decidability. It then outlines the Henkin construction for proving completeness, introduces maximally consistent and existentially complete sets, and discusses the use of Girdle numbering to enumerate all sentences of the language.
Key Concepts
Q‑Consistency – a set of sentences has a model in which all are true.
- True Functional Expansion – replacing quantified variables with all constants already present in the sentences.
T‑Sentences – sentences that state the truth condition of other sentences (e.g., “Grass is green iff grass is Greek”).
- Soundness – if a sentence is derivable, it is logically valid.
Completeness – if a sentence is logically valid, it is derivable.
- Truth‑Functional Completeness – every truth function can be expressed in the language.
Decidability – existence of an algorithm that decides the truth of any sentence.
- Henkin Construction – building a model from a maximally consistent set.
Maximally Consistent Set – consistent and cannot add any further sentence without becoming inconsistent.
- Existentially Complete Set – every existential sentence has a witness constant in the set.
Girdle (Gödel‑style) Numbering – a method of enumerating all sentences of a language.
Detailed Notes
1. Q‑Consistency and Functional Expansions
- A set is Q‑consistent iff there exists an interpretation making all its sentences true.
- True functional expansions must include every constant that occurs in the sentences.
- Example: For constants 1–7, expanding to 7 constants is insufficient to satisfy “not all are in B”; an 8th constant is required.
2. T‑Sentences and Object/Meta Language
Object language: the language being described (e.g., English).
- Meta language: language used to discuss the object language.
- A T‑sentence states the truth condition of a sentence (e.g., “Grass is green is true iff grass is Greek”).
- Such sentences do not assert the truth of the object statement; they provide its truth condition.
3. Metatheory of Predicate Logic (PL)
- Soundness: derivation in the proof system ⇒ logical validity.
- Completeness: logical validity ⇒ derivation in the proof system.
- Truth‑Functional Completeness: every truth function is representable.
- Decidability: PL is undecidable; SL (sentential logic) is decidable via truth tables.
4. Proof of Soundness (Induction on Derivation Length)
- Base case: axioms are true.
- Inductive step: each derivation rule preserves truth.
- Additional cases required for PL: four quantifier rules and two identity rules.
5. Proof of Completeness (Henkin’s Method)
- Assume γ is syntactically consistent.
- Construct γ<sub>e</sub> by doubling subscripts of all constants in γ, ensuring infinitely many unused constants.
- Extend γ<sub>e</sub> to a maximally consistent, existentially complete set γ* (using Girdle numbering to enumerate all sentences).
- Henkin interpretation I*:
- Domain: positive integers (or the set of constants).
- Atomic sentences are true exactly when they belong to γ*.
- Prove by induction that every sentence P is true in I* iff P ∈ γ*.
- Conclude γ is Q‑consistent.
6. Girdle Numbering
- Assign a unique natural number to every symbol (e.g., ∼ → 10, ∧ → 12, A → 30).
- Concatenate numbers of symbols in a sentence to obtain its Gödel number.
- Enumerates all sentences, enabling systematic construction of γ*.
7. Maximal Consistency and Existential Completeness
- Maximal Consistent: a consistent set that cannot be enlarged without inconsistency.
- Existentially Complete: for every ∃x φ(x) in the set, there is a constant a with φ(a) in the set.
8. Consequences and Further Properties
- Compactness: a set is Q‑consistent iff every finite subset is Q‑consistent.
- Undecidability of PL follows from the existence of undecidable theories (e.g., arithmetic).
- Truth‑functional completeness of SL ensures PL inherits it via inclusion.
9. Practical Takeaways
- To test Q‑consistency, search for an interpretation satisfying all sentences.
- When constructing proofs, remember to include identity and quantifier rules.
- For completeness proofs, the Henkin method transforms syntactic consistency into a semantic model.
- Girdle numbering provides a systematic way to enumerate and extend sets.
These notes capture the lecture’s essential arguments and methods, focusing on the metalogical framework that guarantees soundness, completeness, and the construction of models for first‑order logic.