Chapter 1 · Sets, Real Numbers and Countability

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

📘 Definition 1.1 — Operations on sets

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

Union and intersection$\bigcup_{i\in I}A_i=\{x: x\in A_i\text{ for some }i\}$, $\ \bigcap_{i\in I}A_i=\{x: x\in A_i\text{ for every }i\}$.
Difference and complement$A\setminus B=\{x\in A: x\notin B\}$; the complement of $A$ is $A^c=X\setminus A$.
Symmetric difference$A\,\triangle\,B=(A\setminus B)\cup(B\setminus A)$.
Power set$\mathcal{P}(A)$ is the set of all subsets of $A$, including $\varnothing$ and $A$.
Cartesian product$A\times B=\{(a,b):a\in A,\ b\in B\}$; $B^A$ denotes the set of all functions $A\to B$.

Sets $A_i$ are pairwise disjoint if $A_i\cap A_j=\varnothing$ whenever $i\ne j$.

📐 Theorem 1.1 — De Morgan's laws
For any family $\{A_i:i\in I\}$ of subsets of $X$, $$X\setminus\bigcup_{i\in I}A_i=\bigcap_{i\in I}\left(X\setminus A_i\right),$$ $$X\setminus\bigcap_{i\in I}A_i=\bigcup_{i\in I}\left(X\setminus A_i\right).$$ The index set $I$ may be finite, countable or uncountable.

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.

📘 Definition 1.2 — Functions, images and preimages

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))$.

📐 Theorem 1.2 — Images and preimages

Let $f:X\to Y$, let $A,A_i\subseteq X$ and $B,B_i\subseteq Y$.

  1. 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)$.
  2. 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.
  3. 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$. ∎

📐 Theorem 1.3 — Inverses
Let $f:X\to Y$ with $X\ne\varnothing$. (a) $f$ is injective iff it has a left inverse $g:Y\to X$, $g\circ f=\mathrm{id}_X$. (b) $f$ is surjective iff it has a right inverse $h:Y\to X$, $f\circ h=\mathrm{id}_Y$. (c) $f$ is bijective iff it has a two-sided inverse; this inverse is unique and is denoted $f^{-1}$. (d) Composites of injections (surjections, bijections) are injections (surjections, bijections).

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

✏️ Example 1 — Images and preimages under $f(x)=x^2$
Let $f:\mathbb{R}\to\mathbb{R}$, $f(x)=x^2$, $A=[-2,1]$, $B=[0,3]$. Compute $f(A)$, $f(B)$, $f(A\cap B)$, $f(A)\cap f(B)$, $f^{-1}([1,4])$, $f\!\left(f^{-1}([-1,4])\right)$ and $f^{-1}\!\left(f([0,1])\right)$. Which parts of Theorem 1.2 are illustrated?
Images On $[-2,1]$ the values $x^2$ fill $[0,4]$ (largest at $x=-2$, smallest at $x=0$), so $f(A)=[0,4]$; similarly $f(B)=[0,9]$. Since $A\cap B=[0,1]$, $f(A\cap B)=[0,1]$, whereas $f(A)\cap f(B)=[0,4]$.
Strict inclusion $f(A\cap B)=[0,1]\subsetneq[0,4]=f(A)\cap f(B)$: the value $4=f(-2)=f(2)$ is reached from $A$ (at $-2$) and from $B$ (at $2$) but not from $A\cap B$. This is Theorem 1.2(2): $f$ is not injective.
Preimages $1\le x^2\le4\iff1\le|x|\le2$, so $f^{-1}([1,4])=[-2,-1]\cup[1,2]$. Next $f^{-1}([-1,4])=[-2,2]$ and $f([-2,2])=[0,4]\ne[-1,4]$: we recover $[-1,4]\cap f(\mathbb{R})=[0,4]$, as Theorem 1.2(3) predicts ($f$ is not onto).
Round trip $f([0,1])=[0,1]$ and $f^{-1}([0,1])=[-1,1]\supsetneq[0,1]$, again because $f$ is not injective.
📘 Definition 1.3 — Relations, equivalence relations and partitions

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

📐 Theorem 1.4 — Equivalence relations are partitions
If $\sim$ is an equivalence relation on $X$, its classes form a partition of $X$, and $[x]=[y]\iff x\sim y$. Conversely, every partition $\{P_j\}$ of $X$ is the set of classes of exactly one equivalence relation, namely $x\sim y\iff x,y$ lie in the same $P_j$.

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

✏️ Example 2 — Equivalence relation or not?
Decide which of the following are equivalence relations, and describe the classes of those that are. (a) On $\mathbb{R}$: $x\sim y\iff|x-y|\le1$. (b) On $\mathbb{Z}$: $a\sim b\iff 5\mid(a^2-b^2)$. (c) On $\mathbb{R}^2$: $(x,y)\sim(u,v)\iff x^2+y^2=u^2+v^2$.
(a) No Reflexive ($|x-x|=0\le1$) and symmetric, but not transitive: $0\sim0.8$ and $0.8\sim1.6$, yet $|0-1.6|=1.6\gt1$. "Being close" is never transitive — closeness accumulates.
(b) Yes $a^2-a^2=0$ is divisible by $5$; $5\mid(a^2-b^2)\Rightarrow5\mid(b^2-a^2)$; and if $5\mid a^2-b^2$ and $5\mid b^2-c^2$ then $5$ divides the sum $a^2-c^2$. Since $5$ is prime, $5\mid(a-b)(a+b)$ means $a\equiv b$ or $a\equiv-b\pmod5$. The squares mod $5$ are $0,1,4,4,1$ for $a\equiv0,1,2,3,4$, so there are exactly three classes: $\{a\equiv0\}$, $\{a\equiv\pm1\}$, $\{a\equiv\pm2\}\pmod 5$.
(c) Yes It has the form $p\sim q\iff g(p)=g(q)$ for the function $g(x,y)=x^2+y^2$, and every relation of this form is an equivalence relation (equality is). The classes are the fibres $g^{-1}(\{r^2\})$: the origin, and the circles $x^2+y^2=r^2$, $r\gt0$ — uncountably many classes.
Lesson "$p\sim q\iff g(p)=g(q)$" is the universal shape of an equivalence relation: conversely, every equivalence relation arises this way with $g(x)=[x]$, the quotient map $X\to X/\!\sim$.

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.

📘 Definition 1.4 — Equinumerous, finite, countable

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.
📐 Theorem 1.5 — Pigeonhole principle
If $m\lt n$ there is no injection $\mathbb{N}_n\to\mathbb{N}_m$. Consequently the number of elements of a finite set is well defined, and a finite set is never equinumerous with a proper subset of itself.

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

📐 Theorem 1.6 — Subsets of countable sets are countable
Every subset of a countable set is countable. Every infinite subset of $\mathbb{N}$ is countably infinite, enumerated in increasing order.

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

📐 Theorem 1.7 — Three tests for countability
For a nonempty set $A$ the following are equivalent: (i) $A$ is countable; (ii) there is a surjection $\mathbb{N}\to A$; (iii) there is an injection $A\to\mathbb{N}$. In particular the image of a countable set under any function is countable.

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

📐 Theorem 1.8 — $\mathbb{N}\times\mathbb{N}$ is countable
Each of the maps $$\pi(m,n)=\frac{(m+n-1)(m+n-2)}{2}+m,$$ $$\varphi(m,n)=2^{m-1}(2n-1)$$ is a bijection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$. Hence $|\mathbb{N}\times\mathbb{N}|=\aleph_0$.

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)$. ∎

📐 Theorem 1.9 — Countable unions and finite products
(a) If $A_1,\dots,A_k$ are countable then $A_1\times\cdots\times A_k$ is countable. (b) If $A_n$ is countable for every $n\in\mathbb{N}$, then $\bigcup_{n=1}^{\infty}A_n$ is countable. (Part (b) uses the countable axiom of choice; it is a standard and harmless assumption in analysis.)

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

📐 Theorem 1.10 — A catalogue of countable sets
The following sets are countable: $\mathbb{Z}$; $\mathbb{Q}$; $\mathbb{N}^k$, $\mathbb{Z}^k$ and $\mathbb{Q}^k$ for each $k$; the set $\bigcup_{k\ge1}\mathbb{N}^k$ of all finite sequences of natural numbers; the set of all finite subsets of a countable set; the set $\mathbb{Z}[x]$ (and $\mathbb{Q}[x]$) of polynomials with integer (rational) coefficients; the set of all intervals with rational end points.

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

📘 Definition 1.5 — Algebraic and transcendental numbers
A complex number $\alpha$ is algebraic if $p(\alpha)=0$ for some nonzero polynomial $p\in\mathbb{Z}[x]$, and transcendental otherwise. Examples of algebraic numbers: every rational $p/q$ (root of $qx-p$), $\sqrt2$, $\sqrt[3]{5}$, $\sqrt2+\sqrt3$ (root of $x^4-10x^2+1$), $i$. The numbers $e$ and $\pi$ are transcendental (Hermite 1873, Lindemann 1882 — deep theorems we only quote).
📐 Theorem 1.11 — The algebraic numbers are countable (Cantor, 1874)
The set $\mathbb{A}$ of all algebraic numbers is countable, and so is $\mathbb{A}\cap\mathbb{R}$.

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.

✏️ Example 3 — Three explicit bijections
Write down explicit bijections (a) $\mathbb{N}\to\mathbb{Z}$; (b) $[0,1]\to(0,1)$; (c) $(0,1)\to\mathbb{R}$.
(a) List $\mathbb{Z}$ as $0,1,-1,2,-2,3,\dots$: $$f(n)=\begin{cases}n/2,&n\text{ even},\\ (1-n)/2,&n\text{ odd}.\end{cases}$$ Its inverse is $g(k)=2k$ for $k\gt0$ and $g(k)=1-2k$ for $k\le0$; one checks $f(g(k))=k$ and $g(f(n))=n$, so $f$ is a bijection.
(b) Hilbert's hotel The two end points need "rooms". Inside $[0,1]$ pick the sequence $0,1,\tfrac12,\tfrac13,\tfrac14,\dots$ and shift it two places along: $$h(0)=\tfrac12,\qquad h\!\left(\tfrac1n\right)=\tfrac1{n+2}\ (n\ge1),\qquad h(x)=x\ \text{otherwise}.$$ The sequence $0,1,\tfrac12,\tfrac13,\dots$ is mapped bijectively onto $\tfrac12,\tfrac13,\tfrac14,\dots$ (all inside $(0,1)$), and every other point is fixed, so $h:[0,1]\to(0,1)$ is a bijection. Any infinite set absorbs finitely (even countably) many extra points this way.
(c) $t(x)=\dfrac{2x-1}{x(1-x)}$ is continuous on $(0,1)$ with $$t'(x)=\frac{2x^2-2x+1}{x^2(1-x)^2}\gt0$$ (the numerator has negative discriminant $4-8$), and $t(x)\to-\infty$ as $x\to0^+$, $t(x)\to+\infty$ as $x\to1^-$. So $t$ is strictly increasing, hence injective, and onto $\mathbb{R}$ by the intermediate value theorem (§3.1). Alternatively, $x\mapsto\tan\!\left(\pi x-\tfrac{\pi}{2}\right)$.
Moral All intervals — open, closed, bounded or not — have the same cardinality as $\mathbb{R}$. Length is not size.
Interactive 1 — Walking the Diagonals: Counting $\mathbb{N}\times\mathbb{N}$ and $\mathbb{Q}^+$

Cell $(p,q)$ in column $p$ and row $q$ stands for the pair $(p,q)$ — or for the fraction $p/q$. Walking along the finite diagonals $p+q=2,3,4,\dots$ reaches every cell after finitely many steps. In the $\mathbb{Q}^+$ modes, cells that are not in lowest terms (grey) are skipped, so each positive rational is listed exactly once. Press Play or drag the slider; the list on the right is the enumeration being built.

step—
cell (p, q)—
diagonal p + q—
position in the list—
distinct entries listed—
✏️ Example 4 — Countable or uncountable?
Decide, with proof, whether each set is countable: (a) the set $\mathcal{F}$ of all finite subsets of $\mathbb{N}$; (b) $\mathbb{Q}[x]$; (c) the set $c_{00}(\mathbb{Z})$ of integer sequences that are eventually $0$; (d) the set $\mathbb{Z}^{\mathbb{N}}$ of all integer sequences; (e) the set of all infinite subsets of $\mathbb{N}$. (Parts (d), (e) use Theorem 1.12 below.)
(a) Countable $\mathcal{F}=\bigcup_{n\ge1}\mathcal{P}(\mathbb{N}_n)$ (a finite subset of $\mathbb{N}$ lies inside some $\mathbb{N}_n$; the empty set is in $\mathcal{P}(\mathbb{N}_1)$), and each $\mathcal{P}(\mathbb{N}_n)$ is finite with $2^n$ elements. A countable union of finite sets is countable. Explicitly, $S\mapsto\sum_{k\in S}2^{k-1}$ is a bijection from $\mathcal{F}$ onto $\{0,1,2,\dots\}$ (binary notation).
(b) Countable Theorem 1.10: a polynomial is a finite sequence of rationals.
(c) Countable $c_{00}(\mathbb{Z})=\bigcup_{N\ge1}\{(a_n): a_n=0\text{ for }n\gt N\}$, and the $N$-th set is in bijection with $\mathbb{Z}^N$, which is countable.
(d) Uncountable $\{0,1\}^{\mathbb{N}}\subseteq\mathbb{Z}^{\mathbb{N}}$, and $\{0,1\}^{\mathbb{N}}$ is uncountable (Theorem 1.12); a set with an uncountable subset is uncountable (Theorem 1.6).
(e) Uncountable $\mathcal{P}(\mathbb{N})=\mathcal{F}\cup\{\text{infinite subsets}\}$. If the infinite subsets were countable, $\mathcal{P}(\mathbb{N})$ would be a union of two countable sets, hence countable — but it is not (Theorem 1.12 via $S\mapsto\mathbf 1_S$).
Pattern "Finitely much data from a countable alphabet" is countable; "infinitely many independent choices, at least two each" is uncountable. (c) versus (d) and (a) versus (e) are the two most common CSIR traps.
✏️ Example 5 — Disjoint families: prove or disprove
Prove or disprove: (a) every family of pairwise disjoint open intervals in $\mathbb{R}$ is countable; (b) every family of pairwise disjoint nonempty subsets of $\mathbb{R}$ is countable; (c) every family of pairwise disjoint circles (curves $\{(x,y):(x-a)^2+(y-b)^2=r^2\}$, $r\gt0$) in $\mathbb{R}^2$ is countable; (d) every family of pairwise disjoint open discs in $\mathbb{R}^2$ is countable.
(a) True Let $\mathcal{I}$ be such a family. Each $I\in\mathcal{I}$ is a nonempty open interval, so it contains a rational $r(I)$ (density of $\mathbb{Q}$, §1.2). If $I\ne J$ then $I\cap J=\varnothing$, so $r(I)\ne r(J)$: $r:\mathcal{I}\to\mathbb{Q}$ is injective, and $\mathcal{I}$ is countable by Theorem 1.7.
(b) False The singletons $\{x\}$, $x\in\mathbb{R}$, are pairwise disjoint and nonempty, and there are uncountably many of them. The argument of (a) needs each set to contain a whole interval.
(c) False The concentric circles $x^2+y^2=r^2$, $r\gt0$, are pairwise disjoint and indexed by the uncountable set $(0,\infty)$. The argument of (a) breaks down because a circle contains no open disc, so there is no room to pick a rational point inside it.
(d) True Each open disc contains a point of $\mathbb{Q}^2$ (take a rational point close to its centre), distinct discs give distinct points, and $\mathbb{Q}^2$ is countable. The same proof shows: any family of pairwise disjoint nonempty open sets in $\mathbb{R}^n$ is countable.

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.

📐 Theorem 1.12 — $\{0,1\}^{\mathbb{N}}$ is uncountable
The set $\{0,1\}^{\mathbb{N}}$ of all infinite sequences of $0$s and $1$s is uncountable. Consequently $\mathcal{P}(\mathbb{N})$ is uncountable, since $S\mapsto\mathbf{1}_S$ (the sequence with $1$ in place $k$ iff $k\in S$) is a bijection $\mathcal{P}(\mathbb{N})\to\{0,1\}^{\mathbb{N}}$.

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

📐 Theorem 1.13 — $(0,1)$ and $\mathbb{R}$ are uncountable
The interval $(0,1)$ is uncountable; hence so are $\mathbb{R}$, every nondegenerate interval, the irrationals $\mathbb{R}\setminus\mathbb{Q}$ and the transcendental reals $\mathbb{R}\setminus\mathbb{A}$.

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.

📐 Theorem 1.14 — Cantor's theorem
For every set $A$ there is no surjection $A\to\mathcal{P}(A)$. Since $a\mapsto\{a\}$ is an injection, $|A|\lt|\mathcal{P}(A)|$ (Definition 1.6 below). Hence $\aleph_0=|\mathbb{N}|\lt|\mathcal{P}(\mathbb{N})|\lt|\mathcal{P}(\mathcal{P}(\mathbb{N}))|\lt\cdots$: there is no largest cardinality.

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

Interactive 2 — Cantor's Diagonal Argument, Row by Row

Someone claims the rows $s_1,s_2,s_3,\dots$ list all sequences. At step $k$ we read the diagonal digit $a_{kk}$ and write a different digit $d_k$ in the bottom row: $d_k=1-a_{kk}$ for binary rows, and $d_k=5$ (or $4$ if $a_{kk}=5$) for decimal rows. The new sequence $d$ disagrees with row $k$ in place $k$ — so it is on no row at all. Try the second list: it contains every finite binary string, yet still misses $d$.

step k—
diagonal digit a_kk—
new digit d_k—
d so far—
✏️ Example 6 — The relation $x-y\in\mathbb{Q}$
On $\mathbb{R}$ define $x\sim y\iff x-y\in\mathbb{Q}$. Show that $\sim$ is an equivalence relation, that every class is countable and dense in $\mathbb{R}$, and that there are uncountably many classes.
Equivalence $x-x=0\in\mathbb{Q}$; if $x-y\in\mathbb{Q}$ then $y-x=-(x-y)\in\mathbb{Q}$; if $x-y,\ y-z\in\mathbb{Q}$ then $x-z=(x-y)+(y-z)\in\mathbb{Q}$. (We used only that $\mathbb{Q}$ is an additive subgroup of $\mathbb{R}$.)
The classes $[x]=\{x+r:r\in\mathbb{Q}\}=x+\mathbb{Q}$, the image of $\mathbb{Q}$ under $r\mapsto x+r$; it is countable. It is dense: every interval $(a,b)$ contains a rational $r\in(a-x,b-x)$, and then $x+r\in(a,b)$.
Uncountably many By Theorem 1.4, $\mathbb{R}$ is the disjoint union of the classes. If there were only countably many classes, $\mathbb{R}$ would be a countable union of countable sets, hence countable (Theorem 1.9) — contradicting Theorem 1.13. So $\mathbb{R}/\mathbb{Q}$ is uncountable. (With the axiom of choice one shows it has exactly the cardinality $\mathfrak{c}$ of $\mathbb{R}$.)
Where it leads Choosing one point from each class inside $[0,1]$ produces the Vitali set, the standard example of a set that is not Lebesgue measurable (§4.4).

Comparing Cardinalities: Schröder–Bernstein, $\aleph_0$ and $\mathfrak{c}$

📘 Definition 1.6 — Comparing sizes
We write $|A|\le|B|$ if there is an injection $A\to B$, and $|A|\lt|B|$ if $|A|\le|B|$ but $|A|\ne|B|$ (there is an injection but no bijection). Thus $|A|\lt|\mathcal{P}(A)|$ for every set, and a set $A$ is uncountable iff $|A|\gt\aleph_0$ (every infinite set contains a countably infinite subset — Exercise IV.3 — so $\aleph_0$ is the smallest infinite size).

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.

📐 Theorem 1.15 — Schröder–Bernstein theorem
If there are injections $f:A\to B$ and $g:B\to A$, then there is a bijection $h:A\to B$. In other words, $|A|\le|B|$ and $|B|\le|A|$ imply $|A|=|B|$.

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)$. ∎

📘 Definition 1.7 — The cardinality of the continuum
We write $\mathfrak{c}=|\mathbb{R}|$ and say that a set equinumerous with $\mathbb{R}$ has the cardinality of the continuum. By Theorem 1.13, $\aleph_0\lt\mathfrak{c}$.
📐 Theorem 1.16 — Sets of cardinality $\mathfrak{c}$
Each of the following sets has cardinality $\mathfrak{c}$: (a) every interval $(a,b)$, $[a,b]$, $[a,b)$, $(a,\infty)$ with $a\lt b$; (b) $\mathcal{P}(\mathbb{N})$ and $\{0,1\}^{\mathbb{N}}$, so $2^{\aleph_0}=\mathfrak{c}$; (c) $\mathbb{R}^2$, $\mathbb{R}^n$ and $\mathbb{R}^{\mathbb{N}}$ (all real sequences); (d) $\mathbb{N}^{\mathbb{N}}$ and $\mathbb{Z}^{\mathbb{N}}$; (e) $\mathbb{R}\setminus C$ for every countable $C\subseteq\mathbb{R}$ — in particular the irrationals and the transcendental reals.

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

Arithmetic of $\aleph_0$$\aleph_0+\aleph_0=\aleph_0\cdot\aleph_0=\aleph_0$ ($\mathbb{Z}$, $\mathbb{N}\times\mathbb{N}$); $n\cdot\aleph_0=\aleph_0$.
Arithmetic of $\mathfrak{c}$$\mathfrak{c}+\mathfrak{c}=\mathfrak{c}\cdot\mathfrak{c}=\mathfrak{c}^{\aleph_0}=\mathfrak{c}$ ($\mathbb{R}\times\{0,1\}$, $\mathbb{R}^2$, $\mathbb{R}^{\mathbb{N}}$).
Exponentials$2^{\aleph_0}=\aleph_0^{\aleph_0}=\mathfrak{c}$, but $2^{\mathfrak{c}}=|\mathcal{P}(\mathbb{R})|\gt\mathfrak{c}$.
Continuum hypothesisIs there a set $S$ with $\aleph_0\lt|S|\lt\mathfrak{c}$? Gödel (1940) and Cohen (1963): the usual axioms can neither prove nor refute it. Exam questions never depend on it.
📐 Theorem 1.17 — Spaces of functions
(a) The set $C(\mathbb{R})$ of continuous functions $\mathbb{R}\to\mathbb{R}$ has cardinality $\mathfrak{c}$ (so does $C[a,b]$). (b) The set $\mathbb{R}^{\mathbb{R}}$ of all functions $\mathbb{R}\to\mathbb{R}$, and the set $\{0,1\}^{\mathbb{R}}$, have cardinality $2^{\mathfrak{c}}\gt\mathfrak{c}$.

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}$. ∎

🧭 Problem-solving strategy — how big is this set?
  1. 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$.
  2. 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.
  3. 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.
  4. 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}$.
✏️ Example 7 — Four cardinalities
Find the cardinality of: (a) the set $\mathcal{L}$ of all straight lines in $\mathbb{R}^2$; (b) the set of all circles in $\mathbb{R}^2$ with centre in $\mathbb{Q}^2$ and rational radius; (c) the set of all real sequences converging to $0$; (d) the set of all countable subsets of $\mathbb{R}$.
(a) $\mathfrak{c}$ Each line is either $y=mx+c$ or $x=c$, so $\mathcal{L}$ is the image of $(\mathbb{R}^2\times\{0\})\cup(\mathbb{R}\times\{1\})$, a set of cardinality $\mathfrak{c}$: $|\mathcal{L}|\le\mathfrak{c}$. The horizontal lines $y=c$ give an injection $\mathbb{R}\to\mathcal{L}$. Schröder–Bernstein: $|\mathcal{L}|=\mathfrak{c}$.
(b) $\aleph_0$ Such a circle is determined by $(a,b,r)\in\mathbb{Q}^2\times(\mathbb{Q}\cap(0,\infty))$, a countable set; and there are infinitely many (radii $1,2,3,\dots$).
(c) $\mathfrak{c}$ $x\mapsto(x,\tfrac x2,\tfrac x3,\dots)$ is an injection of $\mathbb{R}$ into the null sequences, and the null sequences are a subset of $\mathbb{R}^{\mathbb{N}}$, which has cardinality $\mathfrak{c}$.
(d) $\mathfrak{c}$ Singletons give $\ge\mathfrak{c}$. Every nonempty countable set is the range $\{x_1,x_2,\dots\}$ of some sequence (repeat terms if it is finite), so "range of" maps $\mathbb{R}^{\mathbb{N}}$ onto the nonempty countable subsets, which therefore number at most $|\mathbb{R}^{\mathbb{N}}|=\mathfrak{c}$ (a surjective image is no larger, using choice); adding $\varnothing$ changes nothing. Compare: all subsets of $\mathbb{R}$ number $2^{\mathfrak{c}}\gt\mathfrak{c}$.
⚠️ Counterexamples and pitfalls
  1. 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.
  2. 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.
  3. 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}}$).
  4. 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.
  5. Dense does not mean uncountable. $\mathbb{Q}$, $\mathbb{Q}+\sqrt2$, the dyadic rationals and the algebraic reals are dense in $\mathbb{R}$ and countable.
  6. Uncountable does not mean "contains an interval". $\mathbb{R}\setminus\mathbb{Q}$ and the Cantor set are uncountable but contain no interval.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. Polynomials: coefficients matter. $\mathbb{Q}[x]$ and $\mathbb{A}[x]$ are countable; $\mathbb{R}[x]$ has cardinality $\mathfrak{c}$ (the constants alone).
  12. 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

I
Sets, functions and relations.
  • 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 These are De Morgan's laws relative to $A$: $x\in A\setminus(B\cup C)\iff x\in A$ and $x\notin B$ and $x\notin C\iff x\in(A\setminus B)\cap(A\setminus C)$. Similarly $x\in A\setminus(B\cap C)\iff x\in A$ and ($x\notin B$ or $x\notin C$) $\iff x\in(A\setminus B)\cup(A\setminus C)$.
2 $x\in A\triangle B$ iff $x$ lies in exactly one of $A,B$ iff $x\in A\cup B$ but $x\notin A\cap B$. In terms of indicators, $\mathbf 1_{A\triangle B}=\mathbf 1_A+\mathbf 1_B\pmod2$; addition mod $2$ is associative, so $\mathbf 1_{(A\triangle B)\triangle C}=\mathbf 1_A+\mathbf 1_B+\mathbf 1_C=\mathbf 1_{A\triangle(B\triangle C)}\pmod2$, and sets with equal indicators are equal. ($(\mathcal{P}(X),\triangle)$ is a group with identity $\varnothing$.)
3 $f(x)=(x-1)^2-1$. On $[0,3]$ the minimum $-1$ is at $x=1$ and the maximum $f(3)=3$, so $f([0,3])=[-1,3]$. $f(x)\le3\iff(x-1)^2\le4\iff-1\le x\le3$ and $f\ge-1$ always, so $f^{-1}([-1,3])=[-1,3]$. $f^{-1}((-\infty,-1))=\varnothing$ since $f\ge-1$.
4 If $y\in f(A)\setminus f(B)$, $y=f(a)$ with $a\in A$, and $a\notin B$ (else $y\in f(B)$), so $y\in f(A\setminus B)$. If $f$ is injective and $y=f(a)$, $a\in A\setminus B$, then $y\notin f(B)$ (any $b$ with $f(b)=y$ equals $a\notin B$). If $f(x_1)=f(x_2)$ with $x_1\ne x_2$, take $A=\{x_1\}$, $B=\{x_2\}$: $f(A\setminus B)=\{f(x_1)\}$ but $f(A)\setminus f(B)=\varnothing$.
5 If $f(x_1)=f(x_2)$ then $g(f(x_1))=g(f(x_2))$, so $x_1=x_2$. If $z\in Z$, $z=g(f(x))$ is a value of $g$. Example: $X=Z=\{1\}$, $Y=\{1,2\}$, $f(1)=1$, $g\equiv1$: $g\circ f=\mathrm{id}_{\{1\}}$ is bijective, $f$ is not onto and $g$ is not one-one.
6 (a) Yes — classes $x+\mathbb{Z}$, one for each point of $[0,1)$. (b) No: not reflexive at $0$ ($0\cdot0=0$); it is an equivalence relation on $\mathbb{R}\setminus\{0\}$ with the two classes $(0,\infty)$, $(-\infty,0)$. (c) No: reflexive and symmetric, but $1\sim0$ and $0\sim-1$ while $1\cdot(-1)\lt0$. (d) No: $0\notin\mathbb{R}\setminus\mathbb{Q}$, so it is not reflexive; nor is it transitive: with $x=z=\sqrt2$, $y=0$ we have $x\sim y$ and $y\sim z$, but $x-z=0\in\mathbb{Q}$.
7 It is "$a^3\equiv b^3\pmod7$", of the form $g(a)=g(b)$, so an equivalence relation. Cubes mod $7$: $0^3\equiv0$, $1^3\equiv2^3\equiv4^3\equiv1$, $3^3\equiv5^3\equiv6^3\equiv6$. Three classes: $\{a\equiv0\}$, $\{a\equiv1,2,4\}$, $\{a\equiv3,5,6\}\pmod7$.
8 Equivalence relations correspond to partitions (Theorem 1.4). Partitions of $\{1,2,3,4\}$ by block sizes: $4$ (1 way), $3+1$ (4), $2+2$ (3), $2+1+1$ (6), $1+1+1+1$ (1): total $15$ (the Bell number $B_4$). Exactly two classes: $4+3=7$ (the Stirling number $S(4,2)=2^{3}-1$).
II
Countable sets.
  • 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 $\pi(3,4)=\tfrac{6\cdot5}{2}+3=18$. For $20$: the diagonal $d$ occupies positions $\tfrac{(d-1)(d-2)}2+1,\dots,\tfrac{d(d-1)}2$; for $d=7$ these are $16,\dots,21$. So $20=15+m$ gives $m=5$, $n=d-m=2$. Check: $\pi(5,2)=15+5=20$.
2 See the proof of Theorem 1.8 (unique factorisation $k=2^a b$, $b$ odd). $96=2^5\cdot3$, so $m-1=5$, $2n-1=3$: $\varphi^{-1}(96)=(6,2)$.
3 Count reduced fractions diagonal by diagonal: $d=2$: $1/1$ (1); $d=3$: $1/2,2/1$ (3); $d=4$: $1/3,3/1$ (5); $d=5$: $1/4,2/3,3/2,4/1$ (9); $d=6$: $1/5,5/1$ (11); $d=7$: six fractions (17); $d=8$: $1/7$ (18), $2/6$ skipped, $3/5$ (19). So $3/5$ is in position $19$ and $2/3$ in position $7$.
4 $\mathbb{Z}\times\mathbb{Q}$ is a product of two countable sets (Theorem 1.9(a)). Finite subsets of a countable set are countable (Theorem 1.10).
5 $M_2(\mathbb{Q})\approx\mathbb{Q}^4$ is countable; it is infinite since it contains $qI$ for every $q\in\mathbb{Q}$. The invertible ones form a subset (countable by Theorem 1.6) that contains the infinitely many matrices $qI$, $q\ne0$.
6 An interval with rational end points is determined by $(a,b)\in\mathbb{Q}^2$ and one of four types (open, closed, half-open either way) — at most $4\cdot\aleph_0=\aleph_0$ of them. If $\{I_j\}$ are pairwise disjoint intervals of positive length, each $I_j$ contains an open interval and hence a rational $r_j$; disjointness makes $j\mapsto r_j$ injective.
7 $x=\sqrt2+\sqrt3$: $x^2=5+2\sqrt6$, so $(x^2-5)^2=24$, i.e. $x^4-10x^2+1=0$. $y=1+\sqrt[3]2$: $(y-1)^3=2$, i.e. $y^3-3y^2+3y-3=0$.
8 An eventually periodic sequence is determined by finitely many integers: a pre-period block $(a_1,\dots,a_k)$ and a period block $(b_1,\dots,b_p)$. So the set is the image of the countable set $\bigcup_{k,p}\mathbb{Z}^k\times\mathbb{Z}^p$ (allowing $k=0$), hence countable.
9 $A\subseteq(A\setminus B)\cup B$. If $A\setminus B$ were countable, $A$ would be contained in a union of two countable sets, hence countable. Apply with $A=\mathbb{R}$ and $B=\mathbb{Q}$ or $B=\mathbb{A}\cap\mathbb{R}$ (Theorems 1.11, 1.13).
III
Uncountable sets and cardinalities.
  • 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 $\{0,1\}^{\mathbb{N}}=E\cup F$ where $E$ = sequences with finitely many $1$s (countable: they are the indicators of finite subsets of $\mathbb{N}$) and $F$ = those with infinitely many. If $F$ were countable, $\{0,1\}^{\mathbb{N}}$ would be countable. Alternatively, $(a_n)\mapsto(a_1,1,a_2,1,a_3,1,\dots)$ injects $\{0,1\}^{\mathbb{N}}$ into $F$.
2 On $\{1,\tfrac12,\tfrac13,\dots\}$, $h$ is the shift $\tfrac1n\mapsto\tfrac1{n+1}$, a bijection onto $\{\tfrac12,\tfrac13,\dots\}$; all other points (including $0$) are fixed. The only point of $[0,1]$ not in the range is $1$, so $h$ maps $[0,1]$ bijectively onto $[0,1)$.
3 $u(x)=x/(1-|x|)$ is odd, continuous, and on $[0,1)$ equals $x/(1-x)$, strictly increasing from $0$ to $+\infty$. Inverse: solve $y=x/(1-|x|)$; since $x$ and $y$ have the same sign, $x=\dfrac{y}{1+|y|}$.
4 Enumerate $\mathbb{Q}=\{q_1,q_2,\dots\}$ and let $t_n=n\sqrt2$ (distinct irrationals). Put $\psi(q_n)=t_{2n-1}$, $\psi(t_n)=t_{2n}$, $\psi(x)=x$ for every other $x$. Then $\psi$ maps $\mathbb{Q}\cup\{t_n\}$ bijectively onto $\{t_n\}$ and fixes the rest, so $\psi:\mathbb{R}\to\mathbb{R}\setminus\mathbb{Q}$ is a bijection.
5 (a) $\mathfrak{c}$: each such line other than the $y$-axis is $y=mx$, $m\in\mathbb{R}$ — a bijection with $\mathbb{R}\cup\{\text{one more}\}$. (b) $\aleph_0$: such a line is determined by a pair of points of $\mathbb{Q}^2$, so there are at most $|\mathbb{Q}^4|=\aleph_0$; the lines $y=q$, $q\in\mathbb{Q}$, show there are infinitely many.
6 $\mathfrak{c}$. Upper bound: $\le|\mathcal{P}(\mathbb{N})|=\mathfrak{c}$. Lower bound: for $T\subseteq\mathbb{N}$ let $S_T=\{4n:n\in\mathbb{N}\}\cup\{2t+1:t\in T\}$. Then $S_T$ is infinite, its complement contains every $4n+2$, and $T=\{t:2t+1\in S_T\}$, so $T\mapsto S_T$ is injective. Schröder–Bernstein.
7 (a) $\mathfrak{c}$ (Theorem 1.16(c)). (b) $\mathfrak{c}$: $\mathbb{R}[x]=\bigcup_k\mathbb{R}^{k+1}$, a countable union of sets of size $\mathfrak{c}$, is at most $|\mathbb{N}\times\mathbb{R}|=\mathfrak{c}$, and the constants give $\ge\mathfrak{c}$. (c) $\mathfrak{c}$: $\{0,1\}^{\mathbb{N}}\subseteq\mathbb{Q}^{\mathbb{N}}\subseteq\mathbb{R}^{\mathbb{N}}$. (d) $2^{\mathfrak{c}}$: indicator functions of subsets of $\mathbb{R}$.
8 Injective: if $S\ne T$, some $x$ lies in one and not the other, so $\mathbf 1_S(x)\ne\mathbf 1_T(x)$. Surjective: a function $g:X\to\{0,1\}$ is $\mathbf 1_S$ for $S=g^{-1}(\{1\})$.
9 If $X$ has $n$ elements, $\mathcal{P}(X)$ has $2^n$ — finite. If $X$ is infinite, it contains a countably infinite subset (Exercise IV.3), so $|X|\ge\aleph_0$, and Cantor's theorem gives $|\mathcal{P}(X)|\gt|X|\ge\aleph_0$ — uncountable.
IV
Proofs and challenges.
  • 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}$.
1 $x\mapsto(x,0)$ injects $[0,1]$ into the square. Conversely the square injects into $\{0,1\}^{\mathbb{N}}\times\{0,1\}^{\mathbb{N}}$ (choose for each coordinate a binary expansion, say the one not ending in $1$s when there are two), this injects into $\{0,1\}^{\mathbb{N}}$ by interleaving, and $\{0,1\}^{\mathbb{N}}$ injects into $[0,1]$ by $(a_n)\mapsto\sum2a_n3^{-n}$. (Binary expansions are used only to define an injection, which is legitimate once one expansion per point has been fixed.)
2 A strictly increasing $f$ is the increasing enumeration of its range, an infinite subset of $\mathbb{N}$, and every infinite subset arises (Theorem 1.6). So these functions are in bijection with the infinite subsets of $\mathbb{N}$, which are uncountable (Example 4(e)).
3 Choose $x_1\in X$; since $X$ is infinite, $X\setminus\{x_1,\dots,x_n\}\ne\varnothing$, and we choose $x_{n+1}$ in it (dependent choice). The $x_n$ are distinct, so $\{x_n\}$ is countably infinite. Then $\sigma(x_n)=x_{n+1}$, $\sigma(x)=x$ otherwise, is a bijection $X\to X\setminus\{x_1\}$. Conversely, a finite set is not equinumerous with a proper subset (Theorem 1.5).
4 For each isolated $a$ choose rationals $p_a\lt a\lt q_a$ with $(p_a,q_a)\cap A=\{a\}$ (shrink $(a-\delta,a+\delta)$ to rational end points). If $a\ne b$ are isolated with $(p_a,q_a)=(p_b,q_b)$, this interval meets $A$ in $\{a\}$ and in $\{b\}$ — impossible. So $a\mapsto(p_a,q_a)$ injects the isolated points into $\mathbb{Q}^2$.
5 At a strict local maximum $a$ choose rationals $p_a\lt a\lt q_a$ with $f(x)\lt f(a)$ for $x\in(p_a,q_a)$, $x\ne a$. If $a\ne b$ had the same interval, then $b\in(p_a,q_a)$ gives $f(b)\lt f(a)$ and $a\in(p_b,q_b)$ gives $f(a)\lt f(b)$. Contradiction, so $a\mapsto(p_a,q_a)\in\mathbb{Q}^2$ is injective. (Non-strict local maxima can be uncountable: a constant function.)
6 Upper bound: bijections are elements of $\mathbb{N}^{\mathbb{N}}$, of cardinality $\mathfrak{c}$. Lower bound: for $S\subseteq\mathbb{N}$ let $\sigma_S$ swap $2k-1$ and $2k$ for each $k\in S$ and fix everything else. Each $\sigma_S$ is a bijection and $S=\{k:\sigma_S(2k)=2k-1\}$, so $S\mapsto\sigma_S$ is injective. Schröder–Bernstein gives $\mathfrak{c}$.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

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.

Idea Finite data from a countable alphabet is countable; infinitely many independent choices is not.
Options (A) countable (Theorem 1.10). (B) countable: a polynomial is a finite sequence from the countable set $\mathbb{A}$. (C) uncountable: such sequences correspond bijectively to infinite subsets of $\mathbb{N}$ (Exercise IV.2). (D) countable: each line is determined by two points of $\mathbb{Q}^2$.
Answer (C).

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}}$.

Upper bound An equivalence relation is a subset of $\mathbb{N}\times\mathbb{N}$, and $|\mathcal{P}(\mathbb{N}\times\mathbb{N})|=|\mathcal{P}(\mathbb{N})|=\mathfrak{c}$.
Lower bound For $S\subseteq\{2,3,4,\dots\}$ let $R_S$ have the classes $\{1\}\cup S$ and the singletons $\{n\}$, $n\notin S\cup\{1\}$. The class of $1$ recovers $S$, so $S\mapsto R_S$ is injective, and $\{2,3,\dots\}$ has $\mathfrak{c}$ subsets.
Answer (C) $\mathfrak{c}$, by Schröder–Bernstein. ((D) would need uncountably many points to partition.)

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

Idea Preimages commute with every set operation (Theorem 1.2(1)); images do not.
Counterexample $X=\{1,2\}$, $Y=\{0,9\}$, $f\equiv0$, $A=\{1\}$, $B=\{2\}$: (A) $\varnothing\ne\{0\}$; (C) $f(\{2\})=\{0\}$ but $Y\setminus f(A)=\{9\}$; (D) $f^{-1}(\{0\})=X\ne A$.
Answer (B).

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.

(A) Countable If $x^n=r\in\mathbb{Q}$, $x$ is a root of $qt^n-p$ where $r=p/q$; so the set lies in $\mathbb{A}\cap\mathbb{R}$ (Theorem 1.11). It is infinite ($\mathbb{Q}$ is inside).
(B) Uncountable $(\varepsilon_n)\mapsto(\varepsilon_n/n)$ maps $\{0,1\}^{\mathbb{N}}$ injectively into rational null sequences.
(C) Uncountable It contains every singleton $\{x\}$, $x\in\mathbb{R}$.
(D) Countable A circle is determined by $(a,b,r)\in\mathbb{A}^2\times\mathbb{Q}$, a countable set.
Answer (A) and (D).

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.

(A) True $A=(A\cap\mathbb{Q})\cup(A\setminus\mathbb{Q})$ and $A\cap\mathbb{Q}$ is countable (Exercise II.9).
(B) False $A=\mathbb{R}\setminus\mathbb{Q}$ is uncountable and contains no interval (every interval contains a rational).
(C) True A point of $A$ that is not a limit point of $A$ is isolated in $A$, and the isolated points form a countable set (Exercise IV.4). Since $A$ is uncountable, not all its points are isolated.
(D) False $A=(0,\infty)$: its complement $(-\infty,0]$ is uncountable.
Answer (A) and (C).

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.

(A) True Every strictly increasing function is non-decreasing, and the strictly increasing ones are already uncountable (Exercise IV.2). (Careful: the non-decreasing functions with values in $\{1,2\}$ are only countably many.)
(B) True An eventually constant $f$ is determined by a finite initial block $(f(1),\dots,f(N))$ and the constant value: finite data from $\mathbb{N}$.
(C) False These are the maps $\mathbb{N}\to\{1,2\}$, a copy of $\{0,1\}^{\mathbb{N}}$.
(D) False The involutions $\sigma_S$ swapping $2k-1\leftrightarrow2k$ for $k\in S$ (Exercise IV.6) are distinct for distinct $S\subseteq\mathbb{N}$, and satisfy $\sigma_S\circ\sigma_S=\mathrm{id}$.
Answer (A) and (B).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. 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.
  2. 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?"
  3. 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–Teaching NexusResearch-tutored · optional, about 45 minutes

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.

  1. 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$.
  2. 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.
  3. Observe where $1/n$ first appears and conjecture a formula; explain why the list nevertheless contains every positive rational.
  4. 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.

Instructor note: $3/5$ is in position $10$ of the Calkin–Wilf list (position $19$ in the diagonal list), $22/7$ in position $519$ (diagonal list: $263$), and $1/n$ first appears in position $2^{n-1}$ — a good illustration that an enumeration can reach some elements very late. The best approximation to $\sqrt2$ with denominator at most $100$ is $140/99$ (the mediant of the convergents $41/29$ and $99/70$), with the convergent $99/70$ a very close second.

🧪 Self-check quiz

0/5 correct

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