Everyday proof techniques: by contradiction

This is a great technique to know, whether you're using it in math theorems, linguistic analyses, or just everyday argument. It's also great if you're a teacher, because it's pretty simple to teach. Basically, rather than directly prove your claim, you're going to assume that it's wrong and then show how a contradiction follows from that mistaken assumption. Sidebar: a cause-and-effect argument takes the form "If X is the case, then Y is the case." It is only wrong if the premises (if-part) are true but the conclusion (then-part) is false -- in other words, if a supposed cause doesn't result in the supposed effect, your cause-and-effect argument is false. Now, only false statements can imply contradictions, so your mistaken assumption must have been false -- that is, your claim was correct after all!

In everyday arguments, your assumption may imply only an "absurdity," whether a logical contradiction or otherwise, in which case the technique is called reductio ad absurdum. Just bear in mind that what's absurd to one may not be so to another. Two examples, one from high school geometry and another from linguistics.

First, let's say you want to prove the statement that "If a quadrilateral x is a square, then that quadrilateral x is also a rectangle." Let's assume this statement is false -- then we grant the premises are true, but deny that the conclusion follows from them. So the shape x is a square, which means it has all 90-degree angles. But if shape x is not a rectangle, then at least one of the angles must be something other than 90. However, this contradicts what we said before about all of them measuring 90 -- this is a contradiction, and we only arrived at it by assuming the original statement was false. Therefore, the original statement must be true.

Second, one from the field of syntax in linguistics, which has to do with how words are put together into phrases and sentences. The claim is that "There is no longest sentence" -- i.e. a sentence which is longer than all others in how many words it contains. You may think this is true, but we'll prove that it is. Let's assume it's false -- so there is a longest sentence, which we'll call K. Now, in English as in all languages, there are rules that show how sentences can be formed, one of which is the following:

1) S --> S and S

What this says is "a sentence may-consist-of a sentence, followed by the word 'and,' followed by another sentence." Some version of this rule is going to be in anybody's grammar for any language since they all have sentences and conjunctions like "and." So, we'll just take our longest sentence K, stick "and" to the right of it, and then to the right of that stick any other sentence in the language we want -- let's call this one L. So, now we have "K and L" -- which in turn is a sentence according to 1). Let's say that sentence K is of length n, while L is of length m (which is less than n), where both m and n are nat. numbers. Then our new sentence has length n + m + 1, which is surely longer than just n. But that contradicts how we chose K -- we chose it to be the longest sentence. This contradiction arose from assuming there is a longest sentence in the language, which must be false; thus, the original statement must be true. Note that the words that make up K and L are irrelevant -- we didn't say it would be an interesting sentence; we only cared about how long it was.

Exercise: this relates somewhat the the previous example. Prove by contradiction that, in addition there not being any longest sentence, there are an infinite number of possible sentences in any language. You only have to use the simple rule 1) above to do it.