Wondering why proof by contradiction works

Solution 1:

This is a surprisingly difficult question! The short answer is that proof by contradiction is only valid when the propositions involved are "well-formed" in a certain precise sense - the usual approach is to define a formal language, and then require propositions to be expressed in that language. Now, the trick is that (by a theorem of Tarski) you can't set up a formal language in which a proposition can make claims about its own truth. Imagine explaining the sentence "This statement is false" to someone who doesn't quite get it:

YOU: "This statement is false."

THEM: "Wait, which statement?"

YOU: "That one."

THEM: "Which one?"

YOU: "The statement 'This statement is false'."

THEM: "Oh, ok. But which statement is that one talking about?"

And so on. That's basically the problem - a formal system forces you to explain what you're saying so precisely that statements like this just aren't possible.

Now, in practice, it's a pain to put everything in formal language. Generally, what we do is assume - until proven otherwise - that anything that isn't obviously self-referential could be written in formal language if we wanted to. Which is why you see proofs by contradiction of sentences in plain English.

There's a natural next question, though, that you're probably thinking: if we're allowed to limit the "scope" of proof by contradiction by saying "oh, well, it actually only applies to this sort of sentence", then how do we know we don't have to limit it further? The answer is - we don't. Most mathematicians take it as an assumption (an axiom, more or less, called the Law of the Excluded Middle). However, there's a branch of logic - intuitionistic logic - which rejects this assumption, basically saying "Sometimes, sentences might be neither true nor false." This is a perfectly functional way of doing mathematics, though it's typically much harder; like trying to ride a bike with one hand tied behind your back.

Solution 2:

In (most of) mathematics, "not true" means the same thing as "false" and "not false" means the same thing as "true". So if a statement isn't false, the only choice is that it is true. There's nothing more to it than that.

But, you protest, what then is going on with "This sentence is false"? It can't be either true or false! The answer is that this sentence simply completely breaks mathematics. That is, if you allow a sentence like "This sentence is false" to be part of mathematics, then you reach a contradiction (you can prove that it must be true, but also that it must be false). Since you can prove anything from a contradiction, this destroys all of mathematics.

So, if we want mathematics not to break, the solution must be simply that a sentence like "This sentence is false" is not a part of mathematics. After all, there are lots of other statements that are not part of mathematics, such as "The queen of England is a hamster", or "Blue is a better color than orange".

This raises the question of what statements are part of mathematics. Answering this question is a long story, but the brief answer is that we are restricted to statements that we can express in a certain completely precise formal language. This formal language lets us refer to all our usual mathematical concepts and logical relations between them. If we want to interpret an informal English statement as a real mathematical statement, we need to find a way to translate it into this formal language. It turns out that there is no obvious way to translate a statement like "This sentence is false" into our formal language (and we hope there's not a non-obvious way either, since if there were, then mathematics would break!).

Solution 3:

Hint: look into Tarski's theorem on the undefinability of truth.

Solution 4:

How do we know that the statement being examined does not suffer from the same problem as the proposition above?

The proof by contradiction applies to statements of the form A -> B, and won't work if either A or B entails a contradiction.

When we prove a statement by contradiction, we assume the negation of the statement, find a contradiction, and conclude that the statement must be true. Why is the latter conclusion valid?

So, assuming that neither A nor B entails a contradiction, then you consider A ^ -B (A and not B). If A ^ -B implies a contradiction, then the only way that could happen (assuming that A is true) is when -B is false. If -B is false, the B must be true.

Another way to look at it is that A ^ -B is a contradiction if A entails B. In that case, we have A = A ^ B (whenever A is true so is A ^ B, also whenever A is false so is A ^ B). Therefore A ^ -B becomes A ^ B ^ -B (the required contradiction) because of the equality mentioned in the previous sentence. But A ^ B implies B, So A (which is equal to A ^ B) implies B, ie: A -> B.

PS: Sorry for not using the proper symbols, but the MathJax thing wasn't working properly, and this is my first reply in this forum (I don't know how to use the symbols).