Teoría de conjuntos constructiva - Constructive set theory

La teoría constructiva de conjuntos es un enfoque del constructivismo matemático que sigue el programa de la teoría axiomática de conjuntos . Se suele utilizar el mismo lenguaje de primer orden con " " y " " de la teoría de conjuntos clásica, por lo que no debe confundirse con un enfoque de tipos constructivos . Por otro lado, algunas teorías constructivas están motivadas por su interpretabilidad en las teorías de tipos . ${\ displaystyle =}$${\ Displaystyle \ in}$

Además de rechazar la ley del medio excluido ( ), las teorías de conjuntos constructivos a menudo requieren que algunos cuantificadores lógicos en sus axiomas estén delimitados , motivados por resultados ligados a la impredicatividad . ${\ displaystyle {\ mathrm {LEM}}}$

Introducción

panorama

La lógica de las teorías de conjuntos discutidas aquí es constructiva en el sentido de que rechaza , es decir, que la disyunción se cumple automáticamente para todas las proposiciones. Esto requiere el rechazo de principios de elección sólidos y la reformulación de algunos axiomas estándar. Por ejemplo, el axioma de elección implica para las fórmulas en el esquema de separación adoptado por el teorema de Diaconescu . Resultados similares son válidos para el axioma de regularidad en su forma estándar. Como regla general, para probar una disyunción particular , es necesario probar o bien . En ese caso, se dice que la disyunción es decidible. A su vez, las teorías constructivas tienden a no permitir muchas pruebas clásicas de propiedades que, por ejemplo, son demostrablemente indecidibles computacionalmente . A diferencia de la lógica mínima más conservadora , aquí la lógica subyacente permite la eliminación de la doble negación para los predicados decidibles y las formulaciones del teorema con respecto a las construcciones finitas tienden a no diferir de sus contrapartes clásicas. ${\ displaystyle {\ mathrm {LEM}}}$ ${\ Displaystyle \ phi \ lor \ neg \ phi}$${\ displaystyle {\ mathrm {LEM}}}$${\ Displaystyle P \ lor \ neg P}$${\ Displaystyle P}$${\ Displaystyle \ neg P}$

En particular, una restricción a la lógica constructiva conduce a requisitos más estrictos con respecto a qué caracterizaciones de un conjunto que involucra colecciones ilimitadas constituyen una función (matemática y, por lo tanto, siempre implica total ). Esto a menudo se debe a que el predicado en una posible definición basada en casos puede no ser decidible. En comparación con la contraparte clásica, generalmente es menos probable que se pruebe la existencia de relaciones que no pueden realizarse. Esto también afecta la demostrabilidad de enunciados sobre órdenes totales como el de todos los números ordinales , expresados ​​por la verdad y la negación de los términos en el orden que define la disyunción . Y esto, a su vez, afecta la fuerza de la teoría de la prueba definida en el análisis ordinal . ${\ Displaystyle f \ subconjunto X \ veces Y}$${\ Displaystyle (\ alpha \ in \ beta) \ lor (\ alpha = \ beta) \ lor (\ beta \ in \ alpha)}$

Dicho esto, las teorías matemáticas constructivas generalmente tienden a probar reformulaciones clásicamente equivalentes de teoremas clásicos. Por ejemplo, en el análisis constructivo , no se puede probar el teorema del valor intermedio en su formulación de libro de texto, pero se pueden probar teoremas con contenido algorítmico que, tan pronto como se asume, son a la vez clásicamente equivalentes al enunciado clásico. La diferencia es que las pruebas constructivas son más difíciles de encontrar. ${\ displaystyle {\ mathrm {LEM}}}$

En modelos

Muchas teorías estudiadas en la teoría de conjuntos constructiva son meras restricciones de la teoría${\ Displaystyle {\ mathsf {ZF}}}$ de conjuntos de Zermelo-Fraenkel ( ) con respecto a su axioma, así como a su lógica subyacente. Estas teorías también pueden interpretarse en cualquier modelo de . En lo que respecta a las realizaciones constructivas, existe una teoría de la realizabilidad y la teoría constructiva de Zermelo-Fraenkel ( ) de Aczel se ha interpretado en teorías de tipo Martin-Löf , como se describe a continuación. De esta manera, los teoremas de la teoría de conjuntos demostrables y las teorías más débiles son candidatos para una realización por computadora. Más recientemente, se han introducido modelos de preheaf para teorías de conjuntos constructivos. Estos son análogos a los modelos de Presheaf inéditos para la teoría de conjuntos intuicionista desarrollados por Dana Scott en la década de 1980. ${\ Displaystyle {\ mathsf {ZF}}}$${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathsf {CZF}}}$

Visión general

El tema de la teoría de conjuntos constructiva (a menudo " ") comenzó con el trabajo de John Myhill sobre la teoría también llamada , una teoría de varios tipos y cuantificación limitada, con el objetivo de proporcionar una base formal para el programa de matemáticas constructivas de Errett Bishop . A continuación se muestra una secuencia de teorías en el mismo idioma que , que conducen al estudio bien estudiado de Peter Aczel y más allá. también se caracteriza por las dos características presentes también en la teoría de Myhill: por un lado, está utilizando la Separación Predicativa en lugar del esquema de Separación completo e ilimitado, véase también la jerarquía de Lévy . La delimitación se puede manejar como una propiedad sintáctica o, alternativamente, las teorías se pueden extender de forma conservadora con un predicado de mayor delimitación y sus axiomas. En segundo lugar, se descarta el axioma impredicativo de Powerset , generalmente a favor de axiomas relacionados pero más débiles. La forma fuerte se usa de manera muy casual en la topología general clásica . Añadiendo a una teoría aún más débil que se recupera , como se detalla a continuación. El sistema, que ha llegado a conocerse como teoría de conjuntos intuicionista de Zermelo-Fraenkel ( ), es una teoría de conjuntos sólida sin ella . Es similar , pero menos conservador o predicativo . La teoría denotada es la versión constructiva de la clásica teoría de conjuntos de Kripke-Platek, donde incluso el axioma de colección está limitado. ${\ Displaystyle {\ mathsf {CST}}}$${\ Displaystyle {\ mathsf {CST}}}$${\ Displaystyle {\ mathsf {ZF}}}$${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathsf {CZF}}}$ ${\ displaystyle {\ mathrm {LEM}}}$${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathsf {ZF}}}$${\ Displaystyle {\ mathsf {IZF}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathsf {IKP}}}$${\ Displaystyle {\ mathsf {KP}}}$

Subteorías de ZF

Notación

Debajo del griego denota una variable de predicado en esquemas de axioma y use o para predicados particulares. Existencia única, por ejemplo, medios . Los cuantificadores van por encima del conjunto y se indican con letras minúsculas. ${\ Displaystyle \ phi}$${\ Displaystyle P}$${\ displaystyle Q}$${\ Displaystyle \ existe! xP (x)}$${\ Displaystyle \ existe x. \ forall y. \ left (y = x \ iff P (y) \ right)}$

Como es común en el estudio de las teorías de conjuntos , se utiliza la notación del constructor de conjuntos para las clases , que, en la mayoría de los contextos, no forman parte del lenguaje de objetos, pero se utilizan para una discusión concisa. En particular, se pueden introducir declaraciones de notación de la clase correspondiente a través de " ", con el fin de expresar como . Se pueden usar predicados lógicamente equivalentes para introducir la misma clase. También se escribe como abreviatura de . ${\ Displaystyle A = \ {z \ mid P (z) \}}$${\ Displaystyle P (a)}$${\ Displaystyle a \ in A}$${\ Displaystyle \ {z \ in B \ mid P (z) \}}$${\ Displaystyle \ {z \ mid z \ in B \ land P (z) \}}$

Como es común, se puede abreviar por y expresar la reivindicación subclase , es decir , por . ${\ Displaystyle \ forall z. (z \ in A \ implica P (z))}$${\ Displaystyle \ forall (z \ in A) .P (z)}$${\ Displaystyle \ forall (z \ in A) .z \ in B}$${\ Displaystyle \ forall z. (z \ in A \ implica z \ in B)}$${\ Displaystyle A \ subconjunto B}$

Para una propiedad , trivialmente . Y así sigue eso . ${\ Displaystyle P}$${\ Displaystyle \ forall z. {\ big (} (z \ in B \ land P (z)) \ implica z \ in B {\ big)}}$${\ Displaystyle \ {z \ in B \ mid P (z) \} \ subconjunto B}$

Axiomas comunes

Un punto de partida de axiomas que prácticamente siempre se consideran indiscutibles y forman parte de todas las teorías consideradas en este artículo. ${\ Displaystyle {\ mathsf {ZF}}}$

Denote por el enunciado que expresa que dos clases tienen exactamente los mismos elementos, es decir , o de manera equivalente . ${\ Displaystyle A \ simeq B}$${\ Displaystyle \ forall z. (z \ in A \ iff z \ in B)}$${\ Displaystyle (A \ subconjunto B) \ land (B \ subconjunto A)}$

El siguiente axioma da un medio para probar la igualdad " " de dos conjuntos , de modo que, mediante sustitución, cualquier predicado sobre se traduce en uno de . ${\ displaystyle =}$${\ Displaystyle x}$${\ Displaystyle y}$

Extensionalidad ${\ Displaystyle \ forall x. \ forall y. \ \ x \ simeq y \ implica x = y}$

Por las propiedades lógicas de la igualdad, la dirección inversa se mantiene automáticamente.

En una interpretación constructiva, los elementos de una subclase de pueden venir equipados con más información que los de , en el sentido de que poder juzgar es poder juzgar . Y (a menos que toda la disyunción se siga de axiomas) en la interpretación de Brouwer-Heyting-Kolmogorov , esto significa haberlo probado o haberlo rechazado. Como puede no ser decidible para todos los elementos , las dos clases deben distinguirse a priori. ${\ Displaystyle A = \ {z \ in B \ mid Q (z) \ lor \ neg Q (z) \}}$${\ Displaystyle B}$${\ Displaystyle B}$${\ Displaystyle b \ in A}$${\ Displaystyle Q (b) \ lor \ neg Q (b)}$${\ Displaystyle Q (b)}$${\ displaystyle Q}$ ${\ Displaystyle B}$

Considere una propiedad que se pueda demostrar que es válida para todos los elementos de un conjunto , de modo que , y suponga que la clase del lado izquierdo se establece como un conjunto. Tenga en cuenta que, incluso si este conjunto de la izquierda también se vincula informalmente con información relevante para la prueba sobre la validez de para todos los elementos, el axioma de extensionalidad postula que, en nuestra teoría de conjuntos, el conjunto del lado izquierdo se juzga igual a la uno en el lado derecho. ${\ Displaystyle P}$${\ Displaystyle y}$${\ Displaystyle \ {z \ in y \ mid P (z) \} \ simeq y}$${\ Displaystyle P}$

Las teorías de tipos modernas pueden, en cambio, apuntar a definir la equivalencia demandada " " en términos de funciones, ver, por ejemplo, equivalencia de tipos . El concepto relacionado de extensionalidad de funciones a menudo no se adopta en la teoría de tipos. ${\ Displaystyle \ simeq}$

Otros marcos para las matemáticas constructivas podrían, en cambio, exigir una regla particular para la igualdad o la separación para los elementos de todos y cada uno de los conjuntos discutidos. Incluso entonces, la definición anterior se puede utilizar para caracterizar la igualdad de subconjuntos y . ${\ Displaystyle z \ in x}$${\ Displaystyle x}$ ${\ Displaystyle u \ subconjunto x}$${\ Displaystyle v \ subconjunto x}$

Otros dos axiomas básicos como sigue. Primeramente,

Emparejamiento ${\ Displaystyle \ forall x. \ forall y. \ \ \ existe p. \ forall z. {\ big (} (z = x \ lor z = y) \ implica z \ in p {\ big)}}$

diciendo que para dos conjuntos cualesquiera y , hay al menos un conjunto , que contiene al menos esos dos conjuntos ( ). ${\ Displaystyle x}$${\ Displaystyle y}$${\ Displaystyle p}$${\ Displaystyle z}$

Y luego,

Unión ${\ Displaystyle \ forall x. \ \ \ existe u. \ forall y. {\ big (} (\ existe zy \ in z \ land z \ in x) \ implica y \ in u {\ big)}}$

diciendo que cualquier conjunto , hay al menos un conjunto , que contiene todos los miembros , de los miembros . ${\ Displaystyle x}$${\ Displaystyle u}$${\ Displaystyle y}$${\ Displaystyle x}$${\ Displaystyle z}$

Los dos axiomas también se pueden formular más fuertes en términos de " ", por ejemplo, en el contexto de con Separación, esto no es necesario. ${\ Displaystyle \ iff}$${\ Displaystyle {\ mathsf {BCST}}}$

Juntos, estos dos axiomas implican la existencia de la unión binaria de dos clases y cuando se han establecido como conjuntos, y esto se denota o . Defina la notación de clase para elementos finitos mediante disyunciones, por ejemplo, dice , y defina el conjunto sucesor como . Una especie de mezcla entre emparejamiento y unión, un axioma que se relaciona más fácilmente con el sucesor es el axioma de adjunción . Es relevante para el modelado estándar de ordinales de Neumann individuales . Este axioma también sería aceptado fácilmente, pero no es relevante en el contexto de axiomas más fuertes a continuación. Denotar por el modelo de par ordenado estándar . ${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle \ bigcup \ {a, b \}}$${\ Displaystyle a \ cup b}$${\ Displaystyle c \ in \ {a, b \}}$${\ Displaystyle (c = a) \ lor (c = b)}$ ${\ Displaystyle Sx}$${\ Displaystyle x \ cup \ {x \}}$${\ Displaystyle \ langle x, y \ rangle}$${\ Displaystyle \ {\ {x \}, \ {x, y \} \}}$

La propiedad que es falsa para cualquier conjunto corresponde a la clase vacía, denotada por o cero, 0. Que este es un conjunto se sigue fácilmente de otros axiomas, como el Axioma del Infinito a continuación. Pero si, por ejemplo, uno está explícitamente interesado en excluir conjuntos infinitos en su estudio, puede adoptar en este punto el axioma del conjunto vacío.${\ Displaystyle \ {\}}$

${\ Displaystyle \ existe x. \ forall y. \, \ neg (y \ in x)}$

BCST

Lo siguiente hace uso de esquemas de axiomas , es decir, axiomas para alguna colección de predicados. Tenga en cuenta que algunos de los esquemas de axiomas establecidos a menudo también se presentan con parámetros establecidos , es decir, variantes con cierres universales adicionales de modo que los 's pueden depender de los parámetros. ${\ Displaystyle v}$${\ Displaystyle \ forall v}$${\ Displaystyle \ phi}$

La teoría de conjuntos constructiva básica consta de varios axiomas que también forman parte de la teoría de conjuntos estándar, excepto que el axioma de separación se debilita. Más allá de los tres axiomas anteriores, adopta el ${\ Displaystyle {\ mathsf {BCST}}}$

Esquema del axioma de la separación predicativo : Para cualquier acotada predicado con no libre en ella, ${\ Displaystyle \ phi}$${\ Displaystyle y}$ ${\ Displaystyle \ forall y. \ \ \ existe s. \ forall x. {\ Big (} x \ in s \ iff {\ big (} x \ in y \ land \ phi (x) {\ big)} { \Grande )}}$

El axioma equivale a postular la existencia de un conjunto obtenido por la intersección de cualquier conjunto y cualquier clase descrita predicativamente . Cuando el predicado se toma como por demostrado ser un conjunto, se obtiene la intersección de conjuntos binarios y escribe . ${\ Displaystyle s}$${\ Displaystyle y}$${\ Displaystyle \ {x \ mid \ phi (x) \}}$${\ Displaystyle x \ in z}$${\ Displaystyle z}$${\ Displaystyle s = y \ cap z}$

El esquema también se denomina Separación acotada , como en Separación solo para cuantificadores acotados por conjuntos . Es el esquema del axioma el que hace referencia a los aspectos sintácticos de los predicados. Las fórmulas delimitadas también se indican en la jerarquía teórica de Lévy establecida, en analogía con en la jerarquía aritmética . (Tenga en cuenta, sin embargo, que la clasificación aritmética a veces se expresa no sintácticamente sino en términos de subclases de los naturales. Además, el nivel inferior tiene varias definiciones comunes, algunas de las cuales no permiten el uso de algunas funciones totales. La distinción no es relevante a nivel o La restricción en el axioma es también definiciones impredicativas de control de acceso : la existencia, en el mejor de los casos, no debe afirmarse para objetos que no son explícitamente describibles, o cuya definición se refiere a ellos mismos o hace referencia a una clase adecuada, como cuando una propiedad a comprobar implica un cuantificador universal. Entonces, en una teoría constructiva sin el axioma de poder establecido , uno no debe esperar una clase definida como ${\ Displaystyle \ Delta _ {0}}$${\ Displaystyle \ Delta _ {0} ^ {0}}$${\ Displaystyle \ Sigma _ {1} ^ {0}}$${\ Displaystyle s}$

${\ Displaystyle \ {x \ in y \ mid \ forall (t \ in {\ mathcal {P}} y) .Q (x, t) \}}$

es decir

${\ Displaystyle \ {x \ in y \ mid \ forall t. {\ big (} \ forall (z \ in t). (z \ in y) \ implica Q (x, t) {\ big)} \} }$

ser un conjunto, donde denota algún predicado 2-ario. Tenga en cuenta que si esta subclase es probablemente un conjunto, entonces el término así definido también está en el alcance ilimitado de la variable de término y cumple con el predicado entre corchetes utilizado para definirse a sí mismo. Si bien la Separación predicativa conduce a que se establezcan menos definiciones de clases dadas, se debe enfatizar que muchas definiciones de clases que son clásicamente equivalentes no lo son cuando se restringe uno mismo a la lógica constructiva. Entonces, de esta manera, uno obtiene una teoría más amplia, de manera constructiva. Debido a la indecidibilidad potencial de los predicados generales, la noción de subclase es más elaborada en las teorías de conjuntos constructivas que en las clásicas. ${\ displaystyle Q}$${\ Displaystyle s}$${\ Displaystyle t}$${\ Displaystyle t}$

Como se señaló, a partir de Separación y la existencia de cualquier conjunto (por ejemplo, Infinito a continuación) y el predicado que es falso de cualquier conjunto seguirá la existencia del conjunto vacío.

En virtud del teorema puramente lógico , la construcción de Russel muestra que la Separación Predicativa por sí sola lo implica . En particular, no existe un conjunto universal . ${\ Displaystyle \ forall x. {\ big (} xRs \ Leftrightarrow (xRy \ land \ neg xRx) {\ big)} \ implica \ neg sRy}$${\ Displaystyle \ {x \ in y \ mid x \ notin x \} \ notin y}$

Dentro de este contexto conservador de , el esquema de Separación acotada es en realidad equivalente a Conjunto vacío más la existencia de la intersección binaria para dos conjuntos cualesquiera. La última variante de axiomatización no utiliza un esquema. Como la subtipificación no es una característica necesaria de la teoría de tipos constructivos , se puede decir que la teoría de conjuntos constructiva difiere bastante de ese marco. ${\ Displaystyle {\ mathsf {BCST}}}$

A continuación, considere el

Esquema de axioma de reemplazo : para cualquier predicado , ${\ Displaystyle \ phi}$ ${\ Displaystyle \ forall d. \ \ \ forall (x \ in d). \ existe! y. \ phi (x, y) \ implica \ existe r. \ forall y. {\ big (} y \ in r \ iff \ existe (x \ in d). \ phi (x, y) {\ big)}}$

Es otorgar la existencia, como conjuntos, de la gama de predicados similares a funciones, obtenidos a través de sus dominios.

Con el esquema de Reemplazo, esta teoría prueba que las clases de equivalencia o sumas indexadas son conjuntos. En particular, el producto cartesiano , que contiene todos los pares de elementos de dos conjuntos, es un conjunto.

El reemplazo y el axioma de inducción de conjuntos (presentado a continuación) son suficientes para axiomizar conjuntos finitos hereditariamente de manera constructiva y esa teoría también se estudia sin Infinito. Para comparar, considere la teoría clásica muy débil llamada teoría general de conjuntos que interpreta la clase de números naturales y su aritmética a través de solo extensionalidad, adjunción y separación completa.

En , Reemplazo es principalmente importante para probar la existencia de conjuntos de alto rango , es decir, a través de instancias del esquema de axioma donde se relaciona un conjunto relativamente pequeño con otros más grandes . ${\ Displaystyle {\ mathsf {ZF}}}$${\ Displaystyle \ phi (x, y)}$${\ Displaystyle x}$${\ Displaystyle y}$

Las teorías de conjuntos constructivos comúnmente tienen un esquema de Axioma de reemplazo, a veces restringido a fórmulas acotadas. Sin embargo, cuando se eliminan otros axiomas, este esquema a menudo se refuerza, no más allá , sino simplemente para recuperar algo de fuerza demostrable. ${\ Displaystyle {\ mathsf {ZF}}}$

El reemplazo puede verse como una forma de comprensión. Solo cuando se asume , Reemplazo ya implica Separación total. ${\ displaystyle {\ mathrm {LEM}}}$

ECST

Denote por la propiedad inductiva, por ejemplo . En términos de un predicado subyacente a la clase, esto se traduciría como . Aquí denota una variable de conjunto genérica. Escribe para . Define una clase . ${\ Displaystyle \ mathrm {Ind} (A)}$${\ Displaystyle 0 \ in A \ land \ forall (n \ in A) .Sn \ in A}$${\ Displaystyle P}$${\ Displaystyle P (0) \ land \ forall n. {\ big (} P (n) \ implica P (Sn) {\ big)}}$${\ Displaystyle n}$${\ Displaystyle \ bigcap A}$${\ Displaystyle \ {x \ mid \ forall y. (y \ in A \ implica x \ in y) \}}$${\ Displaystyle \ omega = \ bigcap \ {x \ mid \ mathrm {Ind} (x) \}}$

Para algún predicado fijo , el enunciado expresa que es el conjunto más pequeño entre todos los conjuntos para los que es verdadero. La teoría de conjuntos constructiva elemental tiene el axioma de , así como ${\ Displaystyle P}$${\ Displaystyle P (a) \ land \ forall xP (x) \ implica un \ subconjunto x}$${\ Displaystyle a}$${\ Displaystyle x}$${\ Displaystyle P (x)}$${\ Displaystyle {\ mathsf {ECST}}}$${\ Displaystyle {\ mathsf {BCST}}}$

Infinito fuerte ${\ Displaystyle \ existe w. {\ Big (} \ mathrm {Ind} (w) \, \ land \, {\ big (} \ forall x. \ mathrm {Ind} (x) \ implica w \ subconjunto x { \grande grande )}}$

El segundo conjunto cuantificado universalmente expresa inducción matemática para todos en el universo del discurso, es decir, para conjuntos, resp. para predicados si de hecho definen conjuntos . De esta manera, los principios discutidos en esta sección brindan un medio para probar que algunos predicados son válidos al menos para todos los elementos de . Tenga en cuenta que incluso el axioma bastante fuerte de la inducción matemática completa (inducción para cualquier predicado, discutido a continuación) también puede adoptarse y usarse sin postular nunca que forma un conjunto. ${\ Displaystyle x}$${\ Displaystyle x}$${\ Displaystyle \ omega}$${\ Displaystyle \ omega}$

Se pueden formular formas débiles de axiomas de infinito, todas postulando que existe algún conjunto con las propiedades comunes de los números naturales. Entonces se puede usar la Separación completa para obtener el conjunto "disperso", el conjunto de números naturales. En el contexto de sistemas de axiomas por lo demás más débiles, un axioma de infinito debería fortalecerse para implicar la existencia de un conjunto tan disperso por sí solo. Una forma más débil de Infinity lee

${\ Displaystyle \ existe w. \ forall m. {\ Big (} m \ in w \ iff {\ big (} m = 0 \ lor (\ existe n \ in w). \ forall k. (k \ in m \ iff k \ in n \ lor k = n) {\ big)} {\ Big)}}$

que también se puede escribir de forma más concisa usando . El conjunto así postulado que existe se denota generalmente por el ordinal infinito más pequeño de von Neumann . Para los elementos de este conjunto, la reclamación es decidible. ${\ Displaystyle S}$${\ Displaystyle \ omega}$${\ Displaystyle n, m}$${\ Displaystyle n = m}$

Con esto, se prueba la inducción para todos los predicados dados por fórmulas acotadas. Los dos de los cinco axiomas de Peano con respecto a cero y uno con respecto a la cerrazón de con respecto a seguir bastante directamente de los axiomas de infinito. Finalmente, puede demostrarse que es una operación inyectiva. ${\ Displaystyle {\ mathsf {ECST}}}$${\ Displaystyle S}$${\ Displaystyle \ omega}$${\ Displaystyle S}$

Los números naturales son distinguibles, lo que significa que la igualdad (y por lo tanto la desigualdad) de ellos es decidible. El orden básico se captura mediante la pertenencia a este modelo. En aras de la notación estándar, denotemos un segmento inicial de los números naturales, para cualquiera , incluido el conjunto vacío. ${\ Displaystyle \ {0,1, \ puntos, n-1 \}}$${\ Displaystyle \ {k \ in \ omega \ mid k <n \}}$${\ Displaystyle k \ in \ omega}$

Funciones

Naturalmente, el significado lógico de las afirmaciones de existencia es un tema de interés en la lógica intuicionista. Aquí el foco está en las relaciones totales .

El cálculo de prueba, en un marco matemático constructivo, de enunciados como

${\ Displaystyle \ forall (a \ en A). \ existe (c \ en C) .P (a, c)}$

podría configurarse en términos de programas en dominios representados y posiblemente tener que ser testigo del reclamo. Esto debe entenderse en el sentido de, informalmente hablando, donde denota el valor de un programa como se mencionó, pero esto entra en cuestiones de teoría de la realizabilidad . Para un contexto más fuerte, si y cuando la proposición se sostiene, entonces exigir que esto siempre sea posible con una función recursiva total realizada por alguna es un posible postulado de tesis de Church adoptado, en consecuencia, en el constructivismo ruso estrictamente no clásico . En el párrafo anterior, "función" debe entenderse en el sentido computable de la teoría de la recursividad ; esta ambigüedad ocasional también debe tenerse en cuenta a continuación. ${\ Displaystyle \ forall (a \ in A) .P (a, c_ {a})}$${\ Displaystyle c_ {a}}$${\ Displaystyle A = C = \ omega}$${\ Displaystyle a \ mapsto c_ {a}}$

De manera relacionada, considere la aritmética de Robinson , que es una teoría aritmética clásica que sustituye el esquema de inducción matemático completo por una afirmación de existencia de un número predecesor. Es un teorema que esa teoría representa exactamente las funciones recursivas en el sentido de definir predicados que son probablemente relaciones funcionales totales , ${\ Displaystyle P}$

${\ Displaystyle \ forall (a \ in {\ mathbb {N}}). \ existe! (c \ in {\ mathbb {N}}). P (a, c)}$.

Ahora, en el enfoque teórico de conjuntos actual, definamos la propiedad que involucra a los paréntesis de aplicación de la función ,, como y hablemos de una función cuando sea demostrable ${\ Displaystyle f (a) = c}$${\ Displaystyle \ langle a, c \ rangle \ in f}$${\ Displaystyle f \ subconjunto A \ times C}$

${\ Displaystyle \ forall (a \ en A). \, \ existe! (c \ en C) .f (a) = c}$,

es decir

${\ Displaystyle \ forall (a \ en A). \, \ existe (c \ en C). \, \ forall (c '\ en C). {\ big (} c' = c \ iff \ langle a, c '\ rangle \ in f {\ big)}}$,

lo que en particular implica un cuantificador existencial. El que una subclase pueda considerarse una función dependerá de la fuerza de la teoría, es decir, de los axiomas que uno adopte.

En particular, una clase general podría cumplir con el predicado anterior sin ser una subclase del producto , es decir, la propiedad expresa ni más ni menos que la funcionalidad de las entradas . Si el dominio y el codominio son conjuntos, entonces el predicado anterior solo involucra cuantificadores acotados. Se debe tener cuidado con la nomenclatura "función", que se usa en la mayoría de los marcos matemáticos, también porque algunos vinculan un término de función en sí mismo a un codominio particular. También se han definido variantes de la definición de predicado funcional que utilizan relaciones de separación en setoides . ${\ Displaystyle A \ times C}$${\ Displaystyle A}$

Dejar que (también escrito ) denotan la clase de tales funciones establecidas. Usando la terminología de clase estándar, uno puede hacer uso de funciones libremente, dado que su dominio es un conjunto. Las funciones en su conjunto se establecerán si su codominio es. Cuando las funciones se entienden simplemente como gráficas de funciones como se indicó anteriormente, también se escribe la proposición de pertenencia . A continuación se puede escribir para distinguirlo de la exponenciación ordinal. ${\ Displaystyle C ^ {A}}$${\ Displaystyle {} ^ {A} C}$${\ Displaystyle f \ en C ^ {A}}$${\ Displaystyle f \ colon A \ to C}$${\ Displaystyle x \ to y}$${\ Displaystyle y ^ {x}}$

La separación permite utilizar subconjuntos recortados de productos , al menos cuando se describen de forma limitada. Escribe para . Dado cualquiera , uno ahora es llevado a razonar sobre clases como ${\ Displaystyle A \ times C}$${\ Displaystyle 1}$${\ Displaystyle S0}$${\ Displaystyle B \ subconjunto A}$

${\ Displaystyle \ {\ langle x, y \ rangle \ in A \ times \ {0,1 \} \ mid (x \ in B \ land y = 1) \ lor (\ neg (x \ in B) \ land y = 0) \}.}$

Las funciones características con valores booleanos se encuentran entre esas clases. Pero tenga en cuenta que , en general, puede no ser decidible . Es decir, en ausencia de axiomas no constructivos, la disyunción puede no ser demostrable, ya que se requiere una prueba explícita de cualquier disyunción. Cuando ${\ Displaystyle \ chi _ {B} \ dos puntos A \ a \ {0,1 \}}$${\ Displaystyle a \ in B}$${\ Displaystyle a \ in B \ lor a \ notin B}$

${\ Displaystyle \ existe (y_ {a} \ in \ {0,1 \}). f (a) = y_ {a}}$

no se puede presenciar para todos , o no se puede probar la unicidad de un término , entonces no se puede juzgar constructivamente que la colección comprendida es funcional. ${\ Displaystyle a \ in A}$${\ Displaystyle y_ {a}}$

Por y cualquier natural , tener ${\ Displaystyle I = \ {n \ in \ omega \ mid Q (n) \}}$${\ Displaystyle n \ in \ omega}$

${\ Displaystyle Q (n) \ lor \ neg Q (n) \ implica n \ in I \ lor n \ notin I}$.

Entonces, en la teoría de conjuntos clásica, donde, por , las proposiciones en la definición son decidibles, también lo es la pertenencia a una subclase. Si el conjunto no es finito, "enumerar" sucesivamente todos los números simplemente omitiendo aquellos con clásicamente constituye una secuencia sobreyectiva creciente . Allí se puede obtener una función biyectiva . De esta manera, la clase clásica de funciones es demostrablemente rica, ya que también contiene objetos que están más allá de lo que sabemos que son efectivamente computables , o programáticamente listables en la práctica. ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle Q}$${\ Displaystyle I}$${\ Displaystyle n \ notin I}$${\ Displaystyle a: \ omega \ twoheadrightarrow I}$

Por el contrario, como referencia, en la teoría de la computabilidad , los conjuntos computables son rangos de funciones totales no decrecientes (en el sentido recursivo), en el nivel de la jerarquía aritmética , y no más alto. Decidir un predicado en ese nivel equivale a resolver la tarea de encontrar finalmente un certificado que valide o rechace la membresía. Como no todos los predicados son computablemente decidibles, la teoría por sí sola no afirmará (probará) que todos los infinitos son el rango de alguna función biyectiva con dominio . ${\ Displaystyle \ Sigma _ {1} ^ {0} \ cap \ Pi _ {1} ^ {0} = \ Delta _ {1} ^ {0}}$${\ displaystyle Q}$${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle I \ subconjunto \ omega}$${\ Displaystyle \ omega}$

Ser finito significa que hay una función biyectiva en lo natural. Ser subfinito significa ser un subconjunto de un conjunto finito. La afirmación de que ser un conjunto finito es equivalente a ser subfinito es equivalente a . ${\ displaystyle {\ mathrm {LEM}}}$

Pero siendo compatible con , el desarrollo en esta sección también siempre permite que la "función sobre " sea interpretada como un objeto no necesariamente dado como secuencia legal . Se pueden encontrar aplicaciones en los modelos comunes para afirmaciones sobre probabilidad, por ejemplo, afirmaciones que implican la noción de "recibir" una secuencia aleatoria interminable de lanzamientos de monedas. ${\ Displaystyle {\ mathsf {ZF}}}$${\ Displaystyle \ omega}$

Elección

• Axioma de elección contable : Si , se puede formar el conjunto de relaciones de uno a muchos . El axioma de la elección contable concedería que siempre que se pueda formar una función que asigne cada número a un valor único. La elección contable también puede debilitarse aún más, por ejemplo, restringiendo las posibles cardinalidades de los conjuntos en el rango de , o restringiendo la definición involucrada en su lugar en las jerarquías sintácticas.${\ Displaystyle g \ colon \ omega \ to z}$${\ Displaystyle \ {\ langle n, u \ rangle \ mid n \ in \ omega \ land u \ in g (n) \}}$${\ Displaystyle \ forall (n \ in \ omega). \ existe uu \ in g (n)}$${\ Displaystyle g}$

• Axioma de elección dependiente : está implícito en el axioma más general de elección dependiente, extrayendo una función de cualquier relación completa en un conjunto habitado. La elección contable es similar a un caso de la tesis de la Iglesia constructiva y, de hecho, la elección dependiente se mantiene en muchos modelos de realizabilidad y, por lo tanto, se adopta en muchas escuelas constructivas.

• Elección dependiente relativizada: el principio de elección dependiente relativizado más fuerte es una variante de él: un esquema que involucra una variable predicada adicional. La adopción de esta para las fórmulas simplemente delimitadas en , la teoría ya demuestra la - inducción , se analiza más adelante.${\ Displaystyle {\ mathsf {ECST}}}$${\ Displaystyle \ Sigma _ {1} ^ {0}}$

• Axioma de elección : el axioma de elección relativo a funciones en dominios generales. Implica elección dependiente.

Para resaltar la fuerza de la elección total y su relación con cuestiones de intencionalidad , se deben considerar las clases subfinitas.

${\ Displaystyle x = \ {u \ in \ {0,1 \} \ mid u = 0 \ lor (u = 1 \ land P) \}}$

${\ Displaystyle y = \ {u \ in \ {0,1 \} \ mid u = 1 \ lor (u = 0 \ land P) \}}$

Aquí y son tan contingentes como los predicados involucrados en su definición. Ahora suponga un contexto en el que se establecen para ser conjuntos, así que eso también lo es. Aquí, Axiom of Choice otorgaría la existencia de un mapa con elementos distinguibles. Esto ahora realmente implica eso . Por tanto, la afirmación de existencia de funciones de elección general no es constructiva. Para comprender mejor este fenómeno, se deben considerar casos de implicaciones lógicas, como , etcétera. La diferencia entre el codominio discreto de algunos números naturales y el dominio radica en el hecho de que a priori se sabe poco sobre este último. Es el caso de eso y , independientemente de , posiblemente hacer un contendiente para una función de elección. Pero en el caso de , como implica la demostrabilidad de , uno tiene de modo que exista extensionalmente sólo una entrada de función posible a una función de elección de elección, ahora con sólo , las funciones de elección podrían ser o . Entonces, al considerar la asignación funcional , declarar incondicionalmente no sería consistente. Es posible que la elección no se adopte en una teoría de conjuntos que de otro modo sería fuerte, porque la mera afirmación de la existencia de una función no realiza una función particular. La comprensión de subclase (usada para separar y de , es decir, definirlos) vincula los predicados involucrados en ellos para establecer la igualdad, en la forma descrita, y esto se relaciona con la información sobre funciones. ${\ Displaystyle x}$${\ Displaystyle y}$${\ Displaystyle \ {x, y \}}$${\ Displaystyle f \ colon \ {x, y \} \ to \ {0,1 \}}$${\ Displaystyle f (z) \ in z}$ ${\ Displaystyle P \ lor \ neg P}$${\ Displaystyle P \ implica x = y}$${\ Displaystyle \ {x, y \}}$${\ Displaystyle 0 \ in x}$${\ Displaystyle 1 \ en y}$${\ Displaystyle P}$${\ Displaystyle \ {\ langle x, 0 \ rangle, \ langle y, 1 \ rangle \}}$${\ Displaystyle x = y}$${\ Displaystyle P}$${\ Displaystyle \ {x, y \} = \ {x \}}$${\ Displaystyle \ {x \} \ a \ {0,1 \}}$${\ Displaystyle \ {\ langle x, 0 \ rangle \}}$${\ Displaystyle \ {\ langle x, 1 \ rangle \}}$${\ Displaystyle f (x) = 0}$${\ Displaystyle f (y) = 1}$${\ Displaystyle x}$${\ Displaystyle y}$${\ Displaystyle \ {0,1 \}}$

El desarrollo constructivo a menudo procede de una manera independiente de los principios de elección discutidos.

Aritmética

Los supuestos necesarios para obtener una teoría de la aritmética se estudian a fondo en la teoría de la prueba . Para el contexto, aquí un párrafo sobre las clasificaciones en el mismo: Las teorías clásicas que comienzan con aritmética acotada adoptan diferentes esquemas de inducción conservadores y pueden agregar símbolos para funciones particulares, lo que lleva a teorías entre la aritmética de Robinson y Peano . Sin embargo, la mayoría de estas teorías son relativamente débiles con respecto a la prueba de totalidad para algunas funciones de crecimiento más rápido . Algunos de los ejemplos más básicos incluyen la aritmética de funciones elementales , con un ordinal teórico de prueba (el menos no probablemente recursivo bien ordenado ) de . ha ordinal , es decir, la teoría permite una ordinales codificar de más débil (en este sentido análisis ordinal) teorías (digamos , en términos teoría de conjuntos) como relación recursiva en sólo los naturales, . El esquema de inducción, como, por ejemplo, implica la elección dependiente relativizada, significa inducción para aquellas subclases de naturales computables a través de una búsqueda finita con tiempo de ejecución no ligado (finito). El esquema también es equivalente al esquema de inducción. Se denota la aritmética clásica de primer orden relativamente débil que adopta ese esquema . La inducción-también se adopta el sistema de base matemático inverso clásico de segundo orden . Esa teoría de segundo orden es conservadora sobre la aritmética recursiva primitiva , por lo que demuestra que todas las funciones recursivas primitivas son totales. Todas las últimas teorías aritméticas mencionadas tienen ordinal . La aritmética de orden superior mencionada es un punto de referencia relevante en esta discusión en la medida en que su lenguaje no expresa simplemente conjuntos aritméticos , mientras que todos los conjuntos de naturales que la teoría demuestra que existen son simplemente conjuntos computables . ${\ Displaystyle {\ mathsf {PA}}}$ ${\ displaystyle {\ mathsf {EFA}}}$${\ Displaystyle \ omega ^ {3}}$${\ Displaystyle {\ mathsf {PA}}}$${\ Displaystyle \ varepsilon _ {0}}$${\ Displaystyle \ langle \ omega ^ {3}, \ in \ rangle}$${\ Displaystyle \ langle \ omega, E \ rangle}$${\ Displaystyle \ Sigma _ {1} ^ {0}}$${\ Displaystyle \ Pi _ {1} ^ {0}}$${\ Displaystyle {\ mathsf {I \ Sigma}} _ {1}}$${\ Displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ Displaystyle \ Pi _ {2} ^ {0}}$ ${\ displaystyle {\ mathsf {PRA}}}$${\ Displaystyle \ omega ^ {\ omega}}$

Dicho todo esto, la teoría de conjuntos en realidad ni siquiera interpreta la recursividad primitiva completa. De hecho, a pesar de tener el axioma de Reemplazo, la teoría no prueba que la función de suma sea una función de conjunto. Por otro lado, en esta teoría se pueden probar muchos enunciados por conjunto individual en esta teoría (a diferencia de las expresiones que involucran un cuantificador universal, como por ejemplo, disponible con un principio de inducción) y los objetos de interés matemático se pueden utilizar a nivel de clase en un nivel de manera individual. Como tales, los axiomas enumerados hasta ahora son suficientes como teoría de trabajo básica para una buena parte de las matemáticas básicas. Yendo más allá en lo que respecta a la aritmética, se debe agregar el axioma que otorga la definición de funciones de conjunto a través de funciones de conjunto de pasos de iteración. Lo que se necesita es el equivalente teórico establecido de un objeto de números naturales . Esto permite entonces una interpretación de Heyting aritmética , . Con esto, también se puede definir la aritmética de números racionales y probar sus propiedades, como la unicidad y la contabilidad. Una teoría de conjuntos con esto también demostrará que, para cualquier natural y , los espacios funcionales ${\ Displaystyle {\ mathsf {ECST}}}$${\ Displaystyle {\ mathsf {ECST}}}$${\ Displaystyle {\ mathsf {HA}}}$${\ Displaystyle {\ mathbb {Q}}}$${\ Displaystyle n}$${\ Displaystyle m}$

${\ Displaystyle {\ {0,1, \ dots, n-1 \}} \ to {\ {0,1, \ dots, m-1 \}}}$

son conjuntos.

Por el contrario, una prueba del principio de iteración buscado puede basarse en la colección de funciones que uno quisiera escribir y la existencia de esto está implícita al asumir que los espacios funcionales individuales en dominios finitos en conjuntos forman conjuntos ellos mismos. Esta observación debería motivar la adopción de un axioma de carácter teórico más establecido, en lugar de simplemente incrustar directamente principios aritméticos en nuestra teoría. Sin embargo, el principio de iteración obtenido a través del siguiente axioma teórico más establecido todavía no probará el esquema de inducción matemático completo . ${\ Displaystyle \ cup _ {n \ in \ omega} y ^ {\ {0,1, \ dots, n-1 \}}}$${\ Displaystyle y}$

Exponenciación

Ya se adoptó una forma debilitada del esquema de Separación, y más axiomas estándar se debilitarán para una teoría más predicativa y constructiva. El primero de ellos es el axioma de Powerset , que, de hecho, se adoptó para subconjuntos decidibles de la teoría. ${\ Displaystyle {\ mathsf {ZF}}}$

La caracterización de la clase de todos los subconjuntos de un conjunto implica una cuantificación universal ilimitada, a saber . Aquí se ha definido en términos del predicado de pertenencia anterior. La declaración en sí misma lo es . Entonces, en un marco de teoría matemática de conjuntos, la clase de poder se define no en una construcción de abajo hacia arriba a partir de sus constituyentes (como un algoritmo en una lista, por ejemplo, mapas ) sino a través de una comprensión de todos los conjuntos. ${\ Displaystyle {\ mathcal {P}} x}$${\ Displaystyle x}$${\ Displaystyle \ forall uu \ subconjunto x \ iff u \ in {\ mathcal {P}} x}$${\ Displaystyle \ subconjunto}$${\ Displaystyle \ in}$${\ Displaystyle y = {\ mathcal {P}} x}$${\ Displaystyle \ Pi _ {1}}$${\ Displaystyle \ langle a, b \ rangle \ mapsto \ langle \ langle \ rangle, \ langle a \ rangle, \ langle b \ rangle, \ langle a, b \ rangle \ rangle}$

La riqueza de la clase poderosa en una teoría sin medios excluidos puede entenderse mejor si se consideran pequeños conjuntos clásicamente finitos. Para cualquier fórmula , la clase es igual a 0 cuando se puede rechazar y 1 cuando se puede probar, pero es posible que tampoco se pueda decidir en absoluto. En este punto de vista, la clase de poder del singleton , es decir, la clase , o sugestivamente " ", y generalmente denotada por , se llama álgebra de valor de verdad. Las funciones valoradas en un conjunto se inyectan y, por tanto, corresponden a sus subconjuntos decidibles. ${\ Displaystyle P}$${\ Displaystyle \ {x \ mid (x = 0) \ land P \}}$${\ Displaystyle P}$${\ Displaystyle P}$${\ Displaystyle P}$${\ Displaystyle \ {0 \} = 1}$${\ Displaystyle {\ mathcal {P}} 1}$${\ Displaystyle \ {0, \ dots, 1 \}}$${\ Displaystyle \ Omega}$${\ Displaystyle \ {0,1 \}}$${\ Displaystyle x}$${\ Displaystyle \ Omega ^ {x}}$

A continuación, considere el axioma . ${\ displaystyle {\ mathrm {Exp}}}$

Exponenciación ${\ Displaystyle \ forall x. \ forall y. \ \ \ existe hh = y ^ {x}}$

La formulación aquí usa la notación conveniente para espacios funcionales. De lo contrario, el axioma es más extenso e implica un cuantificador acotado por y el predicado de función total. En palabras, el axioma dice que dados dos conjuntos , la clase de todas las funciones es, de hecho, también un conjunto. Esto es ciertamente necesario, por ejemplo, para formalizar el mapa de objetos de un hom-functor interno como . El uso de los axiomas de exponenciación se deriva del hecho de que los espacios de funciones al ser conjuntos significa que la cuantificación de sus funciones es una noción acotada, lo que permite el uso de la separación. Tiene implicaciones notables: adoptarlo significa que la cuantificación sobre los elementos de ciertas clases de funciones se convierte en una noción acotada, incluso cuando los espacios funcionales son incluso clásicamente incontables . Por ejemplo, la colección de todas las funciones , es decir, el conjunto de puntos subyacentes al espacio de Cantor , es incontable, según el argumento de la diagonal de Cantor , y en el mejor de los casos puede tomarse como contable . (En esta sección, comenzamos a usar el símbolo para el semiring de números naturales en expresiones como o escribimos solo para evitar la fusión de cardinal- con exponenciación ordinal). ${\ Displaystyle x \ times y}$${\ Displaystyle x, y}$${\ Displaystyle y ^ {x}}$${\ Displaystyle {\ mathrm {hom}} ({\ mathbb {N}}, -)}$${\ Displaystyle \ forall f}$${\ Displaystyle f \ colon \ omega \ to \ {0,1 \}}$${\ Displaystyle \ {0,1 \} ^ {\ mathbb {N}}}$${\ Displaystyle y ^ {\ mathbb {N}}}$${\ Displaystyle \ omega \ to y}$

La teoría de conjuntos con exponenciación ahora también prueba la existencia de cualquier función recursiva primitiva en las naturales , como funciones de conjunto en el conjunto . De manera relacionada, obtenga el número exponenciado ordinal , que se puede caracterizar como . Hablando de manera más general, la exponenciación demuestra que la unión de todas las secuencias finitas sobre un conjunto contable es un conjunto contable. Y de hecho, las uniones de los rangos de cualquier familia contable de funciones de conteo son contables. ${\ Displaystyle \ omega}$${\ Displaystyle \ omega \ a \ omega}$${\ Displaystyle \ omega ^ {\ omega}}$${\ Displaystyle \ bigcup _ {n \ in \ omega} \ omega ^ {n}}$

En lo que respecta a la comprensión, la teoría ahora demuestra que la colección de todos los subconjuntos contables de cualquier conjunto (la colección es una subclase de la clase de potencia) es un conjunto. También se puede probar el principio del casillero .

Volviendo a la consideración original de la clase de poder: cuando se asume que todas las fórmulas son decidibles, es decir, se asume , se puede mostrar no solo que se convierte en un conjunto, sino más concretamente que es este conjunto de dos elementos. Suponiendo fórmulas limitadas, Separación permite demostrar que cualquier clase de potencia es un conjunto. Alternativamente, Powerset completo es equivalente a simplemente asumir que la clase de todos los subconjuntos de forma un conjunto. La separación completa equivale a asumir que cada subclase individual de es un conjunto. ${\ displaystyle {\ mathrm {LEM}}}$${\ Displaystyle \ Omega}$${\ displaystyle {\ mathrm {LEM}}}$${\ Displaystyle 1}$${\ Displaystyle 1}$

Nociones teóricas de categorías y tipos

Entonces, en este contexto con la exponenciación, los espacios de funciones son más accesibles que las clases de subconjuntos, como es el caso de los objetos exponenciales resp. subobjetos en la teoría de categorías. En términos teóricos de categorías , la teoría corresponde esencialmente a una preposición cartesiana cerrada constructivamente bien apuntada de Heyting con (siempre que se adopte el Infinito) un objeto de números naturales . La existencia de powerset es lo que convertiría un pretopos de Heyting en un topos elemental . Cada uno de esos topos que interpreta es, por supuesto, un modelo de estas teorías más débiles, pero localmente se han definido pretopos cerrados cartesianos que, por ejemplo, interpretan teorías con Exponenciación pero rechazan la Separación completa y el Powerset. ${\ Displaystyle {\ mathsf {BCST}} + {\ mathrm {Exp}}}$ ${\ Displaystyle {\ mathsf {ZF}}}$

En la teoría de tipos, la expresión " " existe por sí misma y denota espacios funcionales , una noción primitiva. Estos tipos (o, en la teoría de conjuntos, clases o conjuntos) aparecen naturalmente, por ejemplo, como el tipo de biyección de curry entre y , un adjunto . Una teoría de tipos típica con capacidad de programación general, y ciertamente aquellas que pueden modelar , que se considera una teoría de conjuntos constructiva, tendrá un tipo de números enteros y espacios funcionales que representan y, como tal, también incluirá tipos que no son contables. Esto solo implica y significa que entre los términos de función , ninguno tiene la propiedad de ser una biyección. ${\ Displaystyle x \ to y}$${\ Displaystyle (z \ times x) \ to y}$${\ Displaystyle z \ to y ^ {x}}$${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathbb {Z}} \ to {\ mathbb {Z}}}$${\ Displaystyle f \ dos puntos {\ mathbb {Z}} \ to ({\ mathbb {Z}} \ to {\ mathbb {Z}})}$

Las teorías de conjuntos constructivos también se estudian en el contexto de axiomas aplicativos .

Análisis

En este apartado se elabora la fortaleza de . Para el contexto, se mencionan posibles principios adicionales, que no son necesariamente clásicos y tampoco generalmente se consideran constructivos. Aquí conviene hacer una advertencia general: al leer afirmaciones de equivalencia de proposiciones en el contexto computable, uno siempre debe estar consciente de qué principios de elección , inducción y comprensión se asumen silenciosamente. Consulte también el análisis constructivo y el análisis computable relacionados . ${\ Displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$

Hacia los reales

La exponenciación implica principios de recursividad y así , uno puede razonar sobre secuencias o sobre intervalos reducidos y esto también permite hablar de secuencias de Cauchy y su aritmética. Cualquier número real de Cauchy es una colección de secuencias, es decir, un subconjunto de un conjunto de funciones en . Se requieren más axiomas para garantizar siempre la integridad de las clases de equivalencia de tales secuencias y es necesario postular principios sólidos para implicar la existencia de un módulo de convergencia para todas las secuencias de Cauchy. La elección contable débil es generalmente el contexto para demostrar la unicidad de los reales de Cauchy como campo completo (pseudo) ordenado. "Pseudo-" aquí destaca que el orden, en cualquier caso, no siempre será decidible de manera constructiva. ${\ Displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$${\ Displaystyle \ omega \ to {\ mathbb {Q}}}$${\ Displaystyle \ omega \ to ({\ mathbb {Q}} \ times {\ mathbb {Q}})}$${\ Displaystyle \ omega}$

Como en la teoría clásica, los cortes de Dedekind se caracterizan usando subconjuntos de estructuras algebraicas tales como : Las propiedades de estar habitado, delimitado numéricamente arriba, "cerrado hacia abajo" y "abierto hacia arriba" son fórmulas acotadas con respecto al conjunto dado subyacente al algebraico. estructura. Un ejemplo estándar de un corte, el primer componente que de hecho exhibe estas propiedades, es la representación de dado por ${\ Displaystyle {\ mathbb {Q}}}$${\ Displaystyle {\ sqrt {2}}}$

${\ Displaystyle {\ big \ langle} \ {x \ in {\ mathbb {Q}} \ mid x <0 \ lor x ^ {2} <2 \}, \, \ {x \ in {\ mathbb {Q }} \ mid 0 <x \ land 2 <x ^ {2} \} {\ big \ rangle} \, \ \ in \, \ {{\ mathcal {P}} {\ mathbb {Q}}} \ times {{\ mathcal {P}} {\ mathbb {Q}}}}$

(Dependiendo de la convención para cortes, cualquiera de las dos partes o ninguna, como aquí, puede hacer uso del signo ). ${\ Displaystyle \ leq}$

La teoría dada por los axiomas hasta ahora valida que un campo pseudoordenado que también es completo de Arquímedes y Dedekind , si es que existe, se caracteriza de esta manera de manera única, hasta el isomorfismo. Sin embargo, la existencia de solo espacios de función como no otorga ser un conjunto, por lo que tampoco lo es la clase de todos los subconjuntos que cumplen con las propiedades nombradas. Lo que se requiere para que la clase de reales de Dedekind sea un conjunto es un axioma con respecto a la existencia de un conjunto de subconjuntos. ${\ Displaystyle \ {0,1 \} ^ {\ mathbb {Q}}}$${\ Displaystyle {{\ mathcal {P}} {\ mathbb {Q}}}}$${\ Displaystyle {\ mathbb {Q}}}$

En cualquiera de los casos, un menor número de declaraciones sobre la aritmética de los números reales son decidible , en comparación con la teoría clásica.

Escuelas constructivas

Las afirmaciones no constructivas valiosas en el estudio del análisis constructivo se formulan comúnmente en lo que respecta a todas las secuencias binarias, es decir, funciones . Es decir siniestros cuantificados por . ${\ Displaystyle f \ colon \ omega \ to \ {0,1 \}}$${\ Displaystyle \ forall (f \ in \ {0,1 \} ^ {\ mathbb {N}})}$

Un ejemplo más destacado es el principio limitado de omnisciencia , que postula una propiedad disyuntiva, como en el nivel de las oraciones o funciones. (Las funciones de ejemplo se pueden construir en bruto de modo que, si es coherente, los disyuntos en competencia no se puedan demostrar). El principio es independiente de, por ejemplo, que se presenta a continuación. En esa teoría de conjuntos constructiva, implica su versión "menor", denotada , una variante restringida de la ley de De Morgan . Además, implica el principio de Markov , una forma de prueba por contradicción y la versión-del teorema del abanico . La mención de tales principios que se sostienen para las oraciones generalmente insinúa formulaciones equivalentes en términos de secuencias, que deciden la separación de los reales. En un contexto de análisis constructivo con elección contable, es , por ejemplo, equivalente a la afirmación de que todo real es racional o irracional, de nuevo sin el requisito de presenciar una disyunción. ${\ displaystyle {\ mathrm {LPO}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ Displaystyle \ Pi _ {1} ^ {0}}$${\ Displaystyle {\ mathsf {PA}}}$${\ Displaystyle {\ mathsf {PA}}}$${\ Displaystyle {\ mathsf {PA}}}$${\ Displaystyle {\ mathsf {CZF}}}$${\ displaystyle {\ mathrm {LPO}}}$${\ displaystyle {\ mathrm {LLPO}}}$ ${\ Displaystyle {\ mathrm {MP}}}$${\ Displaystyle \ Pi _ {1} ^ {0}}$${\ Displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle {\ mathrm {LPO}}}$

Entonces, para algunas proposiciones empleadas en las teorías del análisis constructivo que no son probables usando solo la lógica intuicionista básica, vea o incluso la tesis constructiva no clásica de Church o algunas de sus consecuencias en el lado de las matemáticas recursivas ( o ), y así como el esquema de Kripke (girando todas las subclases de contables), inducción de barras , el teorema del abanico decidible o incluso el principio de continuidad no clásico que determina funciones en secuencias interminables a través de segmentos iniciales finitos en el lado intuicionista brouweriano ( ). Ambas escuelas se contradicen , por lo que la elección de adoptar tales leyes hace que la teoría sea incompatible con los teoremas del análisis clásico. ${\ Displaystyle {\ mathrm {MP}}}$ ${\ Displaystyle {\ mathrm {CT}}}$${\ displaystyle {\ mathsf {RUSS}}}$${\ displaystyle {\ mathsf {CRM}}}$${\ Displaystyle \ omega}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$ ${\ Displaystyle {\ mathsf {INT}}}$${\ displaystyle {\ mathrm {LPO}}}$

Árboles infinitos

A través de la relación entre la computabilidad y la jerarquía aritmética, los conocimientos de este estudio clásico también son reveladores para consideraciones constructivas. Una idea básica de las matemáticas inversas se refiere a árboles binarios infinitamente ramificados infinitamente computables. Un árbol de este tipo puede, por ejemplo, codificarse como un conjunto infinito de conjuntos finitos.

${\ Displaystyle T \, \ subset \, \ cup _ {n \ in \ omega} \ {0,1 \} ^ {\ {0,1, \ dots, n-1 \}}}$,

con miembros decidibles, y esos árboles contienen entonces elementos de tamaño finito arbitrario grande. El lema Débil de Kőnigs establece: Para tal , siempre existe un camino infinito en , es decir, una secuencia infinita tal que todos sus segmentos iniciales son parte del árbol. En matemáticas inversas, la aritmética de segundo orden no se prueba . Para entender esto, tenga en cuenta que existen árboles computables para los cuales no existe tal ruta computable a través de ellos. Para probar esto, uno enumera las secuencias computables parciales y luego diagonaliza todas las secuencias computables totales en una secuencia computable parcial . Entonces se puede desplegar un cierto árbol , uno exactamente compatible con los valores aún posibles de todas partes, que por construcción es incompatible con cualquier camino computable total. ${\ Displaystyle {\ mathrm {WKL}}}$${\ Displaystyle T}$${\ Displaystyle \ omega \ a \ {0,1 \}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ Displaystyle {\ mathrm {WKL}}}$${\ Displaystyle K}$${\ Displaystyle d}$${\ Displaystyle K}$${\ Displaystyle d}$

En , el principio implica el principio no constructivo menos limitado de omnisciencia . En un contexto más conservador, son equivalentes asumiendo - (una opción contable muy débil). También es equivalente al teorema del punto fijo de Brouwer y otros teoremas con respecto a los valores de funciones continuas en los reales. El teorema del punto fijo a su vez implica el teorema del valor intermedio , pero tenga en cuenta que los teoremas clásicos pueden traducirse en diferentes variantes cuando se expresan en un contexto constructivo. ${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathrm {WKL}}}$ ${\ displaystyle {\ mathrm {LLPO}}}$${\ Displaystyle \ Pi _ {1} ^ {0}}$${\ Displaystyle {\ mathrm {AC}} _ ​​{\ omega, 2}}$

El se refiere a gráficos infinitos y, por lo tanto, su contrapositivo da una condición para la finitud. Sobre la teoría aritmética clásica , esto da equivalencia a la compacidad de Borel con respecto a las subcubiertas finitas del intervalo unitario real. Una afirmación de existencia estrechamente relacionada que involucra secuencias finitas en un contexto infinito es el teorema del abanico decidible . En realidad, son equivalentes. En , esos son distintos, pero nuevamente asumiendo alguna elección, implica . ${\ Displaystyle {\ mathrm {WKL}}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$${\ displaystyle {\ mathsf {RCA}} _ {0}}$${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathrm {WKL}}}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$

Restringir espacios para eventos

En la siguiente observación, la función y las afirmaciones hechas sobre ellas se entienden nuevamente en el sentido de la teoría de la computabilidad. El operador μ habilita todas las funciones recursivas generales parciales (o programas, en el sentido de que son computables de Turing), incluidas, por ejemplo, las no primitivas pero totales, como la función de Ackermann . La definición del operador implica predicados sobre los naturales, por lo que el análisis teórico de las funciones y su totalidad depende del marco formal en cuestión. De cualquier manera, esos números naturales que, en la teoría de la computabilidad, se consideran índices para las funciones computables que son totales, están en la jerarquía aritmética . Es decir, sigue siendo una subclase de los naturales. Y allí, la totalidad, como un predicado en todos los programas, es famosa por ser computablemente indecidible . ${\ displaystyle {\ mathrm {PA}}}$${\ Displaystyle \ Pi _ {2} ^ {0}}$

Una tesis constructiva de Church no clásica , según la suposición de su antecedente, se refiere a las definiciones de predicado (y por lo tanto aquí funciones de conjunto) que son demostrablemente totales y postula que corresponden a programas computables. Adoptar el postulado lo convierte en un conjunto "escaso", como se ve desde la teoría de conjuntos clásica. Ver subresponsabilidad . ${\ Displaystyle {\ mathrm {CT}}}$${\ Displaystyle \ omega \ a \ omega}$

El postulado sigue siendo aritmética o elección intuicionista consistente. Pero contradice principios clásicamente válidos como y , que se encuentran entre los principios más débiles que se discuten a menudo. ${\ Displaystyle {\ mathrm {CT}}}$${\ displaystyle {\ mathrm {LLPO}}}$${\ displaystyle {\ mathrm {FAN}} _ {\ Delta}}$

Inducción

Inducción matemática

En secciones anteriores, la Separación acotada ya estableció la validez de la inducción para definiciones acotadas. En el lenguaje establecido, los principios de inducción pueden leerse con el antecedente definido como más arriba. Es instructivo observar que una proposición en el consecuente , como , aquí expresada usando notación de clase que involucra una subclase que puede no constituir un conjunto - lo que significa que muchos axiomas no se aplicarán - y la llanura son solo dos formas de formular la misma afirmación deseada (una -conjunción indexada de afirmaciones aquí, en particular.) Por lo tanto, un marco teórico establecido con Separación simplemente acotada puede fortalecerse a través de esquemas de inducción aritmética para predicados ilimitados. ${\ Displaystyle \ mathrm {Ind} (A) \ implica \ omega \ subconjunto A}$ ${\ Displaystyle \ mathrm {Ind} (A)}$${\ Displaystyle \ omega \ subset \ {n \ in \ omega \ mid y ^ {\ {0,1, \ dots, n-1 \}} {\ text {es un conjunto}} \}}$${\ Displaystyle \ forall (n \ in \ omega) .y ^ {\ {0,1, \ dots, n-1 \}} {\ text {es un conjunto}}}$${\ Displaystyle n}$

El principio de iteración para las funciones de conjunto mencionado anteriormente, alternativamente a la exponenciación, también está implícito en el esquema de inducción completo sobre la estructura de uno que modela los naturales (por ejemplo ). Este es también el principio aritmético de primer orden para demostrar más funciones en total que las que lo hace. A menudo se formula directamente en términos de predicados, como sigue. Considere el esquema - : ${\ Displaystyle \ omega}$${\ displaystyle {\ mathsf {PRA}}}$${\ Displaystyle \ omega}$${\ Displaystyle {\ mathrm {Ind}}}$

Esquema de axioma de inducción matemática completa : para cualquier predicado en , ${\ Displaystyle \ phi}$${\ Displaystyle \ omega}$ ${\ Displaystyle {\ Big (} \ phi (0) \ \ land \ \ forall (k \ in \ omega). {\ big (} \ phi (k) \ implica \ phi (Sk) {\ big)} { \ Big)} \ implica \ forall (n \ in \ omega). \ Phi (n)}$

Aquí el 0 denota lo anterior y el conjunto denota el conjunto sucesor de , con . Por Axiom of Infinity arriba, nuevamente es miembro de . ${\ Displaystyle \ {\}}$${\ Displaystyle Sn}$${\ Displaystyle n \ in \ omega}$${\ Displaystyle n \ en Sn}$${\ Displaystyle \ omega}$

Como se indica en la sección sobre Elección, los principios de inducción también están implícitos en varias formas de principios de elección. El esquema de inducción completo está implícito en el esquema de separación completo.

Para probar la existencia de un cierre transitivo para cada conjunto con respecto a , se necesita al menos un esquema de iteración acotado. Vale la pena señalar que en el programa de aritmética predicativa, el esquema de inducción matemático completo ha sido criticado por ser posiblemente impredicativo , cuando los números naturales se definen como el objeto que cumple este esquema. ${\ Displaystyle \ in}$

Establecer inducción

La inducción de conjunto completo en prueba la inducción matemática completa sobre los números naturales. De hecho, da inducción sobre ordinales y aritmética ordinal. No se requiere reemplazo para probar la inducción sobre el conjunto de naturales, pero sí lo es para su aritmética modelada dentro de la teoría de conjuntos. ${\ Displaystyle {\ mathsf {ECST}}}$

El axioma más fuerte , entonces dice lo siguiente: ${\ Displaystyle \ in}$${\ Displaystyle {\ mathrm {Ind}}}$

Esquema de axioma de inducción de conjuntos : para cualquier predicado , ${\ Displaystyle \ phi}$ ${\ Displaystyle {\ Big (} \ forall s. \, {\ big (} \ forall (x \ in s). \ \ phi (x) {\ big)} \ implica \ phi (s) {\ Big) } \ implica \ para todo y. \ phi (y)}$

Aquí se sostiene trivialmente y corresponde al "caso inferior" en el marco estándar. La variante del Axioma solo para fórmulas acotadas también se estudia de forma independiente y puede derivarse de otros axiomas. ${\ Displaystyle \ forall x \ in \ {\}. \ phi (x)}$

El axioma permite definiciones de funciones de clase mediante recursividad transfinita . El estudio de los diversos principios que otorgan definiciones de conjuntos por inducción, es decir, definiciones inductivas, es un tema principal en el contexto de la teoría de conjuntos constructiva y sus fortalezas comparativamente débiles . Esto también es válido para sus contrapartes en la teoría de tipos.

El axioma de regularidad junto con la separación limitada / ilimitada implica la inducción de conjuntos, pero también limitada / ilimitada , por lo que la regularidad no es constructiva. Por el contrario, junto con la inducción de conjuntos implica regularidad. ${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathrm {LEM}}}$

Metalogic

Esto ahora cubre variantes de los ocho axiomas de Zermelo-Fraenkel . De hecho, la extensionalidad, el emparejamiento, la unión y el reemplazo son idénticos. Infinity se expresa en una formulación fuerte e implica Emty Set, como en el caso clásico. La separación, clásicamente declarada de forma redundante, no está implícita de manera constructiva en Reemplazo. Sin la Ley del Medio Excluido , la teoría aquí carece, en su forma clásica, de Separación completa, Powerset y Regularidad.

La teoría no supere la fuerza consistencia de Heyting aritmética pero añadiendo en esta etapa podría conducir a una teoría más allá de la fuerza de la típica teoría de tipos : Suponiendo separación en forma irrestricta, a continuación, añadir a da una teoría que demuestra los mismos teoremas como menos regularidad! Por lo tanto, agregar Separación y Regularidad a ese marco da una opción completa y agregarle Opción da . ${\ Displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ displaystyle {\ mathrm {LEM}}}$${\ Displaystyle {\ mathsf {ECST}} + {\ mathrm {Exp}}}$${\ Displaystyle {\ mathsf {ZF}}}$${\ Displaystyle {\ mathsf {ZF}}}$${\ Displaystyle {\ mathsf {ZFC}}}$

La fuerza teórica de la prueba adicional obtenida con la inducción en el contexto constructivo es significativa, incluso si eliminar la regularidad en el contexto de no reduce la fuerza teórica de la prueba. Aczel fue también uno de los principales desarrolladores de la teoría de conjuntos no fundamentada , que rechaza este último axioma. ${\ Displaystyle {\ mathsf {ZF}}}$

Colección fuerte

Con todos los axiomas debilitados de y ahora yendo más allá de esos axiomas que también se ven en el enfoque tipificado de Myhill, considere la teoría con Exponenciación ahora fortalecida por el esquema de colección . Se trata de una propiedad para las relaciones, dando lugar a un formato algo repetitivo en su formulación de primer orden. ${\ Displaystyle {\ mathsf {ZF}}}$

Esquema axiomático de Strong Collection: para cualquier predicado , ${\ Displaystyle \ phi}$ ${\ Displaystyle \ forall a. \ \ {\ Big (} \ forall (x \ in a). \ existe y. \ phi (x, y) {\ Big)} \ implica \ existe b. {\ Big (} \ forall (x \ en a). \ existe (y \ en b). \ phi (x, y) \ \ land \ \ forall (y \ in b). \ existe (x \ en a). \ phi ( x, y) {\ Big)}}$

Establece que si hay una relación entre conjuntos que es total sobre un determinado conjunto de dominio (es decir, tiene al menos un valor de imagen para cada elemento en el dominio), entonces existe un conjunto que contiene al menos una imagen debajo de cada elemento del dominio. Y esta formulación establece además que solo esas imágenes son elementos de ese conjunto de codominio. La última cláusula hace que el axioma, en este contexto constructivo, sea más fuerte que la formulación estándar de Colección. Garantiza que no sobrepase el codominio de y, por lo tanto, el axioma expresa cierto poder de un procedimiento de Separación. ${\ Displaystyle \ phi}$${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle \ phi}$${\ Displaystyle b}$${\ Displaystyle \ phi}$

El axioma es una alternativa al esquema de Reemplazo y de hecho lo reemplaza, debido a que no requiere que la definición de relación binaria sea ​​funcional.

Por regla general, las cuestiones de cardinalidad moderada son más sutiles en un entorno constructivo. Como la aritmética está bien disponible aquí, la teoría tiene productos dependientes, demuestra que la clase de todos los subconjuntos de números naturales no puede ser subcontable y también demuestra que las uniones contables de los espacios funcionales de los conjuntos contables siguen siendo contables.

Metalogic

Esta teoría sin separación ilimitada y conjunto de poder "ingenuo" disfruta de varias propiedades agradables. Por ejemplo, tiene la propiedad de existencia : si, para cualquier propiedad , la teoría prueba que existe un conjunto que tiene esa propiedad, es decir, si la teoría prueba el enunciado , entonces también hay una propiedad que describe de manera única tal instancia de conjunto. Es decir, la teoría también prueba . Esto se puede comparar con la aritmética de Heyting, donde los teoremas se realizan mediante números naturales concretos y tienen estas propiedades. En la teoría de conjuntos, el papel lo desempeñan los conjuntos definidos. Por el contrario, recuerde que en , el axioma de elección implica el teorema del buen ordenamiento , de modo que se demuestra formalmente que existen ordenamientos totales con el mínimo de elementos para subconjuntos de conjuntos como , incluso si no se puede demostrar tal ordenamiento. ${\ displaystyle {\ mathrm {LEM}}}$${\ Displaystyle \ Phi}$${\ Displaystyle \ existe x. \ Phi (x)}$${\ Displaystyle \ Psi}$${\ Displaystyle \ existe! x. \ Psi (x) \ land \ Phi (x)}$${\ Displaystyle {\ mathsf {ZFC}}}$${\ Displaystyle \ mathbb {R}}$

Constructivo Zermelo – Fraenkel

Se puede acercar más al conjunto de poder sin perder una interpretación teórica del tipo. La teoría conocida como los axiomas anteriores más una forma más fuerte de exponenciación. Es adoptando la siguiente alternativa, que nuevamente puede verse como una versión constructiva del axioma de Power set : ${\ Displaystyle {\ mathsf {CZF}}}$

Esquema de axioma de la colección de subconjuntos: para cualquier predicado , ${\ Displaystyle \ phi}$ ${\ Displaystyle \ forall a. \ forall b. \ \ \ existe u. \ forall z. {\ big (} \ forall (x \ in a). \ existe (y \ in b). \ phi (x, y , z) {\ grande)} \ implica \ existe (v \ en u). {\ grande (} \ forall (x \ en a). \ existe (y \ en v). \ phi (x, y, z ) \; \ tierra \; \ forall (y \ in v). \ existe (x \ in a). \ phi (x, y, z) {\ big)}}$

Este esquema de axioma de la colección de subconjuntos es equivalente a un axioma alternativo de plenitud único y algo más claro. Con este fin, let es la clase de todas las relaciones totales entre una y B , esta clase se da como ${\ Displaystyle a \ Sigma {b}}$

${\ Displaystyle r \ in a \ Sigma {b} \ iff {\ big (} \ forall (x \ in a). \ exist (y \ in b). \ langle x, y \ rangle \ in r {\ big )} \, \ land \, {\ big (} \ forall (p \ en r). \ existe (x \ en a). \ existe (y \ in b) .p = \ langle x, y \ rangle { \grande )}}$

Con esto, declara , una alternativa a Subset Collection. Garantiza que exista al menos algún conjunto que contenga una buena cantidad de las relaciones deseadas. Más concretamente, entre dos conjuntos cualesquiera y , hay un conjunto que contiene una subrelación total para cualquier relación total de a . ${\ displaystyle {\ mathrm {Plenitud}}}$${\ Displaystyle c \ subconjunto a \ Sigma {b}}$${\ Displaystyle a}$${\ Displaystyle b}$${\ Displaystyle c}$${\ Displaystyle s}$${\ Displaystyle r}$${\ Displaystyle a}$${\ Displaystyle b}$

Axioma de plenitud:

${\ Displaystyle \ forall a. \ forall b. \ \ \ existe (c \ subset a \ Sigma {b}). \ forall (r \ in a \ Sigma {b}). \ existe (s \ in c). s \ subconjunto r}$

El axioma de Plenitud está a su vez implícito en el llamado Axioma de Presentación sobre secciones, que también se puede formular categoría teóricamente .

La plenitud implica la propiedad de refinamiento binario necesaria para demostrar que la clase de cortes de Dedekind es un conjunto. Esto no requiere inducción o recolección.

En esta teoría no se pueden derivar ni la linealidad de los ordinales ni la existencia de conjuntos de potencias de conjuntos finitos. Asumir cualquiera implica Poder en este contexto.

Metalogic

Esta teoría carece de la propiedad de existencia debido al esquema, pero en 1977 Aczel demostró que todavía se puede interpretar en la teoría de tipos de Martin-Löf , (utilizando el enfoque de proposiciones como tipos ) proporcionando lo que ahora se considera un modelo estándar de la teoría de tipos. . Esto se hace en términos de imágenes de sus funciones, así como una justificación constructiva y predicativa bastante directa, mientras se conserva el lenguaje de la teoría de conjuntos. Este modelo contable valida muchos principios de elección . Con un modelo teórico de tipo, tiene una modesta fortaleza teórica de prueba, ver : ordinal de Bachmann-Howard . ${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathsf {CZF}}}$ ${\ Displaystyle {\ mathsf {IKP}}}$

NB: Rompiendo con ZF

Se puede agregar además la afirmación no clásica de que todos los conjuntos son subcontables como axioma. Entonces es un conjunto (por el infinito y la exponenciación) mientras que la clase o incluso probablemente no es un conjunto, según el argumento diagonal de Cantor . Entonces, esta teoría rechaza lógicamente a Powerset y . ${\ Displaystyle \ omega \ a \ omega}$${\ Displaystyle {\ mathcal {P}} \ omega}$${\ Displaystyle {\ mathcal {P}} \ {0 \}}$${\ displaystyle {\ mathrm {LEM}}}$

En 1989, Ingrid Lindström demostró que los conjuntos no bien fundamentados obtenidos al reemplazar el equivalente del Axioma de Fundación (Inducción) por el axioma anti-fundación de Aczel ( ) también se pueden interpretar en la teoría de tipos de Martin-Löf. ${\ Displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathsf {CZFA}}}$

Zermelo-Fraenkel intuicionista

La teoría es con el conjunto estándar de Separación y Poder . ${\ Displaystyle {\ mathsf {IZF}}}$${\ Displaystyle {\ mathsf {CZF}}}$

Aquí, en lugar del esquema Axiom de reemplazo , uno puede usar el

Esquema de axioma de colección : para cualquier predicado , ${\ Displaystyle \ phi}$ ${\ Displaystyle \ forall z. {\ big (} \ forall (x \ in z). \ exist y. \ phi (x, y) {\ big)} \ implica \ existe w. \ forall (x \ in z ). \ existe (y \ en w). \ phi (x, y)}$

Mientras que el axioma de reemplazo requiere que la relación sea funcional sobre el conjunto (como en, porque cada adentro está asociado exactamente uno ), el axioma de colección no lo hace. Simplemente requiere que haya asociado al menos uno , y afirma la existencia de un conjunto que recopila al menos uno para cada uno . junto con la Colección implica Reemplazo. ${\ Displaystyle \ phi}$${\ Displaystyle z}$${\ Displaystyle x}$${\ Displaystyle z}$${\ Displaystyle y}$${\ Displaystyle y}$${\ Displaystyle y}$${\ Displaystyle x}$${\ displaystyle {\ mathrm {LEM}}}$

Como tal, puede verse como la variante más sencilla de sin . ${\ Displaystyle {\ mathsf {IZF}}}$${\ Displaystyle {\ mathsf {ZF}}}$${\ displaystyle {\ mathrm {LEM}}}$

La teoría es consistente con ser subcountable , así como con la tesis de Church números funciones teóricas. Pero, como se indicó anteriormente, la propiedad de subcontabilidad no se puede adoptar para todos los conjuntos, dado que la teoría demuestra ser un conjunto. ${\ Displaystyle \ omega \ a \ omega}$${\ Displaystyle {\ mathcal {P}} \ omega}$

Metalogic

Cambiando el esquema de Axioma de Reemplazo al esquema de Axioma de Colección, la teoría resultante tiene la Propiedad de Existencia Numérica .

Incluso sin , la fuerza teórica de la prueba de es igual a la de . ${\ displaystyle {\ mathrm {LEM}}}$${\ Displaystyle {\ mathsf {IZF}}}$${\ Displaystyle {\ mathsf {ZF}}}$

Si bien se basa en la lógica intuicionista más que en la clásica, se considera impredicativo . Permite la formación de conjuntos utilizando el axioma de separación con cualquier proposición, incluidos los que contienen cuantificadores que no están acotados. Por tanto, se pueden formar nuevos conjuntos en términos del universo de todos los conjuntos. Además, el axioma del conjunto de poder implica la existencia de un conjunto de valores de verdad . En presencia del medio excluido, este conjunto existe y tiene dos elementos. En ausencia de él, el conjunto de valores de verdad también se considera impredicativo. ${\ Displaystyle {\ mathsf {ZF}}}$

Historia

En 1973, John Myhill propuso un sistema de teoría de conjuntos basado en la lógica intuicionista tomando el fundamento más común , y desechando el axioma de elección y la ley del medio excluido , dejando todo lo demás como está. Sin embargo, las diferentes formas de algunos de los axiomas que son equivalentes en el marco clásico no son equivalentes en el marco constructivo, y algunas formas lo implican . En esos casos, las formulaciones intuicionísticamente más débiles se adoptaron para la teoría de conjuntos constructiva. ${\ Displaystyle {\ mathsf {ZFC}}}$${\ Displaystyle {\ mathsf {ZFC}}}$${\ displaystyle {\ mathrm {LEM}}}$

Z intuicionista

Nuevamente en el extremo más débil, como con su contraparte histórica, la teoría de conjuntos de Zermelo , se puede denotar por la teoría intuicionista establecida como pero sin Reemplazo, Colección o Inducción. ${\ Displaystyle {\ mathsf {IZ}}}$${\ Displaystyle {\ mathsf {IZF}}}$

KP intuicionista

Mencionemos otra teoría muy débil que se ha investigado, a saber, la teoría de conjuntos intuicionista (o constructiva) de Kripke-Platek . La teoría no solo tiene restringida la Separación sino también la Colección, es decir, es similar pero con Inducción en lugar de Reemplazo completo. Es especialmente débil cuando se estudia sin Infinity. La teoría no encaja en la jerarquía presentada anteriormente, simplemente porque tiene el esquema Axiom de Inducción de conjuntos desde el principio. Esto habilita teoremas que involucran la clase de ordinales. ${\ Displaystyle {\ mathsf {IKP}}}$${\ Displaystyle {\ mathsf {BCST}}}$

Teorías ordenadas

Teoría de conjuntos constructiva

Tal como lo presentó, el sistema de Myhill es una teoría que utiliza lógica constructiva de primer orden con identidad y tres tipos , a saber, conjuntos, números naturales y funciones . Sus axiomas son: ${\ Displaystyle {\ mathsf {CST}}}$

• El axioma de extensionalidad habitual para conjuntos, así como uno para funciones, y el axioma habitual de unión .
• El axioma de separación restringida o predicativa, que es una forma debilitada del axioma de separación de la teoría de conjuntos clásica, que requiere que cualquier cuantificación esté limitada a otro conjunto, como se discutió.
• Una forma del axioma del infinito que afirma que la colección de números naturales (para los que introduce una constante ) es de hecho un conjunto.${\ Displaystyle \ omega}$
• El axioma de exponenciación, afirmando que para dos conjuntos cualesquiera, hay un tercer conjunto que contiene todas (y sólo) las funciones cuyo dominio es el primer conjunto y cuyo rango es el segundo conjunto. Ésta es una forma muy debilitada del axioma de poder establecido en la teoría de conjuntos clásica, a la que Myhill, entre otros, objetó sobre la base de su impredicatividad .

Y además:

• Los axiomas habituales de Peano para los números naturales.
• Axiomas que afirman que el dominio y el rango de una función son ambos conjuntos. Además, un axioma de no elección afirma la existencia de una función de elección en los casos en que la elección ya está hecha. Juntos, estos actúan como el axioma de reemplazo habitual en la teoría de conjuntos clásica.

Se puede identificar aproximadamente la fuerza de esta teoría con una subteoría constructiva al compararla con las secciones anteriores. ${\ Displaystyle {\ mathsf {ZF}}}$

Y finalmente la teoría adopta

• Un axioma de elección dependiente , que es mucho más débil que el axioma de elección habitual .

Teoría de conjuntos del estilo Bishop

La teoría de conjuntos en el sabor de la escuela constructivista de Errett Bishop refleja la de Myhill, pero está configurada de una manera que los conjuntos vienen equipados con relaciones que gobiernan su discreción. Comúnmente, se adopta la elección dependiente.

En este contexto, se ha desarrollado mucho análisis y teoría de módulos .

Teorías de categorías

No todas las teorías lógicas formales de conjuntos necesitan axiomizar directamente el predicado de pertenencia binaria " ". Y una teoría elemental de las categorías de conjunto ( ), por ejemplo, capturar pares de mapeos componibles entre objetos, también se puede expresar con una lógica de fondo constructiva ( ). La teoría de categorías puede establecerse como una teoría de flechas y objetos, aunque son posibles las axiomatizaciones de primer orden solo en términos de flechas. ${\ Displaystyle \ in}$${\ Displaystyle {\ mathsf {ETCS}}}$${\ Displaystyle {\ mathsf {CETCS}}}$

Los buenos modelos de teorías de conjuntos constructivos en la teoría de categorías son los pretopos mencionados en la sección Exponenciación, que posiblemente también requieran suficientes proyectivos , un axioma sobre las "presentaciones" sobreyectivas de conjuntos, que implica la elección dependiente contable.

Más allá de eso, los topoi también tienen lenguajes internos que pueden ser intuicionistas en sí mismos y capturar una noción de conjuntos .

Ver también

• Matemáticas constructivas
• Teoría de tipos intuicionistas
• Análisis ordinal
• La impredicatividad
• Propiedad de existencia
• Ley del medio excluido
• Responsabilidad

Referencias

Otras lecturas

• Troelstra, Anne ; van Dalen, Dirk (1988). Constructivismo en matemáticas, vol. 2 . Estudios de Lógica y Fundamentos de las Matemáticas. pag. 619 . ISBN 978-0-444-70358-3.
• Aczel, P. y Rathjen, M. (2001). Notas sobre la teoría de conjuntos constructiva . Informe técnico 40, 2000/2001. Instituto Mittag-Leffler, Suecia.

enlaces externos

• Laura Crosilla, Teoría de conjuntos: ZF constructiva e intuitiva , Enciclopedia de filosofía de Stanford , 20 de febrero de 2009
• Benno van den Berg, Teoría de conjuntos constructiva: una descripción general , diapositivas de Heyting dag, Ámsterdam, 7 de septiembre de 2012