# 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:
• Algebraic theories;
• First-order theories
• Duality theories (that is a fuzzy range of theories with some common features);
• Second-order theories;
• Higher-order theories;
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):
• A natural inclusion of all first-order theories into set theory, viewing their possible models as objects in a common model (universe) of set theory (1.3, 1.4). This view is the usual framework for ordinary mathematics, able to study many systems as "sets together with relations or operations such that...", but also possible connections between them.
• Another procedure (sections 1.9, 1.10) to translate a set theory into the format of a first-order theory (but its interest is more restricted to specialized studies in the foundations of mathematics)
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 :
• A list of types, whose translations into set theory are names of sets. For example, geometry can be seen with 2 types: «points» and «lines».
• A list of symbols of structures. These symbols aim to designate structures, that is connections between objects with specific types. They give their roles to the objects of each type in connection with those of other types. In first-order theories, a structure is either
• An operation between a list of variables with respectively specified types (which aim to specify the types of their values), with values of also one specified type. The number of arguments of an operation is called its arity.
• A constant is the particular case of a nullary operation (it has no argument).
• A relation, that is an operation with value «true» or «false».
We may as well see n-ary operations f(x1,..., xn) as particular cases of (n+1)-ary relations, namely, those with a unique value of y related to any combination of values of x1,..., xn, to serve as the relation (y=f(x1,..., xn)).
• A list of axioms. Each axiom is a ground formula, expressed using these symbols (a system of occurrences of symbols among logical symbols and symbols of structures) plus possible logical connectives and quantifiers (∀and ∃), supposed to be true when these symbols are interpreted in a given system. Axioms are expressions of a selection of models: a choice to only consider those systems of sets with structures where these axioms are true, to be called models of this theory (a system of objects described by the theory), excluding other systems from this title.

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:

• A contradiction of a theory, is a system of formulas connecting axioms of T, that forms a proof of the formula "False" (0).
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
• Any consistent first-order theory has a model.
• Any «true consequence» of any first-order axiomatic theory (formula true in all models) is a theorem (formally provable by these rules).
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 :
TA
⇔ 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:

• As for proofs, nothing says how to find them. In principle, a proof of any theorem can be found by a theoretical computer with infinite available time and resources. But we have no such a computer available, and some "existing" proofs may be too long to be effectively found in practice. There may be no way to distinguish whether a formula is truly unprovable or a proof has only not yet been found.
• For the construction of models, every possible specification is very complex: as models built this way depend on an arbitrary choice of order between formulas, an infinity of other models are possible, resulting from other choices, that can be as worthy and legitimate but with different properties ;
• Once this choice is made, the construction of the model is still not really effective, as it cannot be processed by any finite being such as human thought or computer, thus it cannot be called explicit from such viewpoints. Instead, this construction requires an infinity of steps, each of which involves an infinite knowledge (to decide if a new axiom remains consistent consistent with previous axioms: this is the answer to a halting problem of search for contradiction). Actually, for many theories (and especially foundational ones such as set theory), no model can ever be built in an algorithmic manner.
• The incompleteness theorem will show how, while we established that consistency and existence of a model are equivalent properties of a theory, this still often leaves undecidable the question whether they are both true or both false.

(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