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 A no vacío contiene un elemento disjunto de A. En lógica de primer orden , el axioma dice:

${\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 _(an ) tal que a i ₊₁ 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 se puede revertir: si no existen tales secuencias infinitas, entonces el axioma de regularidad es verdadero. Por tanto, en este contexto el axioma de regularidad es equivalente a la frase de que no hay cadenas de membresía infinitas descendentes.

El axioma es el aporte 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 de 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 demostrar; y no sólo permite realizar la inducción sobre conjuntos bien ordenados sino también sobre clases propias que son estructuras relacionales bien fundadas, como el ordenamiento lexicográfico de ${\displaystyle \{(n,\alpha )\mid n\in \omega \land \alpha {\text{ is an ordinal }}\}\,.}$

Dados 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 usarse en lugar del axioma de regularidad en las teorías intuicionistas (aquellas que no aceptan la ley del tercero 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 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 (según la definición de disjunto ). ${\displaystyle A\cap \{A\}=\varnothing }$

No existe una secuencia descendente infinita de conjuntos.

Supongamos, 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 . Defina S = { f ( n ): n un número natural}, el rango de f , que puede verse como un conjunto del esquema axioma de reemplazo . Aplicando el axioma de regularidad a S , sea B un elemento de S que es disjunto 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 también es un elemento de S . Entonces f ( k +1) está en la intersección de f ( k ) y S. Esto contradice el hecho de que son conjuntos disjuntos. Dado que nuestra suposición conducía a una contradicción, no debe existir tal función, f .

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

Observe que este argumento sólo se aplica a funciones f que pueden representarse como conjuntos en lugar de 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 ^{[ dudoso ]} . Son números naturales "falsos" que son "más grandes" que cualquier número natural real. Este modelo contendrá infinitas secuencias descendentes de elementos. ^{[ se necesita aclaración ]} 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 se puede definir en el modelo y, por tanto, no es un conjunto. Por 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 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 ordenado para obtener detalles. Esta definición elimina un par de llaves de la definición canónica de Kuratowski ( a , b ) = {{ a },{ a , b }}.

Todo conjunto tiene un rango ordinal.

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

Supongamos que x es cualquier conjunto. Sea t la clausura transitiva 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 . Dado que 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 , cada elemento de w está clasificado. Aplicando los axiomas de sustitución y unión para combinar los rangos de los elementos de w , obtenemos un rango ordinal para w , es decir . Esto contradice la conclusión de que w no está clasificado. Entonces, la suposición de que u no estaba vacía debe ser falsa y x debe tener rango. ${\displaystyle \textstyle \operatorname {rank} (w)=\cup \{\operatorname {rank} (z)+1\mid z\in w\}}$

De cada dos conjuntos, sólo uno puede ser 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 sea disjunto de él. Debe ser X o Y. Entonces, según la definición de disjunto, debemos tener que Y no es un elemento de X o viceversa.

El axioma de elección dependiente y de no 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 completa por suposición. Por lo tanto, según 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 tanto, no existe tal S. ${\displaystyle aRb:\Leftrightarrow b\in S\cap a}$

Regularidad y resto de axiomas de 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 lo es. 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 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 involucra (y condujo al estudio de) los 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 ingenua de conjuntos (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 los lógicos han evitado esa contradicción reemplazando el esquema axiomático de comprensión por el esquema axiomático de separación, mucho más débil . Sin embargo, este solo paso lleva a teorías de conjuntos que se consideran demasiado débiles. ^{[ aclaración necesaria ] [ cita necesaria ]} Entonces, 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 de potencias, 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 dicho conjunto universal. Sin embargo, la paradoja de Russell demuestra que no existe un "conjunto de todos los conjuntos" utilizando únicamente el esquema del axioma de separación, 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 uno o más axiomas, entonces 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 se derivara de la teoría original seguiría en la teoría extendida.

La existencia de átomos de Quine (conjuntos que satisfacen la fórmula ecuación x  = { x }, es decir, que se tienen a sí mismos como ú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. ^[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 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 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 notación de no contener variables tipificadas explícitamente, aunque de hecho puede verse como si tuviera una estructura de tipos 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]". ^[2]

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

La verdad es que sólo hay una manera satisfactoria de evitar las paradojas: a saber, el uso de alguna forma de la teoría de tipos . Esta 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. ( Por supuesto, nos referimos a la teoría simple de tipos de Russell.) La simplificación consistió en hacer que los tipos fueran acumulativos . De este modo es más fácil mezclar tipos y se evitan molestas repeticiones. Una vez que a los tipos posteriores se les permite acumular a los anteriores, podemos imaginar fácilmente extender los tipos hasta lo transfinito; necesariamente debe dejarse abierto hasta dónde queremos llegar. 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 equivalente a ZF, incluida la regularidad. ^[3]

Historia

Los conceptos 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 toda cadena descendente x ∋ x ₁ ∋ x ₂ ∋ ... es finita. Mirimanoff, sin embargo, no consideró su noción de regularidad (y fundamento) como un axioma que debía observarse en todos los conjuntos; ^[4] en artículos posteriores, Mirimanoff también exploró lo que ahora se llama conjuntos no bien fundados ("extraordinarios" en la terminología de Mirimanoff). ^[5]

Skolem (1923) y von Neumann (1925) señalaron que los conjuntos no bien fundamentados 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. ^[6] En una publicación posterior, von Neumann (1929, p. 231) dio una versión equivalente pero más compleja del axioma de fundamento de clase, 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 definitiva del axioma se debe a Zermelo (1930).

Regularidad en presencia de urelementos.

Los elementos ur 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 algunas otras teorías de conjuntos, como ZFA , sí los hay. En estas teorías es necesario modificar el axioma de regularidad. La declaración " " debe reemplazarse con una declaració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]}$

Ver también

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

Referencias

1. Rieger 2011, págs.175, 178.
2. Urquhart 2003, pag. 305.
3. Levy 2002, pag. 73.
4. Halbeisen 2012, págs. 62–63.
5. Sangiorgi 2011, págs. 17-19, 26.
6. Rieger 2011, pag. 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 combinatoria de conjuntos: 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: 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 antifundación" (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) desde el original el 9 de octubre de 2022.
• Rieger, Adam (2011), "Paradoja, ZF y el axioma de fundación" (PDF) , en DeVidi, David; Hallett, Michael; Clark, Peter (eds.), Lógica, Matemáticas, Filosofía, Entusiasmos vintage. Ensayos en honor a John L. Bell. , Serie Western Ontario en Filosofía de la Ciencia, vol. 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 axiomática de conjuntos de Gödel" (PDF) , Checoslovak Mathematical Journal , 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), "Teoría de conjuntos axiomatizante", Teoría de conjuntos axiomática. Actas de simposios sobre matemáticas puras, 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.
• Suppes, Patrick (1972) [publicado por primera vez en 1960], Teoría de conjuntos axiomática , 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: 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 consulta en lógica matemática, 1879-1931 , págs.
• 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 fundamento en PlanetMath .
• Conjunto habitado y el axioma de fundación en nLab