The theorem of complétude of the Calcul of the first order predicates was proven by Kurt Gödel (1929, thesis of doctorate, On the complétude of logical calculation). He affirms that the calculation of the Prédicat S is complete with the direction where one knows finished and complete lists of all his principles. In other words any mathematical demonstration can be formalized in theory in Calcul of the predicates.

We will give several equivalent definitions of this concept of complétude.

Various equivalent formulations of the theorem of complétude

One can give a finished number of Axiome S, diagrams of axioms or from rules of inference such as all the logically valid evidence formulated with grammar of the calculation of the first order predicates are obtained starting from these principles.

The notion of validity logical of a proof is specified by the Théorie of the models. A rule of deduction is valid when very model of its premises is also a model of its conclusion. A logical axiom is valid when it is true in all the models. A diagram of axioms is a valid logical principle when all the axioms produced by this diagram are valid logical axioms. A system of logical principles is valid or correct when its axioms, its diagrams of axioms and its rules of deduction are valid. A proof is logically valid when it can be formalized within the framework of a valid logical system.

We will prove that the list of the fifteen rules of natural Déduction is a complete system of the principles of first order logic. This theorem is equivalent to that of Gödel. But the proof of Gödel is based on another formulation of the logical principles, that of the Principia Mathematica of Whitehead and Russell.

For that, let us give some definitions:

• those relating to the use of models (first order): satisfaisability and falsifiability, logical law and logical contradiction, logical consequence, prouvability

a formula of the calculation of the predicates is satisfaisable or possibly true when it is true in at least a model. It is universally valid, or is a logical law , when it is true in all the models. If p is a logical law, one notes $\backslash \; vDash\; p$. If p and Q are two formulas of the calculation of the predicates, it will be said that Q is a logical consequence of p when very model of p is also a model of Q, in other words, for any model m, if p is true in m then Q is true in m, which one notes $p\; \backslash \; vDash\; q$. A formula is falsifiable or possibly false when it is false in at least a model. It is absolutely false, or is a logical contradiction , when it is false in all the models. Its negation is thus a logical law. If p is a logical contradiction, there is thus $\backslash \; vDash\; \backslash \; lnot\; p$. To say that p is satisfaisable, it is to say that p is not a logical contradiction, which one notes $\backslash \; not\; \{\backslash \; vDash\}\; \backslash \; lnot\; p$.

• those relating to the systems of deduction (for the calculation of the first order predicates): coherence and inconsistency, prouvability.

If p is a formula of the calculation of the predicates, p is provable in a system of deduction for logic L, when there exists a proof of p in L, with the direction where the rules of deduction of L are enough to deduce p in a finished number of stages in L, which one notes $\backslash \; vdash\; p$. If T is a whole of formulas of the calculation of the predicates, p is provable starting from T in the logical system L, when there exists a proof of p from some of the formulas of T (of number necessarily finished) in L, which one notes $T\; \backslash \; vdash\; q$ or $\backslash \; vdash\_T\; q$. The systems of deduction L for formulas which use the implication $\backslash \; to$ often check $p\; \backslash \; vdash\; q$ if and only if $\backslash \; vdash\; p\; \backslash \; to\; q$ (it is the case of the natural deduction, the system in Hilbert, or the calculation of the séquents). In other words, it is equivalent to prove Q starting from p in L, or to prove directly $p\; \backslash \; vdash\; q$ in L.

Let us note $\backslash \; bot$ contradiction, if it does not form part of the lanage one can define it by $q\; \backslash \; Land\; \backslash \; lnot\; q$ for an arbitrary closed formula Q . A whole of formulas T is coherent in L when there exists a formula Q which is not provable starting from T in L, or in an equivalent way in traditional logic, if contradiction is not provable starting from T , which one notes $T\; \backslash \; not\; \{\backslash \; vdash\}\; \backslash \; bot$. A whole of formulas T is incoherent or contradictory in L when all the formulas are provable starting from T in L, or in an equivalent way in traditional logic, if contradiction is provable starting from T , which one notes $T\; \backslash \; vdash\; \backslash \; bot$.

A correct system of deduction must be able to prove, starting from true formulas, only true proposals, in particular, one waits until, if $\backslash \; vdash\; p$ then $\backslash \; vDash\; p$. We will show in the paragraph according to whether such is the case for the natural deduction, or an equivalent system, such calculation of the séquents.

The theorem of complétude is concerned with the reciprocal one. That means that the system of deduction L must be sufficiently complete (from where the name of the theorem) in order to be able to prove any logical law, i.e any formula true in very model. The theorem of complétude can be stated in the following form (expressed for a formula, a stronger form of the theorem of complétude is written for a number possibly infi of formulas):

There exist logical systems of deduction valid L which satisfy the following equivalent conditions:

• for all formulas p and Q (of the calculation of the first order predicates), if Q is a logical consequence of p then Q is provable starting from p in L. If $p\; \backslash \; vDash\; q$ then $p\; \backslash \; vdash\; q$.

• For any formula p, if p is a logical law then p is provable. If $\backslash \; vDash\; p$ then $\backslash \; vdash\; p$.
• For any formula p, if p is a logical contradiction then (not p) is provable. If $\backslash \; vDash\; \backslash \; lnot\; p$, then $\backslash \; vdash\; \backslash \; lnot\; p$.
• For any formula p, if p is a logical contradiction then p is incoherent in L. If $\backslash \; vDash\; \backslash \; lnot\; p$, then $p\; \backslash \; vdash\; \backslash \; bot$.
• For any formula p, if p is coherent in L then p is satisfaisable. If $p\; \backslash \; not\; \{\backslash \; vdash\}\; \backslash \; bot$ then $\backslash \; not\; \{\backslash \; vDash\}\; \backslash \; lnot\; p$.

One can finally notice that a unit defined by induction with a finished number of principles (axioms, diagrams of axioms and rules of deduction) is énumérable. In other words, all the usual axiomatic theories are énumérables units. The theorem of complétude says that there exist complete axiomatic theories of first order logic.

It results from it that the whole of the logical laws is énumérable.

That makes it possible to connect this theorem of complétude to the theory of the indecidability, because one can prove that the whole of the logical laws is indécidable. In other words, the whole of the falsifiable formulas is not énumérable, or, in an equivalent way, the whole of the formulas satisfaisables is not énumérable (see also the Théorème of incomplétude and the Théorème of Tarski).

The validity of the calculation of the first order predicates

A system of deduction for the calculation of the predicates being chosen, one shows that if a formula C is deductible, with the rules of this system starting from a whole of formulas H ($h\; \backslash \; vdash\; c$), then C is a semantic consequence of H, i.e. logical consequence within the meaning of the theory of the models, to see above (one notes, to distinguish from the preceding concept, $h\; \backslash \; vDash\; c$).

The proof is made by recurrence on the size of the evidence, cuts that one defines for each system of deduction. It is then a question of checking that each logical axiom is valid, and that each rule preserves the validity. The proof is commonplace, but tiresome to entirely write.

Let us specify a little the case of the natural Déduction: it is more convenient to use a formulation of this one in terms of séquents (having a finished number of premises and a conclusion).

It would be necessary to handle formulas with free variables. To simplify (the idea is the same one) let us make as if we were in propositional calculation, i.e. all the formulas are closed, it does not have there quantifiers. One séquent is valid when very model of its premises is also a model of its conclusion.

One séquent provable if it is or an axiom, or is deduced from the axioms by a number finished of applications of the rules of the natural Déduction. The axioms all are here the séquents form $p\; \backslash \; vdash\; p$ where p is a formula of the calculation of the predicates. As one has in an obvious way $p\; \backslash \; vDash\; p$, the axioms are valid. One can then show, starting from the definition of the truth of the complex formulas (see Théorie of the models), that on the basis of séquents valid, one can deduce only from the valid séquents if one applies one of the rules of the natural deduction of the séquents. One shows then by induction on the structure of the evidence (primarily, it is a recurrence on the height of the evidence as a tree) which all the provable séquents are valid.

For example, let us suppose that one proved $h\; \backslash \; vdash\; p\; \backslash \; Land\; q$ by introduction of the logical connector $\backslash \; land$ ( and ). That means that before, one proved $h\; \backslash \; vdash\; p$ and $h\; \backslash \; vdash\; q$. By induction, there is $h\; \backslash \; vDash\; p$ and $h\; \backslash \; vDash\; q$. In very model making the formulas of H true, p is true and Q is true. Thus $p\; \backslash \; Land\; q$ is true, and there is well $h\; \backslash \; vDash\; p\; \backslash \; Land\; q$.

By applying the same checking to all the séquents, one proves that, if $h\; \backslash \; vdash\; c$, then $h\; \backslash \; vDash\; c$.

To deduce from it that the provable formulas ($\backslash \; vdash\; p$) are logical laws ($\backslash \; vDash\; p$). It is enough to take H empty.

The existence of a model under the assumption of coherence

We will prove the theorem of complétude in the following form.

If a formula is coherent then it is satisfaisable. If $p\; \backslash \; not\; \{\backslash \; vdash\}\; \backslash \; bot$, then $\backslash \; not\; \{\backslash \; vDash\}\; \backslash \; lnot\; p$.

In fact we will prove a reinforced version of this theorem.

If a whole of axioms is coherent then it is satisfaisable.

A whole of axioms is coherent when no contradiction is provable starting from an unspecified number, finished, of these axioms. It is satisfaisable when there is a model in which the axioms all are true. This reinforced version of the theorem is useful to state the paradox of Skolem in particular, because it makes it possible to apply the theorem of complétude to infinite systems of axioms.

Let us start by showing how to replace a system of axioms of the calculation of the predicates by a system are equivalent of axioms of the calculation of the proposals. For that, one starts by putting each axiom under a Forme prénexe.

A formula of the calculation of the predicates is always equivalent to a formula put in form prénexe, i.e. a formula in which all the universal and existential quantifiers are placed at the beginning and not inside the subformulas. One can always prove that a formula is equivalent to a formula prénexe with the rules of following deduction:

• of $(\backslash \; exists\; X\; \backslash ;\; p)\; \backslash \; Land\; q$ to deduce $\backslash \; exists\; X\; \backslash ;\; (p\; \backslash \; Land\; Q)$, provided that Q does not contain X like free variable. (If it contains it, it is enough to substitute to X in $\backslash \; exists\; X\; \backslash ;\; p$ another variable which does not appear in Q).
• of $(\backslash \; exists\; X\; \backslash ;\; p)\; \backslash \; lor\; q$ to deduce $\backslash \; exists\; X\; \backslash ;\; (p\; \backslash \; lor\; Q)$, also provided that Q does not contain X like free variable.
• two other similar rules for the universal quantifier $\backslash \; forall\; x$.
• of $\backslash \; lnot\; (\backslash \; exists\; X\; \backslash ;\; p)$ to deduce $\backslash \; forall\; X\; \backslash ;\; (\backslash \; lnot\; p)$.
• of $\backslash \; lnot\; (\backslash \; forall\; X\; \backslash ;\; p)$ to deduce $\backslash \; exists\; X\; \backslash ;\; (\backslash \; lnot\; p)$.

All these rules are rules derived in the system from natural deduction and they do all to pass from a premise to an equivalent conclusion. By iteration they provide a formula prénexe equivalent to the initial formula.

Form prénexe of an axiom, one passes to his form of Skolem by introducing new fundamental operators, as much as it is necessary some to make disappear all the existential quantifiers in the axioms. For example, the axiom prénexe $\backslash \; forall\; X\; \backslash ;\; \backslash \; exists\; there\; \backslash ;\; x+y\; =\; 0$ is replaced by $\backslash \; forall\; X\; \backslash ;\; x+\; (-\; X)\; =\; 0$ where $-$ is a new unary operator. For an axiom of the form $\backslash \; forall\; X\; \backslash ;\; \backslash \; forall\; there\; \backslash ;\; \backslash \; exists\; Z\; \backslash ;\; P\; (X,\; there,\; Z)$, one introduces a binary operator, $*$ for example, and one takes for axiom $\backslash \; forall\; X\; \backslash ;\; \backslash \; forall\; there\; \backslash ;\; P\; (X,\; there,\; x*y)$

One builds then a universe, a field of the named beings. The names of the basic objects are those which are mentioned in the axioms. If there is not, one introduces one of them, that one can call as it is wanted, 0 for example.

The whole of the names of object is that obtained by induction starting from the names of the basic objects and the names of all the operators mentioned in the axioms of origin or introduced by the method above exposed. The universe U is the whole of all the beings thus named.

Each form of Skolem of an axiom can be conceived like a diagram of axioms inside the calculation of the proposals. All the universal quantifiers are removed and one replaces all the variables then free by names of object. With each starting axiom one thus associates an infinite whole of formulas of the calculation of the proposals. The meeting of all these formulas associated with all the axioms with departure, is the new system of axioms, not quantified, equivalent to the system of origin.

Let us show now that if a finished subset of the system of not-quantified axioms is incoherent then the system of axioms of origin is him also incoherent. That is to say C an incoherent conjunction of not-quantified axioms. That is to say It the formula obtained starting from C by replacing all its constants by distinct variables, in such way that C does not contain any more operators of object, and while quantifying existentiellement on all these variables. As C is incoherent, It is too. But It can be proven starting from a finished number of the axioms of origin, which are thus them also incoherent.

If a system of axioms is coherent all the finished subsets of the system of not quantified axioms are also coherent. According to the Theorem of complétude of the calculation of the proposals, they all are thus satisfaisables. According to the Theorem of compactness, the system - infinite - not quantified axioms is him also satisfaisable. As a model of the system of not-quantified axioms is also a model of the system of origin, one proved the existence of a model for any coherent system of axioms.

The theorem of Löwenheim and the paradox of Skolem

The whole of names from which a model is built in the proof above is countable. One thus also proved the Théorème of Löwenheim-Skolem (proven in 1915 by Leopold Löwenheim and supplemented then for the infinite systems of axioms by Thoralf Skolem.

If a countable system of axioms finished or infinite has a model then it has a countable model.

It is seen that the proof rests on the fact that in a countable language (language in the broad sense: the formulas of the language of the theory form of it part) one cannot to deal that with countable collection of objects. Applied to the set theory, this theorem seems paradoxical. The set theory of Zermelo and its extensions as the theory ZFC are developed in a countable language, which uses a countable infinite whole of axioms. Thus this theory and these extensions have a countable model. By using the Axiom of infinite the and the Axiom of the whole of the parts, one shows the existence of $\backslash \; mathcal\; P\; (\backslash \; NR)$ the whole of all the whole of entireties. Cantor showed, while using, the diagonal reasoning, that this unit is not countable (the other axioms of the set theory of Zermelo are useful to formalize the reasoning).

The paradox is only apparent; it disappears as soon as it is thought that the countable model whose one showed the existence does not identify with the universe in which one worked to show this one. In particular " dénombrable" do not mean any more the same thing inside this countable model.

Indeed one knows that in a model (or universe) of the set theory, whose objects are units, there exist collections of objects (whole with the intuitive direction), whom one can possibly define by a formula, for example the objects which are not belonged to themselves (see Paradoxe of Russell), but which are not units: one cannot find object of the model to which the objects of one of these collections belong (and only those). However to say that a unit is countable, it is to say that there exists a function, i.e. a whole of couples, which is a bijection of $\backslash \; N$ in this unit. In a countable model of the set theory, there is a collection of couples which establishes a bijection between the unit $\backslash \; N$ of the model and the unit $\backslash \; mathcal\; P\; (\backslash \; NR)$ of the model. But this collection is not a unit, i.e. an object of the countable model. Known as in an abrupt way, from the point of view of the countable model, $\backslash \; mathcal\; P\; (\backslash \; NR)$ is not countable indeed.

One can discuss what " wants to say; with the direction intuitif" in the explanation above: it is a convenience of expression. All this is formalized in a set theory (stronger than that which one studies). Known as semantically, in the universe of the set theory in which one works, one defined a model, an object of this universe, which is a countable model (within the meaning of this universe) of the theory of Zermelo, but inside of which, with the maintaining direction of the model that one built, there exist not-countable units.

Random links:

Tony Dreyfus | Gallieni (subway of Paris) | Gilded | Marie Claire | Felix de Cantalice