Re: Question about proof by contradiction

In article <rj2et3lh0seqs777uac7moogtmcm3rstcd@xxxxxxx>,
G. Frege <nomail@invalid> wrote:
On Tue, 11 Mar 2008 20:56:57 +0000 (UTC), magidin@xxxxxxxxxxxxxxxxx
(Arturo Magidin) wrote:


On a related note, what is your take on whether the
diagonal proof of the uncountability of the reals is
or is not a proof by contradiction, or an RAA proof.

There is no "the diagonal proof". There are several variants, just as
there are several variants of the proof of infinitude of the
primes. Some of the variants are proofs by contradiction, but perhaps
the point is that there are variants which do not require an argument
by RAA.

A week ago or so there were several statements by
the upstanding regulars that it is not, but I didn't really
follow. It seems to me, roughly:

1. Assume there exists a list of all real numbers.
(a surjection f:N -> R)
2. We can construct a function which, given f above
as a parameter, returns a real number which is
not in the codomain of f.
3. 1, 2 are a contradiction
4. Therefore the assumption in 1. is false.

Am I doing something wrong?

No, but you do not have to do it this way. You can instead argue as
follows:

A. Let f be an ARBITRARY function f:N -> R.
B. Construct a number x_f, which depends on f, which is not in the
range of f.
C. Conclude that f is not surjective.
D. By universal quantification, conclude that if f is any function
from N to R, then f is not surjective.

Right. If you would stop here, you would be completely right.

For the statement "if f is an arbitrary function f:N->R, then f is not
surjective".

E. Conclude by contrapositive there is no surjection from N to R.

This proof is not by contradiction.

It is. But it is _hidden_ in the last step, you simply refers to as "by
contrapositive". If you try to _justify_ contraposition in, say, a
system of "natural deduction" you will see that you actually NEED RAA
(negation introduction) for this step.

1 (1) P -> Q Assumption
2 (2) P Assumption
1,2 (3) Q 1,2 MPP
4 (4) ~Q Assumption
1,2,4 (5) Q & ~Q 3,4 &I
1,4 (6) ~P 2,5 RAA
1 (7) ~Q -> ~P 4,6 CP
(8) (P -> Q) -> (~Q -> ~P) 1,7 CP

See?

In that case, wouldn't the implicit claim that

"Any list of real numbers is incomplete"

and

"There is no list of all real numbers"

are equivalent not also hide a reductio ad absurdo argument? Or even
that one implies the other?

If so, then even "changing the subject" to the first proposition above
consistutes a hidden invocation of RAA.

One reason why it may be "cleaner" than your argument ...

It's not. Actually, it just _hides_ the "indirect proof".

Wouldn't going from one proposition to the other likewise "_hide_" the
'indirect proof'?

above is that while you cast it as an argument by
contradiction, in fact the only time that the assumption 1 is used
at all is in in step 3;

Right. This amounts to the application of your "by contrapostion".
(Which just hides the application of RAA).

Or to changing from "The real numbers are uncountable" (i.e., there is
no surjection from N to R) to "every list of real numbers is
incomplete". So rather than the 'hiding' being donee in the last step,
it is done when one changes the subject? Does it not likewise amount
to doing an indirect proof "in hiding" or "implicitly"?

You can do that with any proof. You can prove that 1+1 = 2 "by
contradiction" by taking any proof that 1+1=2, prefacing it with
"assume that 1+1 is not equal to 2", and then adding at the end "this
contradicts the hypothesis that 1+1 is not equal to 2, therefore we
conclude that 1+1 is equal to 2".

This analogy is NOT appropriate, sorry.

Analogy?

I said "You can do that with ever proof"; okay, say that I am wrong
about the proof I gave being direct. Is it not true that you can take
any direct proof and change it into an indirect proof by contradiction
by assuming the negation of the conclusion, then doing the direct
proof, and then invoking RAA to derive the conclusion?

In that sense, what I give above is an example of this, surely.

I would point out the difference between the argument given (okay,
throw in my proof if you want) with, say, the proof by contradiction
that sqrt(2) is not rational. In that proof, the assumption that
sqrt(2) is rational is required in order to do the next steps; whereas
in the proof the other poster gave (and if you want, my proof) the
steps do not depend on the assumption of the contrary hypothesis: they
can be performed in their absence. In that respect, the proof by
contradiction that there is no list of all reals, or the proof by
contradiction that the set of primes is infinite, is of a different
"quality" than the proof by contradiction that sqrt(2) is irrational.


--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.

Relevant Pages

  • Re: Review of Mueckenheims book.
    ... >> proof by contradiction is wrong ... It is said that Euclid assumed ... Cantor assumed a complete list of reals and showed the existence ... I do not know of such an axiom. ...
    (sci.math)
  • Cantors diagonal proof wrong?
    ... When I was shown Cantor's diagonal proof that the number of reals was not ... infinity, you are making some basic assumptions on what an idea is. ... of the size of an infinite set is a contradiction in itself). ... So you just reverse the digits in the integer to create the real. ...
    (sci.math)
  • Re: infinitely many nns = infinite nns?
    ... proofs, one which shows that there is a FINITE distance (or difference, ... if you must) between any two reals on the line segment (which is why I ... What "infinite sum of finite distances"? ... We are still waiting for you to present the contradiction. ...
    (sci.logic)
  • Re: Question about proof by contradiction
    ... diagonal proof of the uncountability of the reals is ... or is not a proof by contradiction, or an RAA proof. ... Some of the variants are proofs by contradiction, ... E. Conclude by contrapositive there is no surjection from N to R. ...
    (sci.math)
  • Re: A question about Caontors proof of the uncountability of the reals
    ... understanding Cantor's diagonalization proof: assume the reals are ... countable, show that this assumption leads to a contradiction, conclude ... Cantor's proof of the uncountability of the reals per se, ... Does this answer your objection? ...
    (sci.math)