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:
“He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
—Herman Melville (1819–1891)
“It comes to pass oft that a terrible oath, with a swaggering accent sharply twanged off, gives manhood more approbation than ever proof itself would have earned him.”
—William Shakespeare (1564–1616)
“The chief contribution of Protestantism to human thought is its massive proof that God is a bore.”
—H.L. (Henry Lewis)