Diagonal Lemma - Proof

Proof

Let f: N→N be the function defined by:

f(#(θ)) = #(θ(#(θ))

for each T-formula θ in one free variable, and f(n) = 0 otherwise. The function f is computable, so there is a formula δ representing f in T. Thus for each formula θ, T proves

(∀y) ,

which is to say

(∀y) .

Now define the formula β(z) as:

β(z) = (∀y) ,

then

β(#(θ)) ⇔ (∀y) ,

which is to say

β(#(θ)) ⇔ ψ(#(θ(#(θ))))

Let φ be the sentence β(#(β)). Then we can prove in T that:

(*) φ ⇔ (∀y) ⇔ (∀y) .

Working in T, analyze two cases:
1. Assuming φ holds, substitute #(β(#(β)) for y in the rightmost formula in (*), and obtain:

(#(β(#(β)) = #(β(#(β))) → ψ(#(β(#(β))),

Since φ = β(#(β)), it follows that ψ(#(φ)) holds.
2. Conversely, assume that ψ(#(β(#(β)))) holds. Then the final formula in (*) must be true, and φ is also true.

Thus φ ↔ ψ(#(φ)) is provable in T, as desired.

Read more about this topic:  Diagonal Lemma

Famous quotes containing the word proof:

    “There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
    —Herman Melville (1819–1891)

    “The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
    —Andrew Michael Ramsay (1686–1743)

    “A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
    —Samuel Johnson (1709–1784)