Calculus teaches how to use limits, derivatives and integrals. Real analysis asks why they work at all: what a real number is, what "gets arbitrarily close" means, and which hidden assumption makes the Intermediate Value Theorem or the convergence of $\sum 1/n^2$ true. The answer, again and again, is one property of $\mathbb{R}$ that the rationals $\mathbb{Q}$ lack: completeness, the fact that $\mathbb{R}$ has no gaps. This course rebuilds single-variable calculus on that one axiom, with proofs. It follows the standard undergraduate route of Abbott's Understanding Analysis, with Rudin's Principles of Mathematical Analysis, Bartle and Sherbert's Introduction to Real Analysis, Tao's Analysis I and Spivak's Calculus as parallel reading. This first post sets up the language of proof, the axioms of an ordered field, the supremum and the Axiom of Completeness, and its first consequences: the Archimedean property, density of $\mathbb{Q}$ , the existence of $\sqrt{2}$ , nested intervals, and the fact that $\mathbb{R}$ is uncountable.

Series map: 00 The Real Numbers & Completeness (this post) → 01 Sequences & Series → 02 Topology of ℝ & Continuity → 03 Differentiation & Taylor's Theorem → 04 The Riemann Integral → 05 Uniform Convergence & Power Series.

Learning Outcome

Read and write statements with the quantifiers "for all" ( $\forall$ ) and "there exists" ( $\exists$ ), and negate nested statements such as "for every $\varepsilon > 0$ there is a $\delta > 0$ …" correctly.
Use the three core proof patterns — direct proof, proof by contradiction, and induction — and prove that $\sqrt{2}$ is irrational.
List the ordered field axioms and prove the triangle inequality from them.
Define upper bound, supremum and infimum, and use the $\varepsilon$ -characterization of the supremum.
State the Axiom of Completeness and explain why $\mathbb{Q}$ fails it.
Prove the Archimedean property, the density of $\mathbb{Q}$ in $\mathbb{R}$ , and the existence of $\sqrt{2}$ in $\mathbb{R}$ .
State and prove the Nested Interval Property.
Show that $\mathbb{Q}$ is countable and that $\mathbb{R}$ is uncountable (Cantor's diagonal argument), and describe the Cantor set.

Chapter 1 — Logic and proof

Analysis is written in a small, precise language. Most mistakes in a first analysis course are not mistakes about numbers; they are mistakes about quantifiers.

Terminology

Statement — a sentence that is either true or false, e.g. " $7$ is prime".
Implication " $P \Rightarrow Q$ " — "if $P$ then $Q$ ". It is false only when $P$ is true and $Q$ is false.
Converse of $P \Rightarrow Q$ — the statement $Q \Rightarrow P$ . It is a different statement and may be false.
Contrapositive of $P \Rightarrow Q$ — the statement $\neg Q \Rightarrow \neg P$ . It is logically equivalent to the original.
Universal quantifier $\forall$ — "for all". Existential quantifier $\exists$ — "there exists (at least one)".
Counterexample — one specific object that shows a "for all" statement is false.

Negating quantified statements

The two rules are:

$\neg\big(\forall x,\ P(x)\big) \iff \exists x,\ \neg P(x), \qquad \neg\big(\exists x,\ P(x)\big) \iff \forall x,\ \neg P(x).$

To negate a nested statement, move the $\neg$ from left to right, flipping every quantifier it passes, and negate the final condition. The definition of "the sequence $(a_n)$ converges to $a$ " (see Real Analysis 01) is

$\forall \varepsilon > 0\ \ \exists N \in \mathbb{N}\ \ \forall n \ge N:\ \ \lvert a_n - a \rvert < \varepsilon.$

Its negation, " $(a_n)$ does not converge to $a$ ", is

$\exists \varepsilon > 0\ \ \forall N \in \mathbb{N}\ \ \exists n \ge N:\ \ \lvert a_n - a \rvert \ge \varepsilon.$

In words: there is one fixed tolerance $\varepsilon$ such that, however far out you go, some later term is still at least $\varepsilon$ away from $a$ .

The same mechanical rule applies to continuity (see Real Analysis 02). " $f$ is continuous at $c$ " is $\forall \varepsilon > 0\ \exists \delta > 0\ \forall x:\ \lvert x - c\rvert < \delta \Rightarrow \lvert f(x) - f(c)\rvert < \varepsilon$ . Its negation is

$\exists \varepsilon > 0\ \ \forall \delta > 0\ \ \exists x:\ \ \lvert x - c \rvert < \delta \ \text{ and } \ \lvert f(x) - f(c) \rvert \ge \varepsilon.$

Note that the negation of an implication $A \Rightarrow B$ is " $A$ and not $B$ ", not another implication.

Watch out: the order of quantifiers matters. " $\forall x\ \exists y:\ y > x$ " (every real number has a larger one) is true in $\mathbb{R}$ . " $\exists y\ \forall x:\ y > x$ " (one number is larger than all of them) is false. Swapping $\forall$ and $\exists$ changes the meaning completely. In analysis the classic example is uniform continuity (Real Analysis 02), which differs from continuity only by the position of one quantifier.

Three proof patterns

Direct proof. Assume the hypothesis, reach the conclusion by valid steps. Example: if $m$ and $n$ are even, $m + n$ is even. Write $m = 2a$ , $n = 2b$ ; then $m + n = 2(a + b)$ .

Contrapositive and contradiction. To prove $P \Rightarrow Q$ you may prove $\neg Q \Rightarrow \neg P$ instead. In a proof by contradiction you assume the statement is false and derive something impossible. Example: if $n^2$ is even, then $n$ is even. Contrapositive: if $n$ is odd, $n = 2k + 1$ , then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ is odd.

Induction. To prove $P(n)$ for all $n \in \mathbb{N} = \{1, 2, 3, \dots\}$ , prove the base case $P(1)$ and the inductive step $P(n) \Rightarrow P(n+1)$ . This works because of the well-ordering principle: every nonempty subset of $\mathbb{N}$ has a least element (if $P$ failed somewhere, look at the least failure).

Example (Bernoulli's inequality). For every $x \ge -1$ and every $n \in \mathbb{N}$ , $(1 + x)^n \ge 1 + nx$ .

Proof. For $n = 1$ both sides equal $1 + x$ . Suppose $(1+x)^n \ge 1 + nx$ . Since $1 + x \ge 0$ , multiplying both sides by $1 + x$ keeps the inequality:

$(1+x)^{n+1} \ge (1 + nx)(1 + x) = 1 + (n+1)x + nx^2 \ge 1 + (n+1)x,$

because $nx^2 \ge 0$ . $\blacksquare$

The hypothesis $x \ge -1$ is used exactly once, to multiply an inequality by a non-negative number. Bernoulli's inequality is the standard tool for showing $r^n \to 0$ when $\lvert r \rvert < 1$ (Real Analysis 01).

The square root of 2 is irrational

Theorem. There is no rational number $r$ with $r^2 = 2$ .

Proof. Suppose, for contradiction, that $r = p/q$ with integers $p, q$ , $q \ne 0$ , and $r^2 = 2$ . Cancel common factors, so that $p$ and $q$ are not both even. Then $p^2 = 2q^2$ , so $p^2$ is even, and by the contrapositive example above $p$ is even: $p = 2k$ . Substituting, $4k^2 = 2q^2$ , so $q^2 = 2k^2$ is even, and $q$ is even. Now $p$ and $q$ are both even, contradicting the choice of $p/q$ in lowest terms. $\blacksquare$

This is the first sign that $\mathbb{Q}$ has gaps: the rationals whose square is less than $2$ creep up towards a point that is not there.

Chapter 2 — Ordered fields and absolute value

Terminology

Field — a set $F$ with two operations $+$ and $\cdot$ satisfying the field axioms below.
Ordered field — a field with a relation $<$ satisfying the order axioms below.
Absolute value — $\lvert x \rvert = x$ if $x \ge 0$ and $\lvert x \rvert = -x$ if $x < 0$ .
Distance between $x$ and $y$ — the number $\lvert x - y \rvert$ .

The axioms

A field satisfies, for all $x, y, z$ :

Axiom	Addition	Multiplication
Closure	$x + y \in F$	$xy \in F$
Associative	$(x+y)+z = x+(y+z)$	$(xy)z = x(yz)$
Commutative	$x + y = y + x$	$xy = yx$
Identity	$x + 0 = x$	$1 \cdot x = x$ , with $1 \ne 0$
Inverse	some $-x$ has $x + (-x) = 0$	if $x \ne 0$ , some $x^{-1}$ has $x x^{-1} = 1$
Distributive	$x(y+z) = xy + xz$	(links the two operations)

An ordered field also has a relation $<$ such that:

Trichotomy: for all $x, y$ exactly one of $x < y$ , $x = y$ , $y < x$ holds.
Transitivity: $x < y$ and $y < z$ imply $x < z$ .
Addition: $x < y$ implies $x + z < y + z$ .
Multiplication: $x < y$ and $0 < z$ imply $xz < yz$ .

Everything in high-school algebra follows. For example, $x^2 \ge 0$ for all $x$ , and $0 < 1$ (since $1 = 1^2$ and $1 \ne 0$ ). If $x < y$ and $z < 0$ then $yz < xz$ : multiplying by a negative number flips an inequality.

Both $\mathbb{Q}$ and $\mathbb{R}$ are ordered fields. So these axioms cannot be what distinguishes them; Chapter 3 adds the one axiom that does.

The triangle inequality

Three facts about absolute value, all checked by cases on the signs: $\lvert xy \rvert = \lvert x \rvert \lvert y \rvert$ ; $-\lvert x \rvert \le x \le \lvert x \rvert$ ; and for $a \ge 0$ , $\lvert x \rvert \le a \iff -a \le x \le a$ .

Theorem (triangle inequality). For all real $x, y$ : $\lvert x + y \rvert \le \lvert x \rvert + \lvert y \rvert$ .

Proof. Add $-\lvert x \rvert \le x \le \lvert x \rvert$ and $-\lvert y \rvert \le y \le \lvert y \rvert$ :

$-(\lvert x \rvert + \lvert y \rvert) \le x + y \le \lvert x \rvert + \lvert y \rvert.$

By the third fact with $a = \lvert x \rvert + \lvert y \rvert$ , this says $\lvert x + y \rvert \le \lvert x \rvert + \lvert y \rvert$ . $\blacksquare$

Two forms are used constantly:

Distance form: $\lvert a - b \rvert \le \lvert a - c \rvert + \lvert c - b \rvert$ (put $x = a - c$ , $y = c - b$ ). Going from $a$ to $b$ via $c$ is never shorter.
Reverse triangle inequality: $\big\lvert \lvert x \rvert - \lvert y \rvert \big\rvert \le \lvert x - y \rvert$ . (From $\lvert x \rvert = \lvert (x - y) + y \rvert \le \lvert x - y \rvert + \lvert y \rvert$ , and the same with $x$ and $y$ swapped.)

Trick: almost every $\varepsilon$ proof in this course is "add and subtract a middle term, then use the triangle inequality". When you see $\lvert a_n b_n - ab \rvert$ , write it as $\lvert a_n b_n - a_n b + a_n b - ab \rvert$ and split.

Proving that two numbers are equal

Lemma. Two real numbers $a$ and $b$ are equal if and only if for every $\varepsilon > 0$ , $\lvert a - b \rvert < \varepsilon$ .

Proof. If $a = b$ then $\lvert a - b \rvert = 0 < \varepsilon$ . Conversely, suppose $a \ne b$ . Then $\varepsilon_0 = \lvert a - b \rvert > 0$ , and $\lvert a - b \rvert < \varepsilon_0$ is false. $\blacksquare$

This is how analysis proves equalities: not by computing both sides, but by showing their distance is smaller than any positive tolerance.

Chapter 3 — Supremum, infimum and completeness

Terminology

Upper bound — $b$ is an upper bound of $A \subseteq \mathbb{R}$ if $a \le b$ for every $a \in A$ . $A$ is bounded above if it has one.
Lower bound, bounded below — the same with $\ge$ . Bounded means bounded above and below.
Supremum (least upper bound) — $s = \sup A$ if (i) $s$ is an upper bound of $A$ , and (ii) $s \le b$ for every upper bound $b$ of $A$ .
Infimum (greatest lower bound) — $\inf A$ , defined the same way with the inequalities reversed.
Maximum — an element of $A$ that is an upper bound of $A$ . A set may have a supremum but no maximum.

A supremum is unique when it exists: if $s_1$ and $s_2$ are both least upper bounds, then $s_1 \le s_2$ and $s_2 \le s_1$ .

Examples

Set $A$	$\sup A$	Attained (a max)?	$\inf A$
$[0, 1]$	$1$	yes	$0$
$(0, 1)$	$1$	no	$0$
$\{1 - 1/n : n \in \mathbb{N}\}$	$1$	no	$0$ (a min)
$\{1/n : n \in \mathbb{N}\}$	$1$	yes	$0$ (not a min)
$\mathbb{N}$	none (not bounded above)	—	$1$

For $A = \{1 - 1/n\}$ : $1$ is an upper bound since $1/n > 0$ . If $b < 1$ , the Archimedean property (Chapter 4) gives $n$ with $1/n < 1 - b$ , so $1 - 1/n > b$ and $b$ is not an upper bound. For example, $b = 0.85$ is beaten by $1 - \tfrac17 = \tfrac67 \approx 0.857$ (and $n = 7$ is the first index that works, since $1 - \tfrac16 \approx 0.833$ ). Hence $\sup A = 1$ , and $1 \notin A$ .

The epsilon characterization

Lemma. Let $s$ be an upper bound of $A$ . Then $s = \sup A$ if and only if for every $\varepsilon > 0$ there is some $a \in A$ with $s - \varepsilon < a$ .

Proof. ( $\Rightarrow$ ) Let $\varepsilon > 0$ . Since $s - \varepsilon < s$ and $s$ is the least upper bound, $s - \varepsilon$ is not an upper bound. So some $a \in A$ has $a > s - \varepsilon$ .

( $\Leftarrow$ ) Let $b$ be any upper bound with $b < s$ . Put $\varepsilon = s - b > 0$ . By hypothesis some $a \in A$ has $a > s - \varepsilon = b$ , contradicting that $b$ is an upper bound. So every upper bound $b$ satisfies $b \ge s$ , and $s = \sup A$ . $\blacksquare$

In pictures: nothing in $A$ lies to the right of $s$ , but every window $(s - \varepsilon, s]$ , however narrow, contains a point of $A$ .

The Axiom of Completeness

Axiom of Completeness (least upper bound property). Every nonempty set of real numbers that is bounded above has a supremum in $\mathbb{R}$ .

$\mathbb{R}$ is defined to be an ordered field that satisfies this axiom. (Such a field exists and is unique up to an order-preserving isomorphism; the standard constructions use Dedekind cuts, as in Rudin Chapter 1, or Cauchy sequences of rationals, as in Tao Chapter 5. This course takes the axiom as the starting point, as Abbott does.)

The axiom for infima follows. If $A$ is nonempty and bounded below, then $-A = \{-a : a \in A\}$ is nonempty and bounded above, and $\inf A = -\sup(-A)$ .

Why $\mathbb{Q}$ fails the axiom. Let $S = \{r \in \mathbb{Q} : r^2 < 2\}$ . It is nonempty ( $1 \in S$ ) and bounded above by $2$ . Suppose it had a least upper bound $s$ in $\mathbb{Q}$ . The argument in Chapter 4 (existence of $\sqrt{2}$ ) shows that $s^2 < 2$ and $s^2 > 2$ are both impossible, so $s^2 = 2$ ; but no rational squares to $2$ . So $S$ has no supremum in $\mathbb{Q}$ : the rationals have a hole exactly where $\sqrt{2}$ should be. Concretely, $1, 1.4, 1.41, 1.414, \ldots$ are in $S$ (their squares are below $2$ ; for example $1.414^2 = 1.999396$ ), while $1.5, 1.42, 1.415, \ldots$ are rational upper bounds ( $1.415^2 = 2.002225$ ). Every rational upper bound can be improved, and the two lists close in on a point that $\mathbb{Q}$ does not contain.

Working with suprema

Two small results, each proved with the lemma above, are used often.

Shift: for $c \in \mathbb{R}$ , $\sup(A + c) = \sup A + c$ , where $A + c = \{a + c : a \in A\}$ . (If $s = \sup A$ , then $s + c$ is an upper bound of $A + c$ , and for each $\varepsilon$ some $a > s - \varepsilon$ gives $a + c > (s + c) - \varepsilon$ .)
Order: if $A \subseteq B$ , $A$ is nonempty and $B$ is bounded above, then $\sup A \le \sup B$ . (Every upper bound of $B$ is an upper bound of $A$ .)

Common pitfall: assuming $\sup A \in A$ . The supremum of $(0,1)$ is $1$ , which is not in the set. Proofs that pick "the largest element of $A$ " are wrong unless $A$ is finite or known to have a maximum.

Chapter 4 — First consequences of completeness

The Archimedean property

Theorem (Archimedean property).
(i) For every $x \in \mathbb{R}$ there is $n \in \mathbb{N}$ with $n > x$ .
(ii) For every $y > 0$ there is $n \in \mathbb{N}$ with $1/n < y$ .

Proof. (i) Suppose not: then $x$ is an upper bound of $\mathbb{N}$ , so by completeness $\alpha = \sup \mathbb{N}$ exists. Then $\alpha - 1$ is not an upper bound, so some $n \in \mathbb{N}$ has $n > \alpha - 1$ . But then $n + 1 > \alpha$ and $n + 1 \in \mathbb{N}$ , contradicting that $\alpha$ is an upper bound of $\mathbb{N}$ .
(ii) Apply (i) to $x = 1/y$ : some $n > 1/y$ , so $1/n < y$ . $\blacksquare$

This property looks obvious, yet the proof needs completeness: there are ordered fields (for example suitably ordered fields of rational functions) with "infinitely large" elements, where it fails.

Density of the rationals

Theorem (density of $\mathbb{Q}$ ). For all real $a < b$ there is a rational $r$ with $a < r < b$ .

Proof. By the Archimedean property choose $n \in \mathbb{N}$ with $1/n < b - a$ . Let $m$ be the least integer with $m > na$ (it exists by the Archimedean property and well-ordering), so $m - 1 \le na < m$ . Then $a < m/n$ , and

$m \le na + 1 < na + n(b - a) = nb,$

using $1 < n(b - a)$ . So $a < m/n < b$ . $\blacksquare$

The idea: steps of size $1/n$ are shorter than the interval, so one of the points $m/n$ must land inside.

Corollary. The irrationals are dense too: between any $a < b$ there is an irrational number. (Find a rational $r \ne 0$ with $a/\sqrt{2} < r < b/\sqrt{2}$ ; then $r\sqrt{2}$ is irrational and lies in $(a, b)$ .)

Existence of the square root of 2

Theorem. There is $\alpha \in \mathbb{R}$ with $\alpha^2 = 2$ .

Proof sketch. Let $T = \{t \in \mathbb{R} : t^2 < 2\}$ . It is nonempty ( $1 \in T$ ) and bounded above by $2$ (if $t > 2$ then $t^2 > 4$ ). Let $\alpha = \sup T$ ; note $\alpha \ge 1$ . Show that the other two cases of trichotomy are impossible.

Case $\alpha^2 < 2$ . For $n \in \mathbb{N}$ ,

$\left(\alpha + \tfrac{1}{n}\right)^2 = \alpha^2 + \frac{2\alpha}{n} + \frac{1}{n^2} \le \alpha^2 + \frac{2\alpha + 1}{n}.$

Choose $n$ with $\frac{1}{n} < \frac{2 - \alpha^2}{2\alpha + 1}$ (Archimedean property). Then $(\alpha + 1/n)^2 < 2$ , so $\alpha + 1/n \in T$ , contradicting that $\alpha$ is an upper bound.

Case $\alpha^2 > 2$ . Now $\left(\alpha - \tfrac{1}{n}\right)^2 > \alpha^2 - \frac{2\alpha}{n}$ . Choose $n$ with $\frac{1}{n} < \frac{\alpha^2 - 2}{2\alpha}$ ; then $(\alpha - 1/n)^2 > 2$ , and $\alpha - 1/n > 0$ . Any $t \in T$ with $t > \alpha - 1/n > 0$ would have $t^2 > (\alpha - 1/n)^2 > 2$ , which is impossible. So $\alpha - 1/n$ is an upper bound of $T$ smaller than $\alpha$ — a contradiction.

So $\alpha^2 = 2$ . $\blacksquare$

The same argument, with $\mathbb{Q}$ in place of $\mathbb{R}$ , is the proof that $\{r \in \mathbb{Q} : r^2 < 2\}$ has no supremum in $\mathbb{Q}$ : its supremum would have to square to $2$ . With more algebra it gives $n$ -th roots of every positive real.

The Nested Interval Property

Theorem (Nested Interval Property). For each $n \in \mathbb{N}$ let $I_n = [a_n, b_n]$ be a closed bounded interval, with $I_1 \supseteq I_2 \supseteq I_3 \supseteq \cdots$ . Then $\bigcap_{n=1}^\infty I_n \ne \emptyset$ .

Proof. Nesting means $a_1 \le a_2 \le \cdots$ and $\cdots \le b_2 \le b_1$ , and $a_n \le b_m$ for all $n, m$ (with $k = \max(n,m)$ : $a_n \le a_k \le b_k \le b_m$ ). So the set $A = \{a_n : n \in \mathbb{N}\}$ is nonempty and bounded above by every $b_m$ . Let $x = \sup A$ . Then $a_n \le x$ for all $n$ (upper bound) and $x \le b_m$ for all $m$ (each $b_m$ is an upper bound and $x$ is the least). So $x \in I_n$ for every $n$ . $\blacksquare$

If in addition the lengths $b_n - a_n$ shrink to $0$ , the intersection is exactly one point.

Watch out: both hypotheses are needed. The open intervals $(0, 1/n)$ are nested but their intersection is empty (any $x > 0$ is excluded once $1/n < x$ ). The closed but unbounded intervals $[n, \infty)$ are nested with empty intersection too. And in $\mathbb{Q}$ the property fails: intervals of rationals closing in on $\sqrt{2}$ have no common rational point.

Together with the Archimedean property, the Nested Interval Property is equivalent to the Axiom of Completeness. It is the version used in bisection arguments (Bolzano–Weierstrass in Real Analysis 01, the Intermediate Value Theorem in Real Analysis 02).

Chapter 5 — Countable and uncountable sets

Completeness makes $\mathbb{R}$ enormously larger than $\mathbb{Q}$ , even though both are dense. Cardinality makes "larger" precise.

Terminology

Function $f : A \to B$ — a rule assigning to each $a \in A$ one element $f(a) \in B$ .
One-to-one (injective) — $f(a_1) = f(a_2)$ implies $a_1 = a_2$ .
Onto (surjective) — every $b \in B$ equals $f(a)$ for some $a$ .
Bijection — one-to-one and onto. $A$ and $B$ have the same cardinality, written $A \sim B$ , if a bijection $A \to B$ exists.
Countable — $A \sim \mathbb{N}$ (an infinite list $a_1, a_2, a_3, \dots$ with every element appearing exactly once). Uncountable — infinite and not countable.

The rationals are countable

First, $\mathbb{Z}$ is countable: the list $0, 1, -1, 2, -2, 3, -3, \dots$ is the bijection $f : \mathbb{N} \to \mathbb{Z}$ with $f(n) = (n-1)/2$ for odd $n$ and $f(n) = -n/2$ for even $n$ .

Theorem. $\mathbb{Q}$ is countable.

Proof. For each $n \in \mathbb{N}$ let $A_n$ be the set of rationals that can be written as $\pm p/q$ in lowest terms with integers $p \ge 0$ , $q \ge 1$ and $p + q = n$ . For example $A_1 = \{0\}$ , $A_2 = \{1, -1\}$ , $A_3 = \{1/2, -1/2, 2, -2\}$ . Each $A_n$ is finite, the $A_n$ are disjoint, and every rational lies in exactly one of them. List $A_1$ , then $A_2$ , then $A_3$ , and so on. This list contains every rational exactly once, so it is a bijection with $\mathbb{N}$ . $\blacksquare$

The reals are uncountable

Theorem (Cantor, 1874; diagonal argument 1891). The interval $(0, 1)$ , and hence $\mathbb{R}$ , is uncountable.

Proof. Every $x \in (0,1)$ has a decimal expansion $x = 0.d_1 d_2 d_3 \ldots$ . It is unique if expansions ending in an infinite string of $9$ s are excluded (so $0.4999\ldots$ is written $0.5000\ldots$ ). Suppose $f : \mathbb{N} \to (0,1)$ were onto, and write

$\begin{aligned} f(1) &= 0.\,a_{11}\, a_{12}\, a_{13}\, a_{14} \ldots \\ f(2) &= 0.\,a_{21}\, a_{22}\, a_{23}\, a_{24} \ldots \\ f(3) &= 0.\,a_{31}\, a_{32}\, a_{33}\, a_{34} \ldots \\ &\ \ \vdots \end{aligned}$

Define $x = 0.b_1 b_2 b_3 \ldots$ by $b_n = 2$ if $a_{nn} \ne 2$ and $b_n = 3$ if $a_{nn} = 2$ . This $x$ lies in $(0,1)$ , its expansion has no $9$ s (so it is the unique allowed one), and it differs from $f(n)$ in the $n$ -th digit for every $n$ . So $x \ne f(n)$ for all $n$ , and $f$ is not onto. $\blacksquare$

Since $(0,1) \sim \mathbb{R}$ (for example via $x \mapsto \tan(\pi x - \pi/2)$ ), $\mathbb{R}$ is uncountable. Consequences:

The irrationals $\mathbb{R} \setminus \mathbb{Q}$ are uncountable (if they were countable, $\mathbb{R}$ would be a union of two countable sets, which is countable).
Almost all real numbers are irrational, even though the rationals are dense. Density is about where points are; cardinality is about how many.

Common pitfall: "the diagonal number might equal some $f(n)$ with a different expansion". That is exactly why the proof uses the digits $2$ and $3$ only and excludes trailing $9$ s: the number $x$ has only one decimal expansion, so differing in a digit really means being a different number.

The Cantor set

Start with $C_0 = [0,1]$ . Remove the open middle third to get $C_1 = [0, \tfrac13] \cup [\tfrac23, 1]$ . Remove the open middle third of each piece to get $C_2$ , a union of $4$ intervals of length $\tfrac19$ . In general $C_n$ is a union of $2^n$ closed intervals of length $3^{-n}$ . The Cantor set is $C = \bigcap_{n=0}^\infty C_n$ .

Length removed: at step $k$ you remove $2^{k-1}$ intervals of length $3^{-k}$ , so the total is $\sum_{k=1}^\infty 2^{k-1}/3^k = 1$ . The Cantor set has "length zero".
Many points survive: $0$ , $1$ , $\tfrac13$ , $\tfrac23$ and every endpoint stay forever. So does $\tfrac14$ , which is never an endpoint: in base $3$ , $\tfrac14 = 0.020202\ldots_3$ , since $\sum_{k=1}^\infty 2/9^k = 2/8 = 1/4$ .
Uncountable: $x \in C$ exactly when $x$ has a base- $3$ expansion using only the digits $0$ and $2$ . Replacing each $2$ by $1$ and reading the result in base $2$ maps $C$ onto $[0,1]$ , so $C$ is uncountable.

The Cantor set is the standard example of a set that is "small" in length but "large" in cardinality. It returns in Real Analysis 02 as a closed, compact set that contains no interval.

Practice Exercises

1. Write the negation of: "for every $M > 0$ there is $N \in \mathbb{N}$ such that for all $n \ge N$ , $a_n > M$ " (the definition of $a_n \to \infty$ ).

Solution

"There is $M > 0$ such that for every $N \in \mathbb{N}$ there is $n \ge N$ with $a_n \le M$ ." In words: there is a level $M$ at or below which infinitely many terms stay.

2. Prove by induction that $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ for all $n \in \mathbb{N}$ .

Solution

Base: $1 = \frac{1 \cdot 2}{2}$ . Step: if $1 + \cdots + n = \frac{n(n+1)}{2}$ , then $1 + \cdots + n + (n + 1) = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}$ , which is the formula for $n + 1$ .

3. Prove that $\sqrt{3}$ is irrational.

Solution

First, if $3$ divides $n^2$ then $3$ divides $n$ : otherwise $n = 3k \pm 1$ and $n^2 = 9k^2 \pm 6k + 1$ leaves remainder $1$ on division by $3$ . Now suppose $\sqrt{3} = p/q$ in lowest terms. Then $p^2 = 3q^2$ , so $3$ divides $p$ ; write $p = 3k$ . Then $9k^2 = 3q^2$ , so $q^2 = 3k^2$ and $3$ divides $q$ . Both divisible by $3$ contradicts lowest terms.

4. Find $\sup A$ and $\inf A$ for $A = \left\{ \frac{n}{n+1} : n \in \mathbb{N} \right\}$ and prove your answer for the supremum.

Solution

$\inf A = \frac12$ (the minimum, at $n = 1$ , since $\frac{n}{n+1} = 1 - \frac{1}{n+1}$ increases with $n$ ). $\sup A = 1$ : it is an upper bound since $\frac{n}{n+1} < 1$ . Given $\varepsilon > 0$ , choose $n$ with $\frac{1}{n+1} < \varepsilon$ (Archimedean); then $\frac{n}{n+1} = 1 - \frac{1}{n+1} > 1 - \varepsilon$ . By the $\varepsilon$ -characterization, $\sup A = 1$ . It is not attained.

5. Let $A, B$ be nonempty and bounded above, and $A + B = \{a + b : a \in A, b \in B\}$ . Prove $\sup(A + B) = \sup A + \sup B$ .

Solution

Let $s = \sup A$ , $t = \sup B$ . For $a \in A$ , $b \in B$ : $a + b \le s + t$ , so $s + t$ is an upper bound. Given $\varepsilon > 0$ , pick $a > s - \varepsilon/2$ and $b > t - \varepsilon/2$ ; then $a + b > (s + t) - \varepsilon$ . By the $\varepsilon$ -characterization, $\sup(A + B) = s + t$ .

6. Show that the intervals $I_n = (0, 1/n]$ are nested but have empty intersection. Which hypothesis of the Nested Interval Property fails?

Solution

$1/(n+1) < 1/n$ gives $I_{n+1} \subseteq I_n$ . If $x \le 0$ , $x \notin I_1$ . If $x > 0$ , choose $n$ with $1/n < x$ (Archimedean); then $x \notin I_n$ . So the intersection is empty. The intervals are not closed (the left endpoint $0$ is missing).

7. Show that the set of all finite subsets of $\mathbb{N}$ is countable, but the set $\mathcal{P}(\mathbb{N})$ of all subsets of $\mathbb{N}$ is not.

Solution

Finite subsets: for each $n$ , the subsets of $\{1, \dots, n\}$ form a finite collection ( $2^n$ sets), and every finite subset of $\mathbb{N}$ belongs to one of these collections. List the first collection, then the new sets of the second, and so on; this lists every finite subset exactly once. All subsets: suppose $f : \mathbb{N} \to \mathcal{P}(\mathbb{N})$ were onto. Let $B = \{n : n \notin f(n)\}$ . If $B = f(m)$ , then $m \in B \iff m \notin f(m) = B$ , a contradiction. (This is Cantor's theorem, the same diagonal idea.)

Cheat-sheet

Idea	Statement	Used for
Negation	flip each quantifier, negate the final condition	"does not converge", "not continuous"
Triangle inequality	$\lvert x + y\rvert \le \lvert x\rvert + \lvert y\rvert$	splitting every $\varepsilon$ estimate
Reverse triangle	$\big\lvert \lvert x\rvert - \lvert y\rvert\big\rvert \le \lvert x - y\rvert$	lower bounds on $\lvert a_n \rvert$
Equality lemma	$a = b$ iff $\lvert a - b\rvert < \varepsilon$ for all $\varepsilon > 0$	proving limits are unique
Supremum	least upper bound; may not be in the set	defining limits, integrals
$\varepsilon$ -test	upper bound $s$ , and some $a > s - \varepsilon$ for each $\varepsilon$	every sup computation
Completeness	nonempty + bounded above gives a sup in $\mathbb{R}$	the one axiom $\mathbb{Q}$ lacks
Archimedean	$\mathbb{N}$ unbounded; $1/n < y$ for some $n$	choosing $N$ in limit proofs
Density	a rational (and an irrational) in every $(a,b)$	Dirichlet function, approximation
Nested intervals	closed, bounded, nested: nonempty intersection	bisection proofs
Countable	$\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{Q}$	listing arguments
Uncountable	$\mathbb{R}$ , $(0,1)$ , irrationals, Cantor set	diagonal argument

What's next

Real Analysis 01 uses the Axiom of Completeness to study sequences and series: the $\varepsilon$ – $N$ definition of a limit with an explicit $N$ , the Monotone Convergence Theorem (a supremum in disguise), Bolzano–Weierstrass (nested intervals in disguise), Cauchy sequences, and the convergence tests for infinite series, including why rearranging a series can change its sum.

References

Stephen Abbott, Understanding Analysis, 2nd edition, Springer (Undergraduate Texts in Mathematics), 2015 — Chapter 1 (the model for this post).
Walter Rudin, Principles of Mathematical Analysis, 3rd edition, McGraw-Hill, 1976 — Chapter 1 (ordered fields, construction of $\mathbb{R}$ by Dedekind cuts) and Chapter 2 (countable sets, the Cantor set).
Robert G. Bartle and Donald R. Sherbert, Introduction to Real Analysis, 4th edition, Wiley, 2011 — Chapters 1–2.
Terence Tao, Analysis I, 4th edition, Springer (Texts and Readings in Mathematics), 2022 — Chapters 2–5 (from the natural numbers to the construction of $\mathbb{R}$ ).
Michael Spivak, Calculus, 4th edition, Publish or Perish, 2008 — Chapters 1–2 and 8 (least upper bounds).
MIT OpenCourseWare, 18.100A Real Analysis, Fall 2020 (Casey Rodriguez), lecture notes: https://ocw.mit.edu/courses/18-100a-real-analysis-fall-2020/

Note: this post is in progress. Planned additions: a short construction of $\mathbb{R}$ by Dedekind cuts; a proof that the Nested Interval Property plus the Archimedean property implies completeness; and the Schröder–Bernstein theorem.