Finito axioma de elección: ¿cómo se puede demostrar sólo ZF?

Question

El axioma de elección afirma la existencia de una función de elección para cualquier familia de conjuntos de F. sin embargo, Supongamos que F es finito, o incluso que F tiene un conjunto. Entonces, ¿cómo podemos demostrar la existencia de una función de elección?

La respuesta habitual es que se nos acaba de ir de un set a otro, elegir un elemento de cada conjunto. Puesto que F es finito, este proceso va a terminar. Lo que yo estoy preguntando es cómo podemos elegir siempre a partir de un único conjunto. El sector informal de la respuesta parece ser que es posible... pero esto no es un axioma, por lo que debe ser justificado de alguna otra manera.

Así que: ¿cómo se puede demostrar a partir de los axiomas de sólo ZF sin elección, que para los no vacío de x existe una función f:{x}->x?

Answer 1

Aunque las respuestas ya dadas son correctas, permítanme añadir algo de información (básicamente reformular las corchetes parte de Thomas Scanlon la respuesta) que he encontrado útil para los estudiantes que se planteó esta cuestión. Considere el problema, al final de la pregunta original, de "elegir" a partir de un único conjunto de $x$. Como varias personas han señalado, se nos da la existencial declaración, "Hay un elemento en $x$." Lo que debe tenerse en cuenta además, es que lo que queremos demostrar es también una declaración existencial, "No es una función de elección." Tenemos una explícita de la construcción, que voy a llamar a $C$, que se convertir cualquier elemento de $x$ en una función de elección, es decir, el envío de cualquier $y$ a $\{(x,y)\}$ (como en el aeropuerto Charles Staats el comentario sobre la pregunta original). Si no podemos definir explícitamente cualquier particular $y$, entonces no vamos a ser capaces de definir cualquier función de elección, pero el problema no nos obligan a definir explícitamente una función de elección, sólo tenemos que demostrar que existe. Y que sigue, gracias a $C$, a partir de la existencia de elementos en $x$.

Answer 2

Decir que $x \neq \varnothing$ es exactamente para hacer valer $(\exists y) y \in x$ y la verdad de esta última fórmula será presenciado por algunos de $a$ para que $a \in x$. Por lo tanto, el conjunto de $f := \lbrace \langle x, a \rangle \rbrace$ es una función de $\lbrace x \rbrace$ a $x$.

[Creo que este punto, a saber, que el Axioma de Elección no se utiliza para crear instancias de la verdad de una fórmula existencial por el nombramiento de un testigo es el corazón de su pregunta. No estoy afirmando que habrá constructiva de la elección de la testigo. Es justo que si una fórmula existencial es verdad, debe ser un testigo.]

Más en general, para demostrar que si $F$ es un conjunto finito de conjuntos no vacíos, entonces $\prod F := \lbrace f : f \text{ a function with dom}(f) = F \text{ such that } (\forall x \in F) f(x) \in x \rbrace$ es no-vacío argumenta por inducción.

Si $F = \varnothing$, entonces la función vacía es un elemento de $\prod F$. Si $\text{card}(F) = n+1$, entonces podemos expresar $F = F' \cup \lbrace x \rbrace$ como distinto de la unión donde $\text{card}(F') = n$. Como $x \neq \varnothing$, a partir del cálculo anterior, podemos encontrar algunos de los $f:\lbrace x \rbrace \to x$. Por inducción, hay algunos $g \in \prod F'$. Yo se lo dejo a usted para exponer un bijection entre el $\prod F$ e $(\prod F') \times \prod \lbrace x \rbrace$ y así completar el argumento.

Answer 3

Hay dos finito elección de teoremas, la interna y la externa, ambas son verdaderas, en ZF.

Como Charles Staats señalado, la versión externa es una tautología (modulo algunos combinatoria finita): si $a_1,\dots,a_n$ son todos no vacío, entonces hay $z_1 \in a_1$,...,$z_n \in a_n$ y, a continuación, $\lbrace (a_1,z_1),\ldots,(a_n,z_n)\rbrace$ es la opción deseada de la función de la familia $X = \lbrace a_1,\dots,a_n \rbrace$ de conjuntos no vacíos.

La versión interna "cada finito de la familia de conjuntos no vacíos tiene una función de elección" es más fuerte desde un modelo de ZF puede tener no estándar finito cardenales. La prueba en este caso es por inducción sobre la cardinalidad de la familia.

El vacío de la familia tiene un trivial de la función de elección — la función vacía. Supongamos que sabemos que el teorema de ser cierto para las familias de tamaño $n$. Deje $X$ ser una familia de conjuntos no vacíos con el tamaño de la $n+1$. Deje $g:n+1\to X$ ser un bijection. Deje $X' = g[n]$ e $a = g(n)$. A continuación, $X'$ es una familia de conjuntos no vacíos de tamaño $n$, que por lo tanto tiene una función de elección $f':X' \to \bigcup X'$. Desde $a$ es no vacío, podemos encontrar $z \in a$ y, por tanto, $f = f' \cup \lbrace (a,z) \rbrace$ es una función de elección para el original de la familia $X$.

Answer 4

El Axioma de Elección no permite "elegir" una función de elección, sólo se dice que una función de elección existe. Para demostrar que una función de elección para un único conjunto no vacío existe, usted no tiene que "elegir" un elemento en el conjunto, es suficiente para demostrar que al menos un elemento existe (es decir, el conjunto es no vacío). Cada elemento del conjunto le dará una opción diferente función.

¿Qué quiere decir con "elegir" un elemento de un conjunto? ;)