Teoría de conjuntos constructiva

Teorías de conjuntos axiomáticos basadas en los principios del constructivismo matemático.

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 tercero excluido ( ), las teorías constructivas de conjuntos a menudo requieren que algunos cuantificadores lógicos en sus axiomas sean acotados , motivados por resultados ligados a la impredicatividad . ${\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 analizadas aquí es constructiva porque rechaza el principio del tercero excluido , es decir, que la disyunción se cumple automáticamente para todas las proposiciones . 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 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, 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 simple 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 . ^[1]

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 {OD} })}$ ${\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 principio de tesis de Church correspondiente 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 de la 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 ambas 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 . ^{[2] [3]} 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 tercero excluido, dejando inicialmente todo lo demás tal cual. 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 ^[4] 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; consulte también la jerarquía de Lévy . 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. ^[5] El sistema, que ha llegado a conocerse 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 de conjuntos clásica 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 pero más la existencia de todos los cierres transitivos . (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. ^[6] 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 Axiom 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. ^{[7] [8]} 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. ^[9] ${\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. Por una consideración práctica, la propiedad de ser una secuencia de resultados de lanzamientos de monedas que en general muestran más cara que cruz puede usarse para separar un subconjunto correspondiente de cualquier conjunto de secuencias finitas de lanzamientos de monedas. 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. La negación " " de la igualdad suele escribirse " ". Sin embargo, en un contexto con relaciones de separación , por ejemplo cuando se trata de secuencias, este último símbolo 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 axiomáticos, como se ve a continuación. ${\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)}$

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 la desarticulación capturan muchas de las reglas de negación intuicionistamente válidas: . Usando la notación anterior, esta es una equivalencia puramente lógica y la siguiente 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=\{\}}$

Exprese la afirmación de la subclase , es decir , por . La noción similar 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í. Para un predicado , trivialmente . Y así se sigue . ${\displaystyle \forall (z\in A).z\in B}$ ${\displaystyle \forall z.(z\in A\to z\in B)}$ ${\displaystyle A\subset B}$ ${\displaystyle \forall (z\subset A).z\in 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}$

Equivalencia extensional

Denota por la afirmación que expresa que dos clases tienen exactamente los mismos elementos, es decir , o de forma 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 resalta 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 puede que no sea 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 Q}$ ${\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 tratar la subclase de en el lado derecho de la igualdad para ser utilizada dondequiera que se utilice. ${\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 w=\{x\in w\mid Q(x)\}}$ ${\displaystyle \forall }$ ${\displaystyle w}$ ${\displaystyle w}$

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. Incluso entonces, la definición anterior se puede utilizar para caracterizar la igualdad de subconjuntos y . 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 z\in x}$ ${\displaystyle x}$ ${\displaystyle u\subset x}$ ${\displaystyle v\subset x}$ ${\displaystyle =}$

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,

decir 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 realiza 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, 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 \{\}}$

Para un conjunto , defina el conjunto sucesor como y escriba para . Su interacción 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. 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 . ^{[10] [11]} Todo esto es relevante para el modelado estándar de ordinales de Neumann individuales . ${\displaystyle x}$ ${\displaystyle Sx}$ ${\displaystyle x\cup \{x\}}$ ${\displaystyle 1}$ ${\displaystyle S0}$ ${\displaystyle (y\in Sx)\leftrightarrow (y\in x\lor y=x)}$ ${\displaystyle x\in Sx}$ ${\displaystyle Sx}$

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 . ${\displaystyle \{\}\in \{\}}$ ${\displaystyle 0<0}$ ${\displaystyle \{\}}$ ${\displaystyle \in }$ ${\displaystyle 0}$

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 axioma de separación 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 la 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 acotada 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}}}$

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 también, equivalentemente, también . En el modelo de los naturales, si es un número, 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 de expresar el término medio excluido es como la existencia de un menor número de miembros de la clase habitada . 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 . ${\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 0\in B}$ ${\displaystyle 0}$ ${\displaystyle B}$ ${\displaystyle P\lor \neg P}$ ${\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\}}$ ${\displaystyle P}$ ${\displaystyle B}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle \forall b.(0\in b)\lor (0\notin b)}$

El esquema de axioma de la separación predicativa también se denomina separación acotada, como en la separación sólo para cuantificadores acotados por conjuntos . El alcance de subconjuntos específicos cuya existencia se puede demostrar se enriquece con un postulado de existencia de conjuntos adicional. La separación acotada es un esquema que tiene en cuenta aspectos sintácticos de predicados que definen conjuntos, hasta una equivalencia demostrable. Las fórmulas permitidas se denotan por en la jerarquía teórica establecida de Lévy, de forma análoga a en la jerarquía aritmética . (Tenga en cuenta, sin embargo, que la clasificación aritmética a veces no se expresa 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 de las cuales no permiten el uso de algunas funciones totales. La distinción 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 . Véase también teoría de conjuntos de Kripke-Platek . ${\displaystyle {\mathsf {Z}}}$

Sin conjunto universal

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 la clase de la derecha no es un conjunto. Lo siguiente demuestra esto en el caso especial cuando está vacío, es decir, cuando el lado derecho es la clase universal. ${\displaystyle A\cup \{x\mid x\notin A\}}$ ${\displaystyle 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 es limitada y, por lo tanto, se permite 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 con el axioma de regularidad , como , por supuesto, se puede demostrar que ese subconjunto es igual a sí mismo. Además, en una teoría con estratificación como los Nuevos Fundamentos Intuicionistas , puede existir un conjunto universal porque el uso de la expresión sintáctica puede no estar permitido en pruebas de existencia mediante, esencialmente, separación. ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle \{x\in y\mid x\notin x\}}$ ${\displaystyle y}$ ${\displaystyle x\in x}$

El caso especial ya implica que la subclase de la clase universal también es propia. ${\displaystyle s=y}$ ${\displaystyle \{x\mid x\notin x\}}$

Predicatividad

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 descriptibles explícitamente, 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, debe enfatizarse que muchas definiciones de clases que son clásicamente equivalentes no lo son cuando se restringe uno mismo a la lógica constructiva. De esta manera se obtiene una teoría más amplia y constructiva. Debido a la potencial indecidibilidad de los predicados generales, la noción de subconjunto y subclase es más elaborada en las teorías constructivas de conjuntos que en las clásicas. Esto sigue siendo cierto si se adopta la separación total, 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.

Con el esquema de Reemplazo, esta teoría 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. La igualdad de elementos dentro de un conjunto es decidible si la relación correspondiente como subconjunto de es decidible, en cuyo caso a veces se la llama discreta. ${\displaystyle x\times x\times x\times x}$ ${\displaystyle x}$ ${\displaystyle x\times x}$ ${\displaystyle x}$

El reemplazo no es necesario en el diseño de una teoría de conjuntos constructiva débil que sea biinterpretable con la aritmética de Heyting . Sin embargo, alguna forma de inducción sí lo es. El reemplazo junto con la inducción de conjuntos (que se presenta a continuación) también es suficiente para axiomar constructivamente conjuntos hereditariamente finitos y esa teoría también se estudia sin infinito. 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}}}$

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}}}$

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 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 otorga 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 clausura de son fáciles de lograr. En cuarto lugar, se puede demostrar que en , donde es un conjunto, es una operación inyectiva. ${\displaystyle {\mathsf {BCST}}}$ ${\displaystyle \omega }$ ${\displaystyle S}$ ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle \omega }$ ${\displaystyle S}$

Para algún predicado de conjuntos , el enunciado lo afirma 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))}$

El orden por pares " " de los naturales se captura por su relación de pertenencia " ". Es importante señalar que 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 decidibles 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. ^[12] 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 relativos a 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 constructivo 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 limitado que 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. ^[13] 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. ^[14] ${\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 ejecute 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. Esta 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 "operaciones" en la literatura, que puede 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. ${\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 anterior sólo implica 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}$

Que una subclase (o un predicado) pueda 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 un gráfico 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 finitamente indexada (o Kuratowski -finita) significará que hay una sobreyección de un número natural de von Neumann sobre ella. Llame a un conjunto subfinito si es el subconjunto de un conjunto finito, que así se inyecta en ese conjunto finito. En tercer lugar, para una noción incluso más débil que la de indexado finitamente, estar indexado 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 tres 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, y en el tercero ni siquiera se entiende la pertenencia con respecto a algún superconjunto. necesario entenderlo completamente. 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étera. 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 existe alguna cadena de subconjuntos tal que cada uno tiene algunos elementos nuevos en comparación con su predecesor. 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 {\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 0\neq 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 comprobar la totalidad de los términos , 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. ^[15] 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 se le da una función , es la función característica la que realmente decide la pertenencia a algún conjunto, de modo que ${\displaystyle \chi _{B}\colon A\to \{0,1\}}$ ${\displaystyle B\subset A}$

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

y luego por convención y así como cualquier equivalente de las fórmulas y con free se puede denominar propiedad decidible o conjunto en . Se puede llamar a una colección buscable si la existencia es realmente decidible, ${\displaystyle B}$ ${\displaystyle \chi _{B}}$ ${\displaystyle n\in B}$ ${\displaystyle \chi _{B}(n)=1}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\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 B\neq \{\}}$ ${\displaystyle B}$ ${\displaystyle B=\{\}}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle \forall }$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathrm {LPO} }}$ ${\displaystyle \exists }$ ${\displaystyle {\mathrm {PEM} }}$

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. Con lo anterior, se deduce que ${\displaystyle R\subset \omega }$ ${\displaystyle w_{m}:=\{k\in \omega \mid k>m\}}$

${\displaystyle \forall (r\colon \omega \to R).\exists (m\in \omega ).\forall (k\in w_{m}).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 contabilización 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. ^[dieciséis] ${\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 opción de 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 de Kőnig débil , 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 de 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 al menos 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 un 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 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 0\neq 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 a\neq b)}$ ${\displaystyle \neg P\to (a=\{0\}\land b=\{1\})}$ ${\displaystyle g(a)\neq g(b)\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 no se adopte la elección total 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 se vuelven ampliamente 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 la elección 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. ${\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 la función de suma sea una función establecida. 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 recursividad 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 mansos: cuando en lugar de asumir la inducción completa o la exponenciación completa, tomar espacios funcionales o productos cartesianos n veces, probablemente preserva la contabilidad. ${\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. Existen conjuntos potenciados de conjuntos finitos. 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 supone 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 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 . Cuando se lee de manera constructiva, uno querría 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 aún 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 cuanto mayor es el tamaño del dominio, 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

Lo clásico sin el axioma de Powerset sigue siendo consistente con el hecho de que todos los conjuntos de reales existentes son subcontables , e incluso contables. ^[17] Tal teoría equivale esencialmente a aritmética de segundo orden . ${\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 la forma del espacio de funciones características, ligado a su vez exactamente a las subclases decidibles. 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 declaraciones de existencia como la exponenciación, es decir, que los espacios funcionales son conjuntos, la cuantificación de los elementos de ciertas clases de funciones ahora solo abarca conjuntos. El axioma enriquece directamente el dominio de los conjuntos, pero con él también permite derivar aún más, a través de la separación acotada, lo que a su vez también fortalece otros axiomas. 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 pueden entenderse como colecciones de predicados decidibles, y 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). Sin más axiomas, las matemáticas intuicionistas tienen modelos en funciones recursivas pero también formas de hipercomputación . Una teoría así no prueba que un espacio funcional no sea enumerable, en el sentido de inyecciones fuera de él. ${\displaystyle \forall f}$ ${\displaystyle f\colon \omega \to 2}$ ${\displaystyle 2=\{0,1\}}$ ${\displaystyle 2^{\mathbb {N} }}$ ${\displaystyle 2^{\mathbb {N} }}$ ${\displaystyle y^{\mathbb {N} }}$ ${\displaystyle \omega \to y}$ ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$

En términos generales, los conjuntos clásicamente incontables tienden a no tener una igualdad computable y decidible.

En conjuntos contables

Con la exponenciación, la unión de todas las secuencias finitas en un conjunto contable ahora es un conjunto contable. 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 {\mathsf {ZF}}}$ ${\displaystyle {\mathbb {R} }}$

Por último, cualquier unión finitamente indexada de una familia de resp. subfinitamente indexadas. Los conjuntos subcontables están en sí mismos indexados de manera subfinita. subcontable también. Por supuesto, muchos otros teoremas sobre los diversos predicados de existencia de funciones se mantienen, especialmente cuando se supone una elección contable.

La teoría de conjuntos demuestra ahora 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. Luego se obtiene además el número ordinal exponenciado como un conjunto, que puede caracterizarse como el conjunto contado de palabras en un alfabeto infinito . ${\displaystyle x\times \omega \to y}$ ${\displaystyle \omega }$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle \cup _{n\in \omega }\omega ^{n}}$

Hasta donde llega la comprensión, los productos dependientes o indexados ahora son conjuntos. La teoría ahora demuestra que la colección de todos los subconjuntos contables de cualquier conjunto (la colección es una subclase de la clase de potencia) es un conjunto. ${\displaystyle \Pi _{i\in x}\,y_{i}}$

La clase de subconjuntos de un conjunto.

La caracterización de la clase de todos los subconjuntos de un conjunto implica una cuantificación universal ilimitada, a saber . Aquí se ha definido en términos del predicado de membresía anterior. Así, en un marco de teoría matemática de conjuntos, la clase de poder no se define en una construcción ascendente a partir de sus constituyentes (como un algoritmo en una lista, que por ejemplo mapea ) sino a través de una comprensión de todos los conjuntos. Si es un conjunto, esa cuantificación definitoria abarca incluso más de , lo que hace que el axioma del conjunto de poderes sea impredicativo . La declaración en sí es . ${\displaystyle {\mathcal {P}}_{x}}$ ${\displaystyle x}$ ${\displaystyle \forall u.\left(u\subset x\leftrightarrow u\in {\mathcal {P}}_{x}\right)}$ ${\displaystyle \subset }$ ${\displaystyle \in }$ ${\displaystyle \langle a,b\rangle \mapsto \langle \langle \rangle ,\langle a\rangle ,\langle b\rangle ,\langle a,b\rangle \rangle }$ ${\displaystyle {\mathcal {P}}_{x}}$ ${\displaystyle {\mathcal {P}}_{x}}$ ${\displaystyle y={\mathcal {P}}_{x}}$ ${\displaystyle \Pi _{1}}$

La riqueza de la clase de poder 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, 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. ${\displaystyle {\mathcal {P}}_{1}}$ ${\displaystyle f\in {{\mathcal {P}}_{1}}^{x}}$ ${\displaystyle \{z\in x\mid 0\in f(z)\}\in {\mathcal {P}}_{x}}$

El conjunto de funciones que toman valores en (es decir ) en un conjunto , se inyecta en el espacio funcional y corresponde solo a los subconjuntos decidibles de . 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 2^{x}}$ ${\displaystyle 2:=\{0,1\}}$ ${\displaystyle SS0}$ ${\displaystyle x}$ ${\displaystyle {{\mathcal {P}}_{1}}^{x}}$ ${\displaystyle x}$ ${\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. Además, con el medio excluido acotado, está en biyección con . Véase también la discusión a continuación. 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, es independiente si todos ellos tienen , ni prueba que , ver la hipótesis del continuo y el teorema de Easton relacionado . ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathcal {P}}_{1}}$ ${\displaystyle {\mathcal {P}}_{x}}$ ${\displaystyle 2^{x}}$ ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle {\mathsf {ZFC}}}$ ${\displaystyle |\omega |<|x|}$ ${\displaystyle x}$ ${\displaystyle 2^{|\omega |}\leq |x|}$ ${\displaystyle 2^{|\omega |}<2^{|x|}}$

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} }}$

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. ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {ZFC}}}$

Por lo tanto, esto conduciría a una teoría más allá de la solidez de la teoría de tipos típica .

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 . 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 .

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 , el análisis factible y el análisis computable . ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$

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.

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. ^[18] 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 (Pseudoorden) 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} }}$

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

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. 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 buscable si se pueden buscar todos sus subconjuntos decidibles . 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 de las más destacadas afirmaciones no constructivas y esencialmente lógicas, 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 gran tamaño finito 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 . 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. ^[19] ${\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 ).x\cap \Sigma \neq \{\}\,\,\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 la 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 la 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} }}$

A continuación se destacan las diferentes lecturas de una teoría formal. Denotemos la hipótesis del continuo y así que . Entonces está habitado por y cualquier conjunto que se establezca como miembro de ya sea igual o . La inducción implica que no se puede negar consistentemente que tenga algún miembro del número mínimo natural. Se puede demostrar que el valor de dicho miembro es independiente de teorías como . No obstante, cualquier teoría de conjuntos clásica como ésta también demuestra que existe tal número. ${\displaystyle \mathrm {CH} }$ ${\displaystyle B:=\{z\in 1\mid \mathrm {CH} \}}$ ${\displaystyle 0\in B\leftrightarrow \mathrm {CH} }$ ${\displaystyle b:=B\cup \{1\}}$ ${\displaystyle 1}$ ${\displaystyle b}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle b}$ ${\displaystyle {\mathsf {ZFC}}}$ ${\displaystyle {\mathsf {ZFC}}}$

Colección fuerte

Habiendo discutido todas las formas debilitadas de los axiomas de la teoría clásica de conjuntos, el reemplazo y la exponenciación pueden fortalecerse aún más sin perder un tipo de interpretación teórica, y de una manera que no vaya más allá . ${\displaystyle {\mathsf {ZF}}}$

En primer lugar, uno puede reflexionar sobre la fuerza del axioma de reemplazo , también en el contexto de la teoría clásica de conjuntos. Para cualquier conjunto y cualquier natural , existe el producto recursivamente dado por , que tiene un rango cada vez más profundo . La inducción para predicados libres demuestra que estos conjuntos existen para todos los infinitos naturales. El reemplazo "por " ahora establece además que esta clase infinita de productos se puede convertir en el conjunto infinito . Este tampoco es un subconjunto de ningún conjunto previamente establecido. ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle y^{n}}$ ${\displaystyle y^{n-1}\times y}$ ${\displaystyle n\mapsto y^{n}}$ ${\displaystyle \{p\mid \exists (n\in \omega ).p=y^{n}\}}$

Yendo más allá de los axiomas que también se ven en el enfoque tipificado de Myhill, consideremos la teoría constructiva discutida con Exponenciación e Inducción, pero ahora fortalecida por el esquema de colección . En él es equivalente a Reemplazo, a menos que se elimine el axioma del conjunto de potencias. En el contexto actual, el axioma fuerte presentado reemplaza al Reemplazo, debido a que no requiere que la definición de relación binaria sea funcional, pero posiblemente tenga múltiples valores. ${\displaystyle {\mathsf {ZF}}}$

En palabras, para cada relación total existe un conjunto de imágenes tal que la relación es total en ambas direcciones. Expresar esto a través de una formulación cruda de primer orden conduce a un formato algo repetitivo. El antecedente establece que se considera relación entre conjuntos y que son totales sobre un determinado conjunto de dominio , es decir, tiene al menos un "valor de imagen" para cada elemento del dominio. Esto es más general que una condición de habitabilidad en un axioma de elección teórico establecido, pero también más general que la condición de Reemplazo, que exige una existencia única . En consecuencia, en primer lugar, el axioma establece que existe un conjunto que contiene al menos un valor de "imagen" bajo , para cada elemento del dominio. En segundo lugar, en esta formulación de axiomas se afirma además que sólo tales imágenes son elementos de ese nuevo conjunto de codominios . Garantiza que no se sobrepasa el codominio de y, por lo tanto, el axioma también expresa algún poder similar a un procedimiento de separación. El principio puede utilizarse en el estudio constructivo de conjuntos más grandes más allá de la necesidad diaria de análisis. ${\displaystyle b}$ ${\displaystyle \phi }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle a}$ ${\displaystyle \phi }$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x\in y}$ ${\displaystyle \exists !y}$ ${\displaystyle b}$ ${\displaystyle y}$ ${\displaystyle \phi }$ ${\displaystyle y}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle \phi }$

metalógico

Esta teoría sin separación ilimitada y sin conjunto de poderes "ingenuo" goza de varias propiedades agradables. Por ejemplo, a diferencia del esquema de colección de subconjuntos que aparece a continuación, tiene la propiedad de existencia . ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {CZF}}}$

Zermelo constructivo – Fraenkel

Refinamiento binario

El llamado axioma de refinamiento binario dice que para cualquier existe un conjunto tal que para cualquier cobertura , el conjunto contiene dos subconjuntos y que también hacen este trabajo de cobertura . Es una forma más débil del axioma del conjunto de potencias y está en el centro de algunas pruebas matemáticas importantes. La plenitud a continuación, para las relaciones entre el conjunto y lo finito , implica que esto es realmente posible. ${\displaystyle a}$ ${\displaystyle {\mathcal {B}}_{a}\subset {\mathcal {P}}_{a}}$ ${\displaystyle a=x\cup y}$ ${\displaystyle {\mathcal {B}}_{a}}$ ${\displaystyle c\subset x}$ ${\displaystyle d\subset y}$ ${\displaystyle a=c\cup d}$ ${\displaystyle a}$ ${\displaystyle \{0,1\}}$

Dando otro paso atrás, más la recursión y el refinamiento binario ya se demuestra que existe un campo pseudoordenado completo de Arquímedes y Dedekind. Esa teoría de conjuntos también demuestra que la clase de cortes izquierdos de Dedekind es un conjunto que no requiere inducción ni colección. Y además demuestra que los espacios funcionales en conjuntos discretos son conjuntos (por ejemplo, allí ), sin asumir . Ya en la teoría débil (es decir, sin infinito), el refinamiento binario demuestra que los espacios funcionales en conjuntos discretos son conjuntos y, por tanto, por ejemplo, la existencia de todos los espacios funcionales característicos . ${\displaystyle {\mathsf {ECST}}}$ ${\displaystyle \omega \to \omega }$ ${\displaystyle {\mathrm {Exp} }}$ ${\displaystyle {\mathsf {BCST}}}$ ${\displaystyle \{0,1\}^{a}}$

Colección de subconjuntos

La teoría conocida como adopta los axiomas de las secciones anteriores más una forma más fuerte de Exponenciación. Es adoptando la siguiente alternativa a la exponenciación, que nuevamente puede verse como una versión constructiva del axioma del conjunto de potencias : ${\displaystyle {\mathsf {CZF}}}$

A continuación se detalla una alternativa que no es un esquema.

Plenitud

Para dado y , sea la clase de todas las relaciones totales entre y . Esta clase se da como ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle {\mathcal {R}}_{ab}}$ ${\displaystyle a}$ ${\displaystyle b}$

${\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 )}}$

A diferencia de la definición de función, no existe un cuantificador de existencia único en . La clase representa el espacio de "funciones con valores no únicos" o " funciones multivaluadas " desde hasta , pero como un conjunto de pares individuales con proyección derecha en . La segunda cláusula dice que a uno le interesan sólo estas relaciones, no aquellas que son totales pero que también extienden su dominio más allá . ${\displaystyle \exists !(y\in b)}$ ${\displaystyle {\mathcal {R}}_{ab}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle a}$

No se postula que sea un conjunto, ya que con Reemplazo se puede utilizar esta colección de relaciones entre un conjunto y lo finito , es decir, las "funciones bivaloradas en ", para extraer el conjunto de todos sus subconjuntos. En otras palabras , ser un conjunto implicaría el axioma de Powerset. ${\displaystyle {\mathcal {R}}_{ab}}$ ${\displaystyle a}$ ${\displaystyle b=\{0,1\}}$ ${\displaystyle a}$ ${\displaystyle {\mathcal {P}}_{a}}$ ${\displaystyle {\mathcal {R}}_{ab}}$

Además , existe un axioma alternativo único y algo más claro al esquema de colección de subconjuntos . Postula la existencia de un conjunto suficientemente grande de relaciones totales entre y . ${\displaystyle {\mathsf {ECTS}}+{\text{Strong Collection}}}$ ${\displaystyle {\mathcal {S}}_{ab}}$ ${\displaystyle a}$ ${\displaystyle b}$

Esto dice que para dos conjuntos cualesquiera y , existe un conjunto que entre sus miembros habita una relación todavía total para cualquier relación total dada . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle {\mathcal {S}}_{ab}\subset {\mathcal {R}}_{ab}}$ ${\displaystyle s\in {\mathcal {S}}_{ab}}$ ${\displaystyle r\in {\mathcal {R}}_{ab}}$

En un dominio dado , las funciones son exactamente las relaciones totales más dispersas, es decir, las de valor único. Por tanto, el axioma implica que existe un conjunto tal que todas las funciones están en él. De esta manera, Plenitud implica Exponenciación. Implica además un refinamiento binario, que ya ha terminado . ${\displaystyle a}$ ${\displaystyle {\mathsf {BCST}}}$

El axioma de plenitud, así como la elección dependiente, también está implícito en el llamado axioma de presentación de las secciones, que también puede formularse teóricamente como categoría .

Metalógica de CZF

${\displaystyle {\mathsf {CZF}}}$tiene la propiedad de existencia numérica y la propiedad disyuntiva , pero hay concesiones: carece de la propiedad de existencia debido al esquema de subconjunto o axioma de plenitud. La propiedad de existencia no falta cuando en su lugar se adopta el axioma de exponenciación más débil o el axioma de conjunto de potencias más fuerte pero impredicativo. Esto último carece en general de una interpretación constructiva. ${\displaystyle {\mathsf {CZF}}}$

Reclamaciones indemostrables

La teoría es consistente con algunas afirmaciones anticlásicas, pero por sí sola no prueba nada que no sea demostrable en . Algunas afirmaciones destacadas no probadas por la teoría (ni por , en realidad) son parte de los principios enumerados anteriormente, en las secciones sobre escuelas constructivas en análisis, sobre la construcción de Cauchy y sobre principios no constructivos. Lo que sigue se refiere a conceptos teóricos establecidos: ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {IZF}}}$

La noción acotada de conjuntos transitivos de conjuntos transitivos es una buena manera de definir ordinales y permite la inducción de ordinales. Pero, en particular, esta definición incluye algunos subconjuntos -en . Entonces, asumir que la pertenencia de es decidible en todos los ordinales sucesores resulta válido para fórmulas acotadas en . Además, ni la linealidad de los ordinales ni la existencia de conjuntos potencias de conjuntos finitos son derivables en esta teoría, ya que suponer que cualquiera de las dos implica un conjunto potencia. La circunstancia de que los ordinales se comportan mejor en el contexto clásico que en el constructivo se manifiesta en una teoría diferente de los postulados de existencia de conjuntos grandes. ${\displaystyle \Delta _{0}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle 0}$ ${\displaystyle S\alpha }$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {CZF}}}$

Considere las funciones cuyo dominio es o algunos . Estas son secuencias y sus rangos son conjuntos contados. Denota por la clase caracterizada como el codominio más pequeño tal que los rangos de las funciones antes mencionadas también son miembros de . En , este es el conjunto hereditariamente contable , que es incontable ya que también contiene todos los ordinales contables. no prueba que tal conjunto exista, incluso cuando se supone una elección contable . ${\displaystyle \omega }$ ${\displaystyle n\in \omega }$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle H_{\aleph _{1}}}$ ${\displaystyle {\mathsf {CZF}}}$

Finalmente, la teoría no prueba que todos los espacios funcionales formados a partir de conjuntos en el universo construible sean conjuntos internos , y esto es válido incluso cuando se supone Powerset en lugar del axioma de exponenciación más débil. Entonces esta es una declaración particular que impide demostrar que la clase es un modelo de . ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle L}$ ${\displaystyle {\mathsf {CZF}}}$

Análisis ordinal

Tomar y descartar la inducción de conjuntos da una teoría que es conservadora para enunciados aritméticos, en el sentido de que prueba los mismos enunciados aritméticos para su modelo . Al agregar simplemente la inducción matemática se obtiene una teoría con prueba teórica ordinal , que es el primer punto fijo común de las funciones de Veblen para . Este es el mismo ordinal que para y está debajo del ordinal de Feferman-Schütte . Al exhibir un modelo teórico tipo, la teoría completa va más allá , siendo su ordinal el modesto ordinal de Bachmann-Howard. Suponer que la clase de ordinales tricotómicos es un conjunto aumenta la fuerza teórica de la prueba de (pero no de ). ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle \omega }$ ${\displaystyle \varphi (\varepsilon _{0},0)}$ ${\displaystyle \varphi _{\beta }}$ ${\displaystyle \beta <\varepsilon _{0}}$ ${\displaystyle {\mathsf {ML_{1}}}}$ ${\displaystyle \Gamma _{0}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle \Gamma _{0}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {IZF}}}$

Al estar relacionado con definiciones inductivas o inducción de barras , el axioma de extensión regular plantea la fuerza teórica de prueba de . Este axioma de conjuntos grandes, que garantiza la existencia de ciertos superconjuntos agradables para cada conjunto, queda demostrado por . ${\displaystyle {\mathrm {REA} }}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {ZFC}}}$

Modelos

La categoría de conjuntos y funciones de es un -pretopos. Sin entrar en la teoría del topos , ciertos pretopoi extendidos contienen modelos de . El topos efectivo contiene un modelo de esto basado en mapas caracterizados por ciertas buenas propiedades de subcontabilidad. ${\displaystyle {\mathsf {CZF}}+{\mathrm {REA} }}$ ${\displaystyle \Pi W}$ ${\displaystyle \Pi W}$ ${\displaystyle {\mathsf {CZF}}+{\mathrm {REA} }}$ ${\displaystyle {\mathsf {CZF}}+{\mathrm {REA} }}$

La separación, expresada de manera redundante en un contexto clásico, constructivamente no está implícita en Reemplazo. Hasta el momento, el debate se ha centrado únicamente en la separación limitada predicativamente justificada. Tenga en cuenta que la separación completa (junto con y también para conjuntos) está validada en algunos modelos topos efectivos, lo que significa que el axioma no estropea las piedras angulares de la escuela recursiva restrictiva. ${\displaystyle {\mathrm {RDC} }}$ ${\displaystyle {\mathrm {MP} }}$ ${\displaystyle {\mathrm {IP} }}$

Relacionadas están las interpretaciones teóricas tipográficas. En 1977, Aczel demostró que todavía se puede interpretar en la teoría de tipos de Martin-Löf , ^[20] utilizando el enfoque de proposiciones como tipos . Más específicamente, esto utiliza un universo y tipos, proporcionando lo que ahora se ve como un modelo estándar de . ^[21] Esto se hace en términos de las imágenes de sus funciones y tiene una justificación constructiva y predicativa bastante directa, conservando al mismo tiempo el lenguaje de la teoría de conjuntos. En términos generales, hay dos tipos "grandes" , todos los conjuntos se dan a través de any en some , y la membresía de a en el conjunto se define para mantenerse cuando . Por el contrario, interpreta . Todas las afirmaciones validadas en el modelo subcontable de la teoría de conjuntos se pueden demostrar exactamente mediante el principio de elección , como se explicó más arriba. Como se señaló, teorías como , y también junto con la elección, tienen la propiedad de existencia para una amplia clase de conjuntos en matemáticas comunes. Las teorías de tipo Martin-Löf con principios de inducción adicionales validan los axiomas teóricos del conjunto correspondiente. ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle W}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {ML_{1}V}}}$ ${\displaystyle U,V}$ ${\displaystyle f\colon A\to V}$ ${\displaystyle A\colon U}$ ${\displaystyle x}$ ${\displaystyle \exists (a\colon A).f(a)=x}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {ML_{1}V}}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle \Pi \Sigma }$ ${\displaystyle \mathrm {AC} }$ ${\displaystyle {\mathsf {CZF}}}$

Se han establecido los teoremas de solidez y completitud de , con respecto a la realizabilidad . ${\displaystyle {\mathsf {CZF}}}$

Rompiendo con ZF

Por supuesto, se puede añadir la tesis de Church.

Se puede postular la subcontabilidad de todos los conjuntos. Esto ya es válido en la interpretación teórica del tipo y en el modelo en el topos efectivo. Por infinito y exponenciación, es un conjunto incontable, mientras que la clase o incluso entonces no es un conjunto, según el argumento diagonal de Cantor . Entonces esta teoría rechaza lógicamente a Powerset y por supuesto . La subcontabilidad también está en contradicción con varios axiomas de conjuntos grandes . (Por otro lado, al utilizar también , algunos de estos axiomas implican la coherencia de teorías como y más fuertes.) ${\displaystyle \omega \to \omega }$ ${\displaystyle {\mathcal {P}}_{\omega }}$ ${\displaystyle {\mathcal {P}}_{1}}$ ${\displaystyle {\mathrm {PEM} }}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {ZF}}}$

Como regla de inferencia, se cierra bajo la uniformidad general de Troelstra para ambos y . Se puede adoptar como un esquema de axioma anticlásico, el principio de uniformidad que se puede denotar como , ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle z=\omega }$ ${\displaystyle z=\{0,1\}}$ ${\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)}$

Esto también es incompatible con el axioma del conjunto de potencias. El principio también se formula a menudo para . Ahora, para un conjunto binario de etiquetas , implica el esquema de indescomponibilidad , como se señaló. ${\displaystyle z=\omega }$ ${\displaystyle z=\{0,1\}}$ ${\displaystyle {\mathrm {UP} }}$ ${\displaystyle {\mathrm {UZ} }}$

En 1989, Ingrid Lindström demostró que los conjuntos no bien fundados también pueden interpretarse en la teoría de tipos de Martin-Löf, que se obtienen reemplazando la inducción de conjuntos por el axioma antifundamento de Aczel . ^[22] La teoría resultante puede estudiarse agregando también el esquema de inducción o elección dependiente relativizada , así como la afirmación de que todo conjunto es miembro de un conjunto transitivo . ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {CZFA}}}$ ${\displaystyle \omega }$

Zermelo-Fraenkel intuicionista

La teoría adopta tanto el conjunto estándar de Separación como el de Poder y, como en , uno formula convencionalmente la teoría con Colección a continuación. Como tal, puede verse como la variante más sencilla sin PEM . Como se indicó, en lugar de Reemplazo, se puede usar el ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {IZF}}}$

Mientras que el axioma de reemplazo requiere que la relación ϕ sea funcional sobre el conjunto z (como en, por cada x en z hay asociado exactamente un y ), el axioma de colección no lo requiere. Simplemente requiere que haya asociado al menos un y y afirma la existencia de un conjunto que reúne al menos un y para cada x . En clásico , el esquema de Colección implica el esquema de Axioma de reemplazo . Cuando se utiliza Powerset (y sólo entonces), se puede demostrar que son clásicamente equivalentes. ${\displaystyle {\mathsf {ZFC}}}$

Si bien se basa en una lógica más intuicionista que clásica, se considera impredicativa . Permite la formación de conjuntos mediante una operación de conjunto de potencias y utilizando el axioma general de separación con cualquier proposición, incluidas aquellas que contienen cuantificadores que no están acotados. Así, se pueden formar nuevos conjuntos en términos del universo de todos los conjuntos, distanciando la teoría de la perspectiva constructiva ascendente. Por tanto, es aún más fácil definir conjuntos con membresía indecidible, es decir, haciendo uso de predicados indecidibles definidos en un conjunto. El axioma del conjunto de potencias implica además la existencia de un conjunto de valores de verdad . En presencia de medio excluido, este conjunto tiene dos elementos. En su defecto, el conjunto de valores de verdad también se considera impredicativo. Los axiomas de son lo suficientemente fuertes como para que PEM ya implique PEM completo para fórmulas acotadas. Véase también la discusión anterior en la sección sobre el axioma de exponenciación. Y la discusión sobre la separación ya está implícito en la fórmula particular , el principio de que el conocimiento de la pertenencia a 0 siempre será decidible, sin importar el conjunto. ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle \{x\in B\mid Q(x)\}}$ ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle \forall x.{\big (}0\in x\lor 0\notin x{\big )}}$

metalógico

Como se dio a entender anteriormente, la propiedad de subcontabilidad no se puede adoptar para todos los conjuntos, dado que la teoría demuestra ser un conjunto. La teoría tiene muchas de las buenas propiedades de existencia numérica y es, por ejemplo, consistente con el principio de tesis de Church, además de ser subcontable. También tiene la propiedad disyuntiva. ${\displaystyle {\mathcal {P}}_{\omega }}$ ${\displaystyle \omega \to \omega }$

${\displaystyle {\mathsf {IZF}}}$con Reemplazo en lugar de Colección tiene la propiedad de existencia general, incluso cuando se adopta una elección dependiente relativizada además de todo. Pero tal como está formulado no es así. La combinación de esquemas que incluyen la separación total lo estropea. ${\displaystyle {\mathsf {IZF}}}$

Incluso sin PEM , la fuerza teórica de prueba de es igual a la de . Y demuestra que son equiconsistentes y prueban las mismas oraciones. ${\displaystyle {\mathsf {IZF}}}$ ${\displaystyle {\mathsf {ZF}}}$ ${\displaystyle {\mathsf {HA}}}$ ${\displaystyle \Pi _{1}^{0}}$

Z intuicionista

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

KP intuicionista

Mencionemos otra teoría muy débil que ha sido investigada, a saber, la teoría de conjuntos intuicionista (o constructiva) de Kripke-Platek . No sólo tiene Separación sino también Colección restringida a fórmulas, es decir, es similar pero con Inducción en lugar de Reemplazo completo. La teoría no encaja en la jerarquía presentada anteriormente, simplemente porque tiene un esquema de axioma de inducción de conjuntos desde el principio. Esto permite teoremas que involucran la clase de ordinales. La teoría tiene la propiedad de disyunción. Por supuesto, se obtienen versiones más débiles de restringiendo el esquema de inducción a clases más estrechas de fórmulas, digamos . La teoría es especialmente débil cuando se estudia sin el Infinito. ${\displaystyle {\mathsf {IKP}}}$ ${\displaystyle \Delta _{0}}$ ${\displaystyle {\mathsf {BCST}}}$ ${\displaystyle {\mathsf {IKP}}}$ ${\displaystyle \Sigma _{1}}$

Teorías ordenadas

Teoría de conjuntos constructiva

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

• El habitual Axioma de Extensionalidad para conjuntos, así como uno para funciones, y el habitual Axioma de unión .
• El axioma de separación restringida o predicativa , que es una forma debilitada del axioma de separación de la teoría de conjuntos clásica, que requiere que cualquier cuantificación esté limitada a otro conjunto, como se analizó.
• Una forma del axioma del infinito que afirma que el conjunto de números naturales (para los que introduce una constante ) es de hecho un conjunto. ${\displaystyle \omega }$
• El axioma de exponenciación, que afirma que para dos conjuntos cualesquiera, existe un tercer conjunto que contiene todas (y sólo) las funciones cuyo dominio es el primer conjunto y cuyo rango es el segundo conjunto. Se trata de una forma muy debilitada del axioma de conjunto de potencias de la teoría de conjuntos clásica, al que Myhill, entre otros, objetó por su impredicatividad .

Y además:

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

Se puede identificar aproximadamente la fuerza de esta teoría con subteorías constructivas en comparación con las secciones anteriores. ${\displaystyle {\mathsf {ZF}}}$

Y finalmente la teoría adopta

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

Teoría de conjuntos estilo obispo

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

En este contexto se han desarrollado muchos análisis y teorías de módulos .

Teorías de categorías

No todas las teorías lógicas formales de conjuntos necesitan axiomizar el predicado de pertenencia binaria " " directamente. Una teoría como la Teoría Elemental de las Categorías de Conjuntos ( ), por ejemplo, que captura pares de asignaciones componibles entre objetos, también puede expresarse con una lógica de fondo constructiva. La teoría de categorías puede plantearse como una teoría de flechas y objetos, aunque las axiomatizaciones de primer orden sólo son posibles en términos de flechas. ${\displaystyle \in }$ ${\displaystyle {\mathsf {ETCS}}}$

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

Buenos modelos de teorías constructivas de conjuntos en la teoría de categorías son los pretopos mencionados en la sección Exponenciación. Para una buena teoría de conjuntos, esto puede requerir suficientes proyectivos , un axioma sobre las "presentaciones" sobreyectivas de conjuntos, que implica elección contable y dependiente.

Ver también

• Esquema de axioma de separación predicativa
• Matemáticas constructivas
• Análisis constructivo
• Regla y principio de la tesis de la Iglesia Constructiva
• Conjunto computable
• Propiedad de existencia
• teorema de diaconescu
• Inducción épsilon
• Conjunto hereditariamente finito
• Heyting aritmética
• Impredicatividad
• Teoría de tipos intuicionista
• Ley del tercero excluido
• Análisis ordinal
• Teoría de conjuntos
• Subcontabilidad

Referencias

1. Troelstra, AS, van Dalen D., Constructivismo en matemáticas: una introducción 1 ; Estudios de Lógica y Fundamentos de las Matemáticas; Springer, 1988;
2. Bridges D., Ishihara H., Rathjen M., Schwichtenberg H. (Editores), Manual de matemáticas constructivas ; Estudios de Lógica y Fundamentos de las Matemáticas; (2023) págs.20-56
3. Myhill, "Algunas propiedades de la teoría intuicionista de conjuntos de Zermelo-Fraenkel", Actas de la Escuela de verano de Cambridge de 1971 en lógica matemática (Notas de conferencias sobre matemáticas 337) (1973) págs.
4. Peter Aczel y Michael Rathjen, Notas sobre la teoría constructiva de conjuntos, Reports Institut Mittag-Leffler, Lógica matemática - 2000/2001, n.º 40
5. John L. Bell, Teorías de conjuntos intuicionistas, 2018
6. Jeon, Hanul (2022), "Interpretación constructiva de Ackermann", Annals of Pure and Applied Logic , 173 (5): 103086, arXiv : 2010.04270 , doi :10.1016/j.apal.2021.103086, S2CID  222271938
7. Gambino, N. (2005). "Modelos previos al haz para teorías constructivas de conjuntos" (PDF) . En Laura Crosilla y Peter Schuster (ed.). De conjuntos y tipos a topología y análisis (PDF) . págs. 62–96. doi :10.1093/acprof:oso/9780198566519.003.0004. ISBN 9780198566519.
8. Scott, DS (1985). Modelos de teoría de categorías para la teoría de conjuntos intuicionista. Diapositivas manuscritas de una charla impartida en la Universidad Carnegie-Mellon
9. Benno van den Berg, Teoría del topos predicativo y modelos para la teoría constructiva de conjuntos, Universidad de Holanda, tesis doctoral, 2006
10. Gert Smolka, Teoría de conjuntos en teoría de tipos, Apuntes de conferencias, Universidad del Sarre, enero de 2015
11. Gert Smolka y Kathrin Stark, Conjuntos hereditariamente finitos en la teoría de tipos constructivos, Proc. de ITP 2016, Nancy, Francia, Springer LNCS, mayo de 2015
12. Diener, Hannes (2020). "Matemática inversa constructiva". arXiv : 1804.05495 ​​[matemáticas.LO].
13. Sørenson, Morten; Urzyczyn, Paweł (1998), Conferencias sobre el isomorfismo de Curry-Howard , CiteSeerX 10.1.1.17.7385 , pag. 239
14. Smith, Peter (2007). Una introducción a los teoremas de Gödel (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 978-0-521-67453-9. SEÑOR  2384958., pag. 297
15. Prádic, Pierre; Marrón, Chad E. (2019). "Cantor-Bernstein implica medio excluido". arXiv : 1904.09193 [matemáticas.LO].
16. Michael Rathjen, Principios de elección en teorías de conjuntos clásicas y constructivas, Cambridge University Press: 31 de marzo de 2017
17. Gitman, Victoria (2011), ¿Cuál es la teoría ZFC sin conjunto de energía ?, arXiv : 1110.2430
18. Robert S. Lubarsky, Sobre la integridad de Cauchy de los reales constructivos de Cauchy, julio de 2015
19. Matthew Ralph John Hendtlass, Construcción de puntos fijos y equilibrios económicos, tesis doctoral, Universidad de Leeds, abril de 2013
20. Aczel, Peter: 1978. La interpretación teórica de tipos de la teoría constructiva de conjuntos. En: A. MacIntyre et al. (eds.), Coloquio de lógica '77, Ámsterdam: Holanda Septentrional, 55–66.
21. Rathjen, M. (2004), "Predicatividad, circularidad y antifundación" (PDF) , en Link, Godehard (ed.), Cien años de la paradoja de Russell: matemáticas, lógica, filosofía , Walter de Gruyter, ISBN 978-3-11-019968-0
22. Lindström, Ingrid: 1989. Una construcción de conjuntos no bien fundamentados dentro de la teoría de tipos de Martin-Löf. Revista de lógica simbólica 54: 57–64.

Otras lecturas

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

enlaces externos

• Crosilla, Laura (13 de febrero de 2019). "Teoría de conjuntos: ZF constructiva e intuicionista". En Zalta, Edward N. (ed.). Enciclopedia de Filosofía de Stanford .
• Van den Berg, Benno (7 de septiembre de 2012). "Teoría constructiva de conjuntos: una descripción general" (PDF) . Diapositivas de Heyting dag, Amsterdam