Axioma de regularidad - Axiom of regularity

En matemáticas , el axioma de regularidad (también conocido como el axioma de fundación ) es un axioma de la teoría de conjuntos Zermelo-Fraenkel que los estados que cada no vacía conjunto A contiene un elemento que es disjunta de A . En la lógica de primer orden , el axioma dice:

${\ Displaystyle \ forall x \, (x \ neq \ varnothing \ rightarrow \ existe 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 revertirse: 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 miembros infinitas descendentes.

El axioma fue introducido por von Neumann (1925) ; fue adoptado en una formulación más cercana a la encontrada en los libros de texto contemporáneos por Zermelo (1930) . Prácticamente 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 probar; y no solo permite que la inducción se realice en conjuntos bien ordenados, sino también en clases adecuadas que son estructuras relacionales bien fundadas , como el ordenamiento lexicográfico en${\ Displaystyle \ {(n, \ alpha) \ mid n \ in \ omega \ land \ alpha {\ text {es un ordinal}} \} \ ,.}$

Dados los otros 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 usarse en lugar del axioma de regularidad en las teorías intuicionistas (aquellas que no aceptan la ley del medio 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 en sí mismos.

Implicaciones elementales de la regularidad

Ningún conjunto es un elemento en sí mismo

Sea A un conjunto y aplique 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 }. Dado que el único elemento de { A } es A , debe ser que A sea ​​disjunto de { A }. Entonces, dado que , no podemos tener A ∈ A (por la definición de disjunto ). ${\ Displaystyle A \ cap \ {A \} = \ varnothing}$

No existe una secuencia descendente infinita de conjuntos

Supongamos, por el contrario, que hay una función , f , sobre los números naturales con f ( n +1) un elemento de f ( n ) para cada n . Defina S = { f ( n ): n un número natural}, el rango de f , que puede verse como un conjunto del esquema de axioma de reemplazo . Aplicando el axioma de regularidad a S , deje B sea un elemento de S , que es disjunta de S . Según 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 es también un elemento de S . Así que f ( k 1) está en la intersección de f ( k ) y S . Esto contradice el hecho de que son conjuntos inconexos. Dado que nuestra suposición condujo a una contradicción, no debe existir tal función, f .

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

Observe que este argumento solo se aplica a funciones f que se pueden representar como conjuntos en contraposición a clases indefinibles. Los conjuntos hereditariamente finitos , 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 en realidad no son números naturales. Son números naturales falsos que son "más grandes" que cualquier número natural real. Este modelo contendrá infinitas secuencias descendentes de elementos. Por ejemplo, suponga que n es un número natural no estándar, luego y , y así sucesivamente. Para cualquier número natural real k , . Esta es una secuencia descendente interminable de elementos. Pero esta secuencia no se puede definir en el modelo y, por lo tanto, no es un conjunto. Por tanto, no se puede probar ninguna contradicción con la regularidad. ${\ Displaystyle (n-1) \ in n}$${\ Displaystyle (n-2) \ in (n-1)}$${\ Displaystyle (nk-1) \ in (nk)}$

Definición teórica de conjuntos más simple del par ordenado

El axioma de regularidad permite definir el par ordenado ( a , b ) como { a , { a , b }}; consulte el par pedido para obtener 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

Esta fue en realidad la forma original del axioma en la axiomatización de von Neumann.

Suponga que x es cualquier conjunto. Sea t el cierre transitivo de { x }. Sea u el subconjunto de t que consta de conjuntos no clasificados. Si u está vacío, entonces x se clasifica y terminamos. De lo contrario, aplique el axioma de regularidad a u para obtener un elemento w de u que sea disjunto de u . Como w está en u , w no está clasificado. w es un subconjunto de t según la definición de cierre transitivo. Dado que w es disjunto de u , todos los elementos de w se clasifican. 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 está clasificado. Entonces, la suposición de que u no estaba vacío debe ser falsa y x debe tener rango. ${\ Displaystyle \ textstyle \ operatorname {rango} (w) = \ cup \ {\ operatorname {rango} (z) +1 \ mid z \ in w \}}$

Por cada dos conjuntos, solo uno puede ser un elemento del otro

Sean X e Y conjuntos. Luego aplique 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 es disjunto de él. Debe ser o bien X o Y . Por la definición de disjunto, entonces, debemos tener o Y no es un elemento de X o viceversa.

El axioma de elección dependiente y sin 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 sobre S por , que es completa por supuesto. Por lo tanto, por el axioma de elección depende, hay una cierta secuencia ( un _n ) en S que satisface un _n Ra _{n + 1} para todos los n en N . Como se trata de una cadena descendente infinita, llegamos a una contradicción y, por tanto, no existe tal S.${\ Displaystyle aRb: \ Leftrightarrow b \ in S \ cap a}$

Regularidad y resto de axiomas ZF (C)

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

También se demostró que el axioma de regularidad es independiente de los otros axiomas de ZF (C), asumiendo que son 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) modelos (o método) de permutación de Rieger-Bernays , que se utilizaron para otras pruebas de independencia para sistemas no bien fundamentados ( Rathjen 2004 , p. 193 y Forster 2003 , pp. 210-212).

Regularidad y paradoja de Russell

La teoría de conjuntos ingenua (el esquema del axioma de la comprensión sin restricciones y el axioma de la extensionalidad ) es inconsistente debido a la paradoja de Russell . En las primeras formalizaciones de conjuntos, los matemáticos y los lógicos han evitado esa contradicción reemplazando el esquema de axioma de comprensión por el esquema de axioma de separación mucho más débil . Sin embargo, este paso por sí solo lleva a teorías de conjuntos que se consideran demasiado débiles. De modo que parte del poder de la comprensión se volvió a agregar a través de los otros axiomas de existencia de la teoría de conjuntos ZF (emparejamiento, unión, conjunto de poderes, reemplazo e infinito) que pueden considerarse casos especiales de comprensión. 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 de axioma 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 tal conjunto universal. Sin embargo, la paradoja de Russell proporciona una prueba de que no existe un "conjunto de todos los conjuntos" utilizando el esquema de axioma de separación solo, sin axiomas adicionales. En particular, ZF sin el axioma de regularidad ya prohíbe tal conjunto universal.

Si una teoría se amplía añadiendo un axioma o axiomas, cualquier consecuencia (posiblemente indeseable) de la teoría original seguirá siendo consecuencia de la teoría ampliada. En particular, si ZF sin regularidad se extiende agregando regularidad para obtener ZF, entonces cualquier contradicción (como la paradoja de Russell) que siguió a la teoría original seguiría en la teoría extendida.

La existencia de átomos de Quine (conjuntos que satisfacen la ecuación de la fórmula x  = { x }, es decir, se tienen ellos 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 fundamentadas permiten conjuntos circulares "seguros", como los átomos de Quine, sin volverse inconsistentes por medio de la paradoja de Russell.

Regularidad, jerarquía acumulativa y tipos

En ZF se puede probar 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 con este axioma omitido). A partir de cualquier modelo que no satisfaga el axioma de regularidad, se puede construir un modelo que lo satisfaga tomando solo conjuntos . ${\ Displaystyle \ bigcup _ {\ alpha} V _ {\ alpha}}$${\ Displaystyle \ bigcup _ {\ alpha} V _ {\ alpha}}$

Herbert Enderton  ( 1977 , p. 206) escribió que "La idea de rango es un 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 la notación de no contener ninguna variable tipada explícitamente, aunque de hecho se puede considerar que tiene una estructura de tipo implícita incorporada, al menos si el axioma de regularidad es Los detalles de esta tipificación implícita se detallan en [Zermelo 1930] , y nuevamente en un conocido artículo de George Boolos [Boolos 1971] ".

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

La verdad es que solo hay una forma satisfactoria de evitar las paradojas: a saber, el uso de alguna forma de teoría de tipos . Eso fue la base de las intuiciones de Russell y Zermelo. De hecho, la mejor manera 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 consistió en hacer que los tipos fueran acumulativos . Así, la mezcla de tipos es más fácil y se evitan las molestas repeticiones. Una vez que se permite que los tipos posteriores acumulen los primeros, entonces podemos imaginar fácilmente la extensión de los tipos a lo transfinito: hasta dónde queremos llegar debe dejarse 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.

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, especialmente p. 186, 188). Mirimanoff llamó a un conjunto x "regular" (francés: "ordinaire") si cada cadena descendente x ∋ x ₁ ∋ x ₂ ∋ ... es finita. Mirimanoff, sin embargo, no consideró su noción de regularidad (y fundamento) como un axioma a ser observado por todos los conjuntos; en artículos posteriores, Mirimanoff también exploró lo que ahora se denominan conjuntos no bien fundados ("extraordinarios" en la terminología de Mirimanoff).

Skolem (1923) y von Neumann (1925) señalaron que los conjuntos no bien fundados son superfluos (en la p. 404 en la traducción de van Heijenoort ) y en la misma publicación von Neumann da un axioma (p. 412 en la traducción) que excluye algunos, pero no todos, conjuntos no bien fundamentados. En una publicación posterior, von Neumann (1928) dio el siguiente axioma (traducido en notación moderna por A. Rieger):

${\ Displaystyle \ forall x \, (x \ neq \ emptyset \ rightarrow \ existe y \ in x \, (y \ cap x = \ emptyset))}$.

Regularidad en presencia de urelementos

Urelements son objetos que no son conjuntos, pero que pueden ser elementos de conjuntos. En la teoría de conjuntos de ZF, no hay elementos ureicos, pero en algunas otras teorías de conjuntos, como ZFA , sí los hay. En estas teorías, el axioma de regularidad debe modificarse. La declaración " " debe ser reemplazada por una declaración que no esté vacía y no sea un elemento. Un reemplazo adecuado es , que establece que x está habitado . ${\ Displaystyle x \ neq \ emptyset}$${\ Displaystyle x}$${\ Displaystyle (\ existe y) [y \ en x]}$

Ver también

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

Referencias

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
• 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
• Boolos, George (1971), "La concepción iterativa del 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 suave introducción 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: La 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, D. (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), "Predicativity, Circularity, and Anti-Foundation" (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
• Rieger, Adam (2011), "Paradox, ZF, and the Axiom of Foundation" (PDF) , en DeVidi, David; Hallett, Michael; Clark, Peter (eds.), Lógica, Matemáticas, Filosofía, Vintage Enthusiasms. Ensayos en honor a John L. Bell. , The Western Ontario Series in Philosophy of Science, 75 , págs. 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) , Czechoslovak Mathematical Journal , 7 (3): 323–357, doi : 10.21136 / CMJ.1957.100254
• Sangiorgi, Davide (2011), "Orígenes de la bisimulación y coinducción", en Sangiorgi, Davide; Rutten, Jan (eds.), Temas avanzados en bisimulación y coinducción , Cambridge University Press
• Scott, Dana Stewart (1974), "Teoría de conjuntos axiomatizante", Teoría de conjuntos axiomática. Actas de Symposia in Pure Mathematics Volumen 13, Parte II , págs. 207–214
• Skolem, Thoralf (1923), teoría de conjuntos axiomatizadaReimpreso en From Frege to Gödel , van Heijenoort, 1967, en traducción al inglés de Stefan Bauer-Mengelberg, págs. 291–301.
• Urquhart, Alasdair (2003), "The Theory of Types", en Griffin, Nicholas (ed.), The Cambridge Companion to Bertrand Russell , Cambridge University Press
• Vaught, Robert L. (2001), Teoría de conjuntos: una introducción (2a ed.), Springer, ISBN 978-0-8176-4256-3
• von Neumann, John (1925), "Eine axiomatiserung der Mengenlehre", Journal für die Reine und Angewandte Mathematik , 154 : 219-240; traducción en van Heijenoort, Jean (1967), From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 , págs. 393–413
• von Neumann, John (1928), "Über die Definition 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; traducción en Ewald, WB, ed. (1996), From Kant to Hilbert: A Source Book in the Foundations of Mathematics 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