1 Notation: sets, functions, and relations

A set is a collection of distinct objects, its elements; one writes $x\in A$ for membership and $x\notin A$ for its negation. A set may be given by listing, $\{a,b,c\}$, or by set-builder notation $\{x\in A:P(x)\}$ (“the $x$ in $A$ such that $P(x)$”). One writes $A\subseteq B$ when every element of $A$ lies in $B$, and $A=B$ exactly when $A\subseteq B$ and $B\subseteq A$ — so proving two sets equal means proving two inclusions. The usual operations are union $A\cup B$, intersection $A\cap B$, difference $A\setminus B$, and the empty set $\mathrm{\varnothing }$. The Cartesian product is $A\times B=\{(a,b):a\in A,b\in B\}$, and $A^n$ is the set of $n$-tuples over $A$. For a finite set $A$, $|A|$ denotes its number of elements. The standard number systems are the naturals $\mathbb{N}$, the integers $\mathbb{Z}$, the rationals $\mathbb{Q}$, the reals $ℝ$, and the complex numbers $ℂ$, with $\mathbb{N}\subset \mathbb{Z}\subset \mathbb{Q}\subset ℝ\subset ℂ$; we construct the underlying arithmetic of the prime field ${𝔽}_p$ in §2, certify it as a field—and first call it ${𝔽}_p$—in §4, and treat general finite fields ${𝔽}_q$ in §6.

A function $f:A\to B$ assigns to each $a\in A$ a unique value $f(a)\in B$; $A$ is the domain and $B$ the codomain. It is injective (one-to-one) if $f(a)=f(a^{\prime })$ implies $a=a^{\prime }$; surjective (onto) if every $b\in B$ equals $f(a)$ for some $a\in A$; and bijective if both. The composition of $f:A\to B$ and $g:B\to C$ is $(g\circ f)(a)=g(f(a))$; composition is associative, $h\circ (g\circ f)=(h\circ g)\circ f$, both sides sending $a$ to $h(g(f(a)))$. The identity on $A$ is ${\mathrm{id}}_A:A\to A$, ${\mathrm{id}}_A(a)=a$.

For $S\subseteq A$ the image is $f(S)=\{f(a):a\in S\}$, and for $T\subseteq B$ the preimage is $f^{-1}(T)=\{a\in A:f(a)\in T\}$, defined whether or not $f$ is invertible. The overloading of $f^{-1}$ is harmless: when the inverse function exists, the preimage of $T$ under $f$ is exactly the image of $T$ under $f^{-1}$.

A binary relation on $A$ is a subset $R\subseteq A\times A$; one writes $a\sim b$ for $(a,b)\in R$. It is an equivalence relation if it is reflexive ($a\sim a$), symmetric ($a\sim b\Rightarrow b\sim a$), and transitive ($a\sim b$ and $b\sim c$ imply $a\sim c$). The equivalence class of $a$ is $[a]=\{x\in A:x\sim a\}$, and the set of distinct classes is the quotient $A/\sim$.

We use this construction twice in the present volume: to form the integers modulo $n$ (§2) and the cosets of a subgroup (§3).

A second kind of relation orders rather than identifies. A partial order on $A$ is a relation $⪯$ that is reflexive, transitive, and antisymmetric: $a⪯b$ and $b⪯a$ imply $a=b$. Four partial orders recur in the series: the usual $\le$ on $\mathbb{Z}$; inclusion $\subseteq$ on the subsets of a fixed set, whose antisymmetry is the two-inclusions rule of §1.1; divisibility $\mid$ on $\mathbb{N}$ (§2.2); and the prefix relation on finite sequences, under which a sequence precedes every sequence that extends it. Two elements are comparable if $a⪯b$ or $b⪯a$, and a partial order under which every two elements are comparable is a total (or linear) order. The order $\le$ on $\mathbb{Z}$ is total; the other three are not: $\{1\}$ and $\{2\}$ are incomparable under inclusion, as are $2$ and $3$ under divisibility and the one-term sequences $(1)$ and $(2)$ under prefix.

Every partial order has a strict companion, $a\prec b$ meaning $a⪯b$ and $a\ne b$; the two determine each other.

A strict order $\prec$ is a strict total order when its non-strict companion is total, equivalently when for all $a,b$ exactly one of $a\prec b$, $a=b$, $b\prec a$ holds (trichotomy): at least one holds by totality, and any two together would give $a\prec a$, by substitution or by transitivity. The usual on $\mathbb{Z}$ is the model. A function $f:A\to B$ between ordered sets is monotone (order-preserving) if $a⪯a^{\prime }$ implies $f(a)⪯f(a^{\prime })$, and strictly increasing if $a\prec a^{\prime }$ implies $f(a)\prec f(a^{\prime })$. The one further property of an order that the volume assumes, the well-ordering of $\le$ on $\mathbb{N}$, opens §2.1.

We employ the symbols $\forall$ (“for all”), $\exists$ (“there exists”), $\exists !$ (“there exists a unique”), and “$:$” or “s.t.” for “such that”. Negation swaps the quantifiers: $\neg (\forall xP(x))$ is $\exists x\neg P(x)$, and $\neg (\exists xP(x))$ is $\forall x\neg P(x)$. The order of unlike quantifiers matters: $\forall x\exists yP(x,y)$ (the $y$ may depend on $x$) is weaker than $\exists y\forall xP(x,y)$ (one $y$ works for all $x$).

The following conventions are fixed for the entire series. We prove an implication $P\Rightarrow Q$ directly (assume $P$, derive $Q$), by contraposition (assume $\neg Q$, derive $\neg P$), or by contradiction; we prove a statement $\forall xP(x)$ by taking an arbitrary $x$, and $\exists xP(x)$ by exhibiting a witness. We prove statements about all natural numbers by induction.

The debt incurred at the opening of this section falls due here. The series draws on three alphabets: blackboard-bold letters for the standard number systems and structures, Greek letters, and a handful of relational and operator symbols. Tables 1–3 collect these symbols and the complete Greek alphabet, with common English pronunciations, spelled approximately for reading mathematics aloud. These vary between speakers and regions; the alternatives shown are not exhaustive. A capitalised syllable carries the stress, and a slash separates alternatives. These are English letter names, not a guide to pronouncing Greek words. Each symbol is defined where it is first used; the notes here are reminders, not definitions.