Proofs

Core proof techniques and proof-writing habits for research-facing math in CS, AI, and engineering.

Keywords

proofs, proofwriting, contradiction, induction, counterexample

1 Why This Module Matters

Proof writing is the point where math stops being a pile of techniques and starts becoming a language.

If you want to read theory-heavy papers well, this module is not optional. It is where you learn how to parse assumptions, choose a proof method, and tell the difference between a proof idea that feels plausible and an argument that is actually rigorous.

This module is also unusually transferable. The same habits that help in beginner proof exercises help later in analysis, optimization, probability, learning theory, and research writing.

Prerequisites Algebra fluency, notation comfort, and patience

Unlocks Logic, discrete math, analysis, learning theory

Research Use Theorem reading, assumption tracking, proof debugging, paper writing

2 First Pass Through This Module

1. Statements and Quantifiers
2. Direct Proof
3. Contrapositive and Contradiction
4. Induction
5. Counterexamples and Proof Debugging
6. Proof-writing Clinic

On a first pass, these six pages are the whole story. You should be able to stop at the concept pages and still get a complete beginner-to-usable proof foundation.

3 Navigation Rule

Use the module overview and core concept pages as the main first-pass route.

Each page should be a first-pass finish line for its own topic. Companion pages, when they exist, should feel optional rather than required to understand the main flow.

4 Core Concepts

• Statements and Quantifiers: teaches the logical grammar of theorem statements and negation.
• Direct Proof: teaches the default forward proof pattern from assumptions to conclusion.
• Contrapositive and Contradiction: teaches the main indirect methods and when to use them.
• Induction: teaches how to prove infinitely many cases with a base case and propagation step.
• Counterexamples and Proof Debugging: teaches how to test false theorems and locate broken proof steps.
• Proof-writing Clinic: turns all of the above into a practical revision workflow.

5 Proof Patterns In This Module

• Parse before proving: theorem structure matters before proof strategy.
• Choose the right direction: direct, indirect, and inductive proofs each have natural use cases.
• Debug by first failure: when a proof draft is wrong, find the earliest unjustified step.
• Revise for verifiability: good proofwriting makes correctness easier to check.

6 Applications

6.1 Reading Theory Papers

These pages teach you how to slow down enough to read assumptions, quantify what is actually being claimed, and spot when a theorem is being applied outside its scope.

6.2 Writing Correct Arguments

Whether you are proving an invariant, checking a recurrence, justifying an estimator property, or writing a theorem section in a paper, the same proof habits keep the argument readable and trustworthy.

7 Go Deeper By Topic

7.1 Indirect Proof

Start with Contrapositive and Contradiction.

If that page still feels slippery, revisit:

• Statements and Quantifiers for negation practice
• Direct Proof to compare forward and indirect setups

7.2 Proof Revision

Start with Counterexamples and Proof Debugging, then finish with Proof-writing Clinic.

That pair is the best bridge from “I know proof methods” to “I can diagnose and improve a real proof draft.”

8 Optional Deep Dives After First Pass

Until the proofs module grows companion pages, the best deeper pass is through official proofwriting references:

• Stanford CS103 Proofwriting Checklist - watch how proof structure and sentence structure are treated as part of correctness. Checked 2026-04-24.
• CMU OLI Logic & Proofs - use it as a repetition-and-feedback layer after reading the concept pages. Checked 2026-04-24.

9 Study Order

The intended order is exactly the six-page spine above.

The first three pages teach:

• how to read a theorem
• how to prove something directly
• how to switch to indirect reasoning when needed

The next three pages teach:

• how to reason recursively through induction
• how to disprove and debug
• how to revise a proof draft into a clean final version

You are ready to leave this module when you can:

• parse a theorem without losing its quantifiers
• pick a reasonable proof method
• identify the first broken line in a weak proof
• revise a short proof into something another reader can verify

10 Sources and Further Reading

• Stanford CS103 Guide to Proofs - First pass - one of the best official proof guides for beginners in CS-flavored math. Checked 2026-04-24.
• Stanford CS103 Proofwriting Checklist - First pass - excellent official proof revision checklist. Checked 2026-04-24.
• CMU OLI Logic & Proofs - Second pass - strong official interactive course for repeated logic and proof practice. Checked 2026-04-24.
• MIT Mathematics for Computer Science: What is a Proof? - Second pass - official MIT notes emphasizing proof structure and clarity. Checked 2026-04-24.
• MIT 6.042 PSet Submission and Guidelines - Paper bridge - concise official statement of what readable proof structure looks like in practice. Checked 2026-04-24.

Sources checked online on 2026-04-24:

• Stanford CS103 Guide to Proofs
• Stanford CS103 Proofwriting Checklist
• CMU OLI Logic & Proofs
• MIT proof notes
• MIT proof guidelines