3.4. Mathematical theories and Completeness theorem

We first introduced the notion of mathematical theory with detailed explanations in our first text on the foundations of mathematics, especially sections 1.1, 1.3, 1.4, 1.5, 1.6, 1.8, 1.9 and the Platonism vs Formalism subsection.

The main useful formalisms (kinds of theories), from the weakest (less expressive) to the strongest (most expressive), except set theory, are:
We already explained the two most important formalisms : first-order theories (called there «generic theories»), and the formalism of set theory that is specific (with definiteness classes, and binders depending on sets) and escapes this hierarchical order between formalisms, as we described irreversible correspondences between both (not the inverse of each other):
Let us continue this exposition, summing up the content of theories (first mentioned in 1.3) and going further.

The contents of a theory

Once chosen a formalism, a theory is specified by its content (vocabulary and axioms), as follows.

Every theory is made of 3 kinds of components. Each of these 3 kinds of components of a theory, is a finite system built using the previous kind of components :

But for having any interest for most practical purposes, a theory should be such that there cannot exist, built on the above, any of the 4th kind of components:

Let us examine in more details the properties of these concepts of "proof" and "contradictions"

The Completeness Theorem

Let us assume that there is such a thing as proof theory (a system of rules of proof) that will make things fit, so that the existence of a proof of A in T ensures the truth of A in every model of T. The converse property constitutes the Completeness Theorem. That was originally Gödel's thesis, but we are going to present a simplified version of it; it gives model theory its strength, establishing the equivalence between realism and formalism for first-order theories. Proven for a specific system of rules of proof, it makes the concept of provability perfect and independent of the choice of formalism with the same quality:

Completeness Theorem. First-order logic has a proper proving system (a proof theory, with algorithmic verifiability), in the following (equivalent) senses
Sketch of proof of the first statement (making this fact intuitive but without entering the details ; specifying the rules of proof would be too tedious at this step and not so interesting) :
  1. Rewrite through equivalences in 2.1 and 2.3 (simplified by assuming a nonempty model) each axiom into a chain of quantifiers applied to a quantifier-free formula (prenex form).
  2. Replace each occurrence of ∃ in an axiom by an additional operator symbol K to the language of the theory, following the rule that generalizes in the obvious way
    (∀x,x', ∃y, ∀z, A(x,x',y,z)) ⇢ (∀x,x',∀z, A(x,x',K(x,x'), z)).
  3. Replace the predicate = in axioms, by an ordinary predicate symbol to play the role of equality, together with the axioms of equality [end of 1.6]
  4. Let M be the ground term algebra over the language of operator symbols enriched as above. Replacing the remaining variables of each axiom (now all under ∀) by all possible tuples of elements of M and interpreting there all operator symbols they contain, gives a system of logical axioms whose Boolean variables are the (ground) formulas of the form R(t,t',...) where R is a predicate symbol and t,t',... are in M.
  5. Observe that the resulting theory T' is still consistent, as any contradiction in T' can be converted into a contradiction in the initial theory T (without using the axiom of choice that anyway cannot be used in proofs outside set theory), as follows:
    For every (ground) subterm whose root is a new symbol S, occurring in the proof (each considered only once no matter its number of occurrences in the proof), for example terms S(t0,t1) and S(t0,t2) (where t0, t1, t2 are in M), produced by an axiom like
    (∀x,∃y,∀z,∃u, A(x,y,z,u)) transformed into (∀x,z, A(x,K(x),z, S(x,z)))
    the reasoning in T should start by
    "Let y such that ∀z,∃u, A(t0,y,z,u);
    let u1 such that A(t0,y,t1,u1);
    let u2 such that A(t0,y,t2,u2);"
    and continue by using the proof from T' where y replaces K(t0), u1 replaces S(t0,t1) and u2 replaces S(t0,t2).
  6. Add one by one to the axioms, each of these Boolean variables if it is consistent with previous axioms, so that all get values without contradiction (if infinite, the language needs to be well-orderable for this step to proceed).
  7. Then the quotient [see 2.9] of M by the equivalence relation of "equality", forms a model (with the "true equality"). ∎
Deduction of the second statement from the first :
⇔ The theory (T + ¬A) is inconsistent
⇔ The theory (T + ¬A) has no model
A is true in all models of T.  ∎

However, this still does not make everything clear about provability and existence of models:

(it is possible to somehow translate any first-order theory into an algebraic theory by means of the tricks presented in the proof of the completeness theorem, together with the concept of boolean algebra, that is not just {0,1} but can be any set of subsets of one set that is stable by finite unions, finite intersections and complements).

Next : How mathematical theories develop

 Set theory and foundations of mathematics
1. First foundations of mathematics
2. Basics of set theory
3. Basics of Model Theory
3.1. Morphisms of relational systems and concrete categories
3.2. Algebras
3.3. Algebraic terms, integers and recursion
3.4. Mathematical theories and the Completeness Theorem
3.5. How mathematical theories develop
3.6. Second-order theories (updated, May 2015)
3.7. Formalizations of Arithmetic
3.8. Non-standard models of Arithmetic
3.9. The Incompleteness Theorem