Page 1: Proof by Contradiction

Unit 5, Lab 4, Page 1

Averaging just under 50 minutes, Lab 5: Unsolvable and Undecidable Problems, was the lab to which teachers devoted the least amount of time. It was also found to be the least successful, with only 20% reporting very successful and the majority (71%) noting the lab was neither unsuccessful or very successful.
- Teachers reported supplementing with videos from YouTube

PG: Language inconsistency! Edit to clean up typos. I /really/ like the ideas here but the feedback has not been good.

BH: But change the “at least four” problem to make it clear that you’re only allowed to ask one question.

MF: I want review this page and cut down on the switching back and forth among colored boxes.

“Zoey and I are from the same family.” is a poor choice for motivating proof by contradiction because it doesn’t require it. –MF, 9/1/19

Also, this lab overdoes decidability and solvability which has been simplified in the standards now (and is fully covered in 5.1.6 Heuristic Solutions. When we revise, we should distill down to the core of what we want to teach. –MF, 9/1/19

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.

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, Diego and Zoey. Diego says, “Zoey and I are from the same family.”
1. Can you say for sure which family Zoey is from? If so, which family?
2. Can you say for sure which family Diego is from? If so, which family?

Betsy, Gamal, and Alphie are considering the problem above.

Betsy: I’m pretty sure Zoey is a Truth-teller, but I don’t know how to prove it.

A proof by contradiction is a two-step proof that a statement is false, which is done by

assuming the statement is true
based on that assumption, proving something known to be false (that is, showing the assumption 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 Zoey is a False-teller.

Betsy: Okay. So if Diego is a Truth-teller, then what he said is true, and they are from the same family, the Truth-tellers. But we assumed that Zoey is a False-teller, so they’re actually from different families, and so Diego can’t be a Truth-teller.

Alphie: So, Diego has to be a False-teller.

Gamal: But that won’t work either! If Diego 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 Diego can’t be a False-teller either.

Betsy: No matter what family Diego is from, our assumption that Zoey is a False-teller led us to a contradiction. Zoey can’t be a False-teller, so has to be a Truth-teller. We proved it.

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?
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?!?

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. So 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.

Provably True: For example in this problem, “Zoey is a Truth-teller.”
Provably False: For example, “Zoey is a False-teller.”
Undecidable: For example, “Diego is a Truth-teller.”
Self-Contradictory: Such as “This statement is false.”

What questions can you ask in order to determine whether a person is a Truth-teller or a False-Teller? Talking with others, find at least four questions that will work reliably.

If Diego 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:

In order to prove this by contradiction, assume that not all positive integers are interesting.
Since positive integers don’t go down forever, there must be a smallest non-interesting positive integer.
But isn’t that an interesting thing about that number? ;)

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?