Medio Cantor-Bernstein sin elección

Question

El otro día tuve una discusión con uno de mis profesores, que se redujo a la siguiente pregunta:

Supongamos que ZF. Sea $A,B$ sean conjuntos tales que existen $f\colon A\to B$ que es inyectiva y $g\colon A\to B$ que es suryectiva.

¿Existe $h\colon A\to B$ que es biyectiva?

Por supuesto, basta con demostrar que existe una inyección de $B$ en $A$ y por el teorema de Cantor-Bernstein (que no requiere elección) terminamos la demostración.

Mi intuición dice que esto es cierto, su intuición dice que es falso.

Agradeceremos sus ideas, referencias y posibles soluciones.

---

Como Ricky muestra a continuación, depende de $A$ y $B$ .

Así que a una elección más específica de conjuntos (para los que creo que es cierto) tenemos $A=\mathbb R^\omega$ (es decir, secuencias infinitas de números reales) y $B=[\mathbb R]^\omega$ (es decir, subconjuntos contables de números reales)

Answer 1

La intuición de tu profesor es la correcta.

En primer lugar, recordemos que un conjunto $S$ se dice Dedekind finito si no existe una biyección entre $S$ y cualquier subconjunto adecuado de $S$ . En los primeros días de forzamiento Cohen demostró que si $ZF$ es coherente, entonces es coherente con $ZF$ para que exista un conjunto finito Dedekind infinito $S$ En efecto, la prueba de Cohen demuestra que $S$ puede disponerse como una colección de números reales.

Ahora el resultado clave que responde a su pregunta: Es un teorema de Tarski que si $S$ es infinito pero Dedekind finito, entonces eligiendo:

$B$ := el conjunto de todas las secuencias finitas uno a uno cuyos miembros proceden de $S$ y

$A$ := $B$ \ la secuencia vacía,

entonces $A$ y $B$ proporcionan un contraejemplo para su versión suryectiva sin elección del teorema de Cantor-Bernstein, es decir, no existe una biyección entre $A$ y $B$ [no trivial], pero hay una inyección de $A$ a $B$ [trivial], así como una suryección desde $A$ a $B$ [fácil].

La solución anterior está plagiada del Ejercicio 8 [p.162] de la obra de Jech El axioma de la elección (disponible en edición de bolsillo de Dover). El crédito a Tarski aparece en la p.166.

También puede consultar las pistas del ejercicio 2.42 [p.92] de la obra de Levy Teoría básica de conjuntos otro excelente texto reeditado por Dover.

Answer 2

Si $A = \{0\}\times 2^{\omega}$ y $B = (\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1)$ y no hay inyección de $\omega_1$ a $2^{\omega}$ ,
entonces no existe tal biyección.

Defina $f : (\{0\}\times 2^{\omega}) \to ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1))$ por $f(x) = x$ . Evidentemente, $f$ es inyectiva.
Defina $\operatorname{pair} : \omega^2 \to \omega$ por $\operatorname{pair}(\langle m,n\rangle) = ((m+n)\cdot (m+n+1))+(2\cdot n)$ .
Defina $g_1 : 2^\{\omega\} \to \omega_1$ por

$g_1(x) = \begin{cases} \alpha & \text{if } \{\langle m,n\rangle \in \omega^2 : \operatorname{pair}(\langle m,n\rangle) \in x\} \text{ is a well-order of } \omega \text{ with order type } \alpha \\ 0 & \text{else} \end{cases} \quad .$

Defina $g : (\{0\}\times 2^{\omega}) \to ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1))$ por

$g(\langle 0,x\rangle) = \begin{cases} \langle 0,\{n\in \omega : (n+1) \in x\}\rangle & \text{if } 0 \notin x \\ \langle 1,g_1(\{n\in \omega : (n+1) \in x\})\rangle & \text{if } 0\in x\end{cases} \quad .$

Desde $g_1$ es suryectiva, $g$ también es suryectiva. Sea $h : ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1)) \to (\{0\}\times 2^{\omega})$ sea una función. Defina $h_1 : \omega_1 \to 2^{\omega}$ por $h_1(\alpha) = \operatorname{secondentry}(h(\langle 1,\alpha \rangle))$ .
$h_1$ no es inyectiva, por lo que $h$ tampoco es inyectiva.
Esto funciona para todas las funciones $h : ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1)) \to (\{0\}\times 2^{\omega})$ Así que
no existe una biyección $h : ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1)) \to (\{0\}\times 2^{\omega})$ .

si $A = \{\}$ y $B = \{\}$ entonces existe tal biyección.

Defina $h : A\to B$ por $h(x) = x$ .

Por tanto, no tiene por qué haber una respuesta única, puede depender de $A$ y $B$ .

Si todos los conjuntos de reales tienen la propiedad Baire, entonces no hay inyección de $[\mathbb R]^\omega$ a $\mathbb R^\omega$ .

Sea $h : [\mathbb R]^\omega \to \mathbb R^\omega$ sea una función. Defina $\leq$ como el orden lexicográfico de $\mathbb R^\omega$ .
Por esta respuesta no existe un orden total de ${\mathbb R}/\sim$ . Todos los miembros de ${\mathbb R}/\sim$ son subconjuntos contables de $\mathbb{R}$ .
Defina $\leq_h$ en ${\mathbb R}/\sim$ por $x\: \leq_h\: y$ sólo si $h(x) \leq h(y)$ . Desde $\leq_h$ no es una orden total, $h$ no es inyectiva. Esto funciona para todas las funciones $h : [\mathbb R]^\omega \to \mathbb R^\omega$ por lo que no hay inyección $h : [\mathbb R]^\omega \to \mathbb R^\omega$ .

Por shelah.logic.at/files/446.ps (que no puedo averiguar cómo hacer markdown enlace a),
$\operatorname{ZF} + \operatorname{DC}(\omega_1)$ no prueba que haya una inyección de $[\mathbb R]^\omega$ a $\mathbb R^\omega$ .

Answer 3

En cuanto a su pregunta original, merece la pena mencionar que su hipótesis implica lo siguiente:

Si $|A| = |A \times 2|$ y existe una suryección desde $A$ en $B$ entonces $B$ inyecta en $A$ .

Esto realmente sólo generaliza el ejemplo dado por Ricky, pero para ver esto:

Supongamos que tenemos una biyección $b: A \rightarrow A \times \{0, 1\}$ y una suryección $g: A \rightarrow B$ . $A$ inyecta en $A \cup B$ por el mapa de inclusión, y podemos obtener una suryección de $A$ en $A \cup B$ mediante la asignación de un $a \in A$ a sí misma si la segunda coordenada de $b(a)$ es $0$ o a $g(a)$ si la segunda coordenada de $b(a)$ es $1$ . En otras palabras, dividimos $A$ en dos copias de sí mismo, mapeando la primera copia de forma suryectiva (biyectiva) sobre sí mismo a través de la identidad y la segunda copia de forma suryectiva sobre $B$ vía $g$ . Según su principio, esto significaría que tenemos una biyección $h$ de $A$ en $A \cup B$ mediante $h^{-1} \upharpoonright B$ sería una inyección de $B$ en $A$ .

A partir de esta observación, creo que queda intuitivamente claro cómo su principio es una forma de elección disfrazada. En concreto, su principio implicaría que $\alpha^+$ inyecta en $\mathcal{P}(\alpha)$ para todo ordinal infinito $\alpha$ ya que tenemos una suryección desde $\mathcal{P}(\alpha)$ en $\alpha^+$ (incluso sin elección en virtud del hecho de que todo ordinal de tamaño $|\alpha|$ está codificado por un subconjunto de $\alpha$ ). Pero como seguro que ya sabe, se han construido modelos de ZF en los que esto no es así.