Proof by contradiction

Miscellaneous and Personal Stuff I Must Share
1

I almost put this in GQ, but then decided it’s a bit too much of a “stoner” topic for that forum.

I’m a math major, but I’ve always found proof by contradiction a little emotionally unsatisfying. It’s an extremely powerful technique used all over the place in mathematics, but it has always troubled me viscerally.

I get it on an intellectual level:

To prove premise A:

  • Assume not A
  • Therefore…
  • Therefore…
  • Therefore…(some absurd statement like 1=0)

The rationale being that since we ended up with a contradiction, the original premise must have been false, therefore not (not A), therefore A, QED. This follows from the truth table for “implication”, since only “false” implies “false”.

The reason I find this emotionally unsatisfying is that it seems such an indirect way of proving something; I have to accept it based on the rules of logic and the way “implication” works, but something irks me about ending up at a ridiculous statement, and thereby proving our original premise.

It also seems so arbitrary - you’re trying to prove something with a binary truth value, yet any old contradiction will do the trick. So if you end up with pi = 4 (not a contradiction but an error?), or 2 > 3, or 1 = 0, or “2 is both odd and even”, any of those will do.

Also, has anyone studied exactly what causes you to end up with a particular contradiction, and not some other contradiction? e.g. when I try to prove Fermat’s Last Theorem, I end up with “therefore this elliptical curve isn’t a modular form” (or something…apologies to Andrew Wiles) but when I try to prove sqrt(2) is rational, I end up with “therefore p/q could not have been a fraction in its simplest form”. Is there any information to be gleaned from the particular contradiction that arises? Being a mathematical sort, I’m not content to leave that little box unopened, not to ask why we ended up with that particular contradiction. Could there be some deeper meaning behind the particular contradiction that one ends up with? (in a mathematical sense…I’m not totally off into lala land here.)

2

How do you feel about the law of the excluded middle?

3

It’s a good thing :slight_smile:

Is this a serious question, or are you asking, “If you’re questioning something as basic as reductio ad absurdum, then how about other fundamental tenets of logic like the Law of the Excluded Middle?” ? As mentioned in the OP, I’m not questioning the validity of proof by contradiction, just expressing my unease about it, viscerally.

I’ve read a little on fuzzy logic, and after everything I’ve read, I always come away with the impression that if you end up with a “fuzzy” answer, then the question wasn’t phrased precisely enough.

For example, “Is person A tall?” might be considered a fuzzy question. But if you rephrase it as “is person A taller than 6 feet?” you get a binary answer.

I’m not sure how “indeterminate” questions play into this. “Is 0/0 greater than 5?” I don’t see how you can assign a truth value to that.

ETA: I understand that proof by contradiction requires the LEM in order to be valid. But the LEM somehow doesn’t rub me the wrong way, perhaps because it seems “neater”.

4

I actually feel the opposite: proof by contradiction is a pretty neat way of proving something. Probably because it is so rigorously logical.

5

Proofs by contradiction are non-constructive, in the sense that using them you don’t get to build the object under consideration. You can, for example, prove by contradiction that something exists, but you’ll have no idea what it is or how to obtain it. For this reason, in some branches of mathematics, applied math for example, they can be somewhat unsatisfying.

6

I thought the “excluded middle” referred to the business plan, on South Park, of:

  1. Steal underwear.
  2. ???
  3. Profit!
7

While any contradiction will work, giving some of the benefit and some of the unease with this type of proof, in practice, the contradiction is usually with one of the givens. And this is why I always liked proof by contradiction. The proof that the theorem is true is based on the fact that that the system of mathematics is not consistent if it’s false. I always likened it to math being a kind of monster that eats conjectures, and then vomits up the ones that don’t “agree” with it.

So, there’s that.

8

Think about the proof that the square root of 2 is irrational. How could you possibly prove except by assuming it is rational and seeing a contradiction arise. There is inherent in the definition of irrational as not rational.

Many proofs by contradiction can be reworded to be constructive. The usual proof of the infinitude of the primes is actually a recipe for constructing one more prime. Given any set of primes, take their produce and add 1. That number leaves a remainder of 1 when divided by any number on the original list. So any prime divisor is a new prime.

You might be happier sticking to constructive mathematics. For example, Errett Bishop’s book, Constructive Analysis does everything constructively. Starting with the constructive real numbers. A constructive real number is a pair of recursively enumerable sequences, say {a_n} and {b_n} of sequences of integers such that the second sequence is provably never 0 and that for all m and n, a_n/b_n - a_m/b_m < 1/n + 1/m. Then you can define addition, subtraction, and multiplication of such sequences as well as division provided the second sequence is provably bounded away from 0. Equality is not decidable and it is relatively easy to construct such a sequence that we cannot prove is 0 and we are unlikely to prove non-zero within the current age of the universe. If you like doing math with one hand and four fingers on the other hand tied behind your back, this might be the very thing for you.

Let me just mention one fact. You have probably heard of the Brouwer fixed point theorem. Any continuous motion of the closed unit disk on itself has a fixed point. The argument uses compactness and Brouwer, who became an intuitionist (another variation, which I know nothing about) disavowed. Well, bishop mentions that, using his unit disk (which is not compact and not simply connected since it is full of holes) he can construct a continuous motion that has no fixed point. Whatever else you think of constructivism, this fact alone implies that Brouwer’s cannot have a constructive proof. Bishop can show that for every continuous map of his disk on itself, there is, for any natural number n, a constructible point which is moved by < 1/n. Using compactness, it is trivial to go from this fact to the Brouwer theorem. It is important to recognize that his definition of continuity is much stronger (for functions of one variable, it is defined to mean it is uniformly continuous on any closed interval and the modulus of continuity (delta as a function of epsilon) must be constructive.

I hope there is some food for thought here.