This is proved by showing addition and multiplication are representable, then using the Gödel \( \beta \)-function to encode sequences, allowing the simulation of recursion within PA.

5.3 Decidability and Undecidability

5.4 Gödel’s First Incompleteness Theorem

5.4.1 The Diagonal Lemma

5.4.2 Proof of the First Incompleteness Theorem

Let \( \mathrm{Prov}_T(x) \) be the formula representing the provability predicate: \( \mathrm{Prov}_T(\overline{n}) \) holds (in \( \mathbb{N} \), and is provable in \( T \)) iff \( n \) is the Gödel number of a theorem of \( T \). This predicate exists because the set of proofs in \( T \) is primitive recursive (for recursively axiomatized \( T \)).

Apply the Diagonal Lemma with \( \psi(y) = \lnot \mathrm{Prov}_T(y) \):

There exists a sentence \( G \) such that \( T \vdash G \leftrightarrow \lnot \mathrm{Prov}_T(\ulcorner G \urcorner) \).

Intuitively, \( G \) says “I am not provable in \( T \).”

Claim 1: \( T \not\vdash G \). Suppose \( T \vdash G \). Since the proof system is correct (and \( T \) is consistent), \( \mathbb{N} \models \mathrm{Prov}_T(\ulcorner G \urcorner) \), so \( T \vdash \mathrm{Prov}_T(\ulcorner G \urcorner) \). But then \( T \vdash \lnot G \) (from the biconditional), contradicting consistency.

Claim 2: \( T \not\vdash \lnot G \) (assuming \( T \) is \( \omega \)-consistent or using Rosser’s trick). Under \( \omega \)-consistency: if \( T \vdash \lnot G \), then \( \mathbb{N} \models \lnot\lnot \mathrm{Prov}_T(\ulcorner G \urcorner) \), meaning there is a proof of \( G \) in \( T \). But we showed \( T \not\vdash G \), so \( \mathbb{N} \models \forall n\, \lnot \mathrm{Proof}_T(n, \ulcorner G \urcorner) \) (where \( \mathrm{Proof}_T(n,m) \) says \( n \) codes a proof of \( m \)). Then \( T \vdash \lnot \mathrm{Proof}_T(\overline{n}, \ulcorner G \urcorner) \) for each \( n \) (by representability), contradicting \( \omega \)-consistency and \( T \vdash \lnot G \) (which says a proof exists). \(\square\)

Rosser’s improvement (1936): Replace \( \psi(y) = \lnot \mathrm{Prov}_T(y) \) with the Rosser predicate \( \psi_R(y) = \forall p\, (\mathrm{Proof}_T(p,y) \to \exists q < p\, \mathrm{Proof}_T(q, \lnot y)) \), which says “any proof of me is preceded by a shorter proof of my negation”. Then \( T \not\vdash G_R \) and \( T \not\vdash \lnot G_R \) assuming only consistency (not \( \omega \)-consistency).

5.4.3 Semantic Completeness vs. Syntactic Incompleteness

The completeness theorem (Chapter 2) says: everything that is true in all models is provable. The incompleteness theorem says: even in a single fixed intended model (\( \mathbb{N} \)), there are true statements not provable in \( T \). These are not contradictory! The Gödel sentence \( G \) is true in \( \mathbb{N} \) (since \( \mathbb{N} \models \lnot \mathrm{Prov}_T(\ulcorner G \urcorner) \) — truly there is no proof), but it is not provable in \( T \).

5.5 Gödel’s Second Incompleteness Theorem

Philosophical significance. Hilbert’s program sought a finitary consistency proof for all of mathematics. The Second Incompleteness Theorem shows that no consistent system powerful enough to encode arithmetic can prove its own consistency. In particular, ZFC cannot prove \( \mathrm{Con}(\text{ZFC}) \) (assuming ZFC is consistent). A stronger system can prove the consistency of a weaker one — but one always needs to “stand outside” the system.

5.5.1 Löb’s Theorem

Corollary. The Gödel sentence \( G \) is not provable in \( T \): if it were, then \( T \vdash \mathrm{Prov}_T(\ulcorner G \urcorner) \to G \), but by Löb’s theorem this would give \( T \vdash G \) and hence inconsistency.

5.6 Tarski’s Undefinability of Truth

This is the formal version of the Liar Paradox (“This sentence is false”). Tarski’s theorem is in fact stronger than Gödel’s: it shows not just that \( T \) is incomplete, but that truth in \( \mathbb{N} \) is not even definable in the language of arithmetic, let alone provable.

Chapter 6: Deeper Model Theory

6.1 Ultraproducts and an Alternative Proof of Compactness

Proof of Compactness via Ultraproducts. Let \( \Phi = \{\varphi_j : j \in J\} \) be finitely satisfiable. Index models: for each finite \( F \subseteq J \), let \( \mathfrak{A}_F \models \Phi_F = \{\varphi_j : j \in F\} \). Set \( I = \{F \subseteq J : F \text{ finite}\} \). For each \( j \in J \), let \( X_j = \{F \in I : j \in F\} \). The family \( \{X_j : j \in J\} \) has the finite intersection property (any finite intersection \( X_{j_1} \cap \cdots \cap X_{j_n} \supseteq \{j_1,\ldots,j_n\} \neq \emptyset \)), so it extends to an ultrafilter \( \mathcal{U} \) on \( I \). For each \( j \in J \): \( \{F : \mathfrak{A}_F \models \varphi_j\} \supseteq X_j \in \mathcal{U} \). By Łoś, \( \prod_\mathcal{U} \mathfrak{A}_F \models \varphi_j \) for all \( j \). Hence \( \prod_\mathcal{U} \mathfrak{A}_F \models \Phi \).

6.2 The Omitting Types Theorem

A type is isolated by \( \varphi \) if \( T \vdash \varphi \to \psi \) for all \( \psi \in p \). The theorem says that types which are not forced must be avoidable.

6.3 Categoricity and Morley’s Theorem

This deep theorem — Morley’s first major result in model theory — launched the program of stability theory and classification theory, developed by Shelah in the 1970s. The key tools are:

• Strongly minimal sets: a definable set \( D \) in \( M \models T \) is strongly minimal if it is infinite and for every definable subset \( X \subseteq D \), either \( X \) or \( D \setminus X \) is finite.
• Algebraic independence and Morley rank: a notion of dimension analogous to transcendence degree in field theory.
• Uncountably categorical theories have a strongly minimal set and are “controlled” by this set.

6.4 Stability and Classification

Shelah’s monumental classification program addresses: for which theories \( T \) and cardinals \( \kappa \) is the number of models of \( T \) of cardinality \( \kappa \) small?

Stability spectrum: a theory is:

• \( \omega \)-stable (totally transcendental) if \( |S_1(M)| \leq \aleph_0 \) for all \( M \models T \) with \( |M| = \aleph_0 \). Examples: ACF, the theory of \( (\mathbb{Q}, +) \).
• Superstable if stable in all \( \kappa \geq 2^{|T|} \).
• Stable (but not superstable): DLO is not stable!
• Unstable (has the order property): real closed fields, linear orders.

Chapter 7: Connections and Advanced Topics

7.1 Zermelo–Fraenkel Set Theory and Gödel’s Constructible Universe

Gödel’s L (the Constructible Universe) is built by:

Cohen’s Forcing (1963). Cohen invented the method of forcing to build models of ZFC in which CH fails. One starts with a countable transitive model \( M \) of ZFC and adds a generic set \( G \subseteq \omega \times \omega_2 \) to get an extension \( M[G] \) in which \( 2^{\aleph_0} \geq \aleph_2 \). The key is that the forcing relation “\( p \Vdash \varphi \)” (a condition \( p \) forces \( \varphi \)) is definable in \( M \), so truth in \( M[G] \) can be controlled from within \( M \). This established the independence of CH from ZFC.

7.2 Large Cardinals

The consistency strength of set-theoretic principles is measured by large cardinals:

• Inaccessible cardinals: \( \kappa > \omega \) is inaccessible if it is regular and for all \( \lambda < \kappa \), \( 2^\lambda < \kappa \). ZFC cannot prove inaccessibles exist.
• Measurable cardinals: \( \kappa \) is measurable if there is a \( \kappa \)-complete ultrafilter on \( \kappa \). The ultrapower of \( V \) by this ultrafilter gives an elementary embedding \( j : V \to M \) with critical point \( \kappa \).
• Woodin cardinals, supercompact cardinals, etc.: the large cardinal hierarchy extends far into the transfinite and provides consistency strength for many set-theoretic propositions.

7.3 Reflection and the Relationship Between Syntax and Semantics

This shows that the axioms of ZFC cannot be finite (since any finite list of axioms has a set-sized model, contradicting the incompleteness theorem — actually, this gives another proof that ZFC cannot prove its own consistency).

7.4 Arithmetical Hierarchy

This last fact is essentially Tarski’s undefinability theorem expressed in the language of computability.

Chapter 8: Summary of Major Theorems and Connections

8.1 The Four Pillars — A Unified View

The four main areas of PMATH 432 are deeply interconnected:

First-order logic provides the formal language (Chapter 1). Proof theory (Chapter 2) shows that syntactic deduction (\( \vdash \)) matches semantic entailment (\( \models \)) — the completeness theorem. Model theory (Chapters 3 and 6) explores the space of all structures satisfying a theory: how many are there, how do they relate, what can be expressed? Set theory (Chapter 4) provides the foundational framework and exhibits independence results. Computability (Chapter 5) bounds what can be proved or even defined.

The central theorems and their dependencies:

8.2 Key Examples Revisited

Dense linear orders without endpoints (DLO):

• Axioms: linear order + density + no endpoints.
• Model: \( (\mathbb{Q}, <) \) — the unique countable model up to isomorphism.
• Complete by Vaught’s test (\( \aleph_0 \)-categorical).
• Admits quantifier elimination (definable sets are Boolean combinations of intervals).
• Unstable (the order relation witnesses the order property).

Algebraically closed fields of characteristic \( p \) (\( \mathrm{ACF}_p \)):

• Complete, \( \kappa \)-categorical for all uncountable \( \kappa \).
• Admits quantifier elimination (definable sets = constructible sets).
• Strongly minimal (algebraic closure provides a well-behaved pregeometry).
• Stable (in fact \( \omega \)-stable).

Peano Arithmetic (PA):

• Intended model: \( (\mathbb{N}, 0, S, +, \cdot) \).
• Has many non-isomorphic countable models (non-standard models).
• Incomplete (Gödel) and undecidable.
• Not finitely axiomatizable.

ZFC:

• Axiomatizes set theory. Has models of all infinite cardinalities (Löwenheim–Skolem), including countable ones (Skolem’s paradox).
• Cannot prove its own consistency (Second Incompleteness Theorem).
• Independent statements: CH, large cardinal axioms, many others.

8.3 Proof-Theoretic Ordinals and Gentzen’s Consistency Proof

While PA cannot prove \( \mathrm{Con}(\text{PA}) \), Gentzen (1936) gave a finitistic proof of PA’s consistency using transfinite induction up to the ordinal \( \epsilon_0 = \omega^{\omega^{\omega^{\cdots}}} \) (the least ordinal \( \alpha \) with \( \omega^\alpha = \alpha \)). This shows that the “proof-theoretic ordinal” of PA is \( \epsilon_0 \). The proof-theoretic ordinals of stronger theories are correspondingly larger.

Chapter 9: Selected Worked Problems

9.1 Proving Elementary Equivalence

Problem. Show that \( (\mathbb{Q}, <) \equiv (\mathbb{Q}+\mathbb{Q}, <) \) where \( \mathbb{Q} + \mathbb{Q} \) denotes two disjoint copies of \( \mathbb{Q} \), ordered so all elements of the first copy precede all elements of the second.

Solution. Both structures are dense linear orders without endpoints: \( \mathbb{Q} + \mathbb{Q} \) is a dense linear order (between any two points in the same copy or across copies there are intermediate points) without endpoints. Since \( \mathrm{DLO} \) is complete, all its models are elementarily equivalent. So \( (\mathbb{Q}, <) \equiv (\mathbb{Q}+\mathbb{Q}, <) \). Note they are not isomorphic: \( \mathbb{Q} \) has countably many points and is connected in the Dedekind sense, while \( \mathbb{Q}+\mathbb{Q} \) has a “gap”. But first-order logic cannot detect such a gap.

9.2 Applying Compactness

Problem. Let \( \{G_n : n \geq 1\} \) be groups where each \( G_n \) has an element of order exactly \( n \). Show that there is a group \( G \) in which every element has infinite order.

Solution. Let \( T_{\mathrm{grp}} \) be the group axioms and for each \( n \geq 2 \), let \( \varphi_n = \forall x\, (x^n \neq e) \) (no element of order dividing \( n \)). Let \( \Phi = T_{\mathrm{grp}} \cup \{\varphi_n : n \geq 2\} \). Given any finite subset \( \Phi_0 \), the largest \( n \) appearing is some \( N \). Take the free abelian group \( \mathbb{Z} \); every nonidentity element has infinite order, so \( \mathbb{Z} \models \Phi_0 \). By compactness, \( \Phi \) is satisfiable. Any model \( G \models \Phi \) has no element of any finite order \( \geq 2 \), and since \( \varphi_1 \) (no element of order 1 except the identity) follows from group axioms, every nonidentity element has infinite order.

9.3 Non-Standard Analysis

Problem. Using compactness, show the existence of a proper extension \( {}^*\mathbb{R} \) of \( \mathbb{R} \) in the language of ordered fields with a new constant \( c \) satisfying \( c > 0 \) and \( c < \overline{r} \) for every \( r > 0 \) in \( \mathbb{R} \).

Solution. Let \( T = \mathrm{Th}(\mathbb{R}) \cup \{c > 0\} \cup \{c < \overline{r} : r \in \mathbb{R}, r > 0\} \). For any finite subset, take \( r_{\min} = \min\{r : c < \overline{r} \in \Phi_0\} > 0 \), and interpret \( c \) as \( r_{\min}/2 \). By compactness, \( T \) has a model \( {}^*\mathbb{R} \). The element \( c^{{}^*\mathbb{R}} \) is an infinitesimal — positive but smaller than every positive real. Since \( {}^*\mathbb{R} \models \mathrm{Th}(\mathbb{R}) \), it satisfies all first-order truths about \( \mathbb{R} \) (Transfer Principle), providing the foundation for Abraham Robinson’s non-standard analysis.

9.4 A Fixed Point for the Diagonal Lemma

Problem. Exhibit concretely the Gödel sentence for the theory \( T = \mathrm{PA} \).

Solution. We outline the construction:

1. Fix a Gödel numbering of PA-formulas. Let \( \mathrm{Prov}(x) \) be the PA-formula representing provability (a \( \Sigma^0_1 \) formula).

2. Consider \( \psi(y) = \lnot \mathrm{Prov}(y) \). Let \( \theta(x) = \lnot \mathrm{Prov}(\mathrm{Sub}(x,x)) \) where \( \mathrm{Sub}(x,x) \) represents the substitution operation on Gödel numbers.

3. Let \( m = \ulcorner \theta(v_0) \urcorner \) (the Gödel number of \( \theta \) with free variable \( v_0 \)).

4. The Gödel sentence is \( G = \theta(\overline{m}) = \lnot \mathrm{Prov}(\overline{\mathrm{sub}(m,m)}) \).

   Since \( \mathrm{sub}(m,m) = \ulcorner G \urcorner \), we have \( G = \lnot \mathrm{Prov}(\ulcorner G \urcorner) \).

5. \( G \) is true in \( \mathbb{N} \): if PA \( \vdash G \), then \( \mathbb{N} \models \mathrm{Prov}(\ulcorner G \urcorner) \), giving \( \mathbb{N} \models \lnot G \), contradiction. So PA \( \not\vdash G \), and this is exactly what \( G \) says.

9.5 Uncountable Models of Complete Theories

Problem. Show that every complete theory with an infinite model has models of every infinite cardinality.

Solution. Let \( T \) be a complete theory with infinite model \( \mathfrak{A} \). Since \( \mathfrak{A} \) is infinite, it has cardinality \( \kappa \geq \aleph_0 \). By the upward Löwenheim–Skolem theorem, for any \( \lambda > \kappa \), \( T \) has a model of cardinality \( \lambda \). (The argument: add \( \lambda \) new constants, the resulting theory is satisfiable by compactness and the infiniteness of \( \mathfrak{A} \).) For \( \aleph_0 \leq \lambda < \kappa \): by the downward Löwenheim–Skolem theorem applied to \( \mathfrak{A} \), there is an elementary substructure of cardinality \( \lambda \) (choose any \( \lambda \) elements as a base set and take its Skolem hull). This elementary substructure also models \( T \).

Appendix A: Background on Orders and Algebra

A.1 Well-Orderings and Zorn’s Lemma

Zorn’s Lemma is equivalent to the Axiom of Choice and to the Well-Ordering Theorem: every set can be well-ordered. It is used critically in the proof of the Completeness Theorem (extending consistent sets to maximally consistent sets).

A.2 Boolean Algebras and Stone Duality

Application. The Lindenbaum–Tarski algebra of a theory \( T \) (formulas modulo \( T \)-provable equivalence) is a Boolean algebra. The corresponding Stone space is the type space \( S_0(T) \) — the space of complete types (= complete theories extending \( T \)). A type is isolated iff the corresponding point is isolated in the Stone space. The Omitting Types Theorem says that non-isolated types need not be realized in the prime model.

A.3 Ramsey Theory and 0-1 Laws

This connects model theory with combinatorics and probability: the Fraïssé limit of the class of all finite graphs (the Rado graph) is the almost-sure limit of the random graph model.

Appendix B: Quick Reference

B.1 Key Definitions at a Glance

B.2 Standard Theories and Their Properties

B.3 The Gödel Sentences — Summary

Let \( T \) be a consistent recursively axiomatizable extension of \( Q \).

• \( G_T \): the Gödel sentence, with \( T \vdash G_T \leftrightarrow \lnot \mathrm{Prov}_T(\ulcorner G_T \urcorner) \).

  • \( T \not\vdash G_T \) and \( T \not\vdash \lnot G_T \) (First Incompleteness).
  • \( \mathbb{N} \models G_T \) (the standard model sees \( G_T \) as true).

• \( \mathrm{Con}(T) = \lnot \mathrm{Prov}_T(\ulcorner \bot \urcorner) \): consistency statement.

  • \( T \not\vdash \mathrm{Con}(T) \) (Second Incompleteness).
  • \( T + \mathrm{Con}(T) \) is a strictly stronger consistent theory.

• Relationship: \( T \vdash G_T \leftrightarrow \mathrm{Con}(T) \) (the Gödel sentence is equivalent to consistency over \( T \), essentially).

Appendix C: Computability Theory Primer

This appendix develops the computability-theoretic background that underpins Chapters 5 and 7 in more detail. The reader who has seen the informal account in Chapter 5 will benefit from the formal definitions and classical theorems collected here.

C.1 Primitive Recursive Functions — Complete Development

The primitive recursive functions constitute the “safe” core of computability: every primitive recursive function terminates, and all basic arithmetic operations lie within this class. They are built from three base functions by two closure operations.

Base functions:

1. Zero function: \( Z : \mathbb{N} \to \mathbb{N} \), \( Z(n) = 0 \).
2. Successor function: \( S : \mathbb{N} \to \mathbb{N} \), \( S(n) = n + 1 \).
3. Projection functions: \( \pi^k_i : \mathbb{N}^k \to \mathbb{N} \), \( \pi^k_i(n_1, \ldots, n_k) = n_i \) for \( 1 \leq i \leq k \).

Closure operations:

1. Composition: If \( g : \mathbb{N}^m \to \mathbb{N} \) and \( h_1, \ldots, h_m : \mathbb{N}^k \to \mathbb{N} \) are primitive recursive, then so is \( f(\vec{n}) = g(h_1(\vec{n}), \ldots, h_m(\vec{n})) \).
2. Primitive recursion: If \( g : \mathbb{N}^k \to \mathbb{N} \) and \( h : \mathbb{N}^{k+2} \to \mathbb{N} \) are primitive recursive, then so is \( f \) defined by:

C.2 Partial Recursive Functions and the \( \mu \)-Operator

The \( \mu \)-operator introduces potential non-termination: if \( g(\vec{n}, m) \neq 0 \) for all \( m \), then \( f(\vec{n}) \) is undefined. This is the key distinction between primitive and general recursive functions.

The Normal Form Theorem is a fundamental uniformization result: every partial recursive function has a “standard” representation using a single application of \( \mu \) to a primitive recursive predicate. This allows the set of partial recursive functions to be indexed by natural numbers (the index \( e \) is an “program” or “Gödel number” for \( f \)).

Consequences:

• Every partial recursive function \( f \) has an index \( e \) with \( f = \phi_e \) (the \( e \)-th partial recursive function under the standard indexing).
• The function \( (e, \vec{n}) \mapsto \phi_e(\vec{n}) \) is partial recursive (computable by the universal Turing machine).
• There are only countably many partial recursive functions (indexed by \( \mathbb{N} \)).

C.3 The \( s\text{-}m\text{-}n \) Theorem (Parameter Theorem)

Informally: given a program \( e \) for an \( (m+n) \)-ary function, and given \( m \) fixed inputs \( x_1, \ldots, x_m \), the \( s\text{-}m\text{-}n \) theorem produces the index of an \( n \)-ary program that runs \( e \) with the first \( m \) inputs already “baked in.” This is partial function application or currying — a fundamental operation in programming languages.

Example. Fix \( e \) and \( x \). The function \( y \mapsto \phi_e(x, y) \) is a partial recursive function of \( y \) alone. By \( s\text{-}1\text{-}1 \), its index is \( s^1_1(e, x) \), computable from \( e \) and \( x \) by a primitive recursive procedure. This is the theoretical foundation for closures in functional programming.

Application to the Fixed-Point (Recursion) Theorem. The \( s\text{-}m\text{-}n \) theorem implies the Kleene Recursion Theorem: for every total recursive function \( f \), there exists \( n \) with \( \phi_{f(n)} = \phi_n \). That is, every computable transformation of programs has a “fixed point” program. The Diagonal Lemma in logic is the syntactic analogue of this theorem.

C.4 Rice’s Theorem

One of the most powerful undecidability results is Rice’s theorem, which says that no non-trivial behavioral property of programs is decidable.

Appendix D: Background on Orders and Algebra

D.1 Well-Orderings and Zorn’s Lemma

(See Appendix A.1 above.)

Problem Set: PMATH 432 Comprehensive Exercises

The following twenty problems are organized into five parts, covering the full scope of the course. Problems are designed to build understanding progressively within each part.

Part A: Syntax — Parsing and Classifying Formulas

A1. Consider the signature \( \sigma = (\{f, c\}, \{R\}, \mathrm{ar}) \) where \( \mathrm{ar}(f) = 2 \), \( \mathrm{ar}(c) = 0 \), \( \mathrm{ar}(R) = 2 \). Determine whether each of the following is a term, an atomic formula, a formula but not atomic, or not a well-formed expression. Justify each answer by reference to the inductive definition.

1. \( f(c, x) \)
2. \( R(f(c,c), x) \)
3. \( \forall x\, R(x, f(x,c)) \)
4. \( R(x) \)
5. \( f(R(x,y), c) \)

A2. For each formula below, compute \( \mathrm{free}(\varphi) \) (the set of free variables) using the formal inductive definition. Then classify the formula as a sentence or non-sentence, and if non-sentence, state what mathematical claim it makes about the free variables.

1. \( \varphi_1 = \exists x\, (x < y \land \forall z\, (z < x \to z < y)) \) (in the signature of linear orders).
2. \( \varphi_2 = \forall x\, \forall y\, (x \cdot y \doteq y \cdot x) \) (in the signature of rings).
3. \( \varphi_3 = \exists z\, (x \cdot z \doteq y) \) (in the signature of groups).
4. \( \varphi_4 = \forall x\, (P(x) \to \exists y\, (Q(x,y) \land \lnot Q(y,x))) \) (in a relational signature).

A3. Let \( \sigma_{\mathrm{grp}} = (\{\cdot, e, {}^{-1}\}, \emptyset) \) be the group signature. Write the following group-theoretic statements as first-order \( \sigma_{\mathrm{grp}} \)-sentences:

1. The group is abelian.
2. Every element has order dividing 6 (i.e., \( x^6 = e \) for all \( x \)).
3. There exists an element of order exactly 2.
4. The group has no element of finite order except the identity (a torsion-free group).

A4. Suppose \( \varphi(x, y) \) is a formula with exactly \( \mathrm{free}(\varphi) = \{x, y\} \). Define:

1. Compute \( \mathrm{free}(\psi) \).
2. Suppose we attempt the substitution \( \psi[y/x] \) (replacing \( x \) by \( y \)). Explain what variable capture might occur and how to avoid it.
3. State the formal definition of "\( t \) is free for \( x \) in \( \varphi \)" and check whether \( y \) is free for \( x \) in \( \psi \).
4. Perform the substitution \( \varphi(x,y)[z/x] \) (replacing \( x \) by the fresh variable \( z \)) and state the result.

Part B: Semantics — Computing Truth in Specific Structures

B1. Let \( \mathfrak{A} = (\{0,1,2\}, <^{\mathfrak{A}}) \) be the structure with universe \( \{0,1,2\} \) and \( <^{\mathfrak{A}} = \{(0,1),(0,2),(1,2)\} \) (the standard ordering on \( \{0,1,2\} \)). Evaluate each sentence as true or false in \( \mathfrak{A} \), writing out the semantic computation step by step.

1. \( \forall x\, \exists y\, (x < y) \).
2. \( \exists x\, \forall y\, (y < x \lor y \doteq x) \).
3. \( \forall x\, \forall y\, (x < y \to \exists z\, (x < z \land z < y)) \).
4. \( \forall x\, \forall y\, (x < y \lor y < x \lor x \doteq y) \).

B2. Let \( \mathfrak{Z} = (\mathbb{Z}, 0, S, +, \cdot) \) where \( S(n) = n+1 \) (the integers as a model of the arithmetic signature \( \{0, S, +, \cdot\} \)). Note that \( \mathfrak{Z} \) is NOT a model of PA (the induction axiom fails). For each sentence:

1. \( \forall x\, \exists y\, (y + y \doteq x) \) — does this hold in \( \mathfrak{Z} \)? Does it hold in \( \mathfrak{N} \)?
2. \( \exists x\, (x + x \doteq S(0)) \) — in \( \mathfrak{Z} \)? In \( \mathfrak{N} \)?
3. \( \forall x\, \exists y\, (x + y \doteq 0) \) — in \( \mathfrak{Z} \)? In \( \mathfrak{N} \)?

B3. Let \( T = \mathrm{DLO} \) (the theory of dense linear orders without endpoints). Determine whether each of the following is a consequence of \( T \) (true in all models of \( T \)), consistent with \( T \) (true in some model), or inconsistent with \( T \) (false in all models).

1. \( \exists x\, \exists y\, (x < y \land \lnot \exists z\, (x < z \land z < y)) \).
2. \( \forall x\, \forall y\, (x < y \to \exists z\, (x < z \land z < y)) \).
3. \( \forall x\, \exists y\, (y < x) \land \forall x\, \exists y\, (x < y) \).
4. \( \exists x\, \forall y\, (x < y) \) (there is a minimum element).

B4. Let \( \mathrm{ACF}_0 \) be the theory of algebraically closed fields of characteristic 0. For each sentence, determine whether it is a consequence of \( \mathrm{ACF}_0 \) (provable from \( \mathrm{ACF}_0 \)), its negation is a consequence, or it is independent (neither provable nor refutable). Justify using the completeness of \( \mathrm{ACF}_0 \) and properties of \( \mathbb{C} \).

1. \( \forall x\, \exists y\, (y \cdot y \doteq x) \) (every element has a square root).
2. \( \forall x\, (x \cdot x \doteq x \to x \doteq 0 \lor x \doteq 1) \).
3. \( \exists x\, (x \cdot x \doteq -1) \) (where \( -1 \) abbreviates \( 0 - 1 \)).
4. The field has exactly 4 elements (a sentence asserting \( |F| = 4 \)).

Part C: Proofs — Derivations in the Proof System

C1. Using the Hilbert calculus (with the deduction theorem available as a metatheorem), give a derivation (or derivation sketch with all key steps justified) of each of the following:

1. \( \vdash \varphi \to \varphi \) (reflexivity of implication).
2. \( \varphi \to \psi, \psi \to \chi \vdash \varphi \to \chi \) (hypothetical syllogism).
3. \( \vdash \lnot \lnot \varphi \to \varphi \) (double negation elimination — use the contrapositive axiom).
4. \( \vdash (\varphi \to \psi) \to (\lnot \psi \to \lnot \varphi) \) (contrapositive).

C2. Using the quantifier axioms and the deduction theorem, derive:

1. \( \forall x\, \forall y\, \varphi(x,y) \vdash \forall y\, \forall x\, \varphi(x,y) \) (swapping the order of universal quantifiers).
2. \( \exists x\, \varphi(x) \vdash \exists x\, (\varphi(x) \lor \psi(x)) \) for any formula \( \psi \).
3. Explain why \( \exists x\, \varphi(x) \lor \exists x\, \psi(x) \vdash \exists x\, (\varphi(x) \lor \psi(x)) \), and whether the converse holds.

C3. Let \( T \) be a theory and \( \varphi, \psi \) sentences. Prove each claim from the semantic and syntactic definitions:

1. If \( T \vdash \varphi \) and \( T \vdash \varphi \to \psi \), then \( T \vdash \psi \). (Modus Ponens is admissible from premises.)
2. If \( T \cup \{\varphi\} \vdash \bot \), then \( T \vdash \lnot \varphi \). (Proof by contradiction.)
3. If \( T \vdash \varphi \) and \( T' \supseteq T \), then \( T' \vdash \varphi \). (Monotonicity of provability.)
4. \( T \models \varphi \iff T \cup \{\lnot \varphi\} \) is unsatisfiable. (The semantic version of "proof by contradiction.")

C4. The Deduction Theorem states: \( \Phi \cup \{\psi\} \vdash \varphi \iff \Phi \vdash \psi \to \varphi \) (under the appropriate conditions on generalization). Use the Deduction Theorem to:

1. Show that \( \varphi \to \psi, \lnot \varphi \to \psi \vdash \psi \) (proof by cases).
2. Show that if \( \varphi \vdash \psi \) and \( \varphi \vdash \lnot \psi \), then \( \vdash \lnot \varphi \).
3. State carefully the condition on the generalization rule that must hold for the Deduction Theorem to apply. Give an example where the theorem fails if this condition is violated.

Part D: Completeness and Compactness — Applications

D1. Use the Compactness Theorem to prove each of the following:

1. If \( \Phi \models \varphi \), then some finite \( \Phi_0 \subseteq \Phi \) satisfies \( \Phi_0 \models \varphi \). (Compactness for entailment.)
2. If every finite subgraph of an infinite graph \( G \) is 3-colorable, then \( G \) is 3-colorable. (Graph coloring, see Worked Example 2.3.)
3. If a sentence \( \varphi \) is true in all finite structures of signature \( \sigma \), is \( \varphi \) necessarily true in all infinite structures? Prove or give a counterexample.

D2. Let \( T \) be the theory of torsion-free abelian groups (groups satisfying \( \forall x\, (x^n \neq e) \) for all \( n \geq 1 \), written as an infinite set of sentences). Use compactness to show:

1. \( T \) has no finite models.
2. There is no single first-order sentence \( \varphi \) such that a group satisfies \( \varphi \) iff it is torsion-free.
3. Every model of \( T \) contains an isomorphic copy of \( \mathbb{Z} \).

D3. Recall that the Löwenheim–Skolem theorems are consequences of compactness.

1. Using compactness directly (not the Downward Löwenheim–Skolem theorem), show that if a theory \( T \) has an infinite model, it has a model of cardinality at least \( \kappa \) for every infinite cardinal \( \kappa \).
2. The theory \( \mathrm{PA} \) (Peano arithmetic) has its intended model \( \mathfrak{N} = (\mathbb{N}, 0, S, +, \cdot) \). Using compactness, show that PA has a model containing an element \( c \) greater than \( \overline{n} = S^n(0) \) for every standard natural number \( n \). Such an element is called non-standard.
3. Show that any non-standard model of PA also contains non-standard elements below any given non-standard element (i.e., non-standard numbers are "dense" in a suitable sense).

D4. The Transfer Principle in non-standard analysis says: a first-order sentence is true in \( \mathbb{R} \) iff it is true in \( {}^*\!\mathbb{R} \). Use this to give a non-standard proof sketch of:

1. The intermediate value theorem: if \( f : [a,b] \to \mathbb{R} \) is continuous and \( f(a) < 0 < f(b) \), then \( f(c) = 0 \) for some \( c \in (a,b) \). (Sketch: use infinitesimals to argue about the "first sign change.")
2. Explain what "continuity" means in the language of non-standard analysis (using infinitesimals) and why this formulation is equivalent to the standard \( \varepsilon\text{-}\delta \) definition for first-order expressible properties.
3. What is a fundamental obstacle to using non-standard analysis to prove results that are not first-order expressible? Give an example.

Part E: Computability and Gödel — Challenge Problems

E1. Let \( \mathrm{Prov}_T(x) \) be the provability predicate for a recursively axiomatizable theory \( T \) extending PA. The Löb conditions are:

• (D1) If \( T \vdash \varphi \), then \( T \vdash \mathrm{Prov}_T(\ulcorner \varphi \urcorner) \).
• (D2) \( T \vdash \mathrm{Prov}_T(\ulcorner \varphi \to \psi \urcorner) \land \mathrm{Prov}_T(\ulcorner \varphi \urcorner) \to \mathrm{Prov}_T(\ulcorner \psi \urcorner) \).
• (D3) \( T \vdash \mathrm{Prov}_T(\ulcorner \varphi \urcorner) \to \mathrm{Prov}_T(\ulcorner \mathrm{Prov}_T(\ulcorner \varphi \urcorner) \urcorner) \).

1. Show that (D1) implies: if \( T \vdash \varphi \land \psi \), then \( T \vdash \mathrm{Prov}_T(\ulcorner \varphi \urcorner) \land \mathrm{Prov}_T(\ulcorner \psi \urcorner) \).
2. Using the Löb conditions and the Diagonal Lemma, give a complete proof of Löb's Theorem: if \( T \vdash \mathrm{Prov}_T(\ulcorner \varphi \urcorner) \to \varphi \), then \( T \vdash \varphi \).
3. Deduce the Second Incompleteness Theorem from Löb's Theorem by showing \( T \vdash \mathrm{Con}(T) \to G_T \) where \( G_T \) is the Gödel sentence.

E2. The Arithmetical Hierarchy classifies sets by their logical complexity.

1. Show that the set \( \mathrm{Halt} = \{(e, n) : \phi_e(n) \downarrow\} \) is \( \Sigma^0_1 \) (computably enumerable) but not \( \Pi^0_1 \) (not co-computably enumerable). Use this to give a direct proof that \( \mathrm{Halt} \) is not decidable.
2. Show that the set of indices of total functions, \( \mathrm{Tot} = \{e : \phi_e \text{ is a total function}\} \), is \( \Pi^0_2 \) (of the form \( \forall n\, \exists s\, R(e, n, s) \) for a decidable \( R \)) but not \( \Sigma^0_2 \).
3. State Rice's Theorem and use it to prove that \( \mathrm{Tot} \) is not decidable (without computing its arithmetical complexity).

E3. This problem concerns the relationship between syntax (provability) and semantics (truth).

1. The Completeness Theorem says \( T \models \varphi \iff T \vdash \varphi \). The First Incompleteness Theorem says: for consistent, recursively axiomatizable \( T \supseteq Q \), there exists \( \varphi \) with \( \mathbb{N} \models \varphi \) but \( T \not\vdash \varphi \). Reconcile these two results — are they contradictory?
2. Exhibit a sentence \( \varphi \) such that \( \mathrm{PA} \not\vdash \varphi \) and \( \mathrm{PA} \not\vdash \lnot \varphi \), yet \( \varphi \) is true in \( \mathbb{N} \). (The Gödel sentence works — verify that \( G \) is true in \( \mathbb{N} \) by the argument in Section 5.4.2.)
3. A non-standard model \( \mathfrak{M} \) of PA (i.e., \( \mathfrak{M} \models \mathrm{PA} \) but \( \mathfrak{M} \not\cong \mathfrak{N} \)) satisfies all PA-theorems but may fail true arithmetic sentences. Explain why \( \mathfrak{M} \models \lnot G_{\mathrm{PA}} \) for a non-standard \( \mathfrak{M} \) that happens to be a model of \( \mathrm{PA} + \lnot G_{\mathrm{PA}} \) (the existence of which follows from Gödel's theorems).

E4. This problem concerns Tarski’s undefinability theorem and its relationship to the Liar Paradox.

1. State Tarski's Undefinability Theorem precisely and give its proof via the Diagonal Lemma.
2. The **Liar sentence** in natural language is "This sentence is false." Explain how Tarski's theorem is the formal mathematical version of this paradox, and why the resolution is not a contradiction in mathematics but rather a theorem about the limits of definability.
3. Is there a formula \( \mathrm{True}_{\mathrm{prop}}(x) \) in propositional logic that defines truth for propositional formulas? Explain why this case is different from the first-order arithmetic case, using the fact that propositional tautologies are decidable.
4. The **T-schema** (Tarski's truth condition) says: \( \ulcorner \varphi \urcorner \) is true iff \( \varphi \). Explain why adopting the T-schema for all \( \varphi \) in the same language leads to inconsistency (the Liar paradox), and what Tarski's hierarchical solution is.

End of Problem Set.

Appendix E: Quick Reference

B.1 Key Definitions at a Glance

B.2 Standard Theories and Their Properties

B.3 The Gödel Sentences — Summary

Let \( T \) be a consistent recursively axiomatizable extension of \( Q \).

• \( G_T \): the Gödel sentence, with \( T \vdash G_T \leftrightarrow \lnot \mathrm{Prov}_T(\ulcorner G_T \urcorner) \).

  • \( T \not\vdash G_T \) and \( T \not\vdash \lnot G_T \) (First Incompleteness).
  • \( \mathbb{N} \models G_T \) (the standard model sees \( G_T \) as true).

• \( \mathrm{Con}(T) = \lnot \mathrm{Prov}_T(\ulcorner \bot \urcorner) \): consistency statement.

  • \( T \not\vdash \mathrm{Con}(T) \) (Second Incompleteness).
  • \( T + \mathrm{Con}(T) \) is a strictly stronger consistent theory.

• Relationship: \( T \vdash G_T \leftrightarrow \mathrm{Con}(T) \) (the Gödel sentence is equivalent to consistency over \( T \), essentially).

Appendix F: Supplementary Enrichment

This appendix collects enrichment material filling gaps identified after the main chapters were written. It is self-contained and cross-references the relevant sections above.

F.1 Parse Tree Example: A More Complex Formula

The worked example in Section 1.2.3 parsed the relatively simple sentence \( \forall x\, \exists y\, (x < y) \). Here we work through a more challenging formula that arises naturally in the study of ordered fields and dense orders.

Consider the formula

in the signature \( \sigma_{\mathrm{of}} = (\{+, \cdot, -, 0, 1\}, \{<\}) \) of ordered fields, where \( x + 1 \) abbreviates \( +(x, 1) \) and \( x < y \) abbreviates the relation \( <(x, y) \). This sentence expresses “between every element and its successor there exists another element” — the characteristic property of dense orders.

            forall x
               |
            exists y
               |
            (wedge)
            /      \
         x < y    y < (x+1)
                      |
               R(<, y, +(x,1))
                          |
                       +(x, 1)
                        /    \
                       x      1

F.2 The Lowenheim-Skolem Paradox — Extended Discussion

Section 3.2 stated the Skolem paradox as a brief corollary. The phenomenon is philosophically important and deserves fuller treatment, as it is one of the most striking consequences of the Lowenheim-Skolem theorems.

The downward Lowenheim-Skolem theorem applied to ZFC says: if ZFC is consistent, it has a countable model \( \mathfrak{M} = (M, E) \). There exists a countable set \( M \) and a binary relation \( E \subseteq M \times M \) such that \( (M, E) \models \mathrm{ZFC} \). Since ZFC proves “there exist uncountable sets,” we have \( (M, E) \models \exists x\, \lnot \exists f\, (f \text{ is a bijection from } \omega \text{ to } x) \). But \( M \) is countable. This is Skolem’s Paradox.

F.3 Turing Machines — Formal Definition and Worked Example

Chapter 5 used Turing machines informally. Here we give the formal definition and trace through the canonical worked example of unary incrementing.

F.3.1 Formal Definition

For computing \( \mathbb{N} \to \mathbb{N} \), we use unary encoding: \( n \) is encoded as \( 1^n \) (a run of \( n \) ones). The tape alphabet is \( \{1, \sqcup\} \).

F.3.2 Worked Example: Unary Increment (\( n \mapsto n+1 \))

Step 0: q₀ at cell 0. Read 1 → write 1, R → q₀. Tape: 1 1 1 □ □ …
Step 1: q₀ at cell 1. Read 1 → write 1, R → q₀. Tape: 1 1 1 □ □ …
Step 2: q₀ at cell 2. Read 1 → write 1, R → q₀. Tape: 1 1 1 □ □ …
Step 3: q₀ at cell 3. Read □ → write 1, R → q_acc. Tape: 1 1 1 1 □ …  [ACCEPT]

F.3.3 Church-Turing Equivalence

This equivalence (proved by Kleene, Turing, and Church in 1935–1936) justifies treating the two notions interchangeably. The Church-Turing Thesis extends this: every effectively computable function (in the informal sense) is Turing-computable. This thesis is a philosophical principle, not a theorem, but is universally accepted.

The thesis plays a crucial role in mathematical logic: the provability predicate \( \mathrm{Prov}_T(x) \) (Chapter 5) is representable in PA because “checking whether a finite sequence of formulas is a valid proof” is effectively computable — by the Church-Turing thesis it is Turing-computable, hence partial recursive, hence representable.

F.4 Historical Note: Godel in 1930-1931

Kurt Godel was born on April 28, 1906, in Brunn (now Brno, Czech Republic). He completed his doctoral dissertation at the University of Vienna in 1929 at age 23, proving the Completeness Theorem. The following year, at age 24, he announced and published the incompleteness theorems.

He made the announcement at the Second Conference on the Epistemology of the Exact Sciences in Konigsberg, September 1930. Hilbert gave a triumphant address asserting the achievability of mathematical completeness; shortly after, Godel quietly stated he had found a true arithmetic sentence unprovable in Principia Mathematica. John von Neumann, present at the conference, immediately grasped the result’s significance and within weeks independently derived the Second Incompleteness Theorem — only to learn that Godel had already done so.

The full paper, “Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I,” was published in the Monatshefte fur Mathematik und Physik in 1931. It is widely regarded as the most important single paper in mathematical logic.

End of Appendix F.