M5 · Lesson 3 — Mathematical Reasoning

Proof Structures —
Direct, Contradiction,
Induction

Three templates that cover the vast majority
of proofs you'll read and write in RS/ML.

01
M5 · L3 — Overview

The three proof strategies

Same destination,
different routes

Strategy 01

Direct Proof

Start from premises. Apply logic step by step. Arrive at conclusion.

P → Q

Strategy 02

Proof by Contradiction

Assume the conclusion is false. Show this leads to an impossibility.

¬Q → contradiction

Strategy 03

Proof by Induction

Prove for base case. Prove step from n to n+1. Conclude for all n.

P(0) + P(n)→P(n+1)

In RS/ML papers: Direct proofs dominate (loss bounds, gradient derivations). Contradiction appears in impossibility results. Induction appears in graph propagation convergence proofs.

02
M5 · L3 — Direct Proof

Strategy 1

Direct Proof

Direct Proof

The most common proof in ML. Start with what you know, manipulate until you reach what you want to show.

When to use: When there's a clear algebraic or logical path from premises to conclusion.

Template: "Let [variables]. By assumption, [premise]. Then [manipulation]. Therefore [conclusion]. □"

Example · Regularised loss is non-negative
1.
Let ℒ = ‖y − ŷ‖² + λ‖θ‖² where λ > 0.
2.
‖y − ŷ‖² ≥ 0 for all y, ŷ (squared norm).
3.
λ‖θ‖² ≥ 0 since λ > 0 and ‖θ‖² ≥ 0.
4.
Sum of non-negative terms is non-negative.
5.
Therefore ℒ ≥ 0. □
■
03
M5 · L3 — Proof by Contradiction

Strategy 2

Proof by Contradiction

Contradiction

Assume the opposite of what you want to prove. Show this assumption leads somewhere impossible.

Assume ¬Q
→
Logical steps
→
Contradiction!
→
Therefore Q ✓

Signal words in papers: "Suppose for contradiction...", "Assume to the contrary...", "This contradicts our assumption..."

Example · BPR optimal solution uniqueness (sketch)
1.
Suppose for contradiction that two distinct optima θ* and θ** exist.
2.
Since the BPR objective with L2 regularisation is strictly convex in each block, any convex combination αθ* + (1−α)θ** achieves strictly lower loss.
3.
This contradicts θ* and θ** being optima.
4.
Therefore the optimum is unique. □
■
04
M5 · L3 — Proof by Induction

Strategy 3

Proof by Induction

Induction

Prove a statement holds for all n by proving two things:

Base case

Prove P(0) or P(1). The starting point.

Inductive step

Assume P(n) holds. Prove P(n+1) follows. This is the key step.

Conclusion

By induction, P(n) holds for all n ≥ 0 (or 1).

RS Example · LightGCN layer accumulation
P(l):
After l layers, e_u^{(l)} incorporates information from exactly l-hop neighbours.
Base:
l=0: e_u^{(0)} = initial embedding. Only 0-hop (self). ✓
Step:
Assume P(l). Layer l+1 aggregates from direct neighbours of l-hop nodes → reaches l+1 hops. ✓
∴
By induction, e_u^{(L)} captures L-hop neighbourhood. □
■
05
M5 · L3 — Choosing a Strategy

Practical decision guide

Which proof strategy
to use when

  • Direct when: there's a clear algebraic path. You can manipulate equations step by step. Most loss function properties.
  • Contradiction when: proving impossibility or uniqueness. "There is no..." or "At most one..." statements.
  • Induction when: the result involves layers, steps, or iterations. Graph propagation, recurrence relations, iterative algorithms.
"If you're stuck, try contradiction. Assuming the opposite often reveals structure that's invisible from the forward direction."

In RS/ML, 80% of proofs are direct. Learn that first. Contradiction is your second tool. Induction is for layer-wise arguments.

06
M5 · L3 — Key Takeaways

What to remember

Direct

P → Q

Start from premises, manipulate to conclusion. The default strategy. Used for most algebraic results.

Contradiction

¬Q → impossible

Assume the opposite. Derive something that can't be true. Conclude the original claim must hold.

Induction

P(0) + step → all n

Base case plus inductive step. Used for layer-wise, iterative, or recursive RS arguments.

Next: M5 · L4 — Common Proof Techniques in RS/ML

07
← → arrow keys to navigate
1 / 7