Théorie Des Types

Table des matières:

Théorie Des Types
Théorie Des Types

Vidéo: Théorie Des Types

Vidéo: Théorie Des Types
Vidéo: La théorie homotopique des types | Hardcore 5 2024, Mars
Anonim

Navigation d'entrée

  • Contenu de l'entrée
  • Bibliographie
  • Outils académiques
  • Aperçu du PDF des amis
  • Informations sur l'auteur et la citation
  • Retour au sommet

Théorie des types

Publié pour la première fois le 8 février 2006; révision de fond mar 17 juil.2018

Le sujet de la théorie des types est fondamental à la fois en logique et en informatique. Nous nous limitons ici à esquisser quelques aspects importants en logique. Pour l'importance des types en informatique, nous renvoyons le lecteur par exemple à Reynolds 1983 et 1985.

  • 1. Paradoxes et théories des types de Russell
  • 2. Théorie des types simples et (lambda) - Calcul
  • 3. Hiérarchie ramifiée et principes d'amélioration
  • 4. Théorie des types / Théorie des ensembles
  • 5. Théorie des types / Théorie des catégories
  • 6. Extensions du système de types, polymorphisme, paradoxes
  • 7. Fondations univalentes
  • Bibliographie
  • Outils académiques
  • Autres ressources Internet
  • Entrées connexes

1. Paradoxes et théories des types de Russell

La théorie des types a été introduite par Russell afin de faire face à certaines contradictions qu'il a trouvées dans son exposé de la théorie des ensembles et a été introduite dans «Annexe B: La doctrine des types» de Russell 1903. Cette contradiction a été obtenue en analysant un théorème de Cantor qu'aucun mappage

[F: X / rightarrow / Pow (X))

(où (Pow (X)) est la classe des sous-classes d'une classe (X)) peut être surjective; autrement dit, (F) ne peut pas être tel que chaque membre (b) de (Pow (X)) est égal à (F (a)) pour un élément (a) de (X). Cela peut être formulé «intuitivement» comme le fait qu'il y a plus de sous-ensembles de (X) que d'éléments de (X). La preuve de ce fait est si simple et fondamentale qu'il vaut la peine de la donner ici. Considérez le sous-ensemble suivant de (X):

[A = {x / in X / mid x / not / in F (x) }.)

Ce sous-ensemble ne peut pas être dans la plage de (F). Pour si (A = F (a)), pour certains (a), alors

) begin {align} a / in F (a) & / text {iff} a / in A \& / text {iff} a / not / in F (a) end {align})

ce qui est une contradiction. Quelques remarques s'imposent. Premièrement, la preuve n'utilise pas la loi du milieu exclu et est donc intuitionniste valable. Deuxièmement, la méthode utilisée, appelée diagonalisation, était déjà présente dans les travaux de du Bois-Reymond pour construire des fonctions réelles croissant plus vite que n'importe quelle fonction dans une séquence de fonctions donnée.

Russell a analysé ce qui se passe si nous appliquons ce théorème au cas où A est la classe de toutes les classes, admettant qu'il existe une telle classe. Il a ensuite été amené à considérer la classe spéciale des classes qui n'appartiennent pas à elles-mêmes

) tag {*} R = {w / mid w / not / in w }.)

Nous avons alors

[R / in R / text {iff} R / not / in R.)

Il semble en effet que Cantor était déjà conscient du fait que la classe de tous les ensembles ne peut pas être considérée elle-même comme un ensemble.

Russell a communiqué ce problème à Frege, et sa lettre, ainsi que la réponse de Frege apparaissent dans van Heijenoort 1967. Il est important de se rendre compte que la formulation (*) ne s'applique pas telle qu'elle est au système de Frege. Comme Frege l'a lui-même écrit dans sa réponse à Russell, l'expression «un prédicat est fondé sur lui-même» n'est pas exacte. Frege avait une distinction entre les prédicats (concepts) et les objets. Un prédicat (de premier ordre) s'applique à un objet mais il ne peut pas avoir de prédicat comme argument. La formulation exacte du paradoxe dans le système de Frege utilise la notion d'extension d'un prédicat (P), que nous désignons par (varepsilon P). L'extension d'un prédicat est elle-même un objet. L'axiome V important est:

) tag {Axiom V} varepsilon P = / varepsilon Q / equiv / forall x [P (x) equiv Q (x)])

Cet axiome affirme que l'extension de (P) est identique à l'extension de (Q) si et seulement si (P) et (Q) sont matériellement équivalents. On peut alors traduire le paradoxe de Russell (*) dans le système de Frege en définissant le prédicat

[R (x) text {iff} existe P [x = / varepsilon P / wedge / neg P (x)])

Il peut alors être vérifié, en utilisant Axiom V de manière cruciale, que

[R (varepsilon R) equiv / neg R (varepsilon R))

et nous avons aussi une contradiction. (Notez que pour définir le prédicat (R), nous avons utilisé une quantification existentielle imprédicative sur les prédicats. On peut montrer que la version prédicative du système de Frege est cohérente (voir Heck 1996 et pour d'autres raffinements Ferreira 2002).

Il ressort clairement de ce récit qu'une idée de types était déjà présente dans l'œuvre de Frege: on y trouve une distinction entre objets, prédicats (ou concepts), prédicats de prédicats, etc. (Ce point est souligné dans Quine 1940.) Cette hiérarchie est appelée la «hiérarchie extensionnelle» par Russell (1959), et sa nécessité a été reconnue par Russell comme une conséquence de son paradoxe.

2. Théorie des types simples et (lambda) - Calcul

Comme nous l'avons vu plus haut, la distinction: objets, prédicats, prédicat de prédicats, etc., semble suffisante pour bloquer le paradoxe de Russell (et cela a été reconnu par Chwistek et Ramsey). Nous décrivons d'abord la structure de type telle qu'elle est dans Principia et plus tard dans cette section, nous présentons la formulation élégante due à Church 1940 basée sur (lambda) - calcul. Les types peuvent être définis comme

  1. (i) est le type d'individus
  2. ((,)) est le type de propositions
  3. si (A_1, / ldots, A_n) sont des types alors ((A_1, / ldots, A_n)) est le type de relations (n) - aires sur des objets de types respectifs (A_1, / ldots, Une)

Par exemple, le type de relations binaires sur les individus est ((i, i)), le type de connecteurs binaires est (((,), (,))), le type de quantificateurs sur les individus est \(((je))).

Pour former des propositions, nous utilisons cette structure de type: ainsi (R (a_1, / ldots, a_n)) est une proposition si (R) est de type ((A_1, / ldots, A_n)) et (a_i) est de type (A_i) pour (i = 1, / ldots, n). Cette restriction rend impossible la formation d'une proposition de la forme (P (P)): le type de (P) doit être de la forme ((A)), et (P) ne peut être appliqué aux arguments de type (A), et ne peut donc pas s’appliquer à lui-même puisque (A) n’est pas le même que ((A)).

Cependant la théorie des types simple n'est pas prédicative: on peut définir un objet (Q (x, y)) de type ((i, i)) par

) forall P [P (x) sous-ensemble P (y)])

Supposons que nous ayons deux individus (a) et (b) tels que (Q (a, b)) soit vrai. Nous pouvons définir (P (x)) comme étant (Q (x, a)). Il est alors clair que (P (a)) est vrai, puisque c'est (Q (a, a)). Donc (P (b)) est également valable. Nous avons prouvé, de manière imprédicative, que (Q (a, b)) implique (Q (b, a)).

Des formulations alternatives plus simples, qui ne retiennent que la notion de classes, de classes de classes, etc., ont été formulées par Gödel et Tarski. En fait, cette version plus simple a été utilisée par Gödel dans son article de 1931 sur des propositions formellement indécidables. La découverte des propositions indécidables peut avoir été motivée par un argument heuristique selon lequel il est peu probable que l'on puisse étendre le théorème de complétude de la logique du premier ordre à la théorie des types (voir la fin de sa conférence à Königsberg 1930 dans Gödel Collected Work, Volume III et Goldfarb 2005). Tarski avait une version du théorème de définissabilité exprimé en théorie des types (voir Hodges 2008). Voir Schiemer et Reck 2013.

Nous avons des objets de type 0, pour des individus, des objets de type 1, pour des classes d'individus, des objets de type 2, pour des classes de classes d'individus, etc. Les fonctions de deux arguments ou plus, comme les relations, n'ont pas besoin d'être incluses parmi les objets primitifs car on peut définir des relations comme des classes de paires ordonnées et des paires ordonnées comme des classes de classes. Par exemple, la paire ordonnée d'individus a, b peut être définie comme étant ({ {a }, {a, b } }) où ({x, y }) désigne la classe dont les seuls éléments sont (x) et (y). (Wiener 1914 avait suggéré une réduction similaire des relations en classes.) Dans ce système, toutes les propositions ont la forme (a (b)), où (a) est un signe de type (n + 1) et (b) un signe de type (n). Ainsi, ce système est construit sur le concept d'une classe ou sous-ensemble arbitraire d'objets d'un domaine donné et sur le fait que la collection de tous les sous-ensembles du domaine donné peut former un nouveau domaine du type suivant. A partir d'un domaine donné d'individus, ce processus est ensuite itéré. Comme souligné par exemple dans Scott 1993, dans la théorie des ensembles, ce processus de formation de sous-ensembles est itéré dans le transfini.

Dans ces versions de la théorie des types, comme dans la théorie des ensembles, les fonctions ne sont pas des objets primitifs, mais sont représentées comme une relation fonctionnelle. La fonction d'addition par exemple est représentée comme une relation ternaire par un objet de type ((i, i, i)). Une formulation élégante de la théorie des types simples qui l'étend en introduisant des fonctions comme objets primitifs a été donnée par Church en 1940. Elle utilise la notation (lambda) - calcul (Barendregt 1997). Puisqu'une telle formulation est importante en informatique, pour la connexion avec la théorie des catégories et pour la théorie des types de Martin-Löf, nous la décrivons en détail. Dans cette formulation, les prédicats sont considérés comme un type particulier de fonctions (fonctions propositionnelles), une idée qui remonte à Frege (voir par exemple Quine 1940). En outre,la notion de fonction est considérée comme plus primitive que la notion de prédicats et de relations, et une fonction n'est plus définie comme un type particulier de relation. (Oppenheimer et Zalta 2011 présentent quelques arguments contre une telle représentation primitive des fonctions.) Les types de ce système sont définis inductivement comme suit

  1. il existe deux types de base (i) (le type d'individus) et (o) (le type de propositions)
  2. si (A, B) sont des types alors (A / rightarrow B), le type de fonctions de (A) à (B), est un type

On peut former de cette manière les types:

(i / rightarrow o) (type de prédicats)
((i / rightarrow o) rightarrow o) (type de prédicats de prédicats)

qui correspondent aux types ((i)) et (((i))) mais aussi aux nouveaux types

(i / rightarrow i) (type de fonctions)
((i / rightarrow i) rightarrow i) (type de fonctionnels)

Il est pratique d'écrire

[A_1, / ldots, A_n / rightarrow B)

pour

[A_1 / rightarrow (A_2 / rightarrow / ldots / rightarrow (A_n / rightarrow B)))

De cette façon

[A_1, / ldots, A_n / rightarrow o)

correspond au type ((A_1, / ldots, A_n)).

La logique du premier ordre ne considère que les types du formulaire

(i, / ldots, i / rightarrow i) (type de symboles de fonction), et
(i, / ldots, i / rightarrow o) (type de prédicat, symboles de relation)

Remarquerez que

[A / rightarrow B / rightarrow C)

signifie

[A / rightarrow (B / rightarrow C))

(association à droite).

Pour les termes de cette logique, nous ne suivrons pas le récit de Church mais une légère variation de celui-ci, due à Curry (qui avait des idées similaires avant la parution de l'article de Church) et qui est présentée en détail dans le livre de R. Hindley sur la théorie des types. Comme Church, nous utilisons (lambda) - calcul, qui fournit une notation générale pour les fonctions

[M:: = x / mid MM / mid / lambda xM)

Ici, nous avons utilisé la notation dite BNF, très pratique en informatique. Cela donne une spécification syntaxique des termes (lambda) qui, une fois développés, signifie:

  • chaque variable est un symbole de fonction;
  • chaque juxtaposition de deux symboles de fonction est un symbole de fonction;
  • chaque (lambda xM) est un symbole de fonction;
  • il n'y a pas d'autres symboles de fonction.

La notation pour l'application de fonction (MN) est un peu différente de la notation mathématique, qui serait (M (N)). En général, [M_1 M_2 M_3)

signifie

[(M_1 M_2) M_3)

(association à gauche). Le terme (lambda xM) représente la fonction à laquelle (N) associe (M [x: = N)]. Cette notation est si pratique qu'on se demande pourquoi elle n'est pas largement utilisée en mathématiques. L'équation principale de (lambda) - calcul est alors ((beta) - conversion)

[(lambda xM) N = M [x: = N])

qui exprime la signification de (lambda xM) en tant que fonction. Nous avons utilisé (M [x: = N)] comme notation pour la valeur de l'expression qui résulte lorsque (N) est substitué à la variable (x) dans la matrice (M). On voit généralement cette équation comme une règle de réécriture ((beta) - réduction)

[(lambda xM) N / rightarrow M [x: = N])

Dans le calcul lambda non typé, il se peut qu'une telle réécriture ne se termine pas. L'exemple canonique est donné par le terme (Delta = / lambda xx x) et l'application

) Delta / Delta / rightarrow / Delta / Delta)

(Notez la similitude avec le paradoxe de Russell.) L'idée de Curry est alors de regarder les types comme des prédicats sur des termes lambda, en écrivant (M: A) pour exprimer que (M) satisfait le prédicat / type (A). Le sens de

[N: A / rightarrow B)

est alors

) forall M, / text {if} M: A / text {then} NM: B)

ce qui justifie les règles suivantes

) frac {N: A / rightarrow BM: A} {NM: B})) frac {M: B [x: A]} { lambda xM: A / rightarrow B})

En général on travaille avec des jugements de la forme

[x_1: A_1,…, x_n: A_n / vdash M: A)

où (x_1,…, x_n) sont des variables distinctes, et (M) est un terme ayant toutes les variables libres parmi (x_1,…, x_n). Afin de pouvoir obtenir le système de Church, on ajoute quelques constantes afin de former des propositions. Typiquement

ne pas: (o / rightarrow o)
impliquer: (o / rightarrow o / rightarrow o)
et: (o / rightarrow o / rightarrow o)
pour tous: ((A / rightarrow o) rightarrow o)

Le terme

) lambda x. / neg (xx))

représente le prédicat des prédicats qui ne s'appliquent pas à eux-mêmes. Ce terme n'a cependant pas de type, c'est-à-dire qu'il n'est pas possible de trouver (A) tel que

) lambda x. / neg (xx): (A / rightarrow o) rightarrow o)

qui est l'expression formelle du fait que le paradoxe de Russell ne peut être exprimé. Égalité de Leibniz

[Q: i / rightarrow i / rightarrow o)

sera défini comme

[Q = / lambda x. / lambda y. / forall (lambda P. / imply (P x) (P y)))

On écrit généralement (forall x [M)] au lieu de (forall (lambda xM)), et la définition de (Q) peut alors être réécrite comme

[Q = / lambda x. / Lambda y. / Forall P) imply (P x) (P y)])

Cet exemple illustre à nouveau que nous pouvons formuler des définitions imprédicatives dans la théorie des types simple.

L'utilisation de (lambda) - termes et (beta) - réduction est plus pratique pour représenter les règles de substitution complexes nécessaires dans la théorie des types simple. Par exemple, si nous voulons remplacer le prédicat (lambda xQ ax) pour (P) dans la proposition

) imply (P a) (P b))

on a

) imply ((lambda xQ ax) a) ((lambda xQ ax) b))

et, en utilisant (beta) - réduction,) imply (Q aa) (Q ab))

En résumé, la théorie des types simple interdit l'auto-application mais pas la circularité présente dans les définitions imprédicatives.

Le formalisme de (lambda) - calcul permet également une analyse plus claire du paradoxe de Russell. On peut le voir comme la définition du prédicat

[R x = / neg (xx))

Si nous pensons à (beta) - réduction comme le processus de déroulement d'une définition, nous voyons qu'il y a déjà un problème avec la compréhension de la définition de RR

[RR / rightarrow / neg (RR) rightarrow / neg (neg (RR)) rightarrow / ldots)

Dans un certain sens, nous avons une définition non fondée, qui est aussi problématique qu'une contradiction (une proposition équivalente à sa négation). Un théorème important, le théorème de normalisation, dit que cela ne peut pas arriver avec des types simples: si nous avons (M: A) alors (M) est normalisable de manière forte (toute séquence de réductions commençant à (M) se termine).

Pour plus d'informations sur ce sujet, nous renvoyons à l'entrée sur la théorie des types simples de Church.

3. Hiérarchie ramifiée et principes d'amélioration

Russell a introduit une autre hiérarchie, qui n'était pas motivée par des paradoxes formels exprimés dans un système formel, mais plutôt par la peur de la «circularité» et par des paradoxes informels similaires au paradoxe du menteur. Si un homme dit «je mens», alors nous avons une situation qui rappelle le paradoxe de Russell: une proposition qui équivaut à sa propre négation. Une autre situation paradoxale informelle est obtenue si nous définissons un entier comme étant le «plus petit entier non définissable en moins de 100 mots». Afin d'éviter de tels paradoxes informels, Russell a jugé nécessaire d'introduire un autre type de hiérarchie, la soi-disant «hiérarchie ramifiée». La nécessité d'une telle hiérarchie est suggérée dans l'annexe B de Russell 1903. Il est intéressant de noter que cela est lié à la question de l'identité des propositions équivalentes et du produit logique d'une classe de propositions. Une discussion approfondie peut être trouvée dans le chapitre 10 de Russell 1959. Puisque cette notion de hiérarchie ramifiée a été extrêmement influente en logique et en particulier en théorie de la preuve, nous la décrivons en quelques détails.

Afin de motiver davantage cette hiérarchie, voici un exemple dû à Russell. Si nous disons

Napoléon était Corse.

nous ne faisons référence dans cette phrase à aucun assemblage de propriétés. La propriété «être corse» est dite prédicative. Si nous disons d'un autre côté

Napoléon avait toutes les qualités d'un grand général

nous nous référons à un ensemble de qualités. La propriété «d'avoir toutes les qualités d'un grand général» est dite imprédicative.

Un autre exemple, également venant de Russell, montre comment les propriétés imprédicatives peuvent potentiellement conduire à des problèmes rappelant le paradoxe du menteur. Supposons que nous suggérons la définition

Un Anglais typique est celui qui possède toutes les propriétés possédées par une majorité d'Anglais.

Il est clair que la plupart des Anglais ne possèdent pas toutes les propriétés que possèdent la plupart des Anglais. Par conséquent, un Anglais typique, selon cette définition, devrait être atypique. Le problème, selon Russell, est que le mot «typique» a été défini par une référence à toutes les propriétés et a été traité comme une propriété. (Il est remarquable que des problèmes similaires se posent lors de la définition de la notion de nombres aléatoires, cf. Martin-Löf «Notes sur les mathématiques constructives» (1970).) Russell a introduit la hiérarchie ramifiée afin de traiter l'apparente circularité de telles définitions imprédicatives. Il faut faire une distinction entre les propriétés du premier ordre, comme être corse, qui ne se réfèrent pas à la totalité des propriétés, et considérer que les propriétés du second ordre se réfèrent uniquement à la totalité des propriétés du premier ordre. On peut alors introduire des propriétés de troisième ordre, qui peuvent faire référence à la totalité des propriétés de deuxième ordre, et ainsi de suite. Cela élimine clairement toutes les circularités liées aux définitions imprédicatives.

À peu près au même moment, Poincaré a procédé à une analyse similaire. Il a souligné l'importance des classifications «prédicatives» et de ne pas définir les éléments d'une classe en utilisant une quantification sur cette classe (Poincaré 1909). Poincaré a utilisé l'exemple suivant. Supposons que nous ayons une collection avec les éléments 0, 1 et une opération + satisfaisant

) begin {align} x + 0 & = 0 \\ x + (y + 1) & = (x + y) +1 / end {align})

Disons qu'une propriété est inductive si elle vaut 0 et vaut pour (x + 1) si elle vaut pour (x).

Une définition imprédicative et potentiellement «dangereuse» serait de définir un élément comme étant un nombre s'il satisfait toutes les propriétés inductives. Il est alors facile de montrer que cette propriété «d'être un nombre» est elle-même inductive. En effet, 0 est un nombre car il satisfait toutes les propriétés inductives, et si (x) satisfait toutes les propriétés inductives alors (x + 1) le fait aussi. De même, il est facile de montrer que (x + y) est un nombre si (x, y) sont des nombres. En effet la propriété (Q (z)) que (x + z) est un nombre est inductive: (Q) (0) est valable puisque (x + 0 = x) et si (x + z) est un nombre, alors (x + (z + 1) = (x + z) +1). Cependant, tout cet argument est circulaire puisque la propriété «être un nombre» n'est pas prédicative et doit être traitée avec suspicion.

Au lieu de cela, il faut introduire une hiérarchie ramifiée de propriétés et de nombres. Au départ, on n'a que des propriétés inductives du premier ordre, qui ne renvoient pas dans leurs définitions à un ensemble de propriétés, et on définit les nombres d'ordre 1 comme étant les éléments satisfaisant toutes les propriétés inductives du premier ordre. On peut ensuite considérer les propriétés inductives du second ordre, qui peuvent faire référence à l'ensemble des propriétés du premier ordre, et les nombres d'ordre 2, qui sont les éléments satisfaisant les propriétés inductives d'ordre 2. On peut alors considérer de même des nombres d'ordre 3, et ainsi de suite. Poincaré souligne le fait qu'un nombre d'ordre 2 est a fortiori un nombre d'ordre 1, et plus généralement, un nombre d'ordre (n + 1) est a fortiori un nombre d'ordre (n). Nous avons ainsi une suite de propriétés de plus en plus restreintes:des propriétés inductives d'ordre 1, 2,… et une suite de collections d'objets de plus en plus restreintes: des nombres d'ordre 1, 2,… De plus, la propriété «être un nombre d'ordre (n)» est elle-même une inductive propriété d'ordre (n + 1).

Il ne semble pas possible de prouver que (x + y) est un nombre d'ordre (n) si (x, y) sont des nombres d'ordre (n). Par contre, il est possible de montrer que si (x) est un nombre d'ordre (n + 1), et (y) un nombre d'ordre (n + 1) alors (x + y) est un numéro d'ordre (n). En effet, la propriété (P (z)) que «(x + z) est un nombre d'ordre (n)» est une propriété inductive d'ordre (n + 1: P) (0) tient puisque (x + 0 = x) est un nombre d'ordre (n + 1), et donc d'ordre (n), et si (P (z)) est vrai, c'est-à-dire si (x + z) est un nombre d'ordre (n), alors (x + (z + 1) = (x + z) +1), et donc (P (z + 1)) tient. Puisque (y) est un nombre d'ordre (n + 1), et (P (z)) est une propriété inductive d'ordre (n + 1, P (y)) est valable et donc (x + y) est un numéro d'ordre (n). Cet exemple illustre bien les complexités introduites par la hiérarchie ramifiée.

Les complexités sont encore amplifiées si l'on, comme Russell comme pour Frege, définit même les objets de base comme les nombres naturels comme des classes de classes. Par exemple, le nombre 2 est défini comme la classe de toutes les classes d'individus ayant exactement deux éléments. Nous obtenons à nouveau des nombres naturels d'ordres différents dans la hiérarchie ramifiée. Outre Russell lui-même, et malgré toutes ces complications, Chwistek a tenté de développer l'arithmétique de manière ramifiée, et l'intérêt d'une telle analyse a été souligné par Skolem. Voir Burgess et Hazen 1998 pour un développement récent.

Un autre exemple mathématique, souvent donné, d'une définition imprédicative est la définition de la moindre borne supérieure d'une classe bornée de nombres réels. Si nous identifions un réel à l'ensemble des rationnels inférieurs à ce réel, nous voyons que cette borne inférieure peut être définie comme l'union de tous les éléments de cette classe. Identifions les sous-ensembles des rationnels comme des prédicats. Par exemple, pour les nombres rationnels (q, P (q)) tient si (q) est un membre du sous-ensemble identifié comme (P). Maintenant, nous définissons le prédicat (L_C) (un sous-ensemble des rationnels) comme étant la plus petite borne supérieure de la classe (C) comme:

) forall q [L_C (q) leftrightarrow / existe P [C (P) coin P (q)])

ce qui est imprédicatif: nous avons défini un prédicat (L) par une quantification existentielle sur tous les prédicats. Dans la hiérarchie ramifiée, si (C) est une classe de classes de rationnels du premier ordre, alors (L) sera une classe de rationnels du second ordre. On obtient alors non pas une notion ou des nombres réels, mais des nombres réels d'ordres différents 1, 2,… La moindre borne supérieure d'une collection de réels d'ordre 1 sera alors au moins d'ordre 2 en général.

Comme nous l'avons vu précédemment, un autre exemple de définition imprédicative est donné par la définition d'égalité de Leibniz. Pour Leibniz, le prédicat «est égal à (a)» est vrai pour (b) si (b) satisfait tous les prédicats satisfaits par (a).

Comment gérer les complications introduites par la hiérarchie ramifiée? Russell a montré, dans l'introduction de la deuxième édition de Principia Mathematica, que ces complications peuvent être évitées dans certains cas. Il pensait même, dans l'annexe B de la deuxième édition de Principia Mathematica, que la hiérarchie ramifiée des nombres naturels d'ordre 1,2,… s'effondre à l'ordre 5. Cependant, Gödel a trouvé plus tard un problème dans son argumentation, et en effet, c'était montré par Myhill 1974 que cette hiérarchie ne s'effondre en fait à aucun niveau fini. Un problème similaire,discuté par Russell dans l'introduction de la deuxième édition de Principia Mathematica se pose dans la preuve du théorème de Cantor qu'il ne peut y avoir de fonctions injectives de la collection de tous les prédicats à la collection de tous les objets (la version du paradoxe de Russell dans le système de Frege selon lequel nous présenté dans l'introduction). Cela peut-il être fait dans une hiérarchie ramifiée? Russell doutait que cela puisse être fait dans une hiérarchie ramifiée de prédicats et cela a en effet été confirmé plus tard (Heck 1996).

En raison de ces problèmes, Russell et Whitehead ont introduit dans la première édition de Principia Mathematica l'axiome de réductibilité suivant: la hiérarchie des prédicats, du premier ordre, du second ordre, etc., s'effondre au niveau 1. Cela signifie que pour tout prédicat de tout ordre, il existe un prédicat du niveau du premier ordre qui lui est équivalent. Dans le cas de l'égalité par exemple, nous postulons une relation du premier ordre «(a = b)» qui équivaut à «(a) satisfait toutes les propriétés que (b) satisfait». La motivation de cet axiome était purement pragmatique. Sans cela, toutes les notions mathématiques de base, comme les nombres réels ou naturels, sont stratifiées en différents ordres. Aussi, malgré l'apparente circularité des définitions imprédicatives, l'axiome de réductibilité ne semble pas conduire à des incohérences.

Comme remarqué cependant d'abord par Chwistek, puis par Ramsey, en présence de l'axiome de la réductibilité, il est en fait inutile d'introduire la hiérarchie ramifiée du tout! Il est beaucoup plus simple d'accepter des définitions imprédicatives dès le départ. La simple hiérarchie «extensionnelle» des individus, des classes, des classes de classes,… suffit alors. On obtient ainsi les systèmes plus simples formalisés dans Gödel 1931 ou Church 1940 qui ont été présentés ci-dessus.

L'axiome de réductibilité attire l'attention sur le statut problématique des définitions imprédicatives. Pour citer Weyl 1946, l'axiome de la réductibilité «est un axiome audacieux, presque fantastique; il y a peu de justification pour cela dans le monde réel dans lequel nous vivons, et aucune justification dans l'évidence sur laquelle notre esprit fonde ses constructions »! Jusqu'à présent, aucune contradiction n'a été trouvée en utilisant l'axiome de réductibilité. Cependant, comme nous le verrons ci-dessous, les recherches théoriques de la preuve confirment l'extrême force d'un tel principe.

L'idée de la hiérarchie ramifiée a été extrêmement importante en logique mathématique. Russell n'a considéré que l'itération finie de la hiérarchie: premier ordre, second ordre, etc., mais dès le début, la possibilité d'étendre la ramification de manière transfinie a été envisagée. Poincaré (1909) mentionne le travail de Koenig dans ce sens. Pour l'exemple ci-dessus de nombres d'ordre différent, il définit également un nombre comme inductif d'ordre (omega) s'il est inductif de tous ordres finis. Il souligne ensuite que x + y est inductif d'ordre (omega) si (x) et (y) le sont. Ceci montre que l'introduction d'ordres transfinis peut dans certains cas jouer le rôle d'axiome de réductibilité. Une telle extension transfinie de la hiérarchie ramifiée a été analysée plus en détail par Gödel qui a remarqué le fait clé que la forme suivante de l'axiome de réductibilité est en fait prouvable: quand on étend la hiérarchie ramifiée des propriétés sur les nombres naturels dans le transfini, cette hiérarchie s'effondre au niveau (omega_1), l'ordinal le moins indénombrable (Gödel 1995 et Prawitz 1970). De plus, alors qu'à tous les niveaux (lt / omega_1), la collection de prédicats est dénombrable, la collection de prédicats au niveau (omega_1) est de cardinalité (omega_1). Ce fait était une forte motivation derrière le modèle d'ensembles constructibles de Gödel. Dans ce modèle, la collection de tous les sous-ensembles de l'ensemble des nombres naturels (représentés par des prédicats) est de cardinalité (omega_1) et est similaire à la hiérarchie ramifiée. Ce modèle satisfait ainsi l'hypothèse du continuum et donne une preuve de cohérence relative de cet axiome. (La motivation de Gödel était à l'origine uniquement de construire un modèle où la collection de tous les sous-ensembles de nombres naturels est bien ordonnée.)

La hiérarchie ramifiée a également été à l'origine de nombreux travaux en théorie de la preuve. Après la découverte par Gentzen que la cohérence de l'arithmétique pouvait être prouvée par induction transfinie (sur des prédicats décidables) le long de l'ordinal (varepsilon_0), la question naturelle était de trouver l'ordinal correspondant pour les différents niveaux de la hiérarchie ramifiée. Schütte (1960) a constaté que pour le premier niveau de la hiérarchie ramifiée, c'est-à-dire si nous étendons l'arithmétique en ne quantifiant que sur les propriétés du premier ordre, nous obtenons un système de force ordinale (varepsilon _ { varepsilon_0}). Pour le deuxième niveau, nous obtenons la force ordinale (varepsilon _ { varepsilon_ { varepsilon_0}}), etc. Nous rappelons que (varepsilon _ { alpha}) désigne le (alpha) - th (varepsilon) - nombre ordinal,un (varepsilon) - un nombre ordinal étant un ordinal (beta) tel que (omega ^ { beta} = / beta), voir Schütte (1960).

Gödel a souligné le fait que son approche du problème de l'hypothèse du continuum n'était pas constructive, car elle a besoin de l'ordinal indénombrable (omega_1), et il était naturel d'étudier la hiérarchie ramifiée selon des ordinaux constructifs. Après les travaux préliminaires de Lorenzen et Wang, Schütte a analysé ce qui se passe si nous procédons de la manière suivante plus constructive. Puisque l'arithmétique a pour force ordinale (varepsilon_0), nous considérons d'abord l'itération de la hiérarchie ramifiée jusqu'à (varepsilon_0). Schütte a calculé la force ordinale du système résultant et a trouvé une force ordinale (u (1) gt / varepsilon_0). Nous itérons ensuite la hiérarchie ramifiée jusqu'à cet ordinal (u (1)) et obtenons un système de force ordinale (u (2) gt u (1)), etc. Chaque (u (k)) peut être calculé en fonction de la soi-disant hiérarchie Veblen:(u (k + 1)) est (phi_ {u (k)} (0)). La limite de ce processus donne un ordinal appelé (Gamma_0): si nous itérons la hiérarchie ramifiée jusqu'à l'ordinal (Gamma_0), nous obtenons un système de force ordinale (Gamma_0). Un tel ordinal a été obtenu indépendamment à peu près au même moment par S. Feferman. Il a été affirmé que (Gamma_0) joue pour les systèmes prédicatifs un rôle similaire à (varepsilon_0) pour l'arithmétique. Cependant, des travaux récents de théorie de la preuve concernent des systèmes ayant des ordinaux de la théorie de la preuve plus grands qui peuvent être considérés comme prédicatifs (voir par exemple Palmgren 1995). Il a été affirmé que (Gamma_0) joue pour les systèmes prédicatifs un rôle similaire à (varepsilon_0) pour l'arithmétique. Cependant, des travaux récents de théorie de la preuve concernent des systèmes ayant des ordinaux de la théorie de la preuve plus grands qui peuvent être considérés comme prédicatifs (voir par exemple Palmgren 1995). Il a été affirmé que (Gamma_0) joue pour les systèmes prédicatifs un rôle similaire à (varepsilon_0) pour l'arithmétique. Cependant, des travaux récents de théorie de la preuve concernent des systèmes ayant des ordinaux de la théorie de la preuve plus grands qui peuvent être considérés comme prédicatifs (voir par exemple Palmgren 1995).

Outre ces investigations théoriques de la preuve liées à la hiérarchie ramifiée, de nombreux travaux ont été consacrés en théorie de la preuve à l'analyse de la cohérence de l'axiome de réductibilité ou, de manière équivalente, de la cohérence des définitions imprédicatives. Suite à l'analyse de Gentzen de la propriété d'élimination des coupures dans le calcul séquentiel, Takeuti a trouvé une élégante formulation séquentielle de la théorie des types simple (sans ramification) et a fait la conjecture audacieuse que l'élimination des coupures devrait tenir pour ce système. Cette conjecture paraissait au premier abord extrêmement douteuse compte tenu de la circularité de la quantification imprédicative, qui se reflète bien dans ce formalisme. La règle des quantifications est en effet

) frac { Gamma / vdash / forall X [A (X)]} { Gamma / vdash A [X: = T]})

où (T) est n'importe quel terme prédicat, qui peut lui-même impliquer une quantification sur tous les prédicats. Ainsi la formule (A [X: = T]) peut être elle-même beaucoup plus complexe que la formule (A (X)).

Un des premiers résultats est que l'élimination des coupures pour le système imprédicatif de Takeuti implique d'une manière finitaire la cohérence de l'arithmétique du second ordre. (On montre que cela implique la cohérence d'une forme appropriée d'axiome de l'infini, voir Andrews 2002.) À la suite des travaux de Schütte, il a été montré plus tard par W. Tait et D. Prawitz que la propriété d'élimination de coupure était cela doit utiliser un principe théorique de preuve plus fort, comme il devrait l'être selon le théorème d'incomplétude.)

Ce qui importe ici, c'est que ces études ont révélé l'extrême puissance de la quantification imprédicative ou, de manière équivalente, l'extrême puissance de l'axiome de réductibilité. Cela confirme en quelque sorte les intuitions de Poincaré et Russell. La force théorique de la preuve de l'arithmétique du second ordre est bien au-dessus de toutes les extensions ramifiées de l'arithmétique considérées par Schütte. D'un autre côté, malgré la circularité des définitions imprédicatives, qui est rendue si explicite dans le calcul de Takeuti, aucun paradoxe n'a encore été trouvé dans l'arithmétique du second ordre.

Une autre direction de recherche en théorie de la preuve a été de comprendre dans quelle mesure la quantification imprédicative peut être expliquée à partir des principes disponibles en mathématiques intuitionnistes. Les principes les plus forts sont les formes fortes de définitions inductives. Avec de tels principes, on peut expliquer une forme limitée de quantification imprédicative, appelée (Pi_ {1} ^ 1) - compréhension, où l'on n'utilise qu'un seul niveau de quantification imprédicative sur les prédicats. Fait intéressant, presque toutes les utilisations connues des quantifications imprédicatives: l'égalité de Leibniz, la borne inférieure, etc., peuvent être faites avec (Pi_ {1} ^ 1) - compréhension. Cette réduction de (Pi_ {1} ^ 1) - compréhension a d'abord été réalisée par Takeuti d'une manière assez indirecte, et a ensuite été simplifiée par Buchholz et Schütte en utilisant la règle dite (Omega) -. Il peut être considéré comme une explication constructive de certaines utilisations restreintes, mais non triviales, de définitions imprédicatives.

4. Théorie des types / Théorie des ensembles

La théorie des types peut être utilisée comme une base pour les mathématiques, et en effet, elle a été présentée comme telle par Russell dans son article de 1908, paru la même année que l'article de Zermelo, présentant la théorie des ensembles comme une base pour les mathématiques.

Il est intuitivement clair comment nous pouvons expliquer la théorie des types en théorie des ensembles: un type est simplement interprété comme un ensemble, et les types de fonction (A / rightarrow B) peuvent être expliqués en utilisant la notion théorique d'ensemble de fonction (comme une relation fonctionnelle, c'est-à-dire un ensemble de paires d'éléments). Le type (A / rightarrow o) correspond à l'opération Poweret.

L'autre direction est plus intéressante. Comment expliquer la notion d'ensembles en termes de types? Il existe une solution élégante, due à A. Miquel, qui complète les travaux antérieurs de P. Aczel (1978) et qui a aussi l'avantage d'expliquer des ensembles non nécessairement fondés à la Finsler. On interprète simplement un ensemble comme un graphe pointu (où la flèche dans le graphe représente la relation d'appartenance). Ceci est très bien représenté dans la théorie des types, un graphe pointu étant simplement donné par un type A et une paire d'éléments

[a: A, R: A / rightarrow A / rightarrow o)

On peut alors définir en théorie des types quand deux tels ensembles (A, a, R) et (B, b, S) sont égaux: c'est le cas s'il y a une bisimulation (T) entre (A) et (B) tels que (Tab) tient. Une bisimulation est une relation

[T: A / rightarrow B / rightarrow o)

tel que chaque fois que (Txy) et (Rxu) tiennent, il existe (v) tel que (Tuv) et (Syv) tiennent, et chaque fois que (Txy) et (Ryv) hold, il existe (u) tel que (Tuv) et (Rxu) tiennent. On peut alors définir la relation d'appartenance: l'ensemble représenté (B, b, S) est membre de l'ensemble représenté par (A, a, R) ss'il existe (a_1) tel que (Ra_1a) et (A, a_1, R) et (B, b, S) sont bisimilaires.

On peut alors vérifier que tous les axiomes habituels de l'extension de la théorie des ensembles, de l'ensemble des pouvoirs, de l'union, de la compréhension sur des formules bornées (et même de l'antifondation, de sorte que la relation d'appartenance n'a pas besoin d'être bien fondée) tiennent dans ce modèle simple. (Une formule bornée est une formule où toutes les quantifications sont de la forme (forall x / in a / ldots) ou (exists x / in a / ldots)). De cette façon, il peut être montré que la théorie des types simples de Church est équicohérente avec la version bornée de la théorie des ensembles de Zermelo.

5. Théorie des types / Théorie des catégories

Il existe des liens profonds entre la théorie des types et la théorie des catégories. Nous nous limitons à présenter deux applications de la théorie des types à la théorie des catégories: les constructions de la catégorie fermée cartésienne libre et des topos libres (voir l'entrée sur la théorie des catégories pour une explication de «cartésien fermé» et «topos»).

Pour construire la catégorie fermée cartésienne libre, nous étendons la théorie des types simples avec le type 1 (type d'unité) et le type de produit (A / fois B), pour les types (A, B). Les termes sont étendus en ajoutant des opérations d'appariement et des projections et un élément spécial de type 1. Comme dans Lambek et Scott 1986, on peut alors définir une notion de conversions typées entre termes, et montrer que cette relation est décidable. On peut alors montrer (Lambek et Scott 1986) que la catégorie avec les types comme objets et comme morphismes de (A) vers (B) l'ensemble des termes fermés de type (A / rightarrow B) (avec conversion comme égalité) est la catégorie fermée cartésienne libre. Cela peut être utilisé pour montrer que l'égalité entre les flèches de cette catégorie est décidable.

La théorie des types d'Eglise peut également être utilisée pour construire les topos libres. Pour cela nous prenons comme objets des paires (A, E) de type (A) et (E) une relation d'équivalence partielle, c'est-à-dire un terme fermé (E: A / rightarrow A / rightarrow o) qui est symétrique et transitive. On prend comme morphismes entre (A, E) et (B, F) les relations (R: A / rightarrow B / rightarrow o) fonctionnelles telles que pour tout (a: A) satisfaisant (E aa) il existe un, et un seul élément (modulo (F)) (b) de (B) tel que (F bb) et (R ab). Pour le classificateur de sous-objets, nous prenons la paire (o, E) avec (E: o / rightarrow o / rightarrow o) définie comme

[EMN = / text {et} (imply \, MN) (imply \, NM))

On peut alors montrer que cette catégorie forme un topos, voire le topos libre.

Il est à noter que la théorie des types de Lambek et Scott 1986 utilise une variante de la théorie des types, introduite par Henkin et affinée par P. Andrews (2002) qui consiste à avoir une égalité extensionnelle comme seul connectif logique, c'est-à-dire une constante polymorphe

) text {eq}: A / rightarrow A / rightarrow o)

et de définir tous les connecteurs logiques à partir de ce connectif et des constantes (T, F: o). Par exemple, on définit

) forall P = _ {df} text {eq} (lambda xT) P)

L'égalité au type (o) est l'équivalence logique.

Un avantage de la formulation intensionnelle est qu'elle permet une notation directe des preuves basées sur (lambda) - calcul (Martin-Löf 1971 et Coquand 1986).

6. Extensions du système de types, polymorphisme, paradoxes

Nous avons vu l'analogie entre l'opération A (rightarrow) A (rightarrow) o sur les types et l'opération powerset sur les ensembles. En théorie des ensembles, l'opération d'ensemble de pouvoirs peut être itérée de manière transfinie le long de la hiérarchie cumulative. Il est alors naturel de rechercher des versions transfinies analogues de la théorie des types.

Une telle extension de la théorie des types simples de Church est obtenue en ajoutant des univers (Martin-Löf 1970). L'ajout d'un univers est un processus de réflexion: on ajoute un type (U) dont les objets sont les types considérés jusqu'ici. Pour la théorie des types simples de Church, nous aurons

[o: U, i: U / text {et} A / rightarrow B: U / text {if} A: U, B: U)

et, en outre, (A) est un type si (A: U). On peut alors considérer des types tels que

[(A: U) rightarrow A / rightarrow A)

et des fonctions telles que

) text {id} = / lambda A. / lambda xx: (A: U) rightarrow A / rightarrow A)

La fonction id prend comme argument un "petit" type (A: U) et un élément (x) de type (A), et génère un élément de type (A). Plus généralement si (T (A)) est un type sous l'hypothèse (A: U), on peut former le type dépendant

[(A: U) rightarrow T (A))

Le fait que (M) soit de ce type signifie que (MA: T (A)) chaque fois que (A: U). On obtient ainsi des extensions de la théorie des types dont la force est similaire à celle de la théorie des ensembles de Zermelo (Miquel 2001). Des formes d'univers plus puissantes sont considérées dans (Palmgren 1998). Miquel (2003) présente une version de la théorie des types de la force équivalente à celle de Zermelo-Fraenkel.

Une forme d'univers très forte est obtenue en ajoutant l'axiome (U: U). Cela a été suggéré par P. Martin-Löf en 1970. JY Girard a montré que la théorie des types résultante est incohérente en tant que système logique (Girard 1972). Bien qu'il semble au premier abord que l'on puisse reproduire directement le paradoxe de Russell en utilisant un ensemble de tous les ensembles, un tel paradoxe direct n'est en fait pas possible en raison de la différence entre les ensembles et les types. En effet, la dérivation d'une contradiction dans un tel système est subtile et a été plutôt indirecte (bien que, comme remarqué dans Miquel 2001, elle peut maintenant être réduite au paradoxe de Russell en représentant les ensembles sous forme de graphes pointus). JY Girard a d'abord obtenu son paradoxe pour un système plus faible. Ce paradoxe a été affiné plus tard (Coquand 1994 et Hurkens 1995). (La notion de système de type pur, introduite dans Barendregt 1992,est pratique pour obtenir une formulation précise de ces paradoxes.) Au lieu de l'axiome (U: U), on suppose seulement

[(A: U) rightarrow T (A): U)

si (T (A): U [A: U]). Remarquez la circularité, en effet du même genre que celle qui est rejetée par la hiérarchie ramifiée: on définit un élément de type (U) en quantifiant sur tous les éléments de (U). Par exemple le type

[(A: U) rightarrow A / rightarrow A: U)

sera le type de la fonction d'identité polymorphe. Malgré cette circularité, JY Girard a pu montrer la normalisation des systèmes de types avec cette forme de polymorphisme. Cependant, l'extension de la théorie des types simples de Church avec le polymorphisme est incohérente en tant que système logique, c'est-à-dire que toutes les propositions (termes de type o) sont prouvables.

La motivation de JY Girard pour considérer un système de types avec polymorphisme était d'étendre l'interprétation de Dialectica de Gödel (Gödel 1958) à l'arithmétique du second ordre. Il a prouvé la normalisation en utilisant la méthode de la réductibilité, qui avait été introduite par Tait (1967) lors de l'analyse de Gödel 1958. Il est tout à fait remarquable que la circularité inhérente à l'imprédicativité n'aboutit pas à des termes non normalisables. (L'argument de Girard a ensuite été utilisé pour montrer que l'élimination des coupures se termine dans le calcul séquentiel de Takeuti présenté ci-dessus.) Un système similaire a été introduit indépendamment par J. Reynolds (1974) lors de l'analyse de la notion de polymorphisme en informatique.

L'introduction par Martin-Löf d'un type de tous types vient de l'identification du concept de propositions et de types, suggéré par les travaux de Curry et Howard. Il convient de rappeler ici ses trois points motivants:

  1. Définition de Russell des types en tant que plages de signification des fonctions propositionnelles
  2. le fait qu'il faut quantifier sur toutes les propositions (imprédicativité de la théorie des types simple)
  3. identification de la proposition et des types

Étant donné (1) et (2), nous devrions avoir un type de propositions (comme dans la théorie des types simple), et étant donné (3), cela devrait également être le type de tous les types. Le paradoxe de Girard montre qu'on ne peut pas avoir (1), (2) et (3) simultanément. Le choix de Martin-Löf a été de supprimer (2), restreignant la théorie des types à être prédicative (et, en effet, la notion d'univers est apparue en premier dans la théorie des types comme une version prédicative du type de tous les types). Le choix alternatif de l'emporter (3) est discuté dans Coquand 1986.

7. Fondations univalentes

Les liens entre la théorie des types, la théorie des ensembles et la théorie des catégories reçoivent un éclairage nouveau à travers les travaux sur les fondations univalentes (Voevodsky 2015) et l'axiome de l'univalence. Cela implique de manière essentielle l'extension de la théorie des types décrite dans la section précédente, en particulier les types dépendants, la vision des propositions comme types et la notion d'univers des types. Ces développements sont également pertinents pour discuter de la notion de structure, dont l'importance a par exemple été soulignée dans Russell 1959.

Martin-Löf 1975 [1973] a introduit un nouveau type de base (mathbf {Id} _A (a, b)), si (a) et (b) sont du type (A), qui peut être considéré comme le type de preuves d'égalité de l'élément (a) et (b). Une caractéristique importante de ce nouveau type est qu'il peut être itéré, de sorte que nous pouvons considérer le type (mathbf {Id} _ { mathbf {Id} _A (a, b)} (p, q)) si (p) et (q) sont de type (mathbf {Id} _A (a, b)). Si nous considérons un type comme un type spécial d'ensemble, il est naturel de supposer qu'un tel type de preuves d'égalité est toujours habité pour deux preuves d'égalité quelconques (p) et (q). En effet, intuitivement, il semble y avoir au plus une preuve d'égalité entre deux éléments (a) et (b). Étonnamment, Hofmann et Streicher 1996 ont conçu un modèle de théorie des types dépendants où ce n'est pas valide,c'est un modèle où ils peuvent être des preuves différentes que deux éléments sont égaux. Dans ce modèle, un type est interprété par un groupoïde et le type (mathbf {Id} _A (a, b)) par l'ensemble des isomorphismes entre (a) et (b), ensemble qui peut avoir plus d'un élément. L'existence de ce modèle a pour conséquence qu'il ne peut pas être prouvé en général dans la théorie des types qu'un type d'égalité a au plus un élément. Cette interprétation groupoïde a été généralisée de la manière suivante, ce qui donne une interprétation intuitive du type d'identité. Un type est interprété par un espace topologique, jusqu'à homotopie, et un type (mathbf {Id} _A (a, b)) est interprété par le type de chemins reliant (a) et (b). (Voir Awodey et al. 2013 et [HoTT 2013, Other Internet Resources].)un type est interprété par un groupoïde et le type (mathbf {Id} _A (a, b)) par l'ensemble des isomorphismes entre (a) et (b), ensemble pouvant en avoir plus d'un élément. L'existence de ce modèle a pour conséquence qu'il ne peut pas être prouvé en général dans la théorie des types qu'un type d'égalité a au plus un élément. Cette interprétation groupoïde a été généralisée de la manière suivante, ce qui donne une interprétation intuitive du type d'identité. Un type est interprété par un espace topologique, jusqu'à homotopie, et un type (mathbf {Id} _A (a, b)) est interprété par le type de chemins reliant (a) et (b). (Voir Awodey et al. 2013 et [HoTT 2013, Other Internet Resources].)un type est interprété par un groupoïde et le type (mathbf {Id} _A (a, b)) par l'ensemble des isomorphismes entre (a) et (b), ensemble pouvant en avoir plus d'un élément. L'existence de ce modèle a pour conséquence qu'il ne peut pas être prouvé en général dans la théorie des types qu'un type d'égalité a au plus un élément. Cette interprétation groupoïde a été généralisée de la manière suivante, ce qui donne une interprétation intuitive du type d'identité. Un type est interprété par un espace topologique, jusqu'à homotopie, et un type (mathbf {Id} _A (a, b)) est interprété par le type de chemins reliant (a) et (b). (Voir Awodey et al. 2013 et [HoTT 2013, Other Internet Resources].)L'existence de ce modèle a pour conséquence qu'il ne peut pas être prouvé en général dans la théorie des types qu'un type d'égalité a au plus un élément. Cette interprétation groupoïde a été généralisée de la manière suivante, ce qui donne une interprétation intuitive du type d'identité. Un type est interprété par un espace topologique, jusqu'à homotopie, et un type (mathbf {Id} _A (a, b)) est interprété par le type de chemins reliant (a) et (b). (Voir Awodey et al. 2013 et [HoTT 2013, Other Internet Resources].)L'existence de ce modèle a pour conséquence qu'il ne peut pas être prouvé en général dans la théorie des types qu'un type d'égalité a au plus un élément. Cette interprétation groupoïde a été généralisée de la manière suivante, ce qui donne une interprétation intuitive du type d'identité. Un type est interprété par un espace topologique, jusqu'à homotopie, et un type (mathbf {Id} _A (a, b)) est interprété par le type de chemins reliant (a) et (b). (Voir Awodey et al. 2013 et [HoTT 2013, Other Internet Resources].)b)) est interprété par le type de chemins reliant (a) et (b). (Voir Awodey et al. 2013 et [HoTT 2013, Other Internet Resources].)b)) est interprété par le type de chemins reliant (a) et (b). (Voir Awodey et al. 2013 et [HoTT 2013, Other Internet Resources].)

Voevodsky 2015 a introduit la stratification des types suivante. (Cette stratification a été motivée en partie par cette interprétation d'un type comme espace topologique, mais peut être comprise directement sans référence à cette interprétation.) On dit qu'un type (A) est une proposition si on a (mathbf {Id} _A (a, b)) pour tout élément (a) et (b) de (A) (cela signifie que le type (A) a au plus un élément). On dit qu'un type (A) est un ensemble si le type (mathbf {Id} _A (a, b)) est une proposition pour tout élément (a) et (b) de (UNE). On dit qu'un type (A) est un groupoïde si le type (mathbf {Id} _A (a, b)) est un ensemble pour tout élément (a) et (b) de (UNE). La justification de cette terminologie est qu'il peut être montré, en utilisant uniquement les règles de la théorie des types, qu'un tel type peut en effet être vu comme un groupoïde au sens catégorique habituel,où les objets sont les éléments de ce type, l'ensemble des morphismes entre (a) et (b) étant représenté par l'ensemble (mathbf {Id} _A (a, b)). La composition est la preuve de la transitivité de l'égalité, et le morphisme identitaire est la preuve de la réflexivité de l'égalité. Le fait que chaque morphisme ait un inverse correspond au fait que l'identité est une relation symétrique. Cette stratification peut alors être étendue et nous pouvons définir quand un type est un 2-groupoïde, 3-groupoïde et ainsi de suite. Dans cette optique, la théorie des types apparaît comme une vaste généralisation de la théorie des ensembles, puisqu'un ensemble est un type particulier de type.et le morphisme identitaire est la preuve de la réflexivité de l'égalité. Le fait que chaque morphisme ait un inverse correspond au fait que l'identité est une relation symétrique. Cette stratification peut alors être étendue et nous pouvons définir quand un type est un 2-groupoïde, 3-groupoïde et ainsi de suite. Dans cette optique, la théorie des types apparaît comme une vaste généralisation de la théorie des ensembles, puisqu'un ensemble est un type particulier de type.et le morphisme identitaire est la preuve de la réflexivité de l'égalité. Le fait que chaque morphisme ait un inverse correspond au fait que l'identité est une relation symétrique. Cette stratification peut alors être étendue et nous pouvons définir quand un type est un 2-groupoïde, 3-groupoïde et ainsi de suite. Dans cette optique, la théorie des types apparaît comme une vaste généralisation de la théorie des ensembles, puisqu'un ensemble est un type particulier de type.

Voevodsky 2015 introduit aussi une notion d'équivalence entre types, notion qui généralise de manière uniforme les notions d'équivalence logique entre propositions, bijection entre ensembles, équivalence catégorique entre groupoïdes, etc. On dit qu'une application (f: A / rightarrow B) est une équivalence si, pour tout élément (b) dans (B) le type de paires (a, p) où (p) est de type (mathbf {Id} _B (fa, b)), est une proposition et est habitée. Cela exprime de manière forte qu'un élément dans (B) est l'image d'exactement un élément dans (A), et si (A) et (B) sont des ensembles, nous retrouvons la notion habituelle de bijection entre les ensembles. (En général, si (f: A / rightarrow B) est une équivalence, alors nous avons une application (B / rightarrow A), qui peut être considérée comme l'inverse de (f).) On peut montrer par exemple que la carte d'identité est toujours une équivalence. Soit (text {Equiv} (A, B)) le type de paires (f, p) où (f: A / rightarrow B) et (p) est une preuve que (f) est une équivalence. En utilisant le fait que la carte d'identité est une équivalence, nous avons un élément de (text {Equiv} (A, A)) pour tout type (A). Cela implique que nous avons une carte

) mathbf {Id} _U (A, B) rightarrow / text {Equiv} (A, B))

et l'Axiome d'Univalence déclare que cette carte est une équivalence. En particulier, nous avons l'implication

) text {Equiv} (A, B) rightarrow / mathbf {Id} _U (A, B))

et donc s'il y a une équivalence entre deux petits types alors ces types sont égaux.

Cet axiome peut être vu comme une forme forte du principe d'extensionnalité. Il généralise en effet l'axiome de l'extensionnalité propositionnelle mentionné par Church 1940, qui déclare que deux propositions logiquement équivalentes sont égales. De manière surprenante, cela implique également l'axiome de l'extensionnalité des fonctions, Axiome 10 dans Church 1940, qui déclare que deux fonctions égales ponctuelles sont égales (Voevodsky 2015). Cela implique aussi directement que deux ensembles isomorphes sont égaux, que deux groupoïdes catégoriquement équivalents sont égaux, et donc un.

Ceci peut être utilisé pour donner une formulation de la notion de transport de structures (Bourbaki 1957) le long d'équivalences. Par exemple, soit (MA) le type de structures monoïdes sur l'ensemble (A): c'est le type de tuples (m, e, p) où (m) est une opération binaire sur (A) et (e) un élément de (A) et (p) une preuve que ces éléments satisfont aux lois monoïdes habituelles. La règle de substitution d'égal par égal prend la forme

) mathbf {Id} _U (A, B) rightarrow MA / rightarrow MB)

S'il y a une bijection entre (A) et (B), elles sont égales par l'axiome d'Univalence, et nous pouvons utiliser cette implication pour transporter toute structure monoïde de (A) dans une structure monoïde de (B).

Nous pouvons également utiliser ce cadre pour affiner la discussion de Russell 1959 sur la notion de structure. Par exemple, laissez Monoid être le type de paires (A, p) où (p) est un élément de (MA). Deux de ces paires (A, p) et (B, q) sont isomorphes s'il existe une bijection (f) de (A) vers (B) telle que (q) est égal au transport de la structure de (p) le long de (f). Une conséquence de l'Axiome d'Univalence est que deux éléments isomorphes de type Monoïdesont égaux et partagent donc les mêmes propriétés. Notez qu'un tel transport général de propriétés n'est pas possible lorsque les structures sont formulées dans un cadre théorique d'ensemble. En effet, dans un cadre théorique d'ensemble, il est possible de formuler des propriétés en utilisant les relations d'appartenance, par exemple la propriété que l'ensemble de porteurs de la structure contient le nombre naturel (0), propriété qui n'est pas préservée en général par les isomorphismes. Intuitivement, la description théorique d'ensemble d'une structure n'est pas assez abstraite puisque l'on peut parler de la manière dont cette structure est construite. Cette différence entre la théorie des ensembles et la théorie des types est une autre illustration de la caractérisation par J. Reynolds 1983 d'une structure de types comme «discipline syntaxique pour imposer un niveau d'abstraction».

Bibliographie

  • Aczel, P., 1978, «L'interprétation théorique des types de la théorie constructive des ensembles», Logic Colloquium '77, Amsterdam: North-Holland, 55–66.
  • Andrews, P., 2002, Une introduction à la logique mathématique et à la théorie des types: à la vérité par la preuve (Applied Logic Series: Volume 27), Dordrecht: Kluwer Academic Publishers, deuxième édition.
  • Awodey, S., Pelayo, A., Warren, M. 2013, «L'axiome d'univalence dans la théorie des types d'homotopie», Avis de l'American Mathematical Society, 60 (9): 1157-1164.
  • Barendregt, H., 1997, «L'impact du calcul lambda en logique et en informatique», Bulletin de logique symbolique, 3 (2): 181–215.
  • –––, 1992, calculs Lambda avec types. Manuel de logique en informatique, volume 2, Oxford, New York: Oxford University Press, 117–309.
  • Bell, JL, 2012, «Types, ensembles et catégories», dans Akihiro Kanamory Handbook of the History of Logic. Volume 6: Ensembles et extensions au XXe siècle, Amsterdam: Hollande du Nord.
  • Bourbaki, N., 1958, Théorie des Ensembles, 3e édition, Paris: Hermann.
  • de Bruijn, NG, 1980, «Une enquête sur le projet AUTOMATH», dans To HB Curry: essais sur la logique combinatoire, le calcul lambda et le formalisme, Londres-New York: Academic Press, 579–606.
  • Burgess JP et Hazen AP, 1998, «Logique prédicative et source arithmétique formelle», Notre Dame J. Logique formelle, 39 (1): 1–17.
  • Buchholz, W. et K. Schütte, 1988, Théorie de la preuve des sous-systèmes d'analyse imprédicatifs (Études en théorie de la preuve: Monographie 2), Naples: Bibliopolis.
  • Church, A., 1940, «Une formulation de la théorie simple des types», Journal of Symbolic Logic, 5: 56–68
  • –––, 1984, «La théorie de Russell de l'identité des propositions», Philosophia Naturalis, 21: 513–522
  • Chwistek, L., 1948, Les limites de la science: aperçu de la logique et de la méthodologie des sciences exactes, Londres: Routledge et Kegan Paul.
  • Coquand, T., 1986, «Une analyse du paradoxe de Girard», Proceedings of the IEEE Symposium on Logic in Computer Science, 227-236.
  • –––, 1994, «Un nouveau paradoxe dans la théorie des types», Stud. Logique trouvée. Math. (Volume 134), Amsterdam: Hollande du Nord, 555–570.
  • du Bois-Reymond, P., 1875, «Ueber asymptotische Werthe, infintaere Appproximationen und infitaere Aufloesung von Gleichungen», Mathematische Annalen, 8: 363–414.
  • Feferman, S., 1964, «Systèmes d'analyse prédicative», Journal of Symbolic Logic, 29: 1–30.
  • Ferreira, F. et Wehmeier, K., 2002, «Sur la cohérence du fragment Delta-1-1-CA de Grundgesetze de Frege», Journal of Philosophic Logic, 31: 301–311.
  • Girard, JY, 1972, Interprétation fonctionelle et élimination des coupures dans l'arithmétique d'ordre supérieur, Ces d'Etat, Université Paris 7.
  • Goldfarb, Warren, 2005. «Sur la voie de Godel: l'influence de Rudolf Carnap.» Bulletin de logique symbolique 11 (2): 185–193.
  • Gödel, K., 1995, Collected Works Volume III, Essays and Lectures non publiés, Oxford: Oxford University Press, 1995.
  • –––, 1931, «Über formel untentscheidbare Sätze der Principia Mathematica und verwandter Systeme I», Monatshefte fü Mathematik und Physik, 38: 173–198.
  • –––, 1944, «La logique mathématique de Russell», dans La philosophie de Bertrand Russell, PA Schilpp (éd.), Evanston: Northwestern University Press, 123–153.
  • –––, 1958, «Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes», Dialectica, 12: 280-287.
  • Heck, R., Jr., 1996, «La cohérence des fragments prédicatifs de Grundgesetze der Arithmetik de Frege», History and Philosophy of Logic, 17 (4): 209–220.
  • van Heijenoort, 1967, De Frege à Gödel. Un livre source en logique mathématique 1879–1931, Cambridge, MA: Harvard University Press.
  • Hindley, R., 1997, Théorie de base des types simples, Cambridge: Cambridge University Press.
  • Hodges, W., 2008, «Tarski sur la méthode de Padoa: un cas de test pour comprendre les logiciens d'autres traditions», dans Logic, Navya-Nyāya et Applications: Hommage à Bimal Krishna Matilal, Mihir K. Chakraborti et al. (éds.), Londres: College Publications, pp. 155-169
  • Hofmann, M. et Streicher, Th. 1996, «L'interprétation groupoïde de la théorie des types», dans Vingt-cinq ans de théorie des types constructifs (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 83-111.
  • Howard, WA, 1980, «La notion de construction de formules comme types», dans To HB Curry: essais sur la logique combinatoire, le calcul lambda et le formalisme, Londres, New York: Academic Press, 480–490.
  • Hurkens, AJC, 1995, «Une simplification du paradoxe de Girard. Calculs lambda typés et applications », dans Notes de cours en informatique (volume 902), Berlin: Springer: 266-278.
  • Lambek, J., 1980. «From (lambda) - calculus to cartésian Closed Categories» dans To HB Curry: Essays on Combinatory Logic, (lambda) - calculus and formalism, J. Seldin and J. Hindley (éd.), Londres, New York: Academic Press. pp. 375–402.
  • Lambek, J. et Scott, PJ, 1986, Introduction à la logique catégorielle d'ordre supérieur (Cambridge Studies in Advanced Mathematics: Volume 7), Cambridge: Cambridge University Press; réimprimé en 1988.
  • Lawvere, FW et Rosebrugh, R., 2003, Sets for Mathématiques, Cambridge: Cambridge University Press.
  • Martin-Löf, P., 1970, Notes sur les mathématiques constructives, Stockholm: Almqvist & Wiksell.
  • –––, 1971, Une théorie des types, Rapport technique 71–3, Stockholm: Université de Stockholm.
  • –––, 1998, «Une théorie intuitionniste des types», dans Vingt-cinq ans de théorie des types constructifs (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 127–172.
  • –––, 1975 [1973], «Une théorie intuitionniste des types: partie prédicative», in Logic Colloquium '73 (Actes du Logic Colloquium, Bristol 1973) (Studies in Logic and the Foundations of Mathematics: Volume 80), HE Rose et JC Shepherdson (éd.), Amsterdam: Hollande du Nord, 73–118.
  • Myhill, J., 1974, «The Undefinability of the Set of Natural Nbers in the Ramified Principia», in Bertrand Russell's Philosophy, G. Nakhnikian (ed.), Londres: Duckworth, 19–27.
  • Miquel, A., 2001, Le Calcul des Constructions implicite: syntaxe et sémantique, Thèse de doctorat, Université Paris 7.
  • –––, 2003, «Une correspondance de Curry-Howard fortement normalisante pour la théorie des ensembles IZF», in Computer science Logic (Lecture Notes in Computer Science, 2803), Berlin: Springer: 441–454.
  • Oppenheimer, P. et E. Zalta, 2011, «Relations et fonctions aux fondements de la logique: considérations théoriques de type», Journal of Logic and Computation, 21: 351–374.
  • Palmgren, Erik, 1998, «Sur les univers dans la théorie des types», dans Vingt-cinq ans de théorie des types constructifs (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 191–204.
  • Poincaré, 1909, «H. La logique de l'infini »Revue de métaphysique et de moral, 17: 461–482.
  • Prawitz, D., 1967, «Complétude et Hauptsatz pour la logique du second ordre», Theoria, 33: 246–258.
  • –––, 1970, «Sur la théorie de la preuve de l'analyse mathématique», dans Logique et valeur (Essais consacrés à Thorild Dahlquist à son cinquantième anniversaire), Filosofiska Studier (Filosof. Föreningen och Filosof. Inst.), N ° 9, Uppsala: Université d'Uppsala, 169-180.
  • Quine, W., 1940, «Examen de l'Église« Une formulation de la théorie simple des types »,» Journal of Symbolic Logic, 5: 114.
  • Ramsey, FP, 1926, «Les fondements des mathématiques», Actes de la London Mathematical Society, s2–25 (1), 338–384.
  • Russell, B., 1903, The Principles of Mathematics, Cambridge: Cambridge University Press.
  • –––, 1908, «La logique mathématique basée sur la théorie des types», American Journal of Mathematics, 30: 222-262.
  • –––, 1959, Mon développement philosophique, Londres, New York: Routledge.
  • Russell, B. et Whitehead, A., 1910, 1912, 1913, Principia Mathematica (3 volumes), Cambridge: Cambidge University Press.
  • Reynolds, J., 1974, «Vers une théorie de la structure des types», dans Programming Symposium (Notes de cours en informatique: volume 19), Berlin: Springer, 408–425.
  • –––, 1983, «Types, Abstraction and Parametric Polymorphism», Actes du 9e Congrès mondial de l'informatique de l'IFIP, Paris, 513-523.
  • –––, 1984, «Le polymorphisme n'est pas une théorie des ensembles. Sémantique des types de données », Notes de cours en informatique (Volume 173), Berlin: Springer, 145–156.
  • –––, 1985, «Trois approches de la structure des types. Fondements mathématiques du développement de logiciels », dans Notes de cours en informatique (volume 185), Berlin: Springer, 97-138.
  • Schiemer, G. et Reck, EH, 2013, «La logique dans les années 1930: théorie des types et théorie des modèles», Le Bulletin de la logique symbolique, 19 (4): 433–472.
  • Schütte, K., 1960, Beweistheorie, Berlin: Springer-Verlag.
  • Scott, D., 1993 «Une alternative théorique des types à ISWIM, CUCH, OWHY», Theoretical Computer Science, 121: 411–440.
  • Skolem, T., 1970, Sélection d'œuvres en logique, Jens Erik Fenstad (éd.), Oslo: Universitetsforlaget.
  • Tait, WW, 1967, «Interprétations intensionnelles des fonctionnels de type fini», Journal of Symbolic Logic, 32 (2): 198–212.
  • Takeuti, G., 1955 «Sur la conjecture fondamentale de GLC: I», Journal de la Société mathématique du Japon, 7: 249-275.
  • –––, 1967, «Preuves de cohérence des sous-systèmes d'analyse classique», The Annals of Mathematics (Second Series), 86 (2): 299–348.
  • Tarski, A., 1931, «Sur les ensembles definissables de nombres reels I», Fundamenta Mathematicae, 17: 210-239.
  • Urquhart, A., 2003, «The Theory of Types», dans The Cambridge Companion to Bertrand Russell, Nicholas Griffin (ed.), Cambridge: Cambridge University Press.
  • Voevodsky, V., 2015, «Une bibliothèque expérimentale de mathématiques formalisées basée sur des fondations univalentes», Mathematical Structures in Computer Science, 25: 1278–1294, disponible en ligne.
  • Wiener, N., 1914, «Une simplification de la logique des relations», Actes de la Cambridge Philosophical Society, 17: 387–390.
  • Weyl, H., 1946, «Mathématiques et logique», American Mathematical Monthly, 53: 2–13.
  • Zermelo, E., 1908, «Untersuchungen über die Grundlagen der Mengenlehre I», Mathematische Annalen, 65: 261-281.

Outils académiques

icône de l'homme Sep
icône de l'homme Sep
Comment citer cette entrée.
icône de l'homme Sep
icône de l'homme Sep
Prévisualisez la version PDF de cette entrée à la Friends of the SEP Society.
icône inpho
icône inpho
Recherchez cette rubrique d'entrée sur le projet d'ontologie de philosophie Internet (InPhO).
icône de papiers phil
icône de papiers phil
Bibliographie améliorée pour cette entrée chez PhilPapers, avec des liens vers sa base de données.

Autres ressources Internet

  • Kubota, K., 2018, «Fondements des mathématiques. Généalogie et aperçu », manuscrit, ébauche du 27 mars 2018.
  • [HoTT 2013], Théorie des types d'homotopie: Fondements univalents de mathématiques, Institut d'études avancées.

Recommandé: