Proof Techniques: Direct, Contrapositive, Contradiction and Induction: every key term you need (+ practice quiz)
25 flashcard terms for Discrete Mathematics Topic 2, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
A mathematical statement that has been proved true from axioms, definitions and previously established results. Lesser results used along the way are called lemmas, and easy consequences are called corollaries.
Axiom
A statement accepted without proof that serves as a starting point for a mathematical system. Different axiom choices produce different theories, so every proof is relative to its axioms.
Lemma
A minor result proved chiefly because it is needed as a step in the proof of a larger theorem. Some lemmas, such as the pumping lemma, become more famous than the theorems they served.
Corollary
A statement that follows from a theorem with little or no additional argument, usually by specialising the theorem or applying it to one particular case.
Conjecture
A statement believed to be true, often supported by many examples or computation, but not yet proved. Verified examples never suffice, since a universal claim can fail beyond the range checked.
Direct proof
A proof of if p then q that assumes p, then derives q through a chain of definitions and known results. It is the default technique and should be tried before any indirect method.
Proof by contraposition
A proof of if p then q carried out by assuming not q and deriving not p. It is valid because a conditional and its contrapositive are logically equivalent, and it often turns an awkward hypothesis into a usable one.
Proof by contradiction
A proof that assumes the negation of the desired statement and derives a logical impossibility, forcing the assumption to be false. It is also called reductio ad absurdum.
Vacuous proof
A proof of if p then q that simply shows the hypothesis p can never hold, which makes the conditional true without any examination of the conclusion.
Trivial proof
A proof of if p then q that establishes the conclusion q outright, independent of the hypothesis, so the conditional holds regardless of whether p is true.
Proof by cases
A proof that splits the hypothesis into finitely many exhaustive situations and argues each separately. It is only complete when the cases genuinely cover every possibility.
Without loss of generality
A phrase justifying restriction to one representative case when symmetry means the remaining cases follow by relabelling. It is valid only when that symmetry is real and stated.
Existence proof
An argument establishing that an object with a given property exists. A constructive version exhibits the object, while a nonconstructive one shows existence without producing an example.
Uniqueness proof
An argument that at most one object satisfies a property, usually by supposing two such objects exist and showing they must be equal. Combined with existence it gives exactly one.
Mathematical induction
A technique for proving a statement for all integers from a starting point onward, by proving a base case and proving that truth at an arbitrary value forces truth at the next value.
Base case
The smallest instance of an induction, verified directly. Omitting it invalidates the whole argument, since an inductive step alone can propagate a claim that was never true anywhere.
Inductive hypothesis
The assumption that the statement holds at a particular value, used inside the inductive step to derive the statement at the next value. It is an assumption about one case, not the whole claim.
Inductive step
The part of an induction proving that if the statement holds at an arbitrary value then it holds at the following value, which chains the base case forward through all remaining integers.
Strong induction
A variant whose inductive step may assume the statement for all values below the current one, not just the immediately preceding one. It suits problems where a number splits into smaller unequal parts.
Structural induction
Induction over recursively defined objects such as strings, lists or trees, proving the claim for the base constructors and then for each rule that builds larger objects from smaller ones.
Well ordering principle
The statement that every nonempty set of nonnegative integers contains a least element. It is logically equivalent to induction and underlies minimal counterexample arguments.
Minimal counterexample
A proof strategy that assumes a claim fails, uses well ordering to pick the smallest failing case, then derives a smaller failing case, contradicting minimality.
Parity argument
A proof that uses whether quantities are even or odd, often to show that a configuration is impossible because an invariant parity would have to change.
Irrationality of the square root of two
A classical proof by contradiction: assume the root equals a fraction in lowest terms, deduce both numerator and denominator are even, and contradict the assumption that the fraction was reduced.
Common induction errors
Typical failures include skipping the base case, assuming the full statement rather than one instance, and applying the inductive step at a value where the derivation silently needs an extra element.