¿Por qué el axioma de elección no es necesaria cuando la colección de conjuntos es finita?

Question

De acuerdo a Wikipedia:

Informalmente, el axioma de elección, dice que, dado cualquier colección de los recipientes, cada uno que contiene al menos un objeto, es posible hacer un selección de un objeto exactamente de cada bin. En muchos casos, un la selección puede hacerse sin invocar el axioma de elección, esto es, en en particular el caso de que el número de contenedores es finito...

¿Cómo sabemos que podemos hacer una selección cuando el número de contenedores es finito? ¿Cómo podemos saber que podemos hacer una selección de una sola bandeja de elementos finitos?

A continuación se da un ejemplo:

Para dar una informales ejemplo, para cualquier (infinito) de la colección de pares de zapatos, uno puede elegir el zapato izquierdo de cada par a obtener una adecuada selección, pero para una colección infinita de pares de calcetines (que se supone que no tienen características distintivas), un la selección sólo puede obtenerse mediante la invocación del axioma de elección.

Pero, ¿cómo podemos incluso hacer una selección de un simple par de calcetines si no tienen ninguna de las características distintivas? Hay otro axioma que se asume aquí?

Answer 1

Es una cuestión de las reglas básicas de inferencia permitido en las pruebas.

Supongamos $\mathcal B$ es una "colección" de contenedores con un solo elemento, es decir, $\mathcal B = \{S\}$ algunas $S$. La suposición es que el $S$ es no vacío. Por definición, esto significa que no existe $x \in S$. Podemos utilizar el existencial instantitation regla de inferencia para solucionar $x \in S$. A continuación, la asociación $$\mathcal B \to \bigcup_{T \in \mathcal B} T = S$$ given by $$\{S \mapsto x\}$$ define una función de elección.

Del mismo modo, uno puede demostrar por inducción que si $\mathcal B$ es una colección finita de vacío cubos, luego de una función de elección existe - si $\mathcal B_n$ es una colección de $n$ vacía los cubos, luego de fijación $S \in \mathcal B_n$, se deduce que el $\mathcal B_n \setminus \{S\}$ es una colección de $n-1$ vacía los cubos.

Answer 2

El axioma de elección, dice precisamente que si $I$ es un conjunto y, para cada una de las $i \in I$, tenemos un conjunto no vacío $X_i$, entonces el producto de a $\prod_{i \in I} X_i$ no está vacía. (Los elementos de los productos puede ser identificado con la elección de las funciones, de modo de no-vacío del producto es equivalente a la existencia de una función de elección.) Al $I$ es finito, esta es una afirmación que se puede demostrar por inducción sobre $|I|$, que no requiere de la elección.

Answer 3

Esta es una buena pregunta; la respuesta principal es que el hacer una sola elección de un solo bin es una cuestión de lógica.

Especializado para esta situación en particular, si $S$ es un conjunto y que han demostrado $\exists x : x \in S$, entonces la lógica le permite introducir una nueva constante de símbolos (por ejemplo, $a$) junto con la correspondiente un axioma $a \in S$.

La interpretación usual de esta mecánica es que $a$ representa una "elección" de un elemento de $S$, aunque esto no significa que la única manera de interpretar este tipo de cosas:

• Podríamos interpretar $a$ como simplemente ser una variable ficticia, de modo que lo que estamos haciendo es definir una función de $S$
• Podríamos interpretar $a$ a como una especie de 'genérico' elemento de $S$ más que una elección de un elemento específico
• Algunas formas de la lógica permite introducir $a \in S$, incluso cuando se $S$ es un conjunto vacío; naturalmente, esto no se presta bien a la interpretación de $a$ como una elección de un elemento!

Cualquier forma que se mire, se puede usar para probar que puede hacer una elección de una sola bandeja en la teoría de conjuntos; los pasos principales son

• Introducir $a \in S$
• Espectáculo $\{ (S, a) \}$ es una función de elección en $\{ S \}$

Independientemente de nuestras opiniones filosóficas sobre la lógica, esta construcción se define una función

$$ S \to \operatorname{ChoiceFunctions}(\{ S \}) $$

donde $\operatorname{ChoiceFunctions}(X)$ significa que la colección de todas elección de las funciones de $X$. Esto, junto con la hipótesis de que la $S$ es no vacío, implica que $\operatorname{ChoiceFunctions}(\{ S \}) $ es no vacío así.

---

Finito elección es básicamente el mismo. En un ad-hoc de la moda puede repetir este tipo de argumento en varias ocasiones la introducción de una variable a la vez. Alternativamente (en teoría) puede configurar una definición recursiva y mostrar finito de opciones puede ser hecha por inducción; IIRC la prueba es sencillo, pero complicado.

Answer 4

Esto no es una respuesta directa a la pregunta, sino una manera de pensar sobre el axioma de elección.

El axioma de elección es una generalización de la finitud. Relacionada (por ejemplo, el teorema de compacidad en la lógica, y el teorema de Tychonoff en la topología) a topológico compacto, que es otra generalización de la finitud.

Sin el axioma de elección, a veces, puede especificar una opción: "Elige el zapato izquierdo de cada par." Si usted puede hacer (leer: definir) una especificación, no es necesario el axioma de elección, ya que puede apuntar a que la especificación de su elección.

Considere cómo cada uno equivalente a la definición de la Opción es cierto en lo finito de configuración:

• "Cada finito producto de la no-vacía de conjuntos tiene al menos un elemento." Si te dan un par de conjuntos, puede seleccionar uno de cada uno, un paso a la vez. (Si usted tiene un número infinito de conjuntos, se necesita un número infinito de pasos.)
• "Cada finito conjunto puede ser bien ordenado." Si usted tira de elementos de una en una, que es un buen orden. (De nuevo, sería necesario un número infinito de pasos para un conjunto infinito.)
• "Cada finito espacio vectorial tiene una base." Elija un no-vector cero. A continuación, tomar un vector no en el subespacio lineal generado por el primer vector. A continuación, tomar un vector no en el lapso de los dos primeros vectores. Finalmente, te quedarás fuera de vectores.
• "Cada dos finito cardenales son comparables." Contar desde 0 hasta llegar a la primera. Esa es la más pequeña. Si se llega a los dos a la vez, son iguales.

En un sentido informal, el axioma de elección dice que siempre se puede tomar un número infinito de (ciertos tipos de) pasos en tiempo finito. Y usted puede seguir sólo una declaración y la prueba de que tiene un tiempo limitado para leer. El axioma de elección es también no-constructiva: no se puede usar para hacer un "real" ejemplo, porque había necesidad infinita de tiempo de construcción.

---

Más sobre la finitud y declaraciones:

Deje $X = X_0 \times X_1 \times X_2 \times \dots$ ser un producto de conjuntos. Entonces el axioma de elección, dice

$$\exists x_0 \in X_0 \ \exists x_1 \in X_1 \ \exists x_2 \in X_2 \ \exists \dots \ \text{s.t.} (x_0, x_1,x_2, \dots) \in X$$

Pero los primeros puntos suspensivos en realidad no tienen sentido en la lógica. No hay lógica matemática reglas permiten un número infinito de cuantificadores. El axioma de elección tipo de dice, "está bien, todavía funciona."

Por otro lado, se puede definir la "zapato izquierdo" elección con sólo un número finito de cuantificadores. Deje $I$ ser el índice establecido para el producto. Entonces

$$\{\text{left}_i \in X_i | i \in I\} \in X$$

es una opción de toda la izquierda zapatos, con una implícita cuantificador sobre el conjunto de índices.

Answer 5

Si compro un par de calcetines blancos, y nunca he usado ninguno de ellos, entonces ellos no tienen ninguna de las características distintivas. Sin embargo, la gente hace este tipo de decisiones sobre una base diaria.

Se puede argumentar, mientras que indiscernible, los dos calcetines seguramente tienen alguna característica que los distingue! Y había de ser la correcta. A pesar de que podría no ser capaz de señalar con el dedo y decir "¡Ajá! Esto es lo que distingue a ellos!", y usted podría tener que recurrir a algo así como sus partículas o algunos otros microscópicos a nivel de tipo de diferencia.

Pero si ahora me pide que elija entre varias parejas al mismo tiempo, primero necesita para inspeccionar cada par bajo un microscopio (o algunos otros más destructivas pruebas) con el fin de ser capaz de describir un proceso de elección. Tal vez en un par de algodón, la impureza es mayor en uno, y tal vez en otro es la misma. De manera que cada par debe ir bajo el cuidado de cheques para que usted me puede decir qué calcetín fue elegido de cada par.

Por supuesto, usted puede abandonar este método, y sólo tiene que ir "Este calcetín, que el calcetín, este calcetín, y que de calcetín". Pero eso no va a funcionar si usted tiene una infinidad de calcetines.

Y, de hecho, en la versión formal de los calcetines analogía—que es de todos , de que es una analogía, y haríamos bien en recordar que—tenemos conjuntos de dos elementos y no podemos elegir entre todos estos pares simultáneamente. Por supuesto, dado un par, podemos mostrar que existen diferencias entre los dos elementos del conjunto, después de todo ellos no son el mismo elemento, pero no podemos señalar una propiedad única que funcione para todos los pares al mismo tiempo. Es por eso que el axioma de elección es necesaria en este caso.