¿Existe una prueba constructiva del teorema de Cantor-Bernstein-Schroeder?

Question

Una característica importante del teorema de Cantor-Schroeder-Bernstein es que no se basa en el axioma de elección. Sin embargo, sus diversas pruebas no son constructivas, ya que dependen de la ley del medio excluido.

Hay varias estrategias de prueba bien conocidas. Por ejemplo, hay una prueba sencilla que utiliza el teorema del punto fijo de Tarski.

Mi pregunta se refiere a la conocida prueba atribuida a Julius Konig, y dada aquí: Prueba de Konig . Lo que no he podido entender es cómo esto no es una prueba constructiva. Dadas las funciones $f$ y $g$ ¿no es posible llegar a la biyección formando secuencias biinfinitas como se indica en la prueba?

Answer 1

No hay ninguna prueba constructiva.

Para demostrarlo, dejemos que $A = \mathbb{N}$ y que $B = \{ n \in \mathbb{N}\; |\; \varphi_n(0) \uparrow \}$ , donde $\varphi_n(0) \uparrow$ significa que el $n$ La máquina de Turing es indefinida en la entrada 0. Hay inyecciones computables $f:A \rightarrow B$ y $g:B \rightarrow A$ (la identidad), pero no hay una suryección computable desde $A$ a $B$ porque $B$ no es un conjunto c.e.

Para ver por qué la prueba de Konig no es constructiva, digamos que queremos saber cuál es la imagen de $n \in A$ está bajo la biyección. Para ello necesitamos saber si aplicamos $f$ o $g^{-1}$ . Pero para saber esto tenemos que decidir si $n$ es un $A$ -stopper, a $B$ -stopper, o ninguno. Sin embargo, no podemos hacer esto de forma constructiva porque requeriría comprobar toda la secuencia, posiblemente infinita, para ver si se detiene alguna vez. De hecho, en el ejemplo anterior, poder decidir si $g^{-1}$ es lo mismo que decidir el problema de detención, por lo que en las etapas de impar ni siquiera sabemos si la secuencia se extiende o no hacia atrás en absoluto.

Answer 2

El teorema de Cantor-Bernstein-Schröder (¿he leído en alguna parte que Dedekind fue el primero en demostrarlo?) no es válido constructivamente. He aquí un par de razones que lo explican.

Hay modelos en los que el teorema falla

Aquí hay una bonita. En el topos de realizabilidad sobre las máquinas de Turing de tiempo infinito hay una inyección $\mathbb{R} \to \mathbb{N}$ . Debido a que el topos satisface la elección contable no hay suryección $\mathbb{N} \to \mathbb{R}$ (por lo tanto no hay biyección), pero claramente hay una inyección $\mathbb{N} \to \mathbb{R}$ .

Todd mencionó un modelo de hoja previa en su respuesta.

Las pruebas habituales no son constructivas

Has preguntado qué es lo no constructivo de la prueba de König. Utiliza el medio excluido varias veces:

1. "la secuencia puede extenderse a la izquierda, dependiendo de si $a$ es a imagen y semejanza de $g$ o no",
2. "la secuencia construida en las pruebas termina o no",
3. "las secuencias así construidas particionan la unión disjunta de los dos conjuntos".

Para una demostración que utiliza el medio excluido de forma más controlada, véase la que utiliza el teorema del punto fijo de Tarski, como aquí se describe . El medio excluido se utiliza "sólo" en el último paso, cuando la biyección $i$ se define, dependiendo de si un elemento está en $C$ o no.

El teorema implica cosas extrañas, constructivamente hablando

He aquí una extraña consecuencia del teorema, intentaré mejorarla pero no tengo tiempo ahora mismo. Consideremos el espacio de Cantor $C = 2^\mathbb{N}$ y el subespacio de las secuencias que contienen un 1, $D = \lbrace \alpha \in C \mid \exists n . \alpha n = 1\rbrace$ . Como hay inyecciones $C \to D$ y $D \to C$ existe una biyección $h : C \to D$ . Esto es muy extraño, ya que es coherente suponer que todos los mapas en $C$ son uniformemente continuas, pero dicha biyección no puede ser uniformemente continua. Intentaré mejorar esto.

Answer 3

Si se acepta que las topos son modelos de la teoría constructiva de conjuntos, otra forma de responder a la pregunta es dar un topos (no booleano) en el que falle el teorema CBS; eso demostraría que este teorema no puede tener una demostración constructiva.

Un ejemplo sencillo de este tipo de topos es la categoría de flechas $Set^\to$ cuyos objetos son funciones $X_0 \to X_1$ entre conjuntos y cuyos morfismos son cuadrados conmutativos. Sea $X$ sea el objeto $f: \mathbb{N} \to \mathbb{N}$ que lleva $n \in \mathbb{N}$ a $\mathrm{int}(n/2)$ , donde $\mathrm{int}(x)$ es el mayor número entero menor o igual que $x$ ; deja que $Y$ sea el objeto $g: \mathbb{N} \to \mathbb{N}$ que lleva $n$ a $\mathrm{Int}((n+1)/2)$ , donde $\mathrm{Int}(x)$ es el menor número entero mayor o igual a $x$ . Está bastante claro que $X$ y $Y$ no son isomorfas, porque $g^{-1}(0)$ tiene cardinalidad $1$ donde todas las fibras de $f$ tienen cardinalidad $2$ . Pero, con sólo hacer dibujos de estos objetos, es fácil construir monomofismos $i: X \to Y$ y $j: Y \to X$ (por ejemplo, definir $i_0(n) = n+1$ y $i_1(n) = n+1$ para todos $n$ y definir $j_0(n) = n+1$ para $n \gt 0$ , $j_0(0) = 0$ y $j_1(n) = n$ para todos $n$ ).

---

Para las personas que no están acostumbradas a pensar en la teoría de los topos como "teoría constructiva de conjuntos", hay otra forma de considerar el ejemplo anterior en términos de " $H$ -conjuntos valorados", donde $H$ es el álgebra de Heyting con tres elementos, $H = \{0 < 1/2 < 1\}$ . La ley del medio excluido no se cumple; se puede calcular fácilmente $\neg \neg (1/2) = 1$ .

Un $H$ -conjunto de valores es un conjunto $X$ junto con una función $e_X: X \times X \to H$ que mide el grado en que los elementos de $X$ se consideran "iguales", con sujeción a los axiomas de transitividad y simetría:

$$e_X(x, y) \wedge e_X(y, z) \leq e_X(x, z), \qquad e_X(x, y) = e_X(y, x).$$

Podemos pensar en $e_X(x, x)$ como la medición de la medida en que $x$ "existe". Un $H$ -relación valorada es una función $r: X \times Y \to H$ tal que

$$e_X(x', x) \wedge r(x, y) \leq r(x', y), \qquad r(x, y) \wedge e_Y(y, y') \leq r(x, y'), \qquad r(x, y) \leq e_X(x, x) \wedge e_Y(y, y).$$

Un $H$ -función valorada $f: X \to Y$ es un $H$ -relación valorada tal que

$$f(x, y) \wedge f(x, y') \leq e_Y(y, y'), \qquad e_X(x, x) \leq \bigvee_{y \in Y} f(x, y)$$

donde la primera condición es un análogo de la buena definición y la segunda dice aproximadamente que $f(x)$ se define en la medida en que $x$ existe. Resulta que la categoría de $H$ -es equivalente al topos $Set^\to$ .

Bajo esta equivalencia, $X$ en el ejemplo anterior se identifica con el par $(\mathbb{N}, e_X: \mathbb{N} \times \mathbb{N} \to H)$ donde $e_X(n, n) = 1$ , donde $e_X(m, n) = 1/2$ si $m \neq n$ pero $f(m) = f(n)$ y por otra parte $e_X(m, n) = 0$ . Existe una descripción similar de $Y$ en términos de $H$ -conjuntos valorados. Para tales $H$ -conjuntos valorados donde $e_X(x, x') = 1$ para todos precisamente cuando $x = x'$ , funcional $H$ -las relaciones entre ellos pueden describirse como funciones reales $f: X \to Y$ con la condición de que $e_X(x, x') \leq e_Y(f(x), f(x'))$ para todos $x, x'$ en $X$ .

Las relaciones funcionales monomórficas $i: (\mathbb{N}, e_X) \to (\mathbb{N}, e_Y)$ y $j: (\mathbb{N}, e_Y) \to (\mathbb{N}, e_X)$ resultan estar dadas por $i(n) = n+1$ y $j(0) = 0$ , $j(n) = n+1$ para $n > 0$ (es decir, las funciones $i_0$ y $j_0$ en el ejemplo anterior). La monomorficidad equivale a la condición de que $e_Y(i(x), i(x')) = e_X(x, x')$ para todos $x, x'$ en $X$ (y de forma similar para $j$ ). Esto se puede comprobar fácilmente.

Ahora se puede intentar pasar por la prueba de König para ver qué es lo que se kaflooey. Siguiendo la Descripción de Wikipedia cada elemento de la unión disjunta $X \sqcup Y$ pertenece inequívocamente a un " $X$ -stopper" o a un " $Y$ -stopper":

$$1_X \stackrel{i}{\mapsto} 2_Y \stackrel{j}{\mapsto} 3_X \stackrel{i}{\mapsto} \ldots$$

$$0_Y \stackrel{j}{\mapsto} 0_X \stackrel{i}{\mapsto} 1_Y \stackrel{j}{\mapsto} \ldots$$

Pero: cuando se intenta definir un isomorfismo $\phi: X \to Y$ de esto siguiendo la prescripción, inmediatamente sale mal. Mira lo que esta función putativa $\phi$ hace a los elementos "medio iguales" $0_X$ y $1_X$ . Los envía respectivamente a los elementos no iguales $0_Y$ y $2_Y$ . Por lo tanto, no respeta

$$e_X(0_X, 1_X) \leq e_Y(\phi(0_X), \phi(1_X))$$

como exige la ley.

Answer 4

Es bien sabido que las topos de Grothendieck y las topos de realizabilidad (por diferentes razones) son modelos de la teoría de conjuntos intuicionista de Zermelo-Fraenkel. Por lo tanto, tanto Andrej como Todd demostraron en sus respuestas (de manera esencialmente diferente) que Cantor-Bernstein-Schroeder no puede ser demostrado en IZF.

Por supuesto, esto no significa que la propiedad de Cantor-Bernstein-Schroeder sea incompatible con la matemática constructiva; sólo muestra que IZF es demasiado débil para demostrar la CBS. Por lo tanto, una pregunta complementaria podría ser: ¿cuáles son las implicaciones de IZF+CBS; hace IZF+CBS que la lógica colapse al caso booleano?

Si no me equivoco, la respuesta es no, y el contraejemplo se construye a continuación. Sin embargo, comenzaré con una observación negativa.

Dejemos que $\Omega$ sea un álgebra de Heyting con uniones contables. Un elemento $v \in \Omega$ es complementable si existe un elemento $w \in \Omega$ tal que $v \vee w = 1$ y $v \wedge w = 0$ .

Decimos que $\Omega$ es un álgebra booleana si cada uno de sus elementos es una unión finita de elementos complementables (equivalentemente, si cada elemento es complementable).

Decimos que $\Omega$ es un álgebra pro-booleana si cada uno de sus elementos es una unión contable de elementos complementables.

La afirmación es que todo topos elemental con colímite contable que satisface la propiedad de Cantor-Bernstein-Schroeder es pro-boleana (es decir, su clasificador de subobjetos es un álgebra pro-boleana).

Dejemos que $v \colon V \rightarrow 1$ sea un valor de "verdad" (un monomorfismo en objeto terminal). Construiremos dos objetos $X = \coprod_{\mathbb{N}} 1$ y $Y = V \sqcup X$ . Hay monomorfismos evidentes ${\iota_X}\colon{X}\rightarrow{Y}$ dado por la inyección del coproducto, y ${v \sqcup \mathit{id}}\colon{Y}\rightarrow{X}$ . Por tanto, por Cantor-Bernstein-Schroeder existe un isomorfismo ${b}\colon{Y}\rightarrow{X}$ . Como los coproductos en un topos son extensos, podemos dividir cada componente ${\iota_0}\colon V \rightarrow{Y}$ , ${\iota_k}\colon 1 \rightarrow{Y}$ del coproducto $Y$ a lo largo de $b$ a través de las inyecciones de los coproductos ${\iota_l} \colon 1 \rightarrow{X}$ obtención de elementos $\alpha_{k,l}$ tal que $Y \approx \coprod_k \coprod_l \alpha_{k,l} \approx \coprod_l \coprod_k \alpha_{k,l}$ y $b = \coprod_l b_l$ con cada ${b_l}\colon{\coprod_l \alpha_{l,k}}\rightarrow{1}$ siendo un isomorfismo (utilizando de nuevo la extensividad de los coproductos y el hecho de que el pullback de un iso es iso). Como las uniones en un topos son efectivas (y los coproductos son disjuntos) $1 \approx \coprod_l \alpha_{l,k} = \bigcup_l \alpha_{l,k}$ y así cada $\alpha_{l,k}$ se complementa con $\bigcup_{x \neq l} \alpha_{x,k}$ . Dado que cada valor subterminal puede situarse exactamente de una manera en el objeto terminal, $V = \bigcup_l \alpha_{l,0}$ es una unión disjunta contable de elementos complementables.

(No podemos obtener más de esta construcción; por ejemplo en la categoría de gavillas sobre números racionales con la topología habitual, $\coprod_{\mathbb{N}} 1 \approx V \sqcup \coprod_{\mathbb{N}} 1$ para el valor de verdad (no complementable) $V$ correspondiente a la bola abierta $(-1, 1)$ Por desgracia, hay otros objetos de esta categoría que pueden servir de contraejemplo para CBS. Permítanme también señalar que el procedimiento estándar de construir un isomorfismo a partir de dos monomorfismos no funcionaría en este caso. Sin embargo, por el argumento anterior está claro que tal isomorfismo puede construirse para cualquier topos pro-booleano. La solución es no desplazar uniformemente todo el $V$ (o su pseudocomplemento), pero para mover cada una de las (contablemente muchas) partes complementables de $V$ por separado).

---

[Lo siento mucho, ahora veo que hay un error en el siguiente argumento; intentaré arreglarlo (a condición de que sea posible --- no estoy seguro ahora). Debería haber comprobado todos los detalles relevantes antes de publicar esto como respuesta].

Para obtener un resultado positivo, considere el conjunto: $$\mathcal{D} = \lbrace 0, 1, \frac12, \frac13, \frac14, \dotsc\rbrace$$ con topología heredada de $\mathbb{R}$ y construir la categoría $\mathit{Sh}(\mathcal{D})$ de gavillas sobre $\mathcal{D}$ . Cada conjunto abierto en $\mathcal{D}$ puede construirse a partir de monotones $\lbrace\frac1n\rbrace$ y un conjunto de la forma $[0, \frac1k]$ .

Dejemos que $F, G \colon \mathcal{D}^{op} \rightarrow \mathbf{Set}$ sean cualesquiera gavillas y supongamos que existen monomorfismos $m \colon F \rightarrow G$ y $n \colon G \rightarrow F$ . Un monomorfismo entre láminas es una inyección en cada uno de sus componentes, por lo que por el teorema de CBS para conjuntos $F(U) \approx G(U)$ para todo conjunto abierto $U$ . Sea $\phi_U \colon F(U) \approx G(U)$ sea una colección de tales isomorfismos. Construiremos un isomorfismo $\alpha \colon F \rightarrow G$ entre gavillas de forma inductiva:

• $\lambda_{[0, 1]} = \phi_{[0, 1]}$

• para todo lo que no sea vacío $F(\lbrace\frac1k\rbrace)$ elegir un elemento $1_{\frac1k} \in F(\lbrace\frac1k\rbrace)$ ; si $F(\lbrace\frac1k\rbrace)$ está vacío, entonces $\lambda_{[0, \frac1{k+1}]} = \phi_{[0, \frac1{k+1}]}$ Si no es así $\lambda_{[0, \frac1{k+1}]} = G([0, \frac1{k+1}] \subset [0, \frac1{k}]) \circ h_{\frac1k}$ , donde $h_{\frac1k} \colon F([0, \frac1{k+1}]) \rightarrow F([0, \frac1{k}])$ es el único morfismo hacia el producto $F([0, \frac1{k}]) = F([0, \frac1{k+1}]) \times F(\lbrace\frac1k\rbrace)$ inducido por $F([0, \frac1{k+1}]) \overset{!}\rightarrow 1 \overset{1_{\frac1k}}\rightarrow F(\lbrace\frac1k\rbrace)$ y la identidad en $F([0, \frac1{k+1}])$

• de manera similar, para cada no vacío $F([0, \frac1{k+1}])$ elegir un elemento $1_{[0, \frac1{k+1}]} \in F([0, \frac1{k+1}])$ ; si $F([0, \frac1{k+1}])$ está vacío, entonces $\lambda_{\lbrace\frac1{k}\rbrace} = \phi_{\lbrace\frac1{k}\rbrace}$ Si no es así $\lambda_{\lbrace\frac1{k}\rbrace} = G(\lbrace\frac1{k}\rbrace \subset [0, \frac1{k}]) \circ h_{{[0, \frac1{k+1}]}}$

• si $U$ es una unión disjunta de la forma $[0, \frac1k] \sqcup \bigcup_i\lbrace\frac{1}{n_i}\rbrace$ , donde $[0, \frac1k]$ es el mayor intervalo contenido en $U$ entonces $\lambda_{U} = \lambda_{[0, \frac1k]} \times \prod_i \lambda_{\lbrace\frac{1}{n_i}\rbrace}$ donde los productos están determinados por las estructuras de las gavillas.

En el segundo y tercer paso hemos elegido los componentes de $\lambda$ para ser compatible al alza, y en el cuarto paso la condición de naturalidad se desprende de la propiedad universal de los productos. Así, $F \approx G$ .

[EDIT: Permítanme argumentar que $\phi_U$ puede elegirse de forma que cada $\lambda_U$ es realmente un isomorfismo. Supongamos que todos los $F(\lbrace \frac1k\rbrace)$ son no vacíos. Definir $\mathit{colim}F([0, \frac1k])$ para ser el colímite del diagrama: $$F([0, 1]) \rightarrow F([0, \frac12]) \rightarrow \cdots \rightarrow F([0, \frac1k]) \rightarrow \cdots$$ Lo tenemos: $$(\mathit{colim}_kF([0, \frac1k])) \times (\prod_i F(\lbrace\frac1i\rbrace)) \approx F([0, 1]) \times \mathit{colim}\_k \prod\_{i > k} F(\lbrace\frac1i\rbrace) \approx F([0,1])$$ y de forma similar para $G$ . Dado que en una categoría localmente presentable los monomorfismos son estables bajo colímites dirigidos, tanto: $$\mathit{colim}F([0, \frac1k]) \overset{\mathit{colim}\left(m_{[0, \frac1k]}\right)}\rightarrow \mathit{colim}G([0, \frac1k])$$ y: $$\mathit{colim}F([0, \frac1k]) \overset{\mathit{colim}\left(n_{[0, \frac1k]}\right)}\leftarrow \mathit{colim}G([0, \frac1k])$$ son monomorfismos, por lo que por CBS para conjuntos $\mathit{colim}F([0, \frac1k]) \overset{\phi_0}\approx \mathit{colim}G([0, \frac1k])$ . Por lo tanto, $\phi_{[0, 1]}$ se puede suponer que es de la forma $\phi_0 \times \prod \phi_{\lbrace\frac1k\rbrace}$ . Asimismo, cada $\phi_{[0, \frac1k]}$ . ]

(Por cierto, creo que en realidad no estamos tan lejos de la inversa del teorema anterior, pero eso es para otra historia...)

Answer 5

El fracaso de la ley del medio excluido me resulta difícil de imaginar. Pero aquí hay un intento...

La prueba de König tiene esto:

Para cualquier $a$ esta secuencia puede terminar a la izquierda o no

Pero tal vez haya que considerar también el caso de ambos: termina a la izquierda y también no termina a la izquierda... ???