Logical Inconsistency

Brian and Mary agree to change the name of page 1 to "Proof by Contradiction" next year. --MF, 1/3/18

No EKs?

In this lab, you will learn that some problems can't be solved at all.

On this page, you will solve logic puzzles by finding a contradiction, that is, by showing that one possibility has to be true because the other possibility doesn't make sense.

  1. Imagine an island somewhere with two large families. One family (unlike normal people) can tell only the truth, even when they'd rather lie. This Truth-teller family can't ever make false statements, even by mistake. The other family, the False-Teller family, is just as reliable but in the opposite way: they can't make true statements ever.

    You are visiting the island and meet two of its people, Adam and Eve.

    Adam says, "Eve and I are from the same family."

    Talk with Your Partner
    1. Can you say for sure which family Eve is from? If so, which family?
    2. Can you say for sure which family Adam is from? If so, which family?
Betsy, Gamal, and Alphie are considering the problem above.
Betsy: I'm pretty sure Eve is a Truth-teller, but I don't know how to prove it.

A proof by contradiction is a two-step proof that something is false that is done by:

  1. assuming that it's true
  2. showing how that's impossible (that it creates a contradiction)

Gamal: Sometimes it's easier to prove that something is false than to prove that something is true. So let's assume the opposite of what you want to prove, and see where that leads us. Let's assume that Eve is a False-teller.
Betsy: Okay. So if Adam is a Truth-teller, then what he said is true, and they are from the same family, the Truth-tellers. But we assumed that Eve is a False-teller, so they're actually from different families, and so Adam can't be a Truth-teller.
Alphie: So, Adam has to be a False-teller.
Gamal: But that won't work either! If Adam is a False-teller, then what he said is false, and they are from different families. But they are both False-tellers, so they're actually in the same family, and so Adam can't be a False-teller either.
Betsy: No matter what family Adam is from, our assumption that Eve is a False-teller led us to a contradiction. Eve can't be a False-teller, so has to be a Truth-teller. We proved it.
  1. Imagine you meet someone named Derek on the island and you ask him if he's from the Truth-teller family. What does he answer?
  2. What if you ask Derek if he's from the False-Teller family?
Betsy and Gamal are exploring logical statements of their own.
Betsy: The statement I'm making right now is false.
Gamal: (Thinks for a moment) Wait! What?!?
  1. Betsy claims her statement is false. What do you think? Explain your thinking clearly.
Gamal: That's very clever, Betsy. Your statement can't be true, and it can't be false. No neither a Truth-teller nor a False-teller could say that.
There are four kinds of true/false statements:

An undecidable statement might be true or might be false; we don't know which.

A self-contradictory statement can be neither true nor false.

  1. What questions can you ask in order to determine whether a person is a Truth-teller or a False-Teller? Talk with Your Partner Talking with others, find at least four questions that will work reliably.
    If Adam were a Truth-teller, how would he answer your questions? Check to make sure that if he were a False-Teller, he'd answer differently.

Theorem: All positive integers are interesting.

Proof:

  1. On that island of Truth-tellers and False-Tellers, you meet Max and Min. Max says "Min and I are both liars!" Which kind of statement is this? Is it self-contradictory? Is it undecidable (it could be either, but there's no way to tell)? Or is it definitely resolvable? If resolvable, who's in what family?