Théorie des ensembles constructifs - Constructive set theory

La théorie constructive des ensembles est une approche du constructivisme mathématique suivant le programme de la théorie axiomatique des ensembles . Le même langage de premier ordre avec " " et " " de la théorie des ensembles classique est généralement utilisé, il ne faut donc pas le confondre avec une approche des types constructifs . D'autre part, certaines théories constructives sont en effet motivées par leur interprétabilité dans les théories des types . ${\style d'affichage =}$${\style d'affichage \in }$

En plus de rejeter la loi du tiers exclu ( ), les théories des ensembles constructifs exigent souvent que certains quantificateurs logiques soient bornés dans leurs axiomes , motivés par des résultats liés à l' imprédicativité . ${\displaystyle {\mathrm {LEM} }}$

introduction

Perspectives

La logique des théories des ensembles discutées ici est constructive en ce qu'elle rejette , c'est-à-dire que la disjonction vaut automatiquement pour toutes les propositions. Cela nécessite alors le rejet des principes de choix fort et la reformulation de certains axiomes standards. Par exemple, l' Axiome du Choix implique pour les formules dans son schéma de Séparation adopté, par le théorème de Diaconescu . Des résultats similaires sont valables pour l' axiome de régularité sous sa forme standard. En règle générale, pour prouver une disjonction particulière , soit ou doit être prouvé. Dans ce cas, on dit que la disjonction est décidable. À leur tour, les théories constructives ont tendance à ne pas permettre de nombreuses preuves classiques de propriétés qui sont par exemple prouvables indécidables par calcul . Contrairement à la logique minimale plus conservatrice , ici la logique sous-jacente permet l' élimination de la double négation pour les prédicats décidables et les formulations des théorèmes concernant les constructions finies ont tendance à ne pas différer de leurs homologues classiques. ${\displaystyle {\mathrm {LEM} }}$ ${\displaystyle \phi \lor \neg \phi }$${\displaystyle {\mathrm {LEM} }}$${\displaystyle P\lor \neg P}$${\style d'affichage P}$${\style d'affichage \neg P}$

Notamment, une restriction à la logique constructive conduit à des exigences plus strictes concernant les caractérisations d'un ensemble impliquant des collections illimitées qui constituent une fonction (mathématique, et donc toujours totale ). C'est souvent parce que le prédicat dans une définition potentielle au cas par cas peut ne pas être décidable. Par rapport à l'homologue classique, on est généralement moins susceptible de prouver l'existence de relations qui ne peuvent pas être réalisées. Cela affecte alors aussi la prouvabilité des déclarations sur les ordres totaux tels que celui de tous les nombres ordinaux , exprimé par la vérité et la négation des termes dans l'ordre définissant la disjonction . Et cela affecte à son tour la force théorique de la preuve définie dans l'analyse ordinale . ${\displaystyle f\sous-ensemble X\fois Y}$${\displaystyle (\alpha \in \beta )\lor (\alpha =\beta )\lor (\beta \in \alpha )}$

Cela dit, les théories mathématiques constructives tendent généralement à prouver des reformulations classiquement équivalentes des théorèmes classiques. Par exemple, en analyse constructive , on ne peut pas prouver le théorème des valeurs intermédiaires dans sa formulation de manuel, mais on peut prouver des théorèmes à contenu algorithmique qui, dès qu'on le suppose, sont à la fois classiquement équivalents à l'énoncé classique. La différence est que les preuves constructives sont plus difficiles à trouver. ${\displaystyle {\mathrm {LEM} }}$

Sur les modèles

De nombreuses théories étudiées dans la théorie des ensembles constructive sont de simples restrictions de la théorie${\displaystyle {\mathsf {ZF}}}$ des ensembles de Zermelo-Fraenkel ( ) en ce qui concerne leur axiome ainsi que leur logique sous-jacente. De telles théories peuvent alors également être interprétées dans n'importe quel modèle de . En ce qui concerne les réalisations constructives, il existe une théorie de la réalisabilité et la théorie d'Aczel constructive Zermelo-Fraenkel ( ) a été interprétée dans une théorie de type Martin-Löf , comme décrit ci-dessous. De cette façon, les théorèmes de la théorie des ensembles prouvables et les théories plus faibles sont candidats à une réalisation informatique. Plus récemment, des modèles de préfaisceau pour les théories constructives des ensembles ont été introduits. Ceux-ci sont analogues aux modèles Presheaf non publiés pour la théorie des ensembles intuitionniste développés par Dana Scott dans les années 1980. ${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZF}}}$

Aperçu

Le sujet de la théorie des ensembles constructifs (souvent " ") a commencé par les travaux de John Myhill sur la théorie aussi appelée , une théorie de plusieurs sortes et quantification bornée, visant à fournir une base formelle pour le programme de mathématiques constructives d' Errett Bishop . Vous trouverez ci-dessous une séquence de théories dans le même langage que , menant à l' ouvrage bien étudié de Peter Aczel et au-delà. est également caractérisé par les deux caractéristiques présentes également dans la théorie de Myhill : d'une part, elle utilise la Séparation Prédicative au lieu du schéma de Séparation complet et illimité, voir aussi la hiérarchie de Lévy . La limite peut être traitée comme une propriété syntaxique ou, alternativement, les théories peuvent être étendues de manière conservatrice avec un prédicat de limite plus élevé et ses axiomes. En second lieu , l' imprédicative axiome Powerset est rejeté, généralement en faveur des axiomes connexes , mais plus faibles. La forme forte est très négligemment utilisée dans la topologie générale classique . Ajout à une théorie encore plus faible que récupère , comme détaillé ci-dessous. Le système, connu sous le nom de théorie des ensembles intuitionniste de Zermelo-Fraenkel ( ), est une théorie des ensembles forte sans . Elle est similaire à , mais moins conservatrice ou prédicative . La théorie notée est la version constructive de , la théorie des ensembles classique de Kripke-Platek où même l'Axiome de Collection est borné. ${\displaystyle {\mathsf {CST}}}$${\displaystyle {\mathsf {CST}}}$${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathrm {LEM} }}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {IZF}}}$${\displaystyle {\mathrm {LEM} }}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {IKP}}}$${\displaystyle {\mathsf {KP}}}$

Sous-théories de ZF

Notation

Ci-dessous, le grec désigne une variable de prédicat dans les schémas d'axiome et l'utilisation ou pour des prédicats particuliers. L'existence unique signifie par exemple . Les quantificateurs dépassent l'ensemble et sont indiqués par des lettres minuscules. ${\style d'affichage \phi }$${\style d'affichage P}$${\style d'affichage Q}$${\displaystyle \exists !xP(x)}$${\displaystyle \exists x.\forall y.\left(y=x\iff P(y)\right)}$

Comme il est courant dans l'étude des théories des ensembles , on utilise la notation du constructeur d'ensembles pour les classes , qui, dans la plupart des contextes, ne font pas partie du langage objet mais sont utilisées pour une discussion concise. En particulier, on peut introduire des déclarations de notation de la classe correspondante via " ", dans le but d'exprimer comme . Des prédicats logiquement équivalents peuvent être utilisés pour introduire la même classe. On écrit aussi comme raccourci pour . ${\displaystyle A=\{z\mid P(z)\}}$${\style d'affichage P(a)}$${\displaystyle a\in A}$${\displaystyle \{z\in B\mid P(z)\}}$${\displaystyle \{z\mid z\in B\land P(z)\}}$

Comme il est courant, on peut abréger par et exprimer la revendication de sous-classe , c'est -à- dire par . ${\displaystyle \forall z.(z\in A\implique P(z))}$${\displaystyle \forall (z\in A).P(z)}$${\displaystyle \forall (z\in A).z\in B}$${\displaystyle \forall z.(z\in A\implique z\in B)}$${\style d'affichage A\sous-ensemble B}$

Pour une propriété , trivialement . Et ainsi suit cela . ${\style d'affichage P}$${\displaystyle \forall z.{\big (}(z\in B\land P(z))\implies z\in B{\big )}}$${\displaystyle \{z\in B\mid P(z)\}\sous-ensemble B}$

Axiomes communs

Un point de départ d' axiomes qui sont pratiquement toujours considérés comme non controversés et font partie de toutes les théories considérées dans cet article. ${\displaystyle {\mathsf {ZF}}}$

Désignons par la déclaration exprimant que deux classes ont exactement les mêmes éléments, c'est -à- dire , ou de manière équivalente . ${\style d'affichage A\simeq B}$${\displaystyle \forall z.(z\in A\iff z\in B)}$${\displaystyle (A\sous-ensemble B)\land (B\sous-ensemble A)}$

L'axiome suivant donne un moyen de prouver l'égalité " " de deux ensembles , de sorte que par substitution , tout prédicat about se traduit par l'un de . ${\style d'affichage =}$${\style d'affichage x}$${\style d'affichage y}$

Extensionnalité ${\displaystyle \forall x.\forall y.\ \ x\simeq y\implies x=y}$

Par les propriétés logiques de l'égalité, la direction inverse se vérifie automatiquement.

Dans une interprétation constructive, les éléments d'une sous-classe de peuvent être dotés de plus d'informations que ceux de , en ce sens qu'être capable de juger c'est être capable de juger . Et (à moins que toute la disjonction ne découle des axiomes) dans l' interprétation Brouwer-Heyting-Kolmogorov , cela signifie l'avoir prouvé ou l'avoir rejeté. Comme il n'est peut-être pas décidable pour tous les éléments de , les deux classes doivent a priori être distinguées. ${\displaystyle A=\{z\in B\mid Q(z)\lor \neg Q(z)\}}$${\style d'affichage B}$${\style d'affichage B}$${\style d'affichage b\dans A}$${\displaystyle Q(b)\lor \neg Q(b)}$${\style d'affichage Q(b)}$${\style d'affichage Q}$ ${\style d'affichage B}$

Considérons une propriété qui est valable pour tous les éléments d'un ensemble , de sorte que , et supposons que la classe du côté gauche est établie pour être un ensemble. Notez que, même si cet ensemble de gauche est également lié de manière informelle à des informations pertinentes pour la preuve sur la validité de pour tous les éléments, l'axiome d'extensionnalité postule que, dans notre théorie des ensembles, l'ensemble de gauche est jugé égal au un sur le côté droit. ${\style d'affichage P}$${\style d'affichage y}$${\displaystyle \{z\in y\mid P(z)\}\simeq y}$${\style d'affichage P}$

Les théories de type modernes peuvent plutôt viser à définir l'équivalence demandée " " en termes de fonctions, voir par exemple l' équivalence de type . Le concept connexe d' extensionnalité de fonction n'est souvent pas adopté dans la théorie des types. ${\style d'affichage \simeq }$

D'autres cadres de mathématiques constructives pourraient plutôt exiger une règle particulière d'égalité ou de séparation pour les éléments de chaque ensemble discuté. Même alors, la définition ci-dessus peut être utilisée pour caractériser l'égalité des sous - ensembles et . ${\style d'affichage z\in x}$${\style d'affichage x}$ ${\displaystyle u\sous-ensemble x}$${\displaystyle v\sous-ensemble x}$

Voici deux autres axiomes de base. Premièrement,

Jumelage ${\displaystyle \forall x.\forall y.\ \ \existe p.\forall z.{\big (}(z=x\lor z=y)\implies z\in p{\big )}}$

en disant que pour deux ensembles et , il existe au moins un ensemble , qui contient au moins ces deux ensembles ( ). ${\style d'affichage x}$${\style d'affichage y}$${\style d'affichage p}$${\style d'affichage z}$

Puis,

syndicat ${\displaystyle \forall x.\ \ \exists u.\forall y.{\big (}(\exists zy\in z\land z\in x)\implies y\in u{\big )}}$

en disant que tout ensemble , il y a au moins un ensemble , qui contient tous les membres , des membres de . ${\style d'affichage x}$${\mode d'affichage u}$${\style d'affichage y}$${\style d'affichage x}$${\style d'affichage z}$

Les deux axiomes peuvent également être formulés plus fort en termes de " ", par exemple dans le contexte de avec Séparation, ce n'est pas nécessaire. ${\style d'affichage \iff }$${\displaystyle {\mathsf {BCST}}}$

Ensemble, ces deux axiomes impliquent l'existence de l'union binaire de deux classes et lorsqu'elles ont été établies pour être des ensembles, et cela est noté ou . Définissez la notation de classe pour les éléments finis via des disjonctions, par exemple, dit , et définissez l' ensemble successeur comme . Sorte de mélange entre l'appariement et l'union, un axiome plus facilement apparenté au successeur est l' Axiome d'adjonction . Il est pertinent pour la modélisation standard des ordinaux de Neumann individuels . Cet axiome serait également facilement accepté, mais n'est pas pertinent dans le contexte des axiomes plus forts ci-dessous. Désigne par le modèle de paire ordonnée standard . ${\style d'affichage a}$${\style d'affichage b}$${\displaystyle \bigcup \{a,b\}}$${\displaystyle a\cup b}$${\displaystyle c\in \{a,b\}}$${\style d'affichage (c=a)\lor (c=b)}$ ${\displaystyle Sx}$${\displaystyle x\cup \{x\}}$${\displaystyle \langle x,y\rangle }$${\style d'affichage \{\{x\},\{x,y\}\}}$

La propriété qui est fausse pour tout ensemble correspond à la classe vide, notée par ou zéro, 0. Qu'il s'agisse d'un ensemble découle facilement d'autres axiomes, tels que l'Axiome de l'infini ci-dessous. Mais si, par exemple, on est explicitement intéressé à exclure les ensembles infinis dans son étude, on peut à ce stade adopter l' axiome de l'ensemble vide${\style d'affichage \{\}}$

${\displaystyle \exists x.\forall y.\,\neg (y\in x)}$

BCST

Ce qui suit utilise des schémas d'axiomes , c'est-à-dire des axiomes pour une collection de prédicats. Notez que certains des schémas d'axiome indiqués sont également souvent présentés avec des paramètres définis , c'est-à-dire des variantes avec des fermetures universelles supplémentaires telles que les 's peuvent dépendre des paramètres. ${\style d'affichage v}$${\displaystyle \forall v}$${\style d'affichage \phi }$

La théorie des ensembles constructive de base se compose de plusieurs axiomes faisant également partie de la théorie des ensembles standard, sauf que l' axiome de séparation est affaibli. Au-delà des trois axiomes ci-dessus, il adopte le ${\displaystyle {\mathsf {BCST}}}$

Schéma axiome de la séparation prédicative : Pour tout prédicat borné contenant du non libre, ${\style d'affichage \phi }$${\style d'affichage y}$ ${\displaystyle \forall y.\ \ \exists s.\forall x.{\Big (}x\in s\iff {\big (}x\in y\land \phi (x){\big )}{ \Gros )}}$

L'axiome revient à postuler l'existence d'un ensemble obtenu par l'intersection de tout ensemble et de toute classe décrite prédicativement . Lorsque le prédicat est pris pour avéré être un ensemble, on obtient l'intersection binaire des ensembles et écrit . ${\style d'affichage s}$${\style d'affichage y}$${\displaystyle \{x\mid \phi (x)\}}$${\style d'affichage x\dans z}$${\style d'affichage z}$${\displaystyle s=y\cap z}$

Le schéma est également appelé Séparation bornée, comme dans Séparation pour les quantificateurs bornés uniquement. C'est le schéma de l'axiome qui fait référence aux aspects syntaxiques des prédicats. Les formules bornées sont également notées dans l'ensemble de la hiérarchie de Lévy théorique, par analogie à dans la hiérarchie arithmétique . (Notez cependant que la classification arithmétique est parfois exprimée non pas syntaxiquement mais en termes de sous-classes des naturels. De plus, le niveau inférieur a plusieurs définitions communes, certaines ne permettant pas l'utilisation de certaines fonctions totales. La distinction n'est pas pertinente au niveau ou plus haut.) La restriction dans l'axiome est également des définitions imprédicatives de contrôle : l'existence ne devrait au mieux pas être revendiquée pour des objets qui ne sont pas explicitement descriptibles, ou dont la définition implique eux-mêmes ou une référence à une classe appropriée, comme lorsqu'une propriété à vérifier implique un quantificateur universel. Donc , dans une théorie constructive sans Axiome d' ensemble de puissance , il ne faut pas s'attendre à une classe définie comme ${\displaystyle \Delta _{0}}$${\displaystyle \Delta _{0}^{0}}$${\displaystyle \Sigma _{1}^{0}}$${\style d'affichage s}$

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

c'est à dire

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

être un ensemble, où désigne un prédicat 2-aire. Notez que si cette sous-classe est prouvablement un ensemble, alors le terme ainsi défini est également dans la portée illimitée de la variable term et remplit le prédicat entre crochets dans , utilisé pour se définir. Alors que la séparation prédicative conduit à moins de définitions de classes données étant des ensembles, il faut souligner que de nombreuses définitions de classes qui sont classiquement équivalentes ne le sont pas lorsque l'on se limite à la logique constructive. Donc, de cette façon, on obtient une théorie plus large, de manière constructive. En raison de l' indécidabilité potentielle des prédicats généraux, la notion de sous-classe est plus élaborée dans les théories des ensembles constructives que dans les théories classiques. ${\style d'affichage Q}$${\style d'affichage s}$${\style d'affichage t}$${\style d'affichage t}$

Comme indiqué, à partir de la séparation et de l'existence de tout ensemble (par exemple l'infini ci-dessous) et du prédicat faux de tout ensemble suivront l'existence de l'ensemble vide.

En vertu du théorème purement logique , la construction de Russel montre que la séparation prédicative seule implique que . En particulier, aucun ensemble universel n'existe. ${\displaystyle \forall x.{\big (}xRs\Leftrightarrow (xRy\land \neg xRx){\big )}\implies \neg sRy}$${\displaystyle \{x\in y\mid x\notin x\}\notin y}$

Dans ce contexte conservateur de , le schéma de séparation bornée est en fait équivalent à un ensemble vide plus l'existence de l'intersection binaire pour deux ensembles quelconques. Cette dernière variante de l'axiomatisation ne fait pas appel à un schéma. Comme le sous - typage n'est pas une caractéristique nécessaire de la théorie des types constructifs , on peut dire que la théorie des ensembles constructive diffère assez de ce cadre. ${\displaystyle {\mathsf {BCST}}}$

Considérez ensuite le

Schéma axiome de remplacement : Pour tout prédicat , ${\style d'affichage \phi }$ ${\displaystyle \forall d.\ \ \forall (x\in d).\exists !y.\phi (x,y)\implies \exists r.\forall y.{\big (}y\in r\ ssi \existe (x\in d).\phi (x,y){\big )}}$

C'est accorder l'existence, en tant qu'ensembles, de l'éventail des prédicats fonctionnels, obtenus via leurs domaines.

Avec le schéma de remplacement, cette théorie prouve que les classes d'équivalence ou sommes indexées sont des ensembles. En particulier, le produit cartésien , contenant toutes les paires d'éléments de deux ensembles, est un ensemble.

Le remplacement et l'axiome de l'induction d'ensembles (introduits ci-dessous) suffisent à axiomiser les ensembles héréditairement finis de manière constructive et cette théorie est également étudiée sans l'infini. À titre de comparaison, considérons la théorie classique très faible appelée théorie générale des ensembles qui interprète la classe des nombres naturels et leur arithmétique via simplement l'extensionnalité, l'adjonction et la séparation complète.

Dans , le remplacement est surtout important pour prouver l'existence d'ensembles de rang élevé , notamment via des instances du schéma d'axiome où associe un ensemble relativement petit à des ensembles plus grands, . ${\displaystyle {\mathsf {ZF}}}$${\style d'affichage \phi (x,y)}$${\style d'affichage x}$${\style d'affichage y}$

Les théories constructives des ensembles ont généralement un schéma axiome de remplacement, parfois limité à des formules bornées. Cependant, lorsque d'autres axiomes sont abandonnés, ce schéma est en fait souvent renforcé - pas au - delà de , mais simplement pour regagner une certaine force de prouvabilité. ${\displaystyle {\mathsf {ZF}}}$

Le remplacement peut être vu comme une forme de compréhension. Ce n'est qu'en supposant que le remplacement implique déjà une séparation complète. ${\displaystyle {\mathrm {LEM} }}$

ECST

Notons par la propriété inductive, par exemple . En termes de prédicat sous-jacent à la classe, cela serait traduit par . Dénote ici une variable d'ensemble générique. Écrire pour . Définir une classe . ${\displaystyle \mathrm {Ind} (A)}$${\displaystyle 0\in A\land \forall (n\in A).Sn\in A}$${\style d'affichage P}$${\displaystyle P(0)\land \forall n.{\big (}P(n)\implique P(Sn){\big )}}$${\style d'affichage n}$${\displaystyle \bigcap A}$${\displaystyle \{x\mid \forall y.(y\in A\implies x\in y)\}}$${\displaystyle \omega =\bigcap \{x\mid \mathrm {Ind} (x)\}}$

Pour certains prédicats fixes , l'instruction exprime qu'il s'agit du plus petit ensemble parmi tous les ensembles pour lesquels est vrai. La théorie des ensembles constructive élémentaire a l'axiome de ainsi que ${\style d'affichage P}$${\displaystyle P(a)\land \forall xP(x)\implique un\sous-ensemble x}$${\style d'affichage a}$${\style d'affichage x}$${\style d'affichage P(x)}$${\displaystyle {\mathsf {ECST}}}$${\displaystyle {\mathsf {BCST}}}$

Infini fort ${\displaystyle \exists w.{\Big (}\mathrm {Ind} (w)\,\land \,{\big (}\forall x.\mathrm {Ind} (x)\implies w\subset x{ \gros gros )}}$

Le second conjoint universellement quantifié exprime l'induction mathématique pour tout dans l'univers du discours, c'est-à-dire pour les ensembles, resp. pour les prédicats s'ils définissent effectivement des ensembles . De cette façon, les principes discutés dans cette section donnent des moyens de prouver que certains prédicats sont valables au moins pour tous les éléments de . Soyez conscient que même l'axiome assez fort de l'induction mathématique complète (induction pour tout prédicat, discuté ci-dessous) peut également être adopté et utilisé sans jamais postuler qu'il forme un ensemble. ${\style d'affichage x}$${\style d'affichage x}$${\displaystyle \omega }$${\displaystyle \omega }$

Des formes faibles d'axiomes de l'infini peuvent être formulées, toutes postulant qu'il existe des ensembles avec les propriétés communes des nombres naturels. Ensuite, la séparation complète peut être utilisée pour obtenir un tel ensemble « clairsemé », l'ensemble des nombres naturels. Dans le contexte de systèmes d'axiomes par ailleurs plus faibles, un axiome d'infini devrait être renforcé de manière à impliquer l'existence d'un tel ensemble clairsemé. Une forme plus faible de l'infini

${\displaystyle \exists w.\forall m.{\Big (}m\in w\iff {\big (}m=0\lor (\exists n\in w).\forall k.(k\in m \iff k\in n\lor k=n){\grand )}{\Grand )}}$

qui peut également être écrit de manière plus concise en utilisant . L'ensemble ainsi postulé pour exister est généralement noté par , le plus petit ordinal infini de von Neumann . Pour les éléments de cet ensemble, la revendication est décidable. ${\style d'affichage S}$${\displaystyle \omega }$${\style d'affichage n,m}$${\style d'affichage n=m}$

Avec cela, prouve l' induction pour tous les prédicats donnés par des formules bornées. Les deux des cinq axiomes de Peano concernant zéro et un concernant la fermeture de par rapport à suivre assez directement des axiomes de l'infini. Enfin, peut s'avérer être une opération injective. ${\displaystyle {\mathsf {ECST}}}$${\style d'affichage S}$${\displaystyle \omega }$${\style d'affichage S}$

Les nombres naturels sont distinguables, ce qui signifie que l'égalité (et donc l'inégalité) d'entre eux est décidable. L'ordre de base est capturé par l'appartenance à ce modèle. Par souci de notation standard, notons un segment initial des nombres naturels, pour tout , y compris l'ensemble vide. ${\displaystyle \{0,1,\dots ,n-1\}}$${\displaystyle \{k\in \omega \mid k<n\}}$${\displaystyle k\in \omega }$

Les fonctions

Naturellement, le sens logique des prétentions à l'existence est un sujet d'intérêt dans la logique intuitionniste. Ici, l'accent est mis sur les relations totales .

Le calcul de la preuve, dans un cadre mathématique constructif, d'énoncés tels que

${\displaystyle \forall (a\in A).\existe (c\in C).P(a,c)}$

pourraient être mis en place en termes de programmes sur des domaines représentés et éventuellement avoir à témoigner de la revendication. Ceci doit être compris dans le sens de, de manière informelle, , où désigne la valeur d'un programme tel que mentionné, mais cela soulève des questions de théorie de la réalisabilité . Pour un contexte plus fort, si et quand la proposition est valable, alors exiger que cela soit toujours possible avec une fonction récursive totale réalisée est un postulat possible de la thèse de l'Église adopté, par conséquent, dans le constructivisme russe strictement non classique . Dans le paragraphe précédent, "fonction" doit être compris dans le sens calculable de la théorie de la récursivité - cette ambiguïté occasionnelle doit également être surveillée ci-dessous. ${\displaystyle \forall (a\in A).P(a,c_{a})}$${\style d'affichage c_{a}}$${\displaystyle A=C=\omega }$${\displaystyle a\mapsto c_{a}}$

Dans le même ordre d'idées, considérons l' arithmétique de Robinson , qui est une théorie arithmétique classique qui substitue le schéma d' induction mathématique complet à une prétention à l'existence d'un nombre prédécesseur. C'est un théorème que cette théorie représente exactement les fonctions récursives dans le sens de définir des prédicats qui sont de toute évidence des relations fonctionnelles totales , ${\style d'affichage P}$

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

Maintenant, dans l'approche théorique des ensembles actuelle, wdéfinir la propriété impliquant les crochets d' application de la fonction , , comme et parler d'une fonction lorsqu'il est prouvé ${\style d'affichage f(a)=c}$${\displaystyle \langle a,c\rangle \in f}$${\displaystyle f\sous-ensemble A\fois C}$

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

c'est à dire

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

ce qui implique notamment un quantificateur existentiel. Qu'une sous-classe puisse être considérée comme une fonction dépendra de la force de la théorie, c'est-à-dire des axiomes que l'on adopte.

Notamment, une classe générale pourrait remplir le prédicat ci-dessus sans être une sous-classe du produit , c'est-à-dire que la propriété n'exprime ni plus ni moins que la fonctionnalité par rapport aux entrées de . Si domaine et codomaine sont des ensembles, alors le prédicat ci-dessus n'implique que des quantificateurs bornés. Des précautions doivent être prises avec la nomenclature "fonction", qui est utilisée dans la plupart des cadres mathématiques, également parce que certains lient un terme de fonction lui-même à un codomaine particulier. Des variantes de la définition du prédicat fonctionnel utilisant des relations de séparation sur les sétoïdes ont également été définies. ${\style d'affichage A\fois C}$${\style d'affichage A}$

Soit (également écrit ) la classe de telles fonctions ensemblistes. En utilisant la terminologie de classe standard, on peut librement utiliser des fonctions, étant donné que leur domaine est un ensemble. Les fonctions dans leur ensemble seront définies si leur codomaine l'est. Lorsque les fonctions sont comprises comme des graphes de fonctions comme ci-dessus, la proposition d'appartenance s'écrit également . Ci-dessous, vous pouvez écrire pour le distinguer de l'exponentiation ordinale. ${\style d'affichage C^{A}}$${\displaystyle {}^{A}C}$${\displaystyle f\in C^{A}}$${\displaystyle f\colon A\à C}$${\style d'affichage x\à y}$${\style d'affichage y^{x}}$

La séparation permet d'utiliser des sous-ensembles de produits découpés , du moins lorsqu'ils sont décrits de façon bornée. Écrire pour . Compte tenu de tout , on est maintenant conduit à raisonner sur des classes telles que ${\style d'affichage A\fois C}$${\style d'affichage 1}$${\style d'affichage S0}$${\style d'affichage B\sous-ensemble A}$

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

Les fonctions caractéristiques booléennes font partie de ces classes. Mais sachez que cela peut en général ne pas être décidable . C'est-à-dire qu'en l'absence de tout axiome non constructif, la disjonction peut ne pas être prouvable, puisqu'il faut une preuve explicite de l'une ou l'autre disjonction. Lorsque ${\displaystyle \chi _{B}\colon A\to \{0,1\}}$${\style d'affichage a\dans B}$${\displaystyle a\in B\lor a\notin B}$

${\displaystyle \exists (y_{a}\in \{0,1\}).f(a)=y_{a}}$

ne peut pas être observé pour tous , ou l'unicité d'un terme n'est pas prouvée, alors on ne peut pas juger de manière constructive la collection comprise comme fonctionnelle. ${\displaystyle a\in A}$${\displaystyle y_{a}}$

Pour et tout naturel , ont ${\displaystyle I=\{n\in \omega \mid Q(n)\}}$${\displaystyle n\in \omega }$

${\displaystyle Q(n)\lor \neg Q(n)\implique n\in I\lor n\notin I}$.

Ainsi, dans la théorie des ensembles classique, où, par , les propositions de la définition sont décidables, l'appartenance à une sous-classe l'est aussi. Si l'ensemble n'est pas fini, "lister" successivement tous les nombres en sautant simplement ceux avec constitue classiquement une suite surjective croissante . Là, on peut obtenir une fonction bijective . De cette façon, la classe classique de fonctions est prouvablement riche, car elle contient également des objets qui sont au-delà de ce que nous savons être effectivement calculables , ou listables par programme dans la praxis. ${\displaystyle {\mathrm {LEM} }}$${\style d'affichage Q}$${\style d'affichage I}$${\displaystyle n\notin I}$${\displaystyle a:\omega \twoheadrightarrow I}$

En revanche, pour référence, en théorie de la calculabilité , les ensembles calculables sont des plages de fonctions totales non décroissantes (au sens récursif), au niveau de la hiérarchie arithmétique , et non plus. Décider d'un prédicat à ce niveau revient à résoudre la tâche de finalement trouver un certificat qui valide ou rejette l'adhésion. Comme tous les prédicats ne sont pas calculables, la théorie seule ne prétendra pas (prouver) que tous les infinis sont l'étendue d'une fonction bijective de domaine . ${\displaystyle \Sigma _{1}^{0}\cap \Pi _{1}^{0}=\Delta _{1}^{0}}$${\style d'affichage Q}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle I\sous-ensemble \omega }$${\displaystyle \omega }$

Être fini signifie qu'il y a une fonction bijective à un naturel. Être subfini signifie être un sous-ensemble d'un ensemble fini. L'affirmation selon laquelle être un ensemble fini équivaut à être subfini est équivalente à . ${\displaystyle {\mathrm {LEM} }}$

Mais étant compatible avec , le développement dans cette section permet aussi toujours d'interpréter "fonction sur " comme un objet pas nécessairement donné comme séquence de loi . Des applications peuvent être trouvées dans les modèles courants d'affirmations sur la probabilité, par exemple les déclarations impliquant la notion de « recevoir » une séquence aléatoire sans fin de lancers de pièces. ${\displaystyle {\mathsf {ZF}}}$${\displaystyle \omega }$

Choix

• Axiome du choix dénombrable : Si , on peut former l'ensemble de relations un-à-plusieurs . L'axiome du choix comptable accorderait que chaque fois que , on peut former une fonction mappant chaque nombre à une valeur unique. Le choix dénombrable peut également être encore affaibli, par exemple en restreignant les cardinalités possibles des ensembles dans la plage de , ou en restreignant la définition impliquée par rapport à leur place dans les hiérarchies syntaxiques.${\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 uu\in g(n)}$${\style d'affichage g}$

• Axiome du choix dépendant : Il est impliqué par l'axiome plus général du choix dépendant, extrayant une fonction de toute relation entière sur un ensemble habité. Le choix dénombrable s'apparente à un cas de thèse de l' Église constructive et, en effet, le choix dépendant est valable dans de nombreux modèles de réalisabilité et il est donc adopté dans de nombreuses écoles constructives.

• Choix dépendant relativisé : Le principe de choix dépendant relativisé le plus fort en est une variante - un schéma impliquant une variable de prédicat supplémentaire. En adoptant ceci pour les formules juste bornées dans , la théorie prouve déjà la - induction , discutée plus en détail ci-dessous.${\displaystyle {\mathsf {ECST}}}$${\displaystyle \Sigma _{1}^{0}}$

• Axiome de choix : L'axiome de choix concernant les fonctions sur des domaines généraux. Cela implique un choix dépendant.

Pour mettre en évidence la force du choix complet et sa relation avec les questions d' intentionnalité , il faut considérer les classes subfinies

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

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

Ici et sont aussi contingents que les prédicats impliqués dans leur définition. Supposons maintenant un contexte dans lequel ils sont établis pour être des ensembles, donc c'est aussi le cas. Ici, Axiom of Choice accorderait alors l'existence d'une carte avec des éléments distinguables. Cela implique maintenant en fait que . Ainsi, l'affirmation d'existence des fonctions de choix générales n'est pas constructive. Pour mieux comprendre ce phénomène, il faut considérer des cas d'implications logiques, tels que , et cetera. La différence entre le codomaine discret de certains nombres naturels et le domaine réside dans le fait qu'a priori on en sait peu sur ce dernier. C'est le cas que et , indépendamment de , éventuellement faire un candidat à une fonction de choix. Mais dans le cas de , comme l'implique la prouvabilité de , on a de sorte qu'il n'y ait par extension qu'une seule fonction possible entrée dans une fonction de choix de choix, maintenant avec juste , les fonctions de choix pourraient être ou . Ainsi, lors de l'examen de l'affectation fonctionnelle , une déclaration inconditionnelle ne serait pas cohérente. Le choix peut ne pas être adopté dans une théorie des ensembles par ailleurs forte, parce que la simple affirmation de l'existence d'une fonction ne réalise pas une fonction particulière. La compréhension de la sous-classe (utilisée pour séparer et de , c'est-à-dire les définir) lie les prédicats qui y sont impliqués pour définir l'égalité, de la manière décrite, et cela concerne les informations sur les fonctions. ${\style d'affichage x}$${\style d'affichage y}$${\style d'affichage \{x,y\}}$${\displaystyle f\colon \{x,y\}\to \{0,1\}}$${\style d'affichage f(z)\in z}$ ${\displaystyle P\lor \neg P}$${\style d'affichage P\implique x=y}$${\style d'affichage \{x,y\}}$${\style d'affichage 0\dans x}$${\style d'affichage 1\en y}$${\style d'affichage P}$${\displaystyle \{\langle x,0\rangle ,\langle y,1\rangle \}}$${\style d'affichage x=y}$${\style d'affichage P}$${\displaystyle \{x,y\}=\{x\}}$${\style d'affichage \{x\}\à \{0,1\}}$${\displaystyle \{\langle x,0\rangle \}}$${\displaystyle \{\langle x,1\rangle \}}$${\style d'affichage f(x)=0}$${\style d'affichage f(y)=1}$${\style d'affichage x}$${\style d'affichage y}$${\style d'affichage \{0,1\}}$

Le développement constructif se déroule souvent de manière agnostique par rapport aux principes de choix discutés.

Arithmétique

Les hypothèses nécessaires pour obtenir une théorie de l'arithmétique sont étudiées en profondeur dans la théorie de la preuve . Pour le contexte, voici un paragraphe sur les classifications qu'il contient : Les théories classiques commençant par l' arithmétique bornée adoptent différents schémas d'induction conservatrice et peuvent ajouter des symboles pour des fonctions particulières, conduisant à des théories entre l'arithmétique de Robinson et de Peano . La plupart de ces théories sont cependant relativement faibles en ce qui concerne la preuve de totalité pour certaines fonctions à croissance plus rapide . Certains des exemples les plus élémentaires incluent l'arithmétique des fonctions élémentaires , avec un ordinal théorique de la preuve (le moins bien ordonné récursif non prouvable ) de . a ordinal , ce qui signifie que la théorie permet d'encoder des ordinaux de théories plus faibles (dans ce sens d'analyse ordinale) (disons , en termes de théorie des ensembles) en tant que relation récursive sur les naturels uniquement, . Le schéma d'induction, comme par exemple impliqué par le choix dépendant relativisé, signifie l'induction pour ces sous-classes de naturels calculables via une recherche finie avec un temps d'exécution non lié (fini). Le schéma est également équivalent au schéma -induction. L'arithmétique classique du premier ordre relativement faible qui adopte ce schéma est notée . Le -induction est également adopté le système de base mathématique inverse classique du second ordre . Cette théorie du second ordre est -conservative sur l'arithmétique récursive primitive , prouve donc que toutes les fonctions récursives primitives sont totales. Ces dernières théories arithmétiques mentionnées ont toutes ordinal . L'arithmétique d'ordre supérieur mentionnée est un point de référence pertinent dans cette discussion dans la mesure où son langage n'exprime pas simplement des ensembles arithmétiques , alors que tous les ensembles de naturels dont la théorie prouve l'existence ne sont que des ensembles calculables . ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {EFA}}}$${\displaystyle \omega ^{3}}$${\displaystyle {\mathsf {PA}}}$${\displaystyle \varepsilon _{0}}$${\displaystyle \langle \omega ^{3},\in \rangle }$${\displaystyle \langle \omega ,E\rangle }$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle {\mathsf {I\Sigma }}_{1}}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle {\mathsf {RCA}}_{0}}$${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle {\mathsf {PRA}}}$${\displaystyle \omega ^{\omega }}$

Cela dit, la théorie des ensembles n'interprète même pas la récursivité primitive complète. En effet, malgré l'axiome de remplacement, la théorie ne prouve pas que la fonction d'addition est une fonction ensembliste. D'un autre côté, de nombreuses déclarations peuvent être prouvées par ensemble individuel dans cette théorie (par opposition aux expressions impliquant un quantificateur universel, comme par exemple disponibles avec un principe d'induction) et des objets d'intérêt mathématique peuvent être utilisés au niveau de la classe sur un base individuelle. En tant que tels, les axiomes énumérés jusqu'à présent suffisent comme théorie de travail de base pour une bonne partie des mathématiques de base. Au-delà de l'arithmétique, l'axiome accordant la définition des fonctions ensemblistes via les fonctions ensemblistes par étapes d'itération doit être ajouté. Ce qui est nécessaire, c'est l'équivalent théorique d'un objet de nombres naturels . Cela permet alors une interprétation de l' arithmétique de Heyting , . Avec cela, l'arithmétique des nombres rationnels peut alors également être définie et ses propriétés, comme l'unicité et la dénombrement, être prouvées. Une théorie des ensembles avec cela prouvera également que, pour tout naturel et , les espaces de fonctions ${\displaystyle {\mathsf {ECST}}}$${\displaystyle {\mathsf {ECST}}}$${\displaystyle {\mathsf {HA}}}$${\displaystyle {\mathbb {Q} }}$${\style d'affichage n}$${\style d'affichage m}$

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

sont des ensembles.

Inversement, une preuve du principe d'itération recherché peut être basée sur la collection de fonctions sous laquelle on voudrait écrire et l'existence de ceci est impliquée en supposant que les espaces de fonctions individuelles sur des domaines finis en ensembles forment des ensembles eux-mêmes. Cette remarque devrait motiver l'adoption d'un axiome de saveur théorique plus définie, au lieu d'intégrer directement des principes arithmétiques dans notre théorie. Le principe d'itération obtenu par l'axiome théorique suivant, plus défini, ne prouvera cependant toujours pas le schéma d' induction mathématique complet . ${\displaystyle \cup _{n\in \omega }y^{\{0,1,\dots ,n-1\}}}$${\style d'affichage y}$

Exponentiation

Une forme affaiblie du schéma de séparation a déjà été adoptée, et plusieurs des axiomes standard seront affaiblis pour une théorie plus prédicative et constructive. Le premier d'entre eux est l' axiome Powerset , qui, en fait, a été adopté pour les sous-ensembles décidables de la théorie. ${\displaystyle {\mathsf {ZF}}}$

La caractérisation de la classe de tous les sous-ensembles d'un ensemble implique une quantification universelle illimitée, à savoir . Ici a été défini en termes de prédicat d'appartenance ci-dessus. La déclaration elle - même est . Ainsi, dans un cadre mathématique de théorie des ensembles, la classe de puissance est définie non pas dans une construction ascendante à partir de ses constituants (comme un algorithme sur une liste, qui par exemple mappe ) mais via une compréhension sur tous les ensembles. ${\displaystyle {\mathcal {P}}x}$${\style d'affichage x}$${\displaystyle \forall uu\subset x\iff u\in {\mathcal {P}}x}$${\displaystyle \subset }$${\style d'affichage \in }$${\displaystyle y={\mathcal {P}}x}$${\style d'affichage \Pi _{1}}$${\displaystyle \langle a,b\rangle \mapsto \langle \langle \rangle ,\langle a\rangle ,\langle b\rangle ,\langle a,b\rangle \rangle }$

La richesse de la powerclass dans une théorie sans tiers exclu peut être mieux comprise en considérant de petits ensembles classiquement finis. Pour toute formule , la classe est égale à 0 lorsqu'elle peut être rejetée et 1 lorsqu'elle peut être prouvée, mais peut également ne pas être décidable du tout. Dans cette vue, la powerclass du singleton , c'est-à-dire la classe , ou de manière suggestive " ", et généralement désignée par , est appelée l'algèbre des valeurs de vérité. Les fonctions -valuées sur un ensemble s'injectent dans et correspondent ainsi à ses sous-ensembles décidables. ${\style d'affichage P}$${\displaystyle \{x\mid (x=0)\land P\}}$${\style d'affichage P}$${\style d'affichage P}$${\style d'affichage P}$${\style d'affichage \{0\}=1}$${\displaystyle {\mathcal {P}}1}$${\displaystyle \{0,\dots ,1\}}$${\style d'affichage \Oméga }$${\style d'affichage \{0,1\}}$${\style d'affichage x}$${\displaystyle \Omega ^{x}}$

Considérons maintenant l'axiome . ${\displaystyle {\mathrm {Exp} }}$

Exponentiation ${\displaystyle \forall x.\forall y.\ \ \exists hh=y^{x}}$

La formulation utilise ici la notation commode pour les espaces de fonctions. Sinon, l'axiome est plus long, impliquant un quantificateur borné par et le prédicat de la fonction totale. En mots, l'axiome dit qu'étant donné deux ensembles , la classe de toutes les fonctions est, en fait, aussi un ensemble. Ceci est certainement nécessaire, par exemple, pour formaliser la carte d'objets d'un hom-foncteur interne comme . L'utilisation des axiomes d'exponentiation découle du fait que les espaces de fonctions étant des ensembles, la quantification de leurs fonctions est une notion limitée, permettant l'utilisation de la séparation. Cela a des implications notables : l'adopter signifie que la quantification sur les éléments de certaines classes de fonctions devient une notion bornée, même lorsque les espaces de fonctions sont même classiquement indénombrables . Par exemple, la collection de toutes les fonctions , c'est-à-dire l'ensemble des points sous-jacents à l' espace de Cantor , est indénombrable, par l'argument diagonal de Cantor , et peut au mieux être considérée comme sous- dénombrable . (Dans cette section, nous commençons à utiliser le symbole pour le semi-anneau des nombres naturels dans des expressions comme ou écrire juste pour éviter la confusion du cardinal avec l'exponentiation ordinale.) ${\style d'affichage x\fois y}$${\style d'affichage x,y}$${\style d'affichage y^{x}}$${\displaystyle {\mathrm {hom} }({\mathbb {N} },-)}$${\displaystyle \forall f}$${\displaystyle f\colon \omega \to \{0,1\}}$${\displaystyle \{0,1\}^{\mathbb {N} }}$${\displaystyle y^{\mathbb {N} }}$${\displaystyle \omega \to y}$

La théorie des ensembles avec Exponentiation prouve maintenant aussi l'existence de toute fonction récursive primitive sur les naturels , en tant que fonctions ensemblistes dans l'ensemble . De même, obtenez le nombre ordinal exponentiel , qui peut être caractérisé par . D'une manière plus générale, l'exponentiation prouve que l'union de toutes les séquences finies sur un ensemble dénombrable est un ensemble dénombrable. Et en effet, les unions des plages de toute famille dénombrable de fonctions de comptage sont dénombrables. ${\displaystyle \omega }$${\displaystyle \omega \to \omega }$${\displaystyle \omega ^{\omega }}$${\displaystyle \bigcup _{n\in \omega }\omega ^{n}}$

En ce qui concerne la compréhension, la théorie prouve maintenant que la collection de tous les sous-ensembles dénombrables d'un ensemble (la collection est une sous-classe de la powerclass) est un ensemble. Le principe du pigeonnier peut également être prouvé.

Revenant à la considération de classe de puissance d'origine : en supposant que toutes les formules sont décidables, c'est-à-dire en supposant que , on peut montrer non seulement que cela devient un ensemble, mais plus concrètement qu'il s'agit de cet ensemble à deux éléments. En supposant des formules bornées, Separation permet de démontrer que toute powerclass est un ensemble. Alternativement, full Powerset équivaut simplement à supposer que la classe de tous les sous-ensembles de forme un ensemble. La séparation complète équivaut à supposer que chaque sous-classe individuelle de est un ensemble. ${\displaystyle {\mathrm {LEM} }}$${\style d'affichage \Oméga }$${\displaystyle {\mathrm {LEM} }}$${\style d'affichage 1}$${\style d'affichage 1}$

Notions théoriques des catégories et des types

Ainsi dans ce contexte avec Exponentiation, les espaces de fonctions sont plus accessibles que les classes de sous-ensembles, comme c'est le cas avec les objets exponentiels resp. sous-objets dans la théorie des catégories. En termes théoriques de catégorie , la théorie correspond essentiellement à des pré- topos de Heyting fermés cartésiens constructifs bien pointés avec (chaque fois que l'infini est adopté) un objet de nombres naturels . L'existence d'un ensemble de pouvoirs est ce qui transformerait un prétopos de Heyting en un topos élémentaire . Chacun de ces topos qui interprète est bien sûr un modèle de ces théories plus faibles, mais localement des prétopos fermés cartésiens ont été définis qui, par exemple, interprètent les théories avec l'exponentiation mais rejettent la séparation complète et l'ensemble de puissance. ${\displaystyle {\mathsf {BCST}}+{\mathrm {Exp} }}$ ${\displaystyle {\mathsf {ZF}}}$

En théorie des types, l'expression " " existe par elle-même et désigne des espaces de fonctions , une notion primitive. Ces types (ou, en théorie des ensembles, classes ou ensembles) apparaissent naturellement, par exemple, comme le type de la bijection currying entre et , une adjonction . Une théorie des types typique avec une capacité de programmation générale - et certainement celles qui peuvent modéliser , ce qui est considéré comme une théorie des ensembles constructive - aura un type d'entiers et d'espaces fonctionnels représentant , et en tant que tel inclura également des types qui ne sont pas dénombrables. Cela implique et signifie simplement que parmi les termes de fonction , aucun n'a la propriété d'être une bijection. ${\style d'affichage x\à y}$${\style d'affichage (z\fois x)\à y}$${\displaystyle z\à y^{x}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathbb {Z} }\à {\mathbb {Z} }}$${\displaystyle f\colon {\mathbb {Z} }\to ({\mathbb {Z} }\to {\mathbb {Z} })}$

Les théories constructives des ensembles sont également étudiées dans le contexte des axiomes applicatifs .

Une analyse

Dans cette section s'élabore la force de . Pour le contexte, d'autres principes possibles sont mentionnés, qui ne sont pas nécessairement classiques et qui ne sont pas non plus généralement considérés comme constructifs. Ici, un avertissement général s'impose : lors de la lecture des affirmations d'équivalence de proposition dans le contexte calculable, on doit toujours être conscient des principes de choix , d' induction et de compréhension qui sont implicitement supposés. Voir aussi l' analyse constructive et l' analyse calculable connexes . ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$

Vers les réels

L'exponentiation implique des principes de récursivité et donc dans , on peut raisonner sur des séquences ou sur des intervalles rétrécis dans et cela permet aussi de parler de séquences de Cauchy et de leur arithmétique. Tout nombre réel de Cauchy est une collection de séquences, c'est-à-dire un sous-ensemble d'un ensemble de fonctions sur . Plus d'axiomes sont nécessaires pour toujours garantir l' exhaustivité des classes d'équivalence de telles séquences et des principes forts doivent être postulés pour impliquer l'existence d'un module de convergence pour toutes les séquences de Cauchy. Le choix dénombrable faible est généralement le contexte pour prouver l' unicité des réels de Cauchy en tant que champ (pseudo-)ordonné complet. « Pseudo- » souligne ici que l'ordre ne sera, de toute façon, constructivement pas toujours décidable. ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$${\displaystyle \omega \to {\mathbb {Q} }}$${\displaystyle \omega \to ({\mathbb {Q} }\times {\mathbb {Q} })}$${\displaystyle \omega }$

Comme dans la théorie classique, les coupes de Dedekind sont caractérisées à l'aide de sous-ensembles de structures algébriques telles que : structure. Un exemple standard de coupe, le premier composant présentant bien ces propriétés, est la représentation de donnée par ${\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} }}}$

(Selon la convention pour les coupes, l'une ou l'autre des deux parties ou aucune, comme ici, peut utiliser le signe .) ${\style d'affichage \leq }$

La théorie donnée par les axiomes valide jusqu'à présent qu'un champ pseudo- ordonné qui est également complet d' Archimède et de Dedekind , s'il existe, est ainsi caractérisé de manière unique, à isomorphisme près. Cependant, l'existence d'espaces fonctionnels tels que ne permet pas d'être un ensemble, et donc la classe de tous les sous-ensembles de ceux-ci ne remplit pas les propriétés nommées. Ce qui est requis pour que la classe des réels de Dedekind soit un ensemble est un axiome concernant l'existence d'un ensemble de sous-ensembles. ${\displaystyle \{0,1\}^{\mathbb {Q} }}$${\displaystyle {{\mathcal {P}}{\mathbb {Q} }}}$${\displaystyle {\mathbb {Q} }}$

Dans les deux cas, moins d'énoncés sur l'arithmétique des réels sont décidables , par rapport à la théorie classique.

Écoles constructives

Les revendications non constructives valables dans l'étude de l' analyse constructive sont communément formulées comme concernant toutes les séquences binaires, c'est-à-dire les fonctions . C'est-à-dire des sinistres quantifiés par . ${\displaystyle f\colon \omega \to \{0,1\}}$${\displaystyle \forall (f\in \{0,1\}^{\mathbb {N} })}$

Un exemple le plus frappant est le principe limité d'omniscience , postulant une propriété disjonctive, comme au niveau des phrases ou des fonctions. (Les exemples de fonctions peuvent être construits en brut de telle sorte que, si elles sont cohérentes, les disjonctions concurrentes ne peuvent pas être prouvées.) Le principe est indépendant de, par exemple, présenté ci-dessous. Dans cette théorie des ensembles constructifs, implique sa version "inférieure", notée , une variante restreinte de la loi de De Morgan . Il implique en outre le principe de Markov , une forme de preuve par contradiction et la -version du théorème du ventilateur . La mention de tels principes valables pour les -phrases fait généralement allusion à des formulations équivalentes en termes de séquences, décidant de la séparation des réels. Dans un contexte d'analyse constructive avec choix dénombrable, est par exemple équivalent à l'affirmation que chaque réel est soit rationnel soit irrationnel - encore une fois sans qu'il soit nécessaire de témoigner de l'un ou l'autre disjoint. ${\displaystyle {\mathrm {LPO} }}$${\displaystyle {\mathrm {LEM} }}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle {\mathsf {PA}}}$${\displaystyle {\mathsf {PA}}}$${\displaystyle {\mathsf {PA}}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathrm {LPO} }}$${\displaystyle {\mathrm {LLPO} }}$ ${\displaystyle {\mathrm {MP} }}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle {\mathrm {LPO} }}$

Ainsi, pour certaines propositions employées dans les théories de l'analyse constructive qui ne sont pas prouvables en utilisant uniquement la logique intuitionniste de base, voir ou même la thèse constructive non classique de Church ou certaines de ses conséquences du côté des mathématiques récursives ( ou ), ainsi que le schéma de Kripke (tournant toutes les sous-classes de dénombrable), l' induction bar , le théorème de l'éventail décidable ou encore le principe de continuité non classique déterminant des fonctions sur des suites infinies à travers des segments initiaux finis du côté intuitionniste brouwerien ( ). Les deux écoles se contredisent , de sorte que le choix d'adopter de telles lois rend la théorie incompatible avec les théorèmes de l'analyse classique. ${\displaystyle {\mathrm {MP} }}$ ${\displaystyle {\mathrm {CT} }}$${\displaystyle {\mathsf {RUSS}}}$${\displaystyle {\mathsf {CRM}}}$${\displaystyle \omega }$${\displaystyle {\mathrm {FAN} }_{\Delta }}$ ${\displaystyle {\mathsf {INT}}}$${\displaystyle {\mathrm {LPO} }}$

Arbres infinis

À travers la relation entre la calculabilité et la hiérarchie arithmétique, les idées de cette étude classique sont également révélatrices pour des considérations constructives. Un aperçu de base des mathématiques inversées concerne les arbres binaires calculables infinis à ramifications finies. Un tel arbre peut par exemple être codé comme un ensemble infini d'ensembles finis

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

avec une appartenance décidable, et ces arbres contiennent alors de manière prouvable des éléments de grande taille finie arbitraire. Le lemme de Kőnigs faible énonce : Pour un tel , il existe toujours un chemin infini dans , c'est- à -dire une suite infinie telle que tous ses segments initiaux font partie de l'arbre. En mathématiques inversées, l'arithmétique du second ordre ne prouve pas . Pour comprendre cela, notez qu'il existe des arbres calculables pour lesquels aucun chemin calculable n'existe. Pour le prouver, on énumère les séquences calculables partielles puis diagonalise toutes les séquences calculables totales en une séquences calculables partielles . On peut alors dérouler un certain arbre , un exactement compatible avec les valeurs encore possibles de partout, qui par construction est incompatible avec tout chemin calculable global. ${\displaystyle {\mathrm {WKL} }}$${\style d'affichage T}$${\displaystyle \omega \to \{0,1\}}$${\displaystyle {\mathsf {RCA}}_{0}}$${\displaystyle {\mathrm {WKL} }}$${\style d'affichage K}$${\style d'affichage d}$${\style d'affichage K}$${\style d'affichage d}$

Dans , le principe implique le principe limité non constructif d'omniscience . Dans un contexte plus conservateur, ils sont équivalents en supposant - (un choix comptable très faible). Il est également équivalent au théorème du point fixe de Brouwer et à d'autres théorèmes concernant les valeurs des fonctions continues sur les réels. Le théorème du point fixe implique à son tour le théorème des valeurs intermédiaires , mais sachez que les théorèmes classiques peuvent se traduire par différentes variantes lorsqu'ils sont exprimés dans un contexte constructif. ${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathrm {WKL} }}$ ${\displaystyle {\mathrm {LLPO} }}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle {\mathrm {AC} }_{\omega ,2}}$

Le concerne des graphes infinis et donc sa contraposée donne une condition de finitude. Par rapport à la théorie arithmétique classique , cela donne une équivalence à la compacité de Borel en ce qui concerne les sous-couvertures finies de l'intervalle unitaire réel. Une affirmation d'existence étroitement liée impliquant des séquences finies dans un contexte infini est le théorème du ventilateur décidable . Sur le , ils sont en fait équivalents. Dans , ceux-ci sont distincts, mais encore une fois en supposant un certain choix, cela implique . ${\displaystyle {\mathrm {WKL} }}$${\displaystyle {\mathsf {RCA}}_{0}}$${\displaystyle {\mathrm {FAN} }_{\Delta }}$${\displaystyle {\mathsf {RCA}}_{0}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathrm {WKL} }}$${\displaystyle {\mathrm {FAN} }_{\Delta }}$

Restreindre les espaces fonctionnels

Dans la remarque suivante, la fonction et les affirmations formulées à leur sujet sont à nouveau comprises dans le sens de la théorie de la calculabilité. L' opérateur μ active toutes les fonctions récursives générales partielles (ou programmes, au sens où ils sont calculables de Turing), y compris celles par exemple non primitives mais -totales, comme la fonction d'Ackermann . La définition de l'opérateur implique des prédicats sur les naturels et donc l'analyse théorique des fonctions et de leur totalité dépend du cadre formel à portée de main. Quoi qu'il en soit, ces nombres naturels qui sont, dans la théorie de la calculabilité, considérés comme des indices pour les fonctions calculables qui sont totales, sont , dans la hiérarchie arithmétique . C'est-à-dire que c'est toujours une sous-classe des naturels. Et là, la totalité, en tant que prédicat sur tous les programmes, est notoirement indécidable par calcul . ${\displaystyle {\mathrm {PA} }}$${\displaystyle \Pi _{2}^{0}}$

La thèse d'une Église constructive non classique , selon l'hypothèse de son antécédent, concerne les définitions de prédicats (et donc ici les fonctions définies) qui sont manifestement totales et elle postule qu'elles correspondent à des programmes calculables. L'adoption du postulat en fait un ensemble « clairsemé », tel qu'il est vu de la théorie des ensembles classique. Voir sous- comptabilité . ${\displaystyle {\mathrm {CT} }}$${\displaystyle \omega \to \omega }$

Le postulat est encore une arithmétique intuitionniste cohérente ou un choix. Mais il contredit les principes classiquement valides tels que et , qui sont parmi les principes les plus faibles souvent discutés. ${\displaystyle {\mathrm {CT} }}$${\displaystyle {\mathrm {LLPO} }}$${\displaystyle {\mathrm {FAN} }_{\Delta }}$

Induction

Induction mathematique

Dans les sections précédentes, la séparation bornée établissait déjà la validité de l'induction pour les définitions bornées. Dans le langage des ensembles, les principes d'induction peuvent se lire avec l' antécédent défini comme ci-dessus. Il est instructif d'observer qu'une proposition dans le conséquent , comme , ici exprimée en utilisant la notation de classe impliquant une sous-classe qui peut ne pas constituer un ensemble - ce qui signifie que de nombreux axiomes ne s'appliqueront pas - et le simple ne sont que deux façons de formuler la même affirmation souhaitée (un -conjonction indexée de revendications ici, en particulier.) Ainsi, un cadre théorique défini avec une séparation juste bornée peut être renforcé par des schémas d'induction arithmétique pour des prédicats non bornés. ${\displaystyle \mathrm {Ind} (A)\implies \omega \subset A}$ ${\displaystyle \mathrm {Ind} (A)}$${\displaystyle \omega \subset \{n\in \omega \mid y^{\{0,1,\dots ,n-1\}}{\text{ est un ensemble}}\}}$${\displaystyle \forall (n\in \omega ).y^{\{0,1,\dots ,n-1\}}{\text{ est un ensemble}}}$${\style d'affichage n}$

Le principe d'itération pour les fonctions d'ensemble mentionné précédemment est, alternativement à l'exponentiation, également impliqué par le schéma d'induction complet sur sa structure modélisant les naturels (par exemple ). C'est aussi le principe arithmétique du premier ordre pour prouver plus de fonctions au total que ne le fait. Il est souvent formulé directement en termes de prédicats, comme suit. Considérez le schéma - : ${\displaystyle \omega }$${\displaystyle {\mathsf {PRA}}}$${\displaystyle \omega }$${\displaystyle {\mathrm {Ind} }}$

Schéma d'axiome d' induction mathématique complète : Pour tout prédicat sur , ${\style d'affichage \phi }$${\displaystyle \omega }$ ${\displaystyle {\Big (}\phi (0)\ \land \ \forall (k\in \omega ).{\big (}\phi (k)\implies \phi (Sk){\big )}{ \Big )}\implies \forall (n\in \omega ).\phi (n)}$

Ici, le 0 désigne comme ci-dessus, et l'ensemble désigne l'ensemble successeur de , avec . Par Axiom of Infinity ci-dessus, il est à nouveau membre de . ${\style d'affichage \{\}}$${\displaystyle Sn}$${\displaystyle n\in \omega }$${\style d'affichage n\dans Sn}$${\displaystyle \omega }$

Comme indiqué dans la section sur le choix, les principes d'induction sont également impliqués par diverses formes de principes de choix. Le schéma d'induction complet est impliqué par le schéma de séparation complet.

Pour prouver l'existence d'une fermeture transitive pour chaque ensemble par rapport à , au moins un schéma d'itération borné est nécessaire. Il convient de noter que dans le programme d'arithmétique prédicative, le schéma d'induction mathématique complet a été critiqué comme étant peut-être imprédicatif , lorsque les nombres naturels sont définis comme l'objet qui remplit ce schéma. ${\style d'affichage \in }$

Définir l'induction

L'induction d'ensemble complet prouve l'induction mathématique complète sur les nombres naturels. En effet, il donne l'induction sur les ordinaux et l'arithmétique ordinale. Le remplacement n'est pas nécessaire pour prouver l'induction sur l'ensemble des naturels, mais c'est pour leur arithmétique modélisée dans la théorie des ensembles. ${\displaystyle {\mathsf {ECST}}}$

L'axiome le plus fort - se lit alors comme suit : ${\style d'affichage \in }$${\displaystyle {\mathrm {Ind} }}$

Schéma axiome de l'induction ensembliste : Pour tout prédicat , ${\style d'affichage \phi }$ ${\displaystyle {\Big (}\forall s.\,{\big (}\forall (x\in s).\ \phi (x){\big )}\implies \phi (s){\Big ) }\implique \forall y.\phi (y)}$

Ici tient trivialement et correspond au « cas inférieur » dans le cadre standard. La variante de l'Axiome uniquement pour les formules bornées est également étudiée indépendamment et peut être dérivée d'autres axiomes. ${\displaystyle \forall x\in \{\}.\phi (x)}$

L'axiome permet des définitions de fonctions de classe par récursion transfinie . L'étude des divers principes qui accordent des définitions d'ensembles par induction, c'est-à-dire des définitions inductives, est un sujet principal dans le contexte de la théorie constructive des ensembles et de leurs forces comparativement faibles . Cela vaut également pour leurs homologues de la théorie des types.

L' axiome de Régularité ainsi délimitée séparation / implique Set induction sans bornes , mais aussi borné / non borné , donc Régularité est non constructive. Inversement, avec Set Induction, cela implique la régularité. ${\displaystyle {\mathrm {LEM} }}$${\displaystyle {\mathrm {LEM} }}$

Métalologique

Cela couvre maintenant les variantes de tous les huit axiomes de Zermelo-Fraenkel . L'extensionnalité, l'appariement, l'union et le remplacement sont en effet identiques. L'infini est énoncé dans une formulation forte et implique Emty Set, comme dans le cas classique. La séparation, classiquement énoncée de manière redondante, n'est pas implicitement implicite par le remplacement. Sans la loi du milieu exclu , la théorie manque ici, dans sa forme classique, de séparation complète, d'ensemble de puissance ainsi que de régularité.

La théorie ne dépasse pas la force de cohérence de l' arithmétique de Heyting, mais l'ajout à ce stade conduirait à une théorie au-delà de la force de la théorie des types typique : en supposant une séparation sous une forme non restreinte, puis en ajoutant à donne une théorie prouvant les mêmes théorèmes que la régularité moins ! Ainsi, l'ajout de Séparation et de Régularité à ce cadre donne plein et l'ajout de Choix lui donne . ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$${\displaystyle {\mathrm {LEM} }}$${\displaystyle {\mathrm {LEM} }}$${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {ZFC}}}$

La force de preuve-théorique ajoutée atteinte avec Induction dans le contexte constructif est significative, même si l'abandon de Régularité dans le contexte de ne réduit pas la force de preuve-théorique. Aczel fut aussi l'un des principaux développeurs de la théorie des ensembles non fondée , qui rejette ce dernier axiome. ${\displaystyle {\mathsf {ZF}}}$

Collection forte

Avec tous les axiomes affaiblis et maintenant au-delà de ces axiomes également observés dans l'approche typée de Myhill, considérons la théorie avec Exponentiation désormais renforcée par le schéma de collection . Il s'agit d'une propriété des relations, donnant lieu à un format quelque peu répétitif dans sa formulation du premier ordre. ${\displaystyle {\mathsf {ZF}}}$

Schéma axiome de Strong Collection : Pour tout prédicat , ${\style d'affichage \phi }$ ${\displaystyle \forall a.\ \ {\Big (}\forall (x\in a).\exists y.\phi (x,y){\Big )}\implies \exists b.{\Big (} \forall (x\in a).\existe (y\in b).\phi (x,y)\ \land \ \forall (y\in b).\existe (x\in a).\phi ( x,y){\Grand )}}$

Il indique que si est une relation entre les ensembles qui est totale sur un certain ensemble de domaine (c'est-à-dire qu'il a au moins une valeur d'image pour chaque élément du domaine), alors il existe un ensemble qui contient au moins une image sous de chaque élément du domaine. Et cette formulation indique ensuite que seules de telles images sont des éléments de cet ensemble de codomaines. La dernière clause rend l'axiome - dans ce contexte constructif - plus fort que la formulation standard de Collection. Il garantit que ne dépasse pas le codomaine de et donc l'axiome exprime une certaine puissance d'une procédure de séparation. ${\style d'affichage \phi }$${\style d'affichage a}$${\style d'affichage b}$${\style d'affichage \phi }$${\style d'affichage b}$${\style d'affichage \phi }$

L'axiome est une alternative au schéma de remplacement et le remplace en effet, car il n'exige pas que la définition de la relation binaire soit fonctionnelle.

En règle générale, les questions de cardinalité modérée sont plus subtiles dans un cadre constructif. Comme l'arithmétique est bien disponible ici, la théorie a des produits dépendants, prouve que la classe de tous les sous-ensembles de nombres naturels ne peut pas être sous- dénombrable et prouve également que les unions dénombrables d'espaces fonctionnels d'ensembles dénombrables restent dénombrables.

Métalologique

Cette théorie sans séparation illimitée et ensemble de puissance "naïf" bénéficie de diverses propriétés intéressantes. Par exemple, il a la propriété d'existence : Si, pour toute propriété , la théorie prouve qu'un ensemble existe qui a cette propriété, c'est-à-dire si la théorie prouve l'énoncé , alors il y a aussi une propriété qui décrit de manière unique une telle instance d'ensemble. C'est-à-dire que la théorie prouve alors aussi . Cela peut être comparé à l'arithmétique de Heyting où les théorèmes sont réalisés par des nombres naturels concrets et ont ces propriétés. En théorie des ensembles, le rôle est joué par des ensembles définis. Par contraste, rappelez-vous que dans , l'Axiome du choix implique le théorème du bon ordre , de sorte que les ordres totaux avec le moins d'élément pour des sous-ensembles d'ensembles comme sont formellement prouvés, même si un tel ordre ne peut être décrit. ${\displaystyle {\mathrm {LEM} }}$${\style d'affichage \Phi }$${\displaystyle \exists x.\Phi (x)}$${\style d'affichage \Psi }$${\displaystyle \exists !x.\Psi (x)\land \Phi (x)}$${\displaystyle {\mathsf {ZFC}}}$${\displaystyle \mathbb {R} }$

Zermelo–Fraenkel constructif

On peut approcher le Power set plus loin sans perdre une interprétation théorique type. La théorie dite est constituée des axiomes ci-dessus et d'une forme plus forte d'exponentiation. C'est en adoptant l'alternative suivante, qui peut encore être vue comme une version constructive de l' axiome des ensembles de puissance : ${\displaystyle {\mathsf {CZF}}}$

Schéma axiome de la collection de sous-ensembles : pour tout prédicat , ${\style d'affichage \phi }$ ${\displaystyle \forall a.\forall b.\ \ \existe u.\forall z.{\big (}\forall (x\in a).\existe (y\in b).\phi (x,y ,z){\big )}\implies \exists (v\in u).{\big (}\forall (x\in a).\exists (y\in v).\phi (x,y,z )\;\land \;\forall (y\in v).\existe (x\in a).\phi (x,y,z){\big )}}$

Ce schéma d'axiome de collection de sous-ensembles est équivalent à un axiome alternatif de plénitude unique et quelque peu plus clair. À cette fin, soit la classe de toutes les relations totales entre a et b , cette classe est donnée par ${\displaystyle a\Sigma {b}}$

${\displaystyle r\in a\Sigma {b}\iff {\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 { \gros )}}$

Avec cela, state , une alternative à Subset Collection. Il garantit qu'il existe au moins un ensemble contenant une bonne quantité des relations souhaitées. Plus concrètement, entre deux ensembles quelconques et , il existe un ensemble qui contient une sous-relation totale pour toute relation totale de à . ${\displaystyle {\mathrm {Plénitude} }}$${\displaystyle c\sous-ensemble a\Sigma {b}}$${\style d'affichage a}$${\style d'affichage b}$${\style d'affichage c}$${\style d'affichage s}$${\style d'affichage r}$${\style d'affichage a}$${\style d'affichage b}$

Axiome de plénitude :

${\displaystyle \forall a.\forall b.\ \ \exists (c\subset a\Sigma {b}).\forall (r\in a\Sigma {b}).\existe (s\in c). s\sous-ensemble r}$

L'axiome de plénitude est à son tour impliqué par ce qu'on appelle l' axiome de présentation sur les sections, qui peut également être formulé en catégorie théorique .

La plénitude implique la propriété de raffinement binaire nécessaire pour prouver que la classe des coupes de Dedekind est un ensemble. Cela ne nécessite pas d'induction ou de collecte.

Ni la linéarité des ordinaux , ni l'existence d'ensembles de puissance d'ensembles finis ne sont dérivables dans cette théorie. En supposant que l'un ou l'autre implique un pouvoir défini dans ce contexte.

Métalologique

Cette théorie n'a pas la propriété d'existence due au schéma, mais en 1977, Aczel a montré que cela peut encore être interprété dans la théorie des types de Martin-Löf (en utilisant l' approche des propositions en tant que types ) fournissant ce qui est maintenant considéré comme un modèle standard de la théorie des types . Cela se fait en termes d'images de ses fonctions ainsi que d'une justification constructive et prédicative assez directe, tout en conservant le langage de la théorie des ensembles. Ce modèle sous- comptable valide de nombreux principes de choix . Avec un modèle théorique de type, a une force théorique de preuve modeste, voir : Bachmann-Howard ordinal . ${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {IKP}}}$

NB : Rupture avec ZF

On peut en outre ajouter l'affirmation non classique selon laquelle tous les ensembles sont sous- comptables en tant qu'axiome. Alors est un ensemble (par Infinity et Exponentiation) alors que la classe ou même n'est manifestement pas un ensemble, par l'argument diagonal de Cantor . Cette théorie rejette donc logiquement Powerset et . ${\displaystyle \omega \to \omega }$${\displaystyle {\mathcal {P}}\omega }$${\displaystyle {\mathcal {P}}\{0\}}$${\displaystyle {\mathrm {LEM} }}$

En 1989, Ingrid Lindström a montré que les ensembles non fondés obtenus en remplaçant l'équivalent de l' Axiome de Fondation (Induction) dans par l' axiome d'anti-fondation d'Aczel ( ) peuvent également être interprétés dans la théorie des types de Martin-Löf. ${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZFA}}}$

Zermelo–Fraenkel intuitif

La théorie est avec l'ensemble Séparation et Puissance standard . ${\displaystyle {\mathsf {IZF}}}$${\displaystyle {\mathsf {CZF}}}$

Ici, à la place du schéma de remplacement Axiom , on peut utiliser le

Schéma axiome de collection : Pour tout prédicat , ${\style d'affichage \phi }$ ${\displaystyle \forall z.{\big (}\forall (x\in z).\exists y.\phi (x,y){\big )}\implies \exists w.\forall (x\in z ).\existe (y\in w).\phi (x,y)}$

Alors que l'axiome de remplacement exige que la relation soit fonctionnelle sur l'ensemble (comme dans, pour chaque in il est associé exactement un ), l'axiome de collection ne le fait pas. Il exige simplement qu'il y soit associé au moins un , et il affirme l'existence d'un ensemble qui recueille au moins un tel pour chaque tel . avec la Collection implique le Remplacement. ${\style d'affichage \phi }$${\style d'affichage z}$${\style d'affichage x}$${\style d'affichage z}$${\style d'affichage y}$${\style d'affichage y}$${\style d'affichage y}$${\style d'affichage x}$${\displaystyle {\mathrm {LEM} }}$

En tant que tel, peut être considéré comme la variante la plus simple de sans . ${\displaystyle {\mathsf {IZF}}}$${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathrm {LEM} }}$

La théorie est cohérente avec le fait d' être sous- dénombrable ainsi qu'avec la thèse de Church pour les fonctions théoriques des nombres. Mais, comme indiqué ci-dessus, la propriété de sous-comptabilité ne peut pas être adoptée pour tous les ensembles, étant donné que la théorie s'avère être un ensemble. ${\displaystyle \omega \to \omega }$${\displaystyle {\mathcal {P}}\omega }$

Métalologique

En changeant le schéma Axiome de remplacement en schéma Axiome de collection, la théorie résultante a la propriété d'existence numérique .

Même sans , la force théorique de preuve de est égale à celle de . ${\displaystyle {\mathrm {LEM} }}$${\displaystyle {\mathsf {IZF}}}$${\displaystyle {\mathsf {ZF}}}$

Bien qu'il soit basé sur une logique intuitionniste plutôt que classique, il est considéré comme imprédicatif . Il permet la formation d'ensembles en utilisant l' Axiome de Séparation avec n'importe quelle proposition, y compris celles qui contiennent des quantificateurs qui ne sont pas bornés. Ainsi de nouveaux ensembles peuvent être formés en fonction de l'univers de tous les ensembles. De plus, l'axiome des ensembles de puissance implique l'existence d'un ensemble de valeurs de vérité . En présence de tiers exclu, cet ensemble existe et comporte deux éléments. En l'absence de celui-ci, l'ensemble des valeurs de vérité est également considéré comme imprédicatif. ${\displaystyle {\mathsf {ZF}}}$

Histoire

En 1973, John Myhill a proposé un système de théorie des ensembles basé sur la logique intuitionniste prenant le fondement le plus commun, , et rejetant l' Axiome du choix et la loi du tiers exclu , laissant tout le reste tel quel. Cependant, différentes formes de certains des axiomes qui sont équivalents dans le cadre classique sont inéquivalentes dans le cadre constructif, et certaines formes impliquent . Dans ces cas, les formulations intuitionnistes les plus faibles ont ensuite été adoptées pour la théorie des ensembles constructive. ${\displaystyle {\mathsf {ZFC}}}$${\displaystyle {\mathsf {ZFC}}}$${\displaystyle {\mathrm {LEM} }}$

Intuitionniste Z

Toujours à l'extrémité la plus faible, comme avec son homologue historique la théorie des ensembles de Zermelo , on peut désigner par la théorie intuitionniste érigée comme mais sans Remplacement, Collection ou Induction. ${\displaystyle {\mathsf {IZ}}}$${\displaystyle {\mathsf {IZF}}}$

KP intuitionniste

Citons une autre théorie très faible qui a été étudiée, à savoir la théorie des ensembles intuitionniste (ou constructive) de Kripke-Platek . La théorie a non seulement la séparation mais aussi la collection restreinte, c'est-à-dire qu'elle est similaire mais avec l'induction au lieu du remplacement complet. Il est particulièrement faible lorsqu'il est étudié sans Infinity. La théorie ne rentre pas dans la hiérarchie telle que présentée ci-dessus, simplement parce qu'elle a un schéma Axiome d'Induction d'Ensembles dès le départ. Cela permet des théorèmes impliquant la classe des ordinaux. ${\displaystyle {\mathsf {IKP}}}$${\displaystyle {\mathsf {BCST}}}$

Théories triées

Théorie des ensembles constructifs

Tel qu'il l'a présenté, le système de Myhill est une théorie utilisant la logique constructive du premier ordre avec identité et trois sortes , à savoir les ensembles, les nombres naturels , les fonctions . Ses axiomes sont : ${\displaystyle {\mathsf {CST}}}$

• L' axiome habituel d'extensionnalité pour les ensembles, ainsi qu'un autre pour les fonctions, et l' axiome habituel d'union .
• L'axiome de la séparation restreinte ou prédicative, qui est une forme affaiblie de l' axiome de séparation de la théorie des ensembles classique, exigeant que toutes les quantifications soient liées à un autre ensemble, comme discuté.
• Une forme de l' Axiome de l'infini affirmant que l'ensemble des nombres naturels (pour lesquels il introduit une constante ) est en fait un ensemble.${\displaystyle \omega }$
• L'axiome de l'exponentiation, affirmant que pour deux ensembles, il existe un troisième ensemble qui contient toutes (et seulement) les fonctions dont le domaine est le premier ensemble et dont l'étendue est le deuxième ensemble. Il s'agit d'une forme grandement affaiblie de l' Axiome du pouvoir défini dans la théorie des ensembles classique, à laquelle Myhill, entre autres, s'est opposé en raison de son imprédicativité .

Et en plus :

• Les axiomes de Peano habituels pour les nombres naturels.
• Axiomes affirmant que le domaine et l' étendue d'une fonction sont tous deux des ensembles. De plus, un axiome de non-choix affirme l'existence d'une fonction de choix dans les cas où le choix est déjà fait. Ensemble, ils agissent comme l' axiome de remplacement habituel dans la théorie des ensembles classique.

On peut approximativement identifier la force de cette théorie avec des sous-théories constructives lors de la comparaison avec les sections précédentes. ${\displaystyle {\mathsf {ZF}}}$

Et finalement la théorie adopte

• Un Axiome de choix dépendant , qui est beaucoup plus faible que l' Axiome de choix habituel .

Théorie des ensembles de style Bishop

La théorie des ensembles dans le goût de l' école constructiviste d' Errett Bishop reflète celle de Myhill, mais est conçue de manière à ce que les ensembles soient dotés de relations qui régissent leur discrétion. Généralement, le choix dépendant est adopté.

De nombreuses analyses et théories de modules ont été développées dans ce contexte.

Théories des catégories

Toutes les théories logiques formelles des ensembles n'ont pas besoin d'axiomiser directement le prédicat d'appartenance binaire " ". Et une théorie élémentaire des catégories d'ensemble ( ), par exemple la capture de paires de correspondances composables entre des objets, peut également être exprimée avec une logique de fond constructive ( ). La théorie des catégories peut être érigée en théorie des flèches et des objets, bien que des axiomatisations du premier ordre uniquement en termes de flèches soient possibles. ${\style d'affichage \in }$${\displaystyle {\mathsf {ETCS}}}$${\displaystyle {\mathsf {CETCS}}}$

De bons modèles de théories constructives des ensembles dans la théorie des catégories sont les prétopes mentionnés dans la section Exponentiation - nécessitant peut-être aussi suffisamment de projectifs , un axiome sur les "présentations" surjectives de l'ensemble, impliquant un choix dépendant dénombrable.

Au-delà de cela, les topoi ont aussi des langages internes qui peuvent être eux-mêmes intuitionnistes et capturer une notion d'ensembles .

Voir également

• Mathématiques constructives
• Théorie des types intuitionniste
• Analyse ordinale
• Imprédicativité
• Propriété d'existence
• Loi du tiers exclu
• Sous-comptabilité

Les références

Lectures complémentaires

• Troelstra, Anne ; van Dalen, Dirk (1988). Constructivisme en mathématiques, vol. 2 . Etudes de Logique et Fondements des Mathématiques. p. 619 . ISBN 978-0-444-70358-3.
• Aczel, P. et Rathjen, M. (2001). Notes sur la théorie constructive des ensembles . Rapport technique 40, 2000/2001. Institut Mittag-Leffler, Suède.

Liens externes

• Laura Crosilla, Set Theory: Constructive and Intuitionistic ZF , Stanford Encyclopedia of Philosophy , 20 février 2009
• Benno van den Berg, Constructive set theory – an Overview , slides de Heyting dag, Amsterdam, 7 septembre 2012