Re: Comparing Proofs of Rosser's 1936 Theorem


David C. Ullrich wrote:
On 19 Feb 2006 15:15:30 -0800, "Charlie-Boo" <chvol@xxxxxxx> wrote:

What is the relationship between the following two proofs of Rosser's
1936 theorem?

1. [Turing 1937] We can list the provable sentences, and by negating
each list the refutable sentences. If the system is both complete and
consistent then any given sentence will be provable or refutable but
not both, and thus will be seen in either but not both lists, and we
can tell if the given sentence is provable, which amounts to solving
the halting problem where halt yes means provable and halt no means
refutable, so halt means decidable.

2. [C-B 2005] If the system is both complete and consistent, then the
refutable sentences coincide with the unprovable sentences, but the
former is an r.e. set whereas the latter is not.

They're essentially the same proof.

The first is written out in much more detail, perhaps
because the concepts mentioned in the second were less
well-known in 1937 or perhaps just because it happens
to be written out in more detail. And of course there
are various _other_ ways the details could be filled
in in the second.

But the two are essentially the
same - the one basic idea appears in both proofs,
in different words.

Really? Well, you really beat me on that one, David. I thought they
were different. So, what is the basic idea that appears in both? I
want to learn where I went wrong and correct my mistake.

I thought # 2 was shorter, simpler, doesn't involve knowing the proof
that the Halting Problem is unsolvable, and is easier to understand.
What is the "one basic idea" that you are referring to that you
discovered appears in both proofs?

Thanks for the help,

C-B

************************

David C. Ullrich

.

Relevant Pages

  • Re: Comparing Proofs of Rossers 1936 Theorem
    ... David C. Ullrich wrote: ... not both, and thus will be seen in either but not both lists, and we ... The basic idea in your quoteof Turing is given by what ...
    (sci.logic)
  • Re: Comparing Proofs of Rossers 1936 Theorem
    ... David C. Ullrich wrote: ... not both, and thus will be seen in either but not both lists, and we ... refutable sentences coincide with the unprovable sentences, ... Well, you really beat me on that one, David. ...
    (sci.logic)
  • Re: Mathworld errors
    ... >>Dear David Ullrich, ... I have kept lists of errors, and used to submit them to Eric every once in ... large part of my life doing nothing but correcting MathWorld errors... ...
    (sci.math)
  • Re: Comparing Proofs of Rossers 1936 Theorem
    ... David C. Ullrich wrote: ... refutable sentences coincide with the unprovable sentences, ... Or is it all just a lie to try to deny me ... rely on known facts concerning the provable and refutable sentences. ...
    (sci.logic)
  • Re: Comparing Proofs of Rossers 1936 Theorem
    ... not both, and thus will be seen in either but not both lists, and we ... refutable sentences coincide with the unprovable sentences, ... If your point is that Turing simply lacked the sophistication to ... formalize and fine-tune his analysis. ...
    (sci.logic)