Para cada infinito $S$ , $|S|=|S\times S|$ implica el Axioma de elección

Question

Cómo demostrar la siguiente conclusión:

Para cualquier conjunto infinito $S$ existe una biyección $f:S\to S \times S$ ] implica el axioma de la elección.

¿Puedes dar una prueba sin la teoría de los números ordinales?

Answer 1

Estaré impresionado si puedes hacerlo mejor que Martin Gardner. Escribía artículos pensados para ser consumidos en minutos (aunque no en 2 ó 3), y proporcionaba retos para ayudar a mantener el interés. Hizo artículos fuera de Scientific American, pero no sé si Gardner podría competir con el público que lee cosas como la revista People.

Sin embargo, muchas revistas publican rompecabezas. Si el tema presentado incluye un rompecabezas sencillo de fácil resolución y otro no tan sencillo, eso puede atraer tan buena audiencia como cualquier otra cosa, especialmente si se trata de poco o ningún "razonamiento superior". Aun así, exprimir un tema en dos o tres minutos es un reto. A tres palabras por segundo, son menos de 600 palabras, que caben en un comentario de MathOverflow. Considere, en cambio, una versión de diez minutos.

Gerhard "Ask Me About System Design" Paseman, 2011.02.23

Answer 2

Dejemos que $A$ sea un conjunto infinito arbitrario. Demostraré que $A$ tiene una función de elección, es decir, una función $a:\mathcal{P}(A)\setminus\{\varnothing\}\to A$ tal que $a(X) \in X$ para todo lo que no sea vacío $X \subseteq A$ .

En primer lugar, elija un conjunto $B$ tal que:

• existe una función de elección $b:\mathcal{P}(B)\setminus\{\varnothing\}\to B$ y

• no hay inyección de $B$ en $A$ .

(Por ejemplo, tome $B$ para ser el conjunto de todas las clases de isomorfismo de las ordenaciones de subconjuntos de $A$ .) Supongamos además que $A \cap B = \varnothing$ .

Por hipótesis, hay una inyección $f:(A\cup B)^2\to(A\cup B)$ . Dado $x \in A$ debe haber un $y \in B$ tal que $f(x,y) \in B$ Si no es así $y \in B \mapsto f(x,y)$ sería una inyección de $B$ en $A$ . Así, podemos definir una función $g:A \to B^2$ por $g(x) = (y,f(x,y))$ donde $y = b(\{u \in B : f(x,u) \in B\})$ es decir, para cada $x \in A$ , $g(x)$ elige un par $(y,z) \in B^2$ tal que $f(x,y) = z$ . Tenga en cuenta que $g$ debe ser una inyección: si $g(x) = (y,z) = g(x')$ entonces $f(x,y) = z = f(x',y)$ y por lo tanto $x = x'$ desde $f$ es una inyección.

Ahora observe que $B^2$ tiene una función de elección igual que $B$ . En concreto, dejemos que $c:\mathcal{P}(B^2)\setminus\{\varnothing\}\to B^2$ se define por $c(X) = (y,z)$ donde $$y = b(\{u \in B : (\exists v \in B)((u,v) \in X)\})$$ y $$z = b(\{v \in B : (y,v) \in X \})$$ para todo lo que no sea vacío $X \subseteq B^2$ . De ello se desprende que $A$ también tiene una función de elección. A saber, que $a:\mathcal{P}(A)\setminus\{\varnothing\}\to A$ se define por $$a(X) = g^{-1}(c(\{g(x) : x \in X\}))$$ para todo lo que no sea vacío $X \subseteq A$ .

Observación. La prueba de la existencia del conjunto $B$ esbozado anteriormente se basa en la teoría de los bien ordenados, pero no en la teoría de los ordinales. De hecho, el argumento anterior puede llevarse a cabo en la teoría Z (= ZF menos los axiomas de sustitución y de fundamentación). Es bien sabido que hay modelos de Z con muy pocos ordinales, por ejemplo $V_{\omega+\omega}$ es un modelo de Z.