Math 557 Sep 12

Consistency and Completeness

Key Concepts

  • Consistency:
    A theory \(T\) is consistent if there does not exist a formula \(\psi\) such that \(T \vdash \psi\) and \(T \vdash \neg \psi\).

  • Completeness:
    A theory \(T\) is complete if it is consistent and for every sentence \(\sigma\), \(T \vdash \sigma\) or \(T \vdash \neg \sigma\).

  • In a complete theory, every statement is determined, in the sense that is either true or false in the theory.

  • An important example of a complete theory is the theory of a fixed structure \(\mathcal{M}\),

\[\operatorname{Th}(\mathcal{M}) = \{ \sigma \colon \mathcal{M} \models \sigma \}\]

  • If, on the other hand, we are given a complete theory \(T\), does \(T\) have a model? This is the subject of the Completeness Theorem. It actually shows that any consistent theory has a model.

Problems

Exercise 1 (Carry-over from Sep 10)
Prove the Soundness Theorem, i.e. show that

\[T \vdash \varphi \; \Rightarrow \; T \models \varphi\]

Exercise 2
Why is the theory of a structure, \(\operatorname{Th}(\mathcal{M})\), indeed a complete theory?

Exercise 3
Show that a theory \(T\) is inconsistent iff for every formula \(\psi\), \(T \vdash \psi\)

Exercise 4
For each of the following classes \(\mathbf{K}\) of structures, determine whether they are axiomatizable, i.e. whether there exists a theory \(T\) (in the language of the structures) such that

\[\mathbf{K} = \{ \mathcal{M} \colon \mathcal{M} \models T \}\]

(In this case \(K\) is also called elementary.)

If \(\mathbf{K}\) is axiomatizable, discuss whether it is actually finitely axiomatizable (i.e. can \(T\) be chosen finite). And is \(T\) complete?

  • \(\mathbf{K} =\) Abelian groups
  • \(\mathbf{K} =\) infinite sets
  • \(\mathbf{K} =\) fields of characteristic \(p\) (\(p\) prime)
  • \(\mathbf{K} =\) bipartite graphs
  • \(\mathbf{K} =\) torsion groups (all elements have finite order)
  • \(\mathbf{K} =\) algebraically closed fields of characteristic \(0\)

(Note: We do not yet have the tools to rigorously answer all these questions, but try an “educated” guess.)

Exercise 5
Suppose that \(T \cup \{\neg\varphi\}\) is inconsistent. Show that \(T \vdash \varphi\).

(This is a technical formulation of the legitimacy of proofs by contradiction.)