Re: doubting contradiction

From: Acid Pooh (poohonlsd_at_yahoo.com)
Date: 07/13/04 

Date: 12 Jul 2004 18:10:44 -0700

Mitch Harris <harrisq@tcs.inf.tu-dresden.de> wrote in message news:<2lfimrFbveb9U1@uni-berlin.de>...
> Bryan Olson wrote:
> > Peter Olcott wrote:
> > > The only thing that I am retaining of the original is the original
> > > conclusion of the original proof. The original proof claimed
> > > (paraphrase) that it has proven that the construction of a
> > > program that can correctly detect whether any element of the
> > > universal set of programs halts is impossible.
> >
> > What a mess. 'The only thing [he is] retaining of the original'
> > he has *wrong*.
> >
> > > My only (very tentative at the moment) claim is that I have
> > > shown that this conclusion of the original proof is incorrect.
> >
> > Does anyone who never posted as "GOD", nor claimed to be
> > psychic, think Peter has raised a serious doubt here? I (and
> > I'm sure others) don't want to dismiss questions by anyone
> > legitimately concerned.
>
> There is no doubt at all that he has not -shown- that
> anything is incorrect. Changed the problem possibly, but he
> hasn't shown anything.
>
> But I do think the discussion surrounding his claims have
> brought up questions (OK, only I have mentioned these doubts
> sincerely) about questioning the rule of inference "proof by
> contradiction". My skepticism is purely an intellectual
> exercise, in that I am wondering what things are provable
> with "proof by contradiction".

Well, there are a lot of equivalent formalizations of the first order
logic (equivalent in the sense that something can be proved true in
one iff it can be proved in the other modulo notation differences).
In particular, there is a version of FOL called Fitch which includes
reductio, and Mendelson uses a version which doesn't. Since they are
demonstrably equivalent (details left to the reader: I recommend
Mendelson's text), anything that can be proved with reductio can be
proved otherwise. The length of such proofs is likely astronomical in
most cases.

It seems pretty trivial to me that anything that can be proved
"normally" can be proved by
contradiction too.

'cid 'ooh

Relevant Pages
Quantcast