7 votos

Una elección sin alternativas no es una elección en toda regla.

¿Alguien puede explicar cómo elegimos un calcetín de cada uno de un número finito de pares sin el axioma de elección? Me refiero a la siguiente cita:
Para elegir un calcetín de cada uno de un número infinito de pares de calcetines requiere el Axioma de Elección, pero para los zapatos el Axioma no es necesario. La idea es que los dos calcetines en un par son idénticos en apariencia, y por lo tanto debemos hacer una elección arbitraria si queremos optar por uno de ellos. Para los zapatos, podemos utilizar un algoritmo explícito-por ejemplo, "siempre elegir el zapato izquierdo." ¿Por qué Russell declaración de mencionar una infinidad de pares? Bueno, si sólo tenemos un número finito de pares de calcetines, luego AC no es necesario, podemos elegir uno de los miembros de cada par mediante la definición de "vacío", y podemos repetir la operación un número finito de veces, utilizando las reglas de la lógica formal (no se discute aquí).

33voto

Chris Benard Puntos 1430

El principal reto aquí es explicar el conjunto preciso de la teoría de la instrucción que se entiende por "podemos hacer un número finito de opciones sin el axioma de elección"; la prueba es relativamente fácil. Voy a escribir en una especie de semi-formal, que espero ser lo suficientemente claro que se puede ver cómo se traducen en las declaraciones de ZF.

Por ELECCIÓN, me refiero a la declaración:

Deje $X$ $Y$ se establece, con un mapa de $\pi: X \to Y$. Supongamos que, para cada $y \in Y$, hay un $x \in X$$\pi(x) = y$. Entonces existe un subconjunto $K$ $X$ tal que, para cada $y \in Y$, no hay una única $x \in K$ $\pi(x) = y$

Por lo $X$ es el conjunto vamos a elegir de (el conjunto de todos los calcetines en el universo), $Y$ es el número de opciones que estamos haciendo, y $K$ es el conjunto de decisiones que tomamos.

Ahora, quiero mostrar que esta afirmación es verdadera si $Y$ es finito. Así que debemos discutir la definición de lo finito.

Para cualquier conjunto a $Z$, definir $s(Z) = Z \cup \{ Z \}$. Un conjunto $I$ es llamado inductivo si $\emptyset \in I$ y si, para todos los $Z \in I$, también tenemos $s(Z) \in I$. Se puede demostrar (véase cualquier introducción de la teoría de conjuntos libro) que no hay un único conjunto de $\mathbb{N}$ tales que (1) $\mathbb{N}$ es inductivo y (2) cada inductivo set contiene $\mathbb{N}$. Un conjunto $Y$ se llama finita si se puede poner en bijection con algún miembro de $\mathbb{N}$.


Ahora hemos terminado las definiciones, y se puede mover a la prueba. Vamos a mostrar que, si $A \in \mathbb{N}$, si hay un bijection $Y \to A$, y si tenemos cualquier mapa de $\pi: X \to Y$ la satisfacción de la hipótesis de la ELECCIÓN, entonces la conclusión de OPCIÓN tiene.

Primero de todo, componer $\pi: X \to Y$ con el bijection $Y \to A$, podemos suponer que la $Y$ es un elemento de $\mathbb{N}$. (Ejercicio!)

Digamos que "podemos hacer $Y$ opciones" si la ELECCIÓN es cierto para $Y$, para todos los $\pi$$X$. Deje $T \subseteq \mathbb{N}$ el conjunto de los elementos de la $Y$ $\mathbb{N}$ para que podamos hacer de la $Y$ opciones. (Ejercicio: escribir la definición de $T$ teoría de la notación.) Vamos a mostrar que el $T$ es inductivo.

Primero de todos, podemos hacer de $\emptyset$ opciones. Tome $K = \emptyset$.

Ahora, supongamos que podemos hacer $Z$ opciones. Debemos demostrar que podemos hacer $s(Z)$ opciones. Considere la posibilidad de cualquier mapa de $\pi: X \to s(Z)$. Deje $X' = \pi^{-1}(Z)$, mediante la inclusión de $Z \subseteq s(Z)$. Así que, por hipótesis, existe un subconjunto $K' \subseteq X'$ tal que, para cada $y \in Z$, existe un único elemento $x \in K'$$\pi(x) = y$. También, por la hipótesis de CA, hay un elemento $x \in X$ tal que $\pi(x) = \{ Z \}$. Tome $K = K' \cup \{ x \}$.

Ahora hemos demostrado que el $T$ es inductiva, por lo $\mathbb{N} \subseteq T$. Pero también se $T \subseteq \mathbb{N}$, por la construcción. Por lo $T = \mathbb{N}$. Hemos demostrado que podemos hacer $Y$ opciones para cada $Y \in \mathbb{N}$, como se desee.


Por el camino, usted puede notar que esta prueba se parece mucho a una prueba por inducción. Esta es la forma de escribir una prueba por inducción en ZF. Conjunto de los teóricos de la escritura para los más experimentados de la audiencia acaba de decir "¿por inducción", sin toda la explicación que me has dado.

2voto

DanV Puntos 281

(Siendo algo acosados por la notación de los problemas, de eso estoy completamente de la reescritura de la respuesta)

Supongamos $A=\{y_n\mid n\in\omega\}$ donde $y_n=\{a,b\}$ algunos $a,b$. Por supuesto, $y_n\cap y_m=\varnothing$ para evitar la trivialidad.

Podemos definir, por inducción, una función de finito $n$ a $\bigcup A$ que escoge de la $n$-ésimo par.

Para $n=0$ es simple, $\exists a_0(a_0\in y_0\rightarrow f_0=\{\langle 0,a_0\rangle\})$.

Supongamos que hemos definido $f_n=\{\langle 0,a_0\rangle,\ldots,\langle n,a_n\rangle\}$ donde $a_n\in y_n$. Ahora simplemente reiterar la anterior: $\exists a_{n+1}(a_{n+1}\in y_{n+1}\rightarrow f_{n+1} = f_n\cup\{\langle n+1,a_{n+1}\rangle\})$.

(Esto, por supuesto, puede ser escrito exclusivamente con $\in$$=$. Estoy saltando de la extrema formalidad en aras de la claridad.)

Uno puede preguntar, si se define para todas las $n$, ¿cómo es que no podemos definir a $f=\bigcup f_n$ tal que $f\colon\omega\to\bigcup A$ que elegir entre una infinidad de pares?

Es una buena pregunta. La respuesta radica en el hecho de que nosotros no especifican las funciones reales, sino sólo supone que el anterior que existía. En el $n+1$-ésima etapa, el $f_n$ a partir de la inducción de la hipótesis podría ser diferente de la dada en la $k$-ésima etapa en algún otro momento.

La afirmación de que si definimos $f_n$ todos los $n$ entonces existe una cadena de longitud infinita que se llama el Principio de La Dependiente de la Elección, que es un fragmento de el axioma de elección se utiliza a menudo en el análisis. A la hora de crear un modelo en el que existe una $A$ como antes sin una función de elección, creamos un modelo en el que este principio de elección no se sostiene (y, de hecho, incluso menos posibilidades de elección no se sostiene).

La prueba por inducción, sin embargo, aún se mantiene sin la necesidad de que el axioma de elección. Todavía podemos escribir finito elección de las funciones. Cómo? Bien, simplemente "desplegar" la prueba por inducción:

Supongamos que quiero elegir 4 elementos. Así, la prueba dice que si hay una opción de tres elementos con los que puede elegir un cuarto; si existe una opción de dos elementos, a continuación, puede elegir un tercero; y si existe una opción de un elemento, a continuación, puede elegir un segundo.

Uno de los elementos que siempre puedo elegir, simplemente porque sabemos que el conjunto es no vacío. Deje $a_0$ ser arbitraria en el elemento de $y_0$, ahora la hago rodar hacia arriba, como la oración de arriba me lo permite y puedo elegir a $a_0,\ldots,a_3$ $y_0,\ldots,y_3$ resp.

Este método no puede ser utilizado para elegir infinitamente en un momento, porque hemos elegido arbitraria de elementos. Nada nos garantiza que vamos a elegir estos elementos de nuevo la próxima vez. Podríamos insistir en $a_0$ a ser elegido en cada momento, y que $a_1$ nunca es elegido.

Estas limitaciones, si se quiere, necesita ser escrito en una fórmula cuya longitud es finito , por tanto, no puede permitir que una infinidad de opciones sin alguna función que hace que en adelantado.

Una pieza importante de información es que permite una selección de countably muchos pares de calcetines, todavía no es suficiente para lo que implica el axioma de elección. No, incluso si permitimos que cualquier conjunto infinito de pares.

De hecho, lo anterior no implica que podemos elegir un dedo de una infinidad de manos.

Esto va más allá. Mucho más que eso, y hay maraña de las implicaciones de la restringida versiones de el axioma de elección, las partes de que todavía yacen en la oscuridad, a la espera de ser descubierto.


Un boceto de la prueba para tales modelo de uso de la ZFA (ZF+Átomos).

Supongamos $V$ es un modelo de ZFA+CA en la que hay countably muchos átomos. Considere la posibilidad de una partición de los átomos en countably muchos pares distintos pares. Es decir $A=\bigcup\{\{a_n,b_n\}\mid n\in\omega\}$.

Ahora tome las permutaciones de los átomos tales que $\pi(\{a_n,b_n\})=\{a_n,b_n\}$, que es el respeto a la partición en pares.

Tome un soporte ideal finito de conjuntos, que es para algunos $k\in\omega$ tenemos que si $n<k$ $\pi a_n=a_n$ (lo que también obliga a $\pi b_n=b_n$).

Considere la posibilidad de $\mathcal U$ la permutación modelo creado por estos permutación y el ideal de apoyos descritos anteriormente.

Los conjuntos de átomos en $\mathcal U$, así como la partición en parejas (que es fija, por cualquier permutación en nuestro grupo). Cualquier función que elige a partir de un número infinito de pares puede tener un número finito de apoyo, no existe en $\mathcal U$.

0voto

Frangello Puntos 21

Aunque estoy seguro de que un experto en esto (que no soy) va a publicar una explicación detallada, he aquí una de julio de 2006, de la lesión.la lógica de hilo en lo que usted está preguntando acerca de:

http://groups.google.com/group/sci.logic/browse_thread/thread/e1e4adefec0be32a

Por cierto, he leído que el Axioma de Elección para finito de las colecciones es esencialmente debido a la distributividad de "y" sobre "o" en la lógica.

Abajo está la nota 3 de la página. 49 (Capítulo II.4.2) de los Fundamentos de la Teoría de conjuntos por Abraham A. Fraenkel y Yehoshua Bar-Hillel, North-Holland Publishing Company, 1958:

3) Cf. Littlewood, I, p. 14. Como ha sido señalado por Bernays (por ejemplo, en el 30, pp 359f; cf. Hilbert-Bernays 34, pág. 41), la afirmación de la multiplicativo axioma para finito de conjuntos de $t$ no es sino una aplicación de uno de los distributivas leyes de la conexión lógica de la conjunción y la disyunción. Por lo tanto, en el caso general, uno puede concebir el axioma como una generalización de este elemental lógica de la ley para conjuntos infinitos; en otras palabras, como un suplemento a las reglas lógicas que rigen general y existencial declaraciones. Cf. Collins 54. (Cf. el intuitionistic actitud hacia el principio del medio excluido; véase el Capítulo IV, [Sección] 3.)

Hay una traducción al inglés de la correspondiente Bernays papel libremente disponibles en el internet, y usted puede encontrar Bernays observación sobre AC y la distributividad de las páginas 47 y 48 de esta traducción:

http://www.phil.cmu.edu/projects/bernays/Pdf/bernays09_2002-07-26.pdf

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X