(
Mathematical Logic:)
A
theory is
consistent iff it is free of
contradictions: For any
proposition P, it's possible to prove
at most one of P, ~P from the
axioms of the theory.
One may prove that a theory is consistent iff it has a model:
- --> :
- If it's consistent, we need the axiom of choice to get a model. The proof is extremely technical, but in a sense trivial. We work in a universe which contains just those objects that the theory's language can mention. We arrange for all provable propositions (theorems) P to hold, and then Choose for any unprovable pair (P,~P) which holds, in a "consistent" manner.
- <-- :
- If it has a model, then for any proposition P either P holds in the model or ~P holds in the model. If P holds then ~P cannot be proven (or it would be true in the model, since the model satisfies the axioms), and if ~P holds then P cannot be proven. So a contradiction can never be proved.
This direction is free of the axiom of choice.
This is usually known (for
first order logic) as
Gödel's completeness theorem (
NOT the same as his
incompleteness theorem!)