Glossary.

Absolute value

$|x| = x$ if $x \ge 0$, and $|x| = -x$ if $x < 0$.

Arbitrary element

An element you assume nothing about except what is given. It stands for every element at once.

Base case

The first case of an induction, usually $n = 1$. It starts the chain.

Bézout’s identity

If $\gcd(a, b) = d$, then $a\cdot x + b\cdot y = d$ for some integers $x$, $y$.

Big-O

$f(n) = O(g(n))$ means $f(n) \le c\cdot g(n)$ for all $n \ge N$, for some constants $c$, $N$.

Bijective

Both injective and surjective. A bijection has an inverse function.

Cases

Splitting a claim into possibilities that together cover everything, then proving each one.

Combination

A choice of $k$ objects from $n$ where order does not matter. $\binom{n}{k} = n!/(k!(n-k)!)$.

Complement

$x \in A^{c}$ means $x \notin A$.

Composition

$(g \circ f)(x) = g(f(x))$. Apply $f$ first, then $g$.

Conclusion

The “then” part of an implication, the thing you want to show.

Congruence

$a \equiv b \pmod{n}$ means $n \mid (a - b)$.

Contradiction

A statement and its negation holding together, which is impossible. In a proof by contradiction you assume the opposite of the claim and derive one.

Contrapositive

The contrapositive of $P \Rightarrow Q$ says exactly the same thing. Proving one proves the other.

Converse

The converse of $P \Rightarrow Q$ swaps the two parts. It can be false when the original is true.

Counterexample

One case that makes a “for all” claim false.

$n = 1$ disproves “$n^2 > n$ for every integer $n$”.

De Morgan’s laws

$\lnot (P \land Q) \equiv \lnot P \lor \lnot Q$ and $\lnot (P \lor Q) \equiv \lnot P \land \lnot Q$. Negating “and” gives “or”, and the other way round.

Degree

The degree of a vertex is the number of edges that meet it.

Direct proof

Assume $P$. Deduce, step by step. Arrive at $Q$.

Divides

$a \mid b$ means $b = a\cdot k$ for some integer $k$.

Division algorithm

For integers $a$ and $b > 0$ there are unique integers $q$, $r$ with $a = b\cdot q + r$ and $0 \le r < b$.

Double inclusion

To prove $A = B$, prove $A \subseteq B$ and $B \subseteq A$.

Equivalence class

The set of all elements related to $a$. The classes of an equivalence relation partition the set.

Equivalence relation

A relation that is reflexive, symmetric and transitive.

Equivalent statements

Two statements with the same truth value in every row of a truth table.

Even integer

An integer $n$ is even if $n = 2k$ for some integer $k$.

Greatest common divisor

The largest integer that divides both $a$ and $b$. Euclid’s algorithm computes it with repeated division.

Hypothesis

The “if” part of an implication, the thing you assume.

If and only if

$P \Rightarrow Q$ and $Q \Rightarrow P$ together. Prove it by proving both directions.

Implication

“If $P$ then $Q$”. It is false only when $P$ is true and $Q$ is false.

If $n$ is even, then $n + 2$ is even.

Induction

Prove a base case, then prove that if the claim holds for $k$ it holds for $k + 1$. Then it holds for every $n$ from the base case on.

Inductive hypothesis

In the inductive step, the assumption that the claim holds for $k$.

Injective

A function $f$ is injective if $f(a) = f(b)$ implies $a = b$. Different inputs give different outputs.

Intersection

The elements that are in both A and B.

Limit of a sequence

For every $ε > 0$ there is $N$ such that $|a(n) - L| < ε$ for all $n \ge N$.

Loop invariant

A statement that is true before a loop and after every iteration. Prove initialization, maintenance and termination.

Negating quantifiers

$\lnot \forall x P(x) \equiv \exists x \lnot P(x)$ and $\lnot \exists x P(x) \equiv \forall x \lnot P(x)$. Flip each quantifier and negate what remains.

Negation of an implication

$\lnot (P \Rightarrow Q) \equiv P \land \lnot Q$. An implication fails exactly when the hypothesis holds and the conclusion does not.

Odd integer

An integer $n$ is odd if $n = 2k + 1$ for some integer $k$.

Omega and Theta

$f = Ω(g)$ is a lower bound, and $f = Θ(g)$ means both $O(g)$ and $Ω(g)$ hold.

Pigeonhole principle

If more than $n$ objects go into $n$ boxes, some box holds at least two.

Power set

The set of all subsets of $A$. If $A$ has $n$ elements, $P(A)$ has $2^n$.

Prime

An integer $p > 1$ whose only positive divisors are $1$ and $p$.

QED

Marks the end of a proof. From the Latin for “which was to be shown”.

Quantifier

$\forall$ means “for all”. $\exists$ means “there exists”.

Reflexive

A relation R is reflexive if $a R a$ for every $a$.

Set equality

$A = B$ means $A \subseteq B$ and $B \subseteq A$.

Statement

A sentence that is definitely true or definitely false, never both.

“$7$ is an even number” is a statement. It is false.

Strong induction

Assume $P(1)$, $\ldots$, $P(k)$ are all true, and prove $P(k + 1)$.

Structural induction

Induction that follows the recursive definition of an object: prove the base case, then that building bigger objects keeps the property.

Subset

Every element of A is an element of B.

Surjective

A function $f$: $A \to B$ is surjective if every $b \in B$ equals $f(a)$ for some $a \in A$.

Symmetric

A relation R is symmetric if $a R b$ implies $b R a$.

Theorem

A statement that has been proved.

Transitive

A relation R is transitive if $a R b$ and $b R c$ imply $a R c$.

Tree

A connected graph with no cycles. A tree with $n$ vertices has $n - 1$ edges.

Triangle inequality

$|x + y| \le |x| + |y|$ for all real $x$, $y$.

Truth table

A table listing the truth value of a compound statement for every combination of truth values of its parts. With $n$ statements there are $2^n$ rows.

Uniqueness

“There exists exactly one.” Prove existence by example, and uniqueness by assuming two examples are equal.

Vacuous truth

An implication whose hypothesis is false is true, whatever the conclusion says.

If $2 = 3$, then the moon is cheese.