Axioma de regularidad

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 dice:

${displaystyle forall x,(xneq varnothing rightarrow exists y(yin x land ycap 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 es un elemento de a_i para todos los i. Con el axioma de elección dependiente (que es una forma debilitada del axioma de elección), este resultado se puede invertir: si no hay 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 fue introducido por 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). Prácticamente todos los resultados en las ramas de las matemáticas basadas en la teoría de conjunto mantienen incluso en la ausencia de regularidad; véase el capítulo 3 de Kunen (1980). Sin embargo, la regularidad hace que algunas propiedades de ordinal sean más fáciles de probar; y no sólo permite que la inducción se haga en conjuntos bien ordenados sino también en las clases adecuadas que son estructuras relacionales bien fundadas, como el orden lexicográfico en ${displaystyle {(n,alpha)mid nin omega land alpha {text{ is an 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 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 de sí mismo

Vamos A ser un conjunto, y aplicar el axioma de la regularidad a {A}, que es un conjunto por el axioma de pareado. Vemos que debe haber un elemento de {A} que está deshonrado de {}A}. Desde el único elemento de {A} es A, debe ser que A está deshonrado de {}A}. Así que, desde ${displaystyle Acap {A}=varnothing }$, no podemos haber A ▪ A (por la definición de disjoint).

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) an 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 a partir del esquema del axioma 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< /i>. Sin embargo, sabemos 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< /i>. Esto contradice el hecho de que son conjuntos disjuntos. Dado que nuestra suposición llevó a una contradicción, no debe existir tal función, 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.

Observe que este argumento sólo se aplica a las funciones f que pueden ser representados como conjuntos en lugar de clases indefinibles. Los sets hereditariamente finitos, V_⋅, satisfacer el axioma de la regularidad (y todos los demás axiomas de ZFC excepto el axioma del infinito). Así que si uno forma un ultrapoder no-trivial de V_⋅, entonces también satisfará el axioma de la 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 no son números realmente 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, supongamos n es un número natural no estándar, entonces ${displaystyle (n-1)in n}$ y ${displaystyle (n-2)in (n-1)}$, y así sucesivamente. Para cualquier número natural real k, ${displaystyle (n-k-1)in (n-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. Así que no se puede probar ninguna contradicción con la regularidad.

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 información específica. Esta definición elimina un par de llaves de la definición canónica de Kuratowski (a,b) = {{a},{a< /i>,b}}.

Cada conjunto tiene un rango ordinal

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

Suppose x es cualquier juego. Vamos t ser el cierre transitivo de {x}. Vamos u ser el subconjunto de t que consiste en conjuntos sin rasgar. Si u está vacío, entonces x está clasificado y hemos terminado. De lo contrario, aplicar el axioma de la regularidad a u para conseguir un elemento w de u que está descomunada u. Desde w está dentro u, w está desencadenado. w es un subconjunto de t por definición de cierre transitorio. Desde w está descompuesto u, cada elemento de w está clasificado. Aplicar los axiomas de reemplazo y unión para combinar las filas de los elementos w, tenemos un rango ordinal para w, a wit ${displaystyle textstyle operatorname {rank} (w)=cup {operatorname {rank} (z)+1mid zin w}}$. Esto contradice la conclusión de que w está desencadenado. Así que la suposición de que u no era vacía debe ser falsa y x Debe tener rango.

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

Sean conjuntos X e Y. 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 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 la ausencia de una secuencia descendente infinita de conjuntos implica regularidad

Que el conjunto no vacío S ser un contra-ejemplo al axioma de la regularidad; es decir, cada elemento de S tiene una intersección no vacía con S. Definimos una relación binaria R on S por ${displaystyle aRb:Leftrightarrow bin Scap a}$, que está completo por suposición. Así, por el axioma de la elección dependiente, hay cierta secuencia (a_nEn S satisfacción a_nRa_n+1 para todos n dentro N. Como esta es una cadena descendente infinita, llegamos a una contradicción y así, no S existe.

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 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 otros 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) modelos (o métodos) de permutación de Rieger-Bernays, que se usaron para otras pruebas de independencia para sistemas no bien fundamentados (Rathjen 2004, p. 193 y Forster 2003, pp. 210–212).

La regularidad y la paradoja de Russell

La teoría de conjuntos ingenua (el esquema de axioma de comprensión sin restricciones 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 con el esquema axiomático de separación mucho más débil. Sin embargo, este paso por sí solo nos lleva a teorías de conjuntos que se consideran demasiado débiles. Entonces, parte del poder de 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 potencia, 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 axioma de esquema 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 produce una prueba de que no existe un 'conjunto de todos los conjuntos'. usando el esquema del axioma de separación solo, sin ningún axioma adicional. En particular, ZF sin el axioma de regularidad ya prohíbe tal conjunto universal.

Si una teoría se amplía agregando un axioma o axiomas, cualquier consecuencia (posiblemente indeseable) de la teoría original sigue siendo una 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 deriva 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, se tienen a sí mismos como únicos elementos) es consistente con la teoría obtenida por eliminando el axioma de regularidad de ZFC. Varias teorías de conjuntos no bien fundamentadas permiten que los datos "seguros" conjuntos circulares, 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 ${displaystyle bigcup _{alpha #V_{alpha }$, llamado el universo Von Neumann, es igual a la clase de todos los conjuntos. Esta declaración equivale incluso al axioma de la regularidad (si trabajamos en ZF con este axioma omitido). De cualquier modelo que no satisfaga el axioma de la regularidad, un modelo que satisface puede ser construido tomando sólo conjuntos en ${displaystyle bigcup _{alpha #V_{alpha }$.

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

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

La verdad es que sólo hay una manera satisfactoria de evitar las paradojas: es decir, el uso de alguna forma de la teoría de tipos. Eso fue sobre 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 Russell. (Se refiere a Russell's simple teoría de tipos, por supuesto.) La simplificación era hacer los tipos acumulativo. Así la mezcla de tipos es más fácil y se evitan repeticiones molestosas. Una vez que los tipos posteriores se permiten acumular los anteriores, entonces podemos imaginar fácilmente Ampliación los tipos en el transfinito - sólo hasta dónde queremos ir debe necesariamente ser dejado abierto. Ahora Russell hizo sus tipos explícita en su notación y Zermelo los dejó implícita. [emfasis en 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

Dmitry Mirimanoff (1917) introdujo el concepto de bien fundamentado y el rango de un conjunto, 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 finito. Sin embargo, Mirimanoff no consideró su noción de regularidad (y fundamentación) 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ágina 404 de 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 fundados. En una publicación posterior, von Neumann (1928) dio el siguiente axioma (traducido en notación moderna por A. Rieger):

${displaystyle forall x,(xneq emptyset rightarrow exists yin x,(ycap x=emptyset)}$.

Regularidad en presencia de urelementos

Los elementos son objetos que no son conjuntos, pero que pueden ser elementos de conjuntos. En la teoría del conjunto ZF, no hay urelementos, pero en algunas otras teorías de conjunto como ZFA, hay. En estas teorías, el axioma de la regularidad debe ser modificado. La declaración "${displaystyle xneq emptyset }$" necesita ser reemplazado por una declaración que ${displaystyle x}$ no está vacío y no es un urelement. Un reemplazo adecuado es ${displaystyle (exists y)[yin x]}$, que dice que x está habitado.