December 4, 2005

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.

2 comments:

  1. "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.

    You have unstated premises, don't you? Kinda confuses us stupider people. ;)

    My stab:

    1. A all squares have 4 90-degree angles. (All S1 are S2)
    2. All shapes with 4 90-degree angles are rectangles. (All S2 are R)
    Then:
    3. If a shape is a square, than that shape is a rectangle. (If P then Q - isn't this a premise?)
    4. P
    5. Q.
    OR
    4. Assuming ~P
    5. Then ~Q
    6. Then 2 and ~2??

    I can't figure it out.

    I haven't done formal logic in a year or so and was never very good at it to begin with. Maybe you can straighten me out.

    ReplyDelete
  2. By the way, I don't really get the exercise -- can I just say that we can infinitely add an and to the sentence?

    It seems that we would reach a limit of intelligible sentences pretty quickly... eventually we'd have to make up redundant or gibberish sentences. Are we still dealing with sentences then?

    ReplyDelete

You MUST enter a nickname with the "Name/URL" option if you're not signed in. We can't follow who is saying what if everyone is "Anonymous."