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?

  • 1
    $\begingroup$ Your definition of $F$ isn't clear $\endgroup$ – David Peterson Jan 16 '15 at 21:03
  • $\begingroup$ I assume $F(f)(x)=2x+f(x)$? $\endgroup$ – Hagen von Eitzen Jan 16 '15 at 21:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Dan Rust Jan 16 '15 at 21:08
  • $\begingroup$ 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? $\endgroup$ – user188369 Jan 16 '15 at 21:13
  • $\begingroup$ 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. $\endgroup$ – 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 compact form:

$$(a_n) \mapsto \prod_n (2n-1,2n)^{a_n}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy