Axioma de Elección: ¿Qué es exactamente una opción, y cuándo y por qué es necesaria?

Question

Estoy teniendo problemas para entender la necesidad del Axioma de Elección. Dado un conjunto de no vacía de subconjuntos de, ¿cuál es la necesidad de una función que toma un elemento de cada uno de los subconjuntos? Por ejemplo, echar un vistazo en el siguiente párrafo de la Wikipedia:

Un esbozo de la prueba del lema de Zorn de la siguiente manera, suponiendo que el axioma de elección. Supongamos que el lema es falso. Entonces existe un parcialmente conjunto ordenado, o poset, P tal que cada subconjunto totalmente ordenado tiene una límite superior, y cada elemento tiene uno más grande. Para cada totalmente subconjunto ordenado T entonces podemos definir un mayor elemento de b(T), porque T tiene un límite superior, y que el límite superior tiene un mayor elemento. A en realidad, definir la función b, necesitamos emplear el axioma de elección. El uso de la función b, vamos a definir los elementos de un₀ < ₁ < ₂< un₃ < ... en P. [...]

Para mí está claro que la una_i's existen y ¿por qué necesitamos individualizándolos? Efectivamente, la relación binaria que representa b no puede existir como un conjunto, pero, ¿qué necesitamos?

Por último... si realmente necesario el Axioma de Elección, con una_i's en el párrafo anterior, ya que el axioma sólo postula la existencia de funciones de elección, ¿cómo escogemos a la elección de la función de sí misma, de manera que podemos seleccionar el un_i's con ella? Ciertamente no con otra función de elección, ya que necesitaríamos para elegir esta función por una tercera función de elección.

Así que, cuando y por qué es lo que realmente necesita el Axioma de Elección?

Answer 1

La capacidad de elegir solo los elementos durante una prueba está incorporado en las reglas de la lógica de primer orden; no necesitamos un conjunto teórico axioma para hacerlo. Más precisamente, si sabemos $\exists x.\varphi(x)$ disponible, entonces es admisible para elegir un $x$ que $\varphi$ mantiene. El $\exists x$ fue demostrado anteriormente en la prueba-en cuyo caso sabemos realmente una cosa específica con esta propiedad, debido a que es la forma de demostrar que un $\exists$ - o $\exists x$ proviene de un axioma, en cuyo caso la posibilidad de escoger un $x$ es "moralmente" parte de lo que el axioma que nos promete.

Así que cuando el Axioma de Elección nos promete que "$\exists$" una función de elección, no sólo decir que hay opción de funciones, pero también que nos permite elegir uno.

---

Ahora, ¿por qué queremos tener una función de elección existen dentro de la teoría de conjuntos? La razón principal es que podemos envolver las muchas opciones que se representa y manejar como un único objeto, en particular en el axioma de los esquemas que nos permiten suministrar una fórmula para especificar lo que estamos haciendo. La fórmula puede contener parámetros establecidos, pero sintácticamente sólo puede contener un finito número de parámetros. El Axioma de Elección nos permite parametrizar un ejemplo de axioma esquema con un infinitey de opciones cuando la necesitamos.

Los dos esquemas de axioma esto es relevante por el Axioma de Reemplazo y el Axioma de Selección.

El Axioma de Reemplazo nos permite dar forma a $\{F(x)\mid x\in A\}$ para cualquier conjunto $A$. La función de $F$ no a priori, tienen que existir como un conjunto dentro del conjunto teórico universo; puede ser dada por una fórmula lógica. Pero tenemos que ser capaces de demostrar que no es sólo (o en la mayoría) una $F(x)$ por cada $x$; de lo contrario, el axioma podría producir un conjunto tan grande que se necesita para ser una clase adecuada en su lugar. Sin embargo, a menudo, en realidad queremos utilizar un underspecified $F$ que dice "elegir algo con tal-y-tal de la propiedad", donde podemos demostrar que al menos uno algo siempre existe. Para ello tenemos que envolver todas las opciones como un conjunto de parámetros de la fórmula que representa a $F$; el Axioma de Elección es lo que tenemos que hacer eso. La lógica de primer orden nos permite hacer una sola opciones una por una durante una prueba, pero no para escribir elegir algo como parte de una fórmula.

El Axioma de Selección nos permite dar forma a $\{x\in A\mid \varphi(x)\}$. Aquí, $\varphi$ puede ser una fórmula arbitraria (con parámetros), pero a veces queremos $\varphi$ a depender de algunas opciones arbitrarias que deben ser el mismo para todas las $x$s en $A$ consideramos. De nuevo, el problema -- de parte de ella-es que la fórmula de $\varphi$ no puede hablar acerca de la toma de decisiones de una manera controlada, pero podemos parametrizar $\varphi$ por una función de elección que podemos seleccionar de una vez por todas fuera de la aplicación de la Selección axioma.

---

Todo lo anterior es para el estándar de la lógica de primer orden. Hay una alternativa-pero hoy en día la mayoría olvidado, formalismo lógico, Hilbert $\varepsilon$-cálculo donde en lugar de quantifers en la fórmula de nivel uno tiene un plazo $\varepsilon x.\varphi(x)$ que intuitivamente significa "algunos $x$ que hace $\varphi$ cierto, si tal cosa existe, de lo contrario, un objeto cualquiera". Hay una traducción estándar de estándar de primer orden en las fórmulas de las fórmulas en la $\varepsilon$-cálculo, y es un conservador extensión de FOL con respecto a estas fórmulas.

En el $\varepsilon$-cálculo de nosotros no necesita una opción explícita axioma, porque ahora las fórmulas pueden hablar acerca de las decisiones arbitrarias-pero-opciones coherentes; que es exactamente lo que el $\varepsilon$ operador.

Por otro lado, si queremos formular la teoría de conjuntos sin CA en el $\varepsilon$-cálculo, tenemos que ser cuidadosos para restringir los axiomas de la Sustitución y la Selección, tales que el parámetro de las fórmulas deben ser de la restricción de la forma que surge como traducción del estándar FOL fórmulas. Si esta restricción no se hace, el Axioma de Elección puede ser demostrado: si $X$ es un conjunto de conjuntos no vacíos, entonces $$\{ (x,\varepsilon y.y\in x)\mid x\in X\}$$ es una función de elección para $X$.

Answer 2

Edward Nelson explicó muy bien en el Capítulo 2 de un papel que solía ser en su página de inicio en la universidad de Princeton ("quitado de revisión" hace varios años). Voy a tratar de hacer lo mismo utilizando mi comprensión adquirida a partir de él, ya que no se puede señalar que el papel nada más. En lógica se muestra (extensión por contigüidad de un símbolo de función) que si $\mathbf{\varphi}$ es una fórmula cuyas variables libres se $\mathbf{x, x_1, \dots, x_n}$, y si $\mathbf{\forall x_1 \dots \forall x_n \exists x \varphi}$ es un teorema, entonces podemos lindan con un nuevo $n$-ary símbolo de función $\mathbf{f}$ y el axioma $\mathbf{\forall x_1 \dots \forall x_n [fx_1 \dots x_n/x] \varphi}$ para obtener un conservador de extensión. Pero un conservador de extensión si se aplica a la teoría de conjuntos no contiene nuevo conjunto de axiomas de la teoría de permitir que el nuevo símbolo de función que aparecen en los axiomas obtenidos a partir de la separación (subconjunto) y reemplazo (o colección) de esquema. En la práctica, esto no hace ninguna diferencia si la extensión es lo que se llama una extensión, por definición, lo cual ocurre cuando la declaración más fuerte en la $\mathbf{\forall x_1 \dots \forall x_n \exists ! x \varphi}$ sostiene (donde $\mathbf{\exists ! x}$ significa que "no existe un único $\mathbf{x}$ tal que"). La razón es que en este caso, cualquier fórmula que contiene $\mathbf{f}$ puede ser traducido a un equivalente (en extensión) que la fórmula no contiene $\mathbf{f}$, que la fórmula está permitido en la separación y reemplazo de los axiomas. También, cuando se $\mathbf{\varphi}$ no contiene variables libres distinta de $\mathbf{x}$ no hay ningún problema con lo que permite a la (constante especial, $0$-ary) $\mathbf{f}$ a aparecer en la sustitución y la separación de los axiomas, ya que esos axiomas se mantenga al $\mathbf{f}$ es reemplazado por una variable que no aparece en los axiomas (y la sustitución tiene).

Del mismo modo, si $\mathbf{\psi}$ es una fórmula con variables libres $\mathbf{x_1, \dots, x_n}$, podemos lindan con un nuevo $n$-ary predicado símbolo $\mathbf{p}$, junto con la definición de axioma $\mathbf{\forall x_1 \dots \forall x_n (p x_1 \dots x_n \leftrightarrow \psi)}$. Estos también son llamados extensiones, por definición, presumiblemente debido a las declaraciones que implican $\mathbf{p}$ son traducibles a equivalente declaraciones no implican $\mathbf{p}$. Ser traducible, de nuevo hay ningún problema permitiendo a los nuevos símbolos de predicado derivadas de las extensiones mediante la definición de un predicado símbolo aparezca en la separación y reemplazo de los axiomas.

En la práctica, haciendo que la teoría de conjuntos o de la matemática superior, basado en la teoría de conjuntos, uno puede utilizar las extensiones, por definición, y extensiones de constantes especiales con abandono, incluso en la separación y reemplazo de los axiomas. De hecho, las matemáticas sería impractically tedioso, a menos que este o algo similar. Pero cuando uno utiliza las extensiones por contigüidad de un símbolo de función que no son extensiones de la definición de un símbolo de función, como sucede cuando la singularidad de condición de falla, uno necesita algo como el axioma de elección para reformular los símbolos de función, de modo que puede ser utilizado en la separación y reemplazo de los axiomas. En la práctica, lo que esto significa es que cualquier función de los símbolos debe corresponder a las funciones obtenible por el axioma de elección. A menudo (por ejemplo, cuando las variables rango de más de conjuntos como el conjunto de los números reales) el axioma de elección puede ser utilizado para reemplazar algo como $\mathbf{\forall x_1 \dots \forall x_n \exists x \varphi}$ con algo como $\mathbf{\exists f \forall x_1 \dots \forall x_n [f(x_1, \dots, x_n)/x] \varphi}$, donde aquí $\mathbf{f}$ es una variable que representa un conjunto teórico de la función y el paréntesis denotan un símbolo de función definición de evaluación (para cada función y argumento corresponde una única evaluación de la función en ese argumento, y por lo que la evaluación puede ser definida problemas-libre, por extensión, por definición de la función de símbolo). La declaración de $\mathbf{\exists f \forall x_1 \dots \forall x_n [f(x_1, \dots, x_n)/x] \varphi}$ puede ser utilizado para lindan con un símbolo de función $\mathbf{f_c}$ correspondiente a $\mathbf{f}$ que no causan los problemas que aparecen en la separación o el reemplazo de los axiomas siempre $\mathbf{\varphi}$ sólo involucra $\mathbf{x, x_1, \dots, x_n}$ como variables libres, porque entonces $\mathbf{f_c}$ podría ser definido como una constante especial (confusamente, $\mathbf{f_c}$ tiene que ser $0$-ary).

Bourbaki, mediante el uso de Hilbert tau de operador (que supongo que es parecido o igual de Hilbert epsilon operador) hace algo similar para permitir que las fórmulas obtenidas por mera contigüidad de la función de los símbolos que aparecen en la separación y reemplazo de los axiomas (ambos enfoques haría que el axioma de elección para ser un teorema), pero por mucho que me guste Bourbaki, he llegado a preferir aquí la forma estándar de los lógicos, de hacer las cosas, que utiliza un axioma de elección. Suponiendo que en exceso no es estéticamente agradable.

Answer 3

Como ad, además Henning Makholm explicación.

Ejemplo.
Considere la posibilidad de colección finita de conjuntos de $A_k, \; k\in S=\{1, \ldots , K\}$, donde cada $A_k$ es contable. ¿Qué acerca de la unión de $\bigcup\limits_{k=1}^{K}A_k$?
Así, podemos decir que como $A_1$ es contable existe una enumeración $f_1$, $A_2$ es contable -$f_2$. Entonces podemos repetir esta frase $K$ veces y después podemos trabajar con estas funciones $f_1 \ldots f_K$. Entonces podemos hacer algo simple: tomar un bijection $g: \mathbb{N}\times S \to \mathbb{N}$ y este es: unión finita de conjuntos contables es contable.

OK, pero ten en cuenta contables de la colección de conjuntos contables $A_k, \; k\in\mathbb{N}$ - lo que acerca de la unión de $\bigcup\limits_{k=1}^{\infty}A_k$? No podemos repetir la frase acerca de la enumeración infinitas veces, porque cada prueba en matemáticas debe ser finito. Por lo tanto, tenemos un problema aquí - para cada $k$ existe una función de $f_k: \mathbb{N} \to A_k$, pero no el conjunto de $\{ f_k : k \in \mathbb{N} \}$ existe? Usted no puede decir sin el axioma de elección (en realidad, va a ser suficiente para tener más débil de la versión de ella, pero aún así).