Completeness (Intuition) Formula

Completeness (intuition) is the property of a mathematical system where every true statement that can be expressed in the system can also be proved within it.

The Formula

For every sentence φ, either T⊢φ or T⊢¬φ (the system decides every statement)

Ask yourself: Does this system prove every true statement it can express, leaving no true-but-unprovable gaps?

Quick example

Tarski's axioms for elementary Euclidean geometry are complete: every statement they can express about points can be proved or disproved from them.

Notation

T⊢φ means 'theory T proves φ'; a system is complete if it decides every sentence

What this formula means

The property of a mathematical system where every true statement that can be expressed in the system can also be proved within it.

A complete system is like a library catalogue that lists every book on the shelves: if a book is there, a search will find it. Gödel showed that arithmetic's catalogue always misses some books that really are on the shelves, and every enlarged catalogue misses others. Unlike a real library, the gap cannot be fixed by more careful cataloguing.

Formal view

T is complete iff ∀φ (T⊢φ∨T⊢¬φ); by Gödel's first incompleteness theorem, any consistent, sufficiently strong theory is incomplete

Worked examples

Example 1

easy
The real numbers R are 'complete' while the rationals Q are not. Illustrate this by finding a sequence of rationals that converges to an irrational number.
Show solution

Answer

1,1.4,1.41,1.414,…→2∈R∖Q

First step

1.
Consider the decimal approximations of 2: 1,1.4,1.41,1.414,1.4142,…

Full solution

  1. 2.
    Each term is rational (a terminating decimal). The sequence converges — each term is closer to 2 than the last.
  2. 3.
    But 2∉Q. In Q, this sequence has no limit — the limit 'falls through a gap.'
  3. 4.
    In R, 2 exists, so the limit exists. R is complete; Q is not.
Completeness of R means every Cauchy sequence of reals converges to a real number. The rationals have gaps at irrational numbers, which is why Q is not complete.

Example 2

medium
Check that a proof by induction for P(n) is complete: what cases must be covered? Use P(n): 'n2≥n for all n≥1' as an example.

Example 3

medium
Why is Q not 'complete' as an ordered field? Give a Cauchy sequence in Q that does not converge in Q.

Common mistakes

  • Confusing completeness with consistency - consistency forbids contradictions, completeness requires every truth be provable.
  • Mixing up completeness and soundness - completeness: true implies provable; soundness: provable implies true.
  • Assuming a consistent system must be complete - Gödel showed rich systems can be consistent yet incomplete.

Why this formula matters

Completeness tells you whether 'nobody can prove it' might mean 'it cannot be proved'. In a complete system every question has a proof or a disproof waiting to be found; in arithmetic, some truths have no proof from the usual axioms, so mathematicians sometimes add new axioms. Mixing it up with consistency leads to the false belief that a system free of contradictions must prove everything true.

Frequently asked questions

What is the Completeness (Intuition) formula?

The property of a mathematical system where every true statement that can be expressed in the system can also be proved within it.

How do you use the Completeness (Intuition) formula?

Think about completeness when a question asks whether a set of axioms can settle every statement it expresses, whether some truth might be unprovable, or what Gödel's theorem says about a system. For a small system, check that each statement can be proved or refuted. If the question is only whether the rules contradict each other, that is consistency; whether every provable statement is true is soundness; whether a computer procedure can always find the answer is decidability.

What do the symbols mean in the Completeness (Intuition) formula?

T⊢φ means 'theory T proves φ'; a system is complete if it decides every sentence

Why is the Completeness (Intuition) formula important in Math?

Completeness tells you whether 'nobody can prove it' might mean 'it cannot be proved'. In a complete system every question has a proof or a disproof waiting to be found; in arithmetic, some truths have no proof from the usual axioms, so mathematicians sometimes add new axioms. Mixing it up with consistency leads to the false belief that a system free of contradictions must prove everything true.

What do students get wrong about Completeness (Intuition)?

The procedure for completeness (intuition) is the easy part; the trap is confusing completeness with consistency. Asking "Does this system prove every true statement it can express, leaving no true-but-unprovable gaps?" first is what keeps a correct-looking calculation from being attached to the wrong concept.

What should I learn before the Completeness (Intuition) formula?

Before studying the Completeness (Intuition) formula, you should understand: consistency meta.