Day 12 — Strong Induction, Fallacies & Gate III

Day 12 — Strong Induction, Fallacies & Gate III

Day 32 — Strong induction & invariants

Stage III · concept day
Goal: Use strong induction; prove Fibonacci-style recurrences; solve postage stamp / Frobenius-lite problems; perform structural induction on lists and trees; apply the full loop-invariant pattern (init / maintain / terminate); sketch algorithm correctness without coding labs.

Why this matters

Weak induction assumes only the previous integer; many recurrences need all smaller values (Fibonacci, divide-and-conquer sizes, prime factor existence). Programs induct on structure (list tail, tree children) and on time (loop iterations). Loop invariants are how you prove while loops correct—the industry-adjacent face of induction.

Theory

Strong induction principle

Let \(P(n)\) be a predicate for \(n \ge n_0\).

If:

1. Base: \(P(n_0)\) (sometimes several bases \(P(n_0),\ldots,P(n_0+r)\)), and
   
2. Strong step: for every \(m \ge n_0\),
   \(\bigl(\forall j\in\{n_0,\ldots,m\}\, P(j)\bigr) \rightarrow P(m+1)\)
   (equivalently: assume all \(P(j)\) for \(n_0 \le j \le m\), prove \(P(m+1)\)),

then \(\forall n \ge n_0\, P(n)\).

Equivalent to weak induction in strength for \(\mathbb{N}\) (each can simulate the other), but form differs: you may use \(P(m), P(m-1), \ldots\) in the step.

When to use strong

• Recurrences \(a_{n} = a_{n-1} + a_{n-2}\).
  
• “Every \(n \ge 2\) has a prime factor.”
  
• Postage: amounts from some point onward using stamp denominations.
  
• Algorithms that reduce \(n\) to a strictly smaller instance not necessarily \(n-1\) (e.g. \(n//2\)).

Fibonacci example setup

\(F_0 = 0\), \(F_1 = 1\), \(F_{n} = F_{n-1}+F_{n-2}\) for \(n\ge 2\).
(Or \(F_1=F_2=1\)—fix your convention.)

Postage stamp / Frobenius lite

With stamps of sizes \(a,b\) coprime, all sufficiently large integers are postage-representable (Frobenius number \(ab-a-b\)). Course level: fix denominations (e.g. \(4\) and \(7\), or \(3\) and \(5\)) and prove by strong induction that all \(n \ge N\) work, with explicit bases.

Structural induction

Define a set of structures inductively, then prove \(\forall\) structures \(P\) by:

1. Base structures (empty list, nil tree).
   
2. Constructor step: if \(P\) holds for parts, then \(P\) holds for the compound.

Lists over \(X\): \(\mathrm{nil}\) | \(\mathrm{cons}(h,t)\).
Binary trees: \(\mathrm{Leaf}\) | \(\mathrm{Node}(L,v,R)\).

Examples: length laws, \(\mathrm{height}\), size \(= 1 + \mathrm{size}(L)+\mathrm{size}(R)\), inorder traversal length.

Loop invariants (full pattern)

For a loop with guard \(G\) and body \(B\):

1. Initialization: \(I\) true before the loop.
   
2. Maintenance: \(\{I \wedge G\}\; B\; \{I\}\) (if \(I\) and \(G\) hold, after \(B\), \(I\) holds).
   
3. Termination: loop ends (e.g. variant decreases); then \(I \wedge \neg G\) holds.
   
4. Use: \(I \wedge \neg G\) implies the desired postcondition.

Induction: \(P(t) =\) “after \(t\) successful iterations, \(I\) holds and any variant bounds.”

Algorithm correctness sketches (no labs)

• Linear search: invariant “\(x\) not in \(a[0..i)\)”; at end either found or not in array.
  
• Binary search (sorted): invariant “if \(x\) present, it lies in \(a[lo..hi]\)”; width decreases.
  
• Euclidean algorithm: invariant \(\gcd(a,b)=\gcd(a_0,b_0)\); \(b\) decreases.

State invariants in math; do not require running code.

Strong induction write-up tips

• State “assume \(P(j)\) for all \(j\) with \(n_0 \le j \le m\)” (or \(< n\) when proving \(P(n)\)).
  
• Identify which smaller instances you call.
  
• Provide enough bases for the recurrence depth.

Worked examples

Example 1 — Fibonacci closed identity

\(P(n): F_{n+1} F_{n-1} - F_n^2 = (-1)^n\) (Cassini) for \(n\ge 1\) with standard \(F\)—optional challenge. Simpler:

Claim. \(F_1 + \cdots + F_n = F_{n+2} - 1\) (with \(F_1=1,F_2=1\)).
Weak induction works; uses \(F_{n+1}=F_n+F_{n-1}\) carefully—standard textbook induction.

Example 2 — Strong: every \(n\ge 2\) has a prime factor

Base \(n=2\): prime.
Assume every \(j\) with \(2\le j < n\) has a prime factor. If \(n\) prime, done. If \(n=ab\) with \(1<a,b<n\), then \(a\) has a prime factor, which divides \(n\). \(\square\)

Example 3 — Postage \(3\) and \(5\)

Claim. Every \(n \ge 8\) is \(3x+5y\) for some \(x,y\ge 0\).
Bases: \(8=1\cdot 3+1\cdot 5\), \(9=3\cdot 3\), \(10=2\cdot 5\).
Strong step: for \(n>10\), \(n-3 \ge 8\) is representable by IH; add one \(3\)-stamp. \(\square\)
(Bases of three consecutive needed because step subtracts \(3\).)

Example 4 — Weak fails form for \(F_n\) property needing two

Any identity relating \(F_{n+1}\) to \(F_n\) and \(F_{n-1}\) needs two previous—strong or double base weak with IH on \(k\) and lemma.

Example 5 — List length

\(\mathrm{len}(\mathrm{nil})=0\), \(\mathrm{len}(\mathrm{cons}(h,t))=1+\mathrm{len}(t)\).
Claim. \(\mathrm{len}(xs)+\mathrm{len}(ys)=\mathrm{len}(xs{+\!\!+}ys)\) (concatenate).
Structural induction on \(xs\): nil base; cons step.

Example 6 — Tree size

\(size(\mathrm{Leaf})=1\), \(size(\mathrm{Node}(L,v,R))=1+size(L)+size(R)\).
Claim. \(size(T) \ge 1\). Structural induction.

Example 7 — Tree height

\(height(\mathrm{Leaf})=0\), \(height(\mathrm{Node})=1+\max(height(L),height(R))\).
Claim. \(size(T) \le 2^{height(T)+1}-1\) for binary trees. Strong/structural on \(T\).

Example 8 — Loop invariant: sum

s = 0; i = 1
while i <= n:
    s = s + i
    i = i + 1

Invariant \(I\): \(s = \sum_{j=1}^{i-1} j\) and \(1 \le i \le n+1\).
Init: \(s=0\), \(i=1\). Maintain: add \(i\), increment. Exit: \(i=n+1\), \(s=\sum_{j=1}^n j\).

Example 9 — Linear search invariant

i from \(0\); \(I\): \(\forall j < i,\; a[j] \neq x\). If exit with \(i=n\), \(x\) not present; if find, return index.

Example 10 — Binary search invariant (sketch)

Sorted array; \(I\): \(x\) in \(a[0..n)\) implies \(x\) in \(a[lo..hi]\) (closed or half-open—fix bounds). Mid update preserves \(I\); interval shrinks ⇒ termination.

Example 11 — Euclidean algorithm

While \(b \neq 0\): \((a,b) \leftarrow (b, a \bmod b)\).
Invariant: \(\gcd(a,b)=\gcd(a_0,b_0)\). Maintenance from \(\gcd(a,b)=\gcd(b,a\bmod b)\). Exit \(b=0\) ⇒ \(\gcd=a\).

Example 12 — Strong induction on \(n//2\)

Mergesort correctness: assume recursive calls on smaller lengths correct; merge preserves sortedness. Size decreases by half—strong induction on array length.

Example 13 — Multiple bases Fibonacci inequality

\(F_n \le 2^{n-1}\) for \(n\ge 1\): bases \(n=1,2\); step \(F_{m+1}=F_m+F_{m-1}\le 2^{m-1}+2^{m-2}\le 2^m\).

Example 14 — Structural vs weak

Inducting on \(\mathrm{len}(xs)\) is weak induction on \(\mathbb{N}\); structural induction packages the same idea with constructors—preferred for ADTs.

Exercises

1. Prove by strong induction: every integer \(n\ge 2\) has a prime divisor.
   
2. Postage: denominations \(4\) and \(7\)—find \(N\) such that all \(n\ge N\) work; prove with enough bases.
   
3. Prove \(F_n \le 2^{n-1}\) with your \(F\) indexing.
   
4. Prove \(\sum_{i=1}^n F_i = F_{n+2}-1\) (standard indexing \(F_1=F_2=1\)).
   
5. Structural: \(\mathrm{len}(reverse(xs))=\mathrm{len}(xs)\) (assume recursive reverse definition you write).
   
6. Structural: height bounds size as in Example 7.
   
7. Write init/maintain/exit for factorial loop.
   
8. Write invariant for “find max in nonempty array” loop.
   
9. Prove by strong induction: any amount \(n\ge 12\) using \(4\) and \(5\) cent stamps? Check and adjust \(N\).
   
10. Show weak induction can prove the strong-induction schema by defining \(Q(n)=\forall j\le n\, P(j)\) (outline).
    
11. Binary search: argue termination using \(hi-lo\) decreases.
    
12. Euclid: prove \(b\) strictly decreases and stays nonnegative.
    
13. Tree: prove number of leaves related to number of degree-\(2\) nodes in full binary trees (standard relation).
    
14. Strong induction: \(a_n = a_{\lfloor n/2\rfloor} + n\) with \(a_1=1\)—prove \(a_n \le 2n\) or similar bound you choose and verify.
    
15. Loop invariant for reversing an array in place (two pointers)—state \(I\).
    
16. Why does Example 3 need three bases?
    
17. Prove Cassini for small \(n\) by hand; optional full induction.
    
18. Structural induction: \(\mathrm{map}(f, xs{+\!\!+}ys)=\mathrm{map}(f,xs){+\!\!+}\mathrm{map}(f,ys)\).
    
19. Correctness sketch: insertion into sorted list preserves sortedness (induct on list).
    
20. Give a false algorithm “proof” that forgets init of invariant; explain the hole.
    
21. Prove every positive integer is a product of primes (existence, strong induction)—fundamental theorem’s existence half.
    
22. Frobenius awareness: for \(3,5\) largest impossible is \(7=3\cdot 5-3-5\); verify \(7\) impossible, \(8+\) possible.
    
23. Induct on rounds: after \(r\) doublings, size \(\ge 2^r\) from \(1\).
    
24. Write \(P(n)\) for mergesort and state strong step dependencies.
    
25. Compare: prove \(2^n > n\) by weak induction vs by strong—do both.

CS connection

• Recursion correctness = structural / strong induction on input size.
  
• Loop invariants in Hoare logic; industrial use in critical code reviews.
  
• Binary search bugs are almost always invariant/bound errors (off-by-one).
  
• GCD / crypto depend on Euclid’s invariant.
  
• Distributed rounds use induction on round number.
  
• Compilers: instruction selection/optimizations proved by structural induction on IR.

Common pitfalls

Pitfall	What to do instead
Too few bases for recurrence order	Provide order-many consecutive bases
Claiming strong but only using \(P(k)\)	Still OK, but don’t skip needed \(P(k-1)\)
Invariant too weak	Strengthen so postcondition follows
Invariant too strong	Cannot prove maintenance
No termination argument	Need variant or finite measure
Structural induction without base constructor	Handle nil/leaf
Off-by-one in loop bounds	State inclusive/exclusive ranges in \(I\)

Checkpoint

• State strong induction
  
• Prove prime-factor existence
  
• Complete one postage proof
  
• Structural induction on lists or trees
  
• Full loop invariant (init/maintain/exit/use)
  
• Sketch binary search or Euclid invariant
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — strong induction schema in practice

When proving \(P(n)\), open with:
“Fix \(n > n_0\) and assume \(P(j)\) for all \(j\) with \(n_0 \le j < n\) (strong IH). …”
Then reduce \(n\) to one or more strictly smaller instances.

Fibonacci toolkit

With \(F_1=1,F_2=1,F_{n}=F_{n-1}+F_{n-2}\):

• \(\sum_{i=1}^n F_i = F_{n+2}-1\)
  
• \(F_n\) counts tilings of an \((n-1)\)-board with tiles of size 1 and 2 (combinatorial story)
  
• Growth \(\varphi^n/\sqrt{5}\) awareness (Binet)—not required to prove fully here

Loop invariant quality checklist

Question	Good invariant answers
What’s true about the prefix processed?	Precise predicate on indices
Does init hold?	Check before loop
Does body preserve?	Symbolic one iteration
At exit, enough for post?	\(I\wedge\neg G\Rightarrow\) post
Does it terminate?	Variant decreases

Structural induction = induction on derivation of the object

Lists/trees are built by rules; proofs follow the same rules. This matches how compilers recurse on ASTs.

More worked examples

Example 15 — Strong: complete binary tree node count
At most \(2^{h+1}-1\) nodes at height \(h\): use IH on both subtrees.

Example 16 — Postage 4 and 5
Bases \(4,5,6=4+...,7=...,8=2\cdot4\); step \(n\mapsto n-4\) for \(n\ge 8\) carefully with enough bases.

Example 17 — Euclid variant
\(a+b\) decreases as a variant if you prefer sum to single \(b\).

Example 18 — Binary search invariant bug
Off-by-one: \(lo\le hi\) vs \(lo<hi\); write both and see which postcondition works.

Additional exercises

26. Prove \(F_n\) is even iff \(3\mid n\) (strong or pattern + induction).
    
27. Structural: prove \(\mathrm{size}(T)=1+\mathrm{leaves}(T)+\mathrm{internal}(T)\) with your definitions.
    
28. Write full invariant proof for “max in array” loop.
    
29. Strong induction: any amount \(\ge 12\) with stamps \(4\) and \(5\)—or find exact Frobenius.
    
30. Explain why mergesort needs strong induction on length rather than weak \(n-1\) only.

Extended practice workshop

Strong induction proofs

1. Every \(n\ge 2\) has a prime factor.
   
2. Postage with \(3\) and \(5\) from \(N=8\).
   
3. Postage with \(4\) and \(7\)—find \(N\) and prove.
   
4. \(F_n \le 2^{n-1}\) with stated indexing.
   
5. \(\sum_{i=1}^n F_i = F_{n+2}-1\).
   
6. Existence of prime factorization (product of primes) for \(n\ge 2\).

Structural induction

7. \(\mathrm{len}(xs{+\!\!+}ys)=\mathrm{len}(xs)+\mathrm{len}(ys)\).
   
8. \(\mathrm{len}(\mathrm{rev}(xs))=\mathrm{len}(xs)\) with your rev definition.
   
9. \(size(T)\le 2^{h(T)+1}-1\) for binary trees.
   
10. \(\mathrm{map}(f,xs{+\!\!+}ys)=\mathrm{map}(f,xs){+\!\!+}\mathrm{map}(f,ys)\).

Loop invariants (write init/maintain/exit/use)

11. Sum \(1..n\).
    
12. Linear search.
    
13. Euclid GCD.
    
14. Binary search on sorted array (bounds careful).
    
15. Reverse array two-pointer.

Meta

16. Why three consecutive bases when step subtracts \(3\).
    
17. Convert strong proof idea to \(Q(n)=\forall j\le n\, P(j)\) weak form (outline).
    
18. Compare structural induction on lists vs weak induction on length.

Invariant quality score (0–2 each)

Criterion	Score
Precise predicate
Init true
Maintained
Implies post
Termination

Tomorrow

Day 33 — Fallacies. Affirming the consequent, illicit quantifier shifts, bad induction, circular reasoning; debug broken proofs.

---

Day 33 — Fallacies

Stage III · concept day
Goal: Recognize and name common logical and proof fallacies; debug broken proofs; avoid illicit quantifier shifts, converse/inverse errors, circular reasoning, false dichotomy, proof by example, and off-by-one induction mistakes.

Why this matters

Most wrong proofs look locally plausible. Reviewing pull requests of mathematics—your own included—means spotting invalid steps, not merely arithmetic slips. Fallacies also model real software bugs: affirming the consequent is “the metric is high, so the feature works”; illicit quantifier shift is “for every user there is a password” misread as one global password.

Theory

Propositional fallacies

Affirming the consequent. From \(P\rightarrow Q\) and \(Q\), infer \(P\). Invalid.
Counter-model: \(P\) false, \(Q\) true makes \(P\rightarrow Q\) true.

Denying the antecedent. From \(P\rightarrow Q\) and \(\neg P\), infer \(\neg Q\). Invalid.
Same truth-table family: \(P\) false, \(Q\) true.

Valid related forms.

• Modus ponens: \(P\rightarrow Q\), \(P\) ⊢ \(Q\).
  
• Modus tollens: \(P\rightarrow Q\), \(\neg Q\) ⊢ \(\neg P\).
  
• Hypothetical syllogism: \(P\rightarrow Q\), \(Q\rightarrow R\) ⊢ \(P\rightarrow R\).

Converse and inverse errors

From \(P\rightarrow Q\) infer \(Q\rightarrow P\) (converse) or \(\neg P \rightarrow \neg Q\) (inverse). Both invalid in general. Only the contrapositive \(\neg Q \rightarrow \neg P\) is equivalent.

Quantifier fallacies

Illicit shift \(\forall\exists\) to \(\exists\forall\).
From \(\forall x \exists y\, P(x,y)\) infer \(\exists y \forall x\, P(x,y)\). Invalid (Day 27).

Illicit shift for \(\exists\) witnesses.
From \(\exists x\, P(x)\) and \(\exists x\, Q(x)\) infer \(\exists x\,(P(x)\wedge Q(x))\). Invalid.

Wrong restricted quantifier.
Writing \(\forall x\,(P(x)\wedge Q(x))\) for “all \(P\)s are \(Q\)s.”

Negation errors.
\(\neg\forall x\, P\) treated as \(\forall x\, \neg P\) (too strong).

Circular reasoning (begging the question)

Using the claim (or a thinly renamed form) as a premise in its own proof. Different from induction’s legitimate IH (which is smaller/previous, not the goal).

False dichotomy

Assuming \(C_1 \vee C_2\) when a third possibility exists—missing case in case analysis.

Proof by example / anecdote

Showing \(P(3)\) and concluding \(\forall n\, P(n)\). Valid only for \(\exists\), or when the domain has one element.

Proof by picture / intuition alone

Diagrams help discovery; they are not substitutes for cases at boundaries.

Induction fallacies

• Horses: invalid step at \(n=1\) (Day 31).
  
• Base missing or wrong.
  
• Off-by-one: \(P(n)\) stated for \(n\ge 1\) but step uses \(n-1\) at \(n=1\).
  
• IH applied to a larger instance (circular).
  
• Assuming \(P(k+1)\) inside the step.

Algebra / definition fallacies

• Division by zero.
  
• Treating non-equivalent rewrites as \(\equiv\).
  
• Using \(a\mid bc \Rightarrow a\mid b\) without coprimality/prime hypothesis.

How to debug a proof

1. Underline each inference; ask “what rule?”
   
2. Instantiate universals carefully; track free variables.
   
3. Try small counter-models if the claim is universal.
   
4. Check boundaries (\(0\), empty, \(n=1\)).
   
5. Negate the claim—does the proof still “work”? Then it proved nothing.

Fallacies vs honest mistakes

Honest algebra errors are not “fallacies” in the rhetorical sense but still invalidate proofs. Label both: invalid step vs false premise.

Worked examples

Example 1 — Affirming consequent

Spec: if admin then 2FA enabled. Observe 2FA enabled. Conclude admin. Fallacy. Guest could have 2FA.

Example 2 — Denying antecedent

If authenticated then access. User not authenticated. Conclude no access. Invalid if access can occur through internal network path without that flag—or mathematically \(P\rightarrow Q\) and \(\neg P\) allow \(Q\).

Example 3 — Converse

If sorted then binary search correct. Binary search returned index. Conclude array sorted. No.

Example 4 — Quantifier shift

“Every student has a counselor” \(\forall s\exists c\). Infer \(\exists c\forall s\) “one counselor for all.” Fallacy.

Example 5 — Dual witnesses

\(\exists\) even and \(\exists\) odd integer; not \(\exists\) number both even and odd.

Example 6 — Circular

“\(n\) even because \(n=2k\) and \(2k\) is even because \(n\) is even.” Circular witness.

Example 7 — Horses

Identify non-overlap at \(k=1\) (Day 31).

Example 8 — Proof by example

“\(n^2+n+41\) prime for \(n=0,1,2,\ldots,10\) hence for all \(n\).” False at \(n=40\) or \(n=41\).

Example 9 — Bad negation

Claim: all tests pass. “Negation: all tests fail.” Wrong; some fail is enough.

Example 10 — False dichotomy

“Either \(n\) even or prime” for case proof of property of all \(n\)—misses \(9\), \(15\), etc.

Example 11 — Induction off-by-one

\(P(n): 1+2+\cdots+n = n(n+1)/2\). Step assumes formula for \(k\) including \(k=0\) but starts base at \(1\) only—OK here; broken variant uses empty sum wrongly as \(1\).

Example 12 — Division by zero

From \(x=y\) conclude \(x/x=y/x\) then \(1=1\) “proves” all equal after cancel—invalid if \(x=0\). Famous fake \(1=2\) proofs.

Example 13 — Illicit divisibility

\(4 \mid 2\cdot 2\) but \(4\nmid 2\). Inferring \(a\mid b\) from \(a\mid bc\) fails.

Example 14 — Debugging transcript

Broken: “Assume \(n^2\) even. Then \(n\) even because even squares come from even \(n\).” Uses the claim as reason. Fix: prove contrapositive properly or cite proved lemma.

Exercises

For each broken argument (1–12), name the fallacy and give a counterexample or pinpoint the bad step.

1. If the build is red, tests failed. Tests failed. Therefore the build is red.
   
2. If \(n\) is multiple of \(6\), \(n\) even. \(n\) even; therefore multiple of \(6\).
   
3. Every request has a server. So there is a server that handles every request.
   
4. Some user is admin. Some user is banned. So some admin is banned.
   
5. Checked \(n=1..20\) for primality of \(n^2+n+41\)—all prime—so always prime.
   
6. Horses same color “proof.”
   
7. \(P\rightarrow Q\) proved by assuming \(Q\) and deriving \(Q\).
   
8. To prove \(A\subseteq B\), show one element of \(A\) lies in \(B\).
   
9. From \(\neg(P \wedge Q)\) conclude \(\neg P \wedge \neg Q\).
   
10. Base \(n=0\) false but step OK ⇒ still conclude \(\forall n\,P(n)\)?
    
11. From \(p\rightarrow q\) and \(\neg p\) conclude \(\neg q\).
    
12. “Proof” \(1=2\) via hidden division by zero—find the step.

Construct / repair:

13. Write a valid modus tollens security argument.
    
14. Correctly negate “all packets are authenticated.”
    
15. Give a valid case split for parity of \(n^2\).
    
16. Repair a circular “proof” that \(\sqrt{2}\) irrational that assumes unique factorization vaguely—outline a clean version.
    
17. Is “proof by minimal counterexample” circular? Explain why not (when well-ordering used).
    
18. Find a real-world blog/docs sentence that affirms the consequent; rewrite.
    
19. Show with assignments that converse of \(p\rightarrow q\) is not entailed.
    
20. Quantifiers: write valid and invalid English for \(\forall\exists\) friendship.
    
21. Induction: craft a false \(P\) with true base and false step; show.
    
22. Induction: true step for \(k\ge 2\), false at \(k=1\)—relate to horses.
    
23. Explain why \(\exists x\,(P\rightarrow Q(x))\) is not \(\forall x\, P \rightarrow \exists x\, Q\) mess—parse two different formulas and evaluate on a tiny model.
    
24. Debug: “Since \(n\) and \(n+1\) coprime always, and \(n(n+1)\) even, both factors… wait”—what can and cannot be concluded.
    
25. Portfolio: invent three fallacious one-paragraph proofs for true claims (sound conclusion, bad argument) and fix them.

CS connection

• Metrics as consequents: latency drop does not prove a specific optimization caused it (causal affirming).
  
• AuthZ bugs: wrong direction of implications in policies.
  
• Distributed specs: \(\forall\exists\) vs \(\exists\forall\) leadership.
  
• Flaky tests: “passed on my machine” as proof by example.
  
• Code review: demand valid proof structure for critical concurrent invariants.
  
• Type errors sometimes encode fallacious “conversions” (unsafe cast ≈ illicit implication).

Common pitfalls

Pitfall	What to do instead
Naming a fallacy without a counter-model	Always give assignment or object
Calling induction circular	IH is previous; goal is next
Over-accusing “fallacy” for algebra slips	Separate error types
Fixing English only	Fix the formal step
Using invalid converse in “optimization” of proof	Use contrapositive only if equivalent

Checkpoint

• Name and refute affirming consequent & denying antecedent
  
• Converse vs contrapositive
  
• Illicit \(\forall\exists\) shift example
  
• Proof by example vs valid \(\exists\)
  
• Horses / induction step failure
  
• Circular vs legitimate IH
  
• Debug a provided broken proof
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — a reviewer’s checklist

Before accepting a proof (or merging a “correctness argument” in a design doc):

1. Are all variables quantified?
   
2. Is each inference a named rule or a cited lemma?
   
3. Are base cases of inductions explicit?
   
4. Is \(\forall\exists\) order respected?
   
5. Is any \(\rightarrow\) used in converse form?
   
6. Is “without loss of generality” justified by symmetry?
   
7. Are empty/zero edge cases covered?

Fallacy → bug dictionary

Fallacy	Software analogue
Affirming consequent	Metric moved ⇒ feature caused it
\(\forall\exists\) shift	Per-tenant resource ⇒ one global resource
Proof by example	“Works on my laptop”
False dichotomy	if/else missing a state
Bad induction step	Off-by-one in loop for \(n=1\)
Circular reasoning	Spec cites implementation as justification

Repair patterns

• Converse error → prove contrapositive or find counterexample.
  
• Illicit shift → provide dependence \(y(x)\) or abandon claim.
  
• Circular → push the claim into a lemma proved independently.
  
• Incomplete cases → add the missing residue/sign/branch.

More worked examples

Example 15 — Hidden division by zero
From \(a=b\) derive \(a^2=ab\), then \(a^2-b^2=ab-b^2\), \((a-b)(a+b)=b(a-b)\), cancel \(a-b\) to get \(a+b=b\), so \(a=0\)… the cancel assumes \(a\neq b\) false when \(a=b\). Classic.

Example 16 — Quantifier negation fallacy
“Not every packet is corrupted” ≠ “every packet is uncorrupted.”

Example 17 — Valid-looking induction with false claim
\(P(n): n=n+1\) with step adding 1 to both sides of IH equality—step valid from false IH, base false.

Example 18 — Affirming in security
Alarm triggered ⇒ intrusion. Alarm triggered. Conclude intrusion—false positives exist.

Additional exercises

26. Debug a written fake proof that \(1=2\) (find illegal cancel).
    
27. Write a fallacious and a correct proof that sum of evens is even.
    
28. Identify fallacy: from \(\exists x P(x)\rightarrow Q\) infer \(\exists x(P(x)\rightarrow Q)\)—compare meanings on a model.
    
29. Give a counter-model to converse of “if sorted, binary search correct.”
    
30. Portfolio: collect five fallacies from real life/docs this week.

Extended practice workshop

Name the fallacy (and refute)

1. If compiled, then syntax OK. Syntax OK. Therefore compiled.
   
2. If admin then access. No admin. Therefore no access.
   
3. Every API has a rate limit config. So one global rate limit config exists.
   
4. Some tests failed. Some tests are flaky. So some flaky tests failed.
   
5. \(n^2-n+41\) prime for many \(n\), hence all \(n\).
   
6. Horses same color.
   
7. From \(p\rightarrow q\) conclude \(\neg p\rightarrow\neg q\).
   
8. From \(\neg(p\wedge q)\) conclude \(\neg p\wedge\neg q\).
   
9. To prove \(\forall n\,P(n)\), show \(P(1),P(2),P(3)\).
   
10. Case split: \(n\) prime or \(n\) even—for a property of all \(n\).

Repair the argument

11. Circular “proof” that \(\sqrt{2}\) irrational—rewrite cleanly.
    
12. Induction with missing base—add it.
    
13. Quantifier shift in a system design doc—correct the English.
    
14. Fake \(1=2\) via cancel—mark illegal step.

Valid forms practice

15. Write a modus ponens security argument.
    
16. Write a modus tollens testing argument.
    
17. Write a valid \(\forall\exists\) claim and an invalid \(\exists\forall\) strengthening.

Meta

18. When is “proof by example” valid?
    
19. Why induction’s IH is not circular.
    
20. Reviewer checklist: 5 questions you always ask.

Fallacy flashcards

Fallacy	One-line form
Affirm consequent	\(P\to Q,Q\Rightarrow P\)
Deny antecedent	\(P\to Q,\neg P\Rightarrow\neg Q\)
Converse	\(P\to Q\Rightarrow Q\to P\)
Inverse	\(P\to Q\Rightarrow\neg P\to\neg Q\)
Quantifier shift	\(\forall\exists\Rightarrow\exists\forall\)
Proof by example	\(P(a)\Rightarrow\forall x P(x)\)

Synthesis

Fallacies are invalid inference patterns—local steps that look like reasoning but do not preserve truth. Gate III will mix them with correct proofs; your job is to name, refute (counter-model), and repair. The same skills catch bugs in design docs: wrong implication direction, \(\forall\exists\) leadership claims, and “works on my machine” universals.

Reviewer protocol (run on every suspicious paragraph)

1. Underline each “therefore.”
   
2. Ask: which rule? (MP, MT, UI, EG, IH, cases, …)
   
3. If no rule, demand a counter-model or a fix.
   
4. Check quantifier order and \(\rightarrow\) vs \(\wedge\) in restricted forms.
   
5. For induction: base present? step for all \(k\ge n_0\)?
   
6. For cases: exhaustiveness?

More worked examples

Example 19 — Inverse error in ops.
Policy: “if maintenance mode then reads-only.” Infer: “if not maintenance then not reads-only.” Invalid (inverse). Reads-only may hold for other reasons.

Example 20 — Dual \(\exists\) fusion.
“There is a failed test” and “there is a flaky test” do not yield “there is a failed flaky test.” Witnesses may differ.

Example 21 — False dichotomy in API design.
“Every request is either cached or hits origin.” Misses: rejected before cache, redirected, streamed from third party. Case proof of a total classification needs a true partition.

Example 22 — Circular definition vs circular proof.
Defining \(e\) as “the identity” and then proving uniqueness of identity is fine if the axioms are independent. Using “\(n\) is even because \(n\) is even” inside a divisibility proof is circular. Distinguish definitional unfolding from assuming the theorem.

Example 23 — Valid-looking algebra, invalid cancel.
From \(a=b\) derive \(a^2=ab\), rearrange to \((a-b)(a+b)=b(a-b)\), “cancel” \(a-b\) to conclude \(a+b=b\). Illegal when \(a=b\) (the hypothesis), i.e. dividing by zero in disguise.

Extra exercises (synthesis)

31. Give truth assignments showing affirming the consequent and denying the antecedent are invalid.
    
32. Write English and formal forms of a \(\forall\exists\) claim and an illicit \(\exists\forall\) strengthening; refute the latter on \(\mathbb{Z}\).
    
33. Repair: “\(n^2\) even ⇒ \(n\) even because even squares come from even \(n\).”
    
34. Is minimal-counterexample reasoning circular? Defend in \(\le 5\) sentences.
    
35. Find or invent a docs sentence that treats a metric movement as proof of a specific cause; rewrite carefully.
    
36. Portfolio: three fallacious proofs of true claims (bad argument, good conclusion) and their repairs.

Fallacy ↔︎ Stage III topic map

Fallacy	Closest concept day
Converse / inverse	25 equivalence, 29 contrapositive
Quantifier shift	26–27 quantifiers
Proof by example	28–30 proof methods
Horses / bad induction	31–32 induction
False dichotomy	30 cases
Circular reasoning	28–29 proof hygiene

Before Gate III, rework flashcards cold and debug one fake \(\sqrt{2}\) proof and one horses write-up from blank paper.

Tomorrow

Day 34 — Gate III. Portfolio check: truth tables, quantifier negation, three full proofs (direct, contra/contrapositive, induction), fallacy identification.

---

Day 34 — Gate III

Stage III · gate day
Goal: Closed-book mixed review of propositional logic, quantifiers, and proof methods (Days 23–33). Diagnose weak spots; retest before Stage IV.

Why this matters

Gates are mastery checks, not calendar markers. Stage IV (sets, relations, functions) assumes you can negate statements, choose a proof style, and not swap \(\forall\exists\). If this gate frays, repair now—later counting and graphs pile on justification load.

What this gate covers

Block	Days	Skills
Truth tables & connectives	23	Tables; tautology/contradiction; \(\rightarrow\) vacuous truth; XOR; precedence
Boolean algebra	24	De Morgan, absorption, simplify; DNF/CNF lite
Equivalence	25	Tables + law chains; contrapositive \(\equiv\); completeness awareness
Predicates & quantifiers	26	Translate; negate; restricted \(\forall\)/\(\exists\)
Nested quantifiers	27	Order matters; \(\exists!\); witnesses
Direct proof	28	Parity, divides
Contrapositive / contradiction	29	Method choice; \(\sqrt{2}\) shape
Cases & existence	30	Exhaustion; constructive existence
Weak / strong induction	31–32	\(P(n)\); loop invariant idea; structural lite
Fallacies	33	Affirming consequent; bad induction; quantifier shift

How to use this page

1. Closed book first pass (timebox \(90\)–\(120\) minutes).
   
2. Mark each item: ✅ confident / ⚠ shaky / ❌ failed.
   
3. Open notes only to repair ❌/⚠—then re-solve cold next day.
   
4. Do not proceed to Day 35 until you can clear a second pass on failed items.

Important

No programming labs. Optional calculator only to check arithmetic. Proofs are by hand.

Theory — rapid self-check sheet

Reproduce from memory on scrap paper, then compare:

1. Truth tables for \(p\rightarrow q\), \(p\leftrightarrow q\), \(p\oplus q\).
   
2. De Morgan laws (propositional) and quantifier negation rules.
   
3. \(p\rightarrow q \equiv \neg p \vee q \equiv \neg q \rightarrow \neg p\).
   
4. Restricted quantifiers: \(\forall x\in S\,P\) vs \(\exists x\in S\,P\).
   
5. Why \(\forall x\exists y\,P \not\equiv \exists y\forall x\,P\) (one counter-model).
   
6. Direct / contrapositive / contradiction templates.
   
7. Weak induction skeleton; strong when needed.
   
8. Loop invariant: init / maintain / exit+use.
   
9. Affirming the consequent in one line; illicit \(\forall\exists\) shift.
   
10. Definition of even/odd and \(a\mid b\).

Worked examples (gate warm-ups)

Warm-up A — Table
Show \((p \wedge q) \rightarrow p\) is a tautology (4 rows).

Warm-up B — Simplify
\(\neg(p \rightarrow \neg q) \equiv p \wedge q\) (named laws).

Warm-up C — Quantifiers
Negate \(\forall x \exists y\, (x < y)\) on \(\mathbb{Z}\) and state the truth of the original.

Warm-up D — Direct proof
If \(n\) odd then \(n^2\) odd.

Warm-up E — Contrapositive
If \(n^2\) even then \(n\) even.

Warm-up F — Induction
\(\sum_{i=1}^n i = n(n+1)/2\).

Warm-up G — Fallacy
Name: From “if admin then 2FA” and “has 2FA” infer “admin.”

Warm-up H — Cases
\(n(n+1)\) always even.

Warm-up I — Strong / postage lite
Why three consecutive bases when stepping by \(3\) in postage proofs?

Warm-up J — Nested English
Translate both orders: every student takes some course / some course taken by every student.

Gate exam (closed book)

Part I — Propositional (mix)

1. Full truth table for \((p \rightarrow q) \wedge (q \rightarrow p)\). Relate to \(\leftrightarrow\).
   
2. Is \((p \rightarrow q) \vee (q \rightarrow p)\) a tautology? Justify.
   
3. Simplify \(\neg(\neg p \wedge q)\) with named laws.
   
4. Prove or disprove equivalence: \(p \rightarrow (q \rightarrow r)\) vs \((p \rightarrow q) \rightarrow r\).
   
5. Write XOR in DNF and CNF.
   
6. Parenthesize under standard precedence: \(\neg p \vee q \rightarrow r\).
   
7. Sufficient vs necessary: one sentence each with arrows for “valid token / access.”
   
8. Show \(p \wedge (p \vee q) \equiv p\) (absorption) by algebra or table.

Part II — Quantifiers

9. Translate: “No banned user is admin.” Two equivalent forms.
   
10. Negate fully: \(\forall u\, (Auth(u) \rightarrow \exists r\, Role(u,r))\).
    
11. On \(\mathbb{R}\): truth of \(\forall x\exists y\,(xy=1)\) and \(\exists y\forall x\,(xy=1)\).
    
12. Expand \(\forall n\in\mathbb{N}\, P(n)\) and \(\exists n\in\mathbb{N}\, P(n)\) using \(\rightarrow\) / \(\wedge\).
    
13. Write \(\exists! x\, P(x)\) without the \(!\) symbol.
    
14. Free vs bound: mark variables in \(\forall x\, (P(x,y) \rightarrow \exists y\, Q(y))\).
    
15. Give a \(2\)-element model where \((\exists x\,P)\wedge(\exists x\,Q)\) but not \(\exists x\,(P\wedge Q)\).

Part III — Proofs (write full proofs)

16. Direct: If \(a\mid b\) and \(a\mid c\) then \(a\mid (b+c)\).
    
17. Contrapositive or contradiction: If \(n^2\) is odd then \(n\) is odd.
    
18. Contradiction classic: \(\sqrt{2}\) is irrational (full write-up).
    
19. Cases: For all \(n\in\mathbb{Z}\), \(n^2 \not\equiv 3 \pmod{4}\).
    
20. Weak induction: \(\sum_{i=0}^n 2^i = 2^{n+1}-1\) for \(n\ge 0\).
    
21. Weak or strong: \(3 \mid (4^n-1)\) for \(n\ge 0\).
    
22. Strong induction: Every integer \(n\ge 2\) has a prime factor.
    
23. Existence constructive: Exhibit witnesses for \(\exists x,y\in\mathbb{Z}\, (3x+5y=1)\) or prove impossible.
    
24. Biconditional: \(n\) even iff \(n+1\) odd (both directions).
    
25. Loop invariant sketch: For a loop that sets s += i for i=1..n, state \(I\), init, maintain, exit use.

Part IV — Fallacies (identify & refute)

26. Affirming the consequent—give formal shape and a CS-flavored counterexample.
    
27. Illicit \(\forall\exists \Rightarrow \exists\forall\)—counter-model on \(\mathbb{Z}\).
    
28. Proof by example for a universal claim—why invalid?
    
29. Horses fallacy—where does the step fail?
    
30. From \(p\rightarrow q\) infer \(\neg p \rightarrow \neg q\)—name and counter-assignment.
    
31. Circular reasoning vs legitimate inductive hypothesis—one paragraph.
    
32. False dichotomy in a case proof—invent a broken outline and fix it.

Part V — Mixed synthesis

33. Prove by induction on \(n\) that a set with \(n\) elements has \(2^n\) subsets (outline OK if full algebra clear).
    
34. Negate the \(\varepsilon\)-\(N\) limit definition form \(\forall\varepsilon>0\,\exists N\,\forall n\ge N\,(|a_n-L|<\varepsilon)\).
    
35. Choose methods: for each claim, pick direct / contra / cases / induction and justify in one line:
    1. sum formula; (b) no largest integer; (c) \(n(n+1)\) even; (d) if \(6\mid n\) then \(2\mid n\).
       
36. Boolean: put \((p \rightarrow q) \wedge p\) into simplest equivalent form.
    
37. Translate sorted nondecreasing array of length \(n\) with nested quantifiers.
    
38. Explain vacuous truth of \(\forall x\in\emptyset\, P(x)\) in one sentence.
    
39. Functional completeness awareness: express \(p\vee q\) using only \(\neg\) and \(\wedge\).
    
40. Portfolio reflection: list three skills from Days 23–33 you will drill this week.

Scoring guide (self)

Score band	Meaning	Action
≥ 34/40 solid	Stage III ready	Proceed to Day 35
26–33	Patch holes	Retake failed numbers cold in 48h
≤ 25	Rebuild	Revisit Days 23–27 then 28–33; retake full gate

Count a multi-part proof item as split if needed (e.g. ½ for structure without algebra). Honesty > speed.

Optional deep extras (if clean early)

41. Prove Cassini’s Fibonacci identity for \(n\ge 1\) (state indexing).
    
42. Full loop invariant proof sketch for Euclid’s algorithm.
    
43. Show \(\{\mathrm{NAND}\}\) can express \(\neg\) and \(\wedge\) (formulas).
    
44. Prove \(\log_2 3\) irrational.
    
45. Structural induction: \(\mathrm{len}(xs{+\!\!+}ys)=\mathrm{len}(xs)+\mathrm{len}(ys)\).

CS connection (gate lens)

• Specs are quantified implications; tests seek counterexamples to \(\forall\).
  
• Refactors need \(\equiv\), not “looks similar.”
  
• Invariants are induction; fallacies are production incidents waiting to happen.
  
• Stage IV sets/relations will encode more of the same logic with \(\in\) and \(\subseteq\).

Common pitfalls (gate day)

Pitfall	What to do instead
Open book too early	Close it for pass 1
Sketchy proofs without witnesses	Exhibit \(k\) in parity/divisibility
Forgetting to negate nested quantifiers fully	Flip each quantifier
Method name without proof body	Write the proof
Skipping fallacy counterexamples	Always refute

Checkpoint

• Self-check sheet reproduced from memory
  
• Warm-ups A–J attempted cold
  
• Gate exam Parts I–V scored
  
• Failed items scheduled for retest
  
• Three personal weak spots written down
  
• Ready/not-ready decision for Stage IV

Two takeaways from Stage III:

1. …
   
2. …

Extended drill set (still closed book if possible)

Drill A — Tables under time pressure

41. Table for \(p\oplus q \oplus r\) (careful association).
    
42. Show \((p\rightarrow q)\rightarrow((\neg p\rightarrow q)\rightarrow q)\) is a tautology.
    
43. Contingency hunt: invent a 3-var formula with exactly 3 true rows.

Drill B — Algebra under time pressure

44. Simplify \(\neg(p\wedge\neg(q\vee p))\) fully.
    
45. Prove \(\neg(p\leftrightarrow q)\equiv p\leftrightarrow\neg q\).
    
46. Put \(p\rightarrow(q\wedge r)\) into CNF.

Drill C — Quantifier battery

47. Negate \(\exists x\forall y\exists z\, R(x,y,z)\).
    
48. Translate and negate: “Every nonempty file has a checksum.”
    
49. On \(\mathbb{N}\): \(\forall m\exists n\,(n>m)\) vs \(\exists n\forall m\,(n>m)\).
    
50. Write \(\exists!\) for “unique root of \(x^2-1=0\) in \(\mathbb{R}\)”—is it true? (No—two roots.)

Drill D — Proof battery

51. Direct: product of two odds is odd.
    
52. Contrapositive: if \(n^2\) not divisible by \(2\) then \(n\) not divisible by \(2\).
    
53. Contradiction: no largest negative integer? (false claim)—instead: no largest positive integer.
    
54. Cases: \(n^2\equiv 0\) or \(1\pmod 4\).
    
55. Induction: \(\sum_{i=1}^n (2i-1)=n^2\).
    
56. Strong: every \(n\ge 2\) composite or prime—trivial; instead every \(n\ge 2\) has prime factor.
    
57. Invariant: state \(I\) for while n > 0: n = n-1; c = c+1 counting down.

Drill E — Fallacy battery

58–62. Invent five one-line fallacious inferences and name them.

Repair plan template

Failed #	Topic day	Minutes drill	Retest date

Full sample solution outlines (check after attempt)

Item 18 outline (\(\sqrt{2}\)): assume \(p/q\) lowest terms → \(p^2=2q^2\) → \(p\) even → \(q\) even → contradict gcd.

Item 20 outline (geometric): base \(n=0\); IH sum to \(k\); add \(2^{k+1}\).

Item 22 outline (prime factor): strong IH on smaller factors if composite.

Item 26 outline (fallacy): \(P\rightarrow Q\), \(Q\), infer \(P\)—counter-model \(P\) false \(Q\) true.

Stage III exit criteria

You are ready for Stage IV when you can, cold:

• Finish a 4-row and sketch an 8-row table.
  
• Negate a two-quantifier sentence without hesitation.
  
• Write direct, contrapositive, and induction proofs to a peer standard.
  
• Name and refute three fallacies.

Timed mock (45 minutes)

Do only these, closed book, then stop:

#	Task	Minutes
M1	Table \((p\rightarrow q)\leftrightarrow(\neg q\rightarrow\neg p)\)	6
M2	Simplify \(\neg(p\vee\neg q)\wedge p\)	4
M3	Negate \(\forall x\exists y\,(P(x)\rightarrow Q(x,y))\)	5
M4	Direct: even+even=even	5
M5	Contrapositive: odd square ⇒ odd \(n\)	6
M6	Induction: \(\sum_{i=1}^n i = n(n+1)/2\)	8
M7	Name fallacy: \(P\rightarrow Q\), \(Q\), therefore \(P\)	2
M8	\(\forall\exists\) vs \(\exists\forall\) counter-model on \(\mathbb{Z}\)	5
M9	Cases: \(n^2\not\equiv 3\pmod 4\)	4

Pass bar: \(\ge 7/9\) solid. Below that: schedule full gate retake.

After mock reflection prompts

• Which item was slowest?
  
• Did you skip naming laws in algebra?
  
• Did induction include an explicit \(P(n)\)?
  
• Did quantifier negation flip every quantifier?

Second-pass protocol

1. Only reopen notes for ❌ items.
   
2. Write a correct solution once with notes.
   
3. Next day, redo ❌ cold without notes.
   
4. Log time-to-completion.

Stage III → IV teaser

You will reuse:

• Element chase ≈ direct proof with \(x\in A\).
  
• \(\subseteq\) proofs ≈ implication proofs.
  
• Equivalence relations ≈ kernels of functions.
  
• Induction on set size for \(|\mathcal{P}(S)|=2^n\).

Synthesis — Stage III portfolio

Gate III is not a new topic day; it is a compression of Days 23–33. Treat this synthesis as your one-page mental model before and after the exam.

Skill clusters (what “ready” means)

Cluster	Cold ability
Propositional	4–8 row tables; simplify with named laws; \(\rightarrow\) as \(\neg p\vee q\)
Quantifiers	Translate all/some/no; negate nested; \(\forall\exists\neq\exists\forall\)
Proof methods	Direct, contra, contrapositive, cases, weak/strong induction
Invariants	Init / maintain / exit+use in one paragraph
Fallacies	Name, counter-model, repair

Method choice drill (answer in one line each)

1. \(\sum_{i=1}^n i = n(n+1)/2\) →
   
2. If \(n^2\) even then \(n\) even →
   
3. \(n(n+1)\) always even →
   
4. \(\sqrt{2}\notin\mathbb{Q}\) →
   
5. No largest integer →
   
6. Every \(n\ge 2\) has a prime factor →
   
7. Product of odds is odd →
   
8. \((p\rightarrow q)\wedge p\) simplifies to →

(Expected style: induction; contrapositive; cases/parity; contradiction; contradiction; strong induction; direct; \(p\wedge q\).)

Mini repair log (use after scoring)

Item #	Failure mode	Day to reread	Retest (Y/N)
	wrong \(\rightarrow\) expansion	23–25
	quantifier negation incomplete	26–27
	missing witness in direct proof	28
	lowest terms omitted in \(\sqrt{2}\)	29
	incomplete cases	30
	vague \(P(n)\) / horses	31–32
	fallacy without counter-model	33

More mixed warm-ups (post-exam or second pass)

W1. Negate \(\forall\varepsilon>0\,\exists N\,\forall n\ge N\,(|a_n-L|<\varepsilon)\) fully.
W2. Prove: if \(a\mid b\) and \(a\mid c\) then \(a\mid(bx+cy)\) for all integers \(x,y\).
W3. Cases: \(n^2\equiv 0\) or \(1\pmod 4\).
W4. Induction: \(\sum_{i=0}^n 2^i = 2^{n+1}-1\).
W5. Fallacy: from “if sorted then binary search OK” and “binary search returned index” infer “sorted.”

Exit criteria (restate)

You may enter Stage IV when, without notes, you can: finish a small truth table; negate a two-quantifier sentence; write direct + contrapositive + induction proofs to peer standard; name and refute three fallacies. Honesty over speed—retest beats pretend-ready.

Tomorrow

Day 35 — Sets. Roster and builder notation; \(\in\), \(\subseteq\), \(\subsetneq\); empty set; universe; Russell paradox awareness; equality by double inclusion.