Back to the on-screen lesson ·
The hypotheses the two incompleteness theorems carry, what their conclusions say about provability in one theory, which systems they apply to, and the readings they do not support.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to define consistency, completeness, effective axiomatisation and decidability for a theory, state both incompleteness theorems with their hypotheses, say what follows from each statement and what does not, decide which systems the hypotheses hold of, and use the first theorem in contrapositive to conclude what a complete theory cannot express.
You know what it is for a system to be sound, complete and decidable, and you have seen the completeness theorem for first-order logic. The word complete is about to be used for a different property of a different kind of object, and keeping the two apart is the first thing this lesson asks.
A theory is a set of sentences in a formal language, with the rules for deriving consequences. It is consistent when no sentence and its negation are both provable in it; complete when for every sentence of its language it proves the sentence or its negation; effectively axiomatised when a procedure decides what its axioms are; decidable when a procedure decides what it proves. Completeness of a theory is not the completeness of a logic met earlier: that one said everything entailed is derivable.
First incompleteness theorem. Let $T$ be a theory that is consistent, effectively axiomatised, and whose language can express the arithmetic of addition and multiplication on the natural numbers. Then some sentence of $T$'s language is neither provable nor refutable in $T$ — that is, $T$ is not complete. Second incompleteness theorem. Under the same hypotheses, $T$'s language contains a sentence expressing that $T$ is consistent, and $T$ does not prove it. Four things are worth fixing about these statements. They are about one theory at a time, the one satisfying the hypotheses. Their conclusions are about provability in that theory, not about truth and not about what can be known. Every hypothesis is load-bearing: an inconsistent theory proves everything and is complete, and a theory too weak to express that arithmetic may be complete — Presburger arithmetic, which has addition and no multiplication, is complete and decidable. And incompleteness is not inconsistency; consistency is something the theorems assume.
Another way: steps
Another way: example
Peano arithmetic satisfies all three hypotheses, so the theorem applies to it. Presburger arithmetic satisfies only two — it has no multiplication — and is in fact complete and decidable, which shows the third hypothesis is doing real work.
The first misreading turns a statement about one theory into a statement about all of them, or about knowledge in general. The theorem is a conditional applied to whatever satisfies its hypotheses, and its conclusion is that a particular theory does not prove a particular sentence. The second adds truth to a conclusion that is entirely about provability: what is given is that $T$ proves neither the sentence nor its negation. The third treats incompleteness as a defect that makes a theory unreliable, when consistency is a hypothesis of the theorem and an inconsistent theory is the one that is complete. The fourth confuses this completeness — a property of a theory — with the completeness of first-order logic, which says everything entailed is derivable and is a different result about a different thing.
Does the theorem apply to propositional logic? Its language has no numbers.
Check hypothesis three first.
So the third hypothesis fails and the theorem says nothing about it.
No hypotheses, no conclusion.
Which is as it should be: propositional logic is decidable, by the truth table.
Consistent with the theorem.
$T$ leaves some sentence undecided. Add it to $T$ as a new axiom.
A new theory.
If the result is still consistent and still effectively axiomatised, the hypotheses hold of it too.
Check them again.
So the theorem applies again, to a different sentence. Patching does not escape the hypotheses.
The conclusion returns.
A decidable theory with those two properties would let you decide each sentence, and with consistency that is completeness — which the theorem denies.
So no theory has all four properties at once, and the conclusion is again about what a formal theory can be, rather than about anything beyond it.
Match each property of a theory to its definition.
| No sentence and its negation are both provable in it | For every sentence of its language, it proves that sentence or proves its negation | A procedure decides whether a given sentence is one of its axioms | A procedure decides whether a given sentence is provable in it | |
|---|---|---|---|---|
| Consistent | ||||
| Complete | ||||
| Effectively axiomatised | ||||
| Decidable |
Put the parts of the first incompleteness theorem into order: its three hypotheses first, then its conclusion.
Number the steps in order (write the number in the box):
Let $T$ be consistent, effectively axiomatised, and able to express the arithmetic of addition and multiplication. What does the first incompleteness theorem state about $T$?
Take this as the only thing you are given. $T$ is consistent, effectively axiomatised, and able to express the arithmetic of addition and multiplication; therefore some sentence of $T$'s language is neither provable nor refutable in $T$. Mark every statement that follows.
This task has no paper form; do it on a device.
For each system below, write T if all three hypotheses of the first incompleteness theorem hold of it — consistent, effectively axiomatised, and able to express the arithmetic of addition and multiplication — and F if some hypothesis fails.
| All three hypotheses hold? | |
|---|---|
| Propositional logic | |
| First-order logic with no arithmetical axioms | |
| Presburger arithmetic: addition, with no multiplication | |
| Peano arithmetic |
A theory $S$ is consistent, effectively axiomatised, and complete: for every sentence of its language it proves that sentence or its negation. Taking the first incompleteness theorem as stated, what follows about $S$?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Take this as the only thing you are given. $T$ is consistent, effectively axiomatised and able to express the arithmetic of addition and multiplication; $T$'s language therefore contains a sentence expressing that $T$ is consistent, and $T$ does not prove it. Mark every statement that follows.
This task has no paper form; do it on a device.
You can state both theorems with their hypotheses and say what each conclusion is about. Say in your own words why an inconsistent theory is complete, and why that makes consistency a hypothesis rather than a casualty.
8. Your turn: a consistent, effectively axiomatised theory is decidable and expresses that arithmetic. What follows?, step 2