Proof Techniques glossary
Clear, one-line definitions of the Proof Techniques terms used across the OgbonLab textbooks. Each entry links to the interactive sections where the idea is taught.
27 terms
- bernoulli inequality
- (1 + x)^n ≥ 1 + nx for x ≥ -1 and integer n ≥ 0; provable by induction on n.
- case analysis
- A proof technique that splits the hypothesis into exhaustive cases and proves the conclusion separately in each.
- circular chain
- A proof of multiple equivalences via a cycle of implications, e.g., P₁ ⇒ P₂ ⇒ P₃ ⇒ P₁ to show all three are mutually equivalent.
- conclusion
- The statement an argument aims to derive from its premises.
- constructive proof
- A proof that establishes existence by explicitly exhibiting (constructing) a specific witness.
- contradiction
- A statement of the form P and ¬P, false in every world; deriving one from an assumption refutes the assumption.
- counterexample
- A specific instance that refutes a universal claim ∀x, P(x); finding one disproves the claim.
- deductive argument
- An argument whose conclusion necessarily follows from its premises when the premises are true.
- direct proof
- A proof that assumes the hypothesis P and derives the conclusion Q through a chain of valid implications.
- exhaustive
- A set of cases is exhaustive when every possibility falls into at least one case; required for case-analysis proofs to be valid.
- given
- A premise or assumption available at the start of a proof; what you have to work with.
- goal
- The statement to be proved at any point in a proof; the goal transforms as the proof progresses.
- godel numbering
- An injective assignment of natural numbers to the formulas of a formal language, enabling self-reference and the incompleteness theorems.
- inductive hypothesis
- The assumption that P(k) holds, used to prove P(k+1) in the inductive step of a proof by induction.
- mathematical induction
- A proof technique establishing ∀n ∈ ℕ, P(n) by proving (1) a base case P(0) or P(1), and (2) an inductive step P(k) ⇒ P(k+1).
- See: Proof by Mathematical Induction, The Principle of Mathematical Induction
- non-constructive proof
- A proof of existence that does not exhibit a specific witness, such as proof by contradiction or pigeonhole.
- premise
- A statement assumed true in an argument; together with other premises it derives the conclusion.
- proof by cases
- Synonymous with case analysis: split the situation into exhaustive cases and prove the conclusion in each.
- proof by contradiction
- Assume ¬(goal), derive a contradiction, and conclude the goal must be true.
- recursion
- Defining a function or sequence in terms of its values on smaller inputs, with a base case to anchor the recursion.
- See: Recursion
- restricted domain
- A function obtained from f: A → B by restricting to a subset S ⊆ A, written f|_S: S → B.
- See: Bounded Quantifiers and Restricted Domains
- strong induction
- A variant of induction whose inductive step assumes P(j) for ALL j ≤ k, not just P(k); equivalent to ordinary induction.
- See: Strong Induction
- vacuous truth
- A conditional P ⇒ Q is vacuously true whenever P is false, regardless of Q.
- valid argument
- An argument whose conclusion must be true whenever all premises are true; valid is about form, not content truth.
- well-defined
- A definition or function is well-defined when its result does not depend on the choice of representative used.
- well-ordering principle
- Every nonempty subset of the natural numbers has a smallest element; equivalent to mathematical induction.
- witness
- An explicit element that satisfies an existential claim ∃x, P(x); naming a witness proves the existential.