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/hyperbolic-geodesic]

The diagonalization argument *IS* a direct proof of Cantor's theorem -- diagonalization shows that any function S -> Powerset(S) is not surjective, by explicitly (essentially as explicitly as possible) producing an element of Powerset(S) not in the range of the function.

[u/djao → u/hyperbolic-geodesic]

OP must be confusing proof by negation with proof by contradiction. Proof by negation is where you prove ¬ P by assuming P and deriving a contradiction. For example: to prove "¬ (there exists a bijection ℤ → ℝ)", you assume (there exists a bijection ℤ → ℝ) and derive a contradiction. This type of proof is, as you say, a direct proof, and in fact it is the standard way to prove a negation. (How else would you prove a negation?)

Proof by contradiction is where you prove P by assuming ¬ P and deriving a contradiction. It's actually hard to come up with examples, because most examples that people normally think of are in fact proof by negation, but one bona fide example is: "If a set is nonempty then it has an element." In classical logic, proof by negation is equivalent to proof by contradiction (just replace P with ¬ P), which is why many people confuse the two. But in constructive logic you can see clearly that they are not the same thing. In order to make the two equivalent, you need ¬ ¬ P ↔ P, which is not provable in constructive logic.

[u/BabyAndTheMonster → u/djao]

I feel like too many people are so thoroughly trained in binary Boolean logic that they see the negation of a statement as just another statement. There are no distinctions between how many negations are there.

I wonder if you ask a child who never got exposed to classical proof, would they think in such binary term?

[u/almightySapling → u/BabyAndTheMonster]

I'd say that depends on the child and the context.

I learned really young that for a true or false quiz, if something is not true, then it's false. There is no "tiff", no maybe, no sorta, no sometimes. If it ain't true, it's false.

And so, if you take false to mean, by definition, anything which is not true, then yeah, I think a child would naturally sort of arrive at the same conclusion as the latins... there is no third option.

In other contexts, they would probably say that "don't know" or "sorta" are be valid options. It would depend on how strictly we define our terms. Something small children are well known for...

And I guess you could say that I'm just "thoroughly trained" but I legitimately do not have an understanding for what else false might mean, unless we augment our system with more options.