Problem 1308

### Part (a): Prove that $A$ is non-empty.

1. Consider a subset $E = \{x_1, x_2, \ldots, x_{2008}\}$ of $\mathbb{N}$ which contains exactly 2008 elements.
2. Define a function $f: \mathbb{N} \to \mathbb{N}$ such that:
$$f(x_i) = x_{i+1} \quad \text{for} \quad i = 1, 2, \ldots, 2007 \quad \text{and} \quad f(x_{2008}) = x_1$$
This means $f$ cycles through the elements of $E$.
3. For any $x \notin E$, define $f(x) = x$.
4. We need to check that $f \in A$:
- For $k \in \{1, 2, \ldots, 2007\}$, $f^{[k]} \neq \mathrm{Id}_{\mathbb{N}}$ because $f$ cycles through $E$ and does not return to the identity function until the 2008th iteration.
- $f^{[2008]} \equiv \mathrm{Id}_{\mathbb{N}}$ because after 2008 applications of $f$, each element in $E$ returns to its original position, and elements not in $E$ remain unchanged.

Thus, $f \in A$, proving that $A$ is non-empty.

### Part (b): Find, with proof, whether $A$ is infinite.

1. Consider the construction of $f$ as in part (a). We can choose different subsets $E$ of $\mathbb{N}$ with 2008 elements.
2. There are infinitely many ways to choose such subsets $E$ because $\mathbb{N}$ is infinite.
3. For each distinct subset $E$, we can define a different function $f$ as described in part (a).
4. Therefore, there are infinitely many functions $f$ that satisfy the conditions to be in $A$.

Thus, $A$ is infinite.

### Part (c): Prove that all the elements of $A$ are bijective functions.

1. Let $f \in A$. We need to show that $f$ is bijective.
2. Injectivity: Suppose $f(a) = f(b)$. We need to show $a = b$.
- If $a, b \notin E$, then $f(a) = a$ and $f(b) = b$, so $a = b$.
- If $a, b \in E$, then $f$ is a permutation of $E$. Since permutations are bijective, $f(a) = f(b)$ implies $a = b$.
3. Surjectivity: We need to show that for every $y \in \mathbb{N}$, there exists $x \in \mathbb{N}$ such that $f(x) = y$.
- If $y \notin E$, then $f(y) = y$, so $x = y$.
- If $y \in E$, since $f$ is a permutation of $E$, there exists $x \in E$ such that $f(x) = y$.

Thus, $f$ is bijective.

$\blacksquare$