Search & glossary

Every rule and concept in Proof Writing & Problem Solving, with its definition and a link to the lesson that teaches it. Search by term, by idea, or by lesson title.

Glossary (38)

"For all" and "there exists": A universal claim ("for all $x$ , $P(x)$ ") needs a proof that works for an arbitrary $x$ and is refuted by ONE counterexample.; Existence, Uniqueness and Counterexamples › Quantifiers
"If $P$ then $Q$ " equals "if not $Q$ then not $P$ ": The contrapositive of an implication is logically equivalent to it, and often easier to prove directly — especially when the conclusion $Q$ is a "not" statement or when $P$ gives you nothing to compute with.; Contrapositive and Contradiction › Contrapositive
A proof is a chain of implications: A proof is a sequence of statements, each of which is an assumption, a definition, a previously proved fact, or a logical consequence of earlier lines, ending at the claim.; What a Proof Is › Statements and Definitions
A quantity that only moves one way: A monovariant is a quantity that changes in only one direction with every move.; Problem-Solving Strategies › Monovariants and Games
Assume everything below: In strong induction the inductive hypothesis is " $P(j)$ holds for ALL $j$ with $n_0 \le j \le k$ ", and you prove $P(k + 1)$ .; Induction › Strong Induction
Assume the claim is false, derive nonsense: To prove $P$ by contradiction: assume $\neg P$ and deduce something impossible ( $1 = 0$ , a number that is both even and odd, a smaller element of a set that had a smallest element).; Contrapositive and Contradiction › Contradiction
Assume, unpack, compute, conclude: To prove "if $P$ then $Q$ " directly: assume $P$ ; rewrite $P$ using definitions; manipulate until $Q$ appears in the form of its definition; state $Q$ .; Direct Proof › The Shape of a Direct Proof
Base case, inductive step: To prove $P(n)$ for all $n \ge n_0$ : prove $P(n_0)$ (base case); then prove that for every $k \ge n_0$ , $P(k)$ implies $P(k + 1)$ (inductive step).; Induction › Ordinary Induction
Both halves, every time: An induction has two obligations and each fails in its own way.; Induction › Where Inductions Go Wrong
Color the board to count: To show a region cannot be tiled by certain pieces, color it so that every piece, wherever it is placed, covers a fixed pattern of colors.; Problem-Solving Strategies › Coloring Arguments
Converse, inverse, contrapositive: From $P \Rightarrow Q$ come three relatives: the converse $Q \Rightarrow P$ , the inverse $\text{not } P \Rightarrow \text{not } Q$ , and the contrapositive $\text{not } Q \Rightarrow \text{not } P$ .; What a Proof Is › Statements and Implications
Every non-empty set of positive integers has a least element: This is the well-ordering principle.; Pigeonhole and Extremal Arguments › Well-Ordering and Infinite Descent
Find it backwards, write it forwards: Scratch work may start from the conclusion and work toward something known.; Direct Proof › The Shape of a Direct Proof
Find what does not change: When a process or game is described by moves, look for an invariant: a quantity (often a parity, a sum mod $k$ , or a coloring count) that every move preserves.; Problem-Solving Strategies › Invariants and Parity
How to read: Read a proof three times.; What a Proof Is › Reading a Proof
Induct on size: Induction proves statements about sets, boards, polygons and games — anything with a size $n$ .; Induction › Induction Beyond Formulas
Irrational means "not a ratio": To prove a number is irrational, assume it equals $p/q$ with integers $p, q$ , clear the fraction, and derive something impossible about integers — usually a parity clash, a divisibility that cannot hold, or two different prime factorizations of one number.; Contrapositive and Contradiction › Contradiction With Numbers
Know the definitions cold: Even: $n = 2k$ .; What a Proof Is › Statements and Definitions
Lemmas, cases, and "without loss of generality": Split a long proof into a lemma (a smaller claim proved first and then used) and the main argument.; Writing It Up › Structuring a Longer Proof
Linear combinations: If $d \mid a$ and $d \mid b$ , then $d \mid ax + by$ for all integers $x$ and $y$ .; Direct Proof › Divisibility Arguments
Look at the biggest or smallest: Choose the object that is extreme — the largest number, the shortest distance, the player with the most wins — and argue that its extremity forces a property, or that a "more extreme" object would exist otherwise (contradiction).; Pigeonhole and Extremal Arguments › Extremal Arguments
Minimal counterexample: To prove every $n$ has property $P$ : suppose not, and let $n_0$ be the SMALLEST failure (well-ordering).; Contrapositive and Contradiction › Contradiction
More pigeons than holes: If $n + 1$ objects are placed in $n$ boxes, some box holds at least two.; Pigeonhole and Extremal Arguments › The Pigeonhole Principle
One case, chosen well: To refute "for all $x$ , if $P(x)$ then $Q(x)$ ", produce one $x$ with $P(x)$ true and $Q(x)$ false.; Existence, Uniqueness and Counterexamples › Finding Counterexamples
Proof by cases: When the hypothesis splits naturally (even/odd, positive/negative/zero, $n \bmod 3$ ), prove the claim in each case.; Direct Proof › Cases
Proving something exists without pointing at it: A constructive existence proof exhibits the object.; Existence, Uniqueness and Counterexamples › Existence Without Construction
The audit: Before calling a proof finished: (1) Did you use every hypothesis?; Writing It Up › Checking Your Own Proof
The checklist behind every proof: Before writing: state the claim with its quantifiers and unpack every definition.; What a Proof Is › Putting It Together
The final read: Read the finished proof once as its harshest reader: cover each line, ask what the previous lines force, and uncover.; Writing It Up › Putting It Together
The general form: If $N$ objects are placed in $n$ boxes, some box holds at least $\left\lceil \dfrac Nn \right\rceil$ of them.; Pigeonhole and Extremal Arguments › Choosing the Boxes
The reader's rules: Write in full sentences.; Writing It Up › Style Rules
The shape of the inductive step: Write the $k + 1$ case; find the $k$ case inside it (peel off the last term, factor out one power); substitute the inductive hypothesis; finish with algebra.; Induction › Ordinary Induction
Three routes to one theorem: For "if $P$ then $Q$ ": a direct proof assumes $P$ and reaches $Q$ ; a proof by contrapositive assumes not- $Q$ and reaches not- $P$ ; a proof by contradiction assumes $P$ AND not- $Q$ and reaches any impossibility.; Contrapositive and Contradiction › Choosing a Method
Two halves each: To prove uniqueness: suppose $x$ and $y$ both have the property, and show $x = y$ .; Existence, Uniqueness and Counterexamples › Uniqueness and "If and Only If"
Understand, plan, execute, look back: Understand: restate the problem in your own words; identify the unknown, the data, the condition; draw a figure; try small cases.; Problem-Solving Strategies › Pólya's Four Steps
What "if $P$ then $Q$ " promises: A statement is a sentence that is either true or false.; What a Proof Is › Statements and Implications
Wishful thinking: Ask: "what would make this easy?" If the numbers were smaller, if the shape were symmetric, if one variable were zero — then solve THAT and see whether the solution survives being un-wished.; Problem-Solving Strategies › Pólya's Four Steps
Words that do work: "Suppose", "let", "since", "therefore", "it follows that", "in particular", "conversely", "without loss of generality" (say why), "by the inductive hypothesis".; Writing It Up › Style Rules