Predicate Logic (First-Order Logic)¶
Job: Define FOL syntax and model-theoretic semantics; state Gödel completeness and compactness; mark incompleteness of arithmetic theories.
Core¶
Syntax. Signature \(\mathcal{L}\) (constants, function symbols, relation symbols). Terms; atomic formulas \(R(t_1,\ldots,t_k)\), \(t=s\); formulas closed under \(\neg,\to,\forall x\). Free/bound variables; sentences = no free vars.
Structures. \(\mathcal{M}=(M,\{c^\mathcal{M}\},\{f^\mathcal{M}\},\{R^\mathcal{M}\})\). Satisfaction \(\mathcal{M}\models\varphi[\bar a]\) defined recursively (Tarski). Theory \(\mathrm{Th}(\mathcal{M})=\{\text{sentences }\varphi:\mathcal{M}\models\varphi\}\).
Semantic entailment \(\Gamma\models\varphi\): every model of \(\Gamma\) models \(\varphi\).
Gödel completeness theorem. For FOL, \(\Gamma\vdash\varphi\Leftrightarrow\Gamma\models\varphi\) (in a standard effective deduction system). Hence syntactic consistency \(\Leftrightarrow\) existence of a model (Henkin construction).
Compactness. If every finite subset of \(\Gamma\) has a model, so does \(\Gamma\). Corollaries: upward Löwenheim–Skolem (with completeness); nonstandard models of \(\mathrm{Th}(\mathbb{N})\) if \(\mathrm{Th}(\mathbb{N})\) is the full theory; finite axiomatizability failures.
Löwenheim–Skolem. If \(\Gamma\) has an infinite model, it has models of every infinite cardinality \(\ge|\mathcal{L}|\) (downward: elementary submodels via Skolem hulls; upward: compactness).
Incompleteness (pointer). Any consistent, effectively axiomatized theory \(T\) extending a weak arithmetic (e.g. Robinson \(Q\)) is incomplete: \(\exists\) sentence \(\varphi\) with \(T\nvdash\varphi\) and \(T\nvdash\neg\varphi\). Moreover \(T\) cannot prove its own consistency (Gödel second; Hilbert–Bernays–Löb derivability conditions). FOL itself is complete as a logic; arithmetic theories are incomplete as theories.
Decidability. Valid FOL sentences are r.e. (completeness) but not recursive (Church–Turing). Fragments: monadic FOL decidable; Presburger arithmetic decidable; full \((\mathbb{N},+,\cdot)\) not.
Definability. Set \(A\subseteq M^k\) definable without parameters if \(A=\{\bar a:\mathcal{M}\models\varphi(\bar a)\}\) for some \(\varphi\). Beth / Svenonius relate implicit and explicit definability.
See it¶
Nonstandard arithmetic: \(\Gamma=\mathrm{Th}(\mathbb{N})\cup\{c>n:n\in\mathbb{N}\}\) finitely satisfiable \(\Rightarrow\) model with infinite element \(c\) by compactness. Elementarily equivalent to \(\mathbb{N}\) but not isomorphic.
Check¶
Does completeness of FOL contradict Gödel incompleteness?
No. Completeness: semantic validity of FOL inferences is capturable by proofs. Incompleteness: a particular theory (e.g. PA) fails to decide all arithmetic sentences. Different quantifiers over "all models of \(\Gamma\)" vs "all sentences of arithmetic."
Why can't we finitely axiomatize 'being finite' in FOL?
If \(\Gamma\) had only finite models, and every finite size were bounded by \(N\), ok — but if \(\Gamma\) has arbitrarily large finite models, compactness on \(\Gamma\cup\{\exists^{\ge n}:n\in\mathbb{N}\}\) yields an infinite model. Hence no FOL theory has models exactly the finite structures.
Pitfalls¶
- Second-order logic with full semantics is not compact and not complete for any r.e. proof system (if consistent with standard set theory).
- Skolem paradox: countable models of ZFC fragments still "think" there are uncountable sets — external vs internal cardinality.
- Equality may be logical or a congruence; treat carefully in ultraproducts.
Refs¶
Enderton; Marker, Model Theory; Kunen; Shoenfield; Chang–Keisler.