Esquema axiomático de reemplazo

En la teoría de conjuntos, el esquema de reemplazo del axioma es un esquema de axiomas en la teoría de conjuntos de Zermelo-Fraenkel (ZF) que afirma que la imagen de cualquier conjunto bajo cualquier mapeo definible también es un conjunto. Es necesario para la construcción de ciertos conjuntos infinitos en ZF.

El esquema de axioma está motivado por la idea de que si una clase es un conjunto depende solo de la cardinalidad de la clase, no del rango de sus elementos. Por lo tanto, si una clase es "lo suficientemente pequeña" ser un conjunto, y hay una sobreyección de esa clase a una segunda clase, el axioma establece que la segunda clase también es un conjunto. Sin embargo, debido a que ZFC solo habla de conjuntos, no de clases propias, el esquema se establece solo para sobreyecciones definibles, que se identifican con sus fórmulas definitorias.

Declaración

Esquema axioma de reemplazo: la imagen F[A]{displaystyle F[A] del conjunto de dominio A{displaystyle A} bajo la función de clase definible F{displaystyle F} es en sí mismo un conjunto, B{displaystyle B}.

Suppose P{displaystyle P} es una relación binaria definible (que puede ser una clase adecuada) tal que para cada conjunto x{displaystyle x} hay un conjunto único Sí.{displaystyle y} tales que P()x,Sí.){displaystyle P(x,y)} sostiene. Hay una función definible correspondiente FP{displaystyle F_{P}, donde FP()x)=Sí.{displaystyle F_{P}(x)=y} si P()x,Sí.){displaystyle P(x,y)}. Considere la clase (posiblemente apropiada) B{displaystyle B} define tal que para cada conjunto Sí.{displaystyle y}, Sí.▪ ▪ B{displaystyle yin B} si y sólo si hay x▪ ▪ A{displaystyle xin A} con FP()x)=Sí.{displaystyle F_{P}(x)=y}. B{displaystyle B} se llama la imagen A{displaystyle A} menores FP{displaystyle F_{P}, y denotado FP[A]{displaystyle F_{P}[A] o (notación de configuración) {}FP()x):x▪ ▪ A}{displaystyle {F_{P}(x):xin A}.

El axiom esquema de reemplazo dice que si F{displaystyle F} es una función de clase definible, como arriba, y A{displaystyle A} es cualquier conjunto, entonces la imagen F[A]{displaystyle F[A] es también un juego. Esto se puede ver como un principio de la pequeñez: el axioma afirma que si A{displaystyle A} es lo suficientemente pequeño para ser un conjunto, entonces F[A]{displaystyle F[A] también es lo suficientemente pequeño para ser un conjunto. Está implicado por el axioma más fuerte de la limitación del tamaño.

Debido a que es imposible cuantificar sobre funciones definibles en la lógica de primer orden, se incluye una instancia del esquema para cada fórmula φ φ {displaystyle phi } en el lenguaje de la teoría de conjuntos con variables libres entre w1,...... ,wn,A,x,Sí.{displaystyle A,x,y; pero B{displaystyle B} no es libre en φ φ {displaystyle phi }. En el lenguaje formal de la teoría del conjunto, el esquema del axioma es:

О О w1,...... ,wnО О A()[О О x▪ ▪ A∃ ∃ !Sí.φ φ ()x,Sí.,w1,...... ,wn,A)]⟹ ⟹ ∃ ∃ BО О Sí.[Sí.▪ ▪ B.. ∃ ∃ x▪ ▪ Aφ φ ()x,Sí.,w1,...... ,wn,A)]){displaystyle {begin{aligned}forall w_{1},ldotsw_{n},forall A,([forall xin A limit,exists !y,phi (x,y,w_{1},ldotsw_{n},A)] Longrightarrow exists B,for all y,[yin BLeftrightarrow exists xin A,phi (x,y,w_{1},ldotsw_{n},A)end{aligned}}}

Para el significado de ∃ ∃ !{displaystyle exists!}, ver la cuantificación de singularidad.

Para claridad, en el caso de no variables wi{displaystyle ¿Qué?, esto simplifica:

О О A()[О О x▪ ▪ A∃ ∃ !Sí.φ φ ()x,Sí.,A)]⟹ ⟹ ∃ ∃ BО О Sí.[Sí.▪ ▪ B.. ∃ ∃ x▪ ▪ Aφ φ ()x,Sí.,A)]){displaystyle {begin{aligned}forall A,([forall xin A golpe,exists !y,phi (x,y,A)] Longrightarrow exists B,for all y,[yin BLeftrightarrow exists xin A,phi (x,y,A)])end{aligned}}

Así cada vez φ φ {displaystyle phi } especifica un único x{displaystyle x}-a-Sí.{displaystyle y} correspondencia, similar a una función F{displaystyle F} on A{displaystyle A}, entonces todo Sí.{displaystyle y} alcanzado de esta manera se puede recoger en un conjunto B{displaystyle B}, similar a F[A]{displaystyle F[A].

Aplicaciones

El esquema del axioma de reemplazo no es necesario para las demostraciones de la mayoría de los teoremas de las matemáticas ordinarias. De hecho, la teoría de conjuntos de Zermelo (Z) ya puede interpretar la aritmética de segundo orden y gran parte de la teoría de tipos en tipos finitos, que a su vez son suficientes para formalizar la mayor parte de las matemáticas. Aunque el esquema de axioma de reemplazo es un axioma estándar en la teoría de conjuntos en la actualidad, a menudo se omite de los sistemas de teoría de tipos y sistemas de base en la teoría de topos.

De todos modos, el esquema del axioma aumenta drásticamente la fuerza de ZF, tanto en términos de los teoremas que puede probar (por ejemplo, los conjuntos que se demuestra que existen) como en términos de su fuerza de consistencia teórica de prueba, en comparación con Z A continuación se presentan algunos ejemplos importantes:

• Utilizando la definición moderna debida a von Neumann, demostrando la existencia de cualquier ordinal límite mayor que ω requiere el axioma de reemplazo. El número ordinal ω·2 = ω + ω es el primero de estos ordinal. El axioma del infinito afirma la existencia de un conjunto infinito ω = {0, 1, 2,...}. Se puede esperar definir ω·2 como unión de la secuencia {ω, ω + 1, ω + 2,...}. Sin embargo, tales clases arbitrarias de ordinals no necesitan ser conjuntos - por ejemplo, la clase de todos los ordinals no es un conjunto. El reemplazo ahora permite reemplazar cada número finito n en ω con el correspondiente n, y así garantiza que esta clase es un conjunto. Como aclaración, note que uno puede fácilmente construir un conjunto bien ordenado que es isomorfo a ω·2 sin recurrir a la sustitución – simplemente tomar la unión descomunal de dos copias de ω, con la segunda copia mayor que la primera – pero que esto no es un ordinal ya que no está totalmente ordenado por la inclusión.
• Los ordinales más grandes dependen menos directamente del reemplazo. Por ejemplo, ω₁, el primer ordinal incontable, se puede construir de la siguiente manera: el conjunto de órdenes bien contables existe como un subconjunto de P()N× × N){displaystyle P({mhmhb {N}times {mathbb {N}}} por separación y potencia (una relación A es un subconjunto de A× × A{displaystyle Atimes A}, y así un elemento del sistema de energía P()A× × A){displaystyle P(Atimes A)}. Un conjunto de relaciones es, pues, un subconjunto P()A× × A){displaystyle P(Atimes A)})). Reemplazar cada conjunto bien ordenado con su ordinal. Este es el conjunto de ordinales contables ω₁, que se puede demostrar que es incontable. La construcción utiliza el reemplazo dos veces; una vez para asegurar una asignación ordinal para cada conjunto bien ordenado y otra vez para reemplazar los conjuntos bien ordenados por sus ordinals. Este es un caso especial del resultado del número de Hartogs, y el caso general se puede probar de forma similar.
• A la luz de lo anterior, la existencia de una asignación de un ordinal a cada conjunto bien ordenado requiere también sustitución. Del mismo modo, la asignación cardenal von Neumann que asigna un número cardenal a cada conjunto requiere sustitución, así como el axioma de elección.
• Para conjuntos de tuples recurrentemente definidos como An=An− − 1× × A{displaystyle A^{n}=A^{n-1}times A} y para grandes A{displaystyle A}, el conjunto {}An▪ ▪ n▪ ▪ N}{displaystyle # {fn}mid nnnncH00\fnfncHFF}mnnnnnn\\cH00\\\\\cHFF}mm\cH00\\\cH\\\\\\cH\\\\\\\\\\\\\\\\cH3cH\\\cH3\\\\\cH\\\\\\\\\\\\\\\\\\\\\\\\cH3\\\\\\\\cH\\\cHFF}\\\\cHHH {N} tiene demasiado alto de un rango para que su existencia sea provable de la teoría de conjunto con sólo el axioma del sistema de poder, elección y sin reemplazo.
• Del mismo modo, Harvey Friedman mostró que el reemplazo es necesario para demostrar que los conjuntos de Borel están determinados. El resultado comprobado es el teorema de determinación de Donald A. Martin.
• ZF con reemplazo demuestra la consistencia de Z, como el conjunto V_ω·2 es un modelo de Z cuya existencia se puede probar en ZF. El número cardenal א א ⋅ ⋅ {displaystyle aleph _{omega } es el primero que se puede demostrar que existe en ZF pero no en Z. Para la aclaración, tenga en cuenta que el segundo teorema de incomplesión de Gödel muestra que cada una de estas teorías contiene una frase, "expresando" la propia consistencia de la teoría, que es inprovable en esa teoría, si esa teoría es consistente - este resultado se expresa a menudo flojo como la afirmación de que ninguna de estas teorías puede demostrar su propia consistencia, si es consistente.

Relación con otros esquemas de axiomas

Colección

Esquema de colección Axiom: la imagen f[A]{displaystyle f[A]} del conjunto de dominio A{displaystyle A} bajo la función de clase definible f{displaystyle f} cae dentro de un conjunto B{displaystyle B}.

El esquema axiomático de colección está estrechamente relacionado y con frecuencia se confunde con el esquema axiomático de reemplazo. Sobre el resto de los axiomas ZF, es equivalente al esquema del axioma de reemplazo. El axioma de colección es más fuerte que el reemplazo en ausencia del axioma del conjunto de potencias o su contraparte constructiva de ZF pero más débil en el marco de IZF, que carece de la ley del tercero excluido.

Mientras que el reemplazo se puede leer para decir que la imagen de una función es un conjunto, la colección habla de imágenes de relaciones y luego simplemente dice que una superclase de la imagen de la relación es un conjunto. En otras palabras, el conjunto resultante B{displaystyle B} no tiene requisito de mínimaidad, es decir, esta variante también carece del requisito de singularidad φ φ {displaystyle phi }. Es decir, la relación definida por φ φ {displaystyle phi } no es necesario ser una función —algunos x▪ ▪ A{displaystyle xin A} puede corresponder a muchos Sí.{displaystyle y}Está dentro B{displaystyle B}. En este caso, el conjunto de la imagen B{displaystyle B} cuya existencia se afirma debe contener al menos uno de esos Sí.{displaystyle y} para cada uno x{displaystyle x} en el conjunto original, sin garantía de que sólo contendrá uno.

Supongamos que las variables libres φ φ {displaystyle phi } entre w1,...... ,wn,x,Sí.{displaystyle ¿Qué?; pero tampoco A{displaystyle A} ni B{displaystyle B} está libre en φ φ {displaystyle phi }. Entonces el esquema del axioma es:

О О w1,...... ,wn[()О О x∃ ∃ Sí.φ φ ()x,Sí.,w1,...... ,wn))⇒ ⇒ О О A∃ ∃ BО О x▪ ▪ A∃ ∃ Sí.▪ ▪ Bφ φ ()x,Sí.,w1,...... ,wn)]{displaystyle forall w_{1},ldotsw_{n},[(toall x,exists ,yphi (x,y,w_{1},ldotsw_{n}) Rightarrow forall A,exists B,forall xin A,exists yin B,phi (x,y,w_{1},ldotsw_{n}]

El esquema axiom a veces se declara sin restricciones previas (aparte de B{displaystyle B} no ocurre libre en φ φ {displaystyle phi }En el predicado, φ φ {displaystyle phi }:

О О w1,...... ,wnО О A∃ ∃ BО О x▪ ▪ A[∃ ∃ Sí.φ φ ()x,Sí.,w1,...... ,wn)⇒ ⇒ ∃ ∃ Sí.▪ ▪ Bφ φ ()x,Sí.,w1,...... ,wn)]{displaystyle forall w_{1},ldotsw_{n},forall A,exists B,forall xin A,[exists yphi (x,y,w_{1},ldotsw_{n})Rightarrow exists yin B,phi (x,y,w_{1},ldotsw_{n}]]}

En este caso, puede haber elementos x{displaystyle x} dentro A{displaystyle A} que no están asociados a ningún otro conjunto por φ φ {displaystyle phi }. Sin embargo, el esquema de axioma como se indica requiere que, si un elemento x{displaystyle x} de A{displaystyle A} se asocia con al menos un conjunto Sí.{displaystyle y}, entonces el conjunto de la imagen B{displaystyle B} contendrá al menos uno de esos Sí.{displaystyle y}. El esquema de axioma resultante también se llama axiom esquema de unión.

Separación

El esquema de axioma de separación, el otro esquema de axioma en ZFC, está implícito en el esquema de axioma de reemplazo y el axioma de conjunto vacío. Recuerde que el esquema del axioma de separación incluye

О О A∃ ∃ BО О C()C▪ ▪ B.. [C▪ ▪ A∧ ∧ Silencio Silencio ()C)]){displaystyle forall A,exists B,forall C,(Cin BLeftrightarrow [Cin Aland theta (C)]}

para cada fórmula Silencio Silencio {displaystyle theta } en el lenguaje de la teoría de conjunto en el cual B{displaystyle B} no es libre.

La prueba es la siguiente. Empieza con una fórmula Silencio Silencio ()C){displaystyle theta (C)} que no menciona B{displaystyle B}, y un conjunto A{displaystyle A}. Si no hay elemento E{displaystyle E} de A{displaystyle A} satisfizo Silencio Silencio ()E){displaystyle theta (E)} entonces el set B{displaystyle B} deseada por la instancia pertinente del esquema axiom de separación es el conjunto vacío. De lo contrario, elegir un fijo E{displaystyle E} dentro A{displaystyle A} tales que Silencio Silencio ()E){displaystyle theta (E)} sostiene. Define una función de clase F{displaystyle F} tal que, para cualquier elemento D{displaystyle D}, F()D)=D{displaystyle F(D)=D} si Silencio Silencio ()D){displaystyle theta (D)} tenencias y F()D)=E{displaystyle F(D)=E} si Silencio Silencio ()D){displaystyle theta (D)} es falso. Entonces la imagen de A{displaystyle A} menores F{displaystyle F}, es decir, el set B=F.A:={}F()x):x▪ ▪ A}=A∩ ∩ {}x:Silencio Silencio ()x)}{displaystyle B=F'A:={F(x):xin A}=Acap {x:theta (x)}}, existe (por el axioma del reemplazo) y es precisamente el conjunto B{displaystyle B} requerido para el axioma de separación.

Este resultado muestra que es posible axiomatizar ZFC con un solo esquema de axioma infinito. Debido a que se requiere al menos uno de esos esquemas infinitos (ZFC no es finitamente axiomatizable), esto muestra que el esquema de axioma de reemplazo puede presentarse como el único esquema de axioma infinito en ZFC si se desea. Debido a que el esquema del axioma de separación no es independiente, a veces se omite de las declaraciones contemporáneas de los axiomas de Zermelo-Fraenkel.

Sin embargo, la separación sigue siendo importante para uso en fragmentos de ZFC, debido a consideraciones históricas, y para comparación con axiomatizaciones alternativas de la teoría de conjuntos. Una formulación de la teoría de conjuntos que no incluya el axioma del reemplazo probablemente incluirá alguna forma del axioma de la separación, para asegurar que sus modelos contengan una colección suficientemente rica de conjuntos. En el estudio de modelos de teoría de conjuntos, a veces es útil considerar modelos de ZFC sin reemplazo, como los modelos Vδ δ {displaystyle V_{delta } en la jerarquía de von Neumann.

La prueba anterior utiliza la ley del medio excluido asumiendo que si A{displaystyle A} es no vacío entonces debe contener un elemento (en la lógica intuitiva, un conjunto es "vacío" si no contiene un elemento, y "no vacía" es la negación formal de esto, que es más débil que "tiene un elemento"). El axioma de separación está incluido en la teoría de conjuntos intuitionistas.

Historia

El esquema del axioma de reemplazo no formaba parte de la axiomatización de la teoría de conjuntos (Z) de Ernst Zermelo en 1908. Existía alguna aproximación informal a él en las obras inéditas de Cantor, y apareció de nuevo informalmente en Mirimanoff (1917).

Abraham Fraenkel, entre 1939 y 1949

Thoralf Skolem, en la década de 1930

Su publicación por Abraham Fraenkel en 1922 es lo que convierte a la teoría de conjuntos moderna Zermelo-Fraenkel en teoría de conjuntos (ZFC). El axioma fue descubierto y anunciado de forma independiente por Thoralf Skolem más tarde ese mismo año (y publicado en 1923). El propio Zermelo incorporó el axioma de Fraenkel en su sistema revisado que publicó en 1930, que también incluía como nuevo axioma el axioma de fundamento de von Neumann. Aunque es la versión de primer orden de Skolem de la lista de axiomas que usamos hoy, por lo general no recibe crédito ya que cada axioma individual fue desarrollado anteriormente por Zermelo o Fraenkel. La frase “teoría de conjuntos de Zermelo-Fraenkel” fue utilizada por primera vez en forma impresa por von Neumann en 1928.

Zermelo y Fraenkel se habían escrito mucho en 1921; el axioma de reemplazo fue un tema importante de este intercambio. Fraenkel inició correspondencia con Zermelo en algún momento de marzo de 1921. Sin embargo, sus cartas anteriores a la fechada el 6 de mayo de 1921 se han perdido. Zermelo admitió por primera vez una brecha en su sistema en una respuesta a Fraenkel fechada el 9 de mayo de 1921. El 10 de julio de 1921, Fraenkel completó y envió para su publicación un artículo (publicado en 1922) que describía que su axioma permitía reemplazos arbitrarios: " Si M es un conjunto y cada elemento de M se reemplaza por [un conjunto o un urelement], entonces M vuelve a convertirse en un conjunto&" (completado entre paréntesis y traducción de Ebbinghaus). La publicación de Fraenkel de 1922 agradeció a Zermelo por sus útiles argumentos. Antes de esta publicación, Fraenkel anunció públicamente su nuevo axioma en una reunión de la Sociedad Matemática Alemana celebrada en Jena el 22 de septiembre de 1921. Zermelo estuvo presente en esta reunión; en la discusión que siguió a la charla de Fraenkel, aceptó el axioma de reemplazo en términos generales, pero expresó reservas con respecto a su alcance.

Thoralf Skolem hizo público su descubrimiento de la brecha en el sistema de Zermelo (la misma brecha que había encontrado Fraenkel) en una charla que dio el 6 de julio de 1922 en el 5º Congreso de Matemáticos Escandinavos, que se celebró en Helsinki.; las actas de este congreso se publicaron en 1923. Skolem presentó una resolución en términos de reemplazos definibles de primer orden: "Sea U una proposición definida que se cumple para ciertos pares (a , b) en el dominio B; suponga además que para cada a existe como máximo una b tal que U es verdadera. Entonces, como a se extiende sobre los elementos de un conjunto M_a, b se extiende sobre todos los elementos de un conjunto M_b." En el mismo año, Fraenkel escribió una reseña del artículo de Skolem, en la que Fraenkel simplemente afirmó que las consideraciones de Skolem se corresponden con las suyas.

Zermelo mismo nunca aceptó la formulación de Skolem del esquema del axioma de reemplazo. En un momento llamó al enfoque de Skolem “teoría de conjuntos de los empobrecidos”. Zermelo imaginó un sistema que permitiría cardenales grandes. También se opuso fuertemente a las implicaciones filosóficas de los modelos contables de la teoría de conjuntos, que se derivaron de la axiomatización de primer orden de Skolem. Según la biografía de Zermelo de Heinz-Dieter Ebbinghaus, la desaprobación de Zermelo del enfoque de Skolem marcó el final de la influencia de Zermelo en el desarrollo de la teoría y la lógica de conjuntos.