Day 29 — Contrapositive & contradiction

Day 29 — Contrapositive & contradiction

Stage III · concept day
Goal: Choose when to use contrapositive vs contradiction vs direct proof; prove claims via \(\neg Q \rightarrow \neg P\); run classic contradiction proofs (\(\sqrt{2}\) irrational; infinitude of primes recall); prove uniqueness by contradiction.

Why this matters

Some hypotheses are messy while their negations are clean; some conclusions are “never happens” claims. Contrapositive and contradiction are not decorations—they are the standard tools for irrationality, impossibility, uniqueness, and many CS “cannot occur” safety arguments (deadlock freedom sketches, “no two primaries,” collision impossibility under assumptions).

Theory

Contrapositive proof

To prove \(P \rightarrow Q\), prove the equivalent \(\neg Q \rightarrow \neg P\) (Day 25).

Template:

1. Assume \(\neg Q\).
   
2. Derive \(\neg P\) (often directly).
   
3. Conclude \(P \rightarrow Q\) by contrapositive equivalence.

When it shines: \(Q\) is “\(n\) is even/odd/composite/…” and \(\neg Q\) gives a usable algebraic form; or \(P\) is a compound “and” that is hard to start from.

Proof by contradiction

To prove \(R\), assume \(\neg R\) and derive a contradiction (false statement: \(S \wedge \neg S\), or \(0=1\), or violation of a known theorem).

Template:

1. Assume \(\neg R\) for contradiction.
   
2. Reason to some \(S\) and \(\neg S\) (or absurdity).
   
3. Reject \(\neg R\); conclude \(R\).

Special case for \(P\rightarrow Q\): assume \(P \wedge \neg Q\), derive contradiction. Equivalent to showing \((P \wedge \neg Q)\) is impossible.

Contrapositive vs contradiction vs direct

Method	Assume	Goal shape
Direct	\(P\)	Derive \(Q\)
Contrapositive	\(\neg Q\)	Derive \(\neg P\)
Contradiction	\(\neg R\) (or \(P\wedge\neg Q\))	Derive falsehood

Contradiction is more general (and easier to abuse with fuzzy “absurd”). Prefer direct or contrapositive when they fit; use contradiction for impossibility/uniqueness/global claims.

Classic: \(\sqrt{2}\) is irrational

Claim. \(\sqrt{2} \notin \mathbb{Q}\).

Proof (contradiction). Suppose \(\sqrt{2} = p/q\) with \(p,q\in\mathbb{Z}\), \(q\neq 0\), fraction in lowest terms (\(\gcd(p,q)=1\)), \(p>0\), \(q>0\).
Then \(p^2 = 2 q^2\). So \(p^2\) is even ⇒ \(p\) even (Day 28 converse parity / cases). Write \(p=2k\).
\((2k)^2 = 2q^2 \Rightarrow 4k^2 = 2q^2 \Rightarrow q^2 = 2k^2\) ⇒ \(q\) even.
Then \(2\mid p\) and \(2\mid q\), contradicting \(\gcd(p,q)=1\).
Hence \(\sqrt{2}\) is irrational. \(\square\)

Classic recall: infinitude of primes

Claim. There are infinitely many primes.

Proof sketch (Euclid, contradiction). Suppose only finitely many primes \(p_1,\ldots,p_k\). Let \(N = p_1\cdots p_k + 1\). Then \(N > 1\) has a prime factor \(q\). But \(q\) cannot be any \(p_i\) (each leaves remainder \(1\) when dividing \(N\)). Contradiction. \(\square\)

Uniqueness by contradiction

To prove at most one object satisfies \(P\): assume \(P(a)\), \(P(b)\), and \(a\neq b\), derive contradiction—or better, derive \(a=b\) from \(P(a)\wedge P(b)\) (sometimes direct). Unique existence = existence + uniqueness.

Example pattern. Uniqueness of identity: if \(e,e'\) both identities, \(e = e\cdot e' = e'\).

Negations you need fluently

Claim	Negation
\(n\) even	\(n\) odd (on \(\mathbb{Z}\))
\(a\mid b\)	\(\forall m\, b \neq am\)
\(x\in\mathbb{Q}\)	\(x\) irrational
\(\forall x\, P(x)\)	\(\exists x\, \neg P\)
\(P\rightarrow Q\)	\(P \wedge \neg Q\)

Indirect proof hygiene

• State “assume for contradiction …” explicitly.
  
• Mark the contradictory pair.
  
• Do not assume extra unjustified structure (e.g. “smallest counterexample” is well-ordering/induction territory—Day 31).
  
• Lowest terms / well-defined gcd are part of the \(\sqrt{2}\) setup—mention them.

Proof of \(P \rightarrow Q\) by contradiction vs contrapositive

Assuming \(P\wedge \neg Q\) and deriving \(\neg P\) is essentially contrapositive plus unused \(P\) (or deriving false from \(P\)). Both valid; contrapositive is cleaner if you never need \(P\) in the branch.

Worked examples

Example 1 — Contrapositive parity

Claim. If \(n^2\) is even, then \(n\) is even.

Proof. Contrapositive: if \(n\) odd, then \(n^2\) odd (Day 28). \(\square\)

Example 2 — Contrapositive divides

Claim. If \(n\) is not divisible by \(3\), then \(n^2\) is not divisible by \(3\).
Contrapositive: if \(3\mid n^2\) then \(3\mid n\) (needs Euclid’s lemma / prime property—state as cited fact if not proved).

Example 3 — Contradiction: no largest integer

Claim. There is no largest integer.

Proof. Suppose \(N\) is largest. Then \(N+1 > N\) and \(N+1\in\mathbb{Z}\), contradiction. \(\square\)

Example 4 — \(\sqrt{2}\) details

Emphasize: even square ⇒ even base uses Example 1. gcd step needs that \(2\) is prime or that common factor \(2\) contradicts lowest terms.

Example 5 — Uniqueness of zero additive

If \(z+a=a\) for all \(a\), and \(0\) is the usual zero, show \(z=0\): set \(a=0\), \(z+0=0\) ⇒ \(z=0\). Or from two zeros: \(z = z+0' = 0'\).

Example 6 — Impossible config

Claim. There are not two distinct primary leaders if the system invariant says \(\exists! p\, Primary(p)\).

Proof. If \(Primary(p_1)\), \(Primary(p_2)\), \(p_1\neq p_2\), contradicts uniqueness clause of \(\exists!\). \(\square\)

Example 7 — Direct vs contrapositive choice

Claim: if \(n\) is multiple of \(6\), then \(n\) even. Direct is easy (\(n=6k=2(3k)\)). Contrapositive works but is longer. Prefer direct.

Example 8 — Contradiction for \(\forall\) denial

To show \(\neg \forall x\, P(x)\), exhibit counterexample—this is direct proof of \(\exists x\, \neg P\), not heavy contradiction. Prefer constructive counterexample when available.

Example 9 — Irrationality style for \(\sqrt{3}\) (outline)

Same as \(\sqrt{2}\) with \(3\): \(p^2=3q^2\) ⇒ \(3\mid p^2\) ⇒ \(3\mid p\), etc., need prime \(3\) divides product ⇒ divides factor.

Example 10 — Empty of solutions

Claim. No \(n\in\mathbb{Z}\) with \(n^2 = 2\).
If \(n^2=2\), then \(|n|\ge 2\) ⇒ \(n^2\ge 4\), or \(|n|\le 1\) ⇒ \(n^2\le 1\); contradiction. (Integer case—different from irrationality of \(\sqrt{2}\).)

Example 11 — Contrapositive with implication hypothesis

Prove: if \(n^2 + n\) is odd, then \(n\) is even? Wait check: \(n(n+1)\) always even. Odd never happens—vacuous. Bad claim. Better: if \(n^2\) odd then \(n\) odd (contrapositive of even square).

Example 12 — Infinite primes: construct \(N\)

For primes \(2,3,5\), \(N=31\) prime; for larger lists \(N\) may be composite but still has a new prime factor—that is enough.

Example 13 — Uniqueness of max in strict order

In a strictly ordered set, at most one maximum: if \(m_1,m_2\) both maxima, \(m_1\le m_2\) and \(m_2\le m_1\) ⇒ equal in total order with antisymmetry.

Example 14 — Proof that \(\sqrt{4}\) rational does not “break” method

\(\sqrt{4}=2=2/1\); the step “\(p^2=4q^2\) ⇒ \(p\) even” does not force infinite descent the same way because \(4\) is not square-free—method depends on prime factorization structure.

Exercises

1. Prove by contrapositive: if \(n^2\) is odd, then \(n\) is odd.
   
2. Prove by contrapositive: if \(n\) is even, then \(n+1\) is odd (almost definitional).
   
3. Prove by contradiction: there is no smallest positive real number.
   
4. Write a full \(\sqrt{2}\) irrational proof from memory.
   
5. Outline \(\sqrt{3}\) irrational; identify the prime lemma you need.
   
6. Prove: if \(a\) is rational and \(b\) irrational, then \(a+b\) is irrational (contradiction).
   
7. Prove: if \(a\neq 0\) rational and \(b\) irrational, then \(ab\) irrational.
   
8. Disprove: product of two irrationals is irrational (counterexample).
   
9. Prove uniqueness: at most one identity element in a structure with axiom \(e\cdot x=x=x\cdot e\).
   
10. Prove by contradiction: if \(n^2\) is divisible by \(2\), wait—use contrapositive preferred; write both styles for “even square ⇒ even \(n\).”
    
11. Euclid’s proof: explain why \(N\) is not divisible by any listed prime.
    
12. Prove: \(\log_2 3\) is irrational (hint: \(2^a=3^b\) forces parity/prime contradiction).
    
13. Show there is no largest even integer.
    
14. Prove: if \(3\nmid n\), then \(3\nmid n^2\)—state needed lemma or use cases mod \(3\) (Day 30).
    
15. Uniqueness of solution to \(2x=6\) in \(\mathbb{R}\) (direct or contradiction on two solutions).
    
16. Prove by contradiction that \(\sqrt{2}+\sqrt{8}\) is… actually rational? \(\sqrt{8}=2\sqrt{2}\), sum \(3\sqrt{2}\) irrational. Prove.
    
17. Method choice: for “if \(n\) ends with digit \(5\) then \(5\mid n\),” is direct or contrapositive better?
    
18. Prove: not both \(n\) and \(n+1\) even.
    
19. Formalize “cannot have two distinct masters in a single-master lock” as uniqueness.
    
20. Find the flaw: “Assume \(\sqrt{2}=p/q\). Then … something false about decimals … contradiction.” (Vague contradiction.)
    
21. Prove: if \(n\mid 7\) then \(n\in\{\pm1,\pm7\}\) using size/contradiction on factorization.
    
22. Show \(\nexists n\in\mathbb{Z}\, (2n=1)\).
    
23. Prove contrapositive form of: if a function \(f\) is injective then … (preview) wait: if \(f(a)=f(b)\) is false whenever \(a\neq b\)—write contrapositive of injectivity definition.
    
24. Infinite primes: show that from any finite list you can produce an integer with a prime factor outside the list.
    
25. Write \(\neg(P\rightarrow Q)\) and use it in a contradiction proof skeleton for an implication claim.

CS connection

• Safety properties: “bad state never reachable” often proved by contradiction (assume reachable, violate invariant).
  
• Uniqueness of leaders, mutex holders, primary keys.
  
• Impossibility results (FLP, CAP awareness later) are contradiction/model arguments at systems scale.
  
• Hash collision: under pigeonhole (Day 45), contradiction if too many keys without collision assumed.
  
• Type soundness sketches: assume stuck state, contradict progress/preservation.
  
• Prefer constructive counterexamples for “not always” bugs—contradiction not required.

Common pitfalls

Pitfall	What to do instead
Proving the converse by accident	Write \(\neg Q\rightarrow\neg P\) explicitly
“Contradiction” without naming it	Exhibit \(S\) and \(\neg S\)
Assuming lowest terms silently	State gcd \(=1\)
Using contradiction for easy direct claims	Prefer direct
Circular: using irrationality of \(\sqrt{2}\) to prove itself	Only prior facts
Infinite descent without justification	Formalize or use fixed \(\sqrt{2}\) pattern
Negating \(P\rightarrow Q\) as \(\neg P\rightarrow\neg Q\)	Negation is \(P\wedge\neg Q\)

Checkpoint

• State contrapositive template
  
• State contradiction template
  
• Prove even-square converse via contrapositive
  
• Reproduce \(\sqrt{2}\) irrational proof
  
• Sketch infinitude of primes
  
• Prove one uniqueness claim
  
• Choose methods for three sample claims
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — choosing the method

Claim shape	Prefer	Why
\(P\rightarrow Q\) with messy \(P\), clean \(\neg Q\)	Contrapositive	Start from \(\neg Q\)
“There is no …” / impossibility	Contradiction	Assume exists
Uniqueness	Assume two, derive equal (often direct) or contradict \(\neq\)
Algebraic identity / expansion	Direct
\(\sqrt{2}\notin\mathbb{Q}\)	Contradiction + lowest terms	Classic

Structure of the \(\sqrt{2}\) proof (checklist)

1. Assume \(\sqrt{2}=p/q\) in lowest terms, \(q>0\).
   
2. \(p^2=2q^2\).
   
3. \(p\) even ⇒ \(p=2k\).
   
4. \(q^2=2k^2\) ⇒ \(q\) even.
   
5. Common factor \(2\) contradicts lowest terms.
   
6. Discharge assumption.

Missing step 3’s lemma “even square ⇒ even root” is a common hole—prove it by contrapositive first.

Infinite primes — what is constructive?

Euclid produces, from any finite list, an integer \(N\) that has some prime factor outside the list. You may need to factor \(N\) to name the prime—existence is constructive relative to factorization.

More worked examples

Example 15 — Contrapositive divisibility
If \(n^2\) not divisible by \(3\), then \(n\) not divisible by \(3\) is the converse direction of the useful lemma; useful form: if \(3\mid n^2\) then \(3\mid n\) (Euclid’s lemma for prime \(3\)).

Example 16 — No rational root of \(x^2-2=0\)
Same as irrationality of \(\sqrt{2}\).

Example 17 — Contradiction for simultaneous
Cannot have \(n\) even and \(n=2k+1\) for integers—definitions contradict.

Example 18 — Uniqueness of empty set
If \(E_1,E_2\) both empty, then \(E_1\subseteq E_2\subseteq E_1\) so equal.

Additional exercises

26. Prove \(\sqrt[3]{2}\) irrational (outline with prime \(2\)).
    
27. Prove: if \(a\) rational, \(b\) irrational, \(a\neq 0\), then \(a/b\) irrational.
    
28. Method choice table: fill for five claims of your choice.
    
29. Find the gap in a fake \(\sqrt{2}\) proof that never uses lowest terms.
    
30. Prove uniqueness of additive inverse in \(\mathbb{Z}\).

Extended practice workshop

Contrapositive translations

Rewrite each as a contrapositive claim, then prove or outline:

1. If \(n^2\) even then \(n\) even.
   
2. If \(n\) ends with digit \(0\) then \(10\mid n\) (direct may be easier—note choice).
   
3. If a product \(ab\) is odd then \(a\) and \(b\) both odd.
   
4. If \(f(a)=f(b)\) always implies \(a=b\), then … (injectivity forms).

Contradiction drills

5. Full \(\sqrt{2}\) write-up from blank paper.
   
6. \(\sqrt{3}\) outline with prime lemma named.
   
7. No largest prime (Euclid).
   
8. No rational solution to \(x^2=2\) in \(\mathbb{Q}\).
   
9. If \(a\in\mathbb{Q}\), \(b\notin\mathbb{Q}\), then \(a+b\notin\mathbb{Q}\).
   
10. If \(a\in\mathbb{Q}\setminus\{0\}\), \(b\notin\mathbb{Q}\), then \(ab\notin\mathbb{Q}\).

Uniqueness drills

11. Unique solution to \(3x+1=7\) in \(\mathbb{R}\).
    
12. Unique empty set.
    
13. Unique identity in a monoid (axiomatic).
    
14. At most one maximum in a poset (preview).

Method selection (one line each)

15–20. For six claims of your invention, pick direct/contrapositive/contradiction and justify.

Proof cleanliness rubric

Criterion	0	1	2
Assumption stated
Contradiction pair explicit
Lemmas cited
Quantifiers clear

Synthesis

Indirect proof is not a second-class citizen—it is often the only clean path for impossibility, uniqueness, and “if messy then clean” implications. The skill is method choice plus hygiene: name the assumption, name the contradiction, cite lemmas, and never smuggle the goal into the premises.

Decision flowchart (use until automatic)

1. Is the claim “there is no …” / “impossible” / “at most one”? → Contradiction (or direct uniqueness \(a=b\)).
   
2. Is it \(P\rightarrow Q\) where \(\neg Q\) is algebraically nicer than \(P\)? → Contrapositive.
   
3. Is \(P\) already a usable hypothesis (even, divides, …)? → Direct.
   
4. If stuck, try contradiction on \(P\wedge\neg Q\); if you derive \(\neg P\) without using \(P\), rewrite as contrapositive.

More worked examples

Example 19 — Rational + irrational.
Claim. If \(a\in\mathbb{Q}\) and \(b\notin\mathbb{Q}\), then \(a+b\notin\mathbb{Q}\).
Proof. Suppose \(a+b=r\in\mathbb{Q}\). Then \(b=r-a\in\mathbb{Q}\), contradiction. \(\square\)

Example 20 — Product of nonzero rational and irrational.
Claim. If \(a\in\mathbb{Q}\setminus\{0\}\) and \(b\notin\mathbb{Q}\), then \(ab\notin\mathbb{Q}\).
Proof. If \(ab=r\in\mathbb{Q}\), then \(b=r/a\in\mathbb{Q}\) (since \(a\neq 0\)), contradiction. \(\square\)

Example 21 — Contrapositive beats direct.
Claim. If \(n^2\) is even then \(n\) is even.
Direct: “\(n^2=2k\) ⇒ \(n=\sqrt{2k}\)” is not integer reasoning. Contrapositive uses only odd \(\times\) odd = odd.

Example 22 — Uniqueness of multiplicative identity.
If \(e,e'\) both satisfy \(ex=x=xe\) and \(e'x=x=xe'\) for all \(x\), then \(e=ee'=e'\). No contradiction needed—direct equality chain.

Example 23 — Bad contradiction.
“Assume \(\sqrt{2}\) rational. Rationals have repeating decimals. \(\sqrt{2}\)’s decimal does not repeat. Contradiction.”
Bug: “does not repeat” is not established independently; the argument is circular or incomplete. Prefer the integer lowest-terms proof.

Extra exercises (synthesis)

31. Prove: if \(a\) rational and \(a+b\) rational, then \(b\) rational (contrapositive or direct rearrangement).
    
32. Prove: there is no smallest positive rational (contradiction: half of it).
    
33. Write both a contrapositive and a contradiction proof of “even square ⇒ even \(n\)”; compare length.
    
34. Prove uniqueness of the additive inverse of \(a\) in \(\mathbb{Z}\).
    
35. Outline why \(\sqrt{p}\) is irrational for prime \(p\) (same skeleton as \(\sqrt{2}\)).
    
36. Method choice only (no full proof): (a) sum of first \(n\) integers formula; (b) no largest prime; (c) if \(4\mid n^2\) then \(2\mid n\) (careful—true?); (d) \(n\) even ⇒ \(n^2\) even.

Clean write-up micro-rubric (apply to Ex. 31–35)

• Assumption line present?
  
• Contradiction pair named (\(S\) and \(\neg S\))?
  
• Lowest terms / gcd stated when needed?
  
• Quantifiers on \(n,a,b\) explicit?

Indirect proofs fail most often on hygiene, not on cleverness. Slow is fine; vague is not.

Tomorrow

Day 30 — Cases & existence. Exhaustive cases (parity, mod \(n\)); constructive vs non-constructive existence; max/min arguments; pigeon preview.