This is the canonical notation reference for the whole book. If a symbol ever looks unfamiliar, find it
here. The conventions below are used consistently in every chapter.
A standing convention: in this book $\mathbb{N} = \{0, 1, 2, 3, \dots\}$ — the natural numbers
include 0. When a result needs the positive integers only, we write $\mathbb{Z}^{+}$ or say
"$n \ge 1$."
Number systems
Symbol
Meaning
$\mathbb{N}$
Natural numbers $\{0, 1, 2, \dots\}$
$\mathbb{Z}$
Integers $\{\dots, -2, -1, 0, 1, 2, \dots\}$
$\mathbb{Z}^{+}$
Positive integers $\{1, 2, 3, \dots\}$
$\mathbb{Q}$
Rational numbers
$\mathbb{R}$
Real numbers
$\mathbb{Z}_n$
Integers modulo $n$, $\{0, 1, \dots, n-1\}$
Logic (Chapters 1–3)
Symbol
Meaning
Example
$\neg p$
not $p$ (negation)
$\neg \text{True} = \text{False}$
$p \land q$
$p$ and $q$ (conjunction)
true only if both hold
$p \lor q$
$p$ or $q$ (disjunction)
true if either holds
$p \oplus q$
$p$ xor $q$
true if exactly one holds
$p \rightarrow q$
$p$ implies $q$
false only when $p$ true, $q$ false
$p \leftrightarrow q$
$p$ if and only if $q$
true when $p,q$ have the same value
$p \equiv q$
$p$ is logically equivalent to $q$
same truth table
$\forall x\, P(x)$
for all $x$, $P(x)$
universal quantifier
$\exists x\, P(x)$
there exists $x$ with $P(x)$
existential quantifier
$\exists! x\, P(x)$
there exists a unique $x$
$\top,\ \bot$
true, false (tautology, contradiction)
Sets (Chapter 8, used throughout)
Symbol
Meaning
$x \in A$, $x \notin A$
$x$ is (is not) an element of $A$
$A \subseteq B$, $A \subset B$
$A$ is a subset, a proper subset, of $B$
$A \cup B$, $A \cap B$
union, intersection
$A \setminus B$, $\overline{A}$
set difference, complement
$\emptyset$
the empty set
$\mathcal{P}(S)$
power set (set of all subsets) of $S$
$\lvert S \rvert$
cardinality (size) of $S$
$A \times B$
Cartesian product
$\{x \mid P(x)\}$
set-builder: all $x$ such that $P(x)$
Functions and relations (Chapters 9, 12)
Symbol
Meaning
$f \colon A \to B$
$f$ is a function from $A$ to $B$
$g \circ f$
composition ($g$ after $f$)
$f^{-1}$
inverse function
$\lfloor x \rfloor$, $\lceil x \rceil$
floor, ceiling
$a \mathrel{R} b$
$a$ is related to $b$ under relation $R$
$[a]$
equivalence class of $a$
$\preceq$
a partial order
Number theory (Chapters 22–25)
Symbol
Meaning
$a \mid b$, $a \nmid b$
$a$ divides (does not divide) $b$
$\gcd(a,b)$, $\operatorname{lcm}(a,b)$
greatest common divisor, least common multiple
$a \equiv b \pmod{n}$
$a$ is congruent to $b$ modulo $n$
$a \bmod n$
the remainder of $a$ divided by $n$
$\phi(n)$
Euler's totient of $n$
Counting and probability (Chapters 15–21)
Symbol
Meaning
$n!$
$n$ factorial
$P(n,k)$
permutations of $n$ taken $k$ at a time
$\binom{n}{k}$
binomial coefficient ("$n$ choose $k$")
$\sum_{i=1}^{n} a_i$, $\prod_{i=1}^{n} a_i$
sum, product
$P(A)$, $P(A \mid B)$
probability of $A$; of $A$ given $B$
$E[X]$, $\operatorname{Var}(X)$
expected value, variance of $X$
Complexity (Chapter 14, used throughout)
Symbol
Meaning
$O(f)$
grows no faster than $f$ (upper bound)
$\Omega(f)$
grows no slower than $f$ (lower bound)
$\Theta(f)$
grows at the same rate as $f$ (tight bound)
Graphs (Chapters 27–34)
Symbol
Meaning
$G = (V, E)$
a graph with vertex set $V$ and edge set $E$
$\deg(v)$
degree of vertex $v$
$N(v)$
the neighborhood (adjacent vertices) of $v$
$K_n$
complete graph on $n$ vertices
$K_{m,n}$
complete bipartite graph
$\chi(G)$
chromatic number of $G$
Proof
Symbol
Meaning
$\blacksquare$
end of proof (QED)
$\therefore$
therefore
$\Rightarrow$, $\Leftrightarrow$
implies; if and only if (in reasoning)
A note for builders of this book: all mathematics here uses standard LaTeX commands (e.g.,
\mathbb{N}, \mathcal{P}, \gcd, \operatorname{lcm}, \pmod, \binom, \lceil), with $...$
for inline math and $$...$$ for displayed math. No custom macros are used, so the same source renders
identically under Jupyter Book and mdBook.