Predicate logic - Models Theories and Metalogical Theorems

Models, Theories, and Elementary Classes Introduction First-order logic is one of the most fundamental tools in mathematics and computer science. To understand how it works, we need to distinguish between three related but different concepts: the syntax (what we can write), the semantics (what structures satisfy our statements), and the provability (what we can derive using rules). This section explores the relationship between these three concepts through the lens of theories, models, and the major metalogical theorems that tell us what first-order logic can and cannot do. First-Order Theories A theory is a set of sentences (closed formulas) in some fixed signature. Think of a theory as a collection of rules or constraints written in a formal language. For example, Peano arithmetic is a theory that includes axioms like "0 is a number" and "if n is a number, then n+1 is a number." Among the sentences in a theory, we typically identify a subset called the axioms—these are the foundational statements from which all other true statements can be derived. The remaining sentences are called theorems or derived consequences. A theory is effective when its axioms are recursively enumerable. In practice, this means there is an algorithm (a step-by-step procedure) that can list out all the axioms, though it may take infinitely long to list them all. Most theories we care about, including Peano arithmetic and the axioms of set theory (ZFC), are effective theories. When axioms are finite, the theory is obviously effective—we can just list them. Why this matters: Effectiveness is crucial because it ensures that the theory is genuinely "formal"—there's a mechanical procedure that determines what counts as an axiom. This makes it possible to study theories mathematically. Models of a Theory Now that we have axioms (sentences), we ask: what structures (models) actually satisfy these sentences? A model of a theory $T$ is a structure (consisting of a domain and interpretations of the constants, function symbols, and predicates) such that every sentence of $T$ is true in that structure. For example, the natural numbers $\mathbb{N} = (0, 1, 2, \ldots)$ with the standard operations form a model of Peano arithmetic because all the axioms of Peano arithmetic are true in this structure. The crucial point: A single theory can have multiple models. For instance, Peano arithmetic has multiple models beyond just the natural numbers—these are called non-standard models. These models satisfy all the same axioms but have additional elements that aren't natural numbers in the traditional sense. The elementary class of a theory $T$ is simply the collection of all models of $T$. If we denote the elementary class as $\text{Mod}(T)$, then $M \in \text{Mod}(T)$ if and only if $M$ satisfies every sentence of $T$. Key insight: A theory's strength is partly determined by how much it narrows down the possible models. The more axioms we have, the smaller (more restricted) the elementary class becomes. Consistency and Completeness Two properties of theories are especially important: Consistency means that the theory does not lead to contradiction. More precisely, there is no sentence $\varphi$ such that both $\varphi$ and $\lnot\varphi$ can be proven from the axioms. Equivalently, a consistent theory has at least one model. Completeness means that for every sentence $\varphi$ in the language of the theory, at least one of the following is true: either $\varphi$ is provable from the axioms, or $\lnot\varphi$ is provable from the axioms. In other words, every statement is decided one way or another by the theory. Why the distinction matters: A consistent theory might still be incomplete. It could have sentences that are "undecided"—statements that don't contradict the axioms but also aren't forced to be true by them. For example, Peano arithmetic is consistent, but it is also incomplete (as we'll discuss below). Gödel's Incompleteness Theorem Here is one of the most profound theorems in logic: Gödel's Incompleteness Theorem: Any effective first-order theory that is strong enough to express basic arithmetic cannot be both consistent and complete. In other words, if you have a formal system with computable (effective) axioms that can express arithmetic facts, you must choose: either your system is consistent but leaves some sentences undecided, or every sentence is decidable but your system is inconsistent. This means that there exist true but unprovable sentences in any consistent, effective, arithmetic theory. These sentences are true in the "intended model" (like the natural numbers) but cannot be derived from the axioms. Why this is so significant: This theorem destroyed the hope of creating a complete, finite axiomatization of mathematics. No matter how many axioms you write down, if they're effectively listed and can express arithmetic, there will always be something true that you cannot prove. Fundamental Metalogical Theorems Gödel's Completeness Theorem Despite the incompleteness result above, first-order logic itself has a remarkable property: Gödel's Completeness Theorem: There exist sound and complete deductive systems for first-order logic such that every logically valid formula has a finite proof. What this means: A formula $\varphi$ is logically valid (true in all models) if and only if it is provable using the deductive rules of first-order logic. This shows that the proof rules of first-order logic are "enough"—nothing valid escapes them. Important distinction: The incompleteness theorem applies to specific theories (like Peano arithmetic), while the completeness theorem applies to first-order logic itself. They are not contradictory. First-order logic is complete, but any specific theory built on top of it (like Peano arithmetic) may be incomplete. Semidecidability of Logical Consequence A consequence of the completeness theorem is that first-order logical consequence is semidecidable. Here's what this means: Suppose you have a formula $\varphi$ and ask whether a formula $\psi$ logically follows from it (written $\varphi \models \psi$). In principle, you can enumerate all possible finite derivations in order. If $\psi$ truly is a logical consequence of $\varphi$, then eventually (though you don't know when) you will find a proof of $\psi$ from $\varphi$. However, if $\psi$ is not a logical consequence of $\varphi$, your enumeration might run forever without finding a proof. This is why it's called "semidecidable" rather than "decidable"—we can recognize a positive answer, but we cannot always recognize a negative answer in finite time. Undecidability of First-Order Logic Despite the completeness theorem giving us a way to enumerate all valid formulas, there is a critical limitation: First-order logic is undecidable when the language contains at least one predicate of arity two or higher. This means there is no algorithm that can decide, for an arbitrary pair of formulas $\varphi$ and $\psi$, whether $\varphi$ logically implies $\psi$. In other words, while we can enumerate proofs and eventually find one if it exists (semidecidability), we cannot tell in advance whether we'll ever find one. We cannot "bound" our search and give up confidently. Why the restriction to arity ≥ 2? When all predicates are unary (monadic), the logic becomes decidable. But as soon as you allow binary predicates (or higher), you introduce enough expressive power that undecidability appears. Löwenheim–Skolem Theorem This theorem reveals a profound limitation of first-order logic: Löwenheim–Skolem Theorem: If a first-order theory $T$ has an infinite model, then it has models of every infinite cardinality greater than or equal to the cardinality of its language. To understand this, recall that the cardinality of a language is the number of distinct symbols (constants, predicates, functions) in that language. For example, Peano arithmetic has a language of finite cardinality. What the theorem tells us: If a theory has one infinite model, it has infinitely many, in a very strong sense. For example, Peano arithmetic has models of cardinality $\aleph0$ (countably infinite), but also models of cardinality $\aleph1, \aleph2$, and so on. This is surprising because it means different-sized models satisfy the exact same axioms. First-order axioms cannot distinguish between them. Non-Categoricity of Infinite Theories A direct consequence of Löwenheim–Skolem is that no first-order theory with an infinite model can be categorical. A theory is categorical if it has (up to isomorphism) exactly one model. This means first-order logic cannot uniquely pin down the natural numbers, the real numbers, or any other infinite structure. Example: Peano arithmetic cannot characterize the natural numbers uniquely in first-order logic. While the "standard" natural numbers form one model, there exist non-standard models with additional elements that satisfy all the same axioms. You cannot write down a set of first-order axioms that rules out these non-standard models. This is a fundamental limitation: first-order logic is not expressive enough to uniquely specify infinite structures. Compactness Theorem Here is one of the most elegant theorems in logic: Compactness Theorem: A set of first-order sentences $\Sigma$ has a model if and only if every finite subset of $\Sigma$ has a model. Why this is remarkable: The theorem says that if every finite piece of your specification is consistent (has a model), then the whole specification is consistent. You don't need to check infinitely many finitary constraints separately—if all finite subsets work, the infinite set works. Intuition: Imagine you have infinitely many axioms. Compactness says that consistency is "determined locally" by finite pieces. This is analogous to how continuity in analysis is determined by behavior on small neighborhoods. Applications: Compactness is used to prove existence of models with special properties and to show that certain structures cannot be axiomatized in first-order logic. <extrainfo> Intended Interpretations and Non-standard Models Many theories are designed with a particular structure in mind, called the intended interpretation. For example, when we write the axioms of Peano arithmetic, we have in mind the natural numbers: $\mathbb{N} = (0, 1, 2, 3, \ldots)$ with standard addition and multiplication. However, the Löwenheim–Skolem theorem guarantees that most first-order theories have non-standard models—models that satisfy all the axioms but are not isomorphic to the intended interpretation. These non-standard models can have strange properties. For instance, non-standard models of Peano arithmetic contain elements that act like "infinite numbers" greater than any standard natural number, yet they satisfy all the induction axioms. The existence of non-standard models shows that the intended interpretation cannot be uniquely specified by first-order axioms alone. </extrainfo> <extrainfo> Lindström's Theorem Lindström's Theorem provides a beautiful characterization: First-order logic is the strongest logic that simultaneously satisfies both the Löwenheim–Skolem property and the compactness property. In other words, if you want a logic that is more expressive than first-order logic, you must give up at least one of these two properties. Some higher-order logics are more expressive but lose compactness; infinitary logics have compactness but lose Löwenheim–Skolem. First-order logic represents a "sweet spot" in terms of expressiveness and desirable metalogical properties. </extrainfo> Limitations and Expressiveness Expressiveness Compared with Higher-Order Logics First-order logic has limits, and these are precisely quantified by the results above. Higher-order logics (like second-order logic) can express properties that first-order logic cannot. For example, in second-order logic, you can write axioms that uniquely characterize the natural numbers or the real numbers up to isomorphism. However, the cost is substantial: higher-order logics lose both the compactness property and the Löwenheim–Skolem property. Their meta-theory becomes much more complicated, and many desirable results no longer hold. <extrainfo> Similarly, infinitary logics (which allow infinitely long formulas) can be more expressive than first-order logic, but they also have limited applicability and complexity. </extrainfo> <extrainfo> Decidable Fragments While first-order logic in full generality is undecidable, certain restricted fragments are decidable: Propositional logic (the most basic fragment with no quantifiers or predicates) Monadic predicate logic (only unary predicates) The guarded fragment (restrictions on how quantifiers can be used) Two-variable logic (formulas using only two distinct variables) The Bernays–Schönfinkel class (formulas with a specific quantifier structure) These fragments show that undecidability arises from the interaction of multiple features of first-order logic. By restricting the language or structure, we can recover decidability, but at the cost of expressiveness. </extrainfo> Summary First-order logic is a remarkable formal system. On one hand, it is complete (Gödel's Completeness Theorem), meaning that the proof rules capture exactly the logical validities. On the other hand, any specific theory expressed in first-order logic is either incomplete (Gödel's Incompleteness Theorem) or undecidable. Moreover, first-order logic cannot uniquely characterize infinite structures (Löwenheim–Skolem), but this same feature enables the compactness theorem. Together, these results paint a precise picture of where first-order logic stands in the landscape of formal systems.