Proof by Cases

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Problem Set

Problem set 6, on proof by contradiction, is now available.

The complete-by date is a week from Monday, to provide a little bit slower pace for next week’s rejuvenation day (which is Wednesday, so we won’t have class that day).

See the handout for more details.

Proof by Cases

Based on section 3.4 of the textbook, and this discussion of proofs with cases.

Example 1

(This is the example from the Canvas discussion.)

Suppose f(x) is defined by

Prove that f(x) ≥ 0 for all real numbers x.

We wrote the proof in LaTeX, mainly as an example of what a proof by cases might look like when fully written out. The LaTeX source file and PDF output are available through Canvas.

Example 2

Motivation: is it possible for an irrational number raised to an irrational power to be rational (for example, might π^√2 be rational?)

Since the set of irrational numbers isn’t closed under any other arithmetic operation, it seems unlikely that it’s closed under this sort of exponentiation. So we conjectured…

Conjecture: For some irrational numbers x and y, x^y is rational.

As an outline of the proof, let’s start by considering the square root of 2 raised to the square root of 2 power. Call the result z:

Now we have no idea whether z is rational or not, although a quick check on a calculator shows no sign of a repeating pattern in the first 9 digits or so, so maybe it’s irrational. But we don’t need to know, because we can treat each possibility as a separate case in our proof:

Case 1. z is rational, in which case we’re done! We raised an irrational number, √2, to an irrational power, also √2, and got a rational result. In terms of our conjecture, x = y = √2.

Case 2. z is irrational. In this case, think about what happens if we raise z to the √2 power:

Once again, we raised an irrational number, z, to an irrational power, √2, and got a rational result.

So in both cases, we found that it is possible to raise an irrational number to an irrational power and get a rational result.

(Thanks to Prof. Leary in the math department for showing me this problem and its proof.)

This demonstrates another situation in which you might use cases in a proof: when one case (or several cases) leaves you with nothing left to prove, and another (or others) leave you with enough extra information to finish the proof.

Next

Modular congruence in more depth, and something called the division algorithm.

The main value in studying this material is that it establishes a lot of new properties of modular arithmetic, something that isn’t very visible, but is nonetheless surprisingly common, in the real world. (And, of course, this material provides another context to practice mathematical thinking and proofs in.) For example, the “checksum” for product bar codes, introduced in our March 5 class:

Please read section 3.5 in the textbook.

Please also participate in this discussion of modular congruence and its properties.

Next Lecture