Paper 2, Section II, D

Numbers and Sets | Part IA, 2020

(a) Define what it means for a set to be countable. Prove that N×Z\mathbb{N} \times \mathbb{Z} is countable, and that the power set of N\mathbb{N} is uncountable.

(b) Let σ:XY\sigma: X \rightarrow Y be a bijection. Show that if f:XXf: X \rightarrow X and g:YYg: Y \rightarrow Y are related by g=σfσ1g=\sigma f \sigma^{-1} then they have the same number of fixed points.

[A fixed point of ff is an element xXx \in X such that f(x)=xf(x)=x.]

(c) Let TT be the set of bijections f:NNf: \mathbb{N} \rightarrow \mathbb{N} with the property that no iterate of ff has a fixed point.

[The kth k^{\text {th }}iterate of ff is the map obtained by kk successive applications of ff.]

(i) Write down an explicit element of TT.

(ii) Determine whether TT is countable or uncountable.

Typos? Please submit corrections to this page on GitHub.