Phil 2250 16JUN26
Shared on June 16, 2026
Lecture Notes: Tarski, Compactness, Löwenheim–Skolem, and Meta‑Theory in PL
Overview
These notes capture the main points of a lecture on propositional logic (PL), first‑order logic (FOL), and meta‑theory. The instructor discussed foundational concepts (satisfaction vs truth), key theorems (compactness, Löwenheim–Skolem), derivation techniques, and practical course information (homework deadlines, exam format).
Key Concepts
Concept | Core Idea | Practical Take‑away |
|---|---|---|
Tarski’s Satisfaction | Truth of sentences defined recursively via satisfaction in a structure. PL sentences lack truth values until interpreted. | Use satisfaction when checking truth in models; necessary for recursive truth definitions. |
Homework Policy | Submissions due Thursday for grading; Friday submissions accepted but ungraded. Bonus homework due Thursday. | Plan to submit by Thursday; otherwise you’ll miss credit. |
Compactness (SL & PL) | If every finite subset of an infinite set of sentences is satisfiable, the whole set is satisfiable. | Useful in completeness proofs; holds for both SL and PL. |
Löwenheim–Skolem Theorem | If a sentence has any model, it has one whose domain is the natural numbers. | Allows reducing arbitrary models to countable ones for PL; does not hold for PLE (first‑order logic with identity). |
Identity & Derivation Rules | Equality can be replaced in atomic formulas; derivations often rely on identity elimination. | When proving theorems involving equality, use identity elimination to substitute terms. |
Quantifier Negation | ¬∀x φ ≡ ∃x ¬φ and ¬∃x φ ≡ ∀x ¬φ. | Handy for converting complex quantified formulas into more manageable forms. |
Soundness & Completeness | Soundness: every derivable sentence is true in every model. Completeness: every sentence true in every model is derivable. | Core meta‑theoretical properties of PL and PD; proofs use induction on derivation length. |
Exam Structure | Similar to midterm: symbolization, semantic, derivation, and deeper conceptual questions; includes a bonus problem. | Expect a mix of technical and conceptual questions; practice symbolization and derivations. |
Detailed Notes
1. Tarski’s Satisfaction
Why Satisfaction Matters: PL sentences alone have no truth value; satisfaction provides the bridge to truth in a given interpretation.
- Recursive Definition: For each connective, truth is defined in terms of satisfaction of its sub‑sentences.
2. Homework & Grading
- Deadlines
- Thursday: graded.
- Friday: accepted but ungraded.
- Bonus: due Thursday.
- Policy Rationale: Gives students time to review solutions posted after class before the Monday exam.
3. Compactness
- Statement: Infinite set Γ is satisfiable ⇔ every finite subset of Γ is satisfiable.
- Usage: Proven during completeness proofs; not directly invoked in most class work.
- Implication: Provides a powerful tool for constructing models from consistent sets.
4. Löwenheim–Skolem (LS) Theorem
- PL: If a sentence has a model, it has a model with domain ℕ.
- Fails for PLE: Adding identity allows sentences that force uncountable domains.
- Intuition: PL’s expressive power is limited enough that countable models always suffice.
5. Identity in Derivations
- Identity Elimination: From
x = yand a formula containingx, replacexwithy.
- Common Strategy: Use identity elimination to derive new facts (e.g., from
B = CderiveP(B)→P(C)).
- Example: Deriving
A = CfromA = BandB = C.
6. Quantifier Negation & De Morgan
- Rules:
¬∀x φ≡∃x ¬φ
¬∃x φ≡∀x ¬φ
- De Morgan for quantifiers and disjunctions.
- Practice: Convert nested quantifiers to simplify derivations.
7. Meta‑Theoretical Theorems
- Soundness: Proven by induction on derivation length; ensures no false statements are derivable.
- Completeness: Requires constructing a maximally consistent set and building a model; relies on compactness and LS.
- Compactness Proof Sketch: Show that if all finite subsets of Γ are satisfiable, then Γ is satisfiable via a consistent, complete theory.
8. Exam Expectations
- Content: Symbolization, semantic evaluation, derivation construction, and meta‑theoretical questions.
- Format: Mixed‑style, similar to the midterm; includes a bonus question.
- Preparation: Focus on symbolization practice, derivation rules (especially quantifier and identity rules), and understanding the soundness/completeness arguments.
9. Miscellaneous
- Student Appendix Work: Administrative note on extending study period dates (Sept 4 – June 23). Not directly relevant to logic content but mentioned during the session.
Take‑away: Master the recursive definition of truth via satisfaction, understand how compactness and Löwenheim–Skolem shape model existence, and be fluent with identity and quantifier rules for derivations. Follow homework deadlines closely and prepare for a balanced exam covering both technical skills and conceptual understanding.