Math 557 Sep 15

The Completeness Theorem

Key Concepts

• The Completeness Theorem states that

\[T \vdash_{\mathcal{L}} \varphi \; \iff \; T \models \varphi\]

• The \(\Rightarrow\)-direction is Soundness, which we already proved.

• The \(\Leftarrow\)-direction is usually proved in the following form:

   If \(T\) is consistent, then \(T\) has a model.

• To construct a model of a consistent theory, we consider the constant terms \[K := \{ t \colon t \; \mathcal{L}\text{-term without variables}\}\] and identify provably equal terms: \[s \sim t \; :\iff \; T \vdash_{\mathcal{L}} s = t\]

• The canonical term structure \(\mathcal{A}\) of \(T\) has universe \(A = K/\sim\).

• Moreover, we put

  • \(c^{\mathcal{A}} := [c]\)
  • \(f^{\mathcal{A}}([t_1], \dots, [t_n]) := [ft_1\dots t_n]\)
  • \(R^{\mathcal{A}}([t_1], \dots, [t_n]) \; : \iff \; T \vdash_{\mathcal{L}} Rt_1\dots t_n\)

• It holds that for any atomic sentence \(\sigma\), \[\mathcal{A} \models \sigma \quad \iff \quad T \vdash \sigma\]

Problems

Discuss

We all believe (I think) that \((\mathbb{Z}, +, 0)\) is a model of the group axioms. To what extent does this prove that the group axioms are consistent?

Exercise 1
Verify that \(\sim\) is an equivalence relation.

Exercise 2
Verify that the definition of \(c^{\mathcal{A}}, f^{\mathcal{A}}, R^{\mathcal{A}}\) does not depend on the choice of representative for \([c]\) and \([t_i]\).

Exercise 3
Verify the claim that for atomic sentences, \[\mathcal{A}_T \models \sigma \quad \iff \quad T \vdash \sigma\]