Axioma de elección y conjuntos finitos

Question

Así que estoy relativamente familiarizado con el axioma de elección y con algunas de sus formas equivalentes (el lema de Zorn, lo sobreyectivo implica lo invertible a la derecha, etc.), pero nunca he tomado un curso de teoría de conjuntos.

Sé que hay ocasiones en las que no se ofrece una forma explícita de elegir algunos elementos, y en su lugar recurrimos al Axioma de Elección para que lo haga por nosotros. Pero hay algo que siempre me ha preocupado.

He oído que para un conjunto finito no necesitamos el axioma de elección para elegir un elemento. Esto me parece un poco confuso. ¿En qué se diferencia la elección de un elemento de un conjunto finito de la elección de un conjunto infinito? He oído antes "como el conjunto es finito, hay finitamente muchos órdenes, así que ordena el conjunto y elige el primer elemento del orden". Pero, ¿cómo se elige qué orden utilizar? Se trata de elegir un elemento de un conjunto finito, es decir, se presupone la conclusión.

Supongo que hay una buena razón por la que todo el mundo insiste en que el axioma de elección no es necesario para elegir entre conjuntos finitos, así que ¿podría alguien explicármelo?

Edición: Parece que hay confusión sobre lo que estoy pidiendo exactamente. Sé que necesitamos el axioma de elección, a veces, para hacer infinitas elecciones, de conjuntos finitos o infinitos. Esto no es lo que me confunde. Permítame ser más preciso:

Supongamos que $S$ es un conjunto finito no vacío. Quiero elegir un elemento de $S$ . ¿Elegir un elemento de $S$ ¿requieren el axioma de la elección? Si no es así, ¿cómo puede hacerse la elección sin el axioma de elección?

Diciendo $S$ no está vacío, por lo que existe un $x \in S$ no es suficiente. ¿Cómo puedo elija tal $x$ ? Hay uno, pero ¿cómo lo describo sin ninguna información sobre el conjunto, aparte del hecho de que es no vacío y finito?

Otra aclaración: Yo soy no preguntando sobre el uso de "Que... se dé" como técnica de prueba.

Answer 1

La capacidad de dar un nombre a algún elemento arbitrario de un conjunto no vacío se conoce como "instanciación existencial". Se trata de una regla de inferencia de la lógica subyacente, no de la teoría, por lo que se incluye no sólo en ZFC, sino también en ZF, y en formas apropiadas también se incluye en PA y en cualquier otra teoría de primer orden.

La intuición es que dar un nombre a un objeto no requiere realmente "elegir" un objeto; si sabemos que hay un elemento en un conjunto $A$ y empezamos a discutir sobre algún elemento "dado" $c \in A$ No tenemos que hacer una elección, podemos razonar hipotéticamente ("¿qué pasaría si supiéramos que un elemento $c$ de $A$ ?"). Este razonamiento será sólido porque $A$ es realmente no vacía. Sin embargo, como no sabemos qué elemento se elige, las únicas propiedades que sabemos que tiene son las que podemos demostrar que cada elemento de $A$ tiene. En particular, no podemos asumir que el elemento que se nos da es igual a cualquier otro objeto que ya tengamos, a menos que podamos demostrar que son iguales. Así que tenemos que dar un nuevo nombre que no estemos usando ya para ningún otro objeto.

La palabra "elegir" se utiliza de varias maneras en la teoría de conjuntos, tanto de esta forma (instanciación existencial), como en formas correspondientes al axioma de elección, y en formas en las que no hay realmente ninguna elección, por ejemplo cuando tenemos una función $f$ y un conjunto $x$ y nosotros "elegimos" $y$ tal que $f(x) = y$ . Hay que fijarse en el contexto para saber qué prueba formal sugiere la prueba informal que se lee.

Podría pensar que "elegir" un solo elemento de un conjunto sería una operación algorítmica, pero no es así. La no constructividad de la instanciación existencial es una consecuencia directa del significado no constructivo de $\exists$ en la lógica clásica. Para conseguir un sistema en el que se pueda elegir efectivamente un testigo para cualquier afirmación existencial verdadera, hay que pasar a la matemática constructiva, pero entonces el significado de $\exists$ también cambia.

Answer 2

Saying S is not empty, therefore there is an x∈S, does not suffice.

Ah, pero es hace ¡es suficiente! Sabiendo que $S$ es no vacía, hay hacer existen tales $x$ y así podemos declarar el símbolo $x$ para denotar un elemento de $S$ y el resto de nuestro argumento es entonces una función de $x$ .

Para decirlo de manera más formal, una prueba típica que elige un elemento de $S$ tiene la forma

Let x∈S
...
Therefore P

y constituye una prueba de $\forall x: (x \in S \implies P)$ que a su vez implica $P \vee (S = \emptyset)$ .

De la misma manera, si usted hizo dos elecciones $x \in S, y \in T$ , se suele probar una afirmación como $\forall x,y: \left( (x,y) \in S \times T\implies P \right) $ .

Esto deja claro cómo entra en escena el axioma de elección; una secuencia de infinitas elecciones indexadas por $I$ de la forma descrita anteriormente sería una prueba de

$$ \forall x : \left(x \in \prod_{i \in I} S_i \implies P \right)$$

lo que implica

$$ P \vee \left(\prod_{i \in I} S_i = \emptyset \right) $$

es decir, una prueba de que $P$ es verdadera o la familia $S_i$ no tiene una función de elección (o ambas).

Answer 3

Hay dos cosas. Deja que $(A_i)_{i\in I}$ sea una familia arbitraria de conjuntos no vacíos. Una versión del axioma de elección dice que $\prod_i A_i\neq\emptyset$ . No podemos demostrar esto sin el axioma de elección si sabemos que para todo $i\in I$ el conjunto $A_i$ es finito. Lo que podemos demostrar es que el producto es no vacío si $I$ ¡es finito!

La prueba es la siguiente: Demostramos que para cada $n$ , si $I$ tiene $n$ elementos, entonces el producto es no vacío. Lo hacemos por inducción. Sin pérdida de generalidad, dejamos que $I=\{1,\ldots,n\}$ . Si $I$ contiene un único elemento, demostrar que el producto no es vacío equivale a encontrar un elemento en el conjunto único $A_1$ . Que esto se pueda hacer es simplemente el significado de $A_1$ siendo no vacía. Entonces, supongamos que existe una función de elección $(a_1,\ldots,a_{n-1})$ definido en $I\backslash\{n\}=\{1,\ldots,n-1\}$ . Desde $A_n$ es no vacía, hay algún $a_n\in A_n$ . Esto da una función de elección para $I$ dado por $(a_1,\ldots,a_{n-1},a_n)$ . Y para esto, no necesitamos el axioma de la elección.

Answer 4

El axioma de la elección, como se ha dicho, nos permite elegir entre infinitamente muchos conjuntos a la vez (¡a veces incluso cuando estos conjuntos son finitos!). Sin embargo, si sólo se desea elegir entre un número finito de conjuntos, se puede prescindir de él. Ni siquiera importa si los conjuntos son finitos o no.

Elegir un elemento de $A$ significa fijar un elemento concreto de $A$ . Si podemos nombrarlo ( $0$ por ejemplo, elegido entre los números reales) entonces está bien. Si no conocemos el nombre del elemento de antemano, entonces tenemos que asignarle un nombre.

Lo hacemos utilizando el infame "let", y a partir de ahí acordamos que el nombre asignado se refiera sólo a ese elemento en particular, por ejemplo

Dejemos que $r\in\mathbb R\setminus\mathbb Q$ ...

Lo que ocurre es que como suponemos que $A$ es no vacío entonces la proposición $\exists x(x\in A)$ es cierto. Ahora escribiendo el resto de la prueba podemos pensar en ella como una lista de fórmulas que $x$ es una de las variables libres en esas fórmulas, llamémoslas $\varphi_1(x,y_1),\ldots,\varphi_k(x,y_k)$ .

Cuando elegimos un elemento de $A$ decimos: $$\ldots\exists x(x\in A\land\varphi_1(x,y_1)\ldots\varphi_k(x,y_k))\ldots$$

Así que tenemos alguna proposición previa, algunas otras variables asignadas y tenemos la prueba misma en el medio, y le asignamos un $x$ .

(Tenga en cuenta que si requerimos $x$ para tener una determinada propiedad, entonces sustituimos $A$ con un subconjunto de $A$ de "todos los elementos que tienen la propiedad requerida en $A$ ", ¡por supuesto que a veces tenemos que argumentar que este conjunto no está vacío!)

Si se entiende esta explicación, no debería ser difícil ver por qué podemos elegir también muchos elementos de conjuntos finitos no vacíos.

Answer 5

No es necesario "elegir" $x$ (¿Qué quiere decir con "elegir"? $x$ ?) Sólo tiene que demostrar que al menos uno $x$ existe, que es en realidad su suposición (el conjunto es no vacío), por lo que no hay nada que demostrar.

El axioma de elección no "elige" una función de elección, sólo dice que existe al menos una función de elección. Se puede enunciar de la siguiente forma:

El producto cartesiano de una familia de conjuntos no vacíos es no vacío.

Para un conjunto esto es obvio.