Es el grupo simétrico de números naturales contables?

Question

Supongo que es demasiado difícil una pregunta acerca de la cardinalidad de $S_{\mathbb{N}}$, así que me gustaría preguntar si es contable o no.

Traté de demostrarlo es incontable algo imitación de la diagonal de Cantor argumento, pero fracasó.

Answer 1

He aquí una muy tonto argumento para demostrar $|S_\mathbb{N}| \geq 2^\mathbb{N}$.

Un hecho a partir del cálculo nos dice que no absolutamente convergente la serie cuyos términos converge a cero se pueden reordenar para tomar el valor de cualquier real. Así, por cada $\alpha$, no es una permutación tal que $$ \sum\frac{(-1)^{n_i}}{n_i}= \alpha $$

Así que debe de ser al menos igual número de permutaciones como reales!

Answer 2

Podemos hacer una diagonal argumento directamente, y también: Dejar $(\sigma_0,\sigma_1,\sigma_2,\ldots)$ ser una secuencia infinita de bijections $\mathbb N\to\mathbb N$. Queremos encontrar un bijection $f$ que no está en la secuencia:

Deje que $f$ ser el bijection tal que para cada $k$, $f$ swaps de $2k$ y $2k+1$ si $\sigma_k(2k)=2k$ y los deja solos de otra manera.

Por la construcción de $f$ es un bijection, y diferente de cada uno de los $\sigma_i$s.

(Tenga en cuenta que este argumento muestra menos de lo que el otro responde: sólo cloncludes que la cardinalidad de $S_{\mathbb N}$ es mayor que $\aleph_0$, no se que equivale a $2^{\aleph_0}$.)

---

Tenga en cuenta que a diferencia de en el caso finito, el grupo generado por todos simples transposiciones no es todo el grupo de permutación. En cambio es el conjunto de todas las permutaciones "con finito de apoyo", que es contable.

Answer 3

$S_{\Bbb, N}$ es simplemente el conjunto de bijections de $\Bbb N$ a sí mismo, que tiene cardinalidad de $2^\omega=\mathfrak{c}$. (En particular, es incontable.)

Es claro que $|S_{\Bbb, N}|\le\omega^\omega=2^\omega$. En el otro sentido, vamos a $A$ ser cualquier subconjunto infinito de $\Bbb$ N, y enumerar $A=\{a_k:k\in\Bbb, N\}$ en orden creciente. Vamos

$$\sigma_A:\Bbb N\a\Bbb N:n\mapsto\begin{casos} a_{2k+1},&\text{si }n=a_{2k}\text{ para algunos }k\in\Bbb N\\ a_{2k},&\text{si }n=a_{2k+1}\text{ para algunos }k\in\Bbb N\\ n,&\text{si }n\in\Bbb N\setminus\;. \end{casos}$$

$\Bbb N$ tiene $2^\omega$ infinitos subconjuntos, y $\sigma_A=\sigma_B$ ffi $A=B$, entonces $|S_{\Bbb, N}|\ge 2^\omega$. Por lo tanto, $|S_{\Bbb, N}|=2^\omega$.

Answer 4

Un argumento similar a la de Brian, pero tal vez un poco más fácil: dado un conjunto $S\subseteq\mathbb{N}$, deje que $\pi_S$ ser la permutación que se intercambia $2n$ y $2n+1$ por cada $n\in S$, y deja todos los otros números fijos. Entonces $\pi_S=\pi_{S}\ffi S=S'$, entonces $\vert S_\mathbb{N}\vert=2^\omega$.

¿Qué acerca de las generalizaciones arbitraria de conjuntos infinitos, es decir, para los cuales $$ podemos concluir que $S_A$ tiene cardinalidad de $2^$? (Suponga que la elección no mal, así que esto es trivial.)

• Mi argumento anterior funciona con cualquier conjunto infinito de $$ que se pueden poner en bijection con su doble $A\sqcup$.

• Brian respuesta nos obliga a asumir que cada infinita subconjunto de a se puede escribir como un discontinuo de la unión de los pares. Esto no necesita ser el caso, por ejemplo, si $a=X\times\omega$ para un conjunto amorfo de $X$ - una de las "filas" de igual a $X$ no necesita ser splittable en pares (tenga en cuenta que esta $A$ se puede poner en bijection con $A\sqcup$). (Como está escrito, también se requiere de $2^$ a tienen la misma cardinalidad que el conjunto de los infinitos subconjuntos de $A$, lo cual no es siempre cierto, pero esto es fácilmente corregible: $X$ finitos, tienen los asociados de permutación de fijar exactamente los elementos que no en $X$.)

• Por otra parte, Brian argumento sólo produce una surjection de $S_A$ a $2^$, mientras que el argumento por encima de los rendimientos de una inyección va para otro lado; en general, esto es más fuerte. (El problema con Brian argumento es que uno debe de elegir una manera de escribir un determinado infinito $X\subseteq$ como distinto de la unión de pares.)

• Por otro lado, la relación entre Brian y mi hipótesis no es clara. Ciertamente, la mina no implica la de Brian, pero lo contrario puede ser cierto.

Answer 5

El conjunto de puntos fijos de cualquier permutación de $\pi\colon\mathbb{N}\to\mathbb{N}$ (es decir, el conjunto $\{x\mid \pi(x)=x\}$) puede ser cualquier subconjunto de $\mathbb{N}$, excepto de la forma $\mathbb{N}\setminus\{n\}$ $n$. Así que hay al menos tantas permutaciones como hay tales subconjuntos y hay una cantidad no numerable de subconjuntos.

_{Gracias a Henning Makholm por señalar un error en la versión original de esta respuesta.}