Past exam of the mathematics course of the University of Cambridge / 2013 / ia / Paper 4 / 7E (Numbers and Sets)

Use “countable” to include finite and empty sets: a countable set admits an injection into ${\mathbb{N}}_0$. If $B\subseteq A$ and $j:A\to {\mathbb{N}}_0$ is injective, restricting $j$ to $B$ proves that $B$ is a countable set.

For a countable union of countable sets, index the family as $A_0,A_1,\dots$ and choose an injection $j_i:A_i\to {\mathbb{N}}_0$ for each member. For an element $a$ of the union, let $i(a)$ be the least index containing it, and assignThis is injective: equality of the pair gives the same set index and then the same element. Finally the Cantor pairing functioninjects ${\mathbb{N}}_0^2$ into ${\mathbb{N}}_0$. The union is therefore countable. The proof uses chosen injections for the family, as in the usual set-theoretic framework with axiom of countable choice.

For the cardinality of integer-periodic function spaces, fix a positive period $n$ first. A periodic function $\mathbb{Z}\to \mathbb{Z}$ with that period is completely and uniquely determined by its $n$ values at $0,\dots ,n-1$, so this class is in bijection with ${\mathbb{Z}}^n$. The integers are a countable set, and repeated pairing shows that a finite Cartesian product of countable sets is countable. Taking the union over positive $n$ and using the countable union of countable sets proves that the integer-domain periodic functions form a countable set.

For the rational domain, even period one leaves infinitely many independent choices. Let $q_k=1/(k+2)$ for $k\in {\mathbb{N}}_0$; these are distinct members of $\mathbb{Q}\cap [0,1)$. For every subset $A\subseteq {\mathbb{N}}_0$, defineThe fractional part is unchanged by adding one, so $f_A$ is an integer-valued periodic function on $\mathbb{Q}$. Distinct subsets give distinct functions because $f_A(q_k)$ records whether $k\in A$. Thus the uncountable power set of ${\mathbb{N}}_0$ injects into these functions. The rational-domain periodic functions form an uncountable set. The difference is that $\mathbb{Z}$ has only finitely many residue classes modulo a fixed integer period, whereas $\mathbb{Q}$ has infinitely many.

Use the parabola obstruction to countable line coverings. The curveis in bijection with the real line and hence is an uncountable set. A vertical line meets $\mathcal{P}$ in one point. A nonvertical line $y=ax+b$ meets it only where $t^2-at-b=0$, so it meets $\mathcal{P}$ in at most two points.

If countably many lines covered the plane, their intersections with $\mathcal{P}$ would cover $\mathcal{P}$. That would express $\mathcal{P}$ as a countable union of countable sets, indeed of sets with at most two elements, contradicting its uncountability. Therefore no countable collection of lines covers the plane.