Axioma de regularidad

Axioma de la teoría de conjuntos

En matemáticas , el axioma de regularidad (también conocido como axioma de fundamento ) es un axioma de la teoría de conjuntos de Zermelo-Fraenkel que establece que todo conjunto no vacío A contiene un elemento que es disjunto de A. En lógica de primer orden , el axioma se lee:

${\displaystyle \forall x\,(x\neq \varnothing \rightarrow \exists y(y\in x\ \land y\cap x=\varnothing )).}$

El axioma de regularidad, junto con el axioma de emparejamiento , implica que ningún conjunto es un elemento de sí mismo y que no existe una secuencia infinita ( a _n ) tal que a _i+1 sea un elemento de a _i para todo i . Con el axioma de elección dependiente (que es una forma debilitada del axioma de elección ), este resultado puede invertirse: si no existen tales secuencias infinitas, entonces el axioma de regularidad es verdadero. Por lo tanto, en este contexto, el axioma de regularidad es equivalente a la oración de que no hay cadenas de pertenencia infinitas hacia abajo.

El axioma es una contribución de von Neumann (1925); fue adoptado en una formulación más cercana a la que se encuentra en los libros de texto contemporáneos por Zermelo (1930). Virtualmente todos los resultados en las ramas de las matemáticas basadas en la teoría de conjuntos se mantienen incluso en ausencia de regularidad; véase el capítulo 3 de Kunen (1980). Sin embargo, la regularidad hace que algunas propiedades de los ordinales sean más fáciles de demostrar; y no sólo permite que se haga la inducción en conjuntos bien ordenados sino también en clases propias que son estructuras relacionales bien fundadas, como el ordenamiento lexicográfico en ${\displaystyle \{(n,\alpha )\mid n\in \omega \land \alpha {\text{ is an ordinal }}\}\,.}$

Teniendo en cuenta los demás axiomas de la teoría de conjuntos de Zermelo-Fraenkel, el axioma de regularidad es equivalente al axioma de inducción . El axioma de inducción tiende a utilizarse en lugar del axioma de regularidad en las teorías intuicionistas (las que no aceptan la ley del tercio excluido ), donde los dos axiomas no son equivalentes.

Además de omitir el axioma de regularidad, las teorías de conjuntos no estándar han postulado la existencia de conjuntos que son elementos de sí mismos.

Implicaciones elementales de la regularidad

Ningún conjunto es un elemento de sí mismo

Sea A un conjunto y apliquemos el axioma de regularidad a { A }, que es un conjunto por el axioma de emparejamiento . Vemos que debe haber un elemento de { A } que sea disjunto de { A }. Como el único elemento de { A } es A , debe ser que A sea disjunto de { A }. Por lo tanto, como , no podemos tener a A como el único elemento de A (por la definición de disjunto ). ${\displaystyle A\cap \{A\}=\varnothing }$

No existe una secuencia descendente infinita de conjuntos

Supóngase, por el contrario, que existe una función , f , sobre los números naturales con f ( n +1) un elemento de f ( n ) para cada n . Definamos S = { f ( n ): n un número natural}, el rango de f , que puede verse como un conjunto a partir del esquema axiomático de reemplazo . Aplicando el axioma de regularidad a S , sea B un elemento de S que es disjunto de S . Por la definición de S , B debe ser f ( k ) para algún número natural k . Sin embargo, se nos da que f ( k ) contiene f ( k +1) que también es un elemento de S . Por lo tanto , f ( k +1) está en la intersección de f ( k ) y S . Esto contradice el hecho de que son conjuntos disjuntos. Puesto que nuestra suposición condujo a una contradicción, no debe existir ninguna función de ese tipo, f .

La inexistencia de un conjunto que se contenga a sí mismo puede verse como un caso especial donde la secuencia es infinita y constante.

Nótese que este argumento sólo se aplica a funciones f que pueden ser representadas como conjuntos en oposición a clases indefinibles. Los conjuntos finitos hereditarios , V _ω , satisfacen el axioma de regularidad (y todos los demás axiomas de ZFC excepto el axioma de infinito ). Entonces, si uno forma una ultrapotencia no trivial de V _ω , entonces también satisfará el axioma de regularidad. El modelo resultante contendrá elementos, llamados números naturales no estándar, que satisfacen la definición de números naturales en ese modelo pero que no son realmente números naturales ^{[ dudoso – discutir ]} . Son números naturales "falsos" que son "más grandes" que cualquier número natural real. Este modelo contendrá infinitas secuencias descendentes de elementos. ^{[ aclaración necesaria ]} Por ejemplo, supongamos que n es un número natural no estándar, entonces y , y así sucesivamente. Para cualquier número natural real k , . Esta es una secuencia descendente interminable de elementos. Pero esta secuencia no es definible en el modelo y, por lo tanto, no es un conjunto. Por lo tanto no se puede demostrar ninguna contradicción con la regularidad. ${\displaystyle (n-1)\in n}$ ${\displaystyle (n-2)\in (n-1)}$ ${\displaystyle (n-k-1)\in (n-k)}$

Definición más simple del par ordenado en teoría de conjuntos

El axioma de regularidad permite definir el par ordenado ( a , b ) como { a ,{ a , b }}; véase par ordenado para más detalles. Esta definición elimina un par de llaves de la definición canónica de Kuratowski ( a , b ) = {{ a },{ a , b }}.

Cada conjunto tiene un rango ordinal

Ésta era en realidad la forma original del axioma en la axiomatización de von Neumann.

Supóngase que x es un conjunto cualquiera. Sea t el cierre transitivo de { x }. Sea u el subconjunto de t que consiste en conjuntos sin rango. Si u está vacío, entonces x está clasificado y hemos terminado. De lo contrario, aplique el axioma de regularidad a u para obtener un elemento w de u que es disjunto de u . Como w está en u , w no tiene rango. w es un subconjunto de t por la definición de cierre transitivo. Como w es disjunto de u , cada elemento de w tiene rango. Aplicando los axiomas de reemplazo y unión para combinar los rangos de los elementos de w , obtenemos un rango ordinal para w , a saber . Esto contradice la conclusión de que w no tiene rango. Por lo tanto, la suposición de que u no estaba vacío debe ser falsa y x debe tener rango. ${\displaystyle \textstyle \operatorname {rank} (w)=\cup \{\operatorname {rank} (z)+1\mid z\in w\}}$

Por cada dos conjuntos, sólo uno puede ser elemento del otro

Sean X e Y conjuntos. Luego apliquemos el axioma de regularidad al conjunto { X , Y } (que existe por el axioma de emparejamiento). Vemos que debe haber un elemento de { X , Y } que también sea disjunto de él. Debe ser X o Y . Por la definición de disjunto, entonces, debemos tener que Y no es un elemento de X o viceversa.

El axioma de elección dependiente y la ausencia de una secuencia descendente infinita de conjuntos implica regularidad.

Sea el conjunto no vacío S un contraejemplo del axioma de regularidad; es decir, cada elemento de S tiene una intersección no vacía con S . Definimos una relación binaria R en S por , que es entera por suposición. Así, por el axioma de elección dependiente, hay alguna secuencia ( a _n ) en S que satisface a _n Ra _n+1 para todo n en N . Como se trata de una cadena descendente infinita, llegamos a una contradicción y, por lo tanto, no existe tal S. ${\displaystyle aRb:\Leftrightarrow b\in S\cap a}$

Regularidad y el resto de axiomas de ZF(C)

Skolem (1923) y von Neumann (1929) demostraron que la regularidad es relativamente consistente con el resto de la FZ, lo que significa que si la FZ sin regularidad es consistente, entonces la FZ (con regularidad) también lo es. Para su demostración en notación moderna, véase, por ejemplo, Vaught (2001, §10.1).

También se demostró que el axioma de regularidad es independiente de los demás axiomas de ZF(C), suponiendo que sean consistentes. El resultado fue anunciado por Paul Bernays en 1941, aunque no publicó una prueba hasta 1954. La prueba implica (y condujo al estudio de) los modelos (o métodos) de permutación de Rieger-Bernays , que se utilizaron para otras pruebas de independencia para sistemas no bien fundados (Rathjen 2004, p. 193 y Forster 2003, pp. 210-212).

Regularidad y paradoja de Russell

La teoría de conjuntos ingenua (el esquema axiomático de comprensión irrestricta y el axioma de extensionalidad ) es inconsistente debido a la paradoja de Russell . En las primeras formalizaciones de conjuntos, los matemáticos y lógicos han evitado esa contradicción reemplazando el esquema axiomático de comprensión por el mucho más débil esquema axiomático de separación . Sin embargo, este paso por sí solo lleva a teorías de conjuntos que se consideran demasiado débiles. ^{[ aclaración necesaria ] [ cita necesaria ]} Por lo tanto, parte del poder de comprensión se agregó nuevamente a través de los otros axiomas de existencia de la teoría de conjuntos ZF (emparejamiento, unión, conjunto potencia, reemplazo e infinito) que pueden considerarse casos especiales de comprensión. ^{[ cita necesaria ] [ aclaración necesaria ]} Hasta ahora, estos axiomas no parecen conducir a ninguna contradicción. Posteriormente, se agregaron el axioma de elección y el axioma de regularidad para excluir modelos con algunas propiedades indeseables. Se sabe que estos dos axiomas son relativamente consistentes.

En presencia del esquema axiomático de separación, la paradoja de Russell se convierte en una prueba de que no existe un conjunto de todos los conjuntos . El axioma de regularidad, junto con el axioma de emparejamiento, también prohíben un conjunto universal de este tipo. Sin embargo, la paradoja de Russell produce una prueba de que no existe un "conjunto de todos los conjuntos" utilizando solo el esquema axiomático de separación, sin ningún axioma adicional. En particular, la FZ sin el axioma de regularidad ya prohíbe un conjunto universal de este tipo.

Si se extiende una teoría añadiendo uno o más axiomas, las consecuencias (posiblemente indeseables) de la teoría original siguen siendo consecuencias de la teoría extendida. En particular, si se extiende ZF sin regularidad añadiendo regularidad para obtener ZF, cualquier contradicción (como la paradoja de Russell) que se desprendiera de la teoría original seguiría existiendo en la teoría extendida.

La existencia de átomos de Quine (conjuntos que satisfacen la ecuación de fórmula x  = { x }, es decir, se tienen a sí mismos como sus únicos elementos) es consistente con la teoría obtenida al eliminar el axioma de regularidad de ZFC. Varias teorías de conjuntos no bien fundadas permiten conjuntos circulares "seguros", como los átomos de Quine, sin volverse inconsistentes por medio de la paradoja de Russell. ^[1]

Regularidad, jerarquía acumulativa y tipos

En ZF se puede demostrar que la clase , llamada universo de von Neumann , es igual a la clase de todos los conjuntos. Esta afirmación es incluso equivalente al axioma de regularidad (si trabajamos en ZF omitiendo este axioma). A partir de cualquier modelo que no satisfaga el axioma de regularidad, se puede construir un modelo que lo satisfaga tomando solo conjuntos en . ${\displaystyle \bigcup _{\alpha }V_{\alpha }}$ ${\displaystyle \bigcup _{\alpha }V_{\alpha }}$

Herbert Enderton  (1977, p. 206) escribió que "la idea de rango es descendiente del concepto de tipo de Russell ". Comparando ZF con la teoría de tipos , Alasdair Urquhart escribió que "el sistema de Zermelo tiene la ventaja de no contener ninguna variable tipificada explícitamente, aunque de hecho puede verse como si tuviera una estructura de tipos implícita incorporada, al menos si se incluye el axioma de regularidad. Los detalles de esta tipificación implícita se explican en [Zermelo 1930], y nuevamente en un conocido artículo de George Boolos [Boolos 1971]". ^[2]

Dana Scott  (1974) fue más allá y afirmó que:

La verdad es que sólo hay una forma satisfactoria de evitar las paradojas: a saber, el uso de alguna forma de la teoría de tipos . Ésta estaba en la base de las intuiciones tanto de Russell como de Zermelo. De hecho, la mejor forma de considerar la teoría de Zermelo es como una simplificación y extensión de la de Russell. (Nos referimos a la teoría simple de tipos de Russell, por supuesto). La simplificación consistía en hacer que los tipos fueran acumulativos . De este modo, la mezcla de tipos es más fácil y se evitan repeticiones molestas. Una vez que se permite que los tipos posteriores acumulen a los anteriores, podemos imaginar fácilmente la extensión de los tipos hasta el transfinito; hasta dónde queremos llegar debe quedar necesariamente abierto. Ahora Russell hizo explícitos sus tipos en su notación y Zermelo los dejó implícitos . [énfasis en el original]

En el mismo artículo, Scott muestra que un sistema axiomático basado en las propiedades inherentes de la jerarquía acumulativa resulta ser equivalente a ZF, incluida la regularidad. ^[3]

Historia

El concepto de fundamento y rango de un conjunto fueron introducidos por Dmitry Mirimanoff (1917) cf. Lévy (2002, p. 68) y Hallett (1996, §4.4, esp. p. 186, 188). Mirimanoff llamó a un conjunto x "regular" (en francés: "ordinaire") si cada cadena descendente x ∋ x ₁ ∋ x ₂ ∋ ... es finita. Sin embargo, Mirimanoff no consideró su noción de regularidad (y fundamento) como un axioma que debe ser observado por todos los conjuntos; ^[4] en artículos posteriores Mirimanoff también exploró lo que ahora se llama conjuntos no bien fundados ("extraordinaire" en la terminología de Mirimanoff). ^[5]

Skolem (1923) y von Neumann (1925) señalaron que los conjuntos no bien fundados son superfluos (en la p. 404 de la traducción de van Heijenoort) y en la misma publicación von Neumann da un axioma (p. 412 de la traducción) que excluye algunos, pero no todos, los conjuntos no bien fundados. ^[6] En una publicación posterior, von Neumann (1929, p. 231) dio una versión equivalente pero más compleja del Axioma de Fundación de Clases, cf. Suppes (1972, p. 53) y Lévy (2002, p. 72):

${\displaystyle A\neq \emptyset \rightarrow \exists x\in A\,(x\cap A=\emptyset )}$.

La forma contemporánea y final del axioma se debe a Zermelo (1930).

Regularidad en la presencia de urelementos

Los urelementos son objetos que no son conjuntos, pero que pueden ser elementos de conjuntos. En la teoría de conjuntos ZF, no hay urelementos, pero en otras teorías de conjuntos como ZFA , sí los hay. En estas teorías, el axioma de regularidad debe modificarse. La afirmación " " debe reemplazarse por una afirmación que no esté vacía y no sea un urelemento. Un reemplazo adecuado es , que establece que x está habitado . ${\displaystyle x\neq \emptyset }$ ${\displaystyle x}$ ${\displaystyle (\exists y)[y\in x]}$

Véase también

• Teoría de conjuntos no bien fundada
• El truco de Scott
• Inducción de épsilon

Referencias

1. Rieger 2011, págs. 175, 178.
2. Urquhart 2003, pág. 305.
3. Lévy 2002, pág. 73.
4. Halbeisen 2012, págs. 62–63.
5. Sangiorgi 2011, págs. 17-19, 26.
6. Rieger 2011, pág. 179.

Fuentes

• Bernays, Paul Isaac (1941), "Un sistema de teoría de conjuntos axiomáticos. Parte II", The Journal of Symbolic Logic , 6 (1): 1–17, doi :10.2307/2267281, JSTOR  2267281, S2CID  250344277
• Bernays, Paul Isaac (1954), "Un sistema de teoría de conjuntos axiomáticos. Parte VII" (PDF) , The Journal of Symbolic Logic , 19 (2): 81–96, doi :10.2307/2268864, JSTOR  2268864, S2CID  250351655
• Boolos, George (1971), "La concepción iterativa de conjunto", Journal of Philosophy , 68 (8): 215–231, doi :10.2307/2025204, JSTOR  2025204Reimpreso en Boolos, George (1998), Logic, Logic and Logic , Harvard University Press, págs. 13-29.
• Enderton, Herbert B. (1977), Elementos de la teoría de conjuntos , Academic Press
• Forster, T. (2003), Lógica, inducción y conjuntos , Cambridge University Press
• Halbeisen, Lorenz J. (2012), Teoría de conjuntos combinatorios: con una introducción suave al forzamiento , Springer
• Hallett, Michael (1996) [publicado por primera vez en 1984], Teoría de conjuntos cantoriana y limitación de tamaño , Oxford University Press, ISBN 978-0-19-853283-5
• Jech, Thomas (2003), Teoría de conjuntos: edición del tercer milenio, revisada y ampliada , Springer, ISBN 978-3-540-44085-7
• Kunen, Kenneth (1980), Teoría de conjuntos: una introducción a las pruebas de independencia , Elsevier, ISBN 978-0-444-86839-8
• Lévy, Azriel (2002) [publicado por primera vez en 1979], Teoría básica de conjuntos , Mineola, Nueva York: Dover Publications, ISBN 978-0-486-42079-0
• Mirimanoff, Dmitry (1917), "Les antinomies de Russell et de Burali-Forti et le probleme fondamental de la theorie des ensembles", L'Enseignement Mathématique , 19 : 37–52
• Rathjen, M. (2004), "Predicatividad, circularidad y antifundamento" (PDF) , en Link, Godehard (ed.), Cien años de la paradoja de Russell: matemáticas, lógica, filosofía , Walter de Gruyter, ISBN 978-3-11-019968-0, archivado (PDF) del original el 2022-10-09
• Rieger, Adam (2011), "Paradoja, ZF y el axioma de fundamento" (PDF) , en DeVidi, David; Hallett, Michael; Clark, Peter (eds.), Lógica, matemáticas, filosofía, entusiasmos antiguos. Ensayos en honor a John L. Bell. , The Western Ontario Series in Philosophy of Science, vol. 75, pp. 171–187, CiteSeerX  10.1.1.100.9052 , doi :10.1007/978-94-007-0214-1_9, ISBN 978-94-007-0213-4
• Riegger, L. (1957), "Una contribución a la teoría de conjuntos axiomáticos de Gödel" (PDF) , Revista matemática checoslovaca , 7 (3): 323–357, doi : 10.21136/CMJ.1957.100254
• Sangiorgi, Davide (2011), "Orígenes de la bisimulación y la coinducción", en Sangiorgi, Davide; Rutten, Jan (eds.), Temas avanzados en bisimulación y coinducción , Cambridge University Press
• Scott, Dana Stewart (1974), "Axiomatizing set theory", Teoría axiomática de conjuntos. Actas de simposios sobre matemáticas puras, volumen 13, parte II , págs. 207-214
• Skolem, Thoralf (1923), Teoría de conjuntos axiomatizadosReimpreso en From Frege to Gödel , van Heijenoort, 1967, en traducción al inglés de Stefan Bauer-Mengelberg, págs.
• Suppes, Patrick (1972) [publicado por primera vez en 1960], Teoría de conjuntos axiomáticos , Dover Publications, Inc., ISBN 978-0-486-61630-8
• Urquhart, Alasdair (2003), "La teoría de los tipos", en Griffin, Nicholas (ed.), The Cambridge Companion to Bertrand Russell , Cambridge University Press
• Vaught, Robert L. (2001), Teoría de conjuntos: una introducción (2.ª ed.), Springer, ISBN 978-0-8176-4256-3
• von Neumann, John (1925), "Eine Axiomatisierung der Mengenlehre", Journal für die Reine und Angewandte Mathematik , 154 : 219–240; traducción en van Heijenoort, Jean (1967), De Frege a Gödel: un libro de referencia sobre lógica matemática, 1879-1931 , págs. 393-413
• von Neumann, John (1928), "Über die Definición durch transfinite Induktion und verwandte Fragen der allgemeinen Mengenlehre", Mathematische Annalen , 99 : 373–391, doi :10.1007/BF01459102, S2CID  120784562
• von Neumann, John (1929), "Uber eine Widerspruchfreiheitsfrage in der axiomatischen Mengenlehre", Journal für die Reine und Angewandte Mathematik , 1929 (160): 227–241, doi :10.1515/crll.1929.160.227, S2CID  199545822
• Zermelo, Ernst (1930), "Über Grenzzahlen und Mengenbereiche. Neue Untersuchungen über die Grundlagen der Mengenlehre". (PDF) , Fundamenta Mathematicae , 16 : 29–47, doi : 10.4064/fm-16-1-29-47 , archivado (PDF) desde el original el 9 de octubre de 2022; traducción en Ewald, WB, ed. (1996), De Kant a Hilbert: un libro de consulta sobre los fundamentos de las matemáticas, vol. 2 , Clarendon Press, págs. 1219–33

Enlaces externos

• Axioma de fundación en PlanetMath .
• Conjunto habitado y axioma de fundación en nLab