Proving a set of functions is uncountable I am trying to prove that $D(\mathbb{N}$)={ $f\in \mathbb{N}^\mathbb{N}$ | f is a bijection such that $f(n)\neq n$ for all $n\in\mathbb{N}$} is uncountable. So, I was thinking of showing $D(\mathbb{N})$ ~ $P(\mathbb{N})$ using Cantor Bernstein Theorem. 
For the one direction, is it found to say since $D(\mathbb{N})\subset \mathbb{N}^\mathbb{N}$ ~$P(\mathbb{N})$ then there is an injection from $D(\mathbb{N})$ to $P(\mathbb{N})$? 
I am not too sure how to go about the other direction. Should I show equinumerous to functions from $\mathbb{N}^\mathbb{N}$ instead of using the power set? 
 A: Given $s:E\to \{1,2\}$ where $E$ is the even numbers define
$$f_s(2n)=4n+s(2n)$$
This satisfies $f_s(2n)\neq 2n$.
Now extend $f_s$ to an bijection st $f_s(n)\neq n$. There are many ways to do this, eg just define $f_s(2n+1)$ inductively to be the smallest allowed value.  
Then $f_s$ is a bijection, satisfying your condition and $f_s\neq f_t$ for $s\neq t$.
A: Here's an injective map $\mathcal P(\Bbb N)\to D$:
Given $A\subseteq\Bbb N$, defien $f_A\colon \Bbb N\to\Bbb N$ as
$$ f(n)=(n\operatorname \Delta 2)\operatorname \Delta 1_A(\lfloor n/2\rfloor)$$
where $\Delta$ is the binary "xor" operator and $1_A$ is the indicator fucntion of the set $A$. 
Xor'ing with 2 first ensures that $f_A$ has no fixpoints, xor'ing with the indicator function produces lots of variation.
(The above assumes $0\in\Bbb N$)
Note that this not onyl shows $D$ is uncountable, but even that it has continuum-cardinality.
A: Let $B$ be the set of binary sequences. Let $(a_n)\in B.$ If $a_1 = 0,$ we permute $1,2,3,4$ as follows: $1\to 2 \to 3\to 4 \to 1.$ If $a_1 = 1,$ we take the inverse of this permutation. We let $a_2$ "operate" on $5,6,7,8$ in exactly the same way ... Let this process percolate onwards to define an element of $D(\mathbb N).$ The map sending $(a_n)$ to an element of $D(\mathbb N)$ in this way is injective. It shows $D(\mathbb N)$ has at least the cardinality of $B,$ which is $c,$ the cardinality of the continuum. 
A: I think the easiest way to show that it is uncountable (without identifying what its cardinality actually is) is to just use the classic diagonal argument. Given a proposed enumeration $f_n$, we inductively define a function $f$ by introducing a set $A_0=\mathbb{N}$, then for each $n \in \mathbb{N}$ we define $f(n)$ to be an element of $A_{n-1} \setminus \{ n,f_n(n) \}$ and then define $A_n=A_{n-1} \setminus \{ f(n) \}$. 
This produces an injection from $\mathbb{N}$ to itself with no fixed points which is not in the given enumeration; it is not in the given enumeration because $\forall n \: f_n(n) \neq f(n)$. If additionally we perform the selection of $f(n)$ such that for any $k \in \mathbb{N}$ there exists $N \in \mathbb{N}$ such that for all $n \geq N$, $k \not \in A_n$, then we have in fact constructed a bijection and so we are done. The simplest way to do that is to choose $f(n)=\min A_{n-1} \setminus \{ n,f_n(n) \}$.
