Imprédicativité - Impredicativity

En mathématiques , en logique et en philosophie des mathématiques , quelque chose d' imprédicatif est une définition auto-référencée . En gros, une définition est imprédicative si elle invoque (mentionne ou quantifie sur) l'ensemble en cours de définition, ou (plus communément) un autre ensemble qui contient l'objet en cours de définition. Il n'y a pas de définition précise généralement acceptée de ce que signifie être prédicatif ou imprédicatif. Les auteurs ont donné des définitions différentes mais liées.

Le contraire de l'imprédicativité est la prédicativité, qui consiste essentiellement à construire des théories stratifiées (ou ramifiées) où la quantification sur des niveaux inférieurs aboutit à des variables d'un type nouveau, distinctes des types inférieurs sur lesquels la variable se situe. Un exemple prototypique est la théorie des types intuitionnistes , qui conserve la ramification de manière à écarter l'imprédicativité.

Le paradoxe de Russell est un exemple célèbre de construction imprédicative - à savoir l' ensemble de tous les ensembles qui ne se contiennent pas. Le paradoxe est qu'un tel ensemble ne peut pas exister: s'il existait, on pourrait se demander s'il se contient ou non - s'il existe alors par définition il ne devrait pas, et s'il n'existe pas alors par définition il devrait.

La plus grande borne inférieure d'un ensemble X , glb ( X ) , a également une définition imprédicative : y = glb ( X ) si et seulement si pour tous les éléments x de X , y est inférieur ou égal à x , et tout z inférieur supérieur ou égal à tous les éléments de X est inférieur ou égal à y . Cette définition quantifie sur l'ensemble (potentiellement infini , selon l' ordre en question) dont les membres sont les bornes inférieures de X , dont l'une est le glb lui-même. Par conséquent, le prédicativisme rejetterait cette définition.

Histoire

Les termes «prédicatif» et «imprédicatif» ont été introduits par Russell (1907) , bien que le sens ait un peu changé depuis.

Solomon Feferman fournit une revue historique de la prédicativité, en la reliant aux problèmes de recherche actuels en suspens.

Le principe du cercle vicieux a été suggéré par Henri Poincaré (1905-6, 1908) et Bertrand Russell à la suite des paradoxes comme une exigence sur des spécifications d'ensemble légitimes. Les ensembles qui ne satisfont pas à l'exigence sont appelés imprédicatifs .

Le premier paradoxe moderne est apparu avec la question A sur les nombres transfinis de Cesare Burali-Forti en 1897 et allait devenir le paradoxe Burali-Forti . Cantor avait apparemment découvert le même paradoxe dans sa théorie des ensembles «naïve» (de Cantor) et cela est devenu le paradoxe de Cantor . Russell a pris conscience du problème en juin 1901 avec sa lecture du traité de Frege sur la logique mathématique, son Begriffsschrift de 1879 ; la peine incriminée à Frege est la suivante:

D'un autre côté, il se peut aussi que l'argument soit déterminé et la fonction indéterminée.

En d'autres termes, étant donné f ( a ), la fonction f est la variable et a est la partie invariante. Alors pourquoi ne pas substituer la valeur f ( a ) à f elle-même? Russell a rapidement écrit à Frege une lettre soulignant que:

Vous déclarez ... qu'une fonction aussi, peut agir comme un élément indéterminé. J'y croyais autrefois, mais maintenant ce point de vue me semble douteux à cause de la contradiction suivante. Soit w le prédicat: être un prédicat qui ne peut pas être prédicat par lui-même. W peut-il être fondé sur lui-même? De chaque réponse découle son contraire. Là, nous devons conclure que w n'est pas un prédicat. De même, il n'y a pas de classe (en tant que totalité) de ces classes qui, prises chacune comme une totalité, n'appartiennent pas à elles-mêmes. J'en conclus que dans certaines circonstances, une collection définissable ne forme pas une totalité.

Frege a rapidement répondu à Russell en reconnaissant le problème:

Votre découverte de la contradiction m'a causé la plus grande surprise et, je dirais presque, la consternation, car elle a ébranlé la base sur laquelle je comptais construire l'arithmétique.

Alors que le problème a eu des conséquences personnelles défavorables pour les deux hommes (tous deux avaient des travaux chez les imprimeurs qui ont dû être corrigés), van Heijenoort observe que «le paradoxe a secoué le monde des logiciens et les grondements se font encore sentir aujourd'hui. ... Le paradoxe de Russell , qui utilise les notions nues d'ensemble et d'élément, tombe carrément dans le champ de la logique. Le paradoxe a été publié pour la première fois par Russell dans Les principes des mathématiques (1903) et y est discuté en détail ... ". Russell, après six ans de faux départs, finira par répondre à la question avec sa théorie des types de 1908 en «proposant son axiome de réductibilité . Il dit que toute fonction est coextensive avec ce qu'il appelle une fonction prédicative : une fonction dans laquelle les types de les variables apparentes ne dépassent pas les types d'arguments ". Mais cet «axiome» a rencontré une résistance de tous les côtés.

Le rejet des objets mathématiques définis de manière imprévisible (tout en acceptant les nombres naturels comme compris classiquement) conduit à la position dans la philosophie des mathématiques connue sous le nom de prédicativisme, préconisée par Henri Poincaré et Hermann Weyl dans son Das Kontinuum . Poincaré et Weyl ont soutenu que les définitions imprédicatives ne posent problème que lorsqu'un ou plusieurs ensembles sous-jacents sont infinis.

Ernst Zermelo dans son 1908 "Une nouvelle preuve de la possibilité d'un bon ordre" présente une section entière "b. Objection concernant la définition non prédicative " où il plaide contre "Poincaré (1906, p. 307) [qui déclare que] une définition n'est «prédicative» et logiquement admissible que si elle exclut tous les objets qui dépendent de la notion définie, c'est-à-dire qui peuvent de quelque manière que ce soit être déterminés par elle ". Il donne deux exemples de définitions imprédicatives - (i) la notion de chaînes de Dedekind et (ii) "en analyse lorsque le maximum ou le minimum d'un ensemble" complété "de nombres Z précédemment défini est utilisé pour d'autres inférences. Cela se produit, par exemple , dans la preuve bien connue de Cauchy ... ". Il termine sa section par l'observation suivante: «Une définition peut très bien s'appuyer sur des notions équivalentes à celle qui est définie; en effet, dans toute définition definiens et definiendum sont des notions équivalentes, et le strict respect de l'exigence de Poincaré ferait que chaque définition , d'où toute science, impossible ».

L'exemple de Zermelo du minimum et du maximum d'un ensemble de nombres "complété" précédemment défini réapparaît dans Kleene 1952: 42-42 où Kleene utilise l'exemple de la borne inférieure dans sa discussion des définitions imprédicatives; Kleene ne résout pas ce problème. Dans les prochains paragraphes , il discute la tentative de Weyl dans son 1918 Das Kontinuum ( Continuum ) pour éliminer les définitions imprédicatives et son incapacité à conserver le « théorème qu'un arbitraire non vide ensemble M de nombres réels ayant une limite supérieure a une borne supérieure ( cf. également Weyl 1919) ".

Ramsey a fait valoir que les définitions "imprédicatives" peuvent être inoffensives: par exemple, la définition de "personne la plus grande de la pièce" est imprédicative, car elle dépend d'un ensemble de choses dont elle est un élément, à savoir l'ensemble de toutes les personnes dans le chambre. Concernant les mathématiques, un exemple de définition imprédicative est le plus petit nombre d'un ensemble, formellement défini comme: y = min ( X ) si et seulement si pour tous les éléments x de X , y est inférieur ou égal à x , et y est dans X .

Burgess (2005) discute des théories prédicative et imprédicatives longuement, dans le contexte de Frege logique de, l' arithmétique de Peano , l' arithmétique du second ordre , et la théorie des ensembles axiomatique .

Voir également

• Gödel, Escher, Bach
• Polymorphisme améliorant
• Logicisme
• Le paradoxe de Richard

Remarques

Les références

• "Définitions Prédicatives et Imprédicatives" . Encyclopédie Internet de la philosophie .
• Article de PlanetMath sur le prédicativisme
• John Burgess , 2005. Correction de Frege . Princeton Univ. Presse.
• Solomon Feferman , 2005, « Prédicativité » dans le manuel d'Oxford de philosophie des mathématiques et de la logique . Presse d'université d'Oxford: 590–624.
• Russell, B. (1907), "Sur certaines difficultés de la théorie des nombres transfinis et des types d'ordre" , Proc. Mathématiques de Londres. Soc. , s2–4 (1): 29–53, doi : 10.1112 / plms / s2-4.1.29
• Stephen C. Kleene 1952 (édition de 1971), Introduction to Metamathematics , North-Holland Publishing Company, Amsterdam NY, ISBN   0-7204-2103-9 . En particulier cf. son §11 Les Paradoxes (pp. 36–40) et §12 Premières inférences des paradoxes DÉFINITION IMPRÉDICATIVE (p. 42). Il déclare que ses quelque 6 exemples (célèbres) de paradoxes (antinomies) sont tous des exemples de définition imprédicative, et dit que Poincaré (1905–6, 1908) et Russell (1906, 1910) "ont énoncé la cause des paradoxes de mentir dans ces définitions imprédicatives »(p. 42), cependant,« les parties des mathématiques que nous voulons retenir, en particulier l'analyse, contiennent également des définitions imprédicatives ». (ibid.). Weyl dans son 1918 ("Das Kontinuum") a tenté de dériver autant d'analyse que possible sans l'utilisation de définitions imprédicatives, "mais pas le théorème qu'un ensemble arbitraire non vide M de nombres réels ayant une borne supérieure a au moins borne supérieure (CF. également Weyl 1919) "(p. 43).
• Hans Reichenbach 1947, Éléments de logique symbolique , Dover Publications, Inc., NY, ISBN   0-486-24004-5 . Cf. son §40. Les antinomies et la théorie des types (p. 218 - où il montre comment créer des antinomies, y compris la définition de l' imprédicable elle-même ("La définition de" imprédicable "est-elle imprévisible?"). Il prétend montrer des méthodes pour éliminer les "paradoxes de la syntaxe "(" paradoxes logiques ") - par l'utilisation de la théorie des types - et" les paradoxes de la sémantique "- par l'utilisation du métalangage (sa" théorie des niveaux de langage "). Il attribue la suggestion de cette notion à Russell et plus concrètement à Ramsey.
• Jean van Heijenoort 1967, troisième tirage 1976, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 , Harvard University Press, Cambridge MA, ISBN   0-674-32449-8 (pbk.)