El siguiente artículo de Kurt Maes se centra en una versión de la cuestión que nos ocupa, a saber, encontrar una formulación equivalente de AC en el lenguaje de la teoría de conjuntos utilizando el menor número de cuantificadores, en lugar de simplemente la menor longitud. En su resultado principal, Maes encuentra una afirmación de 5 cuantificadores equivalente al axioma de elección. La afirmación se basa en la misma afirmación que en la respuesta de François, pero modificada para utilizar menos cuantificadores (Maes tiene cinco, en comparación con los diez de François; pero, por supuesto, François no intentaba minimizar esa cantidad).
El resultado de Maes refutó una conjetura de Harvey Friedman, que en la introducción el autor menciona que fue expuesta en F.O.M., de que no sería posible no sería posible enunciar una formulación del axioma de elección utilizando sólo cinco cuantificadores.
Consulte la solución de Maes en su documento.
Cuando me enteré del resultado de Maes (agosto de 2004, aparentemente un borrador anterior de su artículo; no he comprobado las diferencias), naturalmente me propuse la tarea de demostrar el resultado principal por mí mismo, sin mirar el argumento de Maes. Os animo a que hagáis lo mismo: antes de seguir leyendo, intentad expresar AC en el lenguaje de la teoría de conjuntos utilizando sólo cinco cuantificadores. Esto es lo que se me ocurrió (recuperado tras rebuscar en mis viejos archivos de ordenador):
Teorema. AC es equivalente (en ZF) a la siguiente afirmación: $$\forall A\exists B\forall a\in A\, \exists x\forall z$$ $$(x \in a \cap B) \wedge (z \in a \cap B \implies z=x) \wedge (a \neq B)$$ $$\text{or }\quad(B \in x) \wedge (x \in A) \wedge (a \neq x)$$ $$\text{or }\quad(B \in A) \wedge (z \notin B).$$
Prueba. La cuestión es que para reducir a sólo cinco cuantificadores, hay que reutilizar esencialmente los cuantificadores para cubrir los distintos casos. La idea es que la cláusula 1 expresa que $B$ es una selección set para $A$ cuando $A$ es una familia de conjuntos no vacíos disjuntos (además de algo extra útil cuando $A$ no es así). La cláusula 2 expresa que $A$ tiene elementos que no son disjuntos (al menos dos contienen $B$ ). La cláusula 3 expresa que $A$ contiene el conjunto vacío ( $B=\emptyset$ ).
AC implica fácilmente la afirmación. Si $A$ es una familia de conjuntos no vacíos disjuntos conjuntos, entonces podemos dejar que $B$ sea un conjunto de selección para $A$ y verificar la cláusula 1. (nota: para obtener $(a \neq B)$ en el caso de que $A$ es un singleton, podemos añadir libremente elementos irrelevantes a $B$ fuera de $\bigcup A$ .) Si $A$ contiene conjuntos no disjuntos, dejamos que $B$ sea cualquier elemento que esté en al menos dos elementos de $A$ y entonces podemos estar siempre en la cláusula 2, ya que para cualquier elemento de $A$ podemos encontrar otro elemento de $A$ que contiene $B$ . Por último, si $A$ contiene el conjunto vacío, podemos establecer $B=\emptyset$ y verificar siempre la cláusula 3.
A la inversa, supongamos que el principio enunciado es válido. Para demostrar AC, basta con basta con construir un conjunto de selección para una familia $A$ de conjuntos conjuntos no vacíos. Sustituyendo $A$ si es necesario con la copia isomórfica $\{\{w\}\times a\mid a \in A\}$ , donde $w$ tiene un alto rango (como $w=A$ mismo), podemos podemos suponer que cada elemento de $\bigcup A$ tiene el mismo rango. Así, cada elemento de $A$ tiene un rango superior que éste, y cada elemento de $\bigcup\bigcup A$ tiene un rango inferior a esto. De ello se deduce que ningún elemento de $\bigcup A$ está en $A$ y ningún elemento de $\bigcup A$ tiene a su vez elementos en $\bigcup A$ .
Para tal $A$ obtenemos $B$ por el principio enunciado. Obsérvese ahora que la cláusula 2 implica $B \in\bigcup A$ y la cláusula 3 implica $B \in A$ . Mientras tanto, la cláusula 1 implica tanto que $B$ tiene un elemento en $\bigcup A$ y también que $B$ no está en $A$ (ya que implica que $B\cap a$ es no vacía para algún otro $a\in A$ , mientras que los conjuntos en $A$ son disjuntos). Por nuestras suposiciones en $A$ Estas posibilidades son mutuamente excluyentes. De ello se desprende que $B$ debe estar siempre en la cláusula 1, o siempre en la cláusula 2 o siempre en la cláusula 3, independientemente de $a$ , $x$ y $z$ . Si la cláusula 3 siempre ocurre, entonces $\emptyset\in A$ , una contradicción. Si la cláusula 2 siempre ocurre, entonces $B$ debe estar en más de un elemento de $A$ ya que de otra manera podríamos dejar que $a$ sea ese elemento, y esto contradiría la la disociación de los elementos de $A$ . Por lo tanto, debe ser que la cláusula 1 se produzca siempre. En este caso, $B$ es un conjunto de selección, por lo que hemos establecido AC. QED
Aunque no conozco ninguna utilidad que se derive del hecho de que AC se pueda expresar de esta manera, no es menos cierto que la teoría de la prueba a veces ha avanzado investigando los poderes expresivos limitados de los lenguajes.
