1.1 Sets, Functions and Countable Sets
The language of sets and functions, and the surprising arithmetic of infinity: $\mathbb{N}\times\mathbb{N}$, $\mathbb{Q}$ and the algebraic numbers are countable, while $\mathbb{R}$, $\{0,1\}^{\mathbb{N}}$ and $\mathcal{P}(\mathbb{N})$ are not.
Every statement in analysis is a statement about sets: the set of points where a function is continuous, the set of values a sequence takes, the set of upper bounds of a set. Before we can speak precisely about limits we need a precise language for sets and for the functions between them — images, preimages, injections, surjections and equivalence relations. That language is the first half of this section.
The second half asks a question that sounds naive and turns out to be deep: how many elements does an infinite set have? Georg Cantor's answer — that some infinite sets are strictly larger than others, that $\mathbb{Q}$ is no larger than $\mathbb{N}$ although it is dense, and that $\mathbb{R}$ is strictly larger than both — is used constantly in analysis (a monotone function has countably many discontinuities; a countable set has Lebesgue measure zero; the Cantor set is uncountable). It is also a favourite of CSIR NET: almost every paper contains a Part B or Part C question of the form "which of the following sets are countable?", and the traps are always the same handful. By the end of this section you will recognise all of them.
Sets, Functions and Relations
We use the standard notation: $x\in A$ ($x$ is an element of $A$), $A\subseteq B$ ($A$ is a subset of $B$), $\varnothing$ for the empty set, and $\mathbb{N}=\{1,2,3,\dots\}$. Two sets are equal when they have the same elements, so $A=B$ is proved by showing $A\subseteq B$ and $B\subseteq A$ — "element-chasing".
Let $A,B$ be subsets of a universal set $X$, and let $\{A_i:i\in I\}$ be a family of subsets of $X$ indexed by a nonempty set $I$.
Sets $A_i$ are pairwise disjoint if $A_i\cap A_j=\varnothing$ whenever $i\ne j$.
Proof. For $x\in X$: $x\in X\setminus\bigcup A_i$ $\iff$ it is not true that $x\in A_i$ for some $i$ $\iff$ $x\notin A_i$ for every $i$ $\iff$ $x\in X\setminus A_i$ for every $i$ $\iff$ $x\in\bigcap(X\setminus A_i)$. For the second law apply the first to the family $B_i=X\setminus A_i$: $X\setminus\bigcup B_i=\bigcap(X\setminus B_i)=\bigcap A_i$; taking complements of both sides gives $\bigcup(X\setminus A_i)=X\setminus\bigcap A_i$. ∎
De Morgan's laws are the reason that "open" and "closed" sets behave dually in Chapter 7: a statement about unions of open sets becomes, after complementing, a statement about intersections of closed sets.
A function $f:X\to Y$ assigns to every $x\in X$ exactly one $f(x)\in Y$; formally it is a subset of $X\times Y$ (its graph) containing exactly one pair $(x,y)$ for each $x\in X$. For $A\subseteq X$ and $B\subseteq Y$:
- the image of $A$ is $f(A)=\{f(a):a\in A\}\subseteq Y$;
- the preimage (inverse image) of $B$ is $f^{-1}(B)=\{x\in X: f(x)\in B\}\subseteq X$. It is defined for every function, invertible or not.
$f$ is injective (one-one) if $f(x_1)=f(x_2)\Rightarrow x_1=x_2$; surjective (onto) if $f(X)=Y$; bijective if both. The composite of $f:X\to Y$ and $g:Y\to Z$ is $(g\circ f)(x)=g(f(x))$.
Let $f:X\to Y$, let $A,A_i\subseteq X$ and $B,B_i\subseteq Y$.
- Preimages respect everything: $f^{-1}\!\left(\bigcup B_i\right)=\bigcup f^{-1}(B_i)$, $\ f^{-1}\!\left(\bigcap B_i\right)=\bigcap f^{-1}(B_i)$, $\ f^{-1}(Y\setminus B)=X\setminus f^{-1}(B)$.
- Images respect unions only: $f\!\left(\bigcup A_i\right)=\bigcup f(A_i)$ and $f\!\left(\bigcap A_i\right)\subseteq\bigcap f(A_i)$. Equality $f(A_1\cap A_2)=f(A_1)\cap f(A_2)$ holds for all $A_1,A_2$ if and only if $f$ is injective.
- Round trips: $f\!\left(f^{-1}(B)\right)=B\cap f(X)\subseteq B$ and $A\subseteq f^{-1}\!\left(f(A)\right)$. The first is an equality for every $B$ iff $f$ is surjective; the second for every $A$ iff $f$ is injective.
Proof. (1) $x\in f^{-1}(\bigcup B_i)\iff f(x)\in B_i$ for some $i\iff x\in f^{-1}(B_i)$ for some $i$. Replacing "some" by "every" gives the intersection rule, and $x\in f^{-1}(Y\setminus B)\iff f(x)\notin B\iff x\notin f^{-1}(B)$.
(2) $y\in f(\bigcup A_i)\iff y=f(x)$ with $x\in A_i$ for some $i\iff y\in\bigcup f(A_i)$. If $y=f(x)$ with $x$ in every $A_i$, then $y$ is in every $f(A_i)$, which gives the inclusion. Suppose $f$ is injective and $y\in f(A_1)\cap f(A_2)$, say $y=f(a_1)=f(a_2)$ with $a_k\in A_k$; injectivity gives $a_1=a_2\in A_1\cap A_2$, so $y\in f(A_1\cap A_2)$. If $f$ is not injective, pick $x_1\ne x_2$ with $f(x_1)=f(x_2)$; for $A_1=\{x_1\}$, $A_2=\{x_2\}$ we get $f(A_1\cap A_2)=\varnothing\ne\{f(x_1)\}=f(A_1)\cap f(A_2)$.
(3) $y\in f(f^{-1}(B))\iff y=f(x)$ for some $x$ with $f(x)\in B\iff y\in B\cap f(X)$; this equals $B$ for every $B$ iff $f(X)=Y$ (take $B=Y$). If $a\in A$ then $f(a)\in f(A)$, so $a\in f^{-1}(f(A))$. If $f$ is injective and $f(x)\in f(A)$, then $f(x)=f(a)$ for some $a\in A$ and $x=a\in A$. If $f$ is not injective, $A=\{x_1\}$ gives $f^{-1}(f(A))\supseteq\{x_1,x_2\}\ne A$. ∎
Proof. (a) If $g\circ f=\mathrm{id}$ and $f(x_1)=f(x_2)$ then $x_1=g(f(x_1))=g(f(x_2))=x_2$. Conversely, if $f$ is injective, fix $x_0\in X$ and put $g(y)=$ the unique $x$ with $f(x)=y$ when $y\in f(X)$, and $g(y)=x_0$ otherwise. (b) If $f\circ h=\mathrm{id}$, every $y=f(h(y))$ is a value of $f$. Conversely, if $f$ is surjective each set $f^{-1}(\{y\})$ is nonempty, and we let $h(y)$ be a chosen element of it. (Choosing one element from each of possibly infinitely many nonempty sets is exactly the axiom of choice; when $X=\mathbb{N}$ no choice is needed — take the least element.) (c) If $g\circ f=\mathrm{id}_X$ and $f\circ h=\mathrm{id}_Y$ then $g=g\circ(f\circ h)=(g\circ f)\circ h=h$. (d) If $f,g$ are injective and $g(f(x_1))=g(f(x_2))$ then $f(x_1)=f(x_2)$ and $x_1=x_2$; surjections are similar. ∎
A relation on $X$ is a subset $R\subseteq X\times X$; we write $x\sim y$ for $(x,y)\in R$. It is an equivalence relation if it is
reflexive ($x\sim x$), symmetric ($x\sim y\Rightarrow y\sim x$), transitive ($x\sim y,\ y\sim z\Rightarrow x\sim z$).
The equivalence class of $x$ is $[x]=\{y\in X:y\sim x\}$, and the set of classes is the quotient set $X/\!\sim$. A partition of $X$ is a family of nonempty, pairwise disjoint subsets whose union is $X$.
Proof. Reflexivity gives $x\in[x]$, so classes are nonempty and cover $X$. Suppose $x\sim y$. If $z\in[x]$ then $z\sim x$ and $x\sim y$, so $z\sim y$: $[x]\subseteq[y]$; by symmetry $[y]\subseteq[x]$. If instead $[x]\cap[y]$ contains some $z$, then $x\sim z$ (symmetry) and $z\sim y$, so $x\sim y$ and $[x]=[y]$. Hence two classes are either equal or disjoint. Conversely, "same block of the partition" is plainly reflexive, symmetric and transitive (each point is in exactly one block), and its classes are the blocks. ∎
Finite, Countable and Uncountable Sets
To compare the sizes of sets we do not count — we pair off. Two sets have the same size if their elements can be matched one-to-one with none left over. This is how a child checks that there are as many cups as saucers without knowing any numbers, and it is the only notion of size that makes sense for infinite sets.
Sets $A$ and $B$ are equinumerous, written $|A|=|B|$ or $A\approx B$, if there is a bijection $A\to B$. (This is an equivalence relation on any collection of sets, by Theorem 1.3.) Let $\mathbb{N}_n=\{1,2,\dots,n\}$.
- $A$ is finite if $A=\varnothing$ or $A\approx\mathbb{N}_n$ for some $n$ (then $A$ has $n$ elements); otherwise $A$ is infinite.
- $A$ is countably infinite (denumerable) if $A\approx\mathbb{N}$; we write $|A|=\aleph_0$ ("aleph-null"). A bijection $\mathbb{N}\to A$ is an enumeration $a_1,a_2,a_3,\dots$ listing each element exactly once.
- $A$ is countable if it is finite or countably infinite, and uncountable otherwise.
Proof. Induction on $m$. For $m=1$ and $n\ge2$, the elements $1,2$ both go to $1$. Assume the claim for $m$, and let $f:\mathbb{N}_n\to\mathbb{N}_{m+1}$ be injective with $n\gt m+1$. If $m+1\notin f(\mathbb{N}_n)$, then $f$ is an injection into $\mathbb{N}_m$, impossible. Otherwise $f(k)=m+1$ for exactly one $k$; composing $f$ with the transposition of $k$ and $n$ we may assume $f(n)=m+1$. Then $f$ restricted to $\mathbb{N}_{n-1}$ is an injection into $\mathbb{N}_m$ with $n-1\gt m$, contradicting the induction hypothesis. If a finite set $A\approx\mathbb{N}_n$ were equinumerous with a proper subset $B\approx\mathbb{N}_m$ ($m\lt n$), composing bijections would give an injection $\mathbb{N}_n\to\mathbb{N}_m$. ∎
Infinite sets behave quite differently: $n\mapsto2n$ is a bijection from $\mathbb{N}$ onto the proper subset of even numbers. (Dedekind turned this around and defined a set to be infinite when it is equinumerous with a proper subset; see Exercise IV.3.)
Proof. If $A\approx C\subseteq\mathbb{N}$ via a bijection $\phi$, a subset $S\subseteq A$ is equinumerous with $\phi(S)\subseteq\mathbb{N}$, so it suffices to treat $S\subseteq\mathbb{N}$. If $S$ is finite there is nothing to do. If $S$ is infinite, use the well-ordering of $\mathbb{N}$: let $s_1=\min S$ and $s_{k+1}=\min\left(S\setminus\{s_1,\dots,s_k\}\right)$, which exists because $S$ is infinite. Then $s_1\lt s_2\lt\cdots$, so $k\mapsto s_k$ is injective, and $s_k\ge k$ by induction. It is onto: given $s\in S$, if $s\notin\{s_1,\dots,s_s\}$ then $s$ was available at each of the first $s$ steps, so $s_k\le s$ for $k\le s$; with $s\ne s_s$ this gives $s_s\lt s\le s_s$, a contradiction. ∎
Proof. (i)$\Rightarrow$(ii): if $A=\{a_1,\dots,a_n\}$ send $k\mapsto a_{\min(k,n)}$; if $A$ is countably infinite use a bijection. (ii)$\Rightarrow$(iii): if $g:\mathbb{N}\to A$ is onto, let $f(a)=\min g^{-1}(\{a\})$; then $g(f(a))=a$, so $f$ is injective (Theorem 1.3(a)) — and no axiom of choice is needed, because we choose least elements. (iii)$\Rightarrow$(i): $A\approx f(A)\subseteq\mathbb{N}$, which is countable by Theorem 1.6. ∎
Proof. Group the pairs by their diagonal $d=m+n\ge2$. The diagonal $d$ contains the $d-1$ pairs $(1,d-1),(2,d-2),\dots,(d-1,1)$, and the diagonals before it contain $1+2+\cdots+(d-2)=\tfrac{(d-1)(d-2)}{2}$ pairs. So $\pi$ sends the diagonal $d$ onto the block of consecutive integers $\tfrac{(d-1)(d-2)}{2}+1,\dots,\tfrac{d(d-1)}{2}$, in order of $m$. These blocks, for $d=2,3,4,\dots$, are $\{1\},\{2,3\},\{4,5,6\},\dots$: they are disjoint and cover $\mathbb{N}$, so $\pi$ is a bijection. For $\varphi$: by unique factorisation every $k\in\mathbb{N}$ is uniquely $2^a\cdot b$ with $a\ge0$ and $b$ odd, and $\varphi^{-1}(k)=\left(a+1,\tfrac{b+1}{2}\right)$. ∎
Proof. (a) For $k=2$, injections $f_1:A_1\to\mathbb{N}$, $f_2:A_2\to\mathbb{N}$ give the injection $(a,b)\mapsto\pi(f_1(a),f_2(b))$ into $\mathbb{N}$; induct on $k$ using $A_1\times\cdots\times A_{k+1}\approx(A_1\times\cdots\times A_k)\times A_{k+1}$. (b) Discard empty $A_n$ (if all are empty, the union is empty). For each remaining $n$ choose a surjection $g_n:\mathbb{N}\to A_n$ (Theorem 1.7) — this simultaneous choice of countably many $g_n$ is where choice enters. Then $G(m,n)=g_n(m)$ maps $\mathbb{N}\times\mathbb{N}$ onto $\bigcup A_n$, and $G\circ\pi^{-1}:\mathbb{N}\to\bigcup A_n$ is onto. Apply Theorem 1.7. ∎
Proof. $\mathbb{Z}=\mathbb{N}\cup\{0\}\cup(-\mathbb{N})$ is a union of three countable sets. $(p,q)\mapsto p/q$ maps $\mathbb{Z}\times\mathbb{N}$ onto $\mathbb{Q}$, and $\mathbb{Z}\times\mathbb{N}$ is countable by Theorem 1.9(a). Products $\mathbb{N}^k$ etc. are Theorem 1.9(a), and the finite sequences form the countable union $\bigcup_k\mathbb{N}^k$. If $C$ is countable, the map sending a finite sequence $(c_1,\dots,c_k)$ to the set $\{c_1,\dots,c_k\}$ (together with $\varnothing$) is onto the finite subsets of $C$. A polynomial $a_0+a_1x+\cdots+a_kx^k$ is determined by its coefficient vector in $\mathbb{Z}^{k+1}$, so $\mathbb{Z}[x]$ is the image of $\bigcup_k\mathbb{Z}^{k+1}$. An interval with rational end points is determined by its end points (a pair in $\mathbb{Q}^2$) and one of four end-point types. ∎
Proof. For each nonzero $p\in\mathbb{Z}[x]$ the set $Z(p)$ of its complex roots is finite (at most $\deg p$ elements). Thus $\mathbb{A}=\bigcup_{p\in\mathbb{Z}[x]\setminus\{0\}}Z(p)$ is a union, indexed by the countable set $\mathbb{Z}[x]\setminus\{0\}$ (Theorem 1.10), of finite sets; by Theorem 1.9(b) it is countable. $\mathbb{A}\cap\mathbb{R}$ is a subset of it (Theorem 1.6). ∎
Once we know that $\mathbb{R}$ is uncountable (Theorem 1.13), it follows that transcendental numbers exist — in fact "most" real numbers are transcendental — although this argument does not exhibit a single one. Cantor's proof was famous precisely for being an existence proof that names no example.
Cantor's Diagonal Argument and Uncountable Sets
Is every infinite set countable? Cantor's diagonal argument (1891) shows that the answer is no, and the argument is so short and so flexible that it reappears throughout mathematics — in Gödel's incompleteness theorem, in Turing's proof that the halting problem is undecidable, and in the Baire category theorem.
Proof. By Theorem 1.7 it suffices to show that no map $f:\mathbb{N}\to\{0,1\}^{\mathbb{N}}$ is onto. Write the sequence $f(k)$ as $(a_{k1},a_{k2},a_{k3},\dots)$ and arrange these as the rows of an infinite array. Define the "anti-diagonal" sequence $d=(d_1,d_2,\dots)$ by $d_k=1-a_{kk}$. For every $k$, $d$ and $f(k)$ differ in the $k$-th place ($d_k\ne a_{kk}$), so $d\ne f(k)$. Thus $d\notin f(\mathbb{N})$ and $f$ is not onto. ∎
Proof. We use decimal expansions (§1.2, the theorem on $b$-adic expansions): every $x\in(0,1)$ has an expansion $x=0.a_1a_2a_3\ldots$, and a number has two expansions only if one of them ends in an infinite string of $9$s (as $0.5=0.4999\ldots$). Let $x_1,x_2,\dots$ be any sequence in $(0,1)$ and choose an expansion $x_k=0.a_{k1}a_{k2}a_{k3}\ldots$ of each. Define $$d_k=\begin{cases}5,&a_{kk}\ne5,\\4,&a_{kk}=5,\end{cases}\qquad y=0.d_1d_2d_3\ldots$$ Then $y\in[0.444\ldots,0.555\ldots]\subseteq(0,1)$. The expansion of $y$ uses only the digits $4$ and $5$ — it neither ends in $9$s nor in $0$s — so it is the only decimal expansion of $y$. If $y=x_k$, this unique expansion would be the chosen expansion of $x_k$; but the two differ in the $k$-th digit. Hence $y\ne x_k$ for all $k$: no sequence exhausts $(0,1)$. The interval $(a,b)$ is the bijective image of $(0,1)$ under $t\mapsto a+(b-a)t$, and a set containing an uncountable subset is uncountable. Finally $\mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q})$: if the irrationals were countable, $\mathbb{R}$ would be a union of two countable sets; the same argument with $\mathbb{A}\cap\mathbb{R}$ (Theorem 1.11) handles the transcendentals. ∎
The choice of the digits $4$ and $5$ is not decoration: if we used $d_k=a_{kk}+1$ (mod 10), the diagonal number could be $0.0999\ldots=0.1000\ldots$ and might be on the list after all, under its other name. In §1.2 we give a second proof of Theorem 1.13, with nested intervals, that avoids expansions altogether.
Proof. Let $f:A\to\mathcal{P}(A)$ be any map and consider the "diagonal" set $D=\{a\in A: a\notin f(a)\}$. If $D=f(d)$ for some $d\in A$, then $d\in D\iff d\notin f(d)=D$, which is absurd. So $D$ is not a value of $f$. ∎
For $A=\mathbb{N}$ this is exactly Theorem 1.12 in disguise: identify $f(k)$ with its indicator sequence; then $D$ is the set whose indicator is the anti-diagonal $d_k=1-a_{kk}$. Cantor's theorem also shows that there is no "set of all sets" $U$: we would have $\mathcal{P}(U)\subseteq U$, giving a surjection $U\to\mathcal{P}(U)$ (Russell's paradox in another form).
Comparing Cardinalities: Schröder–Bernstein, $\aleph_0$ and $\mathfrak{c}$
To prove $|A|=|B|$ it is often hard to write down a bijection but easy to find injections in both directions. The next theorem says that this is enough.
Proof. The idea: send most points by $f$, but points that "come from outside $g(B)$" along a chain must be handled so that nothing in $B$ is missed. Let $$C_0=A\setminus g(B),\qquad C_{n+1}=g\!\left(f(C_n)\right),\qquad C=\bigcup_{n\ge0}C_n,$$ and define $$h(a)=\begin{cases}f(a),&a\in C,\\ g^{-1}(a),&a\in A\setminus C.\end{cases}$$ This makes sense: if $a\notin C$ then $a\notin C_0$, so $a\in g(B)$, and since $g$ is injective $g^{-1}(a)$ is a single point of $B$.
$h$ is injective. On $C$ it equals the injective $f$; on $A\setminus C$ it equals the injective $g^{-1}$. If $a\in C$, $a'\notin C$ and $f(a)=g^{-1}(a')$, then $a'=g(f(a))$; as $a\in C_n$ for some $n$, $a'\in C_{n+1}\subseteq C$ — a contradiction.
$h$ is surjective. Let $b\in B$. If $g(b)\notin C$ then $h(g(b))=g^{-1}(g(b))=b$. If $g(b)\in C$, then $g(b)\in C_n$ for some $n$; $n\ne0$ because $g(b)\in g(B)$. So $g(b)\in C_n=g(f(C_{n-1}))$, i.e. $g(b)=g(f(a))$ for some $a\in C_{n-1}\subseteq C$; injectivity of $g$ gives $b=f(a)=h(a)$. ∎
Proof. (a) $x\mapsto\dfrac{x}{1-|x|}$ is a bijection $(-1,1)\to\mathbb{R}$ (strictly increasing and continuous, with limits $\mp\infty$), and affine maps carry $(-1,1)$ onto any $(a,b)$. For the other intervals use Schröder–Bernstein: e.g. $(a,b)\subseteq[a,b]\subseteq(a-1,b+1)$ gives injections both ways between $[a,b]$ and an open interval; $(a,\infty)\approx\mathbb{R}$ by $x\mapsto\log(x-a)$.
(b) The indicator map is a bijection $\mathcal{P}(\mathbb{N})\to\{0,1\}^{\mathbb{N}}$. Injection $\mathbb{R}\to\mathcal{P}(\mathbb{Q})$: $x\mapsto\{q\in\mathbb{Q}:q\lt x\}$ — if $x\lt y$ there is a rational between them (§1.2), so the two sets differ; and $\mathcal{P}(\mathbb{Q})\approx\mathcal{P}(\mathbb{N})$ because $\mathbb{Q}\approx\mathbb{N}$. Injection $\{0,1\}^{\mathbb{N}}\to\mathbb{R}$: $(a_n)\mapsto\sum_{n\ge1}2a_n\,3^{-n}$. If $(a_n)\ne(b_n)$ first differ at place $N$, say $a_N=1$, $b_N=0$, the two sums differ by at least $$\frac{2}{3^N}-\sum_{n\gt N}\frac{2}{3^n}=\frac{2}{3^N}-\frac{1}{3^N}=\frac{1}{3^N}\gt0.$$ (The image is the Cantor set of §4.4.) Schröder–Bernstein gives $|\mathbb{R}|=|\mathcal{P}(\mathbb{N})|$.
(c) Interleaving $\big((a_n),(b_n)\big)\mapsto(a_1,b_1,a_2,b_2,\dots)$ is a bijection $\{0,1\}^{\mathbb{N}}\times\{0,1\}^{\mathbb{N}}\to\{0,1\}^{\mathbb{N}}$, so $|\mathbb{R}^2|=|\mathbb{R}|$; induct for $\mathbb{R}^n$. For sequences, $\mathbb{R}^{\mathbb{N}}\approx\left(\{0,1\}^{\mathbb{N}}\right)^{\mathbb{N}}\approx\{0,1\}^{\mathbb{N}\times\mathbb{N}}\approx\{0,1\}^{\mathbb{N}}$, the last step because $\mathbb{N}\times\mathbb{N}\approx\mathbb{N}$.
(d) $\{1,2\}^{\mathbb{N}}\subseteq\mathbb{N}^{\mathbb{N}}\subseteq\mathbb{Z}^{\mathbb{N}}\subseteq\mathbb{R}^{\mathbb{N}}$ and the two ends have cardinality $\mathfrak{c}$.
(e) Let $C$ be countable. $\mathbb{R}\setminus C$ is uncountable, hence infinite, so it contains a sequence of distinct points $t_1,t_2,\dots$ (for $C=\mathbb{Q}$ take $t_n=n\sqrt2$). Let $T=\{t_n\}$ and list $C=\{c_1,c_2,\dots\}$ (if $C$ is finite the same idea works). Define $\psi:\mathbb{R}\to\mathbb{R}\setminus C$ by $\psi(c_n)=t_{2n-1}$, $\psi(t_n)=t_{2n}$, and $\psi(x)=x$ for $x\notin C\cup T$. This is a bijection — Hilbert's hotel again. ∎
Proof. (a) The constant functions give an injection $\mathbb{R}\to C(\mathbb{R})$. Conversely, the restriction map $f\mapsto f|_{\mathbb{Q}}$ is injective on $C(\mathbb{R})$: if $f=g$ on $\mathbb{Q}$ and $x\in\mathbb{R}$, choose rationals $q_n\to x$; continuity gives $f(x)=\lim f(q_n)=\lim g(q_n)=g(x)$ (sequential continuity, §3.1). So $|C(\mathbb{R})|\le|\mathbb{R}^{\mathbb{Q}}|=|\mathbb{R}^{\mathbb{N}}|=\mathfrak{c}$, and Schröder–Bernstein finishes. (b) $\{0,1\}^{\mathbb{R}}\approx\mathcal{P}(\mathbb{R})$ via indicator functions, and $|\mathcal{P}(\mathbb{R})|\gt\mathfrak{c}$ by Cantor. Also $\{0,1\}^{\mathbb{R}}\subseteq\mathbb{R}^{\mathbb{R}}$, and $f\mapsto$ (graph of $f$) injects $\mathbb{R}^{\mathbb{R}}$ into $\mathcal{P}(\mathbb{R}\times\mathbb{R})\approx\mathcal{P}(\mathbb{R})$, using $|\mathbb{R}^2|=\mathfrak{c}$. ∎
- Countable? Can each element be described by finitely many symbols from a countable alphabet (integers, rationals, algebraic numbers, a finite list of earlier objects)? Then the set is a countable union of countable sets — countable. Or find an injection into $\mathbb{N}$, $\mathbb{Q}$ or $\mathbb{N}^k$.
- Uncountable? Find an injection from a known uncountable set: $\{0,1\}^{\mathbb{N}}$ (infinitely many independent binary choices), an interval, $\mathcal{P}(\mathbb{N})$. Or run a diagonal argument directly. Or use the complement trick: if $X=Y\cup Z$ with $X$ uncountable and $Z$ countable, then $Y$ is uncountable.
- Exactly $\mathfrak{c}$? Show $\ge\mathfrak{c}$ by an injection from $\mathbb{R}$ (often "one element for each real parameter"), and $\le\mathfrak{c}$ by describing each element with countably many reals (an injection into $\mathbb{R}^{\mathbb{N}}$); then apply Schröder–Bernstein.
- Bigger than $\mathfrak{c}$? Only when the elements involve arbitrary choices at uncountably many points: all subsets of $\mathbb{R}$, all functions on $\mathbb{R}$, all equivalence relations on $\mathbb{R}$.
- Finite subsets vs all subsets. The finite subsets of $\mathbb{N}$ form a countable set; all subsets, or all infinite subsets, form an uncountable one.
- Eventually zero vs arbitrary sequences. $c_{00}(\mathbb{Z})$ (eventually $0$) and the eventually constant integer sequences are countable; $\mathbb{Z}^{\mathbb{N}}$, $\{0,1\}^{\mathbb{N}}$, and even the strictly increasing sequences in $\mathbb{N}$ are uncountable.
- Countable unions, not countable products. $\bigcup_n A_n$ of countable sets is countable, but $\prod_n A_n$ is uncountable as soon as infinitely many $A_n$ have two or more elements ($\{0,1\}^{\mathbb{N}}$).
- Uncountable unions of small sets. $\mathbb{R}=\bigcup_{x\in\mathbb{R}}\{x\}$ is an uncountable union of finite sets; "union of countable sets" is countable only when there are countably many of them.
- Dense does not mean uncountable. $\mathbb{Q}$, $\mathbb{Q}+\sqrt2$, the dyadic rationals and the algebraic reals are dense in $\mathbb{R}$ and countable.
- Uncountable does not mean "contains an interval". $\mathbb{R}\setminus\mathbb{Q}$ and the Cantor set are uncountable but contain no interval.
- Disjoint open sets are few. Any family of pairwise disjoint nonempty open sets in $\mathbb{R}^n$ is countable (each contains a rational point); disjoint circles or singletons need not be.
- Images keep unions, not intersections. $f(A\cap B)\subsetneq f(A)\cap f(B)$ for $f(x)=x^2$, $A=[-2,1]$, $B=[0,3]$; and $f^{-1}(f(A))\ne A$, $f(f^{-1}(B))\ne B$ in general.
- An enumeration of $\mathbb{Q}$ cannot respect order. Between any two rationals there is a third, so there is no "next" rational: any bijection $\mathbb{N}\to\mathbb{Q}$ jumps around.
- The diagonal argument does not prove $\mathbb{Q}$ uncountable. Run on a list of the rationals in $(0,1)$, it produces a real number — which is simply irrational, so not on the list. No contradiction.
- Polynomials: coefficients matter. $\mathbb{Q}[x]$ and $\mathbb{A}[x]$ are countable; $\mathbb{R}[x]$ has cardinality $\mathfrak{c}$ (the constants alone).
- Symmetric and transitive is not reflexive. $xy\gt0$ on $\mathbb{R}$ is symmetric and transitive but fails at $x=0$; the "proof" $x\sim y\Rightarrow y\sim x\Rightarrow x\sim x$ needs some $y$ related to $x$.
Exercises
- 1 Prove that $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$ and $A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)$.
- 2 Prove that $A\,\triangle\,B=(A\cup B)\setminus(A\cap B)$ and that $\triangle$ is associative. (Hint: $\mathbf 1_{A\triangle B}\equiv\mathbf 1_A+\mathbf 1_B\pmod 2$.)
- 3 For $f:\mathbb{R}\to\mathbb{R}$, $f(x)=x^2-2x$, find $f([0,3])$, $f^{-1}([-1,3])$ and $f^{-1}((-\infty,-1))$.
- 4 Show that $f(A\setminus B)\supseteq f(A)\setminus f(B)$ for all $A,B\subseteq X$, with equality for all $A,B$ if and only if $f$ is injective.
- 5 Let $f:X\to Y$ and $g:Y\to Z$. Prove: if $g\circ f$ is injective then $f$ is injective; if $g\circ f$ is surjective then $g$ is surjective. Give an example in which $g\circ f$ is bijective but neither $f$ nor $g$ is.
- 6 Which of these relations on $\mathbb{R}$ are equivalence relations? (a) $x-y\in\mathbb{Z}$; (b) $xy\gt0$; (c) $xy\ge0$; (d) $x-y\in\mathbb{R}\setminus\mathbb{Q}$.
- 7 On $\mathbb{Z}$ define $a\sim b\iff7\mid(a^3-b^3)$. Show that $\sim$ is an equivalence relation and find its classes.
- 8 How many equivalence relations are there on a $4$-element set? How many of them have exactly two classes?
- 1 With $\pi(m,n)=\tfrac{(m+n-1)(m+n-2)}2+m$, compute $\pi(3,4)$ and find the pair $(m,n)$ with $\pi(m,n)=20$.
- 2 Prove that $\varphi(m,n)=2^{m-1}(2n-1)$ is a bijection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ and find $\varphi^{-1}(96)$.
- 3 In the $\mathbb{Q}^+$ list of Interactive 1 (diagonal sweep, numerator increasing along each diagonal, non-reduced fractions skipped), at which position does $3/5$ appear? And $2/3$?
- 4 Show that $\mathbb{Z}\times\mathbb{Q}$ and the set of all finite subsets of $\mathbb{Q}$ are countable.
- 5 Show that the set of all $2\times2$ matrices with rational entries, and the set of all such matrices that are invertible, are countably infinite.
- 6 Show that the set of intervals with rational end points is countable, and deduce that every family of pairwise disjoint intervals of positive length in $\mathbb{R}$ is countable.
- 7 Show that $\sqrt2+\sqrt3$ and $1+\sqrt[3]{2}$ are algebraic by finding integer polynomials they satisfy.
- 8 Show that the set of all eventually periodic sequences of integers is countable.
- 9 Let $A$ be uncountable and $B$ countable. Prove that $A\setminus B$ is uncountable. Deduce that the irrationals and the transcendental real numbers are uncountable.
- 1 Prove that the set of $0$–$1$ sequences with infinitely many $1$s is uncountable.
- 2 Verify that $h(1/n)=1/(n+1)$ ($n\ge1$), $h(x)=x$ otherwise, is a bijection $[0,1]\to[0,1)$.
- 3 Show that $x\mapsto\dfrac{x}{1-|x|}$ is a bijection $(-1,1)\to\mathbb{R}$ and find its inverse.
- 4 Construct an explicit bijection $\mathbb{R}\to\mathbb{R}\setminus\mathbb{Q}$.
- 5 Find the cardinality of (a) the set of all lines in $\mathbb{R}^2$ through the origin; (b) the set of all lines through two distinct points with rational coordinates.
- 6 Find the cardinality of the set of subsets $S\subseteq\mathbb{N}$ such that both $S$ and $\mathbb{N}\setminus S$ are infinite.
- 7 Find the cardinality of (a) $\mathbb{R}^{\mathbb{N}}$; (b) the set of polynomials with real coefficients; (c) the set of all functions $\mathbb{N}\to\mathbb{Q}$; (d) the set of all functions $\mathbb{R}\to\{0,1\}$.
- 8 Prove directly that $S\mapsto\mathbf 1_S$ is a bijection $\mathcal{P}(X)\to\{0,1\}^X$ for any set $X$.
- 9 Show that there is no set $X$ whose power set is countably infinite.
- 1 Use the Schröder–Bernstein theorem to prove $|[0,1]\times[0,1]|=|[0,1]|$ without decimal expansions.
- 2 Prove that the set of strictly increasing functions $\mathbb{N}\to\mathbb{N}$ is uncountable.
- 3 Prove that every infinite set $X$ contains a countably infinite subset, and deduce that $X$ is infinite iff it is equinumerous with a proper subset of itself.
- 4 A point $a\in A\subseteq\mathbb{R}$ is isolated in $A$ if some interval $(a-\delta,a+\delta)$ meets $A$ only in $a$. Prove that every subset of $\mathbb{R}$ has only countably many isolated points.
- 5 Let $f:\mathbb{R}\to\mathbb{R}$ be any function. Prove that the set of points at which $f$ has a strict local maximum is countable.
- 6 Prove that the set of all bijections $\mathbb{N}\to\mathbb{N}$ has cardinality $\mathfrak{c}$.
E1. CSIR Part B GATE MA Which of the following sets is uncountable? (A) the set of all finite subsets of $\mathbb{Q}$; (B) the set of all polynomials in one variable whose coefficients are algebraic numbers; (C) the set of all strictly increasing sequences of natural numbers; (D) the set of all lines in $\mathbb{R}^2$ passing through at least two distinct points with rational coordinates.
E2. CSIR Part B The cardinality of the set of all equivalence relations on $\mathbb{N}$ is (A) finite; (B) $\aleph_0$; (C) $\mathfrak{c}$; (D) $2^{\mathfrak{c}}$.
E3. CSIR Part B Let $f:X\to Y$ be an arbitrary function, $A,B\subseteq X$ and $C\subseteq Y$. Which statement is always true? (A) $f(A\cap B)=f(A)\cap f(B)$; (B) $f^{-1}(Y\setminus C)=X\setminus f^{-1}(C)$; (C) $f(X\setminus A)=Y\setminus f(A)$; (D) $f^{-1}(f(A))=A$.
E4. CSIR Part C Which of the following sets are countable? (One or more options may be correct.) (A) $\{x\in\mathbb{R}: x^n\in\mathbb{Q}\text{ for some }n\in\mathbb{N}\}$; (B) the set of all sequences of rational numbers converging to $0$; (C) the set of all finite subsets of $\mathbb{R}$; (D) the set of all circles in $\mathbb{R}^2$ whose centre has algebraic coordinates and whose radius is rational.
E5. CSIR Part C Let $A\subseteq\mathbb{R}$ be uncountable. Which of the following are necessarily true? (A) $A\setminus\mathbb{Q}$ is uncountable; (B) $A$ contains a nonempty open interval; (C) some point of $A$ is a limit point of $A$; (D) $\mathbb{R}\setminus A$ is countable.
E6. CSIR Part C Consider functions $f:\mathbb{N}\to\mathbb{N}$. Which of the following statements are true? (A) The set of non-decreasing $f$ is uncountable. (B) The set of eventually constant $f$ is countable. (C) The set of $f$ with $f(n)\le2$ for all $n$ is countable. (D) The set of bijections $f$ with $f\circ f=\mathrm{id}$ is countable.
Suggested plan — 3 lectures × 60 min.
- Sets, functions, relations. De Morgan (Theorem 1.1) by element-chasing; Theorem 1.2 with Example 1 drawn on the board (the parabola makes $f(A\cap B)\ne f(A)\cap f(B)$ visible); equivalence relations and partitions (Theorem 1.4, Example 2). Ten minutes on Theorem 1.3 and why right inverses need choice.
- Countable sets. Definitions, Theorems 1.6–1.8; project Interactive 1 in mode ℕ×ℕ, then ℚ⁺ — ask the class to predict the position of $3/5$ before the walk reaches it. Theorems 1.9–1.11 and Examples 3–5. End with the question "is every infinite set countable?"
- Uncountability. Interactive 2 (start with the random list; then the "all finite strings" list, which surprises students), Theorems 1.12–1.14, Schröder–Bernstein with a picture of the chains $C_n$, Theorem 1.16, Examples 6–7. Finish with Exam-corner E1 and E5 done live.
Discussion questions. (1) $\mathbb{Q}$ is dense and $\mathbb{N}$ is discrete; how can they have the same size? What property of size are we not measuring? (2) Where exactly does the diagonal argument fail if we apply it to a list of all rationals in $(0,1)$? (3) Is "the set of all real numbers that can be defined by a finite English sentence" countable? What does that say about most real numbers?
Misconceptions to watch for. "Infinite means uncountable"; "dense means uncountable"; "a union of countable sets is always countable" (forgetting that there must be countably many); believing the diagonal number "might be on the list later"; treating $f^{-1}(B)$ as if $f$ had an inverse; claiming symmetric + transitive ⇒ reflexive.
Suggested homework. I(3, 4, 6, 7), II(1, 3, 5, 7, 9), III(2, 4, 5, 7), IV(2, 4, 5); Exam corner E2, E4, E6.
Research question. Can the positive rationals be listed exactly once by a one-line rule — no greatest-common-divisor checks, no skipping — and what does such a list have to do with gears in a clock?
Why it matters. In the 1860s the Paris clockmaker Achille Brocot needed gear trains whose ratio approximated awkward astronomical ratios with small tooth counts; the tree of fractions he used (the Stern–Brocot tree) is the same structure behind the Calkin–Wilf enumeration of $\mathbb{Q}^+$, and today it appears in exact computer arithmetic, music tuning systems and rational approximation in signal processing.
What to do.
- Generate the Calkin–Wilf sequence with Newman's rule $x_1=1$, $x_{n+1}=\dfrac{1}{2\lfloor x_n\rfloor-x_n+1}$, using exact fractions (Python's
fractions.Fraction), for $n\le5000$. - Check that no fraction repeats, that every $x_n$ is in lowest terms automatically, and find the positions of $3/5$ and $22/7$. Compare with their positions in the diagonal list of Interactive 1.
- Observe where $1/n$ first appears and conjecture a formula; explain why the list nevertheless contains every positive rational.
- Use the Stern–Brocot tree (mediants $\tfrac{a+c}{b+d}$) to find the fraction with denominator at most $100$ closest to $\sqrt2$, as a clockmaker would for a gear pair.
Tools: Python (or any language with exact rational arithmetic); a spreadsheet for the comparison table.
Hand in: A one-page note: the two positions of each test fraction, your conjecture about $1/n$, and the best gear ratio you found.
Going further. Prove that $x_n=s(n)/s(n+1)$, where $s$ is Stern's diatomic sequence $s(1)=1$, $s(2n)=s(n)$, $s(2n+1)=s(n)+s(n+1)$; read about why every fraction appears exactly once in the Calkin–Wilf tree.
🧪 Self-check quiz
Q1. Which of these sets is countable?
Q2. For an arbitrary $f:X\to Y$, which identity always holds?
Q3. Cantor's theorem states that for every set $A$:
Q4. The cardinality of $\mathbb{R}^2$ is
Q5. In the diagonal proof that $(0,1)$ is uncountable, the new digits are chosen from $\{4,5\}$ (never $0$ or $9$) in order to