Past exam of the mathematics course of the University of Cambridge / 2020 / ia / Paper 2 / 8D (Numbers and Sets)

A set is countable when it is finite or admits a bijection with a subset of $\mathbb{N}$; equivalently, its elements can be listed in a sequence. The integers are countable, for example in the order $0,1,-1,2,-2,\dots$. Enumerating pairs by diagonals, or applying the Cantor pairing function, then shows that $\mathbb{N}\times \mathbb{Z}$ is countable.

Suppose instead that the power set $\mathcal{P}(\mathbb{N})$ had an enumeration $A_1,A_2,\dots$. The Cantor diagonal argument formsFor every $n$, the set $D$ differs from $A_n$ at the element $n$, so it is absent from the alleged enumeration. Therefore

If $x$ is a fixed point of $f$, thenConversely, applying the same argument to $f={\sigma }^{-1}g\sigma$ transports every fixed point of $g$ back to one of $f$. Thus the bijection $\sigma$ restricts to a bijection between the two fixed-point sets, so conjugate functions have the same number of fixed points.

Choose a bijection $h:\mathbb{N}\to \mathbb{Z}$, and conjugate the translation of the integers:Then $f$ is a bijection of $\mathbb{N}$. Its $k$th iterate is $h^{-1}(z\mapsto z+k)h$, which has no fixed point for every $k\ge 1$. Hence $f\in T$.

The set $T$ is uncountable. Partition $\mathbb{N}$ into countably many infinite sets $B_1,B_2,\dots$, and choose bijections $h_j:B_j\to \mathbb{Z}$. For every subset $A\subseteq \mathbb{N}$, define a permutation $f_A$ separately on each block byEvery positive iterate translates each integer coordinate by a nonzero amount, so it has no fixed point and $f_A\in T$. Distinct subsets $A$ give distinct permutations, yielding an injection $\mathcal{P}(\mathbb{N})\hookrightarrow T$. Since the power set is uncountable,In fact its cardinality is the continuum, because it is a subset of all functions $\mathbb{N}\to \mathbb{N}$.