[FOM] RV: Is Godel's Theorem surprising?

[ignacio]

In reply to my comment: 

"It is possible to prove Gödel's first theorem without using
diagonalization, that’s right: but any other technique you use to prove it
is, from a formal mathematical point of view, equivalent to diagonalization"

Aatu Koskensilta wrote:

"Why? How does Kripke's proof as presented by Putnam, for example, 
involve diagonalization "from a formal mathematical point of view"? And 
even if it does, how do you justify the (staggeringly strong) claim that 
any proof of incompleteness must involve diagonalization?"

Because of my clumsiness, I expressed it rather boldly and dogmatically, I
apologize: what I was aiming at is something that I think we all agree on:
you can use diagonalization, concatenation or any sort of recursive coding,
but what you are always proving is "Gödel's first theorem", no matter what
technique is used: it is always rather vague to compare mathematical
"methods": when I said that any possible method used to prove Gödel's first
theorem is "from a formal mathematical point of view equivalent to
diagonalization" I was simply trying to say that any model is isomorphic to
itself, that is to say: if a theory is "compact" it is possible to construct
a proposition that is inconsistent with that theory: this of course can be
proved without using model theory, but it does not change the fact that, for
instance, given two isomorphic models, there is a proposition that is
inconsistent relative to both of them: this shows what I was trying to say
about the "equivalence" of the possible techniques used to prove Gödel's
first: of course, this "equivalence" can not be proved mathematically,
because to try to demonstrate the theorem "any technique used to prove
Gödel's first theorem is equivalent to diagonalization" would be, if I am
not mistaken, mumbo jumbo.

Regarding Putnam's methods: there is an early paper of Putnam published in
the JSL in 1957: "Decidability and essential undecidability"; it is an
interesting fact that later on Smullyan proved the following theorems
without any fixed point argument:

Theorem A. If (A1, A2) is semidoubly universal and A1 and A2 are both
recursively enumerable, then A1 and A2 are both universal sets.

Theorem B. If (A1, A2) is semidoubly universal and A1 and A2 are both
recursively enumerable, then (A1, A2) is doubly universal. 

Both these theorems are derived from early ideas of Putnam which are still
latent in his presentation of Kripke's proof, and they go to the heart of
the question of the incompleteness phenomenon: to my mind, this "heart" of
the question is the following fact: given the recursively enumerable
disjoint pair (A, B) and the function f(x) mapping A into C and B into D,
there is a complete and non-trivial system in which (A, B) is circular.

Regards,

I. Nattochdag.   



 

-- 
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.409 / Virus Database: 268.15.16/582 - Release Date: 11/12/2006