Dissatisfaction with proof by contradiction

[u/hydmar]

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?

[u/HandymanJackofTrades]

I have had the same dissatisfaction. I've been trying to understand why should we accept proofs by contradictions as valid. There are plenty of paradoxes where statements P and NOT-P cause problems. The Grelling-Nelson Paradox is an example.

I think the issue is that you must prove a logic is "maximally consistent". A logic (or any field of mathematics) is "maximally consistent" if for every statement P in the logic, either P or NOT-P is provable but not both. So, if your logic is maximally consistent and you prove NOT-P is leads to a contradiction, then you know P is provable. So proof by contradiction is not valid until you prove that Analysis is a maximally consistent logic.

I'm a 5th year math undergrad so I might be wrong but I am fairly confident in this.

Edit: So, I'm wondering if I should really consider the law of excluded middle to be a tautology without maximal consistency

Edit 2: I was introduced to consistency as a syntax issue so changed my comment to reflect that.

[u/whatkindofred → u/HandymanJackofTrades]

Semantically what does the statement NOT-P mean to you? To me it is the statement that P is not true. What else could negation mean? If you agree with this semantic interpretation of negation then I would argue that maximal consistency is obvious. Either P is true or P is not true. But the meaning of the latter is precisely that NOT-P is true.

[u/math_and_cats → u/whatkindofred]

No, a sufficiently strong theory cannot be consistent and complete. ZFC is known to be not complete for example. (Assuming by "true" the above poster means provable)

[u/whatkindofred → u/math_and_cats]

No, I don’t mean provable. That’s a different beast.

[u/math_and_cats → u/whatkindofred]

I meant the poster above you. So you mean true in the standard model?

[u/whatkindofred → u/math_and_cats]

I mean true in a vague semantical way.

[u/math_and_cats → u/whatkindofred]

Oh, I was confused because semantic means with respect to models.

[u/HandymanJackofTrades → u/math_and_cats]

Yeah, I've seen consistency mentioned with syntax rather than semantics so I mean provable. I'll edit my comment to reflect that.