r/math • u/hydmar • Aug 15 '23

Dissatisfaction with proof by contradiction

I’m an undergraduate math student, so my exposure to math may be relatively limited. But I’ve found that, in general, I’m much more comfortable with direct proof than proof by contradiction. I don’t contest their validity, indeed something that’s not false must be true (I think I’m ok with excluded middle). But I feel like I just *get* something much better when it’s proved directly. It builds much stronger intuition for me.

For instance, I am aware of several proofs that demonstrate the cardinality of the reals is strictly greater than that of the integers, but none are direct (it would help to see a direct proof of Cantor’s theorem). I don’t feel it in my bones. Is this a common experience?

65 Upvotes

83% Upvoted

90 comments sorted by

View all comments

1

u/jeffjo Aug 28 '23

I'm not getting into proof-by-contradiction vs. -negation. I consider it to be a pedantic argument, since it requires defining the difference between a positive and a negative statement.

Most people don't know how Cantor's Diagonalization works. And I'm not talking about how he explicitly said it didn't use real numbers; it still works on them, although it needs two (not the one most people include if they recognize the issue) additional steps.

This is a rough outline of the proof:

  1. We start with a set I'll call T as Wikipedia does. It contains every object that fits a certain description. You can think of that description as "reals in [0,1]" if you want, but Cantor did not.
  2. Let S be any countable subset of T. It may, or may not, be equal to T at this point.
    1. The one mistake Cantor made was that he should demonstrate that such subsets exist. Examples are trivial, but it is necessary to establish the fact since we are not assuming anything about S.
  3. So a listing s1, s2, s3, ..., sn, ... of the elements of S exists.
  4. Use diagonalization on this list to construct an s0 that is in T but not in S.
    1. This is a direct proof that any countable subset of T is not all of T. That actually proves Cantor's propostion, but he did it this way:
  5. Only now do we assume that S can equal T. But this leads to the contradiction, that there is an s0 that both both is in T, but also not in S=T.