Discrete Math Mega-Notes: Sets (incl.

indexed families) & Induction (PMI, PCI, WOP — and why

they’re equivalent)

0) Roadmap & Mental Models

 Sets & Logic first: what a set is, how we build and combine sets, and how to read/quantify
statements about them.

 Indexed families: the right way to talk about “many sets at once,” enabling clean definitions of
big unions/intersections and products.

 Relations & products: Cartesian products, relations as subsets of products, domains/ranges,

identity relation, digraph pictures.

 Induction methods: PMI (ordinary), PCI (strong/complete), WOP (well-ordering/minimal

counterexample).

 Equivalence triangle: PMI ⇄ PCI ⇄ WOP, with short, clean proofs, plus exam-ready templates.

 Worked examples (from your notes):

sums, divisibility, De Moivre, Fibonacci bounds, “4s+5t” representation, √3 irrational,
domain/range examples, equivalence classes, digraphs.

1) Sets: the basic toolkit

1.1 What is a set?

 Definition. A set is a collection of distinct objects (called elements). We write x ∈ A for “ x is an

element of A .”

 Standard sets: N={1 ,2 , 3 , … }(this course uses 1 as the first natural), Z , Q , R , etc. (Your
lecture notes adopt a Peano-style view for N and place PMI among the axioms.)

1.2 Describing sets

 Roster: A={2 , 4 ,6 }.

 Set-builder: A={x ∈ Z : x is even } .

 Power set: P( A)is the set of all subsets of A .

1.3 Set operations (with quick logic mirrors)

 Subset: A ⊆ Biff (∀ x)(x ∈ A ⇒ x ∈ B).

 Union: A ∪ B={ x : x ∈ A or x ∈ B }.
  Intersection: A ∩ B={ x : x ∈ A and x ∈ B }.

 Difference: A ∖ B={x ∈ A : x ∉ B }.

 Complement: Á={x ∈ U : x ∉ A }given a universe U .

 Distributive patterns: A ×(B ∪C )=( A × B)∪( A × C), etc. Your notes prove several product
vs. union/intersection identities and non-identities—see §2.2 for details and a counterexample.

1.4 Quantifiers (because we use them constantly)

 Universal: ∀ x P( x)means “every object has P .”

 Existential: ∃ x P(x )means “some object has P.”

 Proof pattern (from your notes): To prove (∀ x) P(x) , let x be arbitrary and show P(x ).

Pitfall check. Don’t write “assume for all n ” as your inductive hypothesis. It must be “assume for some
arbitrary n .”

2) Cartesian products, relations, digraphs

2.1 Cartesian products

 Definition. A × B={(a , b): a∈ A , b ∈ B }.

 Higher arity: A × B ×C are ordered triples.

Nuance (in your notes): ( A × B)× C vs. A ×(B × C)have the same value sets but different
bracketing/structure; don’t identify them unless you intentionally flatten tuples.

2.2 Identities your notes proved

( A ∩ B)×C=( A ×C )∩(B × C)— true.

Definitions

Cartesian Product:

X ×Y ={(x , y )∣ x ∈ X and y ∈Y }
Intersection:

X ∩Y ={x ∣ x ∈ X and x ∈ Y }

Goal

Show both inclusions:

( A ∩ B)×C ⊆( A × C)∩(B× C)
 ( A ×C )∩(B × C)⊆( A ∩ B)×C

Proof

(1) Show ( A ∩ B)×C ⊆( A × C)∩(B× C)

Take any element (x , y )∈( A ∩ B)×C .

Then:

x ∈ A ∩B , so x ∈ A and x ∈ B ,

y ∈C .

Hence:

(x , y )∈ A ×C ,

(x , y )∈ B× C .
Therefore,

(x , y )∈( A × C)∩(B ×C).

✅ So ( A ∩ B)×C ⊆( A × C)∩(B× C).

(2) Show ( A ×C )∩(B × C)⊆ ( A ∩ B)×C

Take any element (x , y )∈( A × C)∩(B ×C).

Then:

(x , y )∈ A ×C ⟹ x ∈ A and y ∈C ,

(x , y )∈ B× C ⟹ x ∈ B and y ∈C .
Thus:

x ∈ A ∩B ,

y ∈C .

Therefore:

(x , y )∈( A ∩ B)×C .

✅ So ( A ×C )∩(B × C)⊆( A ∩ B)×C .

Conclusion
 Since both inclusions hold, we have equality:

( A ∩ B)×C=( A ×C )∩(B × C) .

Example A ×∅ =∅ — true.

Definitions

1. Cartesian product:
For any sets A and B,

A × B={(a , b)∣ a ∈ A and b∈ B}.

2. Empty set:
∅ has no elements.

Proof

We must show:

A ×∅ =∅ .

Step 1: Show A ×∅ ⊆ ∅ .

Take any element x ∈ A ×∅ .

Then by definition of Cartesian product,

x=(a , b) for some a∈ A and b ∈ ∅ .

But since ∅ has no elements, there is no such b .

Hence there is no x satisfying this condition.
Therefore A ×∅ has no elements, so

A ×∅ ⊆ ∅ .

Step 2: Show ∅ ⊆ A × ∅ .

The empty set is a subset of every set:

∅ ⊆ S for all sets S .

So
 ∅⊆ A×∅.

Step 3: Combine

 Subset but not equality (important counterexample):

( A × B)∪ (C × D) ⊆( A ∪ C )×( B∪ D)Inclusion

Take (x , y )∈( A × B)∪(C × D).

Then either (x , y )∈ A × Bor (x , y )∈C × D.

 If (x , y )∈ A × B , then x ∈ A ⊆ A ∪ C and y ∈ B ⊆ B ∪ D , hence (x , y )∈( A ∪C )×(B ∪ D) .

 If (x , y )∈C × D, the same reasoning gives (x , y )∈( A ∪ C )×(B ∪ D) .

Thus ( A × B)∪(C × D)⊆( A ∪C )×(B∪ D).

Strict in general

Example: let A={1 }, B={1},C={2}, D={2}.

 LHS: ( A × B)∪(C × D)={(1 , 1)}∪ {(2, 2)}={(1 , 1),(2 , 2)}.

 RHS: ( A ∪ C)×(B ∪ D)={1, 2 }× {1 ,2 }={(1 , 1) ,(1 , 2),(2 , 1),(2 , 2)}.

Since {(1 ,1),(2 , 2)}⊊{(1 , 1),(1 , 2),(2 , 1),(2 , 2)}, the inclusion can be strict.

When do we get equality? (optional but handy)

Using ( A ∪C)×(B ∪ D)=(A × B)∪(A × D)∪(C × B)∪(C × D), equality holds iff the “mixed”
pieces are redundant:

A × D ⊆( A × B)∪(C × D)and C × B ⊆( A × B)∪(C × D).

Equivalently,

( A ∖ C)×(D ∖ B)=∅ and (C ∖ A)×(B ∖ D)=∅ ,

i.e.

( A ⊆C or D ⊆B) and (C ⊆ A or B ⊆ D).

(Sufficient special cases: A ⊆ C and B⊆ D ; or C ⊆ A and D ⊆ B ; or A=C ; or B=D .)

2.3 Relations = subsets of products <expand more

  Definition. A relation R from A to Bis any subset R ⊆ A × B. Write xRy for (x , y )∈ R .
Domain: {x ∈ A :∃ y ∈ B ,(x , y) ∈ R }.
Range: { y ∈ B :∃ x ∈ A ,(x , y)∈ R }.

 Identity relation: I A={(a , a):a ∈ A }(the diagonal).

 Counting relations: if ∣ A ∣=m , ∣ B ∣=n, then ∣ A × B ∣=mnand #relations ¿ 2mn(any subset).

From your notes — concrete examples & a domain/range proof:

 Relation on R : R={(x , y): x=∣ y ∣} .

Domain ¿ ¿, Range ¿ R . Full inclusion/exclusion proof appears in your transcript (and I’ve
preserved it). Graphically, this is a sideways “V” opening along the x -axis.

 Relations as digraphs when A is finite: vertices are elements; draw an arrow x → y if xRy . Your
notes include a divisibility-digraph and a specific small digraph with loops and arrows (e.g., 2→6,
2→12, 6→6).

2.4 Equivalence relations & classes (from your notes) <what does it mean>

 Definition. On a set A , a relation ∼is an equivalence relation if it is reflexive, symmetric, and

transitive.
The equivalence class of a is [a]={x ∈ A : x ∼ a} . The set of distinct classes is the quotient
A /∼.

 Examples reproduced from your notes:

o Custom finite example where every element is related to itself and some hand-picked
pairs — checked as R,S,T; quotient classes listed.

o On Z , a ∼b ⟺ a−bis even → two classes: evens, odds.

o Congruence mod 3 on N : three classes [0],[1],[2]. Your digraph view: each class looks
like a complete subgraph with loops.

3) Indexed families of sets (the right way to say “lots of sets”)

3.1 Definition & notation

An indexed family of sets

{ A i }i ∈I

means that for each element iin some index set I , there is a corresponding set Ai .
So, you can think of it like a collection of sets, each one having a label (the index i ) telling you which set
it is.

2. The “labeled shelf” picture

Imagine a bookshelf:

 The shelf labels are the elements of I — maybe I ={1 , 2 ,3 , 4 }or I =N (the natural numbers).

 On each labeled spot i, you place a set Ai .

So:

Label (index) i Set Ai

1 {a, b, c}

2 {b, c, d, e}

3 ∅

4 {x, y}

That’s the family { A i }i ∈{1, 2 ,3 , 4 }.

3. Why it’s called a family (not just a set of sets)

A family is like a list that remembers which index produced which set.
Two different indices can even have the same set value, but they’re still considered different members of
the family because the labels differ.

Example:

A1={1 }, A 2={1}.

Here { A 1 , A2 }(as an unordered set) would just be {{1}},

but the indexed family { A i }i={1 ,2 }still has two entries, because of the distinct indices.

So indexing preserves duplicates and order-like information — it’s like having a “list” of sets rather than
just a “pile” of them.

4. Examples of indexed families

 Finite example:
I ={ 1 , 2, 3 } , A 1= {1 } , A 2={1, 2 }, A3={2 ,3 }.
  Infinite example:
I =N , A n=¿ — an infinite family of intervals.

5. Common operations

Using the index set I , we can define:

¿ i∈ I ❑ Ai (union of all sets in the family)

and

¿ i∈ I ❑ Ai (intersection of all sets in the family) .

For example, if An =¿, then

¿ n=1¿ ∞❑ A n=(0 , 1), ¿ n=1¿ ∞ ❑ A n={0 }.

An indexed family of sets { A i }i ∈I is just a way of organizing (possibly many) sets so that each one has a
clear label i telling you which set it is — like a labeled collection, or a “set-valued function” i↦ A i.

3.2 Big unions & intersections

 ¿ i∈ I ❑ Ai={ x :∃i ∈ I , x ∈ A i }.

 ¿ i∈ I ❑ Ai={ x : ∀ i∈ I , x ∈ Ai }.

 Distribution tips:
X ׿ i❑ A i=¿ i❑(X × Ai );
X ׿ i❑ A i=¿ i❑(X × Ai )(same element-chase you used for two sets).
Common pitfall: Don’t assume ¿ i❑(B i ×C i )=(¿i❑ Bi )×(¿ i❑ Ci ). It needn’t hold; your finite
counterexample scales to indexed families. (Same “cross-pairs appear on RHS” issue.)

3.3 Indexed products (advanced glance)

 For a fixed set X and family {Bi }i∈ I , the “cylinders” X × Bi behave cleanly (see distribution
above).

 For varying coordinates { A i }i ∈I , the direct product ∏ ❑ A iis the set of choice-functions f with
i ∈I

f (i)∈ A i; this generalizes tuples.

4) Induction Principles — statements, templates, and equivalence

We’ll keep the three principles tightly aligned with the style you used in class.

4.1 PMI — Principle of Mathematical Induction (ordinary induction)

Statement (as used in your course).
Let P(n)be a statement about n ∈ N . If

1. P(1)is true; and

2. for some arbitrary k , P(k) ⇒ P(k +1) ,

then P(n)holds for all n ∈ N .

Template (from your notes, exam-ready).

 Base: prove P(1)(or P(n 0)in generalized PMI).

 IH: assume P(k) for some arbitrary k ≥ n0 .

 Step: prove P(k +1) using the IH.

 Conclusion: by PMI, P(n)holds for all n ≥ n0 .

Generalized PMI starts at n 0 ≠ 1(same format).

Classic worked PMI examples (from your notes) <do theses>

n
 ∑ ❑(2i−1)=n2— prove by adding the next odd; you recorded the algebra.
i=1

n
n(n+1)
 ∑ ❑i= 2
— factor the n+1 cleverly; your notes contain the detailed step.
i=1

 Divisibility pattern: a n−b ndivisible by a−b for all n — done via the add/subtract trick; you
captured the algebra neatly.

 De Moivre’s Theorem: ¿— your notes do a clean induction using trig addition formulas.

4.2 PCI — Principle of Complete (Strong) Induction

Statement. If P(n 0)is true and for each m ≥n 0, assuming P(n)for all n 0 ≤ n ≤ mimplies P(m+1), then
all P(n)hold for n ≥ n0.
Mental model: you may use all earlier cases to prove the next.

Template (from your notes).

 Base: prove P(n 0)(and possibly a few initial cases if the recurrence reaches back).

 IH (strong): assume P(n 0), P(n0 +1), … , P(m).

 Step: using all those, prove P(m+1).

 Conclusion: by PCI, all n ≥ n0satisfy P(n).

Worked examples in your notes:

Fibonacci bound: with φ=(1+ √ 5)/2, show F n ≤ φ

n−1
 by PCI (needs two previous cases and the
identity φ 2=φ+1 ). Your notes carry out the details.

 “4s+5t” representation for all n>33 with s ≥ 3 , t ≥2 — your notes do a PCI proof using four base
cases and the m ↦ m−4step so that adding one more 4 preserves the constraints.

4.3 WOP — Well-Ordering Principle (a.k.a. minimal counterexample method)

We are contradicting ourselves. We put this variable, which could be anything, but in this case, it is the
lowest wrong(whatever it may be). then we show that there is a new lower wrong, which contradicts.

We assumed there was a “first wrong case,” then proved that such a case would force an even smaller
wrong one — contradicting the idea of “first.”

Statement. Every nonempty subset of N has a smallest element.

How it’s used: to prove (∀ n) P (n), assume there exists some counterexample, let S={n : P(n) false }
, pick its smallest element n 0, and produce a contradiction (often by pushing down to a smaller
counterexample).

Template (from your notes).

 Assume not; let S={n ∈ N :¬ P (n)}.

 By WOP, n 0=min ⁡Sexists.

 Show from numbers ¿ n0 that P(n 0)must be true → contradiction.

 Therefore S=∅ and (∀ n)P(n).

Canonical examples in your notes:

 Every integer ¿ 1has a prime factor (and hence can be written as a product of primes): assume a
smallest counterexample and factor it — the factors are smaller, so they must have prime
factors; so does n 0; contradiction.

 √ 3is irrational (your WOP/“infinite descent” proof: if √ 3=a/bin lowest terms, 3 divides a , so
write a=3 c and build a smaller element of the set; contradiction).

 Coin-style problem: “every n> 22is 3 ⋅s + 4 ⋅t with s ≥ 3 ,t ≥ 2” — your notes gave a plain-English
WOP sketch and then a formal version.

4.4 The Equivalence Triangle: PMI ⇄ PCI ⇄ WOP

You captured all three directions; here they are, tight and consistent:

(A) PMI ⇒ WOP (by contradiction on the complement)

Assume S ⊆ N is nonempty with no least element. Let T =N ∖ S . Show 1 ∈T , and if 1 , … , n∈ T then

n+1 ∈T (else n+1would be the least of S). By PMI, T =N , contradiction. So every nonempty set has a
least element. (Your notes present this in full.)

(B) WOP ⇒ PMI (smallest counterexample)

If some counterexample to PMI exists, let n 0be the least. Base says P(1)true; the step says
P(n 0−1)⇒ P(n0 ). But by minimality P(n 0−1)is true, so P(n 0)true — contradiction. Therefore PMI
holds. (Your notes present this as the classic “smallest counterexample” kill.)

(C) PMI ⇒ PCI (bundle trick)

Define Q(m)to mean “ P(n) holds for all n ≤ m.” Prove Q(1); then Q(m)⇒ Q(m+1)by applying the
PCI hypothesis inside the bundle. PMI on Q yields PCI for P. (Exactly how you wrote it.)

(D) PCI ⇒ WOP (same complement idea, but strong hypothesis)

Assume nonempty S ⊆ N has no least element. Let T =N ∖ S . Show 1 ∈T . If {1 , … , n }⊆T then also
n+1 ∈T (otherwise n+1would be least in S). By PCI, T =N , contradiction. (You wrote this as a mirror of
the PMI proof.)

Takeaway: the three principles are logically equivalent. Choose whichever matches the structure of the
problem: PMI (one-step), PCI (depends on many earlier steps), WOP (contradiction/minimal
counterexample). Your notes explicitly summarize this “triangle” and its “why it works” blurbs.

5) Worked problems & patterns (curated from your notes)

I’ve grouped your examples by technique and cleaned the logic. Use them as templates.

5.1 PMI templates (with your examples)

n
(i) Sum of odds: ∑ ❑(2i−1)=n .
2

i=1

Add the (2(n+1)−1) term and re-square to get ¿.

n(n+1)
(ii) Sum 1+⋯+n= .
2
(n+1)(n+ 2)
Inductive addition + factoring yields the form.
2
(iii) Divisibility: a n−b ndivisible by a−b .
Use a n+1−b n+1=(a−b)an +b (a n−bn ). The first part has factor a−b , the second is multiple by IH.
(iv) De Moivre:
Multiply ¿by (cos ⁡θ+isin ⁡θ) and apply sum formulas; your notes have the algebra.

5.2 PCI templates (with your examples)

(i) Fibonacci upper bound:

k−1 k−2 k−1 k −2 k
Assume F k ≤ φ and F k−1 ≤ φ ; then F k+1 ≤ φ +φ =φ because φ 2=φ+1 . Your notes include
base cases F 1=F2=1.

(ii) Linear forms with constraints (n=4 s+ 5t , s ≥ 3 ,t ≥ 2for all n>33 ):

Do four base cases (34–37), then if m>37 write m=(m−4)+4 and add one more “4,” preserving s ≥ 3.
Your notes supply the structure and commentary.

5.3 WOP templates (with your examples)

(i) Prime factor existence / product of primes:

Let S={n>1 :no prime factor } . Smallest n 0 ∈ S can’t be prime; if n 0=ab , then a , b< n0so both have
prime factors, hence n 0does — contradiction. (Your notes also give the “smallest counterexample”
version for the full product-of-primes statement.)

(ii) √ 3 ∉Q :
Assume √ 3=a/bin lowest terms; deduce 3 divides a , write a=3 c ; derive a smaller fraction in the same
set; contradict minimality. This mirrors the classic √ 2proof but with 3.

(iii) Coin-change style (≥22 with 3s and 4s, min counts):

Your notes present both the plain-English and formal WOP arguments: establish the first few cases, then
show the minimal failure can’t exist because adding a “3” stays within constraints and lands on an earlier
solvable number.

6) Context, history, and where this matters

 Why sets first? All of discrete math (and CS) formalizes data as sets, functions, and relations;
databases are literally relations (tables). Your notes emphasize relations ↔ digraphs, a staple in
graph algorithms.

 Why induction? It is the proof engine for recurrences, program correctness (loop invariants),
number theory (divisibility, primality), and combinatorics (closed forms). Your Fibonacci, De
Moivre, and divisibility proofs show its breadth.

 Well-ordering/Minimal counterexample often gives the cleanest argument in number theory

(as in the prime factorization sketch and irrationality proofs).

7) Visual organizers you can picture

  Venn-style (sets): draw A , B circles; color A ∩ B, Á , etc.

 Product rectangles: grid with A on x -axis, Bon y -axis; see how A ×(B ∪ C )splits into
rectangles; compare to ( A × B)∪(C × D) to visualize the strict-subset phenomenon your notes
highlight.

 Digraphs (relations on finite sets): nodes are elements; arrows = relation. Equivalence relations
appear as clusters (complete subgraphs with loops), exactly like your “same # of digits” example.

 Induction as dominoes: PMI knocks over the next; PCI lets you “use all prior fallen dominoes”;
WOP forbids an infinite staircase down (there must be a first failure if any exist).

8) Common misconceptions & how to dodge them

 For strong induction: list clearly what you’re allowed to use: “Assume P(n 0), … , P (m) .”

 Base cases for PCI: include enough initial cases to cover the recurrence reach-back (e.g.,
Fibonacci needs two; your “4s+5t” needed four).

 Product parentheses: ( A × B)× C ≠ A ×(B ×C )as sets of tuples (structures differ), even if
there’s a natural bijection.

 Union vs product: ( A × B)∪(C × D)is not typically ( A ∪C)×(B ∪ D); your counterexample
shows why.

 Domain/range extraction: Domain = all first components appearing somewhere in R ; Range =

all second components appearing somewhere in R . See your x=∣ y ∣proof.

9) Expert-level nuances

 Using PMI to prove WOP and vice versa isn’t just trivia — it lets you pick the proof style that
reads best while being logically watertight. Your notes explicitly give all directions.

 Minimal counterexample vs. PCI: These often produce the same core engine; WOP just
packages the contradiction elegantly (e.g., “assume a smallest n 0fails; show a smaller one fails”).

 Inductive definitions (factorial, Fibonacci, recurrences): your notes stress that definitions
themselves can be inductive, not just proofs. Factorial example: 0 ! ⁣= ⁣1, n ! ⁣= ⁣n ⋅(n−1)!. (You
recorded “successor properties” remarks around Peano axioms and why “subtraction” needs
care.)

 Relations↔DB tables↔graphs: Traversals on digraphs are relational queries; equivalence

classes form partitions, a key database normalization idea. Your class notes hint at this
connection.
10) Study-table summaries

10.1 The Induction Equivalence Triangle (at a glance)

Principle Core statement Typical use Your example(s)

P(1)and P(k) ⁣⇒ ⁣P(k+ 1) One-step recurrences, sums, a n−b n, De Moivre

⇒ all n
PMI
algebraic sums

Fibonacci bound; n=4 s+ 5t for

P(n 0)and n>33
PCI Needs many prior cases
{P (n0 ..m)}⇒ P(m+1)

Every nonempty S ⊆ N has prime factorization; √ 3 ∉Q

WOP Minimal counterexample
min

10.2 Relations mini-map

Concept Definition From your notes

Relation
set of ordered pairs counting (2^{
R⊆A ×B

{x :∃ y ,(x , y)∈ R }/
Domain/Range (x=
{ y :∃ x ,(x , y)∈ R }

diagonal line picture

Identity I A {(a , a):a ∈ A }

mod-3 classes, even/odd classes, digit-count classes

Equivalence reflexive, symmetric, transitive (digraph clusters)

11) Quick exam blueprints (verbatim-ready)

PMI (ordinary)

Goal: Prove ∀ n ≥ n0 , P (n).

Base: Verify P(n 0).
IH: Fix some k ≥ n0 and assume P(k) .
Step: Prove P(k +1)using IH.
Conclude: By PMI, P(n)holds for all n ≥ n0.

PCI (strong)

Goal: Prove ∀ n ≥ n0 , P (n).

Base(s): Prove P(n 0), P(n0 +1), … , P(n0 +r )as needed.
IH: Assume P(n 0), … , P (m) .
Step: Prove P(m+1)from all those cases.
Conclude: By PCI, P(n)for all n ≥ n0.

WOP (minimal counterexample)

Goal: Prove ∀ n ∈ N , P(n).

Assume contrary: Let S={n :¬ P(n)}≠ ∅ .
Let n 0=min ⁡S. Use facts about ¿ n0 to force P(n 0).
Contradiction. Hence S=∅ , so P(n)for all n .

We are contradicting ourselves. We put this variable, which could be anything, but in this case, it is the
lowest wrong(whatever it may be). then we show that there is a new lower wrong, which contradicts.

We assumed there was a “first wrong case,” then proved that such a case would force an even smaller
wrong one — contradicting the idea of “first.”

12) Final summary — the big picture in plain terms

 Sets are how we package objects; operations (∪, ∩, ×, …) let us build new sets; relations are just
subsets of products with domain/range and great pictures as digraphs. Equivalence relations
carve a set into neat partitions (equivalence classes). Your notes cover all of this with concrete
examples and pictures.

 Induction comes in three outfits — PMI, PCI, WOP — but they’re equivalent in power. PMI is
“one domino to the next,” PCI lets you lean on all earlier dominoes, and WOP says a “first
failure” can’t exist. Pick the outfit that makes your argument shortest and clearest. Your notes
include the full equivalence proofs and lots of templates.

 Applications: sums and identities (PMI), multi-step recurrences like Fibonacci (PCI), and number-
theoretic “no counterexample exists” arguments (WOP). You’ve already done prime-factorization
style proofs and irrationality with WOP; keep them as mental models.