# Cardinality of set of all bijections $\mathbb{N}\to\mathbb{N}$; is my proof correct?

I need to find cardinality of a set containing all bijections $\mathbb{N} \to \mathbb{N}$.

My proof goes like that:
Let $S$ be the set containing all bijections $\mathbb{N} \to \mathbb{N}$. There exists trivial injection $S \to {\mathbb{N}}^{\mathbb{N}}$ (identity). Therefore $S\subset\mathbb{N}^\mathbb{N}$. We define $$F: \{0,1\}^\mathbb{N} \to S$$ as $$F(f)=\lambda x.\text{if } f(x)=0 \text{ then }2x\text{ else }(2x+1)$$ $F$ is injective. Proof: Assume $F$ isn't injective. Then $\exists f_1, f_2 \in \mathbb{N}\to\{0,1\}. f_1 \ne f_2, F(f_1) = F(f_2)\implies\exists x\in\mathbb{N}.f_1(x) \ne f_2(x)\implies F(f_1)(x) \ne F(f_2)(x) \implies F(f_1) \ne F(f_2)$ Contradiction. It implies $\{0,1\}^\mathbb{N}\subset S$. $$|\{0,1\}^\mathbb{N}| = 2^{\aleph_0} =\mathfrak{c} \\ |\mathbb{N}^\mathbb{N}| = \mathfrak{c} \\ \{0,1\}^\mathbb{N}\subset S\subset\mathbb{N}^\mathbb{N}\\ \text{Cantor-Bernstein:} \\ |\{0,1\}^\mathbb{N}| \le |S| \le |\mathbb{N}^\mathbb{N}| \\ |S| = \mathfrak{c}$$ Is this proof correct?

• Your definition of $F$ isn't clear – David Peterson Jan 16 '15 at 21:03
• I assume $F(f)(x)=2x+f(x)$? – Hagen von Eitzen Jan 16 '15 at 21:05
• Dear god please write your proofs in english. Symbols are not easy to read. A proof should read like a proper collection of grammatically correct sentences. – Dan Rust Jan 16 '15 at 21:08
• Hagen von Eitzen: That's much more simple indeed. Daniel Rust: Sorry for that, I will remember not to do it anymore. Anyways, is the idea of the proof correct or do I miss something? – user188369 Jan 16 '15 at 21:13
• Your $F$ is not well-defined, because for $f = 1_ℕ$, either observe that $F(f)(0) = 1 > 0$ or $F(f)(1) = 3 > 1$ (depending on whether $0 ∈ ℕ$ or not (it’s not)), and since $F(f)(x) ≥ x$, one concludes that $F(f)$ is not surjective. – k.stm Jan 16 '15 at 21:18

@Eric Troy: I think I got your idea. You break the set of naturals into pairs. Now you flip the pair $n$ or not according to $a_n=1$, or $a_n=0$. You get for every infinite sequence of $0$ and $1$ $(a_n)$ a bijection of $\mathbb{N}$.
$$(a_n) \mapsto \prod_n (2n-1,2n)^{a_n}$$