Contables axioma de elección: ¿por qué no se puede probar sólo con ZF

Question

Esta es una pregunta de seguimiento a la discusión acerca de lo finito axioma de elección aquí.

Supongamos que tenemos una contables colección no vacía de conjuntos de $\{A_1, A_2, A_3,\cdots\}$ Razonamiento, como se indica en esa discusión, podemos probar la existencia de una función de elección $c_n$ tal que $c_n(i)$ pertenece a $A_i$ $i = 1,\cdots,n$

De nuevo razonamiento sugerido y el uso de la inducción, se puede demostrar la existencia de una función de $C$ definido a lo largo del $\{1, 2, \cdots\}$ tal que $C(n)$ es una función de elección definida por $i=1,\cdots,n$ $C(n)(i)$ un elemento de A_i. Podemos exigir, además, que el $C(n)(i)$ $C(n-1)(i)$ son iguales para $i=1,\cdots,n-1$.

Ahora podría parecer que podemos probar que los contables axioma de elección mediante la toma de la unión de $C(1)$, $C(2)$, $\cdots$

La pregunta es la siguiente: ¿por qué es que a prueba de mal? Sospecho que la respuesta puede tener algo que ver con el axioma de la unión.

Answer 1

Usted no puede, en general, asegurarse de que $C(n)(i)$ $C(n+1)(i)$ son idénticas para $i \leq n$. Si pudiera hacer eso, usted podría, de hecho, tome $\cup_n C(n)$ para obtener una función de elección. Pero el problema no es con el axioma de la unión, el problema es que se han exagerado lo de inducción en realidad le da.

Es cierto que, cuando se ha demostrado el paso inductivo, temporalmente obtener $C(n)(i)= C(n+1)(i)$, debido a que se amplía el anterior finito función de elección. Pero cuando se aplica el principio de inducción, todo lo que dice es que $$ (\forall n)(\exists C)[C \text{ es una función de elección en } \{A_1, \ldots, A_n\}] $$ Usted no consigue que hay una secuencia infinita $C(n)$ compatible finito elección de las funciones.

---

Este es un lugar donde la diferencia entre "construimos una secuencia infinita de manera inductiva" y "construimos una secuencia de inducción" que realmente importa. Para la construcción de una secuencia infinita de manera inductiva significa dar una construcción de una secuencia infinita $\langle \alpha_0, \alpha_1, \ldots\rangle$ que dice cómo construir $\alpha_0$ y, a continuación, se indica cómo construir $\alpha_{i+1}$$\alpha_i$.

El principio de inducción matemática, por otro lado, tiene la forma general $$ [P(0) \de la tierra (\forall n)[P(n)\P(n+1)]] \(\forall n)P(n). $$ No, en su propio, una forma de tomar una colección de secuencias finitas y combinarlos en una secuencia infinita. Inductivo de construcción, escrito en todos los casos, puede requerir algunas pruebas por inducción para verificar que las condiciones necesarias en la construcción se mantiene en cada paso. Pero el poder de construcciones inductivas realmente va más allá del poder de la inducción matemática.

Hay dos situaciones generales en las que nos podemos encontrar con la perspectiva de la construcción de una secuencia $\langle \alpha_0, \alpha_1, \ldots\rangle$.

Situación 1: se puede seleccionar $\alpha_{i+1}$ únicamente. Por ejemplo, puede ser una función de $f$, de modo que $\alpha_{i+1}$ simplemente puede ser tomado a la igualdad de $f(\langle \alpha_0, \ldots, \alpha_i\rangle)$. En este caso, el axioma de elección no es necesaria para la perspectiva de la construcción.

Un ejemplo es la prueba de la debilidad de Konig del lema: cualquier infinitas $\{0,1\}$ árbol tiene la ruta de acceso. Construimos el camino inductivo; dado un número finito de camino de $\langle \alpha_0, \ldots, \alpha_i\rangle$, si hay infinitamente muchos de los nodos en el árbol por encima de $\alpha_i \smallfrown 0$, a continuación, hacemos de $\alpha_{i+1} = \alpha_i \smallfrown 0$. De lo contrario, tomamos $\alpha_{i+1} = \alpha_i \smallfrown 1$. Este inductivo de construcción no requiere el axioma de elección; puede ser visto simplemente como la iteración de una función determinada para producir la ruta de acceso. La función se define de modo que $f(\sigma) = \sigma\smallfrown 0$ si hay infinitamente muchos de los nodos del árbol por encima de $\sigma\smallfrown 0$, e $f(\sigma) = \sigma\smallfrown 1$ lo contrario. El axioma de elección no es en absoluto necesario para la construcción de ese $f$.

Situación 2: podemos probar la existencia de al menos un valor posible para cada una de las $\alpha_{i+1}$, ya que la construcción avanza, pero no tenemos una función que puede ser usado para guiar la construcción. Esta es precisamente la situación que el axioma de dependiente de elección es la intención de manejar. Dependiente de la elección es precisamente el principio que usted necesita para demostrar el axioma de contables elección por inductivamente la construcción de la función de elección.

Answer 2

Debido a la inducción sólo demuestra que para cada número finito, no es una función de elección. Con el fin de asegurar que existe una secuencia parcial de las opciones que están de acuerdo el uno con el otro de modo que su unión es una función de elección, usted tendría que ir más allá de los poderes de la inducción matemática, y usted tendría que hacer una infinidad de opciones a la vez. De lo contrario, no hay ninguna garantía de que podría haber construido una secuencia de la función de elección así.

Por lo tanto, la idea sería trabajar si usted tenía una función de elección para empezar (a partir de la cual se tomaron segmentos inicial), pero eso simplemente no es cierto en general.

Más concretamente, el principio que nos permite deducir la existencia de dicha secuencia, con solo saber que arbitrariamente ling secuencias finitas existe, se llama el Principio de La Dependiente de la Elección. La prueba de que sugiero es exactamente cómo podemos demostrar contables elección de dependiente de elección; pero el principio en sí mismo no es demostrable a partir de $\sf ZF$ sí.

Answer 3

En su primer párrafo que utiliza contables de elección cuando se dijo "para cada una de las $i$ podemos demostrar la existencia de una función de elección $c_i$$A_i$". La elección está oculto a la vista, en el hecho de que usted utiliza "$c_i$" para la elección de la función en $A_i$. Se han creado así una función de $i \mapsto c_i$. Si quieres evitar este tipo de cosas, debe decir: "para cada una de las $i$ podemos demostrar que existe una función de elección $c$$A_i$". Ahora está claro que $c$ depende de $i$, pero no hemos asumido una asignación específica de $i \mapsto c_i$, que sería la elección.

En su segundo párrafo, en el proceso iterativo de construcción de una función de elección $C$, se utiliza Dependiente de la elección, que es incluso más fuerte que los contables de la elección. El dependiente de la opción tiene la siguiente forma: construimos una secuencia $a_0, a_1, a_2, \ldots$ donde cada una de las $a_{n+1}$ está construido a partir de $a_n$, y hay cierta libertad en lo que exactamente $a_{n+1}$ es, sólo podemos elegir una de las opciones disponibles para $a_{n+1}$. Para evitar dependiente de la elección, tendría que especificar cómo obtener una única $C(n+1)$$C(n)$.

Answer 4

Las opciones son variables.

Es fácil caer en la trampa de pensar de una variable como un indeterminado constante, en cuyo caso, su argumento sería sólo recoger todas las constantes juntos en un solo objeto, pero la falta de argumentos como este muestra las fallas en esa manera de pensar.

Si excavamos un paso más en la capa de abstracción, lo que su argumento está diciendo es que hay una secuencia de conjuntos no vacíos $\mathscr{C}_n$ que contiene la totalidad de la posible elección de las funciones de $n$ elementos-su expresión $C(n)$ es un indeterminado de variables que van más de la $\mathscr{C}_n$. Su argumento es, básicamente, la elección de una "extensión" mapa de $e_{n-1} : \mathscr{C}_{n-1} \to \mathscr{C}_n$. Pero que de nuevo es una opción; $e_{n-1}$ es un indeterminado de variables que van más de un subconjunto de a $\mathscr{C}_n^{\mathscr{C}_{n-1}}$. Aunque sus opciones son, por supuesto, relacionadas por $C(n) = e_{n-1}(C(n-1))$.

Y finalmente, se quiere afirmar que estas opciones pueden ser: que no existe elementos de la infinita producto

$$ \mathscr{C}_0 \times \mathscr{C}_1^{\mathscr{C}_0} \times \mathscr{C}_1 \times \mathscr{C}_2^{\mathscr{C}_1} \times \cdots $$

que son "elegido constantemente" secuencias. El problema es que sin el axioma de elección, las cosas podrían fallar tan mal que este infinito producto puede ser el conjunto vacío!

Usted necesita alguna forma de que el axioma de elección para asegurarse de que usted realmente puede agregar infinidad de opciones como que, y, a continuación, tomar una (única) opción de que el conjunto de todas las posibles agregaciones.

Answer 5

Como Andrej Bauer señaló, para obtener la función de $C$ con el requisito de coherencia que usted afirma que, en realidad se está utilizando dependiente de la elección, que es un fuerte axioma de contables elección. La coherencia requisito, sin embargo, no es realmente necesario. Supongamos que usted tenía una función $C$ que asigna a cada una de las $n\in\mathbb N$ una función de elección $C(n)$, con dominio de $\{1,2,\dots,n\}$. Entonces se podría producir una función de elección $F$ con dominio de todos los de $\{1,2,\dots\}$ mediante el establecimiento $F(n)=C(n)(n)$.

Aunque usted no necesita la coherencia, sí es necesario que el contable axioma de elección para producir su $C$. Usted sabe, por inducción en $n$, que existen elección de las funciones de $c$ $\{1,2,\dots,n\}$ por cada $n$. $C$ se supone que elegir uno de esos $c$ por cada $n$, y la posibilidad de hacer eso es exactamente lo que los contables axioma de elección le da. (Como Andrej señaló también, el uso de una notación como $c_n$ tal $c$ sugiere erróneamente que un determinado $c$ ya ha sido elegido para cada una de las $n$.)

Para decirlo de otra manera, se ha "reducido" el problema de la obtención de una función de elección para la secuencia de conjuntos de $A_n$ a el problema análogo para la secuencia de conjuntos de $B_n$ donde $B_n$ se compone de todos los parciales de la elección de las funciones de $c$ $\{1,2,\dots,n\}$ tal que $c(i)\in A_i$ por cada $i\leq n$.