¿Cuál es la cardinalidad del grupo de biyecciones de $\Omega$ a $\Omega$ con un apoyo finito?

Question

Estas preguntas surgieron en el debate en esta pregunta ,

¿Cuál es la cardinalidad del grupo de biyecciones de $\Omega$ a $\Omega$ con soporte finito, donde $\Omega=\mathbb{N}$ ?

¿Qué pasa con $\Omega$ un conjunto con cardinalidad mayor que la de los números naturales? Es decir, ¿la cardinalidad de $S_{\Omega}$ igual o mayor que el de $\Omega$ ?

Si se toma el conjunto de biyecciones sin soporte finito entonces se obtiene que este grupo tiene cardinalidad estrictamente mayor que la de $\Omega$ . Sin embargo, no estoy seguro de qué hacer para el conjunto de biyecciones con soporte finito (aunque he publicado una idea en la discusión en la pregunta enlazada para $\Omega=\mathbb{N}$ ).

Answer 1

NOTA: He malinterpretado completamente el post original, de forma bastante atroz además. Dejo esto arriba sólo en el pequeño caso de que pueda ser útil. @Moderadores, siéntanse libres de eliminar este post si es inapropiado.

Recuerdo que el año pasado intenté sentarme y demostrar esto por mí mismo (se afirma a menudo, pero no se demuestra a menudo; por ejemplo, surge mucho cuando se habla de las dimensiones de los espacios vectoriales de dimensión infinita). Así que, por si sirve de algo, aquí está mi forma intuitiva (para MÍ) de hacer las cosas. Parece bastante cercano a lo que Arturo lo hizo, al menos en la idea, no tanto en la prueba real. La idea es básicamente demostrar que el conjunto $\mathscr{P}_0(X)$ (si $X$ es nuestro conjunto infinito) de todos los subconjuntos finitos es sólo una unión contable de $X^n$ (o cosas equipotentes a ella) y luego observar que cada $X^n$ es equipotente a $X$ y por tanto la unión contable debe ser equipotente a $X$ . Así que, aquí vamos

(Nota: No soy en absoluto ningún tipo de lógico/teórico de conjuntos, así que tómate esto con un grano de sal de las fundaciones. Tampoco es una amenaza vana, se lo comenté a un profesor mío y le pareció bien, pero aún no estoy seguro).

Lo que reclamamos es que es $\mathscr{S}_n=\left\{A\subseteq X:\#(A)=n\right\}$ que $\#(\mathscr{S}_n)=\#(X)$ para todos $n\in\mathbb{N}$ . Lo hacemos mediante Schroeder-Bernstein. La primera forma es obvia ya que si dejamos que $C_n=\left\{(a_1,\cdots,a_n)\in X^n:a_i\ne a_j\; i\ne j\right\}$ entonces $f:C_n\to\mathscr{S}_n:(a_1,\cdots,a_n)\mapsto \{a_1,\cdots,a_n\}$ es una suryección y por lo tanto $\#(\mathscr{S}_n)\leqslant \#(C_n)\leqslant \#(X^n)=\#(X)$ (donde utilizamos los hechos obvios de que $C_n\subseteq X^n$ y $\#(X^n)=\#(X)$ desde $X$ es infinito).

Para demostrar la desigualdad inversa ordenamos bien $X$ con un poco de ordenamiento $\preceq$ . Entonces observamos que trivialmente existe algún subconjunto finito $V$ de $X$ tal que cada elemento $X-V$ tiene al menos $n-1$ sucesores con $\preceq$ (este paso es innecesario técnicamente porque podríamos simplemente reemplazar $X$ con un ordinal diferente, pero, creo que desde el punto de vista de los requisitos previos, esto es más sencillo). A continuación, definimos $f:X\to\mathscr{S}_n$ por $f:x\mapsto\{x,x+1,\cdots,x+(n-1)\}$ . No es difícil ver que $f$ es una inyección y por lo tanto $\#(X)\leqslant \#(\mathscr{S}_n)$ .

Así, de Schroeder-Bernstein podemos concluir que $\#(X)=\#(\mathscr{S}_n)$ y el resto de la prueba es muy similar a Arturo 's. A saber: $\displaystyle \#(\mathscr{P}_0)=\#\left(\bigsqcup_{n\in\mathbb{N}}\mathscr{S}_n\right)=\sum_{n\in\mathbb{N}}\#(\mathscr{S}_n)=\aleph_0\#(X)=\#(X)$ donde utilizamos el hecho de que $\aleph_0\#(X)=\max\{\#(X),\aleph_0\}$ y $\aleph_0\leqslant\lambda$ para todos los cardenales infinitos $\lambda$ .

Espero que esto te ayude, y recuerda mi descargo de responsabilidad.

Answer 2

Hay un número contable de subconjuntos finitos de $\mathbb{N}$ . Además, si consideramos subconjuntos finitos ordenados seguimos obteniendo un número contable de ellos. Construimos todas las biyecciones con soporte finito eligiendo un subconjunto finito ordenado $A \subset \mathbb{N}$ y un subconjunto finito ordenado $B \subset \mathbb{N}$ y dejar que $\phi$ mapa $a_k$ a $b_k$ y ser la identidad en otro lugar. Por lo tanto, hay un número contable de tales biyecciones.

Answer 3

Asumiré el axioma de la elección en todo momento.

Dejemos que $X$ sea cualquier conjunto infinito, con $|X|=\kappa$ y para cualquier $n\in\mathbb{N}$ , dejemos que $X^n$ sea el conjunto de los $n$ -tuplas.

Hay una proyección de $X^n$ a la colección de todos los subconjuntos de $X$ con un máximo de $n$ elementos, es decir, el mapa que toma el $n$ -tupla $(x_1,\ldots,x_n)$ al subconjunto $\{x_1,\ldots,x_n\}$ . Esto significa que $$\mathcal{P}_n(X) = \{A\subseteq X\mid |A|=n\}$$ tiene como máximo la cardinalidad de $X^n$ .

Pero para infinitos cardenales $\kappa$ , $\kappa\times\kappa = \kappa$ si asumimos el Axioma de Elección (de hecho, esto es equivalente a la CA ), de lo que se deduce por inducción que $\kappa^n = \kappa$ para todos $n\in\mathbb{N}$ . Así que $|\mathcal{P}_n(X)| \leq |X^n| = \kappa$ . Además, $\kappa\leq |\mathcal{P}_n(X)|$ (biproyecto $X$ con $X-\{x_1,\ldots,x_{n-1}\}$ para algún subconjunto de exactamente $n-1$ elementos para conseguir que haya al menos $|X|$ subconjuntos con $n$ elementos). Así que $|\mathcal{P}_n(X)| = |X|=\kappa$ .

Así, si dejamos que $$\mathcal{P}_{\lt\infty}(X) = \{A\subseteq X \mid |A|\lt\aleph_0\},$$ entonces $$\begin{align*} \left|\mathcal{P}_{\lt\infty}(X)\right| &= \left|\bigcup_{n\in\mathbb{N}}\mathcal{P}_n(X)\right|\\ &= \sum_{n\in\mathbb{N}}\left|\mathcal{P}_n(X)\right|\\ &\leq \sum_{n\in \mathbb{N}}\kappa\\ &= |\mathbb{N}|\kappa = \aleph_0\kappa = \kappa, \end{align*}$$ con la última igualdad porque si asumimos el Axioma de Elección, y $\kappa$ y $\lambda$ son dos cardinales cualesquiera, al menos uno infinito y ninguno igual a $0$ entonces $\kappa+\lambda = \kappa\lambda = \max\{\kappa,\lambda\}$ .

Ahora, para cada $A\in \mathcal{P}_{\lt\infty}(X)$ el subgrupo de $S_X$ con el apoyo de $A$ tiene $n!$ elementos, donde $|A|=n$ . Por lo tanto, $$\begin{align*} |S_X| &\leq \sum_{A\in\mathcal{P}_{\lt\infty}(X)} |S_A|\\ &\leq \sum_{A\in\mathcal{P}_{\lt\infty}(X)} \aleph_0\\ &= |P_{\lt\infty}(X)|\aleph_0 = \kappa\aleph_0 = \kappa. \end{align*}$$ Por otro lado, si fijamos $x\in X$ y considerar todas las transposiciones de la forma $(x,y)$ con $y\in X-\{x\}$ entonces tenemos que $|S_X$ tiene al menos $|X|=\kappa$ elementos. Por lo tanto, $|S_X| = \kappa$ .

Es decir: si $X$ es infinito, entonces el grupo de permutaciones de $X$ con soporte finito tiene cardinalidad $|X|$ .

Answer 4

El caso de $\mathbb N$ no requiere ningún axioma de elección, y podemos demostrar que es contable. He aquí cómo:

Tenga en cuenta que $\pi\colon\mathbb N\to\mathbb N$ es una permutación con soporte finito si y sólo si existe alguna $k$ tal que $\pi(n)=n$ para todos $n>k$ . Por lo tanto, para cada uno de estos $\pi$ hay algo de $k(\pi)$ tal que $\pi$ es en realidad una permutación de $\{0,\ldots,k-1\}$ .

Ahora bien, como cada para cada $k$ sólo hay un número finito de permutaciones de $\{0,\ldots,k-1\}$ queremos concluir que se trata de una unión contable de conjuntos finitos y, por tanto, contable. Asumiendo el axioma de elección (o incluso el axioma de elección para conjuntos finitos) concluiríamos esta parte de la prueba.

Sin embargo, sin el axioma de la elección, todavía tenemos trabajo por delante.

Definamos la siguiente secuencia de conjuntos

$$A_k = \{\pi\mid k(\pi)=k\}$$ Son todas las permutaciones que $k$ es el máximo $k$ movido.

Tenga en cuenta que para $m<k$ tenemos $A_m\subsetneq A_k$ . Ahora definiremos inductivamente una enumeración de $A=\bigcup_{k\in\mathbb N} A_k$ .

1. Para $k=2$ tenemos el primer no vacío $A_k$ y sólo tiene un elemento, así que hemos terminado.

2. Supongamos que $A_k$ fue ordenado por $<_k$ definimos el orden $<_{k+1}$ sur $A_{k+1}$ como sigue, para cualquier $\tau,\pi\in A_k$ :

$$\pi<_{k+1}\tau\iff \begin{cases} &\pi,\tau\in A_k&\land&\pi<_k\tau &\text{ or}\\ &\pi\in A_k&\land&\tau\notin A_k &\text{ or}\\ &\pi,\tau\notin A_k&\land&\pi(n)<\tau(n)\text{ where } n=\min\{t<k\mid \pi(t)\neq\tau(t)\} \end{cases}$$

Verifiquemos que se trata efectivamente de un orden lineal, para cualquier $\pi,\tau\in A_{k+1}$ o bien ambos en $A_k$ o en una de ellas no lo es, en cuyo caso está claro que las dos permutaciones son comparables, y si ambas en $A_{k+1}$ entonces hay algo de $n$ para lo cual $\pi(n)\neq\tau(n)$ o bien $\pi=\tau$ .

También está claro por qué $<_{k+1}$ cuando se restringe a $A_k$ es exactamente $<_k$ . Por último, dado que todo orden lineal finito es un buen orden, esto nos da una cadena creciente de órdenes lineales sobre subconjuntos crecientes de $A$ .

Dejemos que $\prec=\bigcup_k <_k$ entonces $\prec$ es una ordenación de pozos de $A$ y es contable, ya que es el límite de las ordenaciones finitas. Por lo tanto, $A$ tiene una enumeración contable por $\prec$ . $\square$

---

Una nota sobre el caso general sin el axioma de elección:

Mientras se asume el axioma de elección podemos sustituir $\mathbb N$ en la prueba anterior por cualquier otro conjunto, y la prueba sólo cambiará un poco. De hecho, podríamos generalizarla sin mucho problema para incluir un soporte aún mayor para conjuntos más grandes.

Sin embargo, a falta de elección las cosas no son tan bonitas. Sin el axioma de la elección tenemos un puede tienen un conjunto infinito $S$ tal que $f\colon S\to S$ es biyectiva entonces tiene un soporte finito. Sin embargo, el conjunto de todas las permutaciones de $S$ tendrá una cardinalidad estrictamente mayor que la de $S$ .

Suponiendo, sin embargo, que $S$ puede estar bien ordenada, entonces las cosas vuelven a estar bien, y la prueba anterior funciona (cambiando los detalles necesarios para que encaje $|S|$ ).