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.