The Lumenary · Advanced undergraduate

Completeness, compactness and Löwenheim–Skolem

Name: ______________________

Date: ______________________

You will learn to

Prove Gödel's completeness theorem for countable languages by a Henkin construction
Derive the compactness theorem, and use it to show that classes such as the finite structures or the torsion groups are not first-order axiomatisable
Construct nonstandard models of arithmetic and ordered fields containing infinitesimals
State and prove the Löwenheim–Skolem theorems via the Tarski–Vaught test, and explain Skolem's paradox
Explain why the completeness theorem and Gödel's incompleteness theorems do not contradict each other

1.
Which statement is Gödel's completeness theorem (as opposed to soundness, or to the incompleteness theorem)?
- A.If $\Gamma \models \varphi$ then $\Gamma \vdash \varphi$
- B.If $\Gamma \vdash \varphi$ then $\Gamma \models \varphi$
- C.For every sentence $\varphi$ , $\Gamma \vdash \varphi$ or $\Gamma \vdash \neg\varphi$
- D.Every true sentence about $\N$ is provable in Peano arithmetic
2.
Which of these classes of structures are first-order axiomatisable (by a possibly infinite set of sentences)? Select all.
- A.Groups
- B.Infinite groups
- C.Finite groups
- D.Torsion groups
- E.Fields of characteristic $0$
- F.Fields of positive characteristic
3.
Colour the numbers $0, 1, \dots, 9$ with $3$ colours so that numbers differing by $1$ or by $2$ get different colours. How many such colourings are there?
4.
In the Henkin proof, why do we add a witness constant $c_\varphi$ and the axiom $\exists x\, \varphi(x) \to \varphi(c_\varphi)$ for every formula $\varphi$ ?
- A.So that in the term model every true existential sentence has a witness named by a closed term
- B.To make the theory complete
- C.To make the language countable
- D.To make equality an equivalence relation on terms
5.
Suppose $T$ axiomatised the torsion groups, and let $\Gamma = T \cup \{c^n \neq e \mid n \ge 1\}$ . Why is every finite subset of $\Gamma$ satisfiable?
- A.It is satisfied by $\Z/(N+1)$ with $c = 1$ , where $N$ bounds the exponents mentioned
- B.It is satisfied by $\Z$ with $c = 1$
- C.It is satisfied by the trivial group
- D.Because $T$ is consistent
6.
Let $M \equiv (\N, 0, 1, +, \times, <)$ contain an element $c$ larger than every numeral. Which statements are true? Select all.
- A. $c$ has a predecessor in $M$
- B. $c$ is even or odd in $M$
- C. $M$ is isomorphic to $\N$
- D.The set of standard elements $\{\overline{n}^M\}$ is definable in $M$ by a formula
- E. $M$ satisfies every axiom of Peano arithmetic, including all induction axioms
7.
A countable model $(M, E)$ of ZFC contains an element $p$ that $M$ believes is $\mathcal P(\omega)$ , and $M \models$ " $p$ is uncountable". Yet $p$ has only countably many $E$ -members. What is the correct resolution?
- A.Bijections between $\omega$ and $p$ exist, but none of them is an element of $M$
- B.ZFC is inconsistent
- C.The Löwenheim–Skolem theorem does not apply to ZFC
- D. $p$ is not really a set of natural numbers
8.
Mathlib defines T.IsFinitelySatisfiable as ∀ T0 : Finset L.Sentence, ↑T0 ⊆ T → (↑T0 : L.Theory).IsSatisfiable. Which Lean statement is the compactness theorem?
- A.T.IsSatisfiable ↔ T.IsFinitelySatisfiable
- B.T.IsSatisfiable ↔ ∀ φ ∈ T, ({φ} : L.Theory).IsSatisfiable
- C.(∃ T0 : Finset L.Sentence, ↑T0 ⊆ T ∧ (↑T0 : L.Theory).IsSatisfiable) → T.IsSatisfiable
- D.T.IsSatisfiable ↔ T.IsComplete
9.
Numbers $i, j$ are joined when $|i - j| \in D$ . Write first_empty_level(k, D, max_n) returning the least $n \le$ max_n such that $\{0, \dots, n - 1\}$ has no proper $k$ -colouring, or None if every $n \le$ max_n has one. (Build the colourings level by level: each proper colouring of $\{0, \dots, n - 1\}$ is extended by a colour for $n$ that differs from the colours of $n - d$ , $d \in D$ .)
Computational — Practice

Answer key — Completeness, compactness and Löwenheim–Skolem

1.
The completeness theorem: $\Gamma \models \varphi \Rightarrow \Gamma \vdash \varphi$ . Soundness is the converse. 'Every sentence is decided' is completeness of a theory, and 'every truth about $\N$ is provable in PA' is false by the incompleteness theorem.
2.
Axiomatisable: groups, infinite groups, fields of characteristic $0$ . Not axiomatisable: finite groups (Theorem 3), torsion groups (Corollary 4) and fields of positive characteristic (add $p \cdot 1 \neq 0$ for all primes $p$ and use compactness with finite fields of large prime order). Note the pattern: 'for every $n$ ' conditions are expressible by infinitely many sentences; 'for some $n$ ' conditions are not.
3.
Numbers $n, n+1, n+2$ are pairwise at distance $1$ or $2$ , so they use all three colours; hence the colour of $n + 3$ equals the colour of $n$ . The colouring is determined by the colours of $0, 1, 2$ , which can be any of the $3! = 6$ arrangements. So there are $6$ — at every level of the colouring tree, which is why König's lemma easily produces a colouring of all of $\N$ here.
4.
The term model consists of (classes of) closed terms. If $\Gamma^*$ contains $\exists x\, \varphi(x)$ , the truth lemma needs a term $t$ with $\varphi(t) \in \Gamma^*$ , so that $[t]$ witnesses the existential in $M$ . The Henkin axioms provide $t = c_\varphi$ . Completeness of $\Gamma^*$ is the separate Lindenbaum step.
5.
A finite $\Gamma_0 \subseteq \Gamma$ contains sentences of $T$ and $c^n \neq e$ only for $n \le N$ . The cyclic group $\Z/(N + 1)$ is a torsion group, hence a model of $T$ , and the element $1$ has order $N + 1$ , so it satisfies $c^n \neq e$ for $n \le N$ . By compactness $\Gamma$ has a model: a torsion group with an element of infinite order — a contradiction, so $T$ does not exist.
6.
True: (a), (b) and (e), since each is (or follows from) a first-order sentence true in $\N$ . False: (c) — an isomorphism would map $\N$ onto the numerals and miss $c$ — and (d): a definable set of nonstandard elements would have a least element by induction, and its predecessor would be standard, whose successor is standard. This 'overspill' phenomenon is a basic tool in the study of nonstandard models.
7.
Inside $M$ , ' $p$ is uncountable' means 'there is no $f \in M$ that is a bijection from $\omega^M$ to $p$ '. From outside, $p$ has countably many members and a bijection exists — but that bijection is not an element of $M$ . So there is no contradiction; Skolem's paradox shows that countability is not absolute between models.
8.
Compactness: T.IsSatisfiable ↔ T.IsFinitelySatisfiable. Pairwise or single-sentence satisfiability is not enough ({φ, ∼φ}), one finite subset is not enough, and satisfiability is not completeness.

def first_empty_level(k, D, max_n):
    level = [()]
    for n in range(max_n):
        nxt = []
        for c in level:
            used = {c[n - d] for d in D if n - d >= 0}
            nxt.extend(c + (col,) for col in range(k) if col not in used)
        if not nxt:
            return n + 1
        level = nxt
    return None

An empty level is a finite reason why the infinite graph on $\N$ cannot be $k$ -coloured. The de Bruijn–Erdős theorem, a consequence of compactness, says that if no level is ever empty, a colouring of all of $\N$ exists — but no finite computation can confirm that 'never'.