Re: Comparing Proofs of Rosser's 1936 Theorem

On 3 Mar 2006 06:42:50 -0800, "Charlie-Boo" <shymathguy@xxxxxxxxx>
wrote:


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?

The basic idea in your quote(?) of Turing is given by what
you wrote.

Thanks for the help,

C-B

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

David C. Ullrich


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

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: Peanos space-filling curve
    ... I've replied to four posts in one to save space and time. ... David C. Ullrich wrote in message ... I have difficulty with 'separate' applied to ordered reals. ...
    (sci.fractals)
  • Re: Peanos space-filling curve
    ... I've replied to four posts in one to save space and time. ... David C. Ullrich wrote in message ... I have difficulty with 'separate' applied to ordered reals. ...
    (sci.math)