Teoría de conjuntos constructiva

Axiomatic set theories based on the principles of mathematical constructivism

La teoría de conjuntos axiomática constructiva es una aproximación al constructivismo matemático siguiendo el programa de la teoría de conjuntos axiomática . Generalmente se utiliza 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 teorías de tipos . ${\displaystyle =}$ ${\displaystyle \in }$

Además de rechazar el principio del medio excluido ( ), las teorías constructivas de conjuntos a menudo requieren que algunos cuantificadores lógicos en sus axiomas se establezcan acotados . Este último está motivado por resultados ligados a la impredicabilidad . ${\displaystyle {\mathrm {PEM} }}$

Introducción

Perspectiva constructiva

Preliminar sobre el uso de la lógica intuicionista

La lógica de las teorías de conjuntos discutidas aquí es constructiva porque rechaza el principio del tercero excluido , es decir, que la disyunción se cumple automáticamente para todas las proposiciones . A esto también se le suele llamar ley del tercero excluido ( ) en contextos donde se supone. Constructivamente, como regla general, para probar el tercero excluido de una proposición , es decir, para probar la disyunción particular , es necesario probar explícitamente o . Cuando se establece cualquiera de estas pruebas, se dice que la proposición es decidible, y esto implica lógicamente que la disyunción se cumple. De manera similar y más común, se dice que un predicado for en un dominio es decidible cuando el enunciado más complejo es demostrable. Los axiomas no constructivos pueden permitir pruebas que afirmen formalmente la decidibilidad de tal (y/o ) en el sentido de que resultan ser el medio excluido de (resp. la afirmación que utiliza el cuantificador anterior) sin demostrar la verdad de ninguno de los lados de la(s) disyunción(es) . Este suele ser el caso en la lógica clásica. Por el contrario, las teorías axiomáticas consideradas constructivas tienden a no permitir muchas pruebas clásicas de enunciados que involucran propiedades que son comprobadamente indecidibles computacionalmente . ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle \phi \lor \neg \phi }$ ${\displaystyle \phi }$ ${\displaystyle {\mathrm {LEM} }}$ ${\displaystyle P}$ ${\displaystyle P\lor \neg P}$ ${\displaystyle P}$ ${\displaystyle \neg P}$ ${\displaystyle Q(x)}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle \forall (x\in X).{\big (}Q(x)\lor \neg Q(x){\big )}}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle P}$

La ley de no contradicción es un caso especial de la forma proposicional del modus ponens . Usar el primero con cualquier enunciado negado implica una ley de De Morgan válida ya en la lógica mínima más conservadora . En palabras, la lógica intuicionista todavía postula: es imposible descartar una proposición y descartar su negación a la vez y, por lo tanto, el rechazo de cualquier enunciado intermedio excluido instanciado para una proposición individual es inconsistente. Aquí la doble negación captura que el enunciado de disyunción ahora probado nunca puede descartarse o rechazarse, incluso en casos en los que la disyunción puede no ser demostrable (por ejemplo, demostrando uno de los disyuntos, decidiendo así ) a partir de los axiomas supuestos. ${\displaystyle \neg P}$ ${\displaystyle \neg \neg (P\lor \neg P)}$ ${\displaystyle P}$

De manera más general, las teorías matemáticas constructivas tienden a demostrar reformulaciones clásicamente equivalentes de los 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 la eliminación de la doble negación y sus consecuencias se suponen legales, son al mismo tiempo clásicamente equivalentes a la clásica. declaración. La diferencia es que las pruebas constructivas son más difíciles de encontrar.

La lógica intuicionista que subyace a las teorías de conjuntos analizadas aquí, a diferencia de la lógica mínima, todavía permite la eliminación de la doble negación para proposiciones individuales para las cuales se cumple el término medio excluido. A su vez, las formulaciones de teoremas sobre objetos finitos tienden a no diferir de sus contrapartes clásicas. Dado un modelo de todos los números naturales, el equivalente para los predicados, es decir, el principio de Markov , no se cumple automáticamente, pero puede considerarse como un principio adicional. ${\displaystyle P}$

En un dominio habitado y mediante explosión , la disyunción implica la reivindicación de existencia , que a su vez implica . Clásicamente, estas implicaciones son siempre reversibles. Si una de las primeras es válida desde el punto de vista clásico, puede valer la pena intentar establecerla en la segunda forma. Para el caso especial en el que se rechaza, se trata de una afirmación de existencia contraejemplo , que generalmente es constructivamente más fuerte que una afirmación de rechazo : ejemplificar algo que es contradictorio, por supuesto, significa que no es el caso que se cumple para todos los posibles . Pero también se puede demostrar que sostener para todos conduciría lógicamente a una contradicción sin la ayuda de un contraejemplo específico, e incluso sin poder construir uno. En el último caso, constructivamente, aquí no se estipula ningún derecho de existencia. ${\displaystyle P\lor \exists (x\in X).\neg Q(x)}$ ${\displaystyle \exists (x\in X).(Q(x)\to P)}$ ${\displaystyle {\big (}\forall (x\in X).Q(x){\big )}\to P}$ ${\displaystyle P}$ ${\displaystyle \exists (x\in X).\neg Q(x)}$ ${\displaystyle \neg \forall (x\in X).Q(x)}$ ${\displaystyle t}$ ${\displaystyle Q(t)}$ ${\displaystyle Q}$ ${\displaystyle x}$ ${\displaystyle Q}$ ${\displaystyle x}$

Restricciones impuestas a una teoría de conjuntos.

En comparación con la contraparte clásica, generalmente es menos probable que se demuestre la existencia de relaciones que no pueden realizarse. Una restricción a la lectura constructiva de la existencia a priori 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 significa total ). Esto a menudo se debe a que el predicado en una posible definición de casos puede no ser decidible. Al adoptar la definición estándar de igualdad de conjuntos a través de la extensionalidad, el axioma de elección completo es un principio no constructivo que implica las fórmulas permitidas en el esquema de separación adoptado, según el teorema de Diaconescu . Se aplican resultados similares para la afirmación de existencia del axioma de regularidad , como se muestra a continuación. Este último tiene un sustituto inductivo clásicamente equivalente . De modo que un desarrollo genuinamente intuicionista de la teoría de conjuntos requiere reformular algunos axiomas estándar para convertirlos en otros clásicamente equivalentes. Aparte de las demandas de computabilidad y las reservas sobre la impredicatividad, ^[1] la cuestión técnica sobre qué axiomas no lógicos extienden efectivamente la lógica subyacente de una teoría también es un tema de investigación por derecho propio. ${\displaystyle f\subset X\times Y}$ ${\displaystyle {\mathrm {PEM} }}$

metalógico

Dado que ya surgen proposiciones computablemente indecidibles en la aritmética de Robinson , incluso la separación predicativa permite definir subconjuntos difíciles de alcanzar fácilmente. En marcado contraste con el marco clásico, las teorías constructivas de conjuntos pueden cerrarse bajo la regla de que cualquier propiedad que sea decidible para todos los conjuntos ya es equivalente a una de las dos triviales, o . También se puede considerar que la línea real es indescomponible en este sentido. La indecidibilidad de las disyunciones también afecta las afirmaciones sobre órdenes totales como la de todos los números ordinales , expresada por la demostrabilidad y el rechazo de las cláusulas en el orden que define la disyunción . Esto determina si la relación es tricotómica . Una teoría debilitada de los ordinales, a su vez, afecta la fuerza teórica de la prueba definida en el análisis ordinal . ${\displaystyle \top }$ ${\displaystyle \bot }$ ${\displaystyle (\alpha \in \beta )\lor (\alpha =\beta )\lor (\beta \in \alpha )}$

A cambio, las teorías constructivas de conjuntos pueden exhibir atractivas propiedades de existencia y disyunción , como resulta familiar del estudio de las teorías aritméticas constructivas. Éstas son características de una teoría fija que relacionan metalógicamente juicios de proposiciones demostrables en la teoría. Particularmente bien estudiadas están aquellas características que pueden expresarse en la aritmética de Heyting , con cuantificadores de números y que a menudo pueden realizarse mediante números, como se formaliza en la teoría de la prueba . En particular, esas son la propiedad de existencia numérica y la propiedad disyuntiva estrechamente relacionada, además de estar cerradas bajo la regla de Church , lo que demuestra que cualquier función dada es computable . ^[2]

Una teoría de conjuntos no sólo expresa teoremas sobre números, por lo que se puede considerar una propiedad de existencia fuerte, más general, que es más difícil de conseguir, como se analizará más adelante. Una teoría tiene esta propiedad si se puede establecer lo siguiente: Para cualquier propiedad , si la teoría prueba que existe un conjunto que tiene esa propiedad, es decir, si la teoría afirma la existencia, entonces también hay una propiedad que describe de manera única dicho conjunto. instancia. Más formalmente, para cualquier predicado hay un predicado tal que ${\displaystyle \phi }$ ${\displaystyle \psi }$ ${\displaystyle \phi }$ ${\displaystyle \psi }$

${\displaystyle {\mathsf {T}}\vdash \exists x.\phi (x)\implies {\mathsf {T}}\vdash \exists !x.\phi (x)\land \psi (x)}$

El papel análogo al de los números realizados en aritmética lo desempeñan aquí conjuntos definidos cuya existencia se ha demostrado mediante (o según) la teoría. Las cuestiones relativas a la fuerza de la teoría axiomática de conjuntos y su relación con la construcción de términos son sutiles. Si bien muchas teorías discutidas tienden a tener todas las propiedades numéricas, la propiedad de existencia puede estropearse fácilmente, como se discutirá más adelante. Se han formulado formas más débiles de propiedades de existencia.

De hecho, algunas teorías con una lectura clásica de la existencia también pueden restringirse para exhibir la propiedad de existencia fuerte. En la teoría de conjuntos de Zermelo-Fraenkel, en la que todos los conjuntos se consideran definibles ordinales , una teoría denotada , no existen conjuntos sin tal definibilidad. La propiedad también se aplica a través del postulado del universo construible en . Por el contrario, considere la teoría dada por más el postulado completo del axioma de existencia de elección : recuerde que esta colección de axiomas prueba el teorema del buen orden , lo que implica que existen buenos ordenamientos para cualquier conjunto. En particular, esto significa que existen formalmente relaciones que establecen el buen ordenamiento de (es decir, la teoría afirma la existencia de un elemento mínimo para todos los subconjuntos de con respecto a esas relaciones). Esto a pesar del hecho de que se sabe que la definibilidad de tal ordenamiento es independiente de . Esto último implica que para ninguna fórmula particular en el lenguaje de la teoría la teoría prueba que el conjunto correspondiente es una relación de reales bien ordenada. De esta manera se demuestra formalmente la existencia de un subconjunto con la propiedad de ser una relación de buen orden, pero al mismo tiempo no se puede definir ningún conjunto particular para el cual se pueda validar la propiedad. ${\displaystyle {\mathsf {ZF}}+({\mathrm {V} }={\mathrm {HOD} })}$ ${\displaystyle {\mathsf {ZF}}+({\mathrm {V} }={\mathrm {L} })}$ ${\displaystyle {\mathsf {ZFC}}}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle W\subset {\mathbb {R} }\times {\mathbb {R} }}$ ${\displaystyle {\mathbb {R} }}$ ${\displaystyle {\mathbb {R} }}$ ${\displaystyle {\mathsf {ZFC}}}$ ${\displaystyle \psi }$ ${\displaystyle {\mathsf {ZFC}}}$ ${\displaystyle W\subset {\mathbb {R} }\times {\mathbb {R} }}$ ${\displaystyle W}$

Principios anticlásicos

Como se mencionó anteriormente, una teoría constructiva puede exhibir la propiedad de existencia numérica, , para algún número y donde denota el numeral correspondiente en la teoría formal. Aquí uno debe distinguir cuidadosamente entre implicaciones demostrables entre dos proposiciones, y las propiedades de la forma de una teoría . Cuando se adopta un esquema metalógicamente establecido de este último tipo como regla de inferencia del propio cálculo de prueba y no se puede probar nada nuevo, se dice que la teoría está cerrada bajo esa regla. ${\displaystyle {\mathsf {T}}}$ ${\displaystyle {\mathsf {T}}\vdash \exists e.\psi (e)\implies {\mathsf {T}}\vdash \psi ({\underline {\mathrm {e} }})}$ ${\displaystyle {\mathrm {e} }}$ ${\displaystyle {\underline {\mathrm {e} }}}$ ${\displaystyle {\mathsf {T}}\vdash P\to Q}$ ${\displaystyle {\mathsf {T}}\vdash P\implies {\mathsf {T}}\vdash Q}$ ${\displaystyle {\mathsf {T}}}$

En cambio, se puede considerar adjuntar la regla correspondiente a la propiedad metateórica como una implicación (en el sentido de " ") a , como un esquema de axioma o en forma cuantificada. Una situación comúnmente estudiada es la de un fijo que exhibe la propiedad metateórica del siguiente tipo: para un caso de alguna colección de fórmulas de una forma particular, aquí capturada a través de y , se estableció la existencia de un número tal que . Aquí se puede entonces postular , donde el límite es una variable numérica en el lenguaje de la teoría. Por ejemplo, la regla de Church es una regla admisible en la aritmética de Heyting de primer orden y, además, el correspondiente principio de tesis de Church puede adoptarse consistentemente como un axioma. La nueva teoría con el principio agregado es anticlásica, en el sentido de que puede que ya no sea consistente adoptarla también . De manera similar, al adjuntar el principio del medio excluido a alguna teoría , la teoría así obtenida puede resultar en enunciados nuevos, estrictamente clásicos, y esto puede estropear algunas de las propiedades metateóricas que se establecieron previamente para . De tal manera, no puede adoptarse en , también conocida como aritmética de Peano . ${\displaystyle \to }$ ${\displaystyle {\mathsf {T}}}$ ${\displaystyle {\mathsf {T}}}$ ${\displaystyle \phi }$ ${\displaystyle \psi }$ ${\displaystyle {\mathrm {e} }}$ ${\displaystyle {\mathsf {T}}\vdash \phi \implies {\mathsf {T}}\vdash \psi ({\underline {\mathrm {e} }})}$ ${\displaystyle \phi \to \exists (e\in {\mathbb {N} }).\psi (e)}$ ${\displaystyle e}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathrm {CT} }_{0}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {T}}}$ ${\displaystyle {\mathsf {T}}}$ ${\displaystyle {\mathrm {CT} }_{0}}$ ${\displaystyle {\mathsf {HA}}+{\mathrm {PEM} }}$ ${\displaystyle {\mathsf {PA}}}$

Esta subsección se centrará en las teorías de conjuntos con cuantificación sobre una noción completamente formal de un espacio de secuencias infinitas, es decir, un espacio funcional, como se presentará más adelante. Una traducción del gobierno de Church al lenguaje de la teoría misma puede leerse aquí

${\displaystyle \forall (f\in {\mathbb {N} }^{\mathbb {N} }).\exists (e\in {\mathbb {N} }).{\Big (}\forall (n\in {\mathbb {N} }).\exists (w\in {\mathbb {N} }).T(e,n,w)\land U(w,f(n)){\Big )}}$

El predicado T de Kleene junto con la extracción del resultado expresa que cualquier número de entrada que se asigne al número se considera, a través de , que es un mapeo computable. Aquí ahora denotamos un modelo de teoría de conjuntos de los números naturales estándar y es un índice con respecto a una enumeración de programa fija. Se han utilizado variantes más fuertes, que extienden este principio a funciones definidas en dominios de baja complejidad. El principio rechaza la decidibilidad para el predicado definido como , expresando que es el índice de una función computable que se detiene en su propio índice. También se pueden considerar formas más débiles, de doble negación, del principio, que no requieren la existencia de una implementación recursiva para cada , pero que aún hacen inconsistentes los principios que afirman la existencia de funciones que probadamente no tienen realización recursiva. Algunas formas de la tesis de Church como principio son incluso consistentes con la clásica y débil teoría aritmética de segundo orden , un subsistema de la teoría de primer orden de dos ordenes . ${\displaystyle n}$ ${\displaystyle f(n)}$ ${\displaystyle w}$ ${\displaystyle {\mathbb {N} }}$ ${\displaystyle e}$ ${\displaystyle f\in {\mathbb {N} }^{X}}$ ${\displaystyle X\subset {\mathbb {N} }}$ ${\displaystyle Q(e)}$ ${\displaystyle \exists (w\in {\mathbb {N} }).T(e,e,w)}$ ${\displaystyle e}$ ${\displaystyle f}$ ${\displaystyle {\mathsf {RCA}}_{0}}$ ${\displaystyle {\mathsf {Z}}_{2}}$

La colección de funciones computables es clásicamente subcontable , lo que clásicamente es lo mismo que ser contable. Pero las teorías de conjuntos clásicas generalmente afirmarán que también cumplen otras funciones además de las computables. Por ejemplo, hay una prueba de que existen funciones totales (en el sentido de la teoría de conjuntos) que no pueden ser capturadas por una máquina de Turing . Tomando en serio el mundo computable como ontología, un excelente ejemplo de una concepción anticlásica relacionada con la escuela markoviana es la subcontabilidad permitida de varias colecciones incontables. Al adoptar la subcontabilidad de la colección de todas las secuencias interminables de números naturales ( ) como axioma en una teoría constructiva, la "pequeñez" (en términos clásicos) de esta colección, en algunas realizaciones teóricas establecidas, ya está capturada por la teoría. sí mismo. Una teoría constructiva tampoco puede adoptar axiomas clásicos ni anticlásicos y, por lo tanto, permanecer agnóstica ante cualquiera de las dos posibilidades. ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$

Los principios constructivos ya prueban para cualquiera . Y así, para cualquier elemento dado de , el enunciado intermedio excluido correspondiente de la proposición no puede negarse. De hecho, para cualquier , dado , por no contradicción es imposible descartar y descartar su negación a la vez, y la regla de De Morgan relevante se aplica como se indicó anteriormente. Pero en algunos casos una teoría también puede permitir la afirmación de rechazo . Adoptar esto no requiere proporcionar un testimonio particular del fracaso del tercero excluido para la proposición particular , es decir, un testimonio de lo inconsistente . Los predicados en un dominio infinito corresponden a problemas de decisión . Motivado por problemas comprobadamente indecidibles y computables , uno puede rechazar la posibilidad de la decidibilidad de un predicado sin hacer también ninguna afirmación de existencia . Como otro ejemplo, tal situación se aplica en el análisis intuicionista brouweriano , en un caso en el que el cuantificador abarca infinitas secuencias binarias interminables y establece que una secuencia es cero en todas partes. En cuanto a esta propiedad de ser identificada de manera concluyente como la secuencia que es siempre constante, la adopción del principio de continuidad de Brouwer descarta estrictamente que esto pueda resultar decidible para todas las secuencias. ${\displaystyle \forall (x\in X).\neg \neg {\big (}Q(x)\lor \neg Q(x){\big )}}$ ${\displaystyle Q}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle Q(x)}$ ${\displaystyle \neg \forall (x\in X).{\big (}Q(x)\lor \neg Q(x){\big )}}$ ${\displaystyle t\in X}$ ${\displaystyle Q(t)}$ ${\displaystyle \neg {\big (}Q(t)\lor \neg Q(t){\big )}}$ ${\displaystyle Q(x)}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle Q(x)}$ ${\displaystyle x}$

Entonces, en un contexto constructivo con la llamada lógica no clásica como se usa aquí, uno puede adoptar consistentemente axiomas que están en contradicción con las formas cuantificadas de término medio excluido, pero también no constructivos en el sentido computable o medido por meta- propiedades de existencia lógica discutidas anteriormente. De esa manera, una teoría de conjuntos constructiva también puede proporcionar el marco para estudiar teorías no clásicas, por ejemplo anillos que modelan análisis infinitesimales suaves .

Historia y descripción general

Históricamente, el tema de la teoría constructiva de conjuntos (a menudo también " ") comenzó con el trabajo de John Myhill sobre las teorías también llamadas y . ^{[3] [4] [5]} En 1973, había propuesto la primera como una teoría de conjuntos de primer orden basada en la lógica intuicionista, tomando el fundamento más común y descartando el axioma de elección, así como el principio del medio excluido. , dejando inicialmente todo lo demás como está. Sin embargo, diferentes formas de algunos de los axiomas que son equivalentes en el contexto clásico no son equivalentes en el contexto constructivo, y algunas formas implican , como se demostrará. En esos casos, se adoptaron en consecuencia las formulaciones intuicionistamente más débiles. El sistema, mucho más conservador, es también una teoría de primer orden, pero de varios tipos y de cuantificación limitada, cuyo objetivo es proporcionar una base formal para el programa de matemáticas constructivas de Errett Bishop . ${\displaystyle {\mathsf {CST}}}$ ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle {\mathsf {CST}}}$ ${\displaystyle {\mathsf {ZFC}}}$ ${\displaystyle {\mathsf {ZFC}}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {CST}}}$

La discusión principal presenta una secuencia de teorías en el mismo lenguaje que conducen al bien estudiado Peter Aczel [ ^6] y más allá. Muchos resultados modernos se remontan a Rathjen y sus estudiantes. también se caracteriza por las dos características presentes también en la teoría de Myhill: por un lado, utiliza la separación predicativa en lugar del esquema de separación completo e ilimitado. La acotación puede manejarse como una propiedad sintáctica o, alternativamente, las teorías pueden ampliarse de manera conservadora con un predicado de acotación superior y sus axiomas. En segundo lugar, se descarta el axioma impredicativo de Powerset, generalmente en favor de axiomas relacionados pero más débiles. La forma fuerte se utiliza de manera muy casual en la topología general clásica . Sumándose a una teoría aún más débil que la recupera , como se detalla a continuación. ^[7] El sistema, que ha llegado a ser conocido como teoría intuicionista de conjuntos de Zermelo-Fraenkel ( ), es una teoría de conjuntos sólida sin . Es similar a , pero menos conservador o predicativo . La teoría denotada es la versión constructiva de la teoría clásica de conjuntos de Kripke-Platek sin una forma de Powerset y donde incluso el axioma de colección es acotado. ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {IKP}}}$ ${\displaystyle {\mathsf {KP}}}$

Modelos

Muchas teorías estudiadas en la teoría constructiva de conjuntos son meras restricciones de la teoría de conjuntos de Zermelo-Fraenkel ( ) ${\displaystyle {\mathsf {ZF}}}$ con respecto a su axioma así como a su lógica subyacente. Estas teorías también pueden interpretarse en cualquier modelo de . ${\displaystyle {\mathsf {ZF}}}$

La aritmética de Peano es biinterpretable con la teoría dada por menos Infinito y sin conjuntos infinitos, más la existencia de todas las clausuras transitivas . (Esto último también está implícito después de promover el esquema Regularidad de inducción de conjuntos , que se analiza a continuación). Asimismo, la aritmética constructiva también puede tomarse como una disculpa para la mayoría de los axiomas adoptados en : La aritmética de Heyting es biinterpretable con una teoría de conjuntos constructiva débil. ^[8] como también se describe en el artículo sobre . Se puede caracterizar aritméticamente una relación de pertenencia " " y con ella demostrar, en lugar de la existencia de un conjunto de números naturales , que todos los conjuntos en su teoría están en biyección con un natural (finito) de von Neumann , un principio denotado . Este contexto valida aún más la Extensionalidad, el Emparejamiento, la Unión, la Intersección Binaria (que está relacionada con el esquema Axioma de separación predicativa ) y el esquema de Inducción de Conjuntos. Tomados como axiomas, los principios antes mencionados constituyen una teoría de conjuntos que ya es idéntica a la teoría dada por menos la existencia de pero más como axioma. Todos esos axiomas se analizan en detalle a continuación. De manera relacionada, también demuestra que los conjuntos hereditariamente finitos cumplen todos los axiomas anteriores. Este es un resultado que persiste al pasar hacia y menos el Infinito. ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle \in }$ ${\displaystyle \omega }$ ${\displaystyle {\mathrm {V} }={\mathrm {Fin} }}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle \omega }$ ${\displaystyle {\mathrm {V} }={\mathrm {Fin} }}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {ZF}}}$

En lo que respecta a las realizaciones constructivas, existe una teoría de la realizabilidad relevante . De manera relacionada, la teoría constructiva de Aczel de Zermelo-Fraenkel ha sido interpretada en teorías de tipo Martin-Löf , como se esboza en la sección sobre . De esta manera, los teoremas demostrables en esta y en teorías de conjuntos más débiles son candidatos para una realización por computadora. ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {CZF}}}$

También se han introducido modelos previos a las teorías constructivas de conjuntos. Estos son análogos a los modelos presheaf para la teoría intuicionista de conjuntos desarrollados por Dana Scott en la década de 1980. ^{[9] [10]} Se han identificado modelos de realizabilidad dentro del topos efectivo que, por ejemplo, validan al mismo tiempo la separación total, la elección dependiente relativizada , la independencia de la premisa para los conjuntos, pero también la subcontabilidad de todos los conjuntos, el principio de Markov y la tesis de Church. en la formulación para todos los predicados. ^[11] ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathrm {RDC} }}$ ${\displaystyle {\mathrm {IP} }}$ ${\displaystyle {\mathrm {MP} }}$ ${\displaystyle {\mathrm {CT} _{0}}}$

Notación

En una teoría de conjuntos axiomática , los conjuntos son entidades que exhiben propiedades. Pero hay entonces una relación más compleja entre el concepto de conjunto y la lógica. Por ejemplo, la propiedad de ser un número natural menor que 100 puede reformularse como miembro del conjunto de números con esa propiedad. Los axiomas de la teoría de conjuntos gobiernan la existencia de conjuntos y, por tanto, gobiernan qué predicados pueden materializarse como entidad en sí misma, en este sentido. La especificación también está directamente gobernada por los axiomas, como se analiza a continuación. Para una consideración práctica, considere la propiedad de ser una secuencia de resultados al lanzar una moneda que, en general, muestra más cara que cruz. Esta propiedad se puede utilizar para separar un subconjunto correspondiente de cualquier conjunto de secuencias finitas de lanzamientos de moneda. De manera relacionada, la formalización teórica de medidas de un evento probabilístico se basa explícitamente en conjuntos y proporciona muchos más ejemplos.

Esta sección presenta el lenguaje objeto y las nociones auxiliares utilizadas para formalizar esta materialización.

Idioma

Los símbolos conectivos proposicionales utilizados para formar fórmulas sintácticas son estándar. Los axiomas de la teoría de conjuntos proporcionan un medio para demostrar la igualdad " " de conjuntos y ese símbolo puede, por abuso de notación , usarse para clases. Un conjunto en el que el predicado de igualdad es decidible también se llama discreto . La negación " " de la igualdad a veces se denomina negación de la igualdad y comúnmente se escribe " ". Sin embargo, en un contexto con relaciones de separación , por ejemplo cuando se trata de secuencias, este último símbolo a veces también se usa para algo diferente. ${\displaystyle =}$ ${\displaystyle \neg }$ ${\displaystyle \neq }$

El tratamiento común, como también se adopta aquí, formalmente sólo extiende la lógica subyacente mediante un predicado binario primitivo de la teoría de conjuntos, " ". Al igual que con la igualdad, la negación de la elementoidad " " a menudo se escribe " ". ${\displaystyle \in }$ ${\displaystyle \in }$ ${\displaystyle \notin }$

variables

A continuación, el griego denota una proposición o predicado variable en esquemas de axiomas y /o se usa para tales predicados en particular. La palabra "predicado" también se usa a veces indistintamente con "fórmulas", incluso en el caso unario . ${\displaystyle \phi }$ ${\displaystyle P}$ ${\displaystyle Q}$

Los cuantificadores solo abarcan conjuntos y estos se indican con letras minúsculas. Como es común, se pueden usar corchetes de argumento para expresar predicados, con el fin de resaltar variables libres particulares en su expresión sintáctica, como en " ". Existencia única aquí significa . ${\displaystyle Q(z)}$ ${\displaystyle \exists !x.Q(x)}$ ${\displaystyle \exists x.\forall y.{\big (}y=x\leftrightarrow Q(y){\big )}}$

Clases

Como también es común, se utiliza la notación de creación de conjuntos para las clases , que, en la mayoría de los contextos, no forman parte del lenguaje objeto pero se utilizan para una discusión concisa. En particular, se pueden introducir declaraciones de notación de la clase correspondiente mediante " ", con el fin de expresar cualquiera como . Se pueden utilizar predicados lógicamente equivalentes para introducir la misma clase. También se escribe como abreviatura de . Por ejemplo, se puede considerar y esto también se denota . ${\displaystyle A=\{z\mid Q(z)\}}$ ${\displaystyle Q(a)}$ ${\displaystyle a\in A}$ ${\displaystyle \{z\in B\mid Q(z)\}}$ ${\displaystyle \{z\mid z\in B\land Q(z)\}}$ ${\displaystyle \{z\in B\mid z\notin C\}}$ ${\displaystyle B\setminus C}$

Se abrevia poco a poco . La noción sintáctica de cuantificación limitada en este sentido puede desempeñar un papel en la formulación de esquemas de axiomas, como se verá en la discusión de axiomas a continuación. Exprese la afirmación de la subclase , es decir , por . Para un predicado , trivialmente . Y así se sigue . La noción de cuantificadores acotados por subconjuntos, como en , también se ha utilizado en la investigación teórica de conjuntos, pero no se destacará más aquí. ${\displaystyle \forall z.{\big (}z\in A\to Q(z){\big )}}$ ${\displaystyle \forall (z\in A).Q(z)}$ ${\displaystyle \exists z.{\big (}z\in A\land Q(z){\big )}}$ ${\displaystyle \exists (z\in A).Q(z)}$ ${\displaystyle \forall (z\in A).z\in B}$ ${\displaystyle \forall z.(z\in A\to z\in B)}$ ${\displaystyle A\subset B}$ ${\displaystyle Q}$ ${\displaystyle \forall z.{\big (}(z\in B\land Q(z))\to z\in B{\big )}}$ ${\displaystyle \{z\in B\mid Q(z)\}\subset B}$ ${\displaystyle \forall (z\subset A).z\in B}$

Si existe comprobadamente un conjunto dentro de una clase, es decir , entonces se le llama habitado . También se puede utilizar la cuantificación para expresar esto como . Entonces se ha demostrado que la clase no es el conjunto vacío, que se presenta a continuación. Si bien es clásicamente equivalente, constructivamente no vacío es una noción más débil con dos negaciones y debería llamarse no deshabitado . Desgraciadamente, la palabra para designar la noción más útil de "habitado" rara vez se utiliza en las matemáticas clásicas. ${\displaystyle \exists z.(z\in A)}$ ${\displaystyle A}$ ${\displaystyle \exists (z\in A).(z=z)}$ ${\displaystyle A}$

Dos formas de expresar que las clases son disjuntas capturan muchas de las reglas de negación intuicionistamente válidas: . Usando la notación anterior, esta es una equivalencia puramente lógica y en este artículo la proposición además se podrá expresar como . ${\displaystyle {\big (}\forall (x\in A).x\notin B{\big )}\leftrightarrow \neg \exists (x\in A).x\in B}$ ${\displaystyle A\cap B=\{\}}$

Una subclase se llama separable si el predicado de pertenencia relativizado es decidible, es decir, si se cumple. También se le llama decidible si la superclase se desprende del contexto; a menudo, este es el conjunto de números naturales. ${\displaystyle A\subset B}$ ${\displaystyle B}$ ${\displaystyle \forall (x\in B).x\in A\lor x\notin A}$

Equivalencia extensional

Denota por la afirmación que expresa que dos clases tienen exactamente los mismos elementos, es decir , o de manera equivalente . Esto no debe confundirse con el concepto de equinumerosidad que también se utiliza a continuación. ${\displaystyle A\simeq B}$ ${\displaystyle \forall z.(z\in A\leftrightarrow z\in B)}$ ${\displaystyle (A\subset B)\land (B\subset A)}$

Con la posición de , la conveniente relación de notación entre y , los axiomas de la forma postulan que la clase de todos los conjuntos para los cuales se cumple en realidad forma un conjunto . De manera menos formal, esto puede expresarse como . Asimismo, la proposición transmite " cuando está entre los conjuntos de la teoría". Para el caso en el que es el predicado trivialmente falso, la proposición equivale a la negación de la afirmación de existencia anterior, expresando la no existencia de como conjunto. ${\displaystyle A}$ ${\displaystyle \{z\mid Q(z)\}}$ ${\displaystyle x\in A}$ ${\displaystyle Q(x)}$ ${\displaystyle \exists a.\forall z.{\big (}z\in a\leftrightarrow Q(z){\big )}}$ ${\displaystyle Q}$ ${\displaystyle \exists a.a\simeq A}$ ${\displaystyle \forall a.(a\simeq A)\to P(a)}$ ${\displaystyle P(A)}$ ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle A}$

En la teoría de conjuntos se utilizan comúnmente otras extensiones de la notación de comprensión de clases, como las anteriores, que dan significado a afirmaciones como " ", etc. ${\displaystyle \{f(z)\mid Q(z)\}\simeq \{\langle x,y,z\rangle \mid T(x,y,z)\}}$

Sintácticamente más general, un conjunto también se puede caracterizar usando otro predicado biario , donde el lado derecho puede depender de la variable real , y posiblemente incluso de la membresía en sí misma. ${\displaystyle w}$ ${\displaystyle R}$ ${\displaystyle \forall x.x\in w\leftrightarrow R(x,w)}$ ${\displaystyle w}$ ${\displaystyle w}$

Subteorías de ZF

Aquí se presenta una serie de axiomas familiares, o sus ligeras reformulaciones relevantes. Se enfatiza cómo la ausencia de en la lógica afecta lo demostrable y se destaca qué axiomas no clásicos son, a su vez, consistentes. ${\displaystyle {\mathrm {PEM} }}$

Igualdad

Utilizando la notación introducida anteriormente, el siguiente axioma proporciona un medio para demostrar la igualdad " " de dos conjuntos , de modo que mediante sustitución, cualquier predicado acerca de se traduce en uno de . Según las propiedades lógicas de la igualdad, la dirección inversa de la implicación postulada se cumple automáticamente. ${\displaystyle =}$ ${\displaystyle x}$ ${\displaystyle y}$

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 derive de axiomas) en la interpretación de Brouwer-Heyting-Kolmogorov , esto significa haberlo probado o haberlo rechazado. Como no puede separarse de , es decir, puede no ser decidible para todos los elementos de , 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 \{z\in B\mid Q(z)\}}$ ${\displaystyle B}$ ${\displaystyle Q}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Considere un predicado que se cumple comprobadamente para todos los elementos de un conjunto , de modo que , y suponga que se establece que la clase del lado derecho es un conjunto. Tenga en cuenta que, incluso si este conjunto de la derecha informalmente también se vincula 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 derecho se considera igual al conjunto de la derecha. uno en el lado izquierdo. Este análisis anterior también muestra que un enunciado de la forma , que en notación de clases informal puede expresarse como , se expresa entonces de manera equivalente como . Esto significa que establecer tales teoremas (por ejemplo, los demostrables mediante inducción matemática completa) permite sustituir la subclase de en el lado izquierdo de la igualdad por just , en cualquier fórmula. ${\displaystyle Q}$ ${\displaystyle y}$ ${\displaystyle y\simeq \{z\in y\mid Q(z)\}}$ ${\displaystyle Q}$ ${\displaystyle \forall (x\in w).Q(x)}$ ${\displaystyle w\subset \{x\mid Q(x)\}}$ ${\displaystyle \{x\in w\mid Q(x)\}=w}$ ${\displaystyle \forall }$ ${\displaystyle w}$ ${\displaystyle w}$

Tenga en cuenta que la adopción de " " como símbolo en una teoría de lógica de predicados hace que la igualdad de dos términos sea una expresión libre de cuantificadores. ${\displaystyle =}$

Aproximaciones alternativas

Si bien se adopta con frecuencia, este axioma ha sido criticado en el pensamiento constructivo, ya que efectivamente colapsa propiedades definidas de manera diferente, o al menos los conjuntos vistos como la extensión de estas propiedades, una noción fregiana .

En cambio, las teorías de tipos modernas pueden apuntar a definir la equivalencia demandada " " en términos de funciones, ver, por ejemplo, equivalencia de tipos . El concepto relacionado de extensionalidad de función 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 separación de los elementos de todos y cada uno de los conjuntos discutidos. Pero también en un enfoque de conjuntos que enfatiza la separación se puede utilizar la definición anterior en términos de subconjuntos para caracterizar una noción de igualdad " " de esos subconjuntos. De manera relacionada, una noción vaga de complementación de dos subconjuntos se da cuando dos miembros cualesquiera están demostrablemente separados entre sí. La colección de pares complementarios se comporta algebraicamente bien. ${\displaystyle z\in x}$ ${\displaystyle x}$ ${\displaystyle \simeq }$ ${\displaystyle u\subset x}$ ${\displaystyle v\subset x}$ ${\displaystyle s\in u}$ ${\displaystyle t\in v}$ ${\displaystyle \langle u,v\rangle }$

Fusionar conjuntos

Defina la notación de clases para el emparejamiento de algunos elementos determinados mediante disyunciones. Por ejemplo, es la declaración sin cuantificador , y también dice , y así sucesivamente. ${\displaystyle z\in \{a,b\}}$ ${\displaystyle (z=a)\lor (z=b)}$ ${\displaystyle z\in \{a,b,c\}}$ ${\displaystyle (z=a)\lor (z=b)\lor (z=c)}$

Otros dos postulados básicos de existencia dados algunos otros conjuntos son los siguientes. En primer lugar,

Dadas las definiciones anteriores, se expande a , por lo que se hace uso de igualdad y disyunción. El axioma dice que para dos conjuntos cualesquiera y , hay al menos un conjunto que contiene al menos esos dos conjuntos. ${\displaystyle \{x,y\}\subset p}$ ${\displaystyle \forall z.(z=x\lor z=y)\to z\in p}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle p}$

Con la separación acotada a continuación, la clase también existe como un conjunto. Denota por el modelo estándar de pares ordenados , de modo que, por ejemplo, denota otra fórmula acotada en el lenguaje formal de la teoría. ${\displaystyle \{x,y\}}$ ${\displaystyle \langle x,y\rangle }$ ${\displaystyle \{\{x\},\{x,y\}\}}$ ${\displaystyle q=\langle x,y\rangle }$

Y luego, usando una cuantificación existencial y una conjunción,

diciendo que para cualquier conjunto , hay al menos un conjunto , que contiene todos los miembros de sus miembros . El conjunto mínimo de este tipo es la unión . ${\displaystyle x}$ ${\displaystyle u}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle y}$

Los dos axiomas comúnmente se formulan de manera más fuerte, en términos de " " en lugar de simplemente " ", aunque esto es técnicamente redundante en el contexto de : Como el axioma de separación a continuación se formula con " ", para declaraciones se puede derivar la equivalencia, dada la La teoría permite la separación usando . En los casos en los que se trata de un enunciado existencial, como aquí en el axioma de unión, también existe otra formulación que utiliza un cuantificador universal. ${\displaystyle \leftrightarrow }$ ${\displaystyle \to }$ ${\displaystyle {\mathsf {BCST}}}$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \exists t.\forall z.\phi (z)\to z\in t}$ ${\displaystyle \phi }$ ${\displaystyle \phi }$

También utilizando la separación acotada, los dos axiomas que acabamos de enunciar juntos implican la existencia de una unión binaria de dos clases y , cuando se ha establecido que son conjuntos, se denotan por o . Para un conjunto fijo , para validar la pertenencia a la unión de dos conjuntos dados y , es necesario validar la parte del axioma, lo que se puede hacer validando la disyunción de los predicados que definen los conjuntos y , para . En cuanto a los conjuntos asociados, se hace validando la disyunción . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \bigcup \{a,b\}}$ ${\displaystyle a\cup b}$ ${\displaystyle z}$ ${\displaystyle z\in a\cup b}$ ${\displaystyle y=a}$ ${\displaystyle y=b}$ ${\displaystyle z\in y}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle z}$ ${\displaystyle z\in a\lor z\in b}$

La unión y otras notaciones que forman conjuntos también se utilizan para las clases. Por ejemplo, la proposición está escrita . Vamos ahora . Teniendo en cuenta , la capacidad de decisión de la membresía en , es decir, la declaración potencialmente independiente , también se puede expresar como . Pero, en cuanto a cualquier enunciado intermedio excluido, se cumple la doble negación del último: esa unión no está habitada por ... Esto demuestra que la partición también es una noción más complicada y constructiva. ${\displaystyle z\in A\land z\notin C}$ ${\displaystyle z\in A\setminus C}$ ${\displaystyle B\subset A}$ ${\displaystyle z\in A}$ ${\displaystyle B}$ ${\displaystyle z\in B\lor z\notin B}$ ${\displaystyle z\in B\cup (A\setminus B)}$ ${\displaystyle z}$

Establecer existencia

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

La introducción del símbolo (como notación abreviada para expresiones que involucran propiedades caracterizantes) se justifica ya que se puede demostrar la unicidad de este conjunto. Como es falso para cualquiera , el axioma dice entonces : ${\displaystyle \{\}}$ ${\displaystyle y\in \{\}}$ ${\displaystyle y}$ ${\displaystyle \exists x.x\simeq \{\}}$

Escribe para , que es igual a , es decir . Asimismo, escriba para , que es igual a , es decir . Una proposición simple y comprobadamente falsa es, por ejemplo, correspondiente a en el modelo aritmético estándar. Nuevamente, aquí los símbolos como se tratan como notación conveniente y cualquier proposición realmente se traduce en una expresión que usa solo " " y símbolos lógicos, incluidos los cuantificadores. Acompañado de un análisis metamatemático de que las capacidades de las nuevas teorías son equivalentes de manera efectiva, también se pueden considerar extensiones formales mediante símbolos como estos . ${\displaystyle 1}$ ${\displaystyle S0}$ ${\displaystyle \{\{\}\}}$ ${\displaystyle \{1\}}$ ${\displaystyle 2}$ ${\displaystyle S1}$ ${\displaystyle \{\{\},\{\{\}\}\}}$ ${\displaystyle \{0,1\}}$ ${\displaystyle \{\}\in \{\}}$ ${\displaystyle 0<0}$ ${\displaystyle \{\}}$ ${\displaystyle \in }$ ${\displaystyle 0}$

De manera más general, para un conjunto , defina el conjunto sucesor como . La interacción de la operación sucesora con la relación de membresía tiene una cláusula recursiva, en el sentido de que . Por la reflexividad de la igualdad, y en particular está siempre habitada. ${\displaystyle x}$ ${\displaystyle Sx}$ ${\displaystyle x\cup \{x\}}$ ${\displaystyle (y\in Sx)\leftrightarrow (y\in x\lor y=x)}$ ${\displaystyle x\in Sx}$ ${\displaystyle Sx}$

BCST

Lo siguiente hace uso de esquemas de axiomas , es decir, axiomas para alguna colección de predicados. Algunos de los esquemas de axiomas establecidos también permitirán cualquier colección de parámetros establecidos (es decir, cualquier variable con nombre en particular ). Es decir, se permiten instanciaciones del esquema en las que el predicado (algún particular ) también depende de un número de variables establecidas adicionales y el enunciado del axioma se entiende con las correspondientes clausuras universales externas adicionales (como en ). ${\displaystyle v_{0},v_{1},\dots ,v_{n}}$ ${\displaystyle \phi }$ ${\displaystyle \forall v_{0}.\forall v_{1}.\cdots \forall v_{n}.}$

Separación

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 llamado axioma de separación "completo" está debilitado. Más allá de los cuatro axiomas anteriores, postula la separación predicativa y el esquema de reemplazo. ${\displaystyle {\mathsf {BCST}}}$

Este axioma equivale a postular la existencia de un conjunto obtenido por la intersección de cualquier conjunto y cualquier clase descrita predicativamente . Para cualquier conjunto demostrado, cuando el predicado se toma como , se obtiene la intersección binaria de conjuntos y se escribe . La intersección corresponde a la conjunción de forma análoga a como la unión corresponde a la disyunción. ${\displaystyle s}$ ${\displaystyle y}$ ${\displaystyle \{x\mid \phi (x)\}}$ ${\displaystyle z}$ ${\displaystyle \phi (x):=x\in z}$ ${\displaystyle s=y\cap z}$

Cuando el predicado se toma como negación , se obtiene el principio de diferencia, concediendo la existencia de cualquier conjunto . Tenga en cuenta que los conjuntos como o siempre están vacíos. Entonces, como se señaló, de la Separación y la existencia de al menos un conjunto (por ejemplo, Infinito a continuación) seguirá la existencia del conjunto vacío (también denotado ). Dentro de este contexto conservador , el esquema de separación predicativa es en realidad equivalente al 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 de fórmula. ${\displaystyle \phi (x):=x\notin z}$ ${\displaystyle y\setminus z}$ ${\displaystyle y\setminus y}$ ${\displaystyle \{x\in y\mid \neg (x=x)\}}$ ${\displaystyle \{\}}$ ${\displaystyle 0}$ ${\displaystyle {\mathsf {BCST}}}$

La separación predicativa es un esquema que tiene en cuenta aspectos sintácticos de predicados que definen conjuntos, hasta una equivalencia demostrable. Las fórmulas permitidas se indican con el nivel más bajo en la jerarquía teórica establecida de Lévy . ^[12] Los predicados generales en la teoría de conjuntos nunca están restringidos sintácticamente de tal manera y, por lo tanto, en la práctica, las subclases genéricas de conjuntos siguen siendo parte del lenguaje matemático. Como el alcance de las subclases que son probablemente conjuntos es sensible a los conjuntos que ya existen, este alcance se amplía cuando se agregan más postulados de existencia de conjuntos. ${\displaystyle \Delta _{0}}$

Para una proposición , un tropo recurrente en el análisis constructivo de la teoría de conjuntos es ver el predicado como la subclase del segundo ordinal . Si se puede demostrar que se cumple, o , o , entonces está habitado, vacío (deshabitado) o no vacío (no deshabitado), respectivamente. Claramente, es equivalente tanto a la proposición , como a . Asimismo, es equivalente a y, de manera equivalente, también . Entonces, aquí, ser separable de exactamente significa ... En el modelo de los naturales, si es un número, también expresa que es menor que . La unión que forma parte de la definición anterior de operación sucesora se puede utilizar para expresar la declaración intermedia excluida como . En palabras, es decidible si y sólo si el sucesor de es mayor que el ordinal más pequeño . La proposición se decide de cualquier manera estableciendo cómo es más pequeño: por ser ya más pequeño que , o por ser el predecesor directo de . Otra forma más de expresar el término medio excluido es como la existencia de un número mínimo de miembros de la clase habitada . ${\displaystyle P}$ ${\displaystyle x=0\land P}$ ${\displaystyle B:=\{x\in 1\mid P\}}$ ${\displaystyle 1:=S0=\{0\}}$ ${\displaystyle P}$ ${\displaystyle \neg P}$ ${\displaystyle \neg \neg P}$ ${\displaystyle B}$ ${\displaystyle P}$ ${\displaystyle 0\in B}$ ${\displaystyle B=1}$ ${\displaystyle \neg P}$ ${\displaystyle B=0}$ ${\displaystyle \neg (0\in B)}$ ${\displaystyle B}$ ${\displaystyle 1}$ ${\displaystyle P\lor \neg P}$ ${\displaystyle B}$ ${\displaystyle 0\in B}$ ${\displaystyle 0}$ ${\displaystyle B}$ ${\displaystyle 0\in SB}$ ${\displaystyle P}$ ${\displaystyle B}$ ${\displaystyle 0}$ ${\displaystyle P}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle B}$ ${\displaystyle 0}$ ${\displaystyle SB}$ ${\displaystyle P}$ ${\displaystyle b:=B\cup \{1\}}$

Si el axioma de separación permite la separación con , entonces hay un subconjunto , que puede denominarse valor de verdad asociado con . Se puede demostrar que dos valores de verdad son iguales, como conjuntos, demostrando una equivalencia. En términos de esta terminología, la colección de valores de prueba puede entenderse a priori como rica. Como era de esperar, las proposiciones decidibles tienen uno de un conjunto binario de valores de verdad. La disyunción media excluida para eso también está implícita en la declaración global . ${\displaystyle P}$ ${\displaystyle B}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \forall b.(0\in b)\lor (0\notin b)}$

Sin conjunto universal

Cuando se utiliza la terminología informal de clases, cualquier conjunto también se considera una clase. Al mismo tiempo, surgen las llamadas clases propias que no pueden tener extensión como conjunto. Cuando en una teoría hay una prueba de , entonces debe ser adecuada. (Cuando se adopta la perspectiva de conjuntos, una teoría que tiene separación total, generalmente se piensa que las clases adecuadas son aquellas que son "demasiado grandes" para ser un conjunto. Más técnicamente, son subclases de la jerarquía acumulativa que se extienden más allá de cualquier conjunto. límite ordinal.) ${\displaystyle \neg \exists x.A\subset x}$ ${\displaystyle A}$ ${\displaystyle {\mathsf {ZF}}}$

Según una observación en la sección sobre fusión de conjuntos, no se puede descartar consistentemente que un conjunto sea miembro de una clase de la forma . Una prueba constructiva de que está en esa clase contiene información. Ahora bien, si es un conjunto, entonces se puede demostrar que la clase es adecuada. Lo siguiente demuestra esto en el caso especial cuando está vacío, es decir, cuando el lado derecho es la clase universal. Al ser resultados negativos, se lee como en la teoría clásica. ${\displaystyle A\cup \{x\mid x\notin A\}}$ ${\displaystyle A}$ ${\displaystyle \{x\mid x\notin A\}}$ ${\displaystyle A}$

Lo siguiente es válido para cualquier relación . Da una condición puramente lógica tal que dos términos y no pueden relacionarse entre sí. ${\displaystyle E}$ ${\displaystyle s}$ ${\displaystyle y}$ ${\displaystyle E}$

${\displaystyle {\big (}\forall x.xEs\leftrightarrow (xEy\land \neg xEx){\big )}\to \neg (yEs\lor sEs\lor sEy)}$

Lo más importante aquí es el rechazo de la disyunción final . La expresión no implica una cuantificación ilimitada y, por tanto, está permitida en la separación. La construcción de Russel, a su vez, muestra que . Entonces, para cualquier conjunto , la separación predicativa por sí sola implica que existe un conjunto del que no es miembro . En particular, en esta teoría no puede existir ningún conjunto universal . ${\displaystyle \neg sEy}$ ${\displaystyle \neg (x\in x)}$ ${\displaystyle \{x\in y\mid x\notin x\}\notin y}$ ${\displaystyle y}$ ${\displaystyle y}$

En una teoría que adopta además el axioma de regularidad , como , resulta comprobado que es falso para cualquier conjunto . En este caso, esto significa que el subconjunto es igual a sí mismo y que la clase es el conjunto vacío. ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle x\in x}$ ${\displaystyle x}$ ${\displaystyle \{x\in y\mid x\notin x\}}$ ${\displaystyle y}$ ${\displaystyle \{x\mid x\in x\}}$

Para cualquiera y , el caso especial en la fórmula anterior da ${\displaystyle E}$ ${\displaystyle y}$ ${\displaystyle s=y}$

${\displaystyle \neg {\big (}\forall x.xEy\leftrightarrow \neg xEx{\big )}}$

Esto ya implica que la subclase de la clase universal también es propia. Pero incluso sin regularidad, es coherente que haya una clase adecuada de singletons, cada uno de los cuales contiene exactamente a sí mismo. ${\displaystyle \{x\mid x\notin x\}}$ ${\displaystyle {\mathsf {ZF}}}$

Además, en una teoría con estratificación como Nuevos fundamentos intuicionistas , la expresión sintáctica puede no estar permitida en Separación. A su vez, la prueba anterior de la negación de la existencia de un conjunto universal no puede realizarse en esa teoría. ${\displaystyle x\in x}$

Predicatividad

El esquema de axioma de la separación predicativa también se denomina -separación o separación acotada, como en la separación sólo para cuantificadores acotados por conjuntos. (Nota de advertencia: la nomenclatura de la jerarquía de Lévy es análoga a la jerarquía aritmética , aunque la comparación puede ser sutil: 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 de la jerarquía aritmética tiene varias definiciones comunes, algunas no permiten el uso de algunas funciones totales. Una distinción similar no es relevante en el nivel o superior. Finalmente, tenga en cuenta que una clasificación de una fórmula puede expresarse hasta la equivalencia en la teoría. ${\displaystyle \Delta _{0}}$ ${\displaystyle \Delta _{0}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Delta _{0}}$

El esquema es también la forma en que Mac Lane debilita un sistema cercano a la teoría de conjuntos de Zermelo , en favor de fundamentos matemáticos relacionados con la teoría del topos . También se utiliza en el estudio del carácter absoluto , y allí forma parte de la formulación de la teoría de conjuntos de Kripke-Platek . ${\displaystyle {\mathsf {Z}}}$

La restricción en el axioma también es un control de definiciones impredicativas : en el mejor de los casos, no se debe afirmar la existencia de objetos que no son explícitamente descriptibles, o cuya definición involucra a ellos mismos o hace referencia a una clase adecuada, como cuando una propiedad a verificar involucra un cuantificador universal. . Entonces, en una teoría constructiva sin axioma de potencia set , cuando denota algún predicado 2-ario, generalmente no se debe esperar que una subclase de sea un conjunto, en caso de que esté definido, por ejemplo, como en ${\displaystyle R}$ ${\displaystyle s}$ ${\displaystyle y}$

${\displaystyle \{x\in y\mid \forall t.{\big (}(t\subset y)\to R(x,t){\big )}\}}$,

o mediante definiciones similares que impliquen cualquier cuantificación de los conjuntos . Tenga en cuenta que si se ha comprobado que esta subclase de es un conjunto, entonces este subconjunto en sí también está en el alcance ilimitado de la variable de conjunto . En otras palabras, a medida que se cumple la propiedad de la subclase , este conjunto exacto , definido mediante la expresión , jugaría un papel en su propia caracterización. ${\displaystyle t\subset y}$ ${\displaystyle s}$ ${\displaystyle y}$ ${\displaystyle t}$ ${\displaystyle s\subset y}$ ${\displaystyle s}$ ${\displaystyle R(x,s)}$

Si bien la separación predicativa conduce a que se establezcan menos definiciones de clases dadas, se puede enfatizar que muchas definiciones de clases que son clásicamente equivalentes no lo son cuando se restringe a la lógica más débil. Debido a la potencial indecidibilidad de los predicados generales, la noción de subconjunto y subclase es automáticamente más elaborada en las teorías constructivas de conjuntos que en las clásicas. De esta manera se ha obtenido una teoría más amplia. Esto sigue siendo cierto si se adopta la separación completa, como en la teoría , lo que sin embargo arruina la propiedad de existencia así como las interpretaciones teóricas de tipo estándar, y de esta manera arruina una visión ascendente de los conjuntos constructivos. Además, como la subtipificación no es una característica necesaria de la teoría de tipos constructiva , se puede decir que la teoría de conjuntos constructiva difiere bastante de ese marco. ${\displaystyle {\mathsf {IZF}}}$

Reemplazo

A continuación considere el

Es garantizar la existencia, como conjuntos, del rango de predicados similares a funciones, obtenidos a través de sus dominios. En la formulación anterior, el predicado no está restringido de manera similar al esquema de Separación, pero este axioma ya implica un cuantificador existencial en el antecedente. Por supuesto, también podrían considerarse esquemas más débiles.

Mediante Reemplazo, la existencia de cualquier par también se deriva de la de cualquier otro par particular, como por ejemplo . Pero como la unión binaria utilizada en ya hizo uso del axioma de emparejamiento, este enfoque requiere postular la existencia de sobre la de . En una teoría con el axioma impredicativo de Powerset, la existencia de también se puede demostrar mediante Separación. ${\displaystyle \{x,y\}}$ ${\displaystyle \{0,1\}=2=SS0}$ ${\displaystyle S}$ ${\displaystyle 2}$ ${\displaystyle 0}$ ${\displaystyle 2\subset {\mathcal {P}}{\mathcal {P}}0}$

Con el esquema de Reemplazo, la teoría esbozada hasta ahora demuestra 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. A su vez, para cualquier número fijo (en la metateoría), la expresión del producto correspondiente, digamos , puede construirse como un conjunto. Los requisitos axiomáticos para conjuntos definidos recursivamente en el lenguaje se analizan más adelante. Un conjunto es discreto, es decir, la igualdad de elementos dentro de un conjunto es decidible, si la relación correspondiente como subconjunto de es decidible. ${\displaystyle x\times x\times x\times x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x\times x}$

El reemplazo es relevante para la comprensión de funciones y puede verse como una forma de comprensión de manera más general. Sólo al asumir la Reposición ya implica la Separación total. En , el reemplazo es principalmente importante para demostrar la existencia de conjuntos de alto rango , es decir, a través de instancias del esquema axiomático que relaciona conjuntos relativamente pequeños con otros más grandes . ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle \phi (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$

Las teorías de conjuntos constructivas suelen tener un esquema de axioma de reemplazo, a veces restringido a fórmulas acotadas. Sin embargo, cuando se descartan otros axiomas, este esquema a menudo se fortalece, no más allá de , sino simplemente para recuperar algo de fuerza de demostrabilidad. Existen axiomas tan fuertes que no estropean las fuertes propiedades de existencia de una teoría, como se analiza más adelante. ${\displaystyle {\mathsf {ZF}}}$

Si se ha comprobado que es una función y está equipada con un codominio (todo se analiza en detalle a continuación), entonces la imagen de es un subconjunto de . En otras aproximaciones al concepto de conjunto, la noción de subconjuntos se define en términos de "operaciones", de esta manera. ${\displaystyle i_{X}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle i_{X}}$ ${\displaystyle Y}$

Conjuntos hereditariamente finitos

Los colgantes de elementos de la clase de conjuntos hereditariamente finitos se pueden implementar en cualquier lenguaje de programación común. Los axiomas discutidos anteriormente se abstraen de operaciones comunes en el tipo de datos establecido : el emparejamiento y la unión están relacionados con el anidamiento y el aplanamiento , o la concatenación en conjunto. El reemplazo está relacionado con la comprensión y la separación está relacionada con el filtrado , a menudo más simple . El reemplazo junto con la inducción de conjuntos (que se presenta a continuación) es suficiente para axiomar de manera constructiva y esa teoría también se estudia sin infinito. ${\displaystyle H_{\aleph _{0}}}$ ${\displaystyle H_{\aleph _{0}}}$

Una especie de mezcla entre emparejamiento y unión, un axioma más fácilmente relacionado con el sucesor es el axioma de conjunción . ^{[13] [14]} Estos principios son relevantes para el modelado estándar de ordinales de Neumann individuales . También existen formulaciones de axiomas que combinan Unión y Reemplazo en uno. Si bien postular el reemplazo no es una necesidad en el diseño de una teoría de conjuntos constructiva débil que sea biinterpretable con la aritmética de Heyting , alguna forma de inducción sí lo es. A modo de comparación, 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 simplemente a través de Extensionalidad, Adjunción y Separación completa. ${\displaystyle {\mathsf {HA}}}$

La discusión continúa ahora con axiomas que garantizan la existencia de objetos que, en forma diferente pero relacionada, también se encuentran en teorías de tipos dependientes , a saber, productos y la colección de números naturales como un conjunto completo. Los conjuntos infinitos son particularmente útiles para razonar sobre operaciones aplicadas a secuencias definidas en dominios de índice ilimitados , digamos la diferenciación formal de una función generadora o la suma de dos secuencias de Cauchy.

ECST

Para algún predicado fijo y un conjunto , la declaración expresa que es el más pequeño (en el sentido de " ") entre todos los conjuntos para los cuales es verdadero, y que siempre es un subconjunto de tal . El objetivo del axioma del infinito es obtener eventualmente el conjunto inductivo más pequeño y único . ${\displaystyle I}$ ${\displaystyle a}$ ${\displaystyle I(a)\land {\big (}\forall y.I(y)\to a\subset y{\big )}}$ ${\displaystyle a}$ ${\displaystyle \subset }$ ${\displaystyle y}$ ${\displaystyle I(y)}$ ${\displaystyle y}$

En el contexto de los axiomas comunes de la teoría de conjuntos, una afirmación de infinidad es afirmar que una clase está habitada y también incluye una cadena de membresía (o alternativamente una cadena de superconjuntos). Eso es,

${\displaystyle \exists z.(z\in A)\land \forall (x\in A).\exists (s\in A).x\in s}$.

Más concretamente, denotemos por la propiedad inductiva, ${\displaystyle \mathrm {Ind} _{A}}$

${\displaystyle (0\in A)\land \forall (x\in A).Sx\in A}$.

En términos de un predicado subyacente a la clase so that , este último se traduce en . ${\displaystyle Q}$ ${\displaystyle \forall x.(x\in A)\leftrightarrow Q(x)}$ ${\displaystyle Q(0)\land \forall x.{\big (}Q(x)\to Q(Sx){\big )}}$

Escribe para la intersección general . (Se puede considerar una variante de esta definición que requiere , pero solo usamos esta noción para la siguiente definición auxiliar.) ${\displaystyle \bigcap B}$ ${\displaystyle \{x\mid \forall (y\in B).x\in y\}}$ ${\displaystyle \cap B\subset \cup B}$

Comúnmente se define una clase , la intersección de todos los conjuntos inductivos. (Las variantes de este tratamiento pueden funcionar en términos de una fórmula que depende de un parámetro establecido de modo que .) La clase cumple exactamente todos los que cumplen la propiedad ilimitada . La intención es que si los conjuntos inductivos existen, entonces la clase comparte cada número natural común con ellos, y luego la proposición , por definición de " ", implica que eso es válido para cada uno de estos naturales. Si bien la separación acotada no es suficiente para demostrar que se trata del conjunto deseado, el lenguaje aquí constituye la base para el siguiente axioma, que garantiza la inducción de números naturales para los predicados que constituyen un conjunto. ${\displaystyle \omega =\bigcap \{y\mid \mathrm {Ind} _{y}\}}$ ${\displaystyle w}$ ${\displaystyle \omega \subset w}$ ${\displaystyle \omega }$ ${\displaystyle x}$ ${\displaystyle \forall y.\mathrm {Ind} _{y}\to x\in y}$ ${\displaystyle \omega }$ ${\displaystyle \omega \subset A}$ ${\displaystyle \subset }$ ${\displaystyle Q}$ ${\displaystyle \omega }$

La Teoría de Conjuntos constructiva elemental tiene el axioma de así como el postulado ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle {\mathsf {BCST}}}$

Continuando, se toma el símbolo para denotar el ahora único conjunto inductivo más pequeño, un ordinal de von Neumann ilimitado . Contiene el conjunto vacío y, por cada conjunto de , otro conjunto que contiene un elemento más. ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$

Los símbolos llamados cero y sucesor están en la firma de la teoría de Peano . En , el sucesor definido anteriormente de cualquier número que también esté en la clase se deriva directamente de la caracterización de los naturales mediante nuestro modelo de von Neumann. Dado que el sucesor de tal conjunto se contiene a sí mismo, también se encuentra que ningún sucesor es igual a cero. Entonces, dos de los axiomas de Peano con respecto a los símbolos cero y el de la cercanía de resultan fáciles. En cuarto lugar, en , donde es un conjunto, se puede demostrar que on es una operación inyectiva. ${\displaystyle {\mathsf {BCST}}}$ ${\displaystyle \omega }$ ${\displaystyle S}$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle \omega }$ ${\displaystyle S}$ ${\displaystyle \omega }$

Para algún predicado de conjuntos , la afirmación afirma que es válida para todos los subconjuntos del conjunto de naturales. Y el axioma demuestra ahora que tales conjuntos existen. Esta cuantificación también es posible en aritmética de segundo orden . ${\displaystyle P}$ ${\displaystyle \forall S.(S\subset \omega \to P(S))}$ ${\displaystyle P}$

El orden por pares " " de los naturales se captura por su relación de pertenencia " ". La teoría demuestra que tanto el orden como la relación de igualdad en este conjunto son decidibles. No sólo ningún número es menor que , sino que la inducción implica que entre los subconjuntos de , es exactamente el conjunto vacío el que no tiene miembro menor. La contrapositiva de esto demuestra la existencia del número mínimo doblemente negado para todos los subconjuntos no vacíos de . Otro principio válido también clásicamente equivalente es la existencia del número mínimo para todos los subconjuntos desmontables habitados. Dicho esto, la mera afirmación de existencia para el subconjunto habitado de es equivalente al medio excluido de , y por lo tanto una teoría constructiva no resultará estar bien ordenada . ${\displaystyle <}$ ${\displaystyle \in }$ ${\displaystyle 0}$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle b:=\{z\in 1\mid P\}\cup \{1\}}$ ${\displaystyle \omega }$ ${\displaystyle P}$ ${\displaystyle \omega }$

Formulaciones más débiles del infinito.

Si necesitara motivación, la conveniencia de postular un conjunto ilimitado de números en relación con otras propiedades inductivas queda clara en la discusión de la aritmética en la teoría de conjuntos más adelante. Pero, como es familiar en la teoría clásica de conjuntos, también se pueden formular formas débiles del Infinito. Por ejemplo, uno puede simplemente postular la existencia de algún conjunto inductivo; tal postulado de existencia es suficiente cuando se puede utilizar la separación completa para crear el subconjunto inductivo de números naturales, el subconjunto compartido de todas las clases inductivas. Alternativamente, se pueden adoptar postulados de mera existencia más específicos. De cualquier manera, el conjunto inductivo cumple la siguiente propiedad de existencia del predecesor en el sentido del modelo de von Neumann : ${\displaystyle \exists y.\mathrm {Ind} _{y}}$ ${\displaystyle w}$ ${\displaystyle \Delta _{0}}$

${\displaystyle \forall m.(m\in w)\leftrightarrow {\big (}m=0\lor \exists (p\in w).Sp=m{\big )}}$

Sin hacer uso de la notación para la notación sucesora previamente definida, la igualdad extensil a un sucesor es capturada por . Esto expresa que todos los elementos son iguales o tienen un conjunto predecesor con el que comparten todos los demás miembros . ${\displaystyle Sp=m}$ ${\displaystyle \forall n.(n\in m)\leftrightarrow (n=p\lor n\in p)}$ ${\displaystyle m}$ ${\displaystyle 0}$ ${\displaystyle p\in w}$ ${\displaystyle m}$

Observe que a través de la expresión " " en el lado derecho, la propiedad que caracteriza aquí sintácticamente a sus miembros contiene nuevamente el símbolo mismo. Debido a la naturaleza ascendente de los números naturales, esto es sencillo aquí. Suponiendo la inducción de -set además de , no hay dos conjuntos diferentes que tengan esta propiedad. Tenga en cuenta también que también existen formulaciones más largas de esta propiedad, evitando " " en favor de cuantificadores ilimitados. ${\displaystyle \exists (p\in w)}$ ${\displaystyle w}$ ${\displaystyle m}$ ${\displaystyle w}$ ${\displaystyle \Delta _{0}}$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle \exists (p\in w)}$

Límites numéricos

Al adoptar un axioma de infinito, la cuantificación limitada por conjuntos legal en los predicados utilizados en -Separación permite explícitamente cuantificadores numéricamente ilimitados; los dos significados de "limitado" no deben confundirse. Con la mano, llame a una clase de números acotados si se cumple la siguiente declaración de existencia ${\displaystyle \Delta _{0}}$ ${\displaystyle \omega }$ ${\displaystyle I\subset \omega }$

${\displaystyle \exists (m\in \omega ).\forall (n\in \omega ).(n\in I\to n<m)}$

Se trata de declaraciones de finitud, también formuladas de manera equivalente a través de . De manera similar, para reflejar más de cerca la discusión de funciones a continuación, considere la condición anterior en la forma . Para propiedades decidibles, estas son declaraciones -en aritmética, pero con el Axioma del Infinito, los dos cuantificadores están ligados a conjuntos. ${\displaystyle m\leq n\to n\notin I}$ ${\displaystyle \exists (m\in \omega ).\forall (n\in I).(n<m)}$ ${\displaystyle \Sigma _{2}^{0}}$

Para una clase , la declaración de ilimitación lógicamente positiva ${\displaystyle C}$

${\displaystyle \forall (k\in \omega ).\exists (j\in \omega ).(k\leq j\land j\in C)}$

ahora también es uno de infinito. Es en el caso aritmético decidible. Para validar la infinidad de un conjunto, esta propiedad funciona incluso si el conjunto contiene otros elementos además de una cantidad infinita de miembros de . ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle \omega }$

Inducción moderada en ECST

A continuación, un segmento inicial de los números naturales, es decir, para cualquier conjunto vacío incluido, se denota por . Este conjunto es igual y por lo tanto en este punto " " es mera notación para su predecesor (es decir, no implica función de resta). ${\displaystyle \{n\in \omega \mid n<m\}}$ ${\displaystyle m\in \omega }$ ${\displaystyle \{0,1,\dots ,m-1\}}$ ${\displaystyle m}$ ${\displaystyle m-1}$

Es instructivo recordar la forma en que una teoría con comprensión de conjuntos y extensionalidad termina codificando la lógica de predicados. Como cualquier clase en la teoría de conjuntos, un conjunto puede leerse como correspondiente a predicados de conjuntos. Por ejemplo, un número entero es par si es miembro del conjunto de los números enteros pares, o un número natural tiene un sucesor si es miembro del conjunto de números naturales que tienen un sucesor. Para un ejemplo menos primitivo, arregle algún conjunto y denote la afirmación existencial de que existe el espacio funcional en el ordinal finito . El predicado se denotará a continuación, y aquí el cuantificador existencial no es simplemente uno entre los números naturales, ni está limitado por ningún otro conjunto. Ahora bien, una proposición como el principio de exponenciación finita y, menos formalmente, la igualdad son sólo dos formas de formular el mismo enunciado deseado, es decir, una conjunción indexada de proposiciones existenciales que abarca el conjunto de todas las naturales. A través de la identificación extensional, la segunda forma expresa la afirmación utilizando notación para la comprensión de subclases y el objeto entre corchetes en el lado derecho puede ni siquiera constituir un conjunto. Si esa subclase no es demostrablemente un conjunto, es posible que en realidad no se use en muchas pruebas de principios de la teoría de conjuntos, y puede que no sea posible establecer el cierre universal como un teorema. Por tanto, la teoría de conjuntos puede reforzarse con más axiomas de existencia de conjuntos, que se utilizarán con la separación predicativa acotada , pero también simplemente postulando afirmaciones -más fuertes. ${\displaystyle y}$ ${\displaystyle Q(n)}$ ${\displaystyle y}$ ${\displaystyle \exists h.h\simeq y^{\{0,1,\dots ,n-1\}}}$ ${\displaystyle \forall (n\in \omega ).Q(n)}$ ${\displaystyle \omega =\{n\in \omega \mid Q(n)\}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \forall (n\in \omega ).Q(n)}$ ${\displaystyle \forall }$

La segunda conjunción universalmente cuantificada en el axioma fuerte del Infinito expresa la inducción matemática para todos en el universo del discurso, es decir, para los conjuntos. Esto se debe a que el consecuente de esta cláusula, establece que todos cumplen el predicado asociado. Al poder utilizar la separación predicativa para definir subconjuntos de , la teoría demuestra la inducción para todos los predicados que involucran únicamente cuantificadores limitados por conjuntos. Este papel de los cuantificadores acotados en conjuntos también significa que más axiomas de existencia de conjuntos impactan la solidez de este principio de inducción, motivando aún más los axiomas de espacio funcional y colección que serán el foco del resto del artículo. En particular, ya valida la inducción con cuantificadores sobre los naturales y, por tanto, la inducción como en la teoría aritmética de primer orden . El llamado axioma de inducción matemática completa para cualquier predicado (es decir, clase) expresado mediante el lenguaje de la teoría de conjuntos es mucho más fuerte que el principio de inducción acotada válido en . El antiguo principio de inducción podría adoptarse directamente, reflejando más fielmente la aritmética de segundo orden. En la teoría de conjuntos también se deriva de la separación total (es decir, ilimitada), que dice que todos los predicados de son conjuntos. La inducción matemática también es reemplazada por el axioma de inducción de conjuntos (completo). ${\displaystyle y}$ ${\displaystyle \omega \subset y}$ ${\displaystyle n\in \omega }$ ${\displaystyle \omega }$ ${\displaystyle \phi (n)}$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle \forall }$

Nota de advertencia: al nombrar enunciados de inducción, se debe tener cuidado de no confundir la terminología con las teorías aritméticas. El esquema de inducción de primer orden de la teoría de la aritmética de números naturales afirma la inducción para todos los predicados definibles en el lenguaje de la aritmética de primer orden , es decir, predicados de números justos. Entonces, para interpretar el esquema axioma de , se interpretan estas fórmulas aritméticas. En ese contexto, la cuantificación limitada significa específicamente cuantificación en un rango finito de números. También se puede hablar de la inducción en la teoría de primer orden pero de dos tipos de la llamada aritmética de segundo orden , en una forma explícitamente expresada para subconjuntos de los naturales. Se puede considerar que esa clase de subconjuntos corresponde a una colección de fórmulas más rica que las definibles en aritmética de primer orden. En el programa de matemáticas inversas , todos los objetos matemáticos discutidos están codificados como naturales o subconjuntos de naturales. Los subsistemas de comprensión de muy baja complejidad estudiados en ese marco tienen un lenguaje que no expresa simplemente conjuntos aritméticos , mientras que todos los conjuntos de naturales particulares que tales teorías demuestran existir son sólo conjuntos computables . Los teoremas que contiene pueden ser un punto de referencia relevante para teorías de conjuntos débiles con un conjunto de naturales, separación predicativa y sólo alguna forma más restringida de inducción. La matemática inversa constructiva existe como campo, pero está menos desarrollada que su contraparte clásica. ^[15] además no debe confundirse con la formulación de segundo orden de la aritmética de Peano . Las teorías de conjuntos típicas como la que se analiza aquí también son de primer orden, pero esas teorías no son aritméticas y, por lo tanto, las fórmulas también pueden cuantificar los subconjuntos de los naturales. Al discutir la solidez de los axiomas relacionados con los números, también es importante tener en cuenta que el marco aritmético y el marco teórico establecido no comparten una firma común . Asimismo, siempre se debe tener cuidado con la comprensión de la totalidad de las funciones. En la teoría de la computabilidad , el operador μ habilita todas las funciones recursivas generales parciales (o programas, en el sentido de que son computables por Turing), incluidas algunas, por ejemplo, recursivas no primitivas pero totales, como la función de Ackermann . La definición del operador implica predicados sobre los naturales y, por lo tanto, el análisis teórico de las funciones y su totalidad depende del marco formal y del cálculo de prueba disponible. ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathsf {Z}}_{2}}$ ${\displaystyle {\mathsf {Z}}_{2}}$ ${\displaystyle {\mathsf {Z}}_{2}}$ ${\displaystyle {\mathsf {PA}}_{2}}$ ${\displaystyle {\mathsf {PA}}}$

Funciones

Nota general sobre programas y funciones.

Naturalmente, el significado de las afirmaciones de existencia es un tema de interés en el constructivismo, ya sea para una teoría de conjuntos o cualquier otro marco. Expresemos una propiedad tal que un marco matemático valide lo que equivale al enunciado ${\displaystyle R}$

${\displaystyle \forall (a\in A).\exists (c\in C).R(a,c)}$

Un cálculo de prueba constructiva puede validar tal juicio en términos de programas en dominios representados y algún objeto que represente una asignación concreta , proporcionando una elección particular de valor en ( uno único ), para cada entrada de . Expresado a través de la reescritura , este objeto de función puede entenderse como testigo de la proposición. Consideremos, por ejemplo, las nociones de prueba en la teoría de la realizabilidad o los términos funcionales en una teoría de tipos con una noción de cuantificadores. Este último captura la prueba de una proposición lógica a través de programas a través de la correspondencia Curry-Howard . ${\displaystyle a\mapsto c_{a}}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle \forall (a\in A).R(a,c_{a})}$

Dependiendo del contexto, la palabra "función" puede usarse en asociación con un modelo particular de computación , y esto es a priori más restringido de lo que se analiza en el presente contexto de la teoría de conjuntos. Una noción de programa está formalizada por "funciones" recursivas parciales en la teoría de la computabilidad . Pero tenga en cuenta que aquí la palabra "función" se utiliza de una manera que también comprende funciones parciales , y no sólo "funciones totales". Las comillas se utilizan para mayor claridad aquí, ya que en un contexto de teoría de conjuntos técnicamente no hay necesidad de hablar de funciones totales , porque este requisito es parte de la definición de una función teórica de conjuntos y los espacios de funciones parciales se pueden modelar mediante uniones. Al mismo tiempo, cuando se combinan con una aritmética formal, los programas de funciones parciales proporcionan una noción particularmente clara de totalidad de las funciones. Según el teorema de la forma normal de Kleene , cada función recursiva parcial en los naturales calcula, para los valores donde termina, lo mismo que , para algún índice de programa de función parcial , y cualquier índice constituirá alguna función parcial. Un programa puede asociarse con a y se puede decir que es total siempre que se pruebe una teoría , donde equivale a un programa recursivo primitivo y está relacionado con la ejecución de . Kreisel demostró que la clase de funciones recursivas parciales probadas -total por no se enriquece cuando se suma. ^[16] Como predicado en , esta totalidad constituye un subconjunto indecidible de índices, destacando que el mundo recursivo de funciones entre los naturales ya está capturado por un conjunto dominado por . Como tercera advertencia, tenga en cuenta que esta noción se refiere realmente a programas y varios índices constituirán de hecho la misma función, en el sentido extensional . ${\displaystyle a\mapsto U(\mu w.T_{1}(e,a,w))}$ ${\displaystyle e\in {\mathbb {N} }}$ ${\displaystyle e}$ ${\displaystyle T_{1}}$ ${\displaystyle \forall a.\exists w.T_{1}(e,a,w)}$ ${\displaystyle T_{1}}$ ${\displaystyle w}$ ${\displaystyle e}$ ${\displaystyle T_{1}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle e}$ ${\displaystyle {\mathbb {N} }}$

Una teoría en lógica de primer orden , como las teorías axiomáticas de conjuntos discutidas aquí, viene con una noción conjunta de total y funcional para un predicado binario , a saber . Estas teorías se relacionan con los programas sólo indirectamente. Si denota la operación sucesora en un lenguaje formal de una teoría que se está estudiando, entonces cualquier número, por ejemplo (el número tres), puede estar metalógicamente relacionado con el número estándar, por ejemplo . De manera similar, los programas en el sentido recursivo parcial pueden desenrollarse en predicados y bastan supuestos débiles para que dicha traducción respete la igualdad de sus valores de retorno. Entre las subteorías finitamente axiomizables de , la aritmética clásica de Robinson cumple exactamente esto. Sus afirmaciones de existencia pretenden referirse únicamente a los números naturales y, en lugar de utilizar el esquema de inducción matemática completo para fórmulas aritméticas, los axiomas de las teorías postulan que todo número es cero o que existe un número predecesor. Centrándonos aquí en las funciones recursivas -totales, es un metateorema que el lenguaje de la aritmética las expresa mediante predicados -que codifican su gráfica de manera que las represente , en el sentido de que prueba o rechaza correctamente para cualquier par de números de entrada-salida y en la metateoría. Ahora, dada una representación correcta , el predicado definido por representa la función recursiva igual de bien, y como esto explícitamente solo valida el valor de retorno más pequeño, la teoría también prueba la funcionalidad para todas las entradas en el sentido de . Dado un predicado representativo, a costa de hacer uso de , siempre se puede también sistemáticamente (es decir, con a ) demostrar que el gráfico es totalmente funcional. ^[17] ${\displaystyle R}$ ${\displaystyle \forall a.\exists !c.R(a,c)}$ ${\displaystyle S}$ ${\displaystyle {\mathrm {SSS0} }}$ ${\displaystyle {\underline {\mathrm {SSS0} }}=SSS0}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {Q}}}$ ${\displaystyle T_{1}}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle G}$ ${\displaystyle {\mathsf {Q}}}$ ${\displaystyle G({\underline {\mathrm {a} }},{\underline {\mathrm {c} }})}$ ${\displaystyle \mathrm {a} }$ ${\displaystyle \mathrm {c} }$ ${\displaystyle G}$ ${\displaystyle G_{\mathrm {least} }(a,c)}$ ${\displaystyle G(a,c)\land \forall (n<c).\neg G(a,n)}$ ${\displaystyle {\mathrm {a} }}$ ${\displaystyle {\mathsf {Q}}\vdash \exists !c.G_{\mathrm {least} }({\underline {\mathrm {a} }},c)}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle \forall a.}$

Qué predicados son demostrablemente funcionales para diversas entradas, o incluso totalmente funcionales en su dominio, generalmente depende de los axiomas adoptados de una teoría y del cálculo de prueba. Por ejemplo, para el problema de detención diagonal , que no puede tener un índice total, es independiente de si el predicado gráfico correspondiente en (un problema de decisión ) es funcional total, pero implica que lo es. Las jerarquías de funciones teóricas de prueba proporcionan ejemplos de predicados totalmente funcionales demostrados en sistemas que van más allá . Qué conjuntos cuya existencia se ha demostrado constituyen una función total, en el sentido que se presenta a continuación, también depende siempre de los axiomas y del cálculo de demostración. Finalmente, tenga en cuenta que la solidez de las afirmaciones de detención es una propiedad metalógica más allá de la coherencia, es decir, una teoría puede ser consistente y a partir de ella se puede probar que algún programa eventualmente se detendrá, a pesar de que esto nunca ocurra cuando se ejecuta dicho programa. Más formalmente, asumir la coherencia de una teoría no implica que también sea aritméticamente sólida . ${\displaystyle T_{1}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathbb {N} }\times \{0,1\}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle \Sigma _{1}}$

Relaciones funcionales totales

En el lenguaje de la teoría de conjuntos aquí, hablamos de una clase de función cuando y de manera comprobada ${\displaystyle f\subset A\times C}$

${\displaystyle \forall (a\in A).\,\exists !(c\in C).\langle a,c\rangle \in f}$.

En particular, esta definición implica que el cuantificador solicite explícitamente la existencia, un aspecto que es particularmente importante en el contexto constructivo. En palabras: Para cada , exige la existencia única de un para que . En el caso de que esto se cumpla, se puede utilizar la notación entre corchetes de aplicación de función y escribir . La propiedad anterior puede expresarse entonces como . Esta notación puede extenderse a la igualdad de valores de funciones. Algunas comodidades de notación que implican la aplicación de funciones sólo funcionarán cuando se haya establecido que un conjunto es una función. Sea (también escrito ) la clase de conjuntos que cumplen la propiedad de la función. Ésta es la clase de funciones desde hasta en una teoría de conjuntos pura. A continuación, la notación también se utiliza para , para distinguirla de la exponenciación ordinal. Cuando las funciones se entienden simplemente como gráficas de funciones como aquí, la proposición de membresía también se escribe . Los valores booleanos se encuentran entre las clases que se analizan en la siguiente sección. ${\displaystyle a}$ ${\displaystyle c}$ ${\displaystyle \langle a,c\rangle \in f}$ ${\displaystyle f(a)=c}$ ${\displaystyle \forall (a\in A).\,\exists !(c\in C).f(a)=c}$ ${\displaystyle C^{A}}$ ${\displaystyle ^{A}C}$ ${\displaystyle A}$ ${\displaystyle C}$ ${\displaystyle x\to y}$ ${\displaystyle y^{x}}$ ${\displaystyle f\in C^{A}}$ ${\displaystyle f\colon A\to C}$ ${\displaystyle \chi _{B}\colon A\to \{0,1\}}$

Por construcción, cualquier función de este tipo respeta la igualdad en el sentido de que , para cualquier entrada de . Vale la pena mencionar esto, ya que también existen conceptos más amplios de "rutinas de asignación" u "operaciones" en la literatura matemática, que en general pueden no respetar esto. También se han definido variantes de la definición de predicado funcional utilizando relaciones de separación en setoides . Un subconjunto de una función sigue siendo una función y el predicado de la función también puede demostrarse para conjuntos de codominios elegidos ampliados. Como se señaló, se debe tener cuidado con la nomenclatura "función", una palabra que se utiliza en la mayoría de los marcos matemáticos. Cuando un conjunto de funciones en sí no está vinculado a un codominio particular, entonces este conjunto de pares también es miembro de un espacio funcional con un codominio más grande. Esto no sucede cuando la palabra uno denota el subconjunto de pares emparejados con un conjunto de codominios, es decir, una formalización en términos de . Esto es principalmente una cuestión de contabilidad, pero afecta cómo se definen otros predicados, una cuestión de tamaño. Esta elección también se ve reforzada por algunos marcos matemáticos. Se aplican consideraciones similares a cualquier tratamiento de funciones parciales y sus dominios. ${\displaystyle (x=y)\to f(x)=f(y)}$ ${\displaystyle A}$ ${\displaystyle (A\times C)\times \{C\}}$

Si tanto el dominio como el codominio considerado son conjuntos, entonces el predicado de función anterior solo involucra cuantificadores acotados. Nociones comunes como inyectividad y sobreyectividad también pueden expresarse de forma limitada, al igual que la biyectividad . Ambos aspectos se relacionan con nociones de tamaño. Es importante destacar que la existencia de inyección entre dos conjuntos proporciona un pedido anticipado . Una clase de poder no se inyecta en su conjunto subyacente y este último no se asigna a la primera. La sobreyectividad es formalmente una definición más compleja. Tenga en cuenta que la inyectividad se definirá positivamente, no por su contrapositivo, que es una práctica común en las matemáticas clásicas. La versión sin negaciones a veces se llama débilmente inyectiva. La existencia de colisiones de valores es una noción fuerte de no inyectividad. Y con respecto a la sobreyectividad, existen consideraciones similares para la producción de valores atípicos en el codominio. ${\displaystyle A}$ ${\displaystyle C}$

Si una subclase (o predicado) puede considerarse un conjunto de funciones, o incluso funcional total para empezar, dependerá de la solidez de la teoría, es decir, de los axiomas que se adopten. Y en particular, una clase general también podría cumplir el predicado definitorio anterior sin ser una subclase del producto , es decir, la propiedad expresa ni más ni menos que la funcionalidad con respecto a las entradas de . Ahora bien, si el dominio es un conjunto, el principio de comprensión de funciones, también llamado axioma de elección única o no elección, dice que una función como conjunto, con algún codominio, existe bien. (Y este principio es válido en una teoría como . Compárese también con el axioma de reemplazo ). Es decir, la información cartográfica existe como un conjunto y tiene un par para cada elemento en el dominio. Por supuesto, para cualquier conjunto de alguna clase, siempre se puede asociar un elemento único del singleton , lo que muestra que el simple hecho de que un rango elegido sea un conjunto no es suficiente para que se le conceda un conjunto de funciones. Es un metateorema para teorías que contienen que agregar un símbolo de función para una función de clase total comprobada es una extensión conservadora, a pesar de que esto cambia formalmente el alcance de la Separación acotada . En resumen, en el contexto de la teoría de conjuntos la atención se centra en capturar relaciones totales particulares que sean funcionales. Para delinear la noción de función en las teorías de la subsección anterior (un predicado lógico biario definido para expresar una gráfica de funciones, junto con una proposición de que es total y funcional) de la noción teórica de conjunto "material" aquí, se puede llame explícitamente al último gráfico de una función , una función o una función establecida . El esquema axioma de Reemplazo también se puede formular en términos de los rangos de tales funciones establecidas. ${\displaystyle A\times C}$ ${\displaystyle A}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle 1}$ ${\displaystyle {\mathsf {BCST}}}$

finitud

Se definen tres nociones distintas que involucran sobrejecciones. Para que un conjunto general sea ( Alfil -) finito significará que hay una función biyectiva para un natural. Si se demuestra que la existencia de tal biyección es imposible, el conjunto se llama no finito . En segundo lugar, para una noción más débil que finita, estar indexada de forma finita (o Kuratowski -finita) significará que hay una sobreyección de un número natural de von Neumann sobre ella. En términos de programación, los elementos de dicho conjunto son accesibles en un bucle for (final) , y solo esos, aunque puede no ser decidible si se produjo la repetición. En tercer lugar, llamar subfinito a un conjunto si es el subconjunto de un conjunto finito, que así se inyecta en ese conjunto finito. Aquí, un bucle for accederá a todos los miembros del conjunto, pero posiblemente también a otros. Para otra noción combinada, más débil que la de indexación finita, estar indexada subfinitamente significa estar en la imagen sobreyectiva de un conjunto subfinito, y en esto simplemente significa ser el subconjunto de un conjunto finitamente indexado, lo que significa que el subconjunto también puede asumirse. el lado de la imagen en lugar del lado del dominio. Se puede entender que un conjunto que exhibe cualquiera de esas nociones está mayorizado por un conjunto finito, pero en el segundo caso la relación entre los miembros del conjunto no necesariamente se comprende completamente. En el tercer caso, validar la pertenencia al conjunto es generalmente más difícil, y ni siquiera es necesario comprender plenamente la pertenencia de su miembro con respecto a algún superconjunto del conjunto. La afirmación de que ser finito equivale a ser subfinito, para todos los conjuntos, es equivalente a . Se pueden definir más propiedades de finitud para un conjunto , por ejemplo, expresando la existencia de algún natural lo suficientemente grande como para que una cierta clase de funciones en los naturales siempre no se puedan asignar a elementos distintos en . Una definición considera alguna noción de no inyectividad en . Otras definiciones consideran funciones a un superconjunto fijo con más elementos. ${\displaystyle {\mathsf {ETCS}}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

La terminología para las condiciones de finitud e infinitud puede variar. En particular, los conjuntos subfinitamente indexados (una noción que necesariamente implica sobreyecciones) a veces se denominan subfinitos (que pueden definirse sin funciones). La propiedad de estar indexada de forma finita también podría denominarse "finitamente contable", para ajustarse a la lógica de nomenclatura, pero algunos autores también la llaman finitamente enumerable (lo que podría resultar confuso ya que sugiere una inyección en la otra dirección). De manera relacionada, no se ha establecido la existencia de una biyección con un conjunto finito, se puede decir que un conjunto no es finito, pero este uso del lenguaje es entonces más débil que afirmar que el conjunto no es finito. El mismo problema se aplica a los conjuntos contables (no contables probados versus no contables probados), etc. Un mapa sobreyectivo también puede denominarse enumeración.

Infinitud

El conjunto en sí es claramente ilimitado. De hecho, para cualquier sobreyección de un rango finito sobre , se puede construir un elemento que sea diferente de cualquier elemento en el rango de funciones. Cuando sea necesario, esta noción de infinitud también puede expresarse en términos de una relación de separación en el conjunto en cuestión. No ser finito en Kuratowski implica no ser finito y, de hecho, los naturales no serán finitos en ningún sentido. Comúnmente, la palabra infinito se usa para la noción negativa de no ser finito. Además, observe que , a diferencia de cualquiera de sus miembros, se puede poner en biyección con algunos de sus subconjuntos ilimitados adecuados, por ejemplo, los de la forma para cualquiera . Esto valida las formulaciones de Dedekind-infinite . Entonces, de manera más general que la propiedad de infinitud en la sección anterior sobre límites numéricos, uno puede llamar infinito a un conjunto en el sentido lógicamente positivo si se puede inyectar en él. Un conjunto que está incluso en biyección puede denominarse contablemente infinito. Un conjunto es Tarski-infinito si hay una cadena de subconjuntos crecientes del mismo. Aquí cada conjunto tiene nuevos elementos en comparación con su predecesor y la definición no habla de conjuntos con rango creciente. De hecho, hay muchas propiedades que caracterizan la infinitud incluso en la teoría clásica y esa teoría no prueba que todos los conjuntos no finitos sean infinitos en el sentido de existencia de inyección, aunque se cumple cuando se supone además una elección contable. sin ninguna opción, incluso se permiten cardinales a un lado los números aleph , y entonces puede haber conjuntos que niegan ambas propiedades anteriores, es decir, son infinitos y no finitos de Dedekind (también llamados conjuntos infinitos finitos de Dedekind). ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle w_{m}:=\{k\in \omega \mid k>m\}}$ ${\displaystyle m\in \omega }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \subset }$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {ZF}}}$

Llame a un conjunto habitado contable si existe una sobreyección sobre él y subcontable si esto se puede hacer desde algún subconjunto de . Llame a un conjunto enumerable si existe una inyección en , lo que hace que el conjunto sea discreto. En particular, todas estas son afirmaciones de existencia de funciones. El conjunto vacío no está habitado, pero generalmente también se considera contable, y tenga en cuenta que el conjunto sucesor de cualquier conjunto contable es contable. El conjunto es trivialmente infinito, contable y enumerable, como lo atestigua la función identidad. También aquí, en las teorías clásicas fuertes, muchas de estas nociones coinciden en general y, como resultado, las convenciones de denominación en la literatura son inconsistentes. Un conjunto infinito y contable es equinumeros a . ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$

También hay varias formas de caracterizar una noción lógicamente negativa. La noción de incontable, en el sentido de no ser contable, también se analiza junto con el axioma de exponenciación más adelante. Otra noción de incontable de se da cuando se puede producir un miembro en el complemento de cualquiera de los subconjuntos contables de. Se pueden definir más propiedades de la finitud como negaciones de tales propiedades, etcétera. ${\displaystyle X}$ ${\displaystyle X}$

Funciones características

La separación nos permite recortar subconjuntos de productos , al menos cuando se describen de forma acotada. Dado cualquiera , ahora uno se ve llevado a razonar sobre clases como ${\displaystyle A\times C}$ ${\displaystyle B\subset A}$

${\displaystyle X_{B}:={\big \{}\langle x,y\rangle \in A\times \{0,1\}\mid (x\in B\land y=1)\lor (x\notin B\land y=0){\big \}}.}$

Desde entonces uno tiene ${\displaystyle \neg (0=1)}$

${\displaystyle {\big (}a\in B\ \leftrightarrow \,\langle a,1\rangle \in X_{B}{\big )}\,\land \,{\big (}a\notin B\ \leftrightarrow \,\langle a,0\rangle \in X_{B}{\big )}}$

y entonces

${\displaystyle {\big (}a\in B\lor a\notin B{\big )}\ \leftrightarrow \ \exists !(y\in \{0,1\}).\langle a,y\rangle \in X_{B}}$.

Pero tenga en cuenta que, en ausencia de axiomas no constructivos, en general puede no ser decidible , ya que se requiere una prueba explícita de cualquiera de las disyunciones. Constructivamente, cuando no se puede atestiguar en su totalidad , o no se puede probar la unicidad de los términos asociados con cada uno , entonces no se puede juzgar que la colección comprendida sea totalmente funcional. Caso en cuestión: la derivación clásica de Schröder-Bernstein se basa en el análisis de casos, pero para constituir una función , los casos particulares deben ser realmente especificables, dada cualquier entrada del dominio. Se ha establecido que Schröder-Bernstein no puede tener una demostración basada en principios constructivos positivos. ^[18] Entonces, en la medida en que la inferencia intuicionista no vaya más allá de lo formalizado aquí, no existe una construcción genérica de una biyección a partir de dos inyecciones en direcciones opuestas. ${\displaystyle a\in B}$ ${\displaystyle \exists (y\in \{0,1\}).\langle x,y\rangle \in X_{B}}$ ${\displaystyle x\in A}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle {\mathsf {IZF}}}$

Pero siendo compatible con , el desarrollo en esta sección siempre permite que "función en " se interprete como un objeto completo que tampoco necesariamente se da como una 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 moneda, incluso si muchas predicciones también pueden expresarse en términos de diferenciales . ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle \omega }$

Si realmente a uno se le da una función , es la función característica la que realmente decide la pertenencia a algún subconjunto separable y ${\displaystyle \chi _{B}\colon A\to \{0,1\}}$ ${\displaystyle B\subset A}$

${\displaystyle B=\{n\in \omega \mid \chi _{B}(n)=1\}.}$

Por convención, el subconjunto separable , así como cualquier equivalente de las fórmulas y (con free) pueden denominarse propiedad decidible o conjunto en . ${\displaystyle B}$ ${\displaystyle \chi _{B}}$ ${\displaystyle n\in B}$ ${\displaystyle \chi _{B}(n)=1}$ ${\displaystyle n}$ ${\displaystyle A}$

Se puede llamar a una colección buscable si la existencia es realmente decidible, ${\displaystyle A}$ ${\displaystyle \chi _{B}}$

${\displaystyle \exists (x\in A).\chi _{B}(x)=1\ \lor \ \forall (x\in A).\chi _{B}(x)=0.}$

Consideremos ahora el caso . Si , digamos, entonces el rango de es un conjunto habitado, contado, por Reemplazo. Sin embargo, no es necesario que vuelva a ser un conjunto decidible en sí mismo, ya que la afirmación equivale a la bastante fuerte . Además, también es equivalente a y, por lo tanto, también se pueden formular proposiciones indecidibles sobre cuándo la membresía en es decidible. Esto también se desarrolla así clásicamente en el sentido de que las afirmaciones acerca de pueden ser independientes , pero cualquier teoría clásica reivindica la proposición conjunta . Consideremos el conjunto de todos los índices de pruebas de una inconsistencia de la teoría en cuestión, en cuyo caso el enunciado universalmente cerrado es una afirmación de coherencia. En términos de principios aritméticos, asumir la decidibilidad de esto sería - o aritmética - . Esto y la aritmética o relacionada más fuerte se analizan a continuación. ${\displaystyle A=\omega }$ ${\displaystyle \chi _{B}(0)=0}$ ${\displaystyle \{0\}\subset R\subset \{0,1\}}$ ${\displaystyle \chi _{B}}$ ${\displaystyle R}$ ${\displaystyle R=\{0\}}$ ${\displaystyle \forall n.\chi _{B}(n)=0}$ ${\displaystyle R=\{0\}}$ ${\displaystyle B=\{\}}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B=\{\}\lor \neg (B=\{\})}$ ${\displaystyle B}$ ${\displaystyle B=\{\}}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle \forall }$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathrm {LPO} }}$ ${\displaystyle \exists }$ ${\displaystyle {\mathrm {PEM} }}$

Testigo de separación

Si hay un predicado que distingue dos términos y en el sentido de que , entonces el principio de identidad de indiscernibles implica que los dos no coinciden. Esta noción de conjunto puede expresarse teóricamente: puede considerarse aparte si existe un subconjunto tal que uno es miembro y el otro no. Restringido a subconjuntos separables, esto puede formularse de manera concisa mediante la cuantificación de funciones . En efecto, ya se rechaza una vez que se establece que no todas las funciones se respetan . Con ese espíritu, en cualquier conjunto se puede definir la relación de separación lógicamente positiva. ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle P(x)\land \neg P(y)}$ ${\displaystyle x,y\in A}$ ${\displaystyle B\subset A}$ ${\displaystyle \chi _{B}\in 2^{A}}$ ${\displaystyle x=y}$ ${\displaystyle f}$ ${\displaystyle f(x)=f(y)}$ ${\displaystyle A}$

${\displaystyle x\,\#_{A}\,y\,:=\,\exists (f\in {\mathbb {N} }^{A}).f(x)\neq f(y)}$.

Como los naturales son discretos, lo anterior aquí se manifiesta en el teorema

${\displaystyle \neg \neg (x\,\#_{A}\,y)\to \neg (x=y)}$.

Conjuntos computables

Volviendo a una mayor generalidad, dado un predicado general sobre los números (digamos uno definido a partir del predicado T de Kleene ), dejemos nuevamente ${\displaystyle Q}$

${\displaystyle B:=\{n\in \omega \mid Q(n)\}.}$

Dado cualquier natural , entonces ${\displaystyle n\in \omega }$

${\displaystyle {\big (}Q(n)\lor \neg Q(n){\big )}\leftrightarrow {\big (}n\in B\lor n\notin B{\big )}.}$

En la teoría de conjuntos clásica, el término medio excluido también se aplica a la pertenencia a una subclase. Si la clase no tiene límite numérico, entonces pasar sucesivamente por los números naturales y así "enumerar" todos los números simplemente omitiendo aquellos con , clásicamente siempre constituye una secuencia sobreyectiva creciente . Allí se puede obtener una función biyectiva . De esta manera, la clase de funciones en las teorías de conjuntos clásicas típicas es rica, ya que también contiene objetos que están más allá de lo que sabemos que son efectivamente computables o enumerables programáticamente en la práctica. ${\displaystyle \forall (n\in \omega ).Q(n)\lor \neg Q(n)}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle B}$ ${\displaystyle n\notin B}$ ${\displaystyle b\colon \omega \twoheadrightarrow B}$

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 superior. Decidir un predicado en ese nivel equivale a resolver la tarea de encontrar eventualmente 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 ilimitados son el rango de alguna función biyectiva con dominio . Véase también el esquema de Kripke. Tenga en cuenta que, no obstante, la separación acotada demuestra que los predicados aritméticos más complicados aún constituyen conjuntos, siendo el siguiente nivel los enumerables computablemente en . ${\displaystyle \Sigma _{1}^{0}\cap \Pi _{1}^{0}=\Delta _{1}^{0}}$ ${\displaystyle Q}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle B\subset \omega }$ ${\displaystyle \omega }$ ${\displaystyle \Sigma _{1}^{0}}$

Existe un gran corpus de nociones de la teoría de la computabilidad sobre cómo se relacionan entre sí los subconjuntos generales de naturales. Por ejemplo, una forma de establecer una biyección de dos de estos conjuntos es relacionándolos mediante un isomorfismo computable , que es una permutación computable de todos los naturales. Este último puede, a su vez, establecerse mediante un par de inyecciones particulares en direcciones opuestas.

Criterios de acotación

Cualquier subconjunto se inyecta en . Si es decidible y habitado por , la secuencia ${\displaystyle B\subset \omega }$ ${\displaystyle \omega }$ ${\displaystyle B}$ ${\displaystyle y_{0}\in B}$

${\displaystyle q:={\big \{}\langle x,y\rangle \in \omega \times B\mid (x\in B\land y=x)\lor (x\notin B\land y=y_{0}){\big \}}}$

es decir

${\displaystyle q(x):={\begin{cases}x&x\in B\\y_{0}&x\notin B\\\end{cases}}}$

es sobreyectivo sobre , lo que lo convierte en un conjunto contado. Esa función también tiene la propiedad . ${\displaystyle B}$ ${\displaystyle \forall (x\in B).q(x)=x}$

Consideremos ahora un conjunto contable acotado en el sentido definido anteriormente. Cualquier secuencia que tome valores también está limitada numéricamente y, en particular, eventualmente no excede la función de identidad en sus índices de entrada. Formalmente, ${\displaystyle R\subset \omega }$ ${\displaystyle R}$

${\displaystyle \forall (r\colon \omega \to R).\exists (m\in \omega ).\forall (k\in \omega ).k>m\to r(k)<k}$

Un conjunto tal que esta declaración delimitada libremente se cumple para todas las secuencias que toman valores en (o una formulación equivalente de esta propiedad) se llama pseudo-limitado . La intención de esta propiedad sería capturar lo que finalmente se agota, aunque ahora esto se expresa en términos del espacio funcional (que es más grande que en el sentido de que siempre se inyecta en ). La noción relacionada, familiar de la teoría del espacio vectorial topológico, se formula en términos de razones que llegan a cero para todas las secuencias ( en la notación anterior). Para un conjunto habitado y decidible, la validez de la pseudolimitación, junto con la secuencia de conteo definida anteriormente, otorga un límite para todos los elementos de . ${\displaystyle I}$ ${\displaystyle I}$ ${\displaystyle I\subset \omega }$ ${\displaystyle I^{\omega }}$ ${\displaystyle I}$ ${\displaystyle I}$ ${\displaystyle I^{\omega }}$ ${\displaystyle {\tfrac {r(k)}{k}}}$ ${\displaystyle I}$

El principio de que cualquier subconjunto habitado y pseudolimitado de eso es simplemente contable (pero no necesariamente decidible) y siempre también está limitado se llama - . El principio también se aplica generalmente en muchos marcos constructivos, como la teoría de bases de Markov , que es una teoría que postula secuencias exclusivamente legales con buenas propiedades de terminación de búsqueda de números. Sin embargo, - es independiente de . ${\displaystyle \omega }$ ${\displaystyle \mathrm {BD} }$ ${\displaystyle {\mathbb {N} }}$ ${\displaystyle {\mathsf {HA}}+{\mathrm {ECT} }_{0}+{\mathrm {MP} }}$ ${\displaystyle \mathrm {BD} }$ ${\displaystyle {\mathbb {N} }}$ ${\displaystyle {\mathsf {IZF}}}$

Funciones de elección

Ni siquiera lo clásico demuestra que cada unión de un conjunto contable de conjuntos de dos elementos sea contable nuevamente. De hecho, se han definido modelos que niegan la contabilidad de tal unión contable de pares. Suponer una elección contable descarta ese modelo como interpretación de la teoría resultante. Este principio sigue siendo independiente de : Una estrategia de prueba ingenua para esa afirmación falla en la explicación de infinitas instancias existenciales . ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {ZF}}}$

Un principio de elección postula que ciertas selecciones siempre pueden realizarse de manera conjunta en el sentido de que también se manifiestan como un conjunto único de funciones en la teoría. Como ocurre con cualquier axioma independiente, esto aumenta las capacidades de demostración al tiempo que restringe el alcance de posibles interpretaciones (teóricas de modelos) de la teoría (sintáctica). La afirmación de existencia de una función a menudo se puede traducir a la existencia de inversas, ordenamientos, etc. Además, la elección implica afirmaciones sobre cardinalidades de diferentes conjuntos, por ejemplo, implican o excluyen la numerabilidad de conjuntos. Agregar elección completa no prueba ningún teorema nuevo , pero es estrictamente no constructivo, como se muestra a continuación. El desarrollo aquí se desarrolla de forma independiente de cualquiera de las variantes que se describen a continuación. ^[19] ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle \Pi _{4}^{1}}$

• Axioma de elección contable (o ): Si , se puede formar el conjunto de relaciones de uno a muchos . El axioma de elección contable garantizaría que siempre que se pueda formar una función que asigne cada número a un valor único. La existencia de tales secuencias generalmente no se puede demostrar sobre la base de esa teoría, y la elección contable no es conservadora. La elección contable en conjuntos generales también puede debilitarse aún más. Una consideración común es restringir las posibles cardinalidades del rango de , dando a la opción contable débil la posibilidad de elegir conjuntos contables, finitos o incluso simplemente binarios ( ). Se puede considerar la versión de elección contable para funciones en (llamadas o ), como lo implica el principio de tesis constructiva de Church , es decir, postulando que todas las relaciones aritméticas totales son recursivas. en aritmética puede entenderse como una forma de axioma de elección. Otra forma de debilitar la elección contable es restringir las definiciones involucradas en su lugar en las jerarquías sintácticas (digamos - ). El lema débil de Kőnig , que rompe las matemáticas estrictamente recursivas como se analiza más adelante, es más fuerte que ( y a veces se considera que captura una forma de elección contable). En presencia de una forma débil de elección contable, el lema se vuelve equivalente al principio no constructivo de sabor más lógico . Constructivamente, se requiere una forma débil de elección para los reales de Cauchy que se portan bien . La elección contable no es válida en la lógica interna de un topos general , que puede verse como modelos de teorías constructivas de conjuntos. ${\displaystyle {\mathrm {AC} _{\omega }}}$ ${\displaystyle {\mathrm {CC} }}$ ${\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 ).\exists u.u\in g(n)}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle \Sigma _{4}^{1}}$ ${\displaystyle g}$ ${\displaystyle {\mathrm {AC} _{\omega ,2}}}$ ${\displaystyle \omega }$ ${\displaystyle {\mathrm {AC} _{\omega ,\omega }}}$ ${\displaystyle {\mathrm {AC} _{00}}}$ ${\displaystyle {\mathrm {CT} _{0}}}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle {\mathrm {AC} _{\omega ,2}}}$ ${\displaystyle {\mathrm {WKL} }}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle {\mathrm {AC} _{\omega ,2}}}$ ${\displaystyle {\mathrm {LLPO} }}$
• Axioma de elección dependiente : La elección contable está implícita en el axioma más general de elección dependiente, que extrae una secuencia en una relación habitada , dada cualquier relación completa . En la teoría de conjuntos, esta secuencia es nuevamente un conjunto infinito de pares, un subconjunto de . Así, a uno se le concede pasar de varios enunciados de existencia a una existencia funcional, concediendo a su vez enunciados de existencia únicos, para cada ser natural. En varios marcos constructivos se adopta una formulación apropiada de elección dependiente, por ejemplo, en algunas escuelas que entienden las secuencias interminables como construcciones en curso en lugar de objetos terminados. Al menos esos casos parecen benignos en los que, para cualquier , la existencia del siguiente valor puede validarse de forma computable. La función recursiva correspondiente , si existe, se conceptualiza como capaz de devolver un valor en infinitas entradas potenciales , pero no es necesario evaluarlas todas juntas a la vez. También es válido en muchos modelos de realizabilidad . En la condición del teorema de recursión formalmente similar , a uno ya se le da una opción única en cada paso, y ese teorema le permite combinarlos en una función en . Así también se pueden considerar formas del axioma con restricciones en . A través del axioma de separación acotada en , el principio también es equivalente a un esquema en dos variables de predicado acotadas: manteniendo todos los cuantificadores en el rango de , se puede restringir aún más este dominio de conjunto usando una variable de predicado unario , mientras que también se usa cualquier predicado 2-ario. en lugar del conjunto de relaciones . ${\displaystyle {\mathrm {DC} }}$ ${\displaystyle z}$ ${\displaystyle R\subset z\times z}$ ${\displaystyle \omega \times z}$ ${\displaystyle x\in z}$ ${\displaystyle \exists (y\in z).xRy}$ ${\displaystyle \omega \to z}$ ${\displaystyle n\in \omega }$ ${\displaystyle \omega }$ ${\displaystyle {\mathrm {DC} }}$ ${\displaystyle R}$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle z}$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \Delta _{0}}$ ${\displaystyle R}$
• Elección dependiente relativizada : este es el esquema que simplemente usa dos clases generales, en lugar de requerir y ser conjuntos. El dominio de la función de elección cuya existencia se concede sigue siendo justo . Además , implica una inducción matemática completa, que, a su vez, permite la definición de funciones a través del esquema de recursividad. Cuando se restringe a definiciones, todavía implica inducción matemática para predicados (con un cuantificador existencial sobre conjuntos), así como . En , el esquema es equivalente a . ${\displaystyle {\mathrm {RDC} }}$ ${\displaystyle z}$ ${\displaystyle R}$ ${\displaystyle \omega }$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle \omega }$ ${\displaystyle {\mathrm {RDC} }}$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle {\mathrm {DC} }}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathrm {RDC} }}$ ${\displaystyle {\mathrm {DC} }}$
• ${\displaystyle \Pi \Sigma }$- : Una familia de conjuntos es mejor controlable si viene indexada por una función. Un conjunto es una base si todas las familias de conjuntos indexadas sobre él tienen una función de elección , es decir . Una colección de conjuntos que contienen y sus elementos y que se cierra tomando sumas y productos indexados (ver tipo dependiente ) se llama cerrado. Si bien el axioma de que todos los conjuntos en la clase cerrada más pequeña son una base necesita algo de trabajo para formularse, es el principio de elección más fuerte que se cumple en la interpretación teórica de tipos . ${\displaystyle \mathrm {AC} }$ ${\displaystyle b}$ ${\displaystyle i_{s}\colon b\to s}$ ${\displaystyle f_{s}}$ ${\displaystyle \forall (x\in b).f_{s}(x)\in i_{s}(x)}$ ${\displaystyle \omega }$ ${\displaystyle \Pi \Sigma }$ ${\displaystyle \Pi \Sigma }$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {ML_{1}V}}}$
• Axioma de elección : Este es el postulado de la función de elección "completa" relativa a dominios que son conjuntos generales que contienen conjuntos habitados, con el codominio dado como su unión general. Dada una colección de conjuntos tal que la lógica permite hacer una elección en cada uno, el axioma garantiza que existe una función de conjunto que captura conjuntamente una elección en todos. Por lo general, se formula para todos los conjuntos, pero también se ha estudiado en formulaciones clásicas para conjuntos solo hasta una cardinalidad particular. Un ejemplo estándar es la elección en todos los subconjuntos habitados de los reales, que clásicamente equivale al dominio . Para esta colección no puede haber una prescripción uniforme de selección de elementos que de manera demostrable constituya una función de elección sobre la base de . Además, cuando se restringe al álgebra de Borel de los reales, por sí solo no prueba la existencia de una función que seleccione un miembro de cada subconjunto no vacío medible por Lebesgue . (El conjunto es el σ-álgebra generado por los intervalos . Incluye estrictamente esos intervalos, en el sentido de , pero también solo tiene la cardinalidad de los reales mismos.) Abundan las sorprendentes afirmaciones de existencia implícitas en el axioma. prueba que existe y entonces el axioma de elección también implica elección dependiente. De manera crítica en el contexto actual, también implica ejemplos del teorema de Via Diaconescu. Para las teorías que lo amplían, esto significa que la elección completa, como mínimo, prueba para todas las fórmulas, una consecuencia no constructiva no aceptable, por ejemplo, desde el punto de vista de la computabilidad. Tenga en cuenta que, desde el punto de vista constructivo, el lema de Zorn no implica elección: cuando la pertenencia a dominios de funciones no es decidible, la función extrema otorgada por ese principio no es siempre demostrable una función de elección en todo el dominio. ${\displaystyle {\mathrm {AC} }}$ ${\displaystyle \{z,\dots \}}$ ${\displaystyle {\mathcal {P}}_{\mathbb {R} }\setminus 1}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathcal {B}}({\mathbb {R} })}$ ${\displaystyle I:=\{(x,y\,]\mid x,y\in {\mathbb {R} }\}}$ ${\displaystyle I\subsetneq {\mathcal {B}}({\mathbb {R} })\subsetneq {\mathcal {P}}_{\mathbb {R} }}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle \omega }$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle \Delta _{0}}$

teorema de diaconescu

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

${\displaystyle a=\{u\in \{0,1\}\mid (u=0)\lor P\}}$

${\displaystyle b=\{u\in \{0,1\}\mid (u=1)\lor P\}}$

de la demostración del teorema de Diaconescu . Son tan contingentes como la proposición involucrada en su definición y no se ha demostrado que sean finitos. Sin embargo, el montaje conlleva varias consecuencias. Volviendo a la elaboración introductoria sobre el significado de dicha notación de clases conveniente, así como al principio de distributividad ,. Así incondicionalmente, así como y en particular están habitados. Como en cualquier modelo de aritmética de Heyting, utilizar el silogismo disyuntivo ambos y cada uno implica . De hecho, las dos afirmaciones son equivalentes a la proposición, como claramente . Este último también dice que la validez de los medios y la comparten todos los miembros, y hay dos de estos. Así son entonces los conjuntos, también por extensionalidad. Por el contrario, asumir que son iguales significa para cualquiera , validar todas las declaraciones de membresía. Por lo tanto, tanto las declaraciones de membresía como las igualdades son equivalentes a . El uso del contrapositivo da como resultado una equivalencia más débil de disyunciones . Por supuesto, explícitamente, y así se descubre realmente en qué sentido los conjuntos pueden llegar a ser diferentes. Como funciones preserva la igualdad por definición, de hecho es válida para cualquiera con dominio . ${\displaystyle P}$ ${\displaystyle t\in a\leftrightarrow {\big (}t=0\lor (t=1\land P){\big )}}$ ${\displaystyle 0\in a}$ ${\displaystyle 1\in b}$ ${\displaystyle \neg (0=1)}$ ${\displaystyle 0\in b}$ ${\displaystyle 1\in a}$ ${\displaystyle P}$ ${\displaystyle P\to (a=\{0,1\}\land b=\{0,1\})}$ ${\displaystyle P}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle P\to (a=b\land \{a,b\}=\{a\})}$ ${\displaystyle x\in a\leftrightarrow x\in b}$ ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle (P\lor \neg P)\leftrightarrow (a=b\lor \neg (a=b))}$ ${\displaystyle \neg P\to (a=\{0\}\land b=\{1\})}$ ${\displaystyle \neg {\big (}g(a)=g(b){\big )}\to \neg P}$ ${\displaystyle g}$ ${\displaystyle \{a,b\}}$

A continuación, supongamos un contexto en el que efectivamente se establece que son conjuntos y, por tanto, conjuntos subfinitos. El axioma general de elección afirma la existencia de una función con . Es importante que los elementos del dominio de la función sean diferentes a los números naturales en el sentido de que a priori se sabe menos sobre los primeros. A la hora de formar entonces la unión de las dos clases, es una condición necesaria pero también suficiente. Por lo tanto , se trata de funciones en un conjunto de dos valores distinguibles . Con la elección viene la conjunción en el codominio de la función, pero se sabe que los posibles valores de retorno de la función son solo o . Utilizando la distributividad surge una lista de condiciones, otra disyunción. Ampliando lo establecido entonces, se encuentra que tanto la igualdad como los conjuntos se mantienen, o que los valores de retorno son diferentes y pueden rechazarse. La conclusión es que el postulado de elección en realidad implica siempre que un axioma de separación permita la comprensión de conjuntos utilizando una proposición indecidible . ${\displaystyle a,b}$ ${\displaystyle f\colon \{a,b\}\to a\cup b}$ ${\displaystyle f(z)\in z}$ ${\displaystyle a,b}$ ${\displaystyle 0,1}$ ${\displaystyle u=0\lor u=1}$ ${\displaystyle a\cup b=\{0,1\}}$ ${\displaystyle f}$ ${\displaystyle f(a)\in a\land f(b)\in b}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P\lor \neg P}$ ${\displaystyle P}$

Análisis del teorema de Diaconescu

Por tanto, la elección total no es constructiva en la teoría de conjuntos tal como se define aquí. El problema es que cuando las proposiciones son parte de una comprensión establecida (como cuando se usa para separar y, por lo tanto, definir, las clases y de ), la noción de sus valores de verdad se ramifica en términos establecidos de la teoría. La igualdad definida por el axioma teórico establecido de extensionalidad , que en sí mismo no está relacionado con funciones, a su vez combina el conocimiento sobre la proposición con la información sobre los valores de la función. Para recapitular el paso final en términos de valores de función: por un lado, atestiguar implica y esta conclusión independientemente también se aplica a atestiguar . Por otro lado, testificar implica que los dos argumentos de función no son iguales y esto lo descarta . En realidad, sólo hay tres combinaciones, ya que el axioma de extensionalidad en la configuración dada hace que sea inconsistente. Entonces, si se debe preservar la lectura constructiva de la existencia, es posible que la elección plena no se adopte en la teoría de conjuntos, porque la mera afirmación de la existencia de una función no realiza una función particular. ${\displaystyle P}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \{0,1\}}$ ${\displaystyle f(a)=1}$ ${\displaystyle P}$ ${\displaystyle a=b}$ ${\displaystyle f(b)=0}$ ${\displaystyle f(a)=0\land f(b)=1}$ ${\displaystyle P}$ ${\displaystyle f(a)=1\land f(b)=0}$

Para comprender mejor por qué no se puede esperar que se le conceda una función de elección definitiva (total) con dominio , considere candidatos a funciones ingenuas. En primer lugar, conviene realizar un análisis del dominio. La sobreyección atestigua que está finitamente indexada. Se observó que sus miembros son subfinitos y también habitados, ya que independientemente de que sea el caso que y . De manera tan ingenua, esto parecería ser un candidato para una función de elección. Cuando se puede rechazar, entonces ésta es efectivamente la única opción. Pero en el caso de la demostrabilidad de , cuando , extensilmente solo hay una función posible de entrada a una función de elección. Entonces, en esa situación, una función de elección tendría explícitamente type , por ejemplo, y esto descartaría al contendiente inicial. En general , el dominio de una posible función de elección no es concreto sino contingente y no se ha demostrado que sea finito. Al considerar la asignación funcional anterior , ni la declaración incondicional ni la declaración son necesariamente consistentes. Habiéndose identificado con , los dos candidatos descritos anteriormente se pueden representar simultáneamente mediante (que tampoco se ha demostrado que sea finito) con el "valor de verdad de " subfinito dado como . Como , postular , o , o el principio clásico aquí implicaría de hecho que es natural, de modo que este último conjunto constituye una función de elección en . Y como en el caso constructivo, dada una función de elección particular (un conjunto que contiene exactamente uno o exactamente dos pares), uno podría en realidad inferir si se cumple o si se cumple. Viceversa, el tercer y último candidato puede ser capturado como parte de , donde . Esto ya se había considerado en la primera sección sobre el axioma de separación. Nuevamente, esta última aquí también es una función de elección clásica en cualquier sentido, donde funciona como una "cláusula if" (potencialmente indecidible). Constructivamente, el dominio y los valores de tales posibles funciones dependientes no se comprenden lo suficiente como para demostrar que son una relación funcional total . ${\displaystyle \{a,b\}}$ ${\displaystyle \{\langle 0,a\rangle ,\langle 1,b\rangle \}}$ ${\displaystyle \{a,b\}}$ ${\displaystyle P}$ ${\displaystyle 0\in a}$ ${\displaystyle 1\in b}$ ${\displaystyle f=\{\langle a,0\rangle ,\langle b,1\rangle \}}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \{a,b\}=\{a\}}$ ${\displaystyle f\colon \{a\}\to \{0,1\}}$ ${\displaystyle f=\{\langle a,0\rangle \}}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle f(a)=0}$ ${\displaystyle f(b)=1}$ ${\displaystyle f(b)=0}$ ${\displaystyle 1}$ ${\displaystyle \{0\}}$ ${\displaystyle f=\{\langle a,0\rangle ,\langle b,B_{\neg }\rangle \}}$ ${\displaystyle \neg P}$ ${\displaystyle B_{\neg }:=\{u\in \{0\}\mid \neg P\}}$ ${\displaystyle (P\to (B_{\neg }=0))\land (\neg P\to (B_{\neg }=1))}$ ${\displaystyle P}$ ${\displaystyle \neg P}$ ${\displaystyle P\lor \neg P}$ ${\displaystyle B_{\neg }}$ ${\displaystyle f}$ ${\displaystyle \{0,1\}}$ ${\displaystyle P}$ ${\displaystyle \neg P}$ ${\displaystyle f=\{\langle b,1\rangle \}}$ ${\displaystyle f=\{\langle a,B\rangle ,\langle b,1\rangle \}}$ ${\displaystyle B:=\{u\in \{0\}\mid P\}}$ ${\displaystyle B}$ ${\displaystyle f}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \{0,1\}}$

Para la semántica computable, los axiomas de la teoría de conjuntos que postulan la existencia (total) de funciones conducen al requisito de detener las funciones recursivas. A partir de su gráfico de funciones en interpretaciones individuales, se pueden inferir las ramas tomadas por las "cláusulas si" que estaban indecisas en la teoría interpretada. Pero en el nivel de los marcos sintéticos, cuando en términos generales se vuelven clásicos al adoptar la elección total, estas teorías de conjuntos extensionales contradicen la regla de la Iglesia constructiva.

La regularidad implica PEM

El axioma de elección otorga a la existencia una función asociada a cada colección de elementos habitados del tamaño de un conjunto , con la que se pueden seleccionar de inmediato elementos únicos . El axioma de regularidad establece que por cada conjunto habitado de la colección universal, existe un elemento en , que no comparte elementos con . Esta formulación no implica funciones ni afirmaciones de existencia única, sino que garantiza directamente conjuntos con una propiedad específica. Como el axioma correlaciona las reclamaciones de membresía en diferentes rangos, el axioma también termina implicando : ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle t\in s}$ ${\displaystyle {\mathrm {PEM} }}$

La prueba de Choice anterior había utilizado un conjunto particular . La prueba en este párrafo también supone que Separation se aplica y utiliza , para lo cual, por definición. Ya se ha explicado que, por lo tanto, se puede excluir el medio para en el formulario . Ahora sea el miembro postulado con la propiedad de intersección vacía. El conjunto se definió como un subconjunto de y, por lo tanto, cualquier dato cumple la disyunción . La cláusula izquierda implica , mientras que para la cláusula derecha se puede usar que el elemento especial que no se cruza cumple . ${\displaystyle 1:=\{0\}}$ ${\displaystyle \{a,b\}}$ ${\displaystyle P}$ ${\displaystyle b}$ ${\displaystyle \{0\}\in b}$ ${\displaystyle P\leftrightarrow 0\in b}$ ${\displaystyle P}$ ${\displaystyle 0\in b\lor 0\notin b}$ ${\displaystyle t\in b}$ ${\displaystyle b}$ ${\displaystyle \{0,1\}}$ ${\displaystyle t\in b}$ ${\displaystyle t=0\lor t=1}$ ${\displaystyle t=0}$ ${\displaystyle 0\in b}$ ${\displaystyle t=1}$ ${\displaystyle t}$ ${\displaystyle (t=\{0\})\leftrightarrow (0\notin b)}$

Exigir que el conjunto de naturales esté bien ordenado con respecto a su relación de orden estándar impone la misma condición al conjunto habitado . Entonces, el principio del menor número tiene la misma implicación no constructiva. Al igual que con la prueba de Elección, el alcance de las proposiciones para las cuales estos resultados son válidos está gobernado por el axioma de Separación. ${\displaystyle b\subset \omega }$

Aritmética

Se han discutido los cuatro axiomas de Peano para y , que caracterizan al conjunto como modelo de los números naturales en la teoría constructiva de conjuntos . El orden " " de los números naturales se captura por la pertenencia " " a este modelo de von Neumann y este conjunto es discreto, es decir, también es decidible. ${\displaystyle 0}$ ${\displaystyle S}$ ${\displaystyle \omega }$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle <}$ ${\displaystyle \in }$ ${\displaystyle \phi (n,m):=(n=m)}$

Como se analizó, la inducción de fórmulas aritméticas es un teorema. Sin embargo, cuando no se asume una inducción matemática completa (o axiomas más fuertes como la separación completa) en una teoría de conjuntos, existe un problema con respecto a la existencia de operaciones aritméticas. La teoría de primer orden de la aritmética de Heyting tiene la misma firma y axiomas no lógicos que la aritmética de Peano . Por el contrario, la firma de la teoría de conjuntos no contiene suma " " ni multiplicación " ". en realidad no permite la recursividad primitiva para definiciones de funciones de lo que sería (donde " " aquí denota el producto cartesiano del conjunto, que no debe confundirse con la multiplicación anterior). De hecho, a pesar de tener el axioma de reemplazo, la teoría no prueba que exista un conjunto que capture la función de suma . En la siguiente sección, se aclara qué axioma teórico de conjuntos se puede afirmar para probar la existencia de este último como un conjunto de funciones, junto con su relación deseada con cero y su sucesor. ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle +}$ ${\displaystyle \times }$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle \omega }$ ${\displaystyle h\colon (x\times \omega )\to y}$ ${\displaystyle \times }$ ${\displaystyle +\colon (\omega \times \omega )\to \omega }$

Mucho más allá del predicado de igualdad, el modelo de aritmética obtenido valida

${\displaystyle {\mathsf {HA}}\vdash \forall n.\forall m.{\big (}\phi (n,m)\lor \neg \phi (n,m){\big )}}$

para cualquier fórmula sin cuantificadores. De hecho, la eliminación conservadora y la doble negación son posibles para cualquier fórmula de Harrop . ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle {\mathsf {HA}}}$

Funciones aritméticas de recursividad

Yendo un paso más allá , se debe agregar el axioma que garantiza la definición de funciones de conjunto a través de funciones de conjunto de pasos de iteración: para cualquier conjunto , conjunto y , también debe existir una función obtenida haciendo uso del primero, es decir, tal que y . Este principio de iteración o recursividad es similar al teorema de recursión transfinita , excepto que está restringido a funciones establecidas y argumentos ordinales finitos, es decir, no hay ninguna cláusula sobre ordinales límite . Funciona como el equivalente teórico establecido de un objeto de números naturales en la teoría de categorías . Esto permite una interpretación completa de la aritmética de Heyting en nuestra teoría de conjuntos, incluidas las funciones de suma y multiplicación. ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle y}$ ${\displaystyle z\in y}$ ${\displaystyle f\colon y\to y}$ ${\displaystyle g\colon \omega \to y}$ ${\displaystyle g(0)=z}$ ${\displaystyle g(Sn)=f(g(n))}$ ${\displaystyle {\mathsf {HA}}}$

Con ello, y están bien fundamentados, en el sentido de la formulación de subconjuntos inductivos . Además, también se puede definir la aritmética de los números racionales y demostrar sus propiedades, como la unicidad y la numerabilidad. ${\displaystyle {\mathbb {N} }}$ ${\displaystyle {\mathbb {Z} }}$ ${\displaystyle {\mathbb {Q} }}$

Recursión de los axiomas de la teoría de conjuntos

Recuerde que es la abreviatura de , donde es la abreviatura del predicado de la función total, una proposición en términos de uso de cuantificadores acotados. Si ambos lados son conjuntos, entonces por extensionalidad esto también es equivalente a . (Aunque por un ligero abuso de notación formal, como ocurre con el símbolo " ", el símbolo " " también se usa comúnmente con las clases de todos modos). ${\displaystyle h\simeq y^{x}}$ ${\displaystyle \forall f.{\big (}f\in h\leftrightarrow f\in y^{x}{\big )}}$ ${\displaystyle f\in y^{x}}$ ${\displaystyle h=y^{x}}$ ${\displaystyle \in }$ ${\displaystyle =}$

Una teoría de conjuntos con el modelo que permite el principio de recursividad, explicado anteriormente, también demostrará que, para todos los naturales y , los espacios funcionales ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle n}$ ${\displaystyle m}$

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

son conjuntos. De hecho, la recursividad acotada es suficiente, es decir, el principio para clases definidas. ${\displaystyle \Delta _{0}}$

Por el contrario, el principio de recursividad se puede demostrar a partir de una definición que implique la unión de funciones recursivas en dominios finitos. Relevante para esto es la clase de funciones parciales tales que todos sus miembros tienen valores de retorno solo hasta algún límite de número natural, que puede expresarse por . La existencia de esto como conjunto se vuelve demostrable asumiendo que los espacios de funciones individuales forman todos conjuntos. Para tal fin ${\displaystyle \omega }$ ${\displaystyle \cup _{n\in \omega }y^{\{0,1,\dots ,n-1\}}}$ ${\displaystyle y^{n}}$

Con este axioma, cualquier espacio de este tipo es ahora un conjunto de subconjuntos de y esto es estrictamente más débil que la separación completa. En particular, la adopción de este principio tiene un tono teórico genuino, en contraste con una incorporación directa de principios aritméticos a nuestra teoría. Y es un principio modesto en la medida en que estos espacios funcionales son dóciles: cuando, en cambio, se supone una inducción completa o una exponenciación completa, se adoptan espacios funcionales o productos cartesianos n veces, se puede demostrar que se conserva la contabilización. ${\displaystyle n\times y}$ ${\displaystyle y}$ ${\displaystyle y^{n}}$

En exponenciación finita positiva, el principio de recursividad es un teorema. Además, ahora también se pueden demostrar numerosas formas del principio del casillero , por ejemplo, que en un conjunto finitamente indexado, cada autoinyección es también una sobreyección. Como consecuencia, la cardinalidad de conjuntos finitos, es decir, el ordinal finito de von Neumann, es demostrablemente única. Los conjuntos discretos finitamente indexados son solo conjuntos finitos. En particular, los subconjuntos de indexados finitamente son finitos. Tomar cocientes o tomar la unión binaria o el producto cartesiano de dos conjuntos preserva la finitud, la subfinitud y la indexación finita. ${\displaystyle {\mathsf {ECTS}}}$ ${\displaystyle \omega }$

Los axiomas de la teoría de conjuntos enumerados hasta ahora incorporan la aritmética de primer orden y son suficientes como marco formalizado para una buena parte de las matemáticas comunes. La restricción a dominios finitos se elimina en el axioma de exponenciación estrictamente más fuerte que aparece a continuación. Sin embargo, ese axioma tampoco implica el esquema de inducción completo para fórmulas con cuantificadores libres en el dominio de conjuntos, ni un principio de elección dependiente. Del mismo modo, existen principios de Cobro que constructivamente no están implícitos en el Reemplazo, como se analiza más adelante. Una consecuencia de esto es que para algunos enunciados de mayor complejidad o indirectos, incluso si casos concretos de interés pueden ser demostrables, la teoría puede no probar el cierre universal. Más fuerte que esta teoría con exponenciación finita es más inducción completa. Implica el principio de recursividad incluso para clases y cosas que son únicas. Ya ese principio de recursividad cuando se restringe a prueba la exponenciación finita, y también la existencia de un cierre transitivo para cada conjunto con respecto a (ya que la formación de uniones es ). Con ello, las construcciones más comunes preservan la contabilidad. Las uniones generales sobre un conjunto finitamente indexado de conjuntos finitamente indexados están nuevamente indexadas finitamente, cuando al menos se asume inducción para predicados - (con respecto al lenguaje de la teoría de conjuntos, y esto se cumple independientemente de la decidibilidad de sus relaciones de igualdad). ${\displaystyle {\mathsf {ECTS}}}$ ${\displaystyle g}$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \in }$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \Sigma _{1}}$

Inducción sin conjuntos infinitos

Antes de analizar incluso los conjuntos clásicamente incontables, esta última sección retrocede un paso hacia un contexto más parecido a . La suma de números, considerada como relación sobre ternas, es una colección infinita, al igual que la colección de números naturales propiamente dichos. Pero tenga en cuenta que se pueden adoptar esquemas de inducción (para conjuntos, ordinales o en conjunción con una clasificación de números naturales), sin postular nunca que el conjunto de naturales existe como un conjunto. Como se señaló, la aritmética de Heyting es biinterpretable con una teoría de conjuntos tan constructiva, en la que se postula que todos los conjuntos están en biyección con un ordinal. El predicado BIT es un medio común para codificar conjuntos en aritmética. ${\displaystyle {\mathsf {BCST}}}$ ${\displaystyle {\mathsf {HA}}}$

Este párrafo enumera algunos principios débiles de inducción de números naturales estudiados en la teoría de prueba de las teorías aritméticas con la suma y la multiplicación en su firma. Éste es el marco donde estos principios se entienden mejor. Las teorías pueden definirse mediante formulaciones limitadas o variaciones de esquemas de inducción que, además, sólo permiten predicados de complejidad restringida. En el lado clásico de primer orden, esto conduce a teorías entre la aritmética de Robinson y la aritmética de Peano : la teoría no tiene ninguna inducción. tiene inducción matemática completa para fórmulas aritméticas y tiene ordinal , lo que significa que la teoría permite codificar ordinales de teorías más débiles como una relación recursiva solo en los naturales. Las teorías también pueden incluir símbolos adicionales para funciones particulares. Muchas de las teorías aritméticas bien estudiadas son débiles en cuanto a la prueba de totalidad para algunas funciones de más rápido crecimiento . Algunos de los ejemplos más básicos de aritmética incluyen la aritmética de funciones elementales , que incluye la inducción para fórmulas aritméticas simplemente acotadas, es decir, con cuantificadores en rangos de números finitos. La teoría tiene un ordinal teórico de prueba (el mejor ordenamiento recursivo menos no probado ) de . El esquema de inducción para fórmulas existenciales aritméticas permite la inducción de aquellas propiedades de los naturales cuya validación es computable mediante una búsqueda finita con un tiempo de ejecución ilimitado (cualquiera, pero finito). El esquema también es clásicamente equivalente al esquema de inducción. La aritmética clásica de primer orden, relativamente débil, que adopta ese esquema se denota y demuestra las funciones recursivas primitivas totales. La teoría es conservadora sobre la aritmética recursiva primitiva . Tenga en cuenta que la -inducción también es parte del sistema básico de matemáticas inversas de segundo orden , siendo sus otros axiomas la comprensión adicional de subconjuntos de naturales. La teoría es conservadora . Todas las últimas teorías aritméticas mencionadas tienen ordinales . ${\displaystyle {\mathsf {Q}}}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {Q}}}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle {\mathsf {EFA}}}$ ${\displaystyle \omega ^{3}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle {\mathsf {I\Sigma }}_{1}}$ ${\displaystyle {\mathsf {I\Sigma }}_{1}}$ ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle {\mathsf {PRA}}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle {\mathsf {RCA}}_{0}}$ ${\displaystyle {\mathsf {Q}}}$ ${\displaystyle \Delta _{1}^{0}}$ ${\displaystyle {\mathsf {RCA}}_{0}}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle {\mathsf {I\Sigma }}_{1}}$ ${\displaystyle \omega ^{\omega }}$

Mencionemos un paso más más allá del esquema de inducción. La falta de esquemas de inducción más sólidos significa, por ejemplo, que algunas versiones ilimitadas del principio del casillero no son demostrables. Una relativamente débil es la afirmación del tipo teorema de Ramsey expresada aquí de la siguiente manera: Para cualquier codificación de un mapa de coloración , asociando cada uno con un color , no es el caso que para cada color exista un número de entrada umbral más allá del cual nunca se alcanza. las asignaciones ya no devuelven valor. (En el contexto clásico y en términos de conjuntos, esta afirmación sobre la coloración puede formularse positivamente, diciendo que siempre existe al menos un valor de retorno tal que, en efecto, para algún dominio ilimitado se cumple que . En palabras, cuando se proporciona infinitas asignaciones enumeradas, cada una de las cuales es de uno de diferentes colores posibles, se afirma que siempre existe un color particular de infinitos números y que, por lo tanto, el conjunto puede especificarse, sin siquiera tener que inspeccionar las propiedades de . ser concretamente especificable y por lo tanto esa formulación es una afirmación más fuerte.) Se necesita una mayor indirección, que en la inducción para meros enunciados existenciales, para reformular formalmente tal negación (la afirmación tipo teorema de Ramsey en la formulación original anterior) y probarla. Es decir, reformular el problema en términos de la negación de la existencia de un número umbral conjunto, dependiendo de todos los hipotéticos , más allá del cual la función todavía tendría que alcanzar algún valor de color. Más específicamente, la fuerza del principio de limitación requerido está estrictamente entre el esquema de inducción en y . Para las propiedades en términos de valores de retorno de funciones en dominios finitos, la verificación de fuerza bruta mediante la verificación de todas las entradas posibles tiene una sobrecarga computacional que es mayor para dominios más grandes, pero siempre finita. La aceptación de un esquema de inducción valida el antiguo principio del casillero infinito, que se refiere a dominios ilimitados y, por lo tanto, a asignaciones con infinitas entradas. ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle m>0}$ ${\displaystyle f}$ ${\displaystyle n\in \omega }$ ${\displaystyle \{0,1,\dots ,m-1\}}$ ${\displaystyle c<m}$ ${\displaystyle n_{c}}$ ${\displaystyle c}$ ${\displaystyle k}$ ${\displaystyle K\subset \omega }$ ${\displaystyle \forall (n\in K).f(n)=k}$ ${\displaystyle f}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle k}$ ${\displaystyle n_{c}}$ ${\displaystyle {\mathsf {I\Sigma }}_{1}^{0}}$ ${\displaystyle {\mathsf {I\Sigma }}_{2}^{0}}$ ${\displaystyle {\mathsf {I\Sigma }}_{2}^{0}}$

Vale la pena señalar que en el programa de la aritmética predicativa , incluso el esquema de inducción matemática ha sido criticado por ser posiblemente impredicativo , cuando los números naturales se definen como el objeto que cumple este esquema, que a su vez se define en términos de todos los naturales.

exponenciación

El clásico sin el axioma Powerset tiene modelos naturales en clases de conjuntos de tamaño hereditario menor que ciertos cardinales incontables. ^[20] En particular, sigue siendo coherente con el hecho de que todos los conjuntos existentes (incluidos los conjuntos que contienen reales) son subcontables , e incluso contables. Una teoría así equivale esencialmente a aritmética de segundo orden . Todos los conjuntos que son subcontables pueden ser constructivamente consistentes incluso en el presente de conjuntos incontables, como se presenta ahora. ${\displaystyle {\mathsf {ZFC}}}$

Se discutieron posibles principios de elección, ya se adoptó una forma debilitada del esquema de separación y se debilitarán más axiomas estándar para una teoría más predicativa y constructiva. El primero de ellos es el axioma de Powerset, que se adopta en forma de espacio de funciones características. El siguiente axioma es estrictamente más fuerte que su colgante para dominios finitos discutidos anteriormente: ${\displaystyle {\mathsf {ZFC}}}$ ${\displaystyle {\mathrm {Exp} }}$

La formulación aquí utiliza nuevamente la notación conveniente para espacios funcionales, como se discutió anteriormente. En palabras, el axioma dice que dados dos conjuntos , la clase de todas las funciones es, de hecho, también un conjunto. Esto ciertamente es necesario, por ejemplo, para formalizar el mapa de objetos de un functor hom interno como ${\displaystyle x,y}$ ${\displaystyle y^{x}}$ ${\displaystyle {\mathrm {hom} }({\mathbb {N} },-).}$

Al adoptar tal declaración de existencia, la cuantificación de los elementos de ciertas clases de funciones (totales) ahora solo abarca conjuntos. Considere la colección de pares que validan la relación de separación . A través de una separación limitada, esto ahora constituye un subconjunto de . Este ejemplo muestra que el axioma de exponenciación no solo enriquece el dominio de los conjuntos directamente, sino que, a través de la separación, también permite la derivación de aún más conjuntos, y esto además fortalece otros axiomas. ${\displaystyle \forall f}$ ${\displaystyle \langle a,b\rangle \in x\times x}$ ${\displaystyle \exists (f\in {\mathbb {N} }^{x}).f(a)\neq f(b)}$ ${\displaystyle x\times x}$

En particular, estos cuantificadores acotados ahora abarcan espacios funcionales que son demostrablemente incontables y, por lo tanto, incluso clásicamente incontables. Por ejemplo, la colección de todas las funciones donde , es decir, el conjunto de puntos subyacentes al espacio de Cantor , es incontable, según el argumento diagonal de Cantor , y, en el mejor de los casos, puede considerarse un conjunto subcontable. En esta teoría, ahora también se pueden cuantificar subespacios de espacios como , que es una noción de tercer orden sobre los naturales. (En esta sección y en adelante, el símbolo para el semianillo de números naturales en expresiones como se usa, o se escribe , solo para evitar la combinación de exponenciación cardinal con ordinal). En términos generales, los conjuntos clásicamente incontables, como por ejemplo estos espacios funcionales, tienden no tener igualdad computable decidible. ${\displaystyle f\colon \omega \to 2}$ ${\displaystyle 2:=SS0=\{0,1\}}$ ${\displaystyle 2^{\mathbb {N} }}$ ${\displaystyle 2^{\mathbb {N} }}$ ${\displaystyle y^{\mathbb {N} }}$ ${\displaystyle \omega \to y}$

Al tomar la unión general sobre una familia indexada , también el producto dependiente o indexado, wirtten , es ahora un conjunto. Para constante , esto nuevamente se reduce al espacio funcional . Y tomando la unión general sobre los propios espacios funcionales, siempre que la clase de poder de sea un conjunto, entonces también el superconjunto de ahora es un conjunto, lo que brinda un medio para hablar sobre el espacio de funciones parciales en . ${\displaystyle x}$ ${\displaystyle \{y_{i}\}_{i}}$ ${\displaystyle \Pi _{i\in x}\,y_{i}}$ ${\displaystyle y_{i}}$ ${\displaystyle y^{x}}$ ${\displaystyle x}$ ${\displaystyle \cup _{s\subset x}y^{s}}$ ${\displaystyle y^{x}}$ ${\displaystyle x}$

Sindicatos y rendición de cuentas

Con la exponenciación, la teoría prueba la existencia de cualquier función recursiva primitiva en , y en particular en los incontables espacios funcionales fuera de . De hecho, con espacios funcionales y los ordinales finitos de von Neumann como dominios, podemos modelar como se discutió y así codificar ordinales en la aritmética. Además, se obtiene el número ordinal exponenciado como un conjunto, que puede caracterizarse como el conjunto contado de palabras en un alfabeto infinito . La unión de todas las secuencias finitas de un conjunto contable es ahora un conjunto contable. Además, para cualquier familia contable de funciones de conteo junto con sus rangos, la teoría demuestra que la unión de esos rangos es contable. Por el contrario, al no asumir una elección contable, incluso es consistente con que el conjunto incontable sea la unión de un conjunto contable de conjuntos contables. ${\displaystyle x\times \omega \to y}$ ${\displaystyle \omega }$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle \cup _{n\in \omega }\omega ^{n}}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathbb {R} }}$

La lista aquí no está de ninguna manera completa. Muchos teoremas sobre los diversos predicados de existencia de funciones se mantienen, especialmente cuando se supone una elección contable, lo cual, como se señaló, nunca se asume implícitamente en esta discusión.

Por último, con la exponenciación, cualquier unión finitamente indexada de una familia de resp. subfinitamente indexada. Los conjuntos subcontables están en sí mismos indexados de manera subfinita. subcontable también. La teoría también demuestra que la colección de todos los subconjuntos contables de cualquier conjunto es un conjunto en sí mismo. Con respecto a este subconjunto de la clase de poder , algunas cuestiones de cardinalidad natural también pueden resolverse clásicamente solo con Elección, al menos para incontables . ${\displaystyle x}$ ${\displaystyle {\mathcal {P}}_{x}}$ ${\displaystyle x}$

La clase de todos los subconjuntos de un conjunto.

Dada una secuencia de conjuntos, se pueden definir nuevas secuencias de este tipo, por ejemplo, en . Pero, en particular, en un marco de teoría matemática de conjuntos, la colección de todos los subconjuntos de un conjunto no se define en una construcción ascendente a partir de sus constituyentes sino a través de una comprensión de todos los conjuntos en el dominio del discurso. La caracterización estándar e independiente de la clase de poder de un conjunto implica una cuantificación universal ilimitada, es decir , donde previamente se definió también en términos del predicado de membresía . En este caso, un enunciado expresado como debe tomarse a priori como una proposición limitada a un conjunto y no es equivalente a ella. De hecho, la declaración en sí lo es . Si es un conjunto, entonces la cuantificación definitoria abarca incluso , lo que hace que el axioma del conjunto de poderes sea impredicativo . ${\displaystyle \langle a,b\rangle \mapsto \langle \langle \rangle ,\langle a\rangle ,\langle b\rangle ,\langle a,b\rangle \rangle }$ ${\displaystyle x}$ ${\displaystyle \forall u.\left(u\in {\mathcal {P}}_{x}\leftrightarrow u\subset x\right)}$ ${\displaystyle \subset }$ ${\displaystyle \in }$ ${\displaystyle \forall (u\in {\mathcal {P}}_{x}).Q(x)}$ ${\displaystyle \forall u.{\big (}u\subset x\to Q(x){\big )}}$ ${\displaystyle y={\mathcal {P}}_{x}}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle {\mathcal {P}}_{x}}$ ${\displaystyle {\mathcal {P}}_{x}}$

Recordemos que un miembro del conjunto de funciones características corresponde a un predicado que es decidible en un conjunto , que por tanto determina un subconjunto separable . A su vez, la clase de todos los subconjuntos separables de ahora también es un conjunto, a través de Reemplazo. Sin embargo, es posible que no tenga propiedades deseables, por ejemplo, estar cerrado bajo operaciones interminables, como las uniones sobre conjuntos de índices contablemente infinitos: para una secuencia contable , el subconjunto de validación para todos existe como un conjunto. Pero es posible que no sea separable y, por lo tanto, no necesariamente sea miembro de . Mientras tanto, en la lógica clásica, todos los subconjuntos de un conjunto son trivialmente separables, lo que significa que , por supuesto, contiene cualquier subconjunto. En comparación con la lógica clásica, esto significa además que la exponenciación convierte la clase de potencia en un conjunto. ${\displaystyle 2^{x}}$ ${\displaystyle x}$ ${\displaystyle s\subset x}$ ${\displaystyle {\mathcal {D}}_{x}\subset {\mathcal {P}}_{x}}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {D}}_{x}}$ ${\displaystyle u_{n}\in {\mathcal {D}}_{x}}$ ${\displaystyle U:=\cup _{k\in \omega }u_{k}}$ ${\displaystyle x}$ ${\displaystyle (a\in U)\leftrightarrow \exists (m\in \omega ).a\in u_{m}}$ ${\displaystyle a\in x}$ ${\displaystyle {\mathcal {D}}_{x}}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {D}}_{x}={\mathcal {P}}_{x}}$ ${\displaystyle {\mathcal {D}}_{x}}$

Traducir los resultados de teorías matemáticas basadas en la teoría de conjuntos, como la topología de conjuntos de puntos o la teoría de la medida, a un marco constructivo es un ir y venir sutil. Por ejemplo, while es un campo de conjuntos , para que forme un σ-álgebra por definición también requiere el carácter cerrado antes mencionado de las uniones. Pero si bien un dominio de subconjuntos puede no exhibir dicha propiedad de cierre de manera constructiva, clásicamente una medida es continua desde abajo y, por lo tanto, su valor en una unión infinita también puede expresarse en cualquier caso sin referencia a ese conjunto como entrada de función, es decir, a partir del secuencia creciente de los valores de la función en uniones finitas. ${\displaystyle {\mathcal {D}}_{x}}$ ${\displaystyle \mu }$ ${\displaystyle \lim _{n\to \infty }}$ ${\displaystyle \mu (\cup _{k\leq n}u_{k})}$

Además de la clase de conjuntos desmontables, ahora también se han demostrado que otras subclases de cualquier clase de poder son conjuntos. Por ejemplo, la teoría también demuestra esto para la colección de todos los subconjuntos contables de cualquier conjunto.

La riqueza de la clase de poder total en una teoría sin un tercero excluido puede entenderse mejor considerando pequeños conjuntos clásicamente finitos. Para cualquier proposición , considere la subclase de (es decir, o ). Es igual cuando se puede rechazar y es igual (es decir ), cuando se puede probar. Pero también puede que no sea decidible en absoluto. Consideremos tres proposiciones indecidibles diferentes, ninguna de las cuales implica de manera comprobada otra. Se pueden utilizar para definir tres subclases del singleton , ninguna de las cuales es demostrablemente igual. Desde este punto de vista, la clase de potencia del singleton, generalmente denotada por , se llama álgebra del valor de verdad y no necesariamente tiene solo dos elementos. ${\displaystyle P}$ ${\displaystyle B:=\{x\in 1\mid P\}}$ ${\displaystyle 1}$ ${\displaystyle \{0\}}$ ${\displaystyle S0}$ ${\displaystyle B=0}$ ${\displaystyle P}$ ${\displaystyle B=1}$ ${\displaystyle B=S0}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle 1}$ ${\displaystyle {\mathcal {P}}_{1}}$ ${\displaystyle \Omega }$

Con Exponenciación, la clase de potencia del singleton, ser un conjunto ya implica Powerset para conjuntos en general. La prueba se realiza mediante el reemplazo de la asociación de to y un argumento de por qué todos los subconjuntos están cubiertos. El conjunto también se inyecta en el espacio funcional . ${\displaystyle {\mathcal {P}}_{1}}$ ${\displaystyle f\in {{\mathcal {P}}_{1}}^{x}}$ ${\displaystyle \{z\in x\mid 0\in f(z)\}\in {\mathcal {P}}_{x}}$ ${\displaystyle 2^{x}}$ ${\displaystyle {{\mathcal {P}}_{1}}^{x}}$

Si la teoría se demuestra por encima de un conjunto (como por ejemplo lo hace incondicionalmente), entonces el subconjunto de es una función con . Afirmar eso es afirmar que el medio excluido es válido para . ${\displaystyle B}$ ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle b:=\{\langle 0,B\rangle \}}$ ${\displaystyle 1\times {\mathcal {P}}_{1}}$ ${\displaystyle b\colon 1\to {\mathcal {P}}_{1}}$ ${\displaystyle {\big (}b(0)=1{\big )}\leftrightarrow P}$ ${\displaystyle {\mathcal {P}}_{1}=2}$ ${\displaystyle P}$

Se ha señalado que el conjunto vacío y el conjunto mismo son, por supuesto, dos subconjuntos de , es decir . Que también sea cierto en una teoría depende de una simple disyunción: ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 2\subset {\mathcal {P}}_{1}}$ ${\displaystyle {\mathcal {P}}_{1}\subset 2}$

${\displaystyle {\big (}\forall (x\in {\mathcal {P}}_{1}).(0\in x\lor 0\notin x){\big )}\to \,{\mathcal {P}}_{1}\subset 2}$.

Entonces, suponiendo que solo se trate de fórmulas acotadas, la separación predicativa permite demostrar que la clase de potencia es un conjunto. Y en este contexto, Powerset también demuestra su elección completa. (En el contexto de , el medio excluido acotado de hecho ya convierte la teoría de conjuntos en clásica, como se analiza más adelante). ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathcal {P}}_{1}}$ ${\displaystyle {\mathsf {IZF}}}$

La separación completa equivale a asumir simplemente que cada subclase individual de es un conjunto. Suponiendo una separación total, tanto la elección completa como la regularidad resultan . ${\displaystyle 1}$ ${\displaystyle {\mathrm {PEM} }}$

Suponiendo que en esta teoría, la inducción de conjuntos se vuelve equivalente a la regularidad y el reemplazo se vuelve capaz de demostrar la separación total. ${\displaystyle {\mathrm {PEM} }}$

Tenga en cuenta que las relaciones cardinales que involucran conjuntos incontables también son difíciles de alcanzar en , donde la caracterización de la incontable se simplifica a . Por ejemplo, con respecto al poder incontable , es independiente de la teoría clásica si todos los tienen , ni lo prueba . Véase la hipótesis del continuo y el teorema de Easton relacionado . ${\displaystyle {\mathsf {ZFC}}}$ ${\displaystyle |\omega |<|x|}$ ${\displaystyle 2^{|\omega |}}$ ${\displaystyle x}$ ${\displaystyle 2^{|\omega |}\leq |x|}$ ${\displaystyle 2^{|\omega |}<2^{|x|}}$

Nociones teóricas de categorías y tipos

Entonces, en este contexto con la exponenciación, la aritmética de primer orden tiene un modelo y todos los espacios funcionales entre conjuntos existen. Estas últimas son más accesibles que las clases que contienen todos los subconjuntos de un conjunto, como es el caso de los objetos exponenciales o. Subobjetos en la teoría de categorías. En términos teóricos de categorías , la teoría corresponde esencialmente a pretopos cartesianos cerrados de Heyting constructivamente bien apuntados con ( cuando se adopta el Infinito) un objeto de números naturales . La existencia de un conjunto de poderes es lo que convertiría un pretopos de Heyting en un topos elemental . ^[21] Cada 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 y el conjunto de poderes completos. Una forma de corresponde a cualquier subobjeto que tenga un complemento, en cuyo caso llamamos al topos booleano. El teorema de Diaconescu en su forma topos original dice que esto se cumple si cualquier coecualizador de dos monomorfismos que no se cruzan tiene una sección. Esta última es una formulación de elección . El teorema de Barr establece que cualquier topos admite una sobreyección de un topos booleano, en relación con los enunciados clásicos que se pueden demostrar de manera intuicionista. ${\displaystyle {\mathsf {BCST}}+{\mathrm {Exp} }}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathrm {PEM} }}$

En teoría de tipos, la expresión " " existe por sí sola y denota espacios funcionales , una noción primitiva. Estos tipos (o, en teoría de conjuntos, clases o conjuntos) aparecen naturalmente, por ejemplo, como el tipo de biyección curry entre y , una adjunción . Una teoría de tipos típica con capacidad de programación general, y ciertamente aquellas que pueden modelar , lo que se considera una teoría de conjuntos constructiva, tendrá un tipo de números enteros y espacios funcionales que representen y, como tales, también incluirán tipos que no son contables. Esto simplemente quiere decir, o implica, que entre los términos de función , ninguno tiene la propiedad de ser una sobreyecció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\colon {\mathbb {Z} }\to ({\mathbb {Z} }\to {\mathbb {Z} })}$

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

metalógico

Si bien la teoría no excede la consistencia de la aritmética de Heyting, agregar el medio excluido da una teoría que prueba los mismos teoremas que la clásica menos la regularidad. Por lo tanto, agregar Regularidad y Separación completa da un sonido clásico completo . Agregar elección completa y separación completa da menos regularidad. Por lo tanto, esto conduciría a una teoría más allá de la solidez de la teoría de tipos típica . ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {ZFC}}}$

La teoría presentada no demuestra que un espacio funcional no sea enumerable, en el sentido de inyecciones fuera de él. Sin más axiomas, la matemática intuicionista tiene modelos en funciones recursivas pero también formas de hipercomputación . ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$

Análisis

En esta sección se detalla la fuerza de. A modo de contexto, se mencionan posibles principios adicionales, que no son necesariamente clásicos y tampoco se consideran constructivos en general. Aquí conviene hacer una advertencia general: al leer las afirmaciones de equivalencia de proposiciones en el contexto computable, siempre se debe tener en cuenta qué principios de elección , inducción y comprensión se asumen silenciosamente. Véase también el análisis constructivo relacionado , ^[22] análisis factible y análisis computable . ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$

Hasta ahora, la teoría demuestra la unicidad de los campos ( pseudo ) ordenados completos de Arquímedes y Dedekind , con equivalencia mediante un isomorfismo único. El prefijo "pseudo" aquí resalta que, en cualquier caso, el orden no siempre será decidible constructivamente. Este resultado es relevante suponiendo que dichos modelos completos existan como conjuntos.

Topología

Independientemente de la elección del modelo, el sabor característico de una teoría constructiva de números se puede explicar mediante una proposición independiente . Consideremos un contraejemplo de la demostrabilidad constructiva del buen orden de los naturales, pero ahora integrado en los reales. Decir ${\displaystyle P}$

${\displaystyle M:=\{x\in {\mathbb {R} }\mid (x=0\land P)\lor (x=1)\}}$.

La distancia métrica mínima entre un punto y dicho subconjunto, lo que puede expresarse como, por ejemplo, puede no existir constructivamente de manera demostrable. De manera más general, esta propiedad de localización de los subconjuntos gobierna la bien desarrollada teoría constructiva del espacio métrico. ${\displaystyle \rho (0,M)}$

Ya sean reales de Cauchy o de Dedekind, entre otros, también son decidibles menos afirmaciones sobre la aritmética de los reales , en comparación con la teoría clásica.

secuencias de cauchy

La exponenciación implica principios de recursividad y, por lo tanto , uno puede razonar cómodamente sobre secuencias , sus propiedades de regularidad como , o sobre intervalos cada vez más reducidos en . Entonces esto permite hablar de secuencias de Cauchy y su aritmética. Este es también el enfoque de análisis adoptado en . ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$ ${\displaystyle s\colon \omega \to {\mathbb {Q} }}$ ${\displaystyle |s_{n}-s_{m}|\leq {\tfrac {1}{n}}+{\tfrac {1}{m}}}$ ${\displaystyle \omega \to ({\mathbb {Q} }\times {\mathbb {Q} })}$ ${\displaystyle {\mathsf {Z}}_{2}}$

reales de cauchy

Cualquier número real de Cauchy es una colección de tales secuencias, es decir, un subconjunto de un conjunto de funciones construidas con respecto a una relación de equivalencia . La exponenciación junto con la separación acotada demuestran que el conjunto de reales de Cauchy es un conjunto, simplificando así un poco el tratamiento lógico de los reales. ${\displaystyle \omega }$

Incluso en la teoría fuerte con una forma reforzada de Colección, los reales de Cauchy se comportan mal cuando no asumen una forma de elección contable , y son suficientes para la mayoría de los resultados. Esto se refiere a la integridad de las clases de equivalencia de tales secuencias, la equivalencia del conjunto completo con los reales de Dedekind, la existencia de un módulo de convergencia para todas las secuencias de Cauchy y la preservación de dicho módulo al tomar límites. ^[23] Un enfoque alternativo que se comporta ligeramente mejor es trabajar una colección de reales de Cauchy juntos con un módulo elegido, es decir, no solo con los números reales sino con un conjunto de pares, o incluso con un módulo fijo compartido por todos los números reales. . ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle {\mathrm {AC} _{\omega ,2}}}$

Hacia los reales de Dedekind

Como en la teoría clásica, los cortes de Dedekind se caracterizan utilizando subconjuntos de estructuras algebraicas tales como : Las propiedades de estar habitado, acotado numéricamente arriba, "cerrado hacia abajo" y "abierto hacia arriba" son todas fórmulas acotadas con respecto al conjunto dado subyacente al algebraico. estructura. Un ejemplo estándar de corte, el primer componente que de hecho exhibe estas propiedades, es la representación de dada 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 espacios de funciones justas como no permite ser un conjunto, por lo que tampoco lo es la clase de todos los subconjuntos que cumplen las propiedades nombradas. Lo que se requiere para que la clase de reales de Dedekind sea un conjunto es un axioma sobre la existencia de un conjunto de subconjuntos y esto se analiza más adelante en la sección sobre refinamiento binario. En un contexto sin Powerset, se supone que la elección contable en conjuntos finitos demuestra la incontabilidad del conjunto de todos los reales de Dedekind. ${\displaystyle \{0,1\}^{\mathbb {Q} }}$ ${\displaystyle {{\mathcal {P}}_{\mathbb {Q} }}}$ ${\displaystyle {\mathbb {Q} }}$ ${\displaystyle {\mathrm {PEM} }}$

Escuelas constructivas

La mayoría de las escuelas de análisis constructivo validan alguna elección y también - , como se define en la segunda sección sobre límites numéricos. Aquí hay algunas otras proposiciones empleadas en teorías de análisis constructivo que no son demostrables utilizando simplemente la lógica intuicionista básica: ${\displaystyle \mathrm {BD} }$ ${\displaystyle {\mathbb {N} }}$

• En el lado de las matemáticas recursivas (el marco constructivo "ruso" o "markoviano" con muchas abreviaturas, por ejemplo ), el primero tiene el principio de Markov , que es una forma de prueba por contradicción motivada por una búsqueda computable (capacidad de memoria ilimitada). Esto tiene un impacto notable en las declaraciones sobre números reales, como se analiza a continuación. En esta escuela se tiene incluso el principio de tesis de Church constructivo anticlásico , generalmente adoptado para funciones de teoría de números. El principio de tesis de Church expresado en el lenguaje de la teoría de conjuntos y formulado para funciones de conjuntos postula que todas ellas corresponden a programas computables que eventualmente se detienen ante cualquier argumento. En la teoría de la computabilidad, los números naturales correspondientes a índices de códigos de funciones computables que son totales están en la jerarquía aritmética , lo que significa que la pertenencia a cualquier índice se afirma validando una proposición. Esto quiere decir que tal colección de funciones sigue siendo una mera subclase de las naturales y, por lo tanto, cuando se la compara con algunos espacios funcionales clásicos, es conceptualmente pequeña. En este sentido, la adopción del postulado lo convierte en un conjunto "escaso", visto desde la teoría de conjuntos clásica. La subcontabilidad de conjuntos también se puede postular de forma independiente. ${\displaystyle {\mathsf {RUSS}}}$ ${\displaystyle {\mathrm {MP} }}$ ${\displaystyle {\mathrm {CT} }}$ ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle \forall x\,\exists y}$ ${\displaystyle {\mathrm {CT} }}$ ${\displaystyle \omega \to \omega }$
• Entonces, en otro extremo, en el lado intuicionista brouweriano ( ), está la inducción de barras , el teorema del abanico decidible que dice que las barras decidibles son uniformes, que se encuentran entre los principios más débiles discutidos a menudo, el esquema de Kripke (con elección contable que convierte todas las subclases de contables), o incluso el principio de continuidad anticlásico de Brouwer, que determina los valores de retorno de lo que se establece como función en secuencias interminables ya a través de segmentos iniciales finitos. ${\displaystyle {\mathsf {INT}}}$ ${\displaystyle {\mathrm {FAN} }_{\Delta }}$ ${\displaystyle \omega }$

Ciertas leyes en ambas escuelas se contradicen , de modo que elegir adoptar todos los principios de cualquiera de las escuelas refuta los teoremas del análisis clásico. Sigue siendo consistente con alguna elección, pero contradice la clásica y , que se explica a continuación. La independencia de la regla de la premisa con premisas de existencia establecidas no se comprende completamente, pero como principio de la teoría de números está en conflicto con los axiomas de la escuela rusa en algunos marcos. En particular, también se contradice , es decir, las escuelas constructivas tampoco pueden combinarse por completo. Algunos de los principios no pueden combinarse constructivamente en la medida en que juntos impliquen formas de , por ejemplo, más la contabilización de todos los subconjuntos de los naturales. Naturalmente, estas combinaciones tampoco son coherentes con otros principios anticlásicos. ${\displaystyle {\mathrm {WLPO} }}$ ${\displaystyle {\mathrm {CT} }_{0}}$ ${\displaystyle {\mathrm {WKL} }}$ ${\displaystyle {\mathrm {LLPO} }}$ ${\displaystyle {\mathrm {CT} }_{0}}$ ${\displaystyle {\mathrm {FAN} }_{\Delta }}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathrm {MP} }}$

Indescomponibilidad

Denota la clase de todos los conjuntos por . La capacidad de decisión de la membresía en una clase se puede expresar como membresía en . También observamos que, por definición, las dos clases extremas y son trivialmente decidibles. La pertenencia a esos dos es equivalente a las proposiciones triviales resp. . ${\displaystyle {\mathcal {V}}}$ ${\displaystyle R}$ ${\displaystyle R\cup ({\mathcal {V}}\setminus R)}$ ${\displaystyle {\mathcal {V}}}$ ${\displaystyle \{\}}$ ${\displaystyle x=x}$ ${\displaystyle \neg (x=x)}$

Llame a una clase indescomponible o cohesiva si, para cualquier predicado , ${\displaystyle R}$ ${\displaystyle \chi }$

${\displaystyle {\big (}\forall (x\in R).\chi (x)\lor \neg \chi (x){\big )}\to {\Big (}{\big (}\forall (x\in R).\chi (x){\big )}\lor {\big (}\forall (x\in R).\neg \chi (x){\big )}{\Big )}}$

Esto expresa que las únicas propiedades sobre las que se puede decidir son las propiedades triviales. Esto está bien estudiado en el análisis intuicionista. ${\displaystyle R}$

El llamado esquema de indescomponibilidad (Unzerlegbarkeit) para la teoría de conjuntos es un posible principio que establece que toda la clase es indescomponible. En términos extensivos, postula que las dos clases triviales son las únicas clases que son decidibles con respecto a la clase de todos los conjuntos. Para un predicado motivador simple, considere la pertenencia a la primera clase no trivial, es decir, la propiedad de estar vacío. Esta propiedad no es trivial en la medida en que separa algunos conjuntos: el conjunto vacío es miembro de , por definición, mientras que una gran cantidad de conjuntos no son miembros de . Pero, utilizando la Separación, por supuesto también se pueden definir varios conjuntos para los cuales la vacuidad no es decidible en absoluto en una teoría constructiva, es decir, la pertenencia a ellos no es demostrable para todos los conjuntos. Así que aquí la propiedad de la vacuidad no divide el dominio teórico establecido del discurso en dos partes decidibles. Para cualquier propiedad no trivial, el contrapositivo de dice que no puede ser decidible en todos los conjuntos. ${\displaystyle {\mathrm {UZ} }}$ ${\displaystyle {\mathcal {V}}}$ ${\displaystyle {\mathrm {UZ} }}$ ${\displaystyle x\in 1}$ ${\displaystyle x=\{\}}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1\cup ({\mathcal {V}}\setminus 1)}$ ${\displaystyle {\mathrm {UZ} }}$

${\displaystyle {\mathrm {UZ} }}$está implícito en el principio de uniformidad , que es consistente y se analiza a continuación. ${\displaystyle {\mathrm {UP} }}$ ${\displaystyle {\mathsf {CZF}}}$

Principios no constructivos

Por supuesto , muchos principios que definen las lógicas intermedias no son constructivos. y , que es para proposiciones simplemente negadas, puede presentarse como las reglas de De Morgan . Más específicamente, esta sección se ocupará de los enunciados en términos de predicados, especialmente los más débiles, expresados ​​en términos de unos pocos cuantificadores sobre conjuntos, además de predicados decidibles sobre números. Volviendo a la sección sobre funciones características, se puede llamar a una colección que se puede buscar si se pueden buscar todos sus subconjuntos separables, que a su vez corresponden a . Esta es una forma de - para . Tenga en cuenta que en el contexto de la exponenciación, dichas proposiciones sobre conjuntos ahora están ligadas a conjuntos. ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathrm {WPEM} }}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle A}$ ${\displaystyle \{0,1\}^{A}}$ ${\displaystyle \exists }$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle A}$

Particularmente valiosas en el estudio del análisis constructivo son las afirmaciones no constructivas comúnmente formuladas en términos de la colección de todas las secuencias binarias y las funciones características en el dominio aritmético están bien estudiadas. Aquí hay una proposición decidible en cada número , pero, como se demostró anteriormente, las declaraciones cuantificadas en términos de pueden no serlo. Como se sabe por el teorema de la incompletitud y sus variaciones, ya en la aritmética de primer orden, las funciones de ejemplo en se pueden caracterizar de tal manera que, si es consistente, las disyunciones en competencia , de baja complejidad, son cada una de ellas improbable (incluso si prueba la disyunción de los dos axiomáticamente.) ${\displaystyle f}$ ${\displaystyle A=\omega }$ ${\displaystyle f({\underline {\mathrm {n} }})=0}$ ${\displaystyle {\mathrm {n} }}$ ${\displaystyle f}$ ${\displaystyle {\mathbb {N} }}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle \exists }$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {PA}}}$

De manera más general, la aritmética , una afirmación esencialmente lógica, no constructiva y muy destacada, recibe el nombre de principio limitado de omnisciencia . En la teoría constructiva de conjuntos que se presenta a continuación, implica - , , la versión - del teorema del abanico, pero también se analiza a continuación. Recordemos ejemplos de frases famosas que se pueden escribir en forma de -, es decir, del tipo Goldbach: entre ellas se encuentran la conjetura de Goldbach , el último teorema de Fermat pero también la hipótesis de Riemann . Asumir la elección dependiente relativizada y el over clásico no permite demostrar más afirmaciones. postula una propiedad disyuntiva, al igual que el enunciado de decidibilidad más débil para funciones que son constantes ( -oraciones) , la aritmética - . Los dos están relacionados de manera similar a versus y esencialmente se diferencian por . a su vez implica la llamada versión "menor" . Esta es la versión (aritmética) de la regla de De Morgan no constructiva para una conjunción negada. Hay, por ejemplo, modelos de la teoría de conjuntos fuertes que separan tales afirmaciones, en el sentido de que pueden validar pero rechazar . ${\displaystyle \exists }$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathrm {LPO} }}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathrm {BD} }}$ ${\displaystyle {\mathbb {N} }}$ ${\displaystyle {\mathrm {MP} }}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle {\mathrm {WKL} }}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle {\mathrm {RDP} }}$ ${\displaystyle {\mathrm {LPO} }}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle \Pi _{0}^{2}}$ ${\displaystyle {\mathrm {LPO} }}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle {\mathrm {WLPO} }}$ ${\displaystyle \forall }$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathrm {WPEM} }}$ ${\displaystyle {\mathrm {MP} }}$ ${\displaystyle {\mathrm {WLPO} }}$ ${\displaystyle {\mathrm {LLPO} }}$ ${\displaystyle \exists }$ ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle {\mathrm {LLPO} }}$ ${\displaystyle {\mathrm {WLPO} }}$

Los principios disyuntivos sobre oraciones - generalmente apuntan a formulaciones equivalentes que deciden la separación en el análisis en un contexto con elección suave o . La afirmación expresada por traducido a números reales es equivalente a la afirmación de que la igualdad o la separación de dos reales cualesquiera es decidible (de hecho, decide la tricotomía). Entonces también es equivalente a la afirmación de que todo real es racional o irracional, sin necesidad ni construcción de un testigo para ninguna de las disyunciones. Asimismo, la afirmación expresada por para números reales es equivalente a que el orden de dos reales cualesquiera es decidible (dicotomía). Entonces también es equivalente a la afirmación de que si el producto de dos reales es cero, entonces cualquiera de los reales es cero, nuevamente sin un testigo. De hecho, las formulaciones de los tres principios de omnisciencia son entonces equivalentes a teoremas de separación, igualdad u orden de dos reales de esta manera. Aún se puede decir más sobre las secuencias de Cauchy que se aumentan con un módulo de convergencia. ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle {\mathrm {MP} }}$ ${\displaystyle {\mathrm {LPO} }}$ ${\displaystyle {\mathrm {LLPO} }}$ ${\displaystyle \leq }$

Una fuente famosa de indecidibilidad computable -y a su vez también de una amplia gama de proposiciones indecidibles- es el predicado que expresa que un programa de computadora es total.

Arboles infinitos

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

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

con membresía decidible, y esos árboles contienen elementos de tamaño finito grande y arbitrario. El llamado lema de Kőnig débil 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, el subsistema aritmético de segundo orden no prueba . Para entender esto, tenga en cuenta que hay árboles computables para los cuales no existe ningún camino computable a través de ellos. Para probar esto, se enumeran las secuencias computables parciales y luego se diagonalizan todas las secuencias computables totales en una secuencia computable parcial . Luego se puede desplegar un determinado árbol , uno exactamente compatible con los valores aún posibles de todas partes, que por construcción es incompatible con cualquier ruta computable total. ${\displaystyle {\mathrm {WKL} }}$ ${\displaystyle T}$ ${\displaystyle \omega \to \{0,1\}}$ ${\displaystyle {\mathsf {RCA}}_{0}}$ ${\displaystyle {\mathrm {WKL} }}$ ${\displaystyle K}$ ${\displaystyle d}$ ${\displaystyle K}$ ${\displaystyle d}$

En , el principio implica y - , una forma muy modesta de elección contable presentada anteriormente. Los dos primeros son equivalentes asumiendo ese principio de elección ya en el contexto aritmético más conservador. también es equivalente al teorema del punto fijo de Brouwer y otros teoremas sobre valores de funciones continuas en los reales. El teorema del punto fijo, a su vez, implica el teorema del valor intermedio , pero siempre tenga en cuenta que estas afirmaciones pueden depender de la formulación, ya que los teoremas clásicos sobre reales codificados pueden traducirse en diferentes variantes cuando se expresan en un contexto constructivo. ^[24] ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathrm {WKL} }}$ ${\displaystyle {\mathrm {LLPO} }}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle {\mathrm {AC} }_{\omega ,2}}$ ${\displaystyle {\mathrm {WKL} }}$

El , y algunas variantes del mismo, se refieren a gráficos infinitos y, por lo tanto, sus contrapositivos dan una condición para la finitud. Nuevamente para conectarnos con el análisis, sobre la teoría aritmética clásica , la afirmación de es, por ejemplo, equivalente a la compacidad de Borel con respecto a subcoberturas finitas del intervalo unitario real. es una afirmación de existencia estrechamente relacionada que involucra secuencias finitas en un contexto infinito. Además , en realidad son equivalentes. En esos son distintos, pero, después de asumir nuevamente alguna elección, aquí implica . ${\displaystyle {\mathrm {WKL} }}$ ${\displaystyle {\mathsf {RCA}}_{0}}$ ${\displaystyle {\mathrm {WKL} }}$ ${\displaystyle {\mathrm {FAN} }_{\Delta }}$ ${\displaystyle {\mathsf {RCA}}_{0}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathrm {WKL} }}$ ${\displaystyle {\mathrm {FAN} }_{\Delta }}$

Inducción

Inducción matemática

Se observó que en el lenguaje de conjuntos, los principios de inducción pueden leerse , con el antecedente definido más arriba, y con significado donde el conjunto siempre denota el modelo estándar de números naturales. A través del fuerte axioma del Infinito y la Separación predicativa, la validez de la inducción para definiciones o definidas por conjuntos ya estaba establecida y discutida a fondo. Para aquellos predicados que involucran sólo cuantificadores sobre , valida la inducción en el sentido de la teoría aritmética de primer orden. En un contexto de teoría de conjuntos donde hay un conjunto, este principio de inducción se puede utilizar para demostrar que las subclases definidas predicativamente son el conjunto mismo. El llamado esquema de inducción matemática completa ahora postula la igualdad de conjuntos de todas sus subclases inductivas. Como en la teoría clásica, también está implícito al pasar al esquema de Separación completo impredicativo. Como se indicó en la sección sobre Elección, principios de inducción como este también están implícitos en diversas formas de principios de elección. ${\displaystyle \mathrm {Ind} _{A}\to \omega \subset A}$ ${\displaystyle \mathrm {Ind} _{A}}$ ${\displaystyle \omega \subset A}$ ${\displaystyle \forall (n\in \omega ).n\in A}$ ${\displaystyle \omega }$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$

El principio de recursividad para funciones establecidas mencionado en la sección dedicada a la aritmética también está implícito en el esquema de inducción matemática completo sobre la estructura que modela los naturales (p. ej. ). Entonces, para ese teorema, otorgar un modelo de aritmética de Heyting, representa una alternativa a los principios de exponenciación. ${\displaystyle \omega }$

Las fórmulas de predicados utilizadas con el esquema deben entenderse como fórmulas de la teoría de conjuntos de primer orden. El cero denota el conjunto anterior y el conjunto denota el conjunto sucesor de , con . Según el Axioma del Infinito anterior, vuelve a ser miembro de . Tenga en cuenta que, a diferencia de una teoría aritmética, los naturales aquí no son los elementos abstractos en el dominio del discurso, sino elementos de un modelo. Como se ha observado en discusiones anteriores, al aceptar , ni siquiera para todos los conjuntos definidos predicativamente es necesariamente decidible la igualdad con un ordinal finito de von Neumann. ${\displaystyle 0}$ ${\displaystyle \{\}}$ ${\displaystyle Sn}$ ${\displaystyle n\in \omega }$ ${\displaystyle n\in Sn}$ ${\displaystyle \omega }$ ${\displaystyle {\mathsf {ECST}}}$

Establecer inducción

Yendo más allá de los principios de inducción anteriores, se tiene una inducción completa, que debe compararse con la inducción bien fundada . Al igual que la inducción matemática anterior, el siguiente axioma se formula como un esquema en términos de predicados y, por lo tanto, tiene un carácter diferente a los principios de inducción probados a partir de los axiomas de la teoría predicativa de conjuntos. Una variante del axioma sólo para fórmulas acotadas también se estudia de forma independiente y puede derivarse de otros axiomas.

Aquí se cumple de manera trivial, por lo que esto cubre el "caso inferior" en el marco estándar. Esto (así como la inducción de números naturales) puede restringirse nuevamente solo a las fórmulas de conjuntos acotados, en cuyo caso la aritmética no se ve afectada. ${\displaystyle \forall (z\in \{\}).\phi (z)}$ ${\displaystyle \phi (\{\})}$

En , el axioma demuestra la inducción en conjuntos transitivos y, por tanto, en particular también para conjuntos transitivos de conjuntos transitivos. Esta última es entonces una definición adecuada de los ordinales, e incluso una formulación -. La inducción de conjuntos, a su vez, permite la aritmética ordinal en este sentido. Además 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 constructiva de conjuntos y sus puntos fuertes comparativamente débiles . Esto también es válido para sus homólogos en la teoría de tipos. No se requiere reemplazo para demostrar la inducción sobre el conjunto de naturales a partir de la inducción de conjuntos, pero ese axioma es necesario para su aritmética modelada dentro de la teoría de conjuntos. ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle \Delta _{0}}$

El axioma de regularidad es un enunciado único con cuantificador universal sobre conjuntos y no un esquema. Como se muestra, implica y, por lo tanto, no es constructivo. Ahora, si se considera la negación de algún predicado y se escribe para la clase , la inducción se lee ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle \phi }$ ${\displaystyle \neg S}$ ${\displaystyle \Sigma }$ ${\displaystyle \{y\mid S(y)\}}$

${\displaystyle \forall (x\in \Sigma ).\neg (x\cap \Sigma =\{\})\,\,\leftrightarrow \,\,\Sigma =\{\}}$

A través del contrapositivo, la inducción de conjuntos implica todos los casos de regularidad, pero sólo con existencia doblemente negada en la conclusión. En la otra dirección, dados suficientes conjuntos transitivos , la regularidad implica cada instancia de inducción de conjuntos.

metalógico

La teoría formulada anteriormente se puede expresar con su colección de axiomas descartados en favor de los axiomas más débiles de Reemplazo y Exponenciación. Demuestra que los reales de Cauchy son un conjunto, pero no la clase de los reales de Dedekind. ${\displaystyle {\mathsf {CZF}}}$

Llame a un ordinal " " tricotómico si la relación de pertenencia irreflexiva " " entre sus miembros es tricotómica . Al igual que el axioma de regularidad, la inducción de conjuntos restringe los posibles modelos de " " y, por tanto, el de una teoría de conjuntos, como fue la motivación para el principio en los años 20. Pero la teoría constructiva aquí no prueba una tricotomía para todos los ordinales, mientras que los ordinales tricotómicos no se comportan bien con respecto a la noción de sucesor y rango. ${\displaystyle \in }$ ${\displaystyle \in }$

La fuerza teórica de prueba adicional lograda 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 prueba. Incluso sin exponenciación, la teoría actual con inducción de conjuntos tiene la misma fuerza teórica de prueba y demuestra las mismas funciones recursivas. Específicamente, su ordinal contable grande de prueba teórica es el ordinal de Bachmann-Howard . Este es también el ordinal de la teoría de conjuntos de Kripke-Platek clásica o intuicionista . Es consistente incluso con asumir que la clase de ordinales tricotómicos forman un conjunto. La teoría actual aumentada con este postulado de existencia de conjuntos ordinales demuestra la consistencia de . ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle {\mathsf {CZF}}}$

Aczel también fue uno de los principales desarrolladores de la teoría de conjuntos no bien fundamentada , que rechaza la inducción de conjuntos.

Relación con ZF

La teoría también constituye una presentación de la teoría de conjuntos de Zermelo-Fraenkel en el sentido de que están presentes variantes de sus ocho axiomas. Extensionalidad, Emparejamiento, Unión y Reemplazo son efectivamente idénticos. La separación se adopta en una forma predicativa débil, mientras que el infinito se expresa en una formulación fuerte. De manera similar a la formulación clásica, este axioma de separación y la existencia de cualquier conjunto ya prueban el axioma del conjunto vacío. La exponenciación para dominios finitos y la inducción matemática completa también están implícitas en sus variantes adoptadas más fuertes. Sin el principio del tercero excluido, la teoría aquí carece, en su forma clásica, de separación completa, conjunto de poderes y regularidad. Aceptar ahora conduce exactamente a la teoría clásica. ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathrm {PEM} }}$

The following highlights the different readings of a formal theory. Let ${\displaystyle \mathrm {CH} }$ denote the continuum hypothesis and ${\displaystyle B:=\{z\in 1\mid \mathrm {CH} \}}$ so that ${\displaystyle 0\in B\leftrightarrow \mathrm {CH} }$. Then ${\displaystyle b:=B\cup \{1\}}$ is inhabited by ${\displaystyle 1}$ and any set that is established to be a member of ${\displaystyle b}$ either equals ${\displaystyle 0}$ or ${\displaystyle 1}$. Induction on ${\displaystyle \omega }$ implies that it cannot consistently be negated that ${\displaystyle b}$ has some least natural number member. The value of such a member can be shown to be independent of theories such as ${\displaystyle {\mathsf {ZFC}}}$. Nonetheless, any classical set theory like ${\displaystyle {\mathsf {ZFC}}}$ also proves there exists such a number.

Strong Collection

Having discussed all the weakened forms of the classical set theory axioms, Replacement and Exponentiation can be further strengthened without losing a type theoretical interpretation, and in a way that is not going beyond ${\displaystyle {\mathsf {ZF}}}$.

So firstly, one may reflect upon the strength of the axiom of replacement, also in the context of the classical set theory. For any set ${\displaystyle y}$ and any natural ${\displaystyle n}$, there exists the product ${\displaystyle y^{n}}$ recursively given by ${\displaystyle y^{n-1}\times y}$, which have ever deeper rank. Induction for unbound predicates proves that these sets exist for all of the infinitely many naturals. Replacement "for ${\displaystyle n\mapsto y^{n}}$" now moreover states that this infinite class of products can be turned into the infinite set, ${\displaystyle \{p\mid \exists (n\in \omega ).p=y^{n}\}}$. This is also not a subset of any previously established set.

Going beyond those axioms also seen in Myhill's typed approach, consider the discussed constructive theory with Exponentiation and Induction, but now strengthened by the collection schema. In ${\displaystyle {\mathsf {ZF}}}$ it is equivalent to Replacement, unless the powerset axiom is dropped. In the current context the strong axiom presented supersedes Replacement, due to not requiring the binary relation definition to be functional, but possibly multi-valued.

In words, for every total relation, there exists an image set ${\displaystyle b}$ such that the relation is total in both directions. Expressing this via a raw first-order formulation leads to a somewhat repetitive format. The antecedent states that one considers relation ${\displaystyle \phi }$ between sets ${\displaystyle x}$ and ${\displaystyle y}$ that are total over a certain domain set ${\displaystyle a}$, that is, ${\displaystyle \phi }$ has at least one "image value" ${\displaystyle y}$ for every element ${\displaystyle x}$ in the domain. This is more general than an inhabitance condition ${\displaystyle x\in y}$ in a set theoretical choice axiom, but also more general than the condition of Replacement, which demands unique existence ${\displaystyle \exists !y}$. In the consequent, firstly, the axioms states that then there exists a set ${\displaystyle b}$ which contains at least one "image" value ${\displaystyle y}$ under ${\displaystyle \phi }$, for every element of the domain. Secondly, in this axioms formulation it then moreover states that only such images ${\displaystyle y}$ are elements of that new codomain set ${\displaystyle b}$. It is guaranteeing that ${\displaystyle b}$ does not overshoot the codomain of ${\displaystyle \phi }$ and thus the axiom is also expressing some power akin to a Separation procedure. The principle may be used in the constructive study of larger sets beyond the everyday need of analysis.

Metalogic

This theory without ${\displaystyle {\mathrm {PEM} }}$, without unbounded separation and without "naive" Power set enjoys various nice properties. For example, as opposed to ${\displaystyle {\mathsf {CZF}}}$ with its subset collection schema below, it has the existence property.

Constructive Zermelo–Fraenkel

Binary refinement

The so called binary refinement axiom says that for any ${\displaystyle a}$ there exists a set ${\displaystyle {\mathcal {B}}_{a}\subset {\mathcal {P}}_{a}}$ such that for any covering ${\displaystyle a=x\cup y}$, the set ${\displaystyle {\mathcal {B}}_{a}}$ holds two subsets ${\displaystyle c\subset x}$ and ${\displaystyle d\subset y}$ that also do this covering job, ${\displaystyle a=c\cup d}$. It is a weakest form of the powerset axiom and at the core of some important mathematical proofs. Fullness below, for relations between the set ${\displaystyle a}$ and the finite ${\displaystyle \{0,1\}}$, implies that this is indeed possible.

Taking another step back, ${\displaystyle {\mathsf {ECST}}}$ plus Recursion and plus Binary refinement already proves that there exists an Archimedean, Dedekind complete pseudo-ordered field. That set theory also proves that the class of left Dedekind cuts is a set, not requiring Induction or Collection. And it moreover proves that function spaces into discrete sets are sets (there e.g. ${\displaystyle \omega \to \omega }$), without assuming ${\displaystyle {\mathrm {Exp} }}$. Already over the weak theory ${\displaystyle {\mathsf {BCST}}}$ (which is to say without Infinity) does binary refinement prove that function spaces into discrete sets are sets, and therefore e.g. the existence of all characteristic function spaces ${\displaystyle \{0,1\}^{a}}$.

Subset Collection

The theory known as ${\displaystyle {\mathsf {CZF}}}$ adopts the axioms of the previous sections plus a stronger form of Exponentiation. It is by adopting the following alternative to Exponentiation, which can again be seen as a constructive version of the Power set axiom:

An alternative that is not a schema is elaborated on below.

Fullness

For given ${\displaystyle a}$ and ${\displaystyle b}$, let ${\displaystyle {\mathcal {R}}_{ab}}$ be the class of all total relations between ${\displaystyle a}$ and ${\displaystyle b}$. This class is given as

${\displaystyle r\in {\mathcal {R}}_{ab}\leftrightarrow {\Big (}{\big (}\forall (x\in a).\exists (y\in b).\langle x,y\rangle \in r{\big )}\,\land \,{\big (}\forall (p\in r).\exists (x\in a).\exists (y\in b).p=\langle x,y\rangle {\big )}{\Big )}}$

As opposed to the function definition, there is no unique existence quantifier in ${\displaystyle \exists !(y\in b)}$. The class ${\displaystyle {\mathcal {R}}_{ab}}$ represents the space of "non-unique-valued functions" or "multivalued functions" from ${\displaystyle a}$ to ${\displaystyle b}$, but as set of individual pairs with right projection in ${\displaystyle b}$. The second clause says that one is concerned with only these relations, not those which are total on ${\displaystyle a}$ but also extend their domain beyond ${\displaystyle a}$.

One does not postulate ${\displaystyle {\mathcal {R}}_{ab}}$ to be a set, since with Replacement one can use this collection of relations between a set ${\displaystyle a}$ and the finite ${\displaystyle b=\{0,1\}}$, i.e. the "bi-valued functions on ${\displaystyle a}$", to extract the set ${\displaystyle {\mathcal {P}}_{a}}$ of all its subsets. In other words ${\displaystyle {\mathcal {R}}_{ab}}$ being a set would imply the Powerset axiom.

Over ${\displaystyle {\mathsf {ECTS}}+{\text{Strong Collection}}}$, there is a single, somewhat clearer alternative axiom to the Subset Collection schema. It postulates the existence of a sufficiently large set ${\displaystyle {\mathcal {S}}_{ab}}$ of total relations between ${\displaystyle a}$ and ${\displaystyle b}$.

This says that for any two sets ${\displaystyle a}$ and ${\displaystyle b}$, there exists a set ${\displaystyle {\mathcal {S}}_{ab}\subset {\mathcal {R}}_{ab}}$ which among its members inhabits a still total relation ${\displaystyle s\in {\mathcal {S}}_{ab}}$ for any given total relation ${\displaystyle r\in {\mathcal {R}}_{ab}}$.

On a given domain ${\displaystyle a}$, the functions are exactly the sparsest total relations, namely the unique valued ones. Therefore, the axiom implies that there is a set such that all functions are in it. In this way, Fullness implies Exponentiation. It further implies binary refinement, already over ${\displaystyle {\mathsf {BCST}}}$.

The Fullness axiom, as well as dependent choice, is in turn also implied by the so-called Presentation Axiom about sections, which can also be formulated category theoretically.

Metalogic of CZF

${\displaystyle {\mathsf {CZF}}}$ has the numerical existence property and the disjunctive property, but there are concessions: ${\displaystyle {\mathsf {CZF}}}$ lacks the existence property due to the Subset Collection Schema or Fullness axiom. The schema can also be an obstacle for realizability models. The existence property is not lacking when the weaker Exponentiation or the stronger but impredicative Powerset axiom axiom is adopted instead. The latter is in general lacking a constructive interpretation.

Unprovable claims

The theory is consistent with some anti-classical assertions, but on its own proves nothing not provable in ${\displaystyle {\mathsf {ZF}}}$. Some prominent statements not proven by the theory (nor by ${\displaystyle {\mathsf {IZF}}}$, for that matter) are part of the principles listed above, in the sections on constructive schools in analysis, on the Cauchy construction and on non-constructive principles. What follows concerns set theoretical concepts:

The bounded notion of a transitive set of transitive sets is a good way to define ordinals and enables induction on ordinals. But notably, this definition includes some ${\displaystyle \Delta _{0}}$-subsets in ${\displaystyle {\mathsf {CZF}}}$. So assuming that the membership of ${\displaystyle 0}$ is decidable in all successor ordinals ${\displaystyle S\alpha }$ proves ${\displaystyle {\mathrm {PEM} }}$ for bounded formulas in ${\displaystyle {\mathsf {CZF}}}$. Also, neither linearity of ordinals, nor existence of power sets of finite sets are derivable in this theory, as assuming either implies Power set. The circumstance that ordinals are better behaved in the classical than in the constructive context manifests in a different theory of large set existence postulates.

Consider the functions the domain of which is ${\displaystyle \omega }$ or some ${\displaystyle n\in \omega }$. These are sequences and their ranges are counted sets. Denote by ${\displaystyle C}$ the class characterized as the smallest codomain such that the ranges of the aforementioned functions into ${\displaystyle C}$ are also itself members of ${\displaystyle C}$. In ${\displaystyle {\mathsf {ZF}}}$, this is the set ${\displaystyle H_{\aleph _{1}}}$ of hereditarily countable sets and has ordinal rank at most ${\displaystyle \omega _{2}}$. In ${\displaystyle {\mathsf {ZF}}}$, it is uncountable (as it also contains all countable ordinals, the cardinality of which is denoted ${\displaystyle \aleph _{1}}$) but its cardinality is not necessarily that of ${\displaystyle {\mathbb {R} }}$. Meanwhile, ${\displaystyle {\mathsf {CZF}}}$ does not prove ${\displaystyle C}$ even constitutes a set, even when countable choice is assumed.

Finally, the theory does not prove that all function spaces formed from sets in the constructible universe ${\displaystyle L}$ are sets inside ${\displaystyle L}$, and this holds even when assuming Powerset instead of the weaker Exponentiation axiom. So this is a particular statement preventing ${\displaystyle {\mathsf {CZF}}}$ from proving the class ${\displaystyle L}$ to be a model of ${\displaystyle {\mathsf {CZF}}}$.

Ordinal analysis

Taking ${\displaystyle {\mathsf {CZF}}}$ and dropping set induction gives a theory that is conservative over ${\displaystyle {\mathsf {HA}}}$ for arithmetic statements, in that sense that it proves the same arithmetical statements for its ${\displaystyle {\mathsf {HA}}}$-model ${\displaystyle \omega }$. Adding back just mathematical induction gives a theory with proof theoretic ordinal ${\displaystyle \varphi (\varepsilon _{0},0)}$, which is the first common fixed point of the Veblen functions ${\displaystyle \varphi _{\beta }}$ for ${\displaystyle \beta <\varepsilon _{0}}$. This is the same ordinal as for ${\displaystyle {\mathsf {ML_{1}}}}$ and is below the Feferman–Schütte ordinal ${\displaystyle \Gamma _{0}}$. Exhibiting a type theoretical model, the full theory ${\displaystyle {\mathsf {CZF}}}$ goes beyond ${\displaystyle \Gamma _{0}}$, its ordinal still being the modest Bachmann–Howard ordinal. Assuming the class of trichotomous ordinals is a set raises the proof theoretical strength of ${\displaystyle {\mathsf {CZF}}}$ (but not of ${\displaystyle {\mathsf {IZF}}}$).

Being related to inductive definitions or bar induction, the regular extension axiom ${\displaystyle {\mathrm {REA} }}$ raises the proof theoretical strength of ${\displaystyle {\mathsf {CZF}}}$. This large set axiom, granting the existence of certain nice supersets for every set, is proven by ${\displaystyle {\mathsf {ZFC}}}$.

Models

The category of sets and functions of ${\displaystyle {\mathsf {CZF}}+{\mathrm {REA} }}$ is a ${\displaystyle \Pi W}$-pretopos. Without diverging into topos theory, certain extended such ${\displaystyle \Pi W}$-pretopoi contain models of ${\displaystyle {\mathsf {CZF}}+{\mathrm {REA} }}$. The effective topos contains a model of this ${\displaystyle {\mathsf {CZF}}+{\mathrm {REA} }}$ based on maps characterized by certain good subcountability properties.

Separation, stated redundantly in a classical context, is constructively not implied by Replacement. The discussion so far only committed to the predicatively justified bounded Separation. Note that full Separation (together with ${\displaystyle {\mathrm {RDC} }}$, ${\displaystyle {\mathrm {MP} }}$ and also ${\displaystyle {\mathrm {IP} }}$ for sets) is validated in some effective topos models, meaning the axiom does not spoil cornerstones of the restrictive recursive school.

Related are type theoretical interpretations. In 1977 Aczel showed that ${\displaystyle {\mathsf {CZF}}}$ can still be interpreted in Martin-Löf type theory,^[25] using the propositions-as-types approach. More specifically, this uses one universe and ${\displaystyle W}$-types, providing what is now seen a standard model of ${\displaystyle {\mathsf {CZF}}}$ in ${\displaystyle {\mathsf {ML_{1}V}}}$.^[26]This is done in terms of the images of its functions and has a fairly direct constructive and predicative justification, while retaining the language of set theory. Roughly, there are two "big" types ${\displaystyle U,V}$, the sets are all given through any ${\displaystyle f\colon A\to V}$ on some ${\displaystyle A\colon U}$, and membership of a ${\displaystyle x}$ in the set is defined to hold when ${\displaystyle \exists (a\colon A).f(a)=x}$. Conversely, ${\displaystyle {\mathsf {CZF}}}$ interprets ${\displaystyle {\mathsf {ML_{1}V}}}$. All statements validated in the subcountable model of the set theory can be proven exactly via ${\displaystyle {\mathsf {CZF}}}$ plus the choice principle ${\displaystyle \Pi \Sigma }$- ${\displaystyle \mathrm {AC} }$, stated further above. As noted, theories like ${\displaystyle {\mathsf {CZF}}}$, and also together with choice, have the existence property for a broad class of sets in common mathematics. Martin-Löf type theories with additional induction principles validate corresponding set theoretical axioms.

Soundness and Completeness theorems of ${\displaystyle {\mathsf {CZF}}}$, with respect to realizability, have been established.

Breaking with ZF

One may of course add a Church's thesis.

One may postulate the subcountability of all sets. This already holds true in the type theoretical interpretation and the model in the effective topos. By Infinity and Exponentiation, ${\displaystyle \omega \to \omega }$ is an uncountable set, while the class ${\displaystyle {\mathcal {P}}_{\omega }}$ or even ${\displaystyle {\mathcal {P}}_{1}}$ is then provenly not a set, by Cantor's diagonal argument. So this theory then logically rejects Powerset and of course ${\displaystyle {\mathrm {PEM} }}$. Subcountability is also in contradiction with various large set axioms. (On the other hand, also using ${\displaystyle {\mathsf {CZF}}}$, some such axioms imply the consistency of theories such as ${\displaystyle {\mathsf {ZF}}}$ and stronger.)

As a rule of inference, ${\displaystyle {\mathsf {CZF}}}$ is closed under Troelstra's general uniformity for both ${\displaystyle z=\omega }$ and ${\displaystyle z=\{0,1\}}$. One may adopt it as an anti-classical axiom schema, the uniformity principle which may be denoted ${\displaystyle {\mathrm {UP} }}$,

${\displaystyle \forall z.{\big (}\forall x.\exists (y\in z).\phi (x,y){\big )}\to \exists (y\in z).\forall x.\phi (x,y)}$

This also is incompatible with the powerset axiom. The principle is also often formulated for ${\displaystyle z=\omega }$. Now for a binary set of labels ${\displaystyle z=\{0,1\}}$, ${\displaystyle {\mathrm {UP} }}$ implies the indecomposability schema ${\displaystyle {\mathrm {UZ} }}$, as noted.

In 1989 Ingrid Lindström showed that non-well-founded sets can also be interpreted in Martin-Löf type theory, which are obtained by replacing Set Induction in ${\displaystyle {\mathsf {CZF}}}$ with Aczel's anti-foundation axiom.^[27] The resulting theory ${\displaystyle {\mathsf {CZFA}}}$ may be studied by also adding back the ${\displaystyle \omega }$-induction schema or relativized dependent choice, as well as the assertion that every set is member of a transitive set.

Intuitionistic Zermelo–Fraenkel

The theory ${\displaystyle {\mathsf {IZF}}}$ is ${\displaystyle {\mathsf {CZF}}}$ adopting both the standard Separation as well as Power set and, as in ${\displaystyle {\mathsf {ZF}}}$, one conventionally formulates the theory with Collection below. As such, ${\displaystyle {\mathsf {IZF}}}$ can be seen as the most straight forward variant of ${\displaystyle {\mathsf {ZF}}}$ without PEM. So as noted, in ${\displaystyle {\mathsf {IZF}}}$, in place of Replacement, one may use the

While the axiom of replacement requires the relation ϕ to be functional over the set z (as in, for every x in z there is associated exactly one y), the Axiom of Collection does not. It merely requires there be associated at least one y, and it asserts the existence of a set which collects at least one such y for each such x. In classical ${\displaystyle {\mathsf {ZFC}}}$, the Collection schema implies the Axiom schema of replacement. When making use of Powerset (and only then), they can be shown to be classically equivalent.

While ${\displaystyle {\mathsf {IZF}}}$ is based on intuitionistic rather than classical logic, it is considered impredicative. It allows formation of sets via a power set operation and using the general Axiom of Separation with any proposition, including ones which contain quantifiers which are not bounded. Thus new sets can be formed in terms of the universe of all sets, distancing the theory from the bottom-up constructive perspective. So it is even easier to define sets ${\displaystyle \{x\in B\mid Q(x)\}}$ with undecidable membership, namely by making use of undecidable predicates defined on a set. The power set axiom further implies the existence of a set of truth values. In the presence of excluded middle, this set has two elements. In the absence of it, the set of truth values is also considered impredicative. The axioms of ${\displaystyle {\mathsf {IZF}}}$ are strong enough so that full PEM is already implied by PEM for bounded formulas. See also the previous discussion in the section on the Exponentiation axiom. And by the discussion about Separation, it is thus already implied by the particular formula ${\displaystyle \forall x.{\big (}0\in x\lor 0\notin x{\big )}}$, the principle that knowledge of membership of ${\displaystyle 0}$ shall always be decidable, no matter the set.

Metalogic

As implied above, the subcountability property cannot be adopted for all sets, given the theory proves ${\displaystyle {\mathcal {P}}_{\omega }}$ to be a set. The theory has many of the nice numerical existence properties and is e.g. consistent with Church's thesis principle as well as with ${\displaystyle \omega \to \omega }$ being subcountable. It also has the disjunctive property.

${\displaystyle {\mathsf {IZF}}}$ with Replacement instead of Collection has the general existence property, even when adopting relativized dependent choice on top of it all. But just ${\displaystyle {\mathsf {IZF}}}$ as formulated does not. The combination of schemas including full separation spoils it.

Even without PEM, the proof theoretic strength of ${\displaystyle {\mathsf {IZF}}}$ equals that of ${\displaystyle {\mathsf {ZF}}}$. And ${\displaystyle {\mathsf {HA}}}$ proves them equiconsistent and they prove the same ${\displaystyle \Pi _{1}^{0}}$-sentences.

Intuitionistic Z

Again on the weaker end, as with its historical counterpart Zermelo set theory, one may denote by ${\displaystyle {\mathsf {IZ}}}$ the intuitionistic theory set up like ${\displaystyle {\mathsf {IZF}}}$ but without Replacement, Collection or Induction.

Intuitionistic KP

Let us mention another very weak theory that has been investigated, namely Intuitionistic (or constructive) Kripke–Platek set theory ${\displaystyle {\mathsf {IKP}}}$. It has not only Separation but also Collection restricted to ${\displaystyle \Delta _{0}}$-formulas, i.e. it is similar to ${\displaystyle {\mathsf {BCST}}}$ but with Induction instead of full Replacement. The theory does not fit into the hierarchy as presented above, simply because it has Axiom schema of Set Induction from the start. This enables theorems involving the class of ordinals. The theory has the disjunction property. Of course, weaker versions of ${\displaystyle {\mathsf {IKP}}}$ are obtained by restricting the induction schema to narrower classes of formulas, say ${\displaystyle \Sigma _{1}}$. The theory is especially weak when studied without Infinity.

Sorted theories

Constructive set theory

As he presented it, Myhill's system ${\displaystyle {\mathsf {CST}}}$ is a theory using constructive first-order logic with identity and two more sorts beyond sets, namely natural numbers and functions. Its axioms are:

• The usual Axiom of Extensionality for sets, as well as one for functions, and the usual Axiom of union.
• The Axiom of restricted, or predicative, separation, which is a weakened form of the Separation axiom from classical set theory, requiring that any quantifications be bounded to another set, as discussed.
• A form of the Axiom of Infinity asserting that the collection of natural numbers (for which he introduces a constant ${\displaystyle \omega }$) is in fact a set.
• The axiom of Exponentiation, asserting that for any two sets, there is a third set which contains all (and only) the functions whose domain is the first set, and whose range is the second set. This is a greatly weakened form of the Axiom of power set in classical set theory, to which Myhill, among others, objected on the grounds of its impredicativity.

And furthermore:

• The usual Peano axioms for natural numbers.
• Axioms asserting that the domain and range of a function are both sets. Additionally, an Axiom of non-choice asserts the existence of a choice function in cases where the choice is already made. Together these act like the usual Replacement axiom in classical set theory.

One can roughly identify the strength of this theory with a constructive subtheories of ${\displaystyle {\mathsf {ZF}}}$ when comparing with the previous sections.

And finally the theory adopts

• An Axiom of dependent choice, which is much weaker than the usual Axiom of choice.

Bishop style set theory

Set theory in the flavor of Errett Bishop's constructivist school mirrors that of Myhill, but is set up in a way that sets come equipped with relations that govern their discreteness. Commonly, Dependent Choice is adopted.

A lot of analysis and module theory has been developed in this context.

Category theories

Not all formal logic theories of sets need to axiomize the binary membership predicate " ${\displaystyle \in }$" directly. A theory like the Elementary Theory of the Categories Of Set ( ${\displaystyle {\mathsf {ETCS}}}$), e.g. capturing pairs of composable mappings between objects, can also be expressed with a constructive background logic. Category theory can be set up as a theory of arrows and objects, although first-order axiomatizations only in terms of arrows are possible.

Beyond that, topoi also have internal languages that can be intuitionistic themselves and capture a notion of sets.

Good models of constructive set theories in category theory are the pretoposes mentioned in the Exponentiation section. For some good set theory, this may require enough projectives, an axiom about surjective "presentations" of set, implying Countable and Dependent Choice.

See also

• Axiom schema of predicative separation
• Constructive mathematics
• Constructive analysis
• Constructive Church's thesis rule and principle
• Computable set
• Diaconescu's theorem
• Disjunction and existence properties
• Epsilon-induction
• Hereditarily finite set
• Heyting arithmetic
• Impredicativity
• Intuitionistic type theory
• Law of excluded middle
• Ordinal analysis
• Set theory
• Subcountability

References

1. Feferman, Solomon (1998), In the Light of Logic, New York: Oxford University Press, pp. 280–283, 293–294, ISBN 0-195-08030-0
2. Troelstra, A. S., van Dalen D., Constructivism in mathematics: an introduction 1; Studies in Logic and the Foundations of Mathematics; Springer, 1988;
3. Bridges D., Ishihara H., Rathjen M., Schwichtenberg H. (Editors), Handbook of Constructive Mathematics; Studies in Logic and the Foundations of Mathematics; (2023) pp. 20-56
4. Myhill, "Some properties of Intuitionistic Zermelo-Fraenkel set theory", Proceedings of the 1971 Cambridge Summer School in Mathematical Logic (Lecture Notes in Mathematics 337) (1973) pp. 206-231
5. Crosilla, Laura; Set Theory: Constructive and Intuitionistic ZF; Stanford Encyclopedia of Philosophy; 2009
6. Peter Aczel and Michael Rathjen, Notes on Constructive Set Theory, Reports Institut Mittag-Leffler, Mathematical Logic - 2000/2001, No. 40
7. John L. Bell, Intuitionistic Set Theorys, 2018
8. Jeon, Hanul (2022), "Constructive Ackermann's interpretation", Annals of Pure and Applied Logic, 173 (5): 103086, arXiv:2010.04270, doi:10.1016/j.apal.2021.103086, S2CID 222271938
9. Gambino, N. (2005). "Presheaf models for constructive set theories" (PDF). In Laura Crosilla and Peter Schuster (ed.). From Sets and Types to Topology and Analysis (PDF). pp. 62–96. doi:10.1093/acprof:oso/9780198566519.003.0004. ISBN 9780198566519.
10. Scott, D. S. (1985). Category-theoretic models for Intuitionistic Set Theory. Manuscript slides of a talk given at Carnegie-Mellon University
11. Benno van den Berg, Predicative topos theory and models for constructive set theory , Netherlands University, PhD thesis, 2006
12. Jech, Thomas (2003), Set Theory, Springer Monographs in Mathematics (Third Millennium ed.), Berlin, New York: Springer-Verlag, p. 642, ISBN 978-3-540-44085-7, Zbl 1007.03002
13. Gert Smolka, Set Theory in Type Theory, Lecture Notes, Saarland University, Jan. 2015
14. Gert Smolka and Kathrin Stark, Hereditarily Finite Sets in Constructive Type Theory, Proc. of ITP 2016, Nancy, France, Springer LNCS, May 2015
15. Diener, Hannes (2020). "Constructive Reverse Mathematics". arXiv:1804.05495 [math.LO].
16. Sørenson, Morten; Urzyczyn, Paweł (1998), Lectures on the Curry-Howard Isomorphism, CiteSeerX 10.1.1.17.7385, p. 239
17. Smith, Peter (2007). An introduction to Gödel's Theorems (PDF). Cambridge, U.K.: Cambridge University Press. ISBN 978-0-521-67453-9. MR 2384958., p. 297
18. Pradic, Pierre; Brown, Chad E. (2019). "Cantor-Bernstein implies Excluded Middle". arXiv:1904.09193 [math.LO].
19. Michael Rathjen, Choice principles in constructive and classical set theories, Cambridge University Press: 31 March 2017
20. Gitman, Victoria (2011), What is the theory ZFC without power set, arXiv:1110.2430
21. Shulman, Michael (2019), "Comparing material and structural set theories", Annals of Pure and Applied Logic, 170 (4): 465-504, arXiv:1808.05204, doi:10.1016/j.apal.2018.11.002
22. Errett Bishop, Foundations of Constructive Analysis, July 1967
23. Robert S. Lubarsky, On the Cauchy Completeness of the Constructive Cauchy Reals, July 2015
24. Matthew Ralph John Hendtlass, Constructing fixed points and economic equilibria, PhD Thesis, University of Leeds, April 2013
25. Aczel, Peter: 1978. The type theoretic interpretation of constructive set theory. In: A. MacIntyre et al. (eds.), Logic Colloquium '77, Amsterdam: North-Holland, 55–66.
26. Rathjen, M. (2004), "Predicativity, Circularity, and Anti-Foundation" (PDF), in Link, Godehard (ed.), One Hundred Years of Russell ́s Paradox: Mathematics, Logic, Philosophy, Walter de Gruyter, ISBN 978-3-11-019968-0
27. Lindström, Ingrid: 1989. A construction of non-well-founded sets within Martin-Löf type theory. Journal of Symbolic Logic 54: 57–64.

Further reading

• Troelstra, Anne; van Dalen, Dirk (1988). Constructivism in Mathematics, Vol. 2. Studies in Logic and the Foundations of Mathematics. p. 619. ISBN 978-0-444-70358-3.
• Aczel, P. and Rathjen, M. (2001). Notes on constructive set theory. Technical Report 40, 2000/2001. Mittag-Leffler Institute, Sweden.

External links

• Crosilla, Laura (13 February 2019). "Set Theory: Constructive and Intuitionistic ZF". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.
• Van den Berg, Benno (7 September 2012). "Constructive set theory – an overview" (PDF). Slides from Heyting dag, Amsterdam