Problem Set
About proof by contradiction and cases. See handout for details.
Questions?
Hints about proving the corollary in Problem 4 from the current problem set?
The corollary is that for all real numbers x and y, if x < y then there exists a natural number n such that x < x + 1/n < y.
The key insight is to realize that because x < y, y - x > 0, and so the proposition from earlier in Problem 4 applies to it. In particular, there exists a natural number n such that 0 < 1/n < y - x. Then add x to each part of the inequality.
The Division Algorithm
From section 3.5
Magically Predicting Bar Codes
Give me the first 11 digits of a UPC bar code and I will predict the last digit.
The trick is that the digits in a bar code have a pattern. Namely, if the digits are identified from left to right as x1, x2, x3, and so forth up to x12, then
3x1 + x2 + 3x3 + x4 + 3x5 + ... + 3x11 + x12 ≡ 0 (mod 10)
This gives an equation that can be solved for any single digit that is missing.
(The real reason for this rule is to allow errors due to mistyped human entry or mis-scanned automatic reading to be detected, namely if the digits entered or read don’t satisfy the above equation. Schemes such as this are called “checksums.”)
The Basic Claim
Try the bar code “magic” for yourselves.
Key Points
You can save yourself work by mentally keeping track of the “r” value from the Division Algorithm for sums of digits, products, etc. as you calculate, rather than keeping full sums, products, etc. That this is equivalent to keeping full sums etc., and then finding r at the end follows from theorems proved in the reading.
Congruence and Proof by Cases
Also from section 3.5.
Example
A simplification of a conjecture from the discussion of bar codes: is it true that for all k ≢ 0 (mod 4), 3k ≢ k (mod 4)?
Analyze the claim by cases (if the claim is true these cases will be the nucleus of a proof by cases, if the claim is false these cases provide a systematic way to find a counter-example)
- k ≡ 1 (mod 4): 3k ≡ 3×1 (mod 4) ≡ 3 (mod 4)
- k ≡ 2 (mod 4): 3k ≡ 6 (mod 4) ≡ 2 (mod 4). So here’s a counter-example to the conjecture.
- k ≡ 3 (mod 4) 3k ≡ 9 (mod 4) ≡ 1 (mod 4).
Next
Introduction to proof by induction.
Read section 4.1.