greatitself.
Continue
research36 min studyLesson 979 in Mathematics

Second incompleteness and consistency strength

Track the derivability conditions and the particular internal sentence expressing consistency.

Before you begin
On this page

The question for today

What you’ll understand

  • State the three standard derivability conditions for an arithmetic provability predicate.
  • Derive the internal implication from consistency to the Gödel sentence.
  • Explain a sound finite consistency progression without assuming arbitrary consistent extensions remain consistent.

The second incompleteness theorem does not say that every sentence informally described as a consistency statement is unprovable. It applies to a particular arithmetized assertion of no proof of contradiction, with a provability predicate satisfying specific derivability conditions. Those conditions let a theory reason about transformations of its own proofs. We will follow that internal argument, then use a carefully scoped consistency progression to distinguish external justification from what a theory can establish about itself.

Fix both the base theory and the provability predicate

Take a consistent c.e. theory T extending Peano arithmetic, with a standard effective proof coding and certified axiom uses. This strength is a convenient sufficient hypothesis, not a claim of minimality. Write Box phi for Prov sub T applied to the numeral coding phi, and bottom for the false arithmetic sentence zero equals one. Define the internal sentence Con(T) as not-Box-bottom. Its intended meaning refers to the chosen proof system and coding; alternative exotic predicates cannot simply be substituted without checking their properties.

The Hilbert–Bernays–Löb conditions say: if T proves phi, it proves Box phi; T proves that Box of an implication combines with Box of its antecedent to give Box of its consequent; and T proves that Box phi implies Box-Box phi. The first is an external rule about T-proofs, while the other two are internal schemes. Standard provability for c.e. extensions of PA satisfies these conditions through formalized finite proof transformations and arithmetic reasoning.

T⊢φ⇒T⊢□φ;T⊢□(φ→ψ)→(□φ→□ψ);T⊢□φ→□□φ.T\vdash\varphi\Rightarrow T\vdash\Box\varphi;\quad T\vdash\Box(\varphi\to\psi)\to(\Box\varphi\to\Box\psi);\quad T\vdash\Box\varphi\to\Box\Box\varphi.
These are derivability hypotheses for the particular provability predicate, not unrestricted reflection principles.↔ Scroll wide equations horizontally.

Formalized proof transformations expose the obstruction

Choose a diagonal sentence G with T proving G equivalent to not-Box-G. Internally, Box-G implies Box-not-Box-G by the first two derivability conditions applied to the forward implication. The third condition also gives Box-Box-G. Combining these two boxed contradictory assertions through the formalized propositional rules yields Box-bottom. Contraposition gives Con(T) implies not-Box-G, hence Con(T) implies G by the fixed-point equivalence.

If T proved its internal Con(T), it would therefore prove G. The first incompleteness argument excludes that under consistency. Thus T does not prove this Con(T). No assumption of omega-consistency is needed for this unprovability conclusion. The proof relies on the internal derivability conditions, especially positive introspection, rather than merely the external fact that a proof checker exists. We do not establish arbitrary reflection, which would infer every asserted provability statement's conclusion.

T⊢□G→□⊥,T⊢Con⁡(T)→G,T⊬Con⁡(T).T\vdash\Box G\to\Box\bot,\qquad T\vdash\operatorname{Con}(T)\to G,\qquad T\nvdash\operatorname{Con}(T).
The last judgment uses external consistency; the first two implications are derivable within T.↔ Scroll wide equations horizontally.

Relative consistency must identify the stronger metatheory

A stronger theory may prove the consistency of a weaker one without contradiction to this theorem. Such a relative consistency argument must specify which proof predicate and ambient theory formalize the comparison. Inclusion of axioms gives a transformation of weaker proofs into stronger proofs; if a base theory verifies that transformation, it proves that consistency of the stronger theory implies consistency of the weaker. The reverse implication is not automatic from inclusion.

For a clean progression example, assume externally that PA is sound in the standard natural numbers. Starting with T0 equal to PA, let each next finite theory add the standard Con sentence for the previous theory. Soundness inductively makes that new sentence true, so every finite stage remains sound and c.e. Second incompleteness shows the new sentence was unprovable at the preceding stage. Plain consistency of an arbitrary possibly unsound theory would not justify the same soundness argument or guarantee that adjoining its consistency sentence preserves consistency.

T0=PA,Tn+1=Tn+Con⁡(Tn)under the external standard-model soundness assumption.T_0=\mathrm{PA},\qquad T_{n+1}=T_n+\operatorname{Con}(T_n)\quad\text{under the external standard-model soundness assumption}.
The finite progression illustrates stronger theories proving earlier consistency statements; it is not an internal PA proof of its own consistency.↔ Scroll wide equations horizontally.

Work it through

Derive Con(T) implies G using only the stated proof conditions

Under the fixed-point equivalence T⊢G↔¬□GT\vdash G\leftrightarrow\neg\Box G and the three derivability conditions, produce the internal implication Con(T)→G and infer the second incompleteness conclusion.

  1. Since T proves G→¬□GG\to\neg\Box G, necessitation for theorems and the implication condition give T⊢□G→□¬□GT\vdash\Box G\to\Box\neg\Box G. Positive introspection independently gives T⊢□G→□□GT\vdash\Box G\to\Box\Box G.

  2. Formal propositional proof combination inside the boxes turns Box of Box-G and Box of not-Box-G into Box-bottom. Therefore T⊢□G→□⊥T\vdash\Box G\to\Box\bot. Contraposition yields T⊢¬□⊥→¬□GT\vdash\neg\Box\bot\to\neg\Box G.

  3. Replace not-Box-bottom by the definition Con(T), and use the reverse direction of the fixed-point equivalence to obtain T⊢Con⁡(T)→GT\vdash\operatorname{Con}(T)\to G. If T proved Con(T), modus ponens would prove G, contradicting the previously established consistency-based unprovability of G.

□G⇒(□□G∧□¬□G)⇒□⊥;¬□⊥⇒¬□G⇒G.\Box G\Rightarrow\bigl(\Box\Box G\land\Box\neg\Box G\bigr)\Rightarrow\Box\bot;\qquad\neg\Box\bot\Rightarrow\neg\Box G\Rightarrow G.
Every displayed implication in this chain is formalized in T; external consistency is used only to exclude a T-proof of G.↔ Scroll wide equations horizontally.
The result

A consistent T with the specified standard provability conditions cannot prove its own chosen internal consistency sentence. The proof does not assert that every true sentence is unprovable.

The living notebook

Explore the model

Interactive lab

Interactive lab · modular

Prove a finite invariant instead of extrapolating from a few steps

Pause and Reset, set modulus 12 and step 4. After three Steps the orbit 0,4,8,0 closes; prove that every visited state remains divisible by four. For a fresh run Reset and set both modulus 12 and step 3; four Steps close 0,3,6,9,0. These closure and invariant proofs justify all-time claims for these exact finite transition rules. They are not arithmetic consistency proofs or an implementation of provability logic. Each Step is one update; parameter changes retain time.

Prove a finite invariant instead of extrapolating from a few stepsAddition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Current readings: Residue r0: 0; Orbit period · m/gcd(m,a): 12; Distinct residues visited: 1 of 12. All parameters are adjustable with the labeled controls below.Repeated addition modulo 12: the current residue is 0, and the orbit period is 12.01234567891011+ 5mod 12An additive orbitn = 0rₙ = 0Period = 12Cycle starts at 0:0 → 5 → 10 → 3 →8 → 1 → 6 → 11 →4 → 9 → 2 → 7 → 0Exact residues · two additions per second
Additive orbitCurrent residue / next edge
Residue r0
0
Orbit period · m/gcd(m,a)
12
Distinct residues visited
1 of 12
t = 0 s

Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forAn all-time assertion needs a proof tied to its rules; a finite display alone is insufficient.

Pause & reason

Check your understanding

Under the standard hypotheses, what exactly does second incompleteness exclude?

Your turn

Try it yourself

Assume externally that PA is sound in the standard natural numbers. Form T1=PA+Con(PA) and T2=T1+Con(T1). Explain why both are sound and why each new consistency sentence was unprovable at the preceding stage. State why replacing soundness by arbitrary consistency would leave a gap.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

A true added axiom preserves standard-model soundness. Apply second incompleteness separately to each preceding effective theory.

Compare with the solution

PA soundness implies PA is consistent, so its standard consistency sentence is true in the natural numbers. Adding it makes T1 sound; then Con(T1) is likewise true and T2 is sound. Both are c.e. extensions of PA. Second incompleteness applied to PA and T1 separately shows that neither proves its own consistency sentence, so each extension adds a previously unprovable axiom. An arbitrary consistent theory can be unsound, and consistency alone does not validate this truth-preservation argument or generally justify adjoining its own consistency assertion.

Keep the idea

Take it with you

  • The internal consistency sentence depends on the selected arithmetized proof predicate.
  • Standard derivability conditions permit the internal Con(T)→G argument.
  • Sound finite consistency progressions need an explicit external soundness justification.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.