Solution. The given \(f\) sends the odd numbers onto \(\{0,1,2,\dots \}\) and the even numbers onto the negatives. Any rule that runs through \(\mathbb {Z}\) without repetition or omission will do; a compact one is \[h(n)=\left \lceil \frac {n}{2}\right \rceil (-1)^{n+1},\] which gives \(h(1)=1\), \(h(2)=-1\), \(h(3)=2\), \(h(4)=-2\), and so on, listing \(\mathbb {Z}\setminus \{0\}\); adjoining \(h(0)=0\), or shifting the index by one, covers \(\mathbb {Z}\) itself.

That two quite different formulas both work is the point: countability asserts that some one-one correspondence exists, and never that it is unique.

Proof. Let \(A\) be infinite. Choose \(a_1\in A\); since \(A\) is infinite it is not empty, so this is possible. Having chosen distinct \(a_1,\dots ,a_n\), the set \(A\setminus \{a_1,\dots ,a_n\}\) is still infinite — removing finitely many elements from an infinite set cannot exhaust it — so we may choose \(a_{n+1}\) in it, distinct from all the previous ones.

This produces a sequence \(a_1,a_2,a_3,\dots \) of distinct elements of \(A\), and \(\{a_n:n\in \mathbb {N}\}\) is a countable subset of \(A\).

The construction makes infinitely many choices, so it uses the axiom of choice in the form of dependent choice; that is unavoidable here and is worth noticing rather than hiding. □

Proof. Let \(A\) be infinite. By the previous theorem it has a countable subset \(C=\{a_1,a_2,a_3,\dots \}\) of distinct elements. Put \[B=A\setminus \{a_1\},\] which is a proper subset of \(A\). We exhibit a bijection \(f:A\rightarrow B\).

Define \[f(x)=\begin {cases} a_{n+1} & \text {if } x=a_n \text { for some } n,\\ x & \text {if } x\notin C . \end {cases}\] On \(C\) this shifts the sequence one place along, which is injective and hits every \(a_n\) with \(n\geq 2\); off \(C\) it is the identity. So \(f\) is a bijection of \(A\) onto \(A\setminus \{a_1\}=B\).

This property is often taken as the definition of an infinite set, and it is exactly what fails for finite sets: no finite set can be put in bijection with a proper subset of itself. □

Proof. Since each \(A_n\) is countable, its elements can be listed: \[A_n=\{a_{n1},a_{n2},a_{n3},\dots \}.\] Arrange the whole collection in an infinite array whose \(n\)-th row is \(A_n\): \[\begin {array}{cccc} a_{11} & a_{12} & a_{13} & \cdots \\ a_{21} & a_{22} & a_{23} & \cdots \\ a_{31} & a_{32} & a_{33} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end {array}\] Now traverse the array along its finite diagonals: first \(a_{11}\), then \(a_{12},a_{21}\), then \(a_{13},a_{22},a_{31}\), and so on. Every entry lies on exactly one diagonal and each diagonal is finite, so this enumerates the whole array in a single sequence.

Deleting repetitions — an element may appear in more than one \(A_n\) — leaves an enumeration of \(\bigcup _{n=1}^{\infty }A_n\), which is therefore countable.

A traversal by rows would fail: it never finishes the first row, so no element of \(A_2\) is ever reached. The diagonal order is what makes the argument work. □

Proof. For each \(n\in \mathbb {N}\) let \[A_n=\left \{\frac {m}{n}: m\in \mathbb {Z}\right \},\] the rationals with denominator \(n\). Each \(A_n\) is countable, being indexed by \(\mathbb {Z}\), and every rational lies in some \(A_n\), so \[\mathbb {Q}=\bigcup _{n=1}^{\infty }A_n .\] By the previous theorem a countable union of countable sets is countable, so \(\mathbb {Q}\) is countable.

It is worth pausing on how strange this is: \(\mathbb {Q}\) is dense in \(\mathbb {R}\), with rationals in every interval however short, yet there are no more of them than there are positive integers. □

Proof. Let \(A\) be countable with enumeration \(A=\{a_1,a_2,a_3,\dots \}\), and let \(B\subseteq A\) be infinite.

Run through the enumeration of \(A\) and record the indices at which an element of \(B\) appears. Let \(n_1\) be the first such index, \(n_2\) the next, and so on; because \(B\) is infinite this never terminates, so we obtain \(n_1<n_2<n_3<\cdots \) and \[B=\{a_{n_1},a_{n_2},a_{n_3},\dots \}.\] The map \(k\mapsto a_{n_k}\) is a bijection from \(\mathbb {N}\) onto \(B\), so \(B\) is countable.

The hypothesis that \(B\) is infinite is what guarantees the list of indices does not stop; a finite subset is of course not countable in this sense. □

Solution.

(a) \([0,1]\) is uncountable

Suppose it were countable, say \([0,1]=\{a_1,a_2,a_3,\dots \}\), and write each in decimal as \(a_k=0.a_{k1}a_{k2}a_{k3}\dots \). Define \(b=0.b_1b_2b_3\dots \) by \[b_k=\begin {cases}5,& a_{kk}\neq 5\\ 6,& a_{kk}=5\end {cases}\] Then \(b\in [0,1]\), and \(b\) differs from \(a_k\) in its \(k\)th decimal place for every \(k\). Choosing only the digits \(5\) and \(6\) avoids the ambiguity of expansions ending in all \(9\)s, so \(b\neq a_k\) for all \(k\) — contradicting the assumption that the list was complete. This is Cantor’s diagonal argument.

(d) \((0,1)\) is uncountable

If \((0,1)\) were countable then \([0,1]=(0,1)\cup \{0,1\}\) would be a union of a countable set and a finite set, hence countable, contradicting (a).

(b) \(\mathbb {R}\) is uncountable

\(\mathbb {R}\) contains \([0,1]\), and a subset of a countable set is countable; so if \(\mathbb {R}\) were countable, \([0,1]\) would be too. Alternatively \(x\mapsto \tan \big (\pi (x-\frac 12)\big )\) is a bijection from \((0,1)\) onto \(\mathbb {R}\).

(c) The irrationals are uncountable

Write \(\mathbb {R}=\mathbb {Q}\cup (\mathbb {R}\setminus \mathbb {Q})\). The rationals are countable. If the irrationals were also countable, \(\mathbb {R}\) would be a union of two countable sets and hence countable, contradicting (b).

The pattern in (b), (c) and (d) is worth noting: once one uncountable set is in hand, others follow by closure properties of countability rather than by repeating the diagonal argument.