In mathematical logic, a formal system is consistent if it does not contain a contradiction, or, more precisely, for no proposition φ are both φ and ¬φ provable.

A consistency proof is a formal proof that a formal system is consistent. The early development of mathematical proof theory was driven by the desire to provide finitary consistency proofs for all of mathematics as part of Hilbert's program. Hilbert's program fell to Gödel's insight that sufficiently strong proof theories cannot prove their own consistency.

Although consistency can be proved by means of model theory, it is often done in a purely syntactical way, without any need reference to some model of the logic. The cut-elimination (or equivalently the normalization of the underlying calculus if there is one) implies the consistency of the calculus: since there is obviously no cut-free proof of falsity, there is no contradiction in general.

Consistency and completeness

The fundamental results relating consistency and completeness were proven by Kurt Gödel:

• Gödel's completeness theorem shows that any consistent first-order theory is complete with respect to a maximal consistent set of formulae which are generated by means of a proof search algorithm.
• Gödel's incompleteness theorems show that theories capable of expressing their own provability relation and of carrying out a diagonal argument are capable of proving their own consistency only if they are inconsistent. Such theories, if consistent, are known as essentially incomplete theories.

By applying these ideas, we see that we can find first-order theories of the following four kinds:

1. Inconsistent theories, which have no models;
2. Theories which cannot talk about their own provability relation, such as Tarski's axiomatisation of point and line geometry, and Presburger arithmetic. Since these theories are satisfactorily described by the model we obtain from the completeness theorem, such systems are complete;
3. Theories which can talk about their own consistency, and which include the negation of the sentence asserting their own consistency. Such theories are complete with respect to the model one obtains from the completeness theorem, but contain as a theorem the derivability of a contradiction, in contradiction to the fact that they are consistent;
4. Essentially incomplete theories.

In addition, it has recently been discovered that there is a fifth class of theory, the self-verifying theories, which are strong enough to talk about their own provability relation, but are too weak to carry out Gödelian diagonalisation, and so which can consistently prove their own consistency.

See also

Hilbert's problems

1. Continuum hypothesis
2. Consistency proof
3. Hilbert's third problem
4. Hilbert's fourth problem
5. Hilbert's fifth problem
6. Hilbert's sixth problem
7. Hilbert's seventh problem
8. Riemann hypothesis
9. Hilbert's ninth problem
10. Matiyasevich's theorem
11. Hilbert's eleventh problem
12. Hilbert's twelfth problem
13. Hilbert's thirteenth problem
14. Hilbert's fourteenth problem
15. Hilbert's fifteenth problem
16. Hilbert's sixteenth problem
17. Hilbert's seventeenth problem
18. Hilbert's eighteenth problem
19. Hilbert's nineteenth problem
20. Hilbert's twentieth problem
21. Hilbert's twenty-first problem
22. Hilbert's twenty-second problem
23. Hilbert's twenty-third problem

Proof theory | Hilbert's problems

希爾伯特第二問題