2.3 Consistency and Completeness

A formal system is judged partly by what it can prove and partly by what it avoids proving. Two central properties are consistency and completeness.

Consistency means the system does not prove contradictions. A system is consistent if there is no statement P such that both P and ¬P are provable.

not both:  ⊢ P  and  ⊢ ¬P

An inconsistent system is unusable for ordinary mathematics because contradiction destroys discrimination. In classical logic, from a contradiction one can derive any statement. This principle is called explosion.

P, ¬P ⊢ Q

If a system proves a contradiction, then every statement becomes provable. False arithmetic, false geometry, and arbitrary claims all follow. Proof no longer separates valid statements from invalid ones.

Completeness has several meanings, and the distinction matters.

A proof system is semantically complete if every logically valid statement is provable.

If every model satisfies φ, then ⊢ φ.

First-order logic is complete in this sense. If a first-order sentence is true in every structure under every interpretation, then there is a formal proof of it.

A theory is syntactically complete if for every sentence φ in its language, either φ or ¬φ is provable.

For every φ:  ⊢ φ  or  ⊢ ¬φ

This means the theory decides every statement expressible in its language.

These two uses of completeness should not be confused.

A theory can be consistent but incomplete. This is common. It means the theory avoids contradiction but still leaves some statements undecided.

Arithmetic gives the central example. Any sufficiently expressive, effectively axiomatized, consistent theory of arithmetic cannot decide every arithmetical statement. Some statements are independent of the theory.

T ⊬ φ
T ⊬ ¬φ

The statement φ is then undecidable in T.

This does not mean φ has no meaning. It means the chosen axioms are insufficient to settle it. Stronger axioms may decide it.

Consistency is usually the minimum requirement. Completeness is stronger and often unavailable.

For strong theories, consistency cannot usually be proved from inside the same theory. A sufficiently strong consistent theory cannot prove its own consistency, assuming it is expressed in the required formal way. This is one of the major limits of formalization.

To prove consistency, one often works in a stronger meta-theory. For example, one may show that a theory has a model. If a model exists, the theory is consistent, because all axioms are true in that model and valid inference rules preserve truth.

Model exists  ⇒  theory is consistent

This connects consistency with semantics.

Completeness connects proof with decision. A complete theory gives an answer for every sentence in its language. An incomplete theory leaves gaps. These gaps are not necessarily defects. They may indicate that the language is rich enough to express questions whose answers require additional principles.

Geometry provides a useful example. Euclidean geometry includes the parallel postulate. If that postulate is removed, both Euclidean and non-Euclidean geometries become possible. The remaining axioms do not decide the parallel postulate.

Independence shows that multiple consistent extensions can exist.

T + φ      consistent
T + ¬φ     consistent

When both extensions are consistent, the original theory does not determine the statement.

Completeness is also related to categoricity. A theory is categorical if all its models are essentially the same up to isomorphism. If a theory has many non-isomorphic models, then its axioms do not isolate one structure uniquely.

This is important in arithmetic and set theory. First-order theories often have nonstandard models. Even if the intended model is clear informally, the formal axioms may admit other models.

A practical reading strategy is:

Mathematical foundations balance strength and safety. Stronger axioms prove more theorems but may carry greater consistency assumptions. Weaker axioms are safer but decide fewer questions.

Consistency protects reasoning from collapse. Completeness measures how much the system can decide. The tension between them explains why formal mathematics has both power and limits.