Re: Comparing Proofs of Rosser's 1936 Theorem


Daryl McCullough wrote:
Charlie-Boo says...

Daryl McCullough wrote:

Here's the claim, you give me the proof:

For any consistent r.e. theory T extending PA, the set of non-theorems
is not r.e.

You mean is not representable? You agree that's trivial, right?

Well, that's basically Godel's theorem. But Rosser's theorem does
not follow trivially from Godel's theorem.

Let's label the claims here:

S1: For any consistent r.e. theory T extending PA, the set
of theorems of T is not representable in T.

S2: For any consistent r.e. theory T extending PA, the set
of theorems of T is not a recursive set.

S3: For any consistent r.e. theory T extending PA, T is not
complete.

You seem to be thinking that if T were complete, then theoremhood
would be representable in T, contradicting S1. But why would
theoremhood be representable in T?

The correct argument is that if T were complete, then theoremhood
would be *recursive*, contradicting S2. But then how do you prove
S2?

If every recursive set is representable in T, then S1 implies S2,
which implies S3. But how do you know that every recursive set is
representable in T?

Your proof was simple because you left out all the hard parts.

Please clarify:

1. You said "Why do you believe that the set of unprovable sentences
is not representable?". I said, "Trivial diagonalization." You
said, "No, diagonalization doesn't do it."

Do you believe that the set of unprovable sentences is not
representable? Do you really believe that this cannot be proven by
simple diagonalization?

2. You continued, "That's basically Godel's theorem. But Rosser's
theorem does not follow trivially from Godel's theorem."

Who or what suggests or implies that Rosser's Theorem follows
trivially from Godel's theorem?

3. In 2, are you referring to my use of the word "trivial"?

4. You say "You seem to be thinking . . . The correct argument is . .
.. Your proof was simple because you left out all the hard parts."
This seems to be saying that my proof is wrong, but it is simple only
because it lacks details. But if it is wrong, then simplicity is
irrelevant because we're not talking about a proof anyway (only a
misconstrued attempt at a proof.)

5. You say, "How do you prove S2?" Is there some reason that I
should or implication if I don't or can't?

6. You say, "How do you know that every recursive set is
representable in T?". Is there some reason that I should or
implication if I don't or can't say?

7. You say, "Your proof was simple because you left out all the hard
parts." What parts did I leave out? What parts did Turing leave
out?

Thanks,

C-B

--
Daryl McCullough
Ithaca, NY

.

Relevant Pages