On this concept: Formula

Not sure which lesson to do first? Find your level and get a plan →

Math · Sets & Logic · Grade 9-12

Completeness (Intuition)

Completeness means a system can prove every true statement expressible in it — nothing true is beyond the reach of its axioms.

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

Quick Answer

Completeness means a system can prove every true statement expressible in it — nothing true is beyond the reach of its axioms. The question comes up when you ask whether a set of axioms is strong enough to settle every statement it can express, not just whether it avoids contradictions. Small systems can be complete: the rules for adding 0 and 1 on a two-position switch decide every equation they can state. Kurt Gödel showed that arithmetic cannot be: any consistent, checkable list of axioms for whole-number arithmetic leaves some true statements unprovable.

Why This 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.

Intuitive Explanation

Picture a switch with two positions, 0 and 1, where pressing it twice brings you back: 0+0=0, 0+1=1, 1+0=1, 1+1=0. Any equation you can write in this little language, such as 1+1+1=1, can be settled by working through the table: (1+1)+1=0+1=1, so it is true and provable. Every true equation can be proved this way and every false one refuted. That system is complete: no true statement it can express is out of its reach.

Ordinary arithmetic is different. In 1931 Gödel proved that for any consistent list of axioms that a computer could check and that is strong enough to handle whole-number addition and multiplication, some statement about whole numbers is true but cannot be proved from those axioms. Adding that statement as a new axiom does not end the problem, because the enlarged system has its own unprovable truth. The gaps are not a failure of effort; they are built in.

Completeness is easy to confuse with two neighbours. Consistency means the system never proves a contradiction, and a consistent system can still leave truths unprovable. Soundness runs in the opposite direction from completeness: sound means everything provable is true, complete means everything true is provable. Arithmetic's usual axioms are true of the whole numbers, so they prove nothing false, yet they cannot be complete.

Think of it like this. 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.

Core idea. A system is complete if every statement it can express is settled — provably true or provably false — with no true-but-unprovable gaps.


When to Use

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.

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

How to Recognize It

Before calling a system complete, separate two questions, whether its rules avoid contradictions and whether they are strong enough to settle every statement they can express, since only the second is completeness.

  1. Is the question about whether the rules can settle every statement, rather than whether they clash?

    If yes, it is about completeness. If it asks only whether the rules can all hold at once, that is consistency, a separate property: a system can be consistent and still leave questions open.

  2. Can you find a statement the rules neither prove nor refute?

    If yes, the system is incomplete: rules for a game that never mention ties leave 'is a tie a win?' undecided. If every statement can be proved or refuted, the system is complete.

  3. Could the rules prove something false?

    If yes, the problem is soundness, the reverse guarantee: soundness means provable implies true, while completeness means true implies provable. A system can pass one test and fail the other.

  4. Is the question whether a step-by-step procedure can always find the answer, rather than whether a proof exists?

    If yes, that is decidability. A proof can exist without any procedure guaranteed to find it; Alan Turing studied this question about mechanical procedures in 1936.

Completeness (Intuition) compared with Consistency, Soundness, and Decidability

All four rows describe how a system of rules relates to truth, which is why they blur. Ask what is guaranteed: no clashes (consistency), every truth provable (completeness), every proof yielding a truth (soundness), or a mechanical procedure that always gives the answer (decidability).

Completeness (Intuition)

Meaning
Use this when you ask whether a system's axioms can prove every true statement it can express.
Key test
Does this system prove every true statement it can express, leaving no true-but-unprovable gaps?
Formula
For every sentence φ, either T⊢φ or T⊢¬φ (the system decides every statement)
Example
A toy system has axioms that decide every statement about {0,1} addition. Is it complete?

Consistency

Meaning
Forbids contradictions; says nothing about whether all truths are provable.
Key test
Use when checking the system has no internal clash, not its proving power.
Formula
P1∧⋯∧Pn≠⊥
Example
No rule contradicts another

Soundness

Meaning
Guarantees provable statements are true; completeness guarantees true statements are provable — the converse.
Key test
Use when checking proofs never produce falsehoods.
Formula
T⊢φ⇒φ true
Example
Every theorem is actually true

Decidability

Meaning
Whether an algorithm can decide truth, not whether a proof merely exists.
Key test
Use when asking about a mechanical procedure, not provability in principle.
Example
An algorithm settling any statement

Formula & Notation

For every sentence φ, either T⊢φ or T⊢¬φ (the system decides every statement)
T is complete iff ∀φ (T⊢φ∨T⊢¬φ); by Gödel's first incompleteness theorem, any consistent, sufficiently strong theory is incomplete

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

Worked Examples

Example 1 — Powerful enough?

Easy

A toy system has axioms that decide every statement about {0,1} addition. Is it complete?
Show the steps and the answer
  1. Write out the system, taking addition to wrap around as on a two-position switch: the axioms are 0+0=0, 0+1=1, 1+0=1, 1+1=0.

    These four facts are the whole content of {0,1} addition, so every statement is built from them.

  2. Settle a sample statement: (1+1)+1=0+1=1, so the system proves 1+1+1=1 and refutes 1+1+1=0.

    Any equation of 0s and 1s reduces to a single value by repeated use of the table.

  3. Cover every equation: each side reduces to 0 or 1, leaving 0=0, 1=1 (proved) or 0=1, 1=0 (refuted). A statement such as 'for every x, x+x=0' is settled by trying x=0 and x=1.

    For every sentence φ the system proves φ or proves ¬φ, which is the definition of completeness.

  4. Note why this worked: there are only two objects, so every question ends in a finite calculation.

    Arithmetic on all whole numbers has infinitely many objects, and Gödel showed no consistent, checkable axioms for it can decide every statement.

Answer: Yes — it is complete (it decides every statement)

Takeaway: A system is complete when every statement it can express is either proved or refuted. Small systems can be checked by calculation; for whole-number arithmetic, no consistent, checkable set of axioms is complete.

Example 2 — Consistency, not completeness

Standard

A system never contradicts itself but cannot prove a certain true statement. Is it complete?
Show the steps and the answer
  1. Separate the two facts: 'never contradicts itself' and 'cannot prove a certain true statement'.

    Each fact speaks to a different property, so judge them one at a time.

  2. Read the first as consistency: the system never proves both a statement and its negation.

    Consistency is only about the absence of contradictions.

  3. Read the second against completeness: a true statement with no proof is a gap.

    Completeness requires every true statement to be provable, so a single gap makes the system incomplete.

  4. Match it to a real case: the usual axioms for whole-number arithmetic are trusted to be consistent, and Gödel's theorem guarantees a true statement they cannot prove.

    This is the standard example of a consistent system that is not complete.

Answer: Consistent but not complete

Takeaway: Having no contradictions does not mean having no gaps. Consistency and completeness are separate properties, and arithmetic has the first without the second.

Example 3 — Find the mistake: consistent does not mean complete

Application

Mo writes: "Euclid's first four postulates never contradict each other, so they must be able to either prove or disprove the parallel postulate (through a point not on a line there is exactly one line that never meets it)." Find the mistake and correct it.
Show the steps and the answer
  1. Separate Mo's two claims: 'never contradict each other' is consistency, while 'prove or disprove every statement' is completeness.

    Mo assumes the first gives the second, and that is the step to test.

  2. Find two geometries where all four postulates hold: the flat plane, and the hyperbolic plane (often pictured as a saddle shape).

    Anything provable from the four postulates must be true in both geometries.

  3. Check the parallel postulate in each: in the flat plane exactly one such line exists and triangle angles sum to 180∘; in the hyperbolic plane infinitely many exist and triangle angles sum to less than 180∘.

    The statement is true in one geometry and false in the other.

  4. Conclude: no proof exists, because the postulate fails in the hyperbolic plane, and no disproof exists, because it holds in the flat plane.

    The four postulates are consistent but leave this statement undecided, so they are not complete.

Answer: The first four postulates are consistent but not complete: the parallel postulate can be neither proved nor disproved from them.

Takeaway: Consistency does not imply completeness. Two geometries that obey the same axioms, one where a statement holds and one where it fails, show that the axioms cannot decide it.

Where You'll See It

  • Tic-tac-toe is completely settled

    Tic-tac-toe is a small, finite system: there are 255,168 possible games, so every question about it, such as 'can the first player force a win?', can be answered by checking them all. Computers did exactly that, and the answer is no: with perfect play every game is a draw.

  • Sizes of infinity nobody can settle

    Is there a size of infinity between the whole numbers and the real numbers? Gödel in 1940 and Paul Cohen in 1963 showed that the standard axioms of set theory can neither prove nor disprove that such a size exists. It is a concrete gap, and set theorists still debate which new axioms, if any, should settle it.

  • Goodstein sequences

    A Goodstein sequence starting at 4 grows for an astronomically long time before finally falling to 0. Every Goodstein sequence does reach 0, but in 1982 Kirby and Paris showed that this true statement about whole numbers cannot be proved from the standard axioms of arithmetic.

Common Mistakes

  1. The slip: Confusing completeness with consistency

    Instead: consistency forbids contradictions, completeness requires every truth be provable.

  2. The slip: Mixing up completeness and soundness

    Instead: completeness: true implies provable; soundness: provable implies true.

  3. The slip: Assuming a consistent system must be complete

    Instead: Gödel showed rich systems can be consistent yet incomplete.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. A toy system has the axiom "0 is even" and one rule: from "n is even", derive "n+2 is even". Can it prove "6 is even"? Can it prove "5 is odd"?

    Hint: List what the rule can produce, starting from 0.

  2. A system's only axioms are x=3 and the usual rules of algebra. Can it decide "x+1=4"? "x2=9"? "y=2"?

    Hint: Which statements follow from knowing x, and which need information the axioms never give?

  3. Axioms: a+b=10 and a−b=2. Does this system decide "a=6" and "ab=24"? Now drop the second axiom: is "a=6" still decided?

    Hint: Solve the pair of equations. With one equation, how many solutions are there?

  4. Axioms about a hidden integer n: "1≤n≤4" and "n is even". Which statements are decided: "n>1", "n=2", "n2<20"?

    Hint: List every n the axioms allow, then test each statement on all of them.

  5. System S proves the statement "2+2=5". Is that a failure of completeness or of soundness?

    Hint: Is the trouble that a true statement is missing, or that a false one got proved?

  6. Nia says: "My axioms x>0 and x<10 never contradict each other, so my system is complete." Correct her.

    Hint: Can her axioms settle whether x=5?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Didn't Gödel also prove a completeness theorem?

Yes, and the names cause confusion. In 1929 Gödel proved that first-order logic is complete in one sense: any statement true in every possible model of a set of axioms can be proved from them. His 1931 incompleteness theorem says something different: for arithmetic, no consistent, checkable list of axioms proves every statement that is true about the ordinary whole numbers. The two results hold side by side.

What does a true but unprovable statement look like?

Gödel's example is a statement that says, in effect, 'this statement cannot be proved in this system'. If the system proved it, the system would prove something false, which a sound system cannot do. So it is unprovable, which is exactly what it says, and therefore true. Later mathematicians found more natural examples, such as the Paris-Harrington theorem about colouring sets of numbers, which is true but unprovable in standard arithmetic.

Does incompleteness mean mathematics is broken?

No. Almost every theorem you meet in school or university is proved from standard axioms, and the unprovable statements Gödel's theorem guarantees rarely appear in everyday work. When a statement does turn out to be unprovable, mathematicians can add a new axiom to decide it, though the larger system then has unprovable statements of its own. Incompleteness is a limit on any single list of axioms, not a crack in what has been proved.

Is any part of school mathematics complete?

Yes, surprisingly. Alfred Tarski showed that the algebra of real numbers, with addition, multiplication and order, is complete and even decidable: every statement built from these, such as 'every cubic has a real root', can be proved or refuted by a fixed procedure. Whole-number arithmetic is different because it can encode statements about its own proofs, while real-number algebra cannot even single out which reals are whole numbers.

Learning Path

← Before

Consistency (Meta)
Completeness (Intuition)

You are here

Next →

Nothing after this yet
You need Consistency (Meta) first: a set of statements with no contradiction. Completeness adds the opposite worry, whether every true statement can actually be reached by a proof, and shows that small systems can be complete while arithmetic cannot. With both ideas you can follow Gödel's incompleteness theorems, see why the parallel postulate is neither provable nor disprovable from Euclid's other axioms, and understand why set theorists debate new axioms.

See Also