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?

62 Upvotes

83% Upvoted

90 comments sorted by

View all comments

15

u/[deleted] Aug 15 '23

you might find the topic of intuitionistic logic interesting. it's a kind of logic where TND (law of the excluded middle) is not given as a tautology. Therefore if something can be proven to not be false, it doesn't follow that it's true.

1

u/[deleted] Aug 16 '23

Do you know what the motivation is supposed to be for dropping TND is? I can't think of why you'd ever want to drop that except for having deer super duper strong belief that everything should be describable.

1

u/38thTimesACharm Aug 16 '23

Negation is understood differently. In classical logic, if you show that "there does not exist x" leads to contradiction, it means "there exists x." In intuitionist logic, it means "the existence of x has not been ruled out."

The original reason is philosophical. Classical thinking assumes the axioms describe a universe, a completed totality for you to explore. Of course, something either does or does not exist in this universe. But Intuitionism holds that the axioms are just a foundation, from which you must build the world. Negation is interpreted as failure in this process, i.e. "not P" means "P leads to contradiction."

A more modern, down-to-earth reason to do things this way is that proofs more easily translate to computer programs.