These are notes for the Cambridge Part IA course *Numbers and [Sets](/page/Set)*, the first pure mathematics course in the Cambridge Mathematical Tripos. The course is not primarily about learning new mathematical content — much of the material (primes, divisibility, basic set theory) may be familiar from secondary school or mathematical competitions. Instead, the course is about learning *how mathematics is done*: how to construct rigorous arguments from precisely stated axioms, how to present proofs clearly, and how to recognise when an argument has gaps. The approach is axiomatic. We begin with a small number of assumptions — the Peano axioms for $\mathbb{N}$, the ordered field axioms for $\mathbb{R}$ — and derive everything else as a logical consequence. Nothing is handwaved. Every step must be justified, every object must be defined before it is used, and every theorem must be proved before it is applied. This is a significant shift from the way mathematics is typically taught before university, and the main skill the course aims to develop. The content spans five chapters. We begin with **Proofs and Logic**, which introduces the language of mathematical reasoning: proof techniques (direct proof, contrapositive, contradiction), propositional connectives, quantifiers, and the systematic negation of complex statements. **Elementary Number Theory** then provides a rich proving ground for these techniques, developing divisibility, primes, the Euclidean algorithm, modular arithmetic, and the Fundamental Theorem of Arithmetic — with an application to RSA cryptography. **The Reals** shifts to analysis, introducing $\mathbb{R}$ axiomatically and exploring the consequences of the least upper bound axiom: the Archimedean property, density of the rationals and irrationals, convergence of [sequences](/page/Sequence) and [series](/page/Series), decimal expansions, and the irrationality of $e$. **Sets, [Functions](/page/Function) and Relations** builds the foundational language of mathematics — set operations, functions (injections, surjections, bijections), equivalence relations and quotients, and the combinatorics of finite sets (binomial coefficients, inclusion-exclusion). Finally, **Countability** asks how to compare the sizes of infinite sets, proving that $\mathbb{Q}$ is countable while $\mathbb{R}$ is not, and culminating in Cantor's theorem and the Schröder-Bernstein theorem. The chapters build on each other in essential ways. Induction and the well-ordering principle from Chapter 1–2 are used throughout. The Fundamental Theorem of Arithmetic (Chapter 2) appears in the countability proofs (Chapter 5). The Fermat-Euler theorem (Chapter 2) is needed to characterise periodic decimals (Chapter 3). The language of sets and functions (Chapter 4) underpins the entire discussion of countability (Chapter 5). The course is best read in order. # Proofs and Logic Mathematics, unlike the experimental sciences, deals in certainty. A physicist may accumulate evidence for a theory over decades, only to see it overturned — Newtonian mechanics stood for centuries before general relativity revealed it as an approximation. In mathematics, once a statement is proved, it is settled: the conclusion follows inescapably from the hypotheses and axioms. This chapter introduces the language and techniques of proof — the machinery that makes mathematical certainty possible. The goal is not to learn new mathematical content, but to learn how mathematical arguments are constructed and presented. We begin with the informal idea of proof, see it in action through small examples, then develop the formal language of propositional logic and quantifiers that allows us to state and manipulate mathematical assertions with precision. ## What is a Proof? Before formalising anything, we need a working understanding of what a proof actually does. In secondary school, many results are presented as facts to be memorised — for instance, that every natural number has a unique prime factorisation. In rigorous mathematics, nothing is accepted without justification. Every claim must be derived, step by step, from previously established results and axioms. [definition:Proof] A **proof** is a finite sequence of statements, each of which is either an axiom, a previously established result, or follows from earlier statements in the sequence by a valid logical rule, such that the final statement is the desired conclusion. [/definition] This definition is deliberately informal — a fully formal treatment of proof theory belongs to mathematical logic. For our purposes, a proof is a chain of reasoning with no gaps: every step must be justified, and the reader should be able to verify each transition independently. ### Direct Proof The most straightforward proof technique is *direct proof*: assume the hypotheses, then derive the conclusion through a sequence of logical deductions. The following example illustrates the method. [example:Divisibility Of Consecutive Product] **Claim.** For all $n \in \mathbb{N}$, the expression $n^3 - n$ is a multiple of $3$. We factor algebraically: \begin{align*} n^3 - n = n(n^2 - 1) = n(n-1)(n+1) = (n-1) \cdot n \cdot (n+1). \end{align*} The right-hand side is a product of three consecutive integers. Among any three consecutive integers, exactly one is divisible by $3$ (since the residues modulo $3$ cycle through $0, 1, 2$). Therefore $3$ divides the product $(n-1) \cdot n \cdot (n+1) = n^3 - n$. [/example] The proof above is direct: we started with $n^3 - n$, rearranged it into a form where the conclusion is transparent, and invoked a general fact about consecutive integers. No assumption about the conclusion was needed. ### Proof by Contrapositive Sometimes the direct approach is awkward, and it is easier to prove the *contrapositive*. The statement "if $A$ then $B$" is logically equivalent to "if not $B$ then not $A$." Proving the contrapositive is therefore just as valid as proving the original implication. [example:Even Square Implies Even] **Claim.** For any $n \in \mathbb{N}$, if $n^2$ is even, then $n$ is even. A direct proof would require working from "$n^2$ is even" to "$n$ is even," which is not immediately obvious. Instead, we prove the contrapositive: if $n$ is *not* even (i.e. $n$ is odd), then $n^2$ is not even. Suppose $n$ is odd. Then $n = 2k + 1$ for some integer $k$, and \begin{align*} n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, \end{align*} which is odd. Hence $n^2$ is not even, establishing the contrapositive. [/example] ### Proof by Contradiction A third fundamental technique is *proof by contradiction* (also called *reductio ad absurdum*): to prove a statement $P$, assume $\neg P$ and derive a logical impossibility. Since the axioms and rules of inference are consistent, the assumption $\neg P$ must be false, so $P$ holds. This technique is especially powerful when the statement asserts nonexistence or uniqueness. We will see it deployed repeatedly in later chapters — for instance, to prove the irrationality of $\sqrt{2}$, the infinitude of primes, and the uncountability of $\mathbb{R}$. ## Propositional Logic To manipulate mathematical statements efficiently, we need a compact notation for combining assertions. English phrases like "A and B," "A or B," and "not A" are adequate for informal reasoning, but they carry ambiguities (does "or" mean inclusive or exclusive?) that formal notation resolves. [definition:Conjunction] Let $A$ and $B$ be propositions. The **conjunction** $A \wedge B$ ("$A$ and $B$") is true if and only if both $A$ and $B$ are true. [/definition] [definition:Disjunction] Let $A$ and $B$ be propositions. The **disjunction** $A \vee B$ ("$A$ or $B$") is true if and only if at least one of $A$ or $B$ is true (inclusive or). [/definition] [definition:Negation] Let $A$ be a proposition. The **negation** $\neg A$ ("not $A$") is true if and only if $A$ is false. [/definition] The inclusive interpretation of "or" is a deliberate choice: $A \vee B$ is true when both $A$ and $B$ hold. This matches mathematical usage — "an integer is in $S$ if it is even or a multiple of $3$" includes integers like $6$ that satisfy both conditions. With these connectives in hand, we can express compound assertions concisely. The next two definitions capture the most important compound forms: implication and equivalence. [definition:Logical Implication] The **logical implication** $A \implies B$ ("if $A$ then $B$," or "$A$ implies $B$") is defined to be false if and only if $A$ is true and $B$ is false. In all other cases, $A \implies B$ is true. [/definition] The definition of implication may seem surprising at first: if $A$ is false, then $A \implies B$ is true regardless of $B$. This is a convention, not a deep philosophical claim. It is adopted because it makes the implication useful in proofs: when we prove "for all $n$, if $P(n)$ then $Q(n)$," we only need to worry about the cases where $P(n)$ actually holds. [definition:Logical Equivalence] The **logical equivalence** $A \iff B$ ("$A$ if and only if $B$") is true when $A$ and $B$ have the same truth value (both true or both false), and false otherwise. [/definition] Equivalently, $A \iff B$ means that both $A \implies B$ and $B \implies A$ hold. ### Truth Tables The truth values of compound propositions can be tabulated systematically. For propositions $P$ and $Q$, the truth table is: | $P$ | $Q$ | $P \wedge Q$ | $P \vee Q$ | $P \implies Q$ | $P \iff Q$ | $\neg P$ | |-----|-----|---------------|------------|-----------------|------------|----------| | T | T | T | T | T | T | F | | T | F | F | T | F | F | F | | F | T | F | T | T | F | T | | F | F | F | F | T | T | T | ### [De Morgan's Laws](/theorems/622) The interaction between negation and the connectives $\wedge$, $\vee$ is governed by De Morgan's Laws, which are fundamental to manipulating logical expressions and will reappear in the context of set operations in a later chapter. [quotetheorem:761] The first law says: "$A$ or $B$" fails precisely when *both* $A$ and $B$ fail. The second says: "$A$ and $B$" fails precisely when *at least one* of them fails. Both can be verified directly from the truth table, checking all four rows — the proof is a straightforward exhaustive case analysis. [citeproof:761] ## Quantifiers When a proposition $P(x)$ depends on a variable $x$ ranging over a set $X$, we often want to assert that $P$ holds for all elements, or for at least one element. The quantifiers $\forall$ and $\exists$ formalise these assertions. [definition:Universal Quantifier] The statement $\forall x \in X,\; P(x)$ ("for all $x$ in $X$, $P(x)$ holds") is true if and only if $P(x)$ is true for every element $x \in X$. [/definition] [definition:Existential Quantifier] The statement $\exists x \in X,\; P(x)$ ("there exists $x$ in $X$ such that $P(x)$ holds") is true if and only if $P(x)$ is true for at least one element $x \in X$. [/definition] For a finite set $X = \{x_1, x_2, \ldots, x_n\}$, quantifiers reduce to connectives: \begin{align*} \forall x \in X,\; P(x) &\iff P(x_1) \wedge P(x_2) \wedge \cdots \wedge P(x_n), \\ \exists x \in X,\; P(x) &\iff P(x_1) \vee P(x_2) \vee \cdots \vee P(x_n). \end{align*} This correspondence makes the quantifier notation a generalisation of $\wedge$ and $\vee$ to potentially infinite sets. ## Negating Statements A recurrent task in mathematics is to negate a complex statement — for instance, to set up a proof by contradiction. The fundamental rule for negating quantified statements mirrors De Morgan's Laws: *negate the quantifiers and negate the predicate*. \begin{align*} \neg(\forall x \in X,\; P(x)) &= \exists x \in X,\; \neg P(x), \\ \neg(\exists x \in X,\; P(x)) &= \forall x \in X,\; \neg P(x). \end{align*} Intuitively: the failure of "every $x$ satisfies $P$" means some $x$ fails $P$; the failure of "some $x$ satisfies $P$" means every $x$ fails $P$. ### Negating Nested Quantifiers When a statement involves multiple quantifiers, the negation is obtained by flipping each quantifier in turn and negating the innermost predicate. The following extended example illustrates the process. [example:Negating Continuity] The $\varepsilon$-$\delta$ definition of [continuity](/page/Continuity) of a function $f: \mathbb{R} \to \mathbb{R}$ at a point $x$ states: \begin{align*} \forall \varepsilon > 0,\; \exists \delta > 0,\; \forall y \in \mathbb{R},\; |x - y| < \delta \implies |f(x) - f(y)| < \varepsilon. \end{align*} To negate this — i.e. to write down what it means for $f$ to be *discontinuous* at $x$ — we proceed from left to right, flipping each quantifier: \begin{align*} &\neg\bigl(\forall \varepsilon > 0,\; \exists \delta > 0,\; \forall y \in \mathbb{R},\; |x - y| < \delta \implies |f(x) - f(y)| < \varepsilon\bigr) \\ &= \exists \varepsilon > 0,\; \forall \delta > 0,\; \exists y \in \mathbb{R},\; |x - y| < \delta \;\wedge\; |f(x) - f(y)| \ge \varepsilon. \end{align*} In the last step, we negated the implication $|x-y| < \delta \implies |f(x) - f(y)| < \varepsilon$. Since $\neg(A \implies B)$ is equivalent to $A \wedge \neg B$, the negation becomes: $|x - y| < \delta$ *and* $|f(x) - f(y)| \ge \varepsilon$. In words: $f$ is discontinuous at $x$ if there exists some tolerance $\varepsilon > 0$ such that, no matter how small we choose $\delta$, there is always a point $y$ within distance $\delta$ of $x$ at which $f$ jumps by at least $\varepsilon$. [/example] The systematic approach — labelling nested sub-propositions $P_1, P_2, \ldots$ and peeling off one quantifier at a time — ensures that no sign errors or quantifier-flipping mistakes are introduced, even in highly nested expressions. This technique is indispensable in analysis, where definitions routinely involve three or more alternating quantifiers. # Elementary Number Theory Chapter 1 introduced the tools of mathematical reasoning — proof techniques, logical connectives, quantifiers — in the abstract. This chapter puts them to work. The natural numbers $1, 2, 3, \ldots$ are the most primitive mathematical objects, yet their structure is remarkably rich. Starting from a precise axiomatic definition of $\mathbb{N}$ (the Peano axioms), we develop the basic theory of divisibility, primes, and modular arithmetic, building up to the Fundamental Theorem of Arithmetic and its application to RSA encryption. Every proof technique from Chapter 1 appears: direct proof (the permutation argument for [Fermat's Little Theorem](/theorems/731)), proof by contrapositive (the reverse direction of [Quadratic Residue $-1$](/theorems/736)), proof by contradiction (the [infinitude of primes](/theorems/724)), and induction in both its ordinary and strong forms. The central theme is that a small number of axioms and a single proof technique (induction) generate an elaborate and beautiful theory. ## The Natural Numbers ### The Peano Axioms We begin by pinning down exactly what the natural numbers *are*. Informally, $\mathbb{N}$ consists of $1, 1+1, 1+1+1, \ldots$, but this description presupposes an understanding of the "$\ldots$" — precisely the kind of vagueness that axioms are meant to eliminate. [definition:Natural Numbers] The **natural numbers**, written $\mathbb{N}$, is a set containing a distinguished element $1$ and equipped with an operation "$+1$" (the successor operation) satisfying: (i) For all $n \in \mathbb{N}$, $n + 1 \ne 1$ (i.e. $1$ is not the successor of any natural number). (ii) For all $m, n \in \mathbb{N}$, if $m \ne n$ then $m + 1 \ne n + 1$ (i.e. the successor operation is injective). (iii) (Axiom of Induction) For any property $P(n)$, if $P(1)$ is true and $P(n) \implies P(n+1)$ for all $n \in \mathbb{N}$, then $P(n)$ is true for all $n \in \mathbb{N}$. [/definition] Axioms (i) and (ii) ensure that distinct natural numbers remain distinct: no two numbers share the same successor, and no number loops back to $1$. Axiom (iii) captures the idea that the list $1, 2, 3, \ldots$ is *complete* — there are no "rogue" natural numbers outside the chain starting at $1$. To see this, take $P(n) =$ "$n$ is on the list"; then (iii) says every natural number is reachable from $1$ by repeated application of the successor operation. ### Strong Induction Ordinary induction (Axiom (iii)) requires us to deduce $P(n+1)$ from $P(n)$ alone. In many arguments, we need access to the truth of $P$ at *all* values up to $n$, not just at $n$ itself. This motivates the principle of strong induction, which is logically equivalent to ordinary induction but often more natural to apply. [quotetheorem:720] Strong induction is not a new axiom — it is a consequence of Peano's third axiom. The proof introduces an auxiliary property $Q(n) = $ "$P(m)$ holds for all $m \le n$," which bundles together all predecessors. This "bundling" trick is a recurring technique: when a single-step induction hypothesis is too weak, strengthen it by carrying more information. [citeproof:720] ### The Well-Ordering Principle Strong induction tells us that if a property propagates from smaller to larger numbers, it holds everywhere. There is a complementary perspective: if a property holds *somewhere*, it holds at a *smallest* place. This is the well-ordering principle, and it turns out to be logically equivalent to strong induction. [definition:Well-Ordering Principle] The **well-ordering principle** (WOP) states that every non-empty subset of $\mathbb{N}$ has a least element. [/definition] This is equivalent to saying: if $P(n)$ holds for some $n \in \mathbb{N}$, then there is a *least* such $n$. The well-ordering principle is extremely useful in proofs by contradiction — if a counterexample exists, a *minimal* counterexample exists, and we can exploit its minimality to derive a contradiction. The equivalence of these two principles is a foundational result. The proof in both directions uses the technique of considering the negated property $Q(n) = \neg P(n)$. [quotetheorem:722] The two directions of the proof use the same core idea — proof by contradiction combined with minimality — but play it in opposite directions. In (a), we assume strong induction and derive a least counterexample to construct a contradiction. In (b), we assume WOP and use the non-existence of a least element to drive an induction. The elegance of the proof lies in the symmetry: each principle is the "flip side" of the other. [citeproof:722] ## Primes We have established the axiomatic foundations of $\mathbb{N}$: the Peano axioms, induction in its two forms, and the well-ordering principle. These are our tools; now we need something to use them on. The multiplicative structure of $\mathbb{N}$ provides the raw material. The basic question is: which numbers can be "broken down" into smaller factors, and which cannot? The ones that cannot — the primes — turn out to be the fundamental building blocks of all natural numbers, and understanding their properties is the central goal of this chapter. ### Divisibility With the natural numbers in hand, we turn to their multiplicative structure. The central notion is divisibility. [definition:Divisibility] For $a, b \in \mathbb{Z}$, we say $a$ **divides** $b$, written $a \mid b$, if there exists $c \in \mathbb{Z}$ such that $b = ac$. [/definition] For any $b \in \mathbb{Z}$, the integers $\pm 1$ and $\pm b$ always divide $b$; all other divisors are called **proper**. [definition:Prime Number] A natural number $p \ge 2$ is **prime** if its only divisors in $\mathbb{Z}$ are $\pm 1$ and $\pm p$. [/definition] [definition:Composite Number] A natural number $n \ge 2$ is **composite** if it is not prime — equivalently, if $n = ab$ for some integers $a, b$ with $1 < a, b < n$. [/definition] ### Existence of Prime Factorisations The first structural result about primes is that every natural number can be broken down into prime building blocks. This is the "existence" half of the Fundamental Theorem of Arithmetic; uniqueness requires more work and will come later. [quotetheorem:723] The proof is a clean application of strong induction. The key observation is that a composite number $n = ab$ with $1 < a, b < n$ reduces the problem to strictly smaller numbers, where the inductive hypothesis applies. The fact that *both* $a$ and $b$ are strictly less than $n$ is essential — ordinary induction, which only gives access to $n - 1$, would not suffice. [citeproof:723] ### Infinitude of Primes Given that primes exist and that every number is built from them, a natural question is: how many primes are there? Euclid's answer, dating to around 300 BC, is one of the most celebrated arguments in all of mathematics. [quotetheorem:724] Euclid's proof is a proof by contradiction with a remarkably simple construction. The number $N = p_1 \cdots p_k + 1$ is *not* claimed to be prime — it is only claimed that none of the listed primes can divide it. Since $N \ge 2$, it must have *some* prime factor (by the [Natural Numbers as Products of Primes](/theorems/723)), and that factor cannot be any of $p_1, \ldots, p_k$. A common error is to say "$N$ itself is prime"; this is false in general (e.g. $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509$). [citeproof:724] We have established that primes exist in abundance, but the deeper question remains: is the prime factorisation of a number *unique*? The answer is yes — this is the Fundamental Theorem of Arithmetic — but the proof requires a tool that is not at all obvious from the statement. We need to show that if a prime $p$ divides a product $ab$, then $p$ must divide $a$ or $b$. This fact ([Euclid's Lemma](/theorems/729)) turns out to depend on expressing $\gcd(p, a)$ as a *linear combination* of $p$ and $a$, which in turn requires the Euclidean algorithm. The logical chain is: Division Algorithm → Euclid's Algorithm → GCD as linear combination → Euclid's Lemma → Fundamental Theorem of Arithmetic. We now develop each link. ## Highest Common Factors and Euclid's Algorithm ### The GCD Suppose we want to solve the equation $12x + 8y = c$ in integers. For which values of $c$ does a solution exist? Since $12x + 8y$ is always a multiple of $4$ (because $12 = 4 \cdot 3$ and $8 = 4 \cdot 2$), the equation has no solution unless $4 \mid c$. Conversely, $12 \cdot 1 + 8 \cdot (-1) = 4$ shows that $c = 4$ is achievable, and scaling gives all multiples of $4$. The number $4$ — the greatest common divisor of $12$ and $8$ — is the key to the entire problem. This is the first hint that the GCD controls the solvability of linear equations, a theme that will culminate in [Bézout's Theorem](/theorems/728). The greatest common divisor is defined not as the "largest common factor" (though it is), but through a divisibility condition that is far more useful in proofs. [definition:Greatest Common Divisor] Given $a, b \in \mathbb{N}$, a natural number $c$ is the **greatest common divisor** (or **highest common factor**) of $a$ and $b$, written $\gcd(a, b)$, if: (i) $c \mid a$ and $c \mid b$, and (ii) if $d \mid a$ and $d \mid b$, then $d \mid c$. [/definition] Condition (ii) is the powerful one: it says that *every* common factor of $a$ and $b$ divides $c$. This is stronger than merely being the largest common factor, and it is the form we actually use in arguments (e.g. "since $d$ is a common factor, $d \mid \gcd(a,b)$"). ### The Division Algorithm The Division Algorithm is the engine behind Euclid's Algorithm and much of modular arithmetic. It formalises the idea that dividing $n$ by $k$ produces a quotient and a remainder. [quotetheorem:725] The proof proceeds by induction on $n$. At each step, the remainder either increases by one (if it has not yet reached $k-1$) or resets to zero (if it has), with the quotient incrementing. This two-case structure is a small but instructive example of how induction arguments handle [boundary](/page/Boundary) behaviour. [citeproof:725] ### Euclid's Algorithm To compute $\gcd(a, b)$ in practice, we use Euclid's algorithm: repeatedly apply the division algorithm, replacing the larger number with the remainder, until the remainder is zero. The last non-zero remainder is the GCD. [definition:Euclid Algorithm] Let $a, b \in \mathbb{N}$ with $a > b$. **Euclid's algorithm** is the following procedure. Set $r_{-1} = a$ and $r_0 = b$. At step $k \ge 1$, apply the division algorithm to write $r_{k-2} = q_k r_{k-1} + r_k$ with $0 \le r_k < r_{k-1}$. The algorithm terminates when $r_{n+1} = 0$ for some $n$, and the output is $r_n$ (the last non-zero remainder). [/definition] The algorithm terminates because the remainders $r_0 > r_1 > r_2 > \cdots \ge 0$ form a strictly decreasing sequence of non-negative integers, which must reach zero in finitely many steps (by the well-ordering principle applied to the set of non-negative integers below $b$). [example:Euclid Algorithm On 372 And 162] We compute $\gcd(372, 162)$. Applying the division algorithm repeatedly: \begin{align*} 372 &= 2 \cdot 162 + 48, \\ 162 &= 3 \cdot 48 + 18, \\ 48 &= 2 \cdot 18 + 12, \\ 18 &= 1 \cdot 12 + 6, \\ 12 &= 2 \cdot 6 + 0. \end{align*} The last non-zero remainder is $6$, so $\gcd(372, 162) = 6$. Back-substituting to express $6$ as a linear combination of $372$ and $162$: \begin{align*} 6 &= 18 - 1 \cdot 12 = 18 - 1 \cdot (48 - 2 \cdot 18) = 3 \cdot 18 - 48 \\ &= 3(162 - 3 \cdot 48) - 48 = 3 \cdot 162 - 10 \cdot 48 \\ &= 3 \cdot 162 - 10(372 - 2 \cdot 162) = 23 \cdot 162 - 10 \cdot 372. \end{align*} So $(-10) \cdot 372 + 23 \cdot 162 = 6$, confirming that $\gcd(372, 162)$ is a linear combination of $372$ and $162$. This back-substitution process is exactly how the [GCD as Linear Combination](/theorems/727) result is proved constructively. [/example] We now verify that this algorithm always produces the GCD — not merely a common divisor, but the *greatest* one in the divisibility sense. [quotetheorem:726] The correctness proof has an elegant structure: it verifies both halves of the GCD definition by "walking" up and down the algorithm's chain of equations. Walking *up* (from the last equation to the first) shows the output divides both inputs; walking *down* (from the first to the last) shows every common divisor of the inputs divides the output. The key insight is that the relation $r_{k-1} = q_{k+1} r_k + r_{k+1}$ preserves the set of common divisors at each step. [citeproof:726] ### GCD as a Linear Combination Euclid's algorithm does more than compute the GCD — by "back-substituting" through the chain of equations, it expresses the GCD as a linear combination of the two inputs. This is one of the most useful results in elementary number theory. [quotetheorem:727] The result has two conceptually distinct proofs. The first is constructive: run Euclid's algorithm, then substitute backwards through each equation to express $r_n$ in terms of $a$ and $b$. The second is non-constructive: take the *smallest* positive linear combination of $a$ and $b$, and show it satisfies the GCD axioms by a divisibility argument using the division algorithm. The minimality proof is particularly elegant — it shows that $h \mid a$ by contradiction, observing that the remainder $r = a - qh$ would be a *smaller* positive linear combination. [citeproof:727] ### Bézout's Theorem The GCD-as-linear-combination result immediately yields a criterion for when the Diophantine equation $ax + by = c$ is solvable. [quotetheorem:728] The forward direction is a one-line argument: if $h = \gcd(a,b)$ divides both $a$ and $b$, it divides any linear combination of them. The reverse uses the [GCD as Linear Combination](/theorems/727) to exhibit an explicit solution by scaling. This result is the gateway to solving linear congruences and underpins the proof of the Chinese Remainder Theorem. [citeproof:728] ## The Fundamental Theorem of Arithmetic The Fundamental Theorem of Arithmetic states that every natural number has a *unique* prime factorisation (up to ordering). Existence was established earlier; the missing ingredient for uniqueness is Euclid's Lemma, which says that primes cannot divide a product without dividing one of the factors. ### Euclid's Lemma [quotetheorem:729] The proof uses the [GCD as Linear Combination](/theorems/727) in an essential way. If $p \nmid a$, then $\gcd(p, a) = 1$ (since $p$ is prime), so we can write $1 = px + ay$ for some integers $x, y$. Multiplying by $b$ produces $b = pbx + aby$, and since $p$ divides both summands on the right, it divides $b$. The argument breaks down if $p$ is not prime — for instance, $6 \mid (4 \times 9)$ but $6 \nmid 4$ and $6 \nmid 9$. [citeproof:729] ### The Theorem With Euclid's Lemma in hand, we can prove uniqueness of prime factorisations. [quotetheorem:730] The proof proceeds by strong induction. Given two factorisations $n = p_1 \cdots p_r = q_1 \cdots q_s$, [Euclid's Lemma](/theorems/729) forces $p_1$ to equal some $q_i$. After cancelling and applying the inductive hypothesis to $n/p_1 < n$, the two factorisations are shown to be identical up to reordering. The argument would fail in number systems where Euclid's Lemma does not hold — for example, in $\mathbb{Z}[\sqrt{-3}]$, the number $4$ admits two distinct "prime" factorisations: $4 = 2 \times 2 = (1 + \sqrt{-3})(1 - \sqrt{-3})$. [citeproof:730] Unique factorisation is a powerful structural result — it reduces questions about divisibility to questions about comparing exponents in prime factorisations. But many problems in number theory are better approached not through the multiplicative structure of $\mathbb{N}$, but through the additive structure of *remainders*. The question "does $7$ divide $n$?" is equivalent to "is $n \equiv 0 \pmod{7}$?", and this shift in perspective — from divisibility to congruence — opens up an entirely new algebraic toolkit. Modular arithmetic also connects back to the GCD theory: the [Units Modulo n](/theorems/735) result shows that invertibility modulo $n$ is equivalent to coprimality, and the [Chinese Remainder Theorem](/theorems/734) is essentially a statement about the structure of $\mathbb{Z}/mn\mathbb{Z}$ when $\gcd(m, n) = 1$. ## Modular Arithmetic ### Congruence What is the last digit of $7^{100}$? Computing $7^{100}$ directly is infeasible, but the last digit depends only on remainders modulo $10$. We observe $7^1 = 7$, $7^2 = 49$, $7^3 = 343$, $7^4 = 2401$ — the last digits cycle as $7, 9, 3, 1, 7, 9, 3, 1, \ldots$ with period $4$. Since $100 = 4 \cdot 25$, the last digit of $7^{100}$ is $1$. This calculation used nothing about $7^{100}$ except its remainder when divided by $10$ — and the fact that remainders are preserved under multiplication. Modular arithmetic formalises this idea: rather than working with integers themselves, we work with their equivalence classes modulo a fixed number, and the key insight is that addition and multiplication respect this equivalence. This section develops modular arithmetic as a self-contained algebraic system. The payoff is substantial: Fermat's Little Theorem (controlling powers modulo primes), the Chinese Remainder Theorem (solving systems of congruences), and ultimately the RSA encryption scheme all emerge naturally from this framework. [definition:Congruence Modulo n] Let $n \ge 2$ be a natural number. We say that integers $x$ and $y$ are **congruent modulo** $n$, written $x \equiv y \pmod{n}$, if $n \mid (x - y)$. [/definition] Congruence modulo $n$ is an [equivalence relation](/page/Equivalence%20Relation) (it is reflexive, symmetric, and transitive). The key property that makes modular arithmetic work is *compatibility with addition and multiplication*: if $a \equiv a' \pmod{n}$ and $b \equiv b' \pmod{n}$, then $a + b \equiv a' + b' \pmod{n}$ and $ab \equiv a'b' \pmod{n}$. This follows from the identity $ab - a'b' = (a - a')b + a'(b - b')$. ### Units and Inverses Addition and multiplication in $\mathbb{Z}_n$ work well — we can add, subtract, and multiply freely. But *division* is problematic. In $\mathbb{Z}_6$, we have $2 \cdot 3 \equiv 0 \pmod{6}$, so "dividing by $2$" is impossible: if $2$ had an inverse $b$ with $2b \equiv 1$, then $0 = b \cdot 0 = b(2 \cdot 3) = (2b) \cdot 3 \equiv 3 \pmod{6}$, a contradiction. The elements that *do* admit division — those with multiplicative inverses — are called units, and the criterion for being a unit turns out to be exactly coprimality with the modulus. [definition:Unit Modulo n] An integer $a$ is a **unit modulo** $n$ (or is **invertible modulo** $n$) if there exists $b \in \mathbb{Z}$ with $ab \equiv 1 \pmod{n}$. The integer $b$ is called the **inverse** of $a$ modulo $n$. [/definition] The criterion for invertibility is clean: it reduces to a GCD condition. [quotetheorem:735] The proof is a direct chain of equivalences passing through [Bézout's Theorem](/theorems/728). This result explains, for instance, why $4$ has no inverse modulo $10$ (since $\gcd(4, 10) = 2 \ne 1$) but $3$ does (since $\gcd(3, 10) = 1$, and indeed $3 \times 7 = 21 \equiv 1 \pmod{10}$). [citeproof:735] ### Fermat's Little Theorem When the modulus is prime, every non-zero element is a unit — this gives $\mathbb{Z}_p$ a particularly nice algebraic structure. Fermat's Little Theorem exploits this to control the behaviour of powers modulo a prime. [quotetheorem:731] The proof uses a beautiful "permutation argument": multiplying the list $\{1, 2, \ldots, p-1\}$ by a unit $a$ simply rearranges the list (since multiplication by a unit is a bijection on the units). Comparing the products of the original and rearranged lists extracts $a^{p-1}$, which must be $1$ after cancelling $(p-1)!$. This same argument generalises to the Fermat-Euler theorem below. [citeproof:731] ### The Fermat-Euler Theorem Fermat's Little Theorem is powerful but limited: it only applies when the modulus is prime. What happens modulo a composite number like $12$? The permutation argument breaks down because not every non-zero element has a multiplicative inverse — for instance, $4 \cdot 3 = 12 \equiv 0 \pmod{12}$, so $4$ is a "zero divisor," not a unit. The fix is simple: restrict attention to the elements that *do* have inverses — the units, which by the [Units Modulo n](/theorems/735) result are precisely the elements coprime to the modulus. The number of such units is counted by the Euler totient function $\varphi(n)$. [definition:Euler Totient Function] For $m \ge 1$, the **Euler totient function** $\varphi(m)$ is the number of integers $a$ with $1 \le a \le m$ and $\gcd(a, m) = 1$. Equivalently, $\varphi(m)$ is the number of units modulo $m$. [/definition] When $p$ is prime, $\varphi(p) = p - 1$ (every non-zero residue is coprime to $p$). For a product of distinct primes $p, q$: $\varphi(pq) = pq - p - q + 1 = (p-1)(q-1)$, obtained by subtracting the multiples of $p$ and $q$ below $pq$ and adding back the one number ($pq$ itself) subtracted twice. [quotetheorem:732] The proof is a direct generalisation of the permutation argument for [Fermat's Little Theorem](/theorems/731): multiplication by $a$ permutes the units modulo $m$, so the product of all units is unchanged up to a factor of $a^{\varphi(m)}$, which must therefore be $1$. The restriction to units (rather than all residues) is what makes the argument work for composite moduli. [citeproof:732] ### Wilson's Theorem Wilson's Theorem provides a surprising characterisation of primes through factorials. [quotetheorem:733] The proof uses the pairing structure of inverses modulo $p$. Among $1, 2, \ldots, p-1$, most elements pair with a *distinct* inverse, and these pairs multiply to $1$. The only exceptions are the self-inverse elements (those with $x^2 \equiv 1 \pmod{p}$), which by [Euclid's Lemma](/theorems/729) are precisely $x \equiv \pm 1 \pmod{p}$. After all the inverse pairs cancel, only $1 \times (p-1) \equiv -1$ remains. [citeproof:733] ### The Chinese Remainder Theorem Suppose we want to find a number that leaves remainder $2$ when divided by $3$ and remainder $3$ when divided by $5$. That is, we seek $x$ with $x \equiv 2 \pmod{3}$ and $x \equiv 3 \pmod{5}$ simultaneously. Trial and error gives $x = 8$ (and $x = 23, 38, \ldots$). The Chinese Remainder Theorem says this always works when the moduli are coprime: any system of congruences with pairwise coprime moduli has a solution, and the solution is unique modulo the product of the moduli. [quotetheorem:734] The proof is constructive: it uses Bézout coefficients $sm + tn = 1$ to build the solution $x = a(tn) + b(sm)$ explicitly. The term $tn$ acts as a "selector" — it is $1$ modulo $m$ and $0$ modulo $n$, so $a(tn)$ contributes $a$ to the first congruence and $0$ to the second. Uniqueness follows from the fact that if two solutions exist, their difference is divisible by both $m$ and $n$, hence by $mn$ (since $\gcd(m,n) = 1$). The theorem extends by induction to any number of pairwise coprime moduli. [citeproof:734] ### Quadratic Residues: When is $-1$ a Square? Wilson's Theorem has a striking application: it determines exactly which primes $p$ admit a square root of $-1$ modulo $p$. [quotetheorem:736] The forward direction ($p \equiv 1 \pmod{4}$ implies $-1$ is a square) uses [Wilson's Theorem](/theorems/733) to factorise $(p-1)!$ into a perfect square times $(-1)^{(p-1)/2}$, which equals $1$ when $(p-1)/2$ is even. The reverse direction ($p \equiv 3 \pmod{4}$ implies $-1$ is not a square) uses [Fermat's Little Theorem](/theorems/731): if $z^2 \equiv -1$, then $z^{p-1} = (z^2)^{(p-1)/2} = (-1)^{(p-1)/2}$, which equals $-1$ when $(p-1)/2$ is odd, contradicting $z^{p-1} \equiv 1$. [citeproof:736] ## Public Key Cryptography We have now developed a substantial body of number theory: the Euclidean algorithm computes GCDs, [Bézout's theorem](/theorems/728) characterises solvable linear equations, the [Fermat-Euler theorem](/theorems/732) controls powers modulo $n$, and the [Chinese Remainder Theorem](/theorems/734) solves systems of congruences. Individually, these results are elegant but seem purely theoretical. Remarkably, they combine to produce one of the most important practical algorithms of the twentieth century: the RSA encryption scheme, which underpins much of modern internet security. RSA exploits the asymmetry between multiplication (easy) and factorisation (hard) of large numbers. [definition:RSA Encryption] The **RSA encryption scheme** operates as follows. Let $A$ denote the recipient and $B$ the sender. (i) $A$ chooses two large primes $p, q$ and computes $n = pq$. (ii) $A$ chooses $e \in \mathbb{N}$ with $\gcd(e, \varphi(n)) = 1$, where $\varphi(n) = (p-1)(q-1)$. (iii) $A$ computes $d = e^{-1} \bmod \varphi(n)$. (iv) $A$ publishes the *public key* $(n, e)$ and keeps $d$ secret. (v) $B$ encodes a message as a number $M$ with $1 \le M < n$ and sends $x = M^e \bmod n$. (vi) $A$ recovers the message by computing $x^d \bmod n$. [/definition] The inverse $d$ in step (iii) exists because $\gcd(e, \varphi(n)) = 1$, so $e$ is a unit modulo $\varphi(n)$ by the [Units Modulo n](/theorems/735). Decryption works because $ed \equiv 1 \pmod{\varphi(n)}$, so $ed = 1 + \lambda \varphi(n)$ for some integer $\lambda$. By the [Fermat-Euler Theorem](/theorems/732) (assuming $\gcd(M, n) = 1$): \begin{align*} x^d \equiv (M^e)^d = M^{ed} = M^{1 + \lambda \varphi(n)} = M \cdot (M^{\varphi(n)})^\lambda \equiv M \cdot 1^\lambda = M \pmod{n}. \end{align*} The security of RSA rests on the difficulty of computing $\varphi(n) = (p-1)(q-1)$ without knowing the factorisation $n = pq$. While multiplying two 300-digit primes takes milliseconds, no known algorithm can factor their product in feasible time. # The Reals The rational numbers $\mathbb{Q}$ are adequate for everyday arithmetic, but they have a fatal deficiency for analysis: they contain "gaps." To see this concretely, consider the sequence of rational approximations to $\sqrt{2}$: \begin{align*} a_1 = 1, \quad a_2 = 1.4, \quad a_3 = 1.41, \quad a_4 = 1.414, \quad a_5 = 1.4142, \quad \ldots \end{align*} This sequence is increasing and bounded above (by $2$, for instance). In any reasonable number system, a bounded increasing sequence should converge. But the limit — $\sqrt{2}$ — is not rational: if $\sqrt{2} = p/q$ in lowest terms, then $2q^2 = p^2$, which forces $p$ to be even, say $p = 2k$, giving $q^2 = 2k^2$, which forces $q$ to be even, contradicting lowest terms. So $\mathbb{Q}$ contains bounded increasing sequences with *no rational limit*. There is a "hole" in $\mathbb{Q}$ where $\sqrt{2}$ should be. The real numbers $\mathbb{R}$ are constructed precisely to fill these gaps. The key axiom — the least upper bound property — guarantees that bounded sets have suprema, which is exactly what $\mathbb{Q}$ lacks. Every result in this chapter flows from this single axiom: the [Archimedean Property](/theorems/737) (no infinitely large or infinitely small reals), the [density of $\mathbb{Q}$](/theorems/740) (rationals are everywhere despite having gaps), the [existence of $\sqrt{2}$](/theorems/739) (the gaps are filled), and the [Monotone Convergence Theorem](/theorems/743) (bounded monotone sequences converge). The chapter closes with two celebrated applications: the [irrationality of $e$](/theorems/746) and the existence of [transcendental numbers](/theorems/747). ## Axioms for the Real Numbers ### The Ordered Field Axioms Rather than constructing $\mathbb{R}$ from $\mathbb{Q}$ (which can be done via Dedekind cuts or [Cauchy sequences](/page/Cauchy%20Sequence)), we take the axiomatic approach: we state the properties that $\mathbb{R}$ must satisfy and develop the theory from there. [definition:Real Numbers] The **real numbers**, written $\mathbb{R}$, is a set with distinguished elements $0$ and $1$ (with $0 \ne 1$), equipped with operations $+$ and $\times$, and a total ordering $<$, satisfying: (i) $(\mathbb{R}, +, 0)$ is a commutative group: $+$ is commutative and associative with identity $0$, and every $x \in \mathbb{R}$ has an additive inverse $-x$. (ii) $(\mathbb{R} \setminus \{0\}, \times, 1)$ is a commutative group: $\times$ is commutative and associative with identity $1$, and every $x \ne 0$ has a multiplicative inverse $x^{-1}$. (iii) $\times$ distributes over $+$: $a \times (b + c) = a \times b + a \times c$ for all $a, b, c \in \mathbb{R}$. (iv) $<$ is a total order compatible with the field operations: for all $a, b, c \in \mathbb{R}$, $a < b$ implies $a + c < b + c$, and $a < b$ with $c > 0$ implies $ac < bc$. (v) (Least Upper Bound Axiom) Every non-empty subset of $\mathbb{R}$ that is bounded above has a least upper bound in $\mathbb{R}$. [/definition] Axioms (i)–(iv) say that $\mathbb{R}$ is an *ordered field*. The rational numbers $\mathbb{Q}$ also satisfy (i)–(iv). It is axiom (v) — the least upper bound axiom, also called *completeness* — that distinguishes $\mathbb{R}$ from $\mathbb{Q}$ and is the source of all the deeper results in this chapter. ### Bounds and Suprema The least upper bound axiom refers to concepts that we now make precise. [definition:Bounded Above] A set $S \subseteq \mathbb{R}$ is **bounded above** if there exists $M \in \mathbb{R}$ with $s \le M$ for all $s \in S$. Such an $M$ is called an **upper bound** for $S$. [/definition] [definition:Supremum] Let $S \subseteq \mathbb{R}$ be non-empty and bounded above. The **supremum** (or **least upper bound**) of $S$, written $\sup(S)$, is the smallest upper bound: $\sup(S)$ is an upper bound for $S$, and every other upper bound $M$ satisfies $M \ge \sup(S)$. [/definition] Analogously, a set bounded below has an **infimum** (greatest lower bound), written $\inf(S)$. To see that infima exist, observe that if $S$ is non-empty and bounded below, then $-S = \{-s : s \in S\}$ is non-empty and bounded above, so $\sup(-S)$ exists, and $\inf(S) = -\sup(-S)$. ## Consequences of Completeness ### The Archimedean Property The first consequence of the least upper bound axiom may seem trivially obvious: the natural numbers $1, 2, 3, \ldots$ are unbounded in $\mathbb{R}$. Why does this need proof? Because it is a *theorem about $\mathbb{R}$*, not a self-evident truth. There exist ordered fields — perfectly consistent number systems satisfying axioms (i)–(iv) — in which the natural numbers *are* bounded above (the field of formal Laurent series is one example). The Archimedean property is a consequence of completeness, and it is the foundation on which every $\varepsilon$-argument in analysis rests: whenever we need a quantity smaller than a given $\varepsilon > 0$, we use the fact that $1/n < \varepsilon$ for large enough $n$. [quotetheorem:737] The proof is a short but powerful application of the completeness axiom. If $\mathbb{N}$ were bounded above, its supremum $c$ would exist, and then $c - 1$ would fail to be an upper bound, producing an element $n \in \mathbb{N}$ with $n > c - 1$, whence $n + 1 > c$ — a contradiction. This argument uses the completeness of $\mathbb{R}$ in an essential way: in a non-Archimedean ordered field (such as the field of formal Laurent series), the "natural numbers" *are* bounded above. [citeproof:737] An immediate and frequently used consequence is the ability to make $1/n$ arbitrarily small: [quotetheorem:738] This follows from the [Archimedean Property](/theorems/737) by taking reciprocals. Despite its simplicity, this corollary is the workhorse behind most $\varepsilon$-arguments in analysis: whenever we need a quantity smaller than a given $\varepsilon > 0$, we invoke it. [citeproof:738] ### Existence of Roots The rationals fail to contain $\sqrt{2}$; the reals do not. The following result demonstrates that the least upper bound axiom closes the gaps in $\mathbb{Q}$. [quotetheorem:739] The proof constructs $\sqrt{2}$ as $\sup\{x \in \mathbb{R} : x^2 < 2\}$ and then eliminates both $c^2 < 2$ and $c^2 > 2$ by perturbation arguments. If $c^2 < 2$, we show $c + t \in S$ for small $t > 0$, contradicting the definition of supremum. If $c^2 > 2$, we show $c - t$ is still an upper bound for $S$, contradicting the *least*ness. The same proof template works to show that $\sqrt[n]{x}$ exists for all $x > 0$ and $n \in \mathbb{N}$. [citeproof:739] The existence of $\sqrt{2}$ shows that $\mathbb{R}$ contains numbers that $\mathbb{Q}$ misses. But *how* are the rationals and irrationals distributed in $\mathbb{R}$? Are the irrationals clustered in special regions, with large "rational-only" intervals between them? The next two results show the opposite: both $\mathbb{Q}$ and $\mathbb{R} \setminus \mathbb{Q}$ are *everywhere* — between any two distinct reals, no matter how close, there lies a rational *and* an irrational. ### Density Results The Archimedean property has a striking [topological](/page/Topology) consequence: both $\mathbb{Q}$ and $\mathbb{R} \setminus \mathbb{Q}$ are *dense* in $\mathbb{R}$, meaning that between any two distinct reals, there lies a rational and an irrational. [quotetheorem:740] The proof constructs a rational in $(a, b)$ by choosing a denominator $n$ with $1/n < b - a$ (via the [Archimedean Corollary](/theorems/738)) and then selecting the right numerator using the well-ordering principle. The interplay between the Archimedean property (to get the denominator) and the well-ordering principle (to get the numerator) is characteristic of many constructions in real analysis. [citeproof:740] The irrationals are dense for a simpler reason: the rationals are, and scaling by an irrational preserves irrationality. [quotetheorem:741] The proof reduces to the [Density of Rationals](/theorems/740) by a scaling trick: find a rational in $(a\alpha, b\alpha)$ for some fixed irrational $\alpha > 0$, then divide by $\alpha$. The quotient is irrational because a rational divided by an irrational is irrational (unless the numerator is zero, which is excluded since the rational lies in an interval not containing zero). [citeproof:741] The density results paint a remarkable picture: $\mathbb{Q}$ and $\mathbb{R} \setminus \mathbb{Q}$ are thoroughly interwoven, each dense in $\mathbb{R}$. But density is a qualitative statement — it says there *exists* a rational (or irrational) in every interval, without telling us how to systematically approach a given real number. Sequences provide the quantitative machinery: they let us *approximate* real numbers by explicit constructions, and the key question becomes when such approximations converge. The answer depends on completeness — and the [Monotone Convergence Theorem](/theorems/743), which we prove below, is the single most important consequence of the least upper bound axiom for the rest of analysis. ## Sequences and Convergence ### Definitions Sequences are the basic objects of real analysis. Informally, a sequence is an ordered list $a_1, a_2, a_3, \ldots$ of real numbers; formally, it is a function from $\mathbb{N}$ to $\mathbb{R}$. [definition:Convergence] A sequence $(a_n)_{n=1}^{\infty}$ of real numbers **converges to the limit** $l \in \mathbb{R}$ if for every $\varepsilon > 0$, there exists $N \in \mathbb{N}$ such that $|a_n - l| < \varepsilon$ for all $n \ge N$. We write $a_n \to l$ as $n \to \infty$, or $\lim_{n \to \infty} a_n = l$. A sequence that does not converge is said to **diverge**. [/definition] The definition encodes the intuition that the terms $a_n$ eventually get (and stay) arbitrarily close to $l$. The quantifier structure is important: "for every $\varepsilon$" comes first, then "there exists $N$" — the choice of $N$ is allowed to depend on $\varepsilon$. [definition:Bounded Sequence] A sequence $(a_n)$ is **bounded** if there exists $B \in \mathbb{R}$ with $|a_n| \le B$ for all $n \in \mathbb{N}$. [/definition] Every convergent sequence is bounded: if $a_n \to l$, choose $N$ so that $|a_n - l| \le 1$ for $n \ge N$; then $|a_n| \le |l| + 1$ for $n \ge N$, and $|a_n| \le \max\{|a_1|, \ldots, |a_{N-1}|, |l| + 1\}$ for all $n$. ### Uniqueness of [Limits](/page/Limit) Convergent sequences have at most one limit — the definition pins it down uniquely. [quotetheorem:742] The proof uses the triangle inequality to force two distinct limits into an impossible configuration. If $a_n$ were eventually within $\varepsilon = |l-k|/2$ of both $l$ and $k$, the triangle inequality would give $|l - k| < |l - k|$, a contradiction. This argument is prototypical of many uniqueness proofs in analysis: assume two objects satisfy the same approximation property, then derive a self-contradictory inequality. [citeproof:742] ### The Monotone Convergence Theorem Not all convergent sequences are easy to evaluate — sometimes we know a sequence converges without knowing its limit. The Monotone Convergence Theorem provides a powerful sufficient condition: bounded monotone sequences always converge. [definition:Monotone Sequence] A sequence $(a_n)_{n=1}^{\infty}$ is **monotone** if it is either increasing ($a_{n+1} \ge a_n$ for all $n$) or decreasing ($a_{n+1} \le a_n$ for all $n$). [/definition] [quotetheorem:743] The proof identifies the limit as the supremum of the range $\{a_n : n \ge 1\}$, which exists by the least upper bound axiom. The supremum is a limit because: (a) every term satisfies $a_n \le l = \sup$, and (b) for any $\varepsilon > 0$, some term exceeds $l - \varepsilon$ (else $l - \varepsilon$ would be a smaller upper bound), and (c) monotonicity ensures all subsequent terms also exceed $l - \varepsilon$. This result *fails* in $\mathbb{Q}$: the sequence $1, 1.4, 1.41, 1.414, \ldots$ of rational approximations to $\sqrt{2}$ is bounded and increasing but has no rational limit. In fact, the Monotone Convergence Theorem is *equivalent* to the least upper bound axiom. [citeproof:743] The Monotone Convergence Theorem is the tool that makes infinite processes rigorous in $\mathbb{R}$: it guarantees that bounded monotone sequences — which arise constantly when constructing limits, summing series, or building approximations — always land somewhere. We now apply it to two concrete settings: decimal expansions (where the partial sums $\sum_{j=1}^{n} d_j / 10^j$ form a bounded increasing sequence) and the definition of Euler's number $e$ (where the partial sums $\sum_{j=0}^{n} 1/j!$ converge by the same mechanism). The connection to number theory is unexpected: characterising which decimals are periodic will require the [Fermat-Euler Theorem](/theorems/732) from the previous chapter. ## Decimal Expansions and Series ### Series The notion of series extends addition from finite to infinite sums, using limits of partial sums. [definition:Convergence Of Series] Let $(a_n)_{n=1}^{\infty}$ be a sequence of real numbers. The **$k$-th partial sum** is $s_k = \sum_{n=1}^{k} a_n$. The series $\sum_{n=1}^{\infty} a_n$ **converges** if the sequence $(s_k)_{k=1}^{\infty}$ of partial sums converges, in which case we write $\sum_{n=1}^{\infty} a_n = \lim_{k \to \infty} s_k$. [/definition] ### Decimal Expansions Decimal expansions are a special case of series: $0.d_1 d_2 d_3 \ldots = \sum_{n=1}^{\infty} d_n / 10^n$. The [Monotone Convergence Theorem for Sequences](/theorems/743) guarantees convergence (the partial sums are increasing and bounded above by $\sum_{n=1}^{\infty} 9/10^n = 1$). The deeper question is whether every real number in $[0, 1)$ *has* a decimal expansion. [quotetheorem:744] The proof constructs digits greedily: at each step, choose the largest digit such that the partial sum does not overshoot $x$. This greedy algorithm produces a "remainder" $x - S_n$ that is squeezed between $0$ and $1/10^n$, which forces convergence to $x$. The same approach works in any base — for example, binary expansions use digits in $\{0, 1\}$ and powers of $1/2$. [citeproof:744] ### Characterisation of Rational Decimals Which real numbers have *periodic* (eventually repeating) decimal expansions? The answer is exactly the rationals — connecting the algebraic structure of $\mathbb{Q}$ to the analytic structure of decimal representations. [definition:Periodic Decimal] A decimal expansion $0.d_1 d_2 d_3 \ldots$ is **periodic** if there exist integers $l \ge 0$ and $k \ge 1$ such that $d_{n+k} = d_n$ for all $n > l$. The block $d_{l+1} d_{l+2} \ldots d_{l+k}$ is the **repeating block** and $k$ is the **period**. [/definition] [quotetheorem:745] The forward direction (periodic implies rational) uses the geometric series formula. The reverse direction (rational implies periodic) is the more surprising half: it uses the [Fermat-Euler Theorem](/theorems/732) to show that $10^{\varphi(q)} \equiv 1 \pmod{q}$ when $\gcd(q, 10) = 1$, which forces the decimal to repeat with period dividing $\varphi(q)$. This is a beautiful connection between number theory and analysis — the period of the decimal expansion of $1/q$ is controlled by the multiplicative order of $10$ modulo $q$. [citeproof:745] The characterisation of periodic decimals draws a clean line between the rationals and the irrationals: a real number is rational if and only if its decimal expansion eventually repeats. But how "irrational" can a number be? Every rational is algebraic (it satisfies a degree-1 polynomial), and many irrational numbers are also algebraic ($\sqrt{2}$ satisfies $x^2 - 2 = 0$). The deepest question is whether there exist numbers that are not roots of *any* polynomial with integer coefficients — *transcendental* numbers. We close this chapter by studying two specific real numbers: Euler's number $e$, which we prove is irrational, and Liouville's constant, which we prove is transcendental. ## Special Numbers ### Euler's Number The number $e$ arises naturally as the sum of the reciprocals of factorials. Its convergence follows from comparison with a geometric series. [definition:Euler Number] **Euler's number** is defined by \begin{align*} e = \sum_{j=0}^{\infty} \frac{1}{j!} = 1 + 1 + \frac{1}{2} + \frac{1}{6} + \frac{1}{24} + \cdots. \end{align*} [/definition] The series converges by the [Monotone Convergence Theorem for Sequences](/theorems/743): the partial sums are increasing (each term is positive), and bounded above by $1 + 1 + 1/2 + 1/4 + 1/8 + \cdots = 3$, since $1/k! \le 1/2^{k-1}$ for $k \ge 1$. Hence $2 < e \le 3$. A natural question is whether $e$ is rational. The answer is no, and the proof is a gem. [quotetheorem:746] The proof isolates the "tail" of the series past the $q$-th term — multiplied by $q!$, this tail is a positive real number strictly less than $1$. Since the "head" (the first $q + 1$ terms times $q!$) is an integer, the product $q! \cdot e$ is an integer plus a number in $(0, 1)$, which is not an integer. This contradicts the assumption $e = p/q$. The bound $x \le 1/q < 1$ is the critical step; it uses the geometric series comparison $1/(q+1)^j$ for the tail terms. [citeproof:746] ### Algebraic and Transcendental Numbers The irrationality of $e$ means $e$ is not a root of any degree-1 polynomial with integer coefficients. A much stronger statement is that $e$ is not a root of *any* non-zero polynomial with integer coefficients — it is *transcendental*. While the transcendence of $e$ (proved by Hermite in 1873) requires tools beyond this course, we can exhibit explicit transcendental numbers using a different approach. [definition:Algebraic Number] A real number $x$ is **algebraic** if it is a root of some non-zero polynomial with integer coefficients. Every rational number $p/q$ is algebraic (it satisfies $qx - p = 0$), and so is $\sqrt{2}$ (it satisfies $x^2 - 2 = 0$). [/definition] [definition:Transcendental Number] A real number is **transcendental** if it is not algebraic — i.e. it is not a root of any non-zero polynomial with integer coefficients. [/definition] The existence of transcendental numbers is not obvious — after all, the algebraic numbers already include every rational, every $n$-th root, and every root of every polynomial with integer coefficients. Is there anything left? In the Countability chapter below, we will give a remarkably short proof: since the algebraic numbers are [countable](/theorems/757) and the reals are [uncountable](/theorems/758), transcendental numbers must exist — and in fact they vastly outnumber the algebraic numbers. But that argument is non-constructive: it tells us transcendentals exist without naming one. Liouville's construction below gives an explicit example, using the idea that algebraic numbers of degree $d$ cannot be approximated "too well" by rationals. [quotetheorem:747] The proof is a contradiction argument with two competing estimates. On one hand, the partial sums $L_n$ converge to $L$ extremely fast — the error $|L - L_n|$ is at most $2/10^{(n+1)!}$, which decays super-exponentially. On the other hand, if $L$ were algebraic — a root of a degree-$d$ polynomial $p$ with integer coefficients — then $|p(L_n)|$ could not be too small: since $L_n = s/10^{n!}$ is rational with denominator $10^{n!}$, the value $p(L_n) = t/10^{dn!}$ for some integer $t$, and if $L_n$ is not itself a root of $p$ (which it is not for large $n$, since $p$ has only finitely many roots), then $|p(L_n)| \ge 10^{-dn!}$. Combining with the Lipschitz bound $|p(L_n)| = |p(L_n) - p(L)| \le K|L - L_n|$ gives $10^{-dn!} \le 2K \cdot 10^{-(n+1)!}$, which fails for large $n$ since $(n+1)! - dn! = n!(n+1-d) \to \infty$. [citeproof:747] # Sets, Functions and Relations Throughout the previous chapters, we used sets freely — the set of primes, the set $\{x \in \mathbb{R} : x^2 < 2\}$, the set of units modulo $n$ — without ever defining what a set *is* or what operations are permitted on sets. This worked because the sets we encountered were always subsets of familiar objects like $\mathbb{N}$ or $\mathbb{R}$. But what happens when we try to form more exotic collections? Can we take "the set of all sets"? Can we form $\{x : x \notin x\}$? Russell's paradox (which we will see shortly) shows that naive set-formation leads to contradictions, and that the rules for building sets must be stated carefully. This chapter develops the foundational language in which all of mathematics is written. We begin with the basic operations on sets — union, intersection, difference — and prove their algebraic laws (distributivity, De Morgan). We then formalise the notion of a function as a subset of a Cartesian product, isolating the key properties (injectivity, surjectivity, bijectivity) that will drive the countability arguments in the next chapter. Along the way, we develop the combinatorics of finite sets — the [Binomial Theorem](/theorems/750) and the [Inclusion-Exclusion Principle](/theorems/751) — which are indispensable tools throughout mathematics. The chapter concludes with equivalence relations and quotient sets, which provide the formal framework for constructions like $\mathbb{Z}_n$ (integers modulo $n$, already encountered in the number theory chapter) and $\mathbb{Q}$ (rationals as equivalence classes of pairs of integers). ## Basic Set Theory ### Sets and Subsets We take the notion of a set as primitive — a set is a collection of mathematical objects, called its *elements*. [definition:Set Equality] Two sets $A$ and $B$ are **equal**, written $A = B$, if they have the same elements: $\forall x,\; x \in A \iff x \in B$. Equivalently, $A = B$ if and only if $A \subseteq B$ and $B \subseteq A$. [/definition] The "mutual inclusion" characterisation ($A \subseteq B$ and $B \subseteq A$) is the standard technique for proving two sets are equal: show that every element of one belongs to the other, and vice versa. [definition:Subset] A set $B$ is a **subset** of $A$, written $B \subseteq A$, if every element of $B$ is an element of $A$. We say $B$ is a **proper subset** of $A$, written $B \subsetneq A$, if $B \subseteq A$ and $B \ne A$. [/definition] Given a set $A$ and a property $P$, we can form the subset $\{x \in A : P(x)\}$ consisting of those elements of $A$ satisfying $P$. This *subset selection* (or *specification*) axiom is carefully restricted to subsets of an existing set — forming $\{x : P(x)\}$ without reference to an ambient set leads to paradoxes, as Russell's paradox demonstrates. ### Set Operations The fundamental operations on sets — union, intersection, difference, and complement — mirror the logical connectives $\vee$, $\wedge$, and $\neg$. [definition:Union] For sets $A$ and $B$, the **union** is $A \cup B = \{x : x \in A \text{ or } x \in B\}$. [/definition] [definition:Intersection] For sets $A$ and $B$, the **intersection** is $A \cap B = \{x : x \in A \text{ and } x \in B\}$. [/definition] Two sets $A$ and $B$ are called **disjoint** if $A \cap B = \varnothing$. [definition:Set Difference] For sets $A$ and $B$, the **set difference** is $A \setminus B = \{x \in A : x \notin B\}$. [/definition] Both $\cup$ and $\cap$ are commutative and associative. More importantly, they distribute over each other: [quotetheorem:748] The proof is a direct element-chasing argument: to show two sets are equal, show each is a subset of the other. For instance, to show $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$, take $x \in A \cap (B \cup C)$ and split into cases $x \in B$ or $x \in C$. The reverse inclusion is similarly straightforward. The parallel with the [propositional De Morgan's Laws](/theorems/761) from Chapter 1 is exact: replacing $\in$ with "true," $\cup$ with $\vee$, and $\cap$ with $\wedge$ turns each set-theoretic identity into a logical one. This is not a coincidence — the membership relation $x \in A$ is a proposition, and set operations are defined through logical connectives. [citeproof:748] ### Cartesian Products and Power Sets To define functions formally, we first need ordered pairs and Cartesian products. [definition:Cartesian Product] For sets $A$ and $B$, the **Cartesian product** $A \times B$ is the set of all ordered pairs: \begin{align*} A \times B = \{(a, b) : a \in A,\; b \in B\}. \end{align*} [/definition] The power set — the set of all subsets — is the other fundamental set-building operation. [definition:Power Set] For any set $X$, the **power set** $\mathcal{P}(X)$ is the set of all subsets of $X$: \begin{align*} \mathcal{P}(X) = \{Y : Y \subseteq X\}. \end{align*} [/definition] [example:Power Set Of A Two Element Set] If $X = \{1, 2\}$, then $\mathcal{P}(X) = \{\varnothing, \{1\}, \{2\}, \{1, 2\}\}$, which has $4 = 2^2$ elements. [/example] ### Russell's Paradox Not every collection of objects forms a set. Attempting to define the "set of all sets that do not contain themselves" leads to a contradiction. [example:Russell Paradox] Suppose $X = \{x : x \text{ is a set and } x \notin x\}$ were a set. If $X \in X$, then by definition of $X$, $X \notin X$ — contradiction. If $X \notin X$, then $X$ satisfies the defining property, so $X \in X$ — contradiction. Hence no such set exists. [/example] This paradox shows why subset selection must be relative to an existing set: $\{x \in A : P(x)\}$ is always safe, but $\{x : P(x)\}$ is not. A consequence is that there is no "universal set" containing all sets — if such a set $V$ existed, we could form $\{x \in V : x \notin x\}$ and reproduce the paradox. With the basic set-theoretic machinery in place — sets, subsets, operations, Cartesian products, power sets — we can now ask quantitative questions: how many elements does a set have? For finite sets, this leads to the combinatorics of binomial coefficients and inclusion-exclusion. For infinite sets, the question becomes much subtler and will occupy the entire next chapter. ## Finite Sets and Counting ### Cardinality Counting the elements of finite sets — and later, comparing the "sizes" of infinite sets — is a central theme that continues into the next chapter on countability. [definition:Finite Set] A set $A$ has **size** $n \in \mathbb{N}_0 = \mathbb{N} \cup \{0\}$ if its elements can be listed as $A = \{a_1, a_2, \ldots, a_n\}$ with all $a_i$ distinct. We write $|A| = n$. A set is **finite** if it has size $n$ for some $n \in \mathbb{N}_0$, and **infinite** otherwise. [/definition] The power set of an $n$-element set has a clean cardinality formula. [quotetheorem:749] The proof establishes a bijection between subsets of $\{1, \ldots, n\}$ and binary strings of length $n$: each subset corresponds to an indicator sequence $(b_1, \ldots, b_n) \in \{0, 1\}^n$, where $b_i = 1$ iff $i$ belongs to the subset. Since each of the $n$ bits can independently be $0$ or $1$, there are $2^n$ binary strings and hence $2^n$ subsets. [citeproof:749] For finite sets, $|\mathcal{P}(X)| = 2^{|X|} > |X|$ — the power set is always strictly larger. A deep result in the next chapter ([Cantor's Theorem](/theorems/759)) shows that this strict inequality persists for *infinite* sets: there is no bijection from any set $X$ to $\mathcal{P}(X)$, even when both are infinite. This is what makes the hierarchy of infinities inexhaustible. ### Binomial Coefficients To count subsets of a *fixed size*, we use binomial coefficients. [definition:Binomial Coefficient] For $n \in \mathbb{N}_0$ and $0 \le k \le n$, the **binomial coefficient** $\binom{n}{k}$ (read "$n$ choose $k$") is the number of subsets of size $k$ in an $n$-element set: \begin{align*} \binom{n}{k} = |\{S \subseteq \{1, 2, \ldots, n\} : |S| = k\}| = \frac{n!}{k!(n-k)!}. \end{align*} [/definition] The formula $\binom{n}{k} = n! / (k!(n-k)!)$ counts ordered selections ($n(n-1) \cdots (n-k+1)$ ways to pick $k$ elements one by one) divided by the number of orderings of each subset ($k!$ permutations). A useful identity is Pascal's rule: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$, which follows from partitioning the subsets of $\{1, \ldots, n\}$ of size $k$ according to whether they contain $n$. ### The Binomial Theorem Binomial coefficients arise naturally when expanding powers of sums. [quotetheorem:750] The proof is combinatorial rather than algebraic. Expanding $(a+b)^n = (a+b)(a+b) \cdots (a+b)$ produces $2^n$ terms, each obtained by choosing $a$ or $b$ from each factor. The term $a^{n-k}b^k$ arises from choosing $b$ in exactly $k$ of the $n$ factors, which can be done in $\binom{n}{k}$ ways. Setting $a = 1, b = x$ gives the useful approximation $(1 + x)^n \approx 1 + nx$ for small $x$. [citeproof:750] ### Inclusion-Exclusion When counting the union of overlapping sets, we must correct for double-counting. The inclusion-exclusion principle provides the exact correction. [quotetheorem:751] The proof shows that each element of the union is counted exactly once on the right-hand side. An element belonging to exactly $m$ of the $n$ sets contributes $\binom{m}{1} - \binom{m}{2} + \cdots + (-1)^{m+1}\binom{m}{m}$ to the alternating sum. By the [Binomial Theorem](/theorems/750) with $a = 1, b = -1$: $\sum_{r=0}^{m} (-1)^r \binom{m}{r} = 0$, so the alternating sum (starting from $r = 1$) equals $1$. [citeproof:751] The combinatorial results above — power set cardinality, binomial coefficients, inclusion-exclusion — all count *sets*. But the proofs themselves relied on an unstated concept: the idea of a *bijection* between a set of objects and a set of labels (e.g., between subsets and binary strings in the [power set proof](/theorems/749)). To make such arguments precise — and to extend the notion of "same size" to infinite sets in the next chapter — we need a formal definition of what a function is. ## Functions ### Definition and Terminology The notion of a function — a rule that assigns to each input exactly one output — is the single most important concept in mathematics. Every theorem in this course can be rephrased as a statement about functions: the [Division Algorithm](/theorems/725) defines a function $n \mapsto (q, r)$; the [decimal expansion](/theorems/744) theorem says a certain function from $[0,1)$ to digit sequences is surjective; and the entire next chapter on countability reduces to one question: does a *bijection* from a given set to $\mathbb{N}$ exist? The three properties we isolate below — injectivity (no collisions), surjectivity (everything is hit), and bijectivity (both at once) — are the precise tools for answering such questions. [definition:Function] A **function** from $A$ to $B$ is a subset $f \subseteq A \times B$ such that for every $x \in A$, there exists a unique $y \in B$ with $(x, y) \in f$. We write $f: A \to B$, and denote the unique $y$ by $f(x)$. The set $A$ is the **domain** and $B$ the **codomain** (or **range**) of $f$. The **image** of $f$ is $f(A) = \{f(a) : a \in A\}$. [/definition] Three properties of functions are fundamental to the theory of sets and will be crucial in the chapter on countability. [definition:Injective Function] A function $f: A \to B$ is **injective** (or **one-to-one**) if $f(a) = f(a')$ implies $a = a'$ for all $a, a' \in A$. [/definition] [definition:Surjective Function] A function $f: A \to B$ is **surjective** (or **onto**) if for every $b \in B$, there exists $a \in A$ with $f(a) = b$. [/definition] [definition:Bijective Function] A function $f: A \to B$ is **bijective** if it is both injective and surjective. Equivalently, $f$ is bijective if and only if it has an inverse — a function $g: B \to A$ with $g \circ f = \operatorname{id}_A$ and $f \circ g = \operatorname{id}_B$. [/definition] Bijections preserve set size: if there exists a bijection $f: A \to B$, then $|A| = |B|$. This observation is the starting point for comparing the sizes of infinite sets. ### Composition Functions can be composed: given $f: A \to B$ and $g: B \to C$, the composition $g \circ f: A \to C$ is defined by $(g \circ f)(a) = g(f(a))$. Composition is associative — $f \circ (g \circ h) = (f \circ g) \circ h$ — but not commutative in general. ## Relations ### Equivalence Relations In the [number theory chapter](/page/Cambridge%20Part%20IA%20Numbers%20and%20Sets), we defined congruence modulo $n$ and observed that it is reflexive, symmetric, and transitive — we could add and multiply "as if" congruent integers were equal. We also built $\mathbb{Q}$ informally by treating $1/2$ and $2/4$ as "the same." Both of these are instances of a general pattern: we declare certain pairs of objects to be equivalent, and then work with the equivalence classes rather than the objects themselves. The abstract definition of an equivalence relation captures this pattern precisely, and the key theorem of this section — that equivalence classes partition the underlying set — guarantees that the construction is well-behaved. [definition:Relation] A **relation** on a set $X$ is a subset $R \subseteq X \times X$. We write $aRb$ (or $a \sim b$) to mean $(a, b) \in R$. [/definition] The most important class of relations are equivalence relations, which capture the idea of grouping elements that are "the same" in some respect. [definition:Equivalence Relation] A relation $\sim$ on a set $X$ is an **equivalence relation** if it is: - **Reflexive:** $x \sim x$ for all $x \in X$. - **Symmetric:** $x \sim y$ implies $y \sim x$ for all $x, y \in X$. - **Transitive:** $x \sim y$ and $y \sim z$ imply $x \sim z$ for all $x, y, z \in X$. [/definition] [example:Congruence As Equivalence] Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$: reflexivity ($a \equiv a$), symmetry ($a \equiv b \implies b \equiv a$), and transitivity ($a \equiv b, b \equiv c \implies a \equiv c$) all follow from the corresponding properties of divisibility. The equivalence classes are the residue classes $[0], [1], \ldots, [n-1]$. [/example] ### Equivalence Classes and Partitions An equivalence relation on $X$ slices $X$ into non-overlapping pieces, each consisting of mutually equivalent elements. [definition:Equivalence Class] If $\sim$ is an equivalence relation on $X$, the **equivalence class** of $x \in X$ is $[x] = \{y \in X : y \sim x\}$. [/definition] [definition:Partition] A **partition** of a set $X$ is a collection of pairwise disjoint, non-empty subsets of $X$ whose union is $X$. [/definition] The fundamental theorem of equivalence relations says that equivalence classes always form a partition, and conversely, any partition defines an equivalence relation. [quotetheorem:762] The forward direction has two parts. First, $X$ is the union of its equivalence classes (since $x \in [x]$ for every $x$, by reflexivity). Second, any two equivalence classes are either identical or disjoint: if $[x] \cap [y] \ne \varnothing$, pick $z \in [x] \cap [y]$; then $x \sim z$ and $z \sim y$, so $x \sim y$ by transitivity, and a further transitivity argument shows $[x] \subseteq [y]$ and $[y] \subseteq [x]$, giving $[x] = [y]$. The converse is equally natural: the parts of a partition define "same part" as the equivalence relation, and each element's class is exactly its part. [citeproof:762] ### Quotient Sets The set of equivalence classes itself forms a new mathematical object. [definition:Quotient Set] Given an equivalence relation $R$ on a set $X$, the **quotient** of $X$ by $R$ is $X/R = \{[x] : x \in X\}$, the set of equivalence classes. The map $q: X \to X/R$ defined by $q(x) = [x]$ is the **quotient map**. [/definition] [example:Rationals As Quotient] On $\mathbb{Z} \times \mathbb{N}$, define $(a, b) \sim (c, d)$ if $ad = bc$. This is an equivalence relation, and the equivalence class $[(a, b)]$ represents the rational number $a/b$. The quotient $(\mathbb{Z} \times \mathbb{N})/{\sim}$ is a copy of $\mathbb{Q}$. [/example] With the language of sets, functions, and bijections in place, we can finally ask a question that has been lurking since we first encountered $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$: are these sets all the "same size," or are some genuinely larger than others? For finite sets, the answer is easy — we count elements. But $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{Q}$ are all infinite, so counting is not available. The key insight is that *bijections* are the right tool for comparing infinite sets: two sets have the same size if and only if there is a bijection between them. This leads to Cantor's shocking discovery that $\mathbb{Q}$ — despite being dense in $\mathbb{R}$ — is no larger than $\mathbb{N}$, while $\mathbb{R}$ is genuinely, provably larger. The machinery of injections, surjections, and the [Fundamental Theorem of Arithmetic](/theorems/730) (which provides the injection $(x, y) \mapsto 2^x 3^y$ needed to prove $\mathbb{N} \times \mathbb{N}$ is countable) will all be essential. # Countability For finite sets, the notion of "size" is straightforward — we count elements. For infinite sets, every intuition fails. Consider the map $n \mapsto 2n$ from $\mathbb{N}$ to the even numbers. This is a bijection: every even number is hit exactly once. So the even numbers — a *proper subset* of $\mathbb{N}$ — have "the same number of elements" as $\mathbb{N}$ itself. This is impossible for finite sets (a proper subset is always strictly smaller), but it is the defining feature of infinite sets: they can be placed in bijection with proper subsets of themselves. Once we accept bijections as the right tool for comparing sizes, two remarkable facts emerge. First, many sets that *look* much larger than $\mathbb{N}$ turn out to have the same cardinality: $\mathbb{Z}$ (which extends in both directions), $\mathbb{N} \times \mathbb{N}$ (which is two-dimensional), and even $\mathbb{Q}$ (which is [dense in $\mathbb{R}$](/theorems/740) — between any two rationals lies another rational) are all *countable*. Second, $\mathbb{R}$ is genuinely, provably larger: no bijection $\mathbb{N} \to \mathbb{R}$ can exist, and the proof is Cantor's diagonal argument — one of the most elegant constructions in all of mathematics. The chapter develops these ideas systematically, building the countability toolkit from subsets of $\mathbb{N}$ up to the [Schröder-Bernstein Theorem](/theorems/760) and [Cantor's Theorem](/theorems/759). ## [Countable Sets](/page/Countable%20Set) ### Definition The fundamental idea is to compare the size of an arbitrary set to $\mathbb{N}$ by looking for bijections. [definition:Countable Set] A set $X$ is **countable** if either $X$ is finite or there exists a bijection $X \to \mathbb{N}$. A set that is not countable is **uncountable**. [/definition] Informally, a countably infinite set is one whose elements can be "listed" as $x_1, x_2, x_3, \ldots$ — the bijection with $\mathbb{N}$ assigns each element its position in the list. The challenge is to show that various familiar sets can (or cannot) be listed in this way. ### Subsets of $\mathbb{N}$ The first result shows that $\mathbb{N}$ has no uncountable subsets — every subset is countable. [quotetheorem:752] The proof enumerates an infinite subset $S \subseteq \mathbb{N}$ in increasing order, using the well-ordering principle at each step to extract the next-smallest element. The resulting map $n \mapsto s_n$ is a bijection because it is strictly increasing (hence injective) and reaches every element of $S$ within finitely many steps (since each $s_n \le n$, there are at most $k - 1$ elements of $S$ below any given $k \in S$). [citeproof:752] ### Equivalent Characterisations Working directly with bijections to $\mathbb{N}$ can be cumbersome. The following result provides more flexible criteria: an injection into $\mathbb{N}$ or a surjection from $\mathbb{N}$ suffices. [quotetheorem:753] The proof cycles through the equivalences. The most subtle direction is (iii) $\implies$ (i): given a surjection $h: \mathbb{N} \to X$, we construct an injection $g: X \to \mathbb{N}$ by sending each $a \in X$ to the *smallest* $n$ with $h(n) = a$ (using the well-ordering principle). This "minimum preimage" trick is a standard technique for converting surjections into injections. [citeproof:753] The equivalent characterisations give us three ways to prove a set is countable: construct a bijection to $\mathbb{N}$, an injection into $\mathbb{N}$, or a surjection from $\mathbb{N}$. We now apply these tools systematically, building up from simple sets to increasingly complex ones. The pattern at each step is the same: reduce the new set to a previously known countable set, using injections or countable unions. ## Building Countable Sets ### Products The set $\mathbb{N} \times \mathbb{N}$ looks "much larger" than $\mathbb{N}$ — it is two-dimensional rather than one-dimensional. Remarkably, it has the same cardinality. [quotetheorem:754] Two proofs are presented. The first, via the injection $(x, y) \mapsto 2^x 3^y$, uses the [Fundamental Theorem of Arithmetic](/theorems/730) to guarantee injectivity — distinct pairs produce distinct prime factorisations. The second constructs an explicit bijection by traversing the grid $\mathbb{N} \times \mathbb{N}$ along successive anti-diagonals: $(1,1), (2,1), (1,2), (3,1), (2,2), (1,3), \ldots$. Both approaches have their merits: the injection proof is shorter, while the diagonal enumeration is constructive and generalises to $\mathbb{Z} \times \mathbb{Z}$ and beyond. [citeproof:754] Since $\mathbb{Z}$ is countable (via the bijection $0 \mapsto 1, 1 \mapsto 2, -1 \mapsto 3, 2 \mapsto 4, -2 \mapsto 5, \ldots$), and $\mathbb{Z} \times \mathbb{Z}$ injects into $\mathbb{N} \times \mathbb{N}$ componentwise, we get that $\mathbb{Z} \times \mathbb{Z}$ is countable. By induction, $\mathbb{Z}^k$ is countable for any $k \in \mathbb{N}$. ### Countable Unions The most powerful closure property of countable sets is that countable unions of countable sets remain countable. [quotetheorem:755] The proof constructs an injection from $\bigcup_{i \in I} A_i$ into $\mathbb{N} \times \mathbb{N}$ by pairing each element $x$ with two numbers: the index of the set containing $x$ (choosing the smallest such index via the well-ordering principle, to handle overlaps) and the position of $x$ within that set. Since $\mathbb{N} \times \mathbb{N}$ is countable by the [Countability of Product of Natural Numbers](/theorems/754), the union is countable. The well-ordering step is essential — without it, an element in multiple sets would produce multiple images, and $h$ would not be well-defined. [citeproof:755] ### The Rationals are Countable With the countable union theorem in hand, the countability of $\mathbb{Q}$ follows quickly. [quotetheorem:756] The proof decomposes $\mathbb{Q} = \bigcup_{n \in \mathbb{N}} \{m/n : m \in \mathbb{Z}\}$. Each slice is a copy of $\mathbb{Z}$ (hence countable), and there are countably many slices (indexed by $\mathbb{N}$). The [Countable Union of Countable Sets](/theorems/755) gives the result. Despite having a dense linear order (between any two rationals lies another rational), $\mathbb{Q}$ is no larger than $\mathbb{N}$. [citeproof:756] ### Algebraic Numbers are Countable How far does countability extend? The rationals are all roots of degree-1 polynomials $qx - p = 0$, but there are many more numbers satisfying polynomial equations: $\sqrt{2}$ satisfies $x^2 - 2 = 0$, $\sqrt[3]{5}$ satisfies $x^3 - 5 = 0$, and so on. The set of all *algebraic* numbers — roots of *any* polynomial with integer coefficients — is vastly larger than $\mathbb{Q}$, yet it is still countable. The proof pushes the same technique one level further: each polynomial is determined by finitely many integer coefficients, so the set of polynomials is countable; each polynomial has finitely many roots; and a countable union of finite sets is countable. [quotetheorem:757] The proof proceeds in layers. First, polynomials of fixed degree $d$ with integer coefficients are parametrised by $\mathbb{Z}^{d+1}$ (via the coefficient map), which is countable. Then the set of all integer polynomials is a countable union over degrees. Finally, the algebraic numbers are a countable union of finite sets (each polynomial has finitely many roots), hence countable by the [Countable Union of Countable Sets](/theorems/755). This argument illustrates a general principle: objects defined by finitely many integer parameters are countable. [citeproof:757] At this point, a pattern has emerged: every set we have tested — $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{N} \times \mathbb{N}$, $\mathbb{Q}$, the algebraic numbers — turns out to be countable. The techniques are always the same: construct an injection into $\mathbb{N}$ (often via the [Fundamental Theorem of Arithmetic](/theorems/730)), or write the set as a [countable union of countable sets](/theorems/755). One might begin to suspect that every infinite set is countable — that there is only one "size" of infinity. The next section shows this is spectacularly false. ## Uncountable Sets ### $\mathbb{R}$ is Uncountable Having established that $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, and the algebraic numbers are all countable, a natural question arises: is *every* infinite set countable? Cantor's celebrated diagonal argument shows the answer is no. [quotetheorem:758] The diagonal argument constructs a real number $r$ that differs from the $n$-th listed real in the $n$-th decimal digit, guaranteeing $r \ne r_n$ for every $n$. The digits $1$ and $2$ are chosen (rather than, say, $0$ and $9$) to avoid the decimal non-uniqueness issue ($0.999\ldots = 1.000\ldots$), ensuring $r$ has a unique decimal representation. The argument actually proves the stronger statement that $(0, 1)$ is uncountable, from which the uncountability of $\mathbb{R}$ follows immediately (since a subset of a countable set is countable by the [Subsets of Natural Numbers are Countable](/theorems/752) argument). [citeproof:758] This result forces us to rethink everything we know about the relationship between $\mathbb{Q}$ and $\mathbb{R}$. In the [Reals chapter](/page/Cambridge%20Part%20IA%20Numbers%20and%20Sets), we proved that [the rationals are dense](/theorems/740): between any two reals there is a rational. Intuitively, $\mathbb{Q}$ is "everywhere" in $\mathbb{R}$ — there are no gaps from the perspective of approximation. Yet $\mathbb{Q}$ is countable and $\mathbb{R}$ is uncountable, so in a precise sense, $\mathbb{Q}$ is infinitesimally small compared to $\mathbb{R}$. Density says nothing about cardinality: a set can be "everywhere" without being "large." This is one of the deepest tensions in analysis, and it explains why measure theory (which assigns $\mathbb{Q}$ measure zero despite its density) eventually becomes essential. The uncountability of $\mathbb{R}$ also provides a second, non-constructive proof of a result we proved constructively in the previous chapter using [Liouville's number](/theorems/747). ### Uncountably Many Transcendentals The countability of algebraic numbers, combined with the uncountability of $\mathbb{R}$, immediately gives a non-constructive proof that transcendental numbers exist in abundance. [quotetheorem:763] The proof is a clean two-line contradiction: if the transcendentals were countable, the reals would be a union of two countable sets (algebraic and transcendental), hence countable — contradicting [Cantor's diagonal argument](/theorems/758). This gives a second proof of the existence of transcendental numbers (complementing the explicit construction of the [Liouville number](/theorems/747)), but it is *non-constructive*: it tells us transcendentals exist without naming a single one. [citeproof:763] ### Cantor's Theorem: No Set Bijects with its Power Set The uncountability of $\mathbb{R}$ is a special case of a much more general phenomenon: for *any* set $X$, the power set $\mathcal{P}(X)$ is strictly larger. [quotetheorem:759] The proof is a diagonal argument in its purest form. Given *any* function $f: X \to \mathcal{P}(X)$, the "anti-diagonal" set $S = \{x \in X : x \notin f(x)\}$ cannot be $f(a)$ for any $a$: if $a \in S$, then $a \notin f(a) = S$ (contradiction); if $a \notin S$, then $a \in S$ (contradiction). The structural similarity to the proof of the [Uncountability of the Reals](/theorems/758) is not a coincidence — both are instances of the same abstract argument. As a corollary, there is no "set of all sets": if a universal set $V$ existed, the surjection $V \to \mathcal{P}(V)$ given by $x \mapsto \{x\}$ would violate Cantor's theorem. [citeproof:759] Applied to $X = \mathbb{N}$: the [Power Set Cardinality](/theorems/749) theorem shows $|\mathcal{P}(\{1, \ldots, n\})| = 2^n > n$ for finite sets, and Cantor's theorem extends this strict inequality to infinite sets. In particular, $\mathcal{P}(\mathbb{N})$ is uncountable. One can verify this directly by constructing an injection from $(0, 1)$ into $\mathcal{P}(\mathbb{N})$ via binary expansions: the real $0.b_1 b_2 b_3 \ldots$ (with $b_i \in \{0, 1\}$, avoiding infinite tails of $1$s) maps to $\{n \in \mathbb{N} : b_n = 1\}$. Cantor's theorem tells us what *cannot* exist (a surjection from $X$ to $\mathcal{P}(X)$), and the diagonal argument tells us what *cannot* exist (a bijection from $\mathbb{N}$ to $\mathbb{R}$). But in many situations we want to show that a bijection *does* exist, and the only tools we have are injections in both directions. The final theorem of this course addresses exactly this situation: if we can inject $A$ into $B$ *and* inject $B$ into $A$, does a bijection between them necessarily exist? ## The Schröder-Bernstein Theorem ### Motivation In many situations, we can construct injections $f: A \to B$ and $g: B \to A$ without having an explicit bijection. Does the existence of two injections guarantee the existence of a bijection? The answer is yes, and it is far from obvious. [example:Bijection Between Intervals] Is there a bijection from $[0, 1]$ to $[0, 1] \cup [2, 3]$? The set $[0, 1] \cup [2, 3]$ looks "twice as big," yet we can construct injections in both directions: $f: [0,1] \to [0,1] \cup [2,3]$ by $f(x) = x$, and $g: [0,1] \cup [2,3] \to [0,1]$ by $g(x) = x/3$. The Schröder-Bernstein theorem guarantees a bijection exists — though constructing it explicitly is non-trivial. [/example] ### The Theorem [quotetheorem:760] The proof partitions each set into three classes based on "ancestor sequences" — chains of preimages alternating between $A$ and $B$ via $g^{-1}$ and $f^{-1}$. Each element's ancestor sequence either terminates in $A$ (class $A_A$), terminates in $B$ (class $A_B$), or runs indefinitely (class $A_\infty$). The bijection $h$ uses $f$ on $A_A$ and $A_\infty$ (where the $A$-ancestry ensures $f$ maps into the corresponding $B$-class) and $g^{-1}$ on $A_B$ (where the $B$-ancestry ensures $g^{-1}$ maps into $B_B$). The key insight is that the ancestor classification is invariant under the maps — applying $f$ or $g$ shifts the ancestor sequence by one step without changing its termination behaviour. [citeproof:760] ## Summary of Proof Techniques The proof techniques in this chapter illustrate a recurring theme from the entire course: the interplay between *construction* and *contradiction*. To show a set is countable, we construct an explicit injection or listing — this is direct, constructive reasoning of the kind introduced in Chapter 1. To show a set is uncountable, we argue by contradiction: we assume a listing exists and derive an impossibility, exactly as we did to prove the [irrationality of $\sqrt{2}$](/theorems/739) and the [infinitude of primes](/theorems/724). The diagonal argument — Cantor's great invention — is a proof by contradiction with a specific combinatorial structure that appears nowhere else in this course, yet echoes the self-referential reasoning of Russell's paradox. The techniques fall into complementary toolkits. **To show $X$ is countable:** (a) Construct an explicit bijection or listing $x_1, x_2, x_3, \ldots$ of the elements of $X$. (b) Construct an injection $X \to \mathbb{N}$ (by the [Equivalent Characterisations of Countability](/theorems/753)). (c) Write $X$ as a countable union of countable sets (by the [Countable Union of Countable Sets](/theorems/755)). (d) If $X \subseteq \mathbb{R}$ or $X$ is "near" $\mathbb{R}$, use the [Countability of the Rationals](/theorems/756) as an intermediate step. **To show $X$ is uncountable:** (a) Use a diagonal argument directly on $X$ (as for $\mathbb{R}$). (b) Construct an injection from a known uncountable set into $X$ (since subsets of countable sets are countable, an injection from an uncountable set into $X$ forces $X$ to be uncountable).