La cardinalidad del conjunto de bijective funciones en $\mathbb{N}$?

Question

Me enteré de que el conjunto de todos los uno-a-uno asignaciones de $\mathbb{N}$ a $\mathbb{N}$ tiene cardinalidad $|\mathbb{R}|$.

¿Qué acerca de surjective funciones y bijective funciones?

Answer 1

La misma. Basta para mostrar que no se $2^\omega=\mathfrak c=|\Bbb R|$ bijections de$\Bbb N$$\Bbb N$. Deje $P$ el conjunto de pares $\{2n,2n+1\}$$n\in\Bbb N$. (Mi $\Bbb N$ incluye a $0$.) Para cada una de las $S\subseteq P$ definir

$$f_S:\Bbb N\a\Bbb N:k\mapsto\begin{cases} k+1,&\text{if }k\in p\text{ for some }p\in S\text{ and }k\text{ is even}\\ k-1,&\text{if }k\in p\text{ for some }p\in S\text{ and }k\text{ is odd}\\ k,&\text{if }k\notin\bigcup S\;; \end{casos}$$

la función de $f_S$ simplemente intercambia los miembros de cada par $p\in S$. Claramente $|P|=|\Bbb N|=\omega$, lo $P$ $2^\omega$ subconjuntos $S$, cada definición de una clara bijection $f_S$$\Bbb N$$\Bbb N$. Por lo tanto, hay por lo menos $2^\omega$ tal bijections. Y cada una de las funciones de cualquier tipo de $\Bbb N$ $\Bbb N$es un subconjunto de a $\Bbb N\times\Bbb N$, por lo que hay en la mayoría de las $2^\omega$ funciones en total. Por lo tanto, no son exactamente $2^\omega$ bijections.

Answer 2

Además de Asaf la respuesta, se puede utilizar la siguiente argumentación directa para surjective funciones:

---

Considere la posibilidad de cualquier asignación de $f: \Bbb N \to \Bbb N$ tal forma que:

$$\forall n \in \Bbb N: f(2n) = n$$

A continuación, $f$ es surjective, sino para cualquier tipo de $g: \Bbb N \to \Bbb N$ podemos definir $f(2n+1) = g(n)$, mostrando efectivamente que hay, al menos, $2^{\aleph_0}$ surjective funciones-hemos demostrado que uno de cada función arbitraria $g: \Bbb N \to \Bbb N$.

Answer 3

Ambos tienen cardinalidad $2^{\aleph_0}$. Tenga en cuenta que el conjunto de la bijective funciones es un subconjunto de la surjective funciones.

A ver que no se $2^{\aleph_0}$ bijections, tomar cualquier partición de $\Bbb N$ en dos conjuntos infinitos, y cambiar entre ellos. No es difícil mostrar que hay $2^{\aleph_0}$ particiones como que, por lo que estamos por hacer.

Answer 4

Elija un número natural. Cómo quedan muchos para elegir?

Más rigurosamente, $$\operatorname{Aut}\mathbb{N} \cong \prod_{n \in \mathbb{N}} \mathbb{N} \setminus \{1, \ldots, n\} \cong \prod_{n \in \mathbb{N}} \mathbb{N} \cong \mathbb{N}^\mathbb{N} = \operatorname{End}\mathbb{N},$$ where $\{1, \ldots, 0\} := \varnothing$. The first isomorphism is a generalization of $\#S_n = n!$ Edit: pero no he pensado todavía, voy a volver a usted.