These are notes for the Cambridge Part IA course Numbers and Sets, 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.

p.

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 and series, decimal expansions, and the irrationality of $e$. Sets, Functions 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

h

at 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 resu

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 independent

le illustrates the method.

[example:Divisibi

^

3$.

We factor algebraically:
\begin{align*}
n^3 - n = n(n^2 - 1) = n(n-1)(n+1) = (n-1)

\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 assump

s 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 \mat

even (i.e. $n$ is odd), then $n^2$ is not even.

Suppose $n$ is odd. Then $n =

n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1,
\end{align*}
which is odd. Henc

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 consist

nfinitude of primes, and

or" mean inclusive or excl

$ ("$A$ and $B$

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 on

$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 o

initions capture the most importan

d only if $A$ i

P

o 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 w

$ have the same truth value (both true or both false), and false otherwise.
[/defi

lently, $A \iff B$ means that both $A \implies B$ and $B \implies A$ hold.

Truth Tables

The truth values of compound

th table is:

| $P$ | $Q$ | $P \wedge Q$ | $P \vee Q$ | $P \implies Q$ | $P \iff Q$

--|----------|
| T | T | T | T | T | T

| F | F | F | T | T | T |

De Morgan's Laws

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 di

t

c

ds for all elements, or for at least one element. The quantifiers $\forall$ and $\exists$ formalise these assertions.

[definition:Universal Quantifier]
The statement $\forall

)$ ("for all $x$ in $X$, $P(x)$ holds

("there exists $x$ in $X$ such that $P(x)$ holds") is true if and only if $P(x)$ is true for at leas

ifiers reduce to connectives:
\begin{align*}
\forall x \in X,; P(x) &\iff P(x_1) \we

end{align*}
This corresp

on. The fundamental rule for negating quantified statements mirrors De Morgan's La

eg(\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 nega

[example:Negating Continuity]
The $\varepsilon$-$\delta$ definition of continuity of a function $f: \mathbb{R} \to \mathbb{R}$ at a point $x$ stat

l

lign*}

To ne

ign*}
&\neg\bigl(\forall \varepsilon > 0,; \exists \delta > 0,; \forall y \in \mathbb{R},; |x - y| < \delta \implies |f(x) - f(y)| < \varepsilon\bigr

)

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), proof by contrapositive (the reverse direction of Quadratic Residue $-1$), proof by contradiction (the infinitude of primes), and induction in bot

n

t

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$

ii) (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

e

\le n$," which bundles together all predecessors.

r

a property holds somewhere, it holds at a smallest place. This is the well-ordering principle, and it turns out to be log

h $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 mi

construct a contr

I

ors, 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 t

a

d

mid b$, if there exists $c \in \mathbb{Z}$ such that $b = ac$. [/definition] For any $b \in \mathbb{Z}$, the inte

\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 structu

b

e 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]

f 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 N

ts 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) turns out to depend on expressing $\gcd(p, a)$ as a linear combination of $p$ and $a$, which in

s

ll 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

b

that is far more useful in proofs.

[definition:Greatest Common D

ition]

Condition (ii) is t

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 proceed

n

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 behaviour.

[citep

ithm** 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 termina

equence of non-negative integers, which must reach zero

y the well-ordering princ

et of non-negative integers below $b$).

[example:Euclid Algorithm On 372 And 162]
We compute $\gcd(372, 162)$. Applying the division algorithm repe

\cdot 18 + 12, \
18 &= 1 \cdot 12 + 6, \
12 &= 2 \cdot

, 162) = 6$.

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 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 equati

*

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

t

smallest positi

of $a$ and $b$, and show it satisfies the GCD axioms by a divisibility argument using the division algorithm. The minimality proof

l

ection is a one-line argument: if $h = \gcd(a,b)$ divides bo

The Fundamenta

metic

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 in an essen

\nmid a$, then $\g

egers $x, y$. Multip

r cancelling and a

u

irely new algebraic toolkit. Modular arithmetic also connects back to the GCD theory: the Units Modulo n result shows that invertibility modulo $n$ is equivalent to coprimality, and the Chinese Remainder Theorem 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

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 (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. 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 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: 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 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 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: 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 characterises solvable linear equations, the Fermat-Euler theorem controls powers modulo $n$, and the Chinese Remainder Theorem 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.

Decryption works because $ed \equiv 1 \pmod{\varphi(n)}$, so $ed = 1 + \lambda \varphi(n)$ for some integer $\lambda$. By the Fermat-Euler Theorem (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 (no infinitely large or infinitely small reals), the density of $\mathbb{Q}$ (rationals are everywhere despite having gaps), the existence of $\sqrt{2}$ (the gaps are filled), and the Monotone Convergence Theorem (bounded monotone sequences converge). The chapter closes with two celebrated applications: the irrationality of $e$ and the existence of transcendental numbers.

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), 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 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 leastness. 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 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) 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 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, 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

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 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 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 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: 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 and the reals are uncountable, 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 and the Inclusion-Exclusion Principle — 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 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) 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 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). 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 defines a function $n \mapsto (q, r)$; the decimal expansion 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, 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

alence 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 (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}$ — 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 and Cantor's Theorem.

Countable Sets

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 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, 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 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 degr

s $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. 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), or write the set as a countable union of countable sets. 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 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, we proved that the rationals are dense: 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.

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. This gives a second proof of the existence of transcendental numbers (complementing the explicit construction of the Liouville number), 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 is no

e — 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 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}$ and the infinitude of primes. 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).

(c) Write $X$ as a countable union of countable sets (by the [Countable Union of Countable

5)).

(d) If $X \subseteq \mathbb{R}$ or $X$ is "near" $\mathbb{R}$, use the Countability of the Rationals 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).