Day 30 — Cases & existence

Day 30 — Cases & existence

Stage III · concept day
Goal: Structure exhaustive case proofs (parity, residue classes mod \(n\)); distinguish constructive and non-constructive existence; use min/max arguments carefully; preview the pigeonhole principle.

Why this matters

Computers branch; proofs branch. Exhaustive cases mirror switch on a finite set of possibilities. Existence claims mirror “there is a witness object”—sometimes you construct it, sometimes you only know it exists. Algorithms often need constructive witnesses (return the index); pure math sometimes does not. Knowing which you proved prevents false confidence in implementability.

Theory

Proof by exhaustive cases

To prove \(R\), find statements \(C_1,\ldots,C_k\) such that \(C_1\vee\cdots\vee C_k\) is true (covers all possibilities), and prove \(C_i \rightarrow R\) for each \(i\).

Checklist:

1. Cases are exhaustive (every possibility falls in some \(C_i\)).
   
2. Cases may overlap (OK if each still implies \(R\)) unless you claim a partition.
   
3. Handle edge cases (zero, empty, \(n=1\)).
   
4. Announce case structure up front.

Classic partitions

Parity: every \(n\in\mathbb{Z}\) is even or odd (not both).

Mod \(m\): every \(n\in\mathbb{Z}\) satisfies exactly one of \(n\equiv 0,1,\ldots,m-1 \pmod{m}\) (Division Algorithm).

Sign: \(x>0\), \(x=0\), or \(x<0\) for real \(x\).

Boolean: \(P\) or \(\neg P\) (classical logic).

Existence proofs

Constructive: exhibit an explicit witness \(c\) with \(P(c)\), or give an algorithm producing one.

Non-constructive: prove \(\exists x\, P(x)\) without naming a concrete \(x\)—often via contradiction (\(\neg\exists \equiv \forall\neg\) leads to falsehood), pigeonhole, or intermediate value-type theorems.

Both are valid classical mathematics. Software extraction usually wants constructive proofs.

Non-example of existence

Proof by example shows \(\exists\) sometimes, but “\(P(n)\) for \(n=1,2,3\)” does not show \(\forall n\, P(n)\).

Max and min arguments

On a finite nonempty set of reals (or integers), a maximum and minimum exist. On infinite sets, not always (\(\mathbb{Z}\) has no max; \((0,1)\) has no min in the set).

Well-ordering principle (for \(\mathbb{N}\)): every nonempty subset of \(\mathbb{N}\) has a least element. Underpins induction (Day 31) and “smallest counterexample” proofs.

Minimal counterexample method: to prove \(\forall n\, P(n)\), assume the set of counterexamples is nonempty, take least \(n_0\), derive contradiction (often using smaller cases that do satisfy \(P\)).

Pigeonhole principle (preview)

Basic. If \(n+1\) pigeons go into \(n\) holes, some hole has at least two pigeons.

Formally. Any function \(f: A \to B\) with \(|A| > |B|\) (finite) is not injective—some fiber has size \(\ge 2\).

Full treatment Day 45; today use only the basic form in simple arguments.

Combining with earlier methods

Cases inside a direct proof; existence of a case that works; contradiction that all cases fail; constructive choice of residue.

Division algorithm (tool)

For \(a\in\mathbb{Z}\) and \(d>0\), there exist unique \(q,r\) with \(a = dq + r\) and \(0\le r < d\). Residue \(r\) is the case label mod \(d\).

Worked examples

Example 1 — \(n(n+1)\) even

Claim. For all \(n\in\mathbb{Z}\), \(n(n+1)\) is even.

Proof. Case 1: \(n\) even, \(n=2k\), product \(2k(2k+1)\) even.
Case 2: \(n\) odd, \(n+1\) even, product even. \(\square\)

Example 2 — Squares mod \(4\)

Claim. For all \(n\in\mathbb{Z}\), \(n^2 \not\equiv 3 \pmod{4}\).

Proof. Cases \(n\equiv 0,1,2,3 \pmod{4}\):
\(0^2\equiv 0\), \(1^2\equiv 1\), \(2^2=4\equiv 0\), \(3^2=9\equiv 1 \pmod{4}\). Never \(3\). \(\square\)

Example 3 — Constructive existence

Claim. \(\exists n\in\mathbb{Z}\, (n^2 = n)\).
Witness \(n=0\) (or \(n=1\)). Constructive. \(\square\)

Example 4 — Non-constructive flavor (IVT awareness)

Any continuous \(f:[0,1]\to\mathbb{R}\) with \(f(0)<0<f(1)\) has a root—existence without a closed formula for the root. (Awareness; not a full analysis proof today.)

Example 5 — Pigeon preview

Among \(13\) people, at least two share a birth month (12 months). Holes = months, pigeons = people.

Example 6 — Cases on gcd style

If \(n\) mod \(3\) is \(0,1,2\), then \(n(n+1)(n+2)\) divisible by \(3\) (three consecutive). Case or note one of three consecutive is \(0 \bmod 3\).

Example 7 — Existence of quotient

For \(a=17\), \(d=5\), \(q=3\), \(r=2\) because \(17=5\cdot 3+2\). Constructive from division.

Example 8 — Max of finite set

\(S=\{3,1,4,1,5\}\) has max \(5\). Proof of existence for finite nonempty: induct on size (Day 31) or scan.

Example 9 — No max

\(\mathbb{N}\) if defined without bound has no maximum (for every \(n\), \(n+1\) larger). Contradiction proof Day 29 style.

Example 10 — Case split on algorithm branch

Correctness: if key present then path A returns index; if absent path B returns \(-1\). Exhaustiveness of present/absent.

Example 11 — Constructive vs not in number theory

Euclid’s proof shows a prime factor of \(N\) exists outside the list—constructive existence of some prime dividing \(N\), not necessarily a formula for the \(k\)-th prime.

Example 12 — Minimal counterexample sketch

Claim \(\forall n\ge 0\, 2^n \ge n\). If false, least \(n_0\ge 0\) with \(2^{n_0}<n_0\). Cannot be \(0\); then \(n_0-1\) ok… (complete with care Day 31 induction is cleaner).

Example 13 — Overlapping cases OK

Prove \(n^2 \ge n\) for \(n\in\mathbb{Z}\): cases \(n\le 0\) and \(n\ge 1\) (overlap \(n=0,1\) fine). Or \(n\le 0\), \(n=1\), \(n\ge 2\).

Example 14 — Existence for sorted check witness

If array not sorted, \(\exists i\, A[i]>A[i+1]\)—constructive by scanning for first inversion.

Exercises

1. Prove by cases: if \(n\in\mathbb{Z}\) then \(n^2+n\) is even.
   
2. Prove: \(n^2 \equiv 0\) or \(1 \pmod{4}\) for all \(n\).
   
3. Prove: among any \(3\) integers, two have difference divisible by \(2\) (parity pigeon).
   
4. Show \(\exists k\in\mathbb{Z}\, (5k+3 = 18)\) or disprove.
   
5. Constructive: find \(x,y\in\mathbb{Z}\) with \(3x+5y=1\) (or explain none).
   
6. Prove by mod \(3\) cases: if \(3\nmid n\) then \(n^2\equiv 1\pmod{3}\).
   
7. Existence: \(\exists\) irrational \(x,y\) with \(x+y\) rational (construct).
   
8. Existence: \(\exists\) irrational \(x,y\) with \(xy\) rational (construct).
   
9. Why does “checked \(n=1..1000\)” not prove a \(\forall n\) claim?
   
10. Pigeon: show among any \(6\) people, at least \(3\) born on same day of week? (Generalized—compute.)
    
11. Prove every integer is \(\equiv 0,1,\) or \(2 \pmod{3}\) using division algorithm statement.
    
12. Max argument: finite nonempty set of integers has a maximum—prove by induction on cardinality (outline OK).
    
13. Show \((0,1)\) has no least element.
    
14. Case proof: \(|x| \ge x\) and \(|x| \ge -x\) for real \(x\) from definition of \(|x|\).
    
15. If \(n\) mod \(2\) and \(m\) mod \(2\) known, case-table the parity of \(n+m\).
    
16. Non-constructive template: write a skeleton proving \(\exists x\, P(x)\) by assuming \(\forall x\, \neg P\) leads to contradiction (fill a toy \(P\)).
    
17. Among \(n+1\) integers, two have difference divisible by \(n\) (pigeon on residues mod \(n\)). Prove.
    
18. Does every nonempty subset of \(\mathbb{Q}^+\) have a least element? Counterexample.
    
19. Prove \(n^3 - n\) divisible by \(3\) by factoring or cases.
    
20. Algorithmic: describe a constructive witness for “unsorted array has an inversion.”
    
21. Prove: for all \(n\), \(n\) or \(n+1\) is even (cases / excluded middle).
    
22. Existence of mid index in binary search bounds \(lo \le hi\): \(mid=\lfloor(lo+hi)/2\rfloor\) is integer with \(lo\le mid\le hi\)—prove.
    
23. Case on empty/nonempty list for “max of list” spec.
    
24. Show that \(x^2 + y^2 = 3\) has no integer solutions by cases mod \(4\) (use Ex. squares mod \(4\)).
    
25. Write a full case proof that the product of two consecutive integers is even.

CS connection

• Branch coverage in testing tries to hit proof cases.
  
• Constructive proofs ≈ programs that return witnesses (Curry–Howard lite awareness).
  
• Default cases in switch must preserve exhaustiveness—same bug as missing proof case.
  
• Pigeonhole in hashing (Day 45–76): collisions must exist when load is high.
  
• Division algorithm underpins % and bucket indices.
  
• Min-counterexample debugging: smallest failing input.

Common pitfalls

Pitfall	What to do instead
Missing a residue class	List \(0,\ldots,m-1\) explicitly
Overlapping cases that disagree	Ensure each case implies the same claim \(R\)
Proof by example for \(\forall\)	Use arbitrary \(n\) or induction
Claiming construction when only non-constructive	Label the method
Max of open/infinite sets	Check finiteness / closedness
Pigeon with wrong hole count	Define holes clearly
Division algorithm with \(d\le 0\)	Require positive divisor

Checkpoint

• Run a parity case proof cold
  
• Run a mod \(4\) or mod \(3\) case proof
  
• Give constructive and non-constructive existence examples
  
• State basic pigeonhole
  
• State well-ordering of \(\mathbb{N}\)
  
• Explain when max/min exist
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — building exhaustive case splits

1. Name the discriminant (parity, \(n \bmod m\), sign, empty/nonempty).
   
2. Prove the discriminant hits every possibility (cite division algorithm or LEM).
   
3. In each case, prove the goal—possibly with different algebra.
   
4. Optional: note overlapping cases if simpler.

Division algorithm (statement to use)

For integers \(a\) and \(d>0\), unique \(q,r\) exist with \(a=dq+r\) and \(0\le r<d\).
Residue \(r\) is the complete set of cases mod \(d\).

Constructive vs non-constructive table

Proof style	Delivers	Example
Exhibit witness	Object + check	\(n=0\) for \(n^2=n\)
Algorithm	Procedure producing object	Linear scan finds max
Contradiction / PHP	Existence only	Collision among \(n+1\) keys
IVT-style	Existence, not closed form	Root of continuous \(f\)

Minimal counterexample pattern

To prove \(\forall n\ge n_0\, P(n)\): assume \(C=\{n\ge n_0:\neg P(n)\}\neq\emptyset\), take \(m=\min C\), derive contradiction from \(P\) on smaller values. This is induction in disguise (Day 31).

More worked examples

Example 15 — Squares mod 3
\(n\equiv 0,1,2 \pmod 3\) ⇒ \(n^2\equiv 0,1,1\pmod 3\) never \(2\).

Example 16 — Existence of inverse mod prime (preview)
For \(p\) prime and \(a\not\equiv 0\), the map \(x\mapsto ax \bmod p\) injective on \(\{0,\ldots,p-1\}\) hence surjective—non-constructive-ish existence of inverse; extended Euclid constructs it.

Example 17 — Max of two
\(\max(x,y)\) exists for reals \(x,y\): cases \(x\ge y\) and \(y>x\).

Example 18 — Guarantee a pair of socks
3 colors, draw 4: PHP cases on colors.

Additional exercises

26. Prove \(n^2\equiv 0\) or \(1\pmod 3\) for all \(n\).
    
27. Prove no integer solutions to \(x^2+y^2=3\) using mod 4.
    
28. Construct irrational \(x,y\) with \(x^y\) rational (classic \(\sqrt{2}^{\sqrt{2}}\) story outline).
    
29. Case proof: \(|xy|=|x||y|\) for real \(x,y\).
    
30. Write a minimal-counterexample sketch for \(2^n \ge n+1\).

Extended practice workshop

Workshop 1 — Parity master sheet

Prove each in \(\le 6\) lines:

1. Sum of two odds is even.
   
2. Product of two odds is odd.
   
3. \(n\) even iff \(n^2\) even (both directions; one may use contrapositive).
   
4. \(n(n+1)(n+2)\) divisible by \(6\) (parity + mod 3).

Workshop 2 — Mod \(m\) master sheet

5. Squares mod \(5\) take values in \(\{0,1,4\}\).
   
6. No integer \(n\) with \(n^2\equiv 2\pmod 4\).
   
7. Among any \(3\) integers, two have difference divisible by \(2\).
   
8. Among any \(5\) integers, two have difference divisible by \(4\) (residues).

Workshop 3 — Existence master sheet

9. Construct \(x\in\mathbb{Q}\setminus\mathbb{Z}\).
   
10. Construct irrationals \(x,y\) with \(x+y\in\mathbb{Q}\).
    
11. Non-constructive: explain PHP existence of collision without naming keys.
    
12. Does every nonempty finite set of reals have a max? Prove or cite.

Workshop 4 — Algorithm-shaped cases

13. Spec: binary search mid index—cases on empty range / singleton / larger.
    
14. Spec: merge two sorted lists—cases on which head smaller.
    
15. Prove \(\lfloor n/2\rfloor + \lceil n/2\rceil = n\) by cases \(n\) even/odd.

Self-score

Workshop	Solved cold	Needed notes
1	/4
2	/4
3	/4
4	/3

Method selection cards

Keep these as flashcards:

• Cases when a finite partition of the domain is natural.
  
• Construct when a witness is easy.
  
• PHP when crowding forces a property.
  
• Contradiction when the claim is “none exist.”
  
• Induction (tomorrow) when a statement is parameterized by \(n\in\mathbb{N}\).

Synthesis

Case analysis and existence are the branching and return of mathematical argument. Exhaustiveness is correctness of the switch; constructivity is whether the proof yields a program. Together with direct and indirect proof, you now have a complete “method menu” for Stage III claims that are not inductive.

Building a case proof that survives review

1. Name the discriminant (parity, residue mod \(m\), sign, empty/nonempty, key present/absent).
   
2. Cite why it covers all possibilities (division algorithm, LEM, definition).
   
3. Prove the same goal \(R\) in each branch—different algebra is fine; different conclusions are not.
   
4. Call out edges (\(n=0\), \(m=1\), empty list) even if they fall into a general case.

More worked examples

Example 19 — Product of two consecutive integers is even.
Cases: \(n\) even ⇒ \(n(n+1)\) even; \(n\) odd ⇒ \(n+1\) even ⇒ product even. Exhaustive by parity.

Example 20 — Squares mod \(5\).
Residues \(0,1,2,3,4\): squares \(0,1,4,4,1\). So \(n^2\not\equiv 2,3\pmod 5\). Useful for “no integer solution” arguments later.

Example 21 — Constructive irrationals summing to rational.
\(\sqrt{2}\) and \(1-\sqrt{2}\) are both irrational (if \(1-\sqrt{2}\) were rational then \(\sqrt{2}\) would be), and sum to \(1\in\mathbb{Q}\). Witness pair exhibited.

Example 22 — Non-constructive collision.
Any function \(\{1,\ldots,13\}\to\{1,\ldots,12\}\) is non-injective (PHP). Existence of a colliding pair without naming which keys collide until you scan.

Example 23 — Minimal counterexample vs induction.
To prove \(\forall n\ge 0\, P(n)\), taking the least counterexample and deriving a contradiction is induction in disguise. Prefer explicit induction write-ups once Day 31’s template is fluent; keep minimal-counterexample as a discovery tool.

Extra exercises (synthesis)

31. Prove by mod \(4\) cases that \(n^2+m^2\not\equiv 3\pmod 4\) for integers \(n,m\)—hence \(x^2+y^2=4k+3\) has no integer solutions.
    
32. Among any \(5\) integers, show two have difference divisible by \(4\) (pigeon on residues mod \(4\)).
    
33. Construct irrational \(x,y\) with \(xy\) rational and \(x\neq y\).
    
34. Prove \(\lfloor x\rfloor \le x < \lfloor x\rfloor+1\) for real \(x\) from the definition of floor (existence of the integer is the division/completeness tool you may cite).
    
35. Write a case-structured correctness argument for: “if list length is \(0\) return sentinel; else return max”—exhaust empty vs nonempty.
    
36. Is “checked all \(n\le 10^6\)” a case proof for a \(\forall n\in\mathbb{N}\) claim? Explain.

Existence hygiene checklist

Question	Why it matters
Did I exhibit a witness?	Constructive
Did I only show nonemptiness?	May be non-constructive
Is the witness in the claimed domain?	Type/universe bugs
Did I prove \(\forall\) by three examples?	Invalid

Cases without exhaustiveness and existence without domain checks are the two most common silent failures in student proofs and in design docs.

Tomorrow

Day 31 — Weak induction. Principle, well-ordering link, sums/divisibility/inequalities, loop invariant preview, common failures (horses), template.