Transfinito edizioni

Giancarlo Calciolari
Il romanzo del cuoco

pp. 740
formato 15,24x22,86

euro 35,00
acquista

libro


Giancarlo Calciolari
La favola del gerundio. Non la revoca di Agamben

pp. 244
formato 10,7x17,4

euro 24,00
acquista

libro


Christian Pagano
Dictionnaire linguistique médiéval

pp. 450
formato 15,24x22,86

euro 22,00
acquista

libro


Fulvio Caccia
Rain bird

pp. 232
formato 15,59x23,39

euro 15,00
acquista

libro


Jasper Wilson
Burger King

pp. 96
formato 14,2x20,5

euro 10,00
acquista

libro


Christiane Apprieux
L’onda e la tessitura

pp. 58

ill. colori 57

formato

cm 33x33

acquista

libro


Giancarlo Calciolari
La mela in pasticceria. 250 ricette

pp. 380
formato 15x23

euro 14,00
euro 6,34

(e-book)

acquista

libro

e-book


Riccardo Frattini
In morte del Tribunale di Legnago

pp. 96
formato cartaceo 15,2x22,8

euro 9,00
e-book

euro 6,00

acquista

libro

e-book


Giancarlo Calciolari
Imago. Non ti farai idoli

pp. 86
formato 10,8x17,5

euro 7,20
carrello


Giancarlo Calciolari
Pornokratès. Sulla questione del genere

pp. 98
formato 10,8x17,5

euro 7,60
carrello


Giancarlo Calciolari
Pierre Legendre. Ipotesi sul potere

pp. 230
formato 15,24x22,86

euro 12,00
carrello


TRANSFINITO International Webzine

Prélude à la lecture de Gödel

Patrice Pissavin
(21.02.2011)

Commentaires sur les implications des théorèmes de Gödel de 1931 et apparentés

Le présent texte a été rédigé à partir d’une critique détaillée que nous avons consacrée à un article de vulgarisation sur les implications des théorèmes de Gödel de 1931 et apparentés. Il nous donne l’occasion de dénoncer un certain nombre d’erreurs que l’on trouve couramment sur ce sujet. Il constitue ainsi une sorte de prélude à une synthèse plus approfondie qui sera rédigée après l’achèvement de notre doctorat.

Nous avons regroupé nos commentaires en cinq parties :

Signification de la vérité en logique et en mathématiques,
Sens des termes métamathématiques de consistance, de complétude et de décidabilité,
Systèmes formels concernés par les résultats d’incomplétude, d’indécidabilité et d’impossibilité d’établir la consistance par des moyens finitistes,
Intuition et hypothèses a priori en métamathématique,
Implications philosophiques des théorèmes de Gödel de 1931 et apparentés.

Pour ne pas alourdir notre propos nous ne justifierons pas les résultats d’ordre factuels, en logique et en mathématiques, sur lesquels nous nous appuyons.

Les termes qui sont pris dans leur sens précis en logique formelle sont en italique (mais seule la définition des plus importants est donnée dans le texte).

JPEG - 206 Kb
Hiko Yoshitaka, "Un rêve de Lacan", 2007


Signification de la vérité en logique et en mathématiques



La principale particularité de la logique formelle est de distinguer dérivabilité et vérité d’un énoncé logique ou mathématique, contre l’opinion commune, contre la tradition et même contre la pratique mathématique courante. Mais si la notion de dérivabilité se conçoit assez bien (elle est souvent identifiée à la logique formelle par l’opinion commune), celle de vérité est plus délicate.

Il y a bien sûr la vérité au sens intuitif, correspondant à ce qui est reconnu comme "évidemment vrai" (comme 2 + 2 = 4) ou donnée par ce que "veut dire" l’énoncé lui-même (l’exemple typique en est l’énoncé G de Gödel, qui code l’affirmation de sa propre non dérivabilité). Le problème majeur de ce sens est qu’il n’est pas rigoureusement défini et ne bénéficie pas d’un consensus général des mathématiciens (au-delà du fini).

Les logiciens ont donc été amenés à introduire une définition rigoureuse de la "vérité", au travers de ce que l’on appelle une « théorie de la vérité[1] ». La plus connue est celle de Tarski, mais il en existe d’autres. Et c’est par rapport à cette définition (donc par rapport à une théorie de la vérité) que, par exemple, la complétude est définie (depuis A. Tarski). La vérité au sens de Tarski constitue alors une formalisation tout à fait naturelle de la vérité au sens intuitif, à condition de se référer au modèle standard de la théorie.

Sens des termes métamathématiques de consistance, de complétude et de décidabilité


Il existe plusieurs définitions différentes de la consistance (qui se rapportent toutes à un système formel). Toutefois, en se limitant à la logique classique, la consistance simple, qui correspond à la non contradiction syntaxique, peut être considérée comme suffisante pour notre propos.

Au contraire, une difficulté majeure associée à l’usage du terme : « complétude » en logique formelle, est la multiplicité de ses sens (qui se rapportent également tous à un système formel). La synthèse des deux recensions les plus récentes[2] conduit à pas moins de quatorze acceptions différentes (certaines étant coextensives[3]), et cela nonobstant les variations d’appellation pour un même sens.
Les cinq principales définitions (qui peuvent se ramener à quatre) sont les suivantes :

complétude syntaxique, « pour tout énoncé, celui-ci est dérivable ou réfutable »,

complétude sémantique par rapport à un modèle, « il existe au moins un modèle tel que tout énoncé vrai dans ce modèle est dérivable », qui est coextensive à la complétude syntaxique,
saturation, « l’ajout au système formel de n’importe quel énoncé non dérivable, le rend simplement inconsistant »,
équivalence entre modèles, « tout énoncé vrai dans un modèle est vrai dans tous »,

complétude sémantique, « pour tout énoncé, si celui-ci est valide (vrai simultanément dans l’ensemble des modèles), il est dérivable ».
Mais surtout, aucun de ces sens ne traduit véritablement le sens du langage courant suivant lequel l’incomplétude indique qu’il "manque quelque chose"[4].

Pour la décidabilité d’un système formel il existe essentiellement une seule définition[5].

Mais une complication est introduite par le fait que le terme de décidabilité (i.e. d’indécidabilité) ne s’applique pas seulement à un système formel mais également à un énoncé[6] et à un problème[7].
Et pour un problème, il est nécessaire de distinguer entre son indécidabilité et son insolubilité :

si la formulation du problème inclut une exigence d’effectivité, une démonstration d’indécidabilité constitue au contraire la résolution du problème[8],
sinon, une démonstration d’indécidabilité ne traduit que l’insolubilité algorithmique du problème : c’est-à-dire son insolubilité lorsque l’on s’impose l’exigence supplémentaire d’effectivité. Elle n’interdit donc aucunement la possibilité de résoudre le problème en faisant appel à une procédure adaptée à chacune de ses instances.



Systèmes formels concernés par les résultats d’incomplétude, d’indécidabilité et d’impossibilité d’établir la consistance par des moyens finitistes


Une double confusion est souvent commise par les non connaisseurs de la logique formelle, qui supposent que :

les résultats d’incomplétude, d’indécidabilité (et d’incapacité à établir la consistance par des moyens finitistes), vont nécessairement ensemble,
ces résultats concernent tout système formel logique, toute théorie mathématique.

Il n’en est évidement rien, comme l’énonciation des principaux résultats "positifs" permet de s’en convaincre immédiatement :
démonstration finitiste de consistance, du calcul des propositions (Post_1921),
complétude sémantique, du calcul des propositions (Post_1921) et de toute théorie du calcul des prédicats du 1er ordre (Gödel_1930),
décidabilité, du calcul des propositions (Post_1921), du calcul pur des prédicats du 1er ordre monadique (Löwenheim_1915), de l’arithmétique récursive limitée à l’addition (Presburger_1929),
complétude syntaxique et décidabilité de l’algèbre et de la géométrie élémentaire (Tarski_1939/1967).

Enfin, à ces résultats historiques, il convient d’ajouter une remarque cruciale vis-à-vis de la velléité d’appliquer les résultats d’indécidabilité et (ou) d’incomplétude au-delà de la logique et des mathématiques. Cette remarque est qu’aucun de ces résultats "négatifs" ne peut concerner un système dont le domaine d’application est fini, même si celui-ci est aussi grand que l’on veut[9].



Intuition et hypothèses a priori en métamathématique


Nous avons déjà signalé le fondement intuitif de toute théorie de la vérité. Mais la dérivabilité fait également implicitement référence à l’intuition, dans le choix des règles qui caractérisent tout système formel (règles qui sont retenues dans la mesure où elles traduisent le comportement de la logique et des mathématiques intuitives).
Au-delà, il convient de dissiper deux malentendus répandus, lés à l’emploi du terme « absolu » dans les textes concernant le "problème des fondements" (des mathématiques) :

ce terme n’a été utilisé qu’à propos des démonstrations de consistance, qui sont les seules à se rapporter directement à ce "problème des fondements" (les aspects de complétudes et de décidabilité étant ici secondaires),
il a été introduit simplement pour s’opposer aux démonstrations de consistance relatives (d’un système formel par rapport à un système formel plus fondamental, se ramenant in fine à l’arithmétique) ; il n’en est pas moins associé à la nécessité de disposer d’un fond minimal de logique et de mathématiques, nécessairement extérieur aux systèmes formels et aux théories formalisées, accepté a priori, c’est-à-dire sur la base intuitive de son évidence. Ce fond commun minimal se traduit par des critères « finitistes » ou « constructivistes ».

Il est donc clair que les logiciens, à commencer par D. Hilbert, n’ont pas imaginé pouvoir justifier la consistance des mathématiques ex nihilo. Ils ont au contraire admis la nécessité pour cela, de s’appuyer sur ce fond "intuitif" minimal. Par contre, il n’y a pas eu de consensus sur le contenu (et surtout l’étendue) de ce socle commun[10].

Et une démonstration "absolue" de consistance (par extension de décidabilité, éventuellement de complétude,) revient à la seule obligation à se limiter, en dehors des moyens du système formel lui-même, à ces exigences finitistes (ou constructivistes). Celles-ci se traduisent en particulier par les critères généraux d’effectivité[11] requis pour un système formel. Ces exigences et ces critères s’appliquent à tout système formel (toute théorie).

Au final, il est donc clair que la logique formelle ne s’affranchit pas d’une référence à l’intuition, comme cela est parfaitement exprimé par J. Ladrière[12] : « Comme toute démonstration prend son point d’appui dans l’intuition, les critères formels eux-mêmes ne peuvent être jugés en définitive, qu’au nom d’exigences intuitives. Il n’y a pas de recours ultime dans le formel ».



Interprétation philosophique des théorèmes de Gödel de 1931 et apparentés

Nous avons beaucoup insisté sur ce que les théorèmes de Gödel de 1931 (et apparentés) n’impliquent pas. Il reste évidemment la question de savoir ce qu’ils impliquent, en particulier sur le plan philosophique. Trois grandes questions ont en fait été posées à ce sujet :

ces résultats peuvent-ils s’étendre à d’autres disciplines (la physique en particulier) et introduisent-ils une limitation absolue aux possibilités d’une « théorie du Tout » ?

dans quelle mesure peuvent-t-ils s’appliquer à l’esprit humain et entraînent-ils l’impossibilité (en principe) de créer une machine "intelligente" ?

au-delà d’une limitation de la connaissance, correspondent-ils à une limitation de la raison et de la pensée (comme l’a défendu J. Ladrière) ?
La première question n’a été l’objet de travaux sérieux que récemment. Elle a généralement été abordée via la théorie algorithmique de l’information et les résultats de G. Chaitin[13]. Des éléments de réponse ont été proposés, mais qui restent parcellaires et n’ont pas véritablement permis de conclure.

La seconde question, beaucoup plus étudiée, s’est traduite par un débat toujours en vigueur depuis les années soixante (controverse Lucas / Hofstadter / Penrose / Feferman, Delahaye). Tout ce qu’il est possible d’en dire aujourd’hui et qu’aucun argument décisif n’a été produit et qu’aucun consensus ne s’est dégagé dans les communautés scientifique et philosophique.

La dernière question est clairement plus philosophique que les précédentes. Aucun travail sérieux ne lui a été explicitement consacré, depuis celui de J. Ladrière en 1957 (déjà cité). Cette question est explicitement le sujet de notre doctorat. Nous nous contenterons simplement de préciser pour le moment, qu’une réponse ne peut certainement pas y être dissociée de l’engagement ontologique en philosophie des mathématiques, de son auteur (qui est un réalisme "platonicien" au sens fort dans le cas de K. Gödel lui-même).

Au final, les erreurs que nous dénonçons concernent essentiellement cinq points, qui modifient radicalement l’analyse qui est souvent proposée, des implications des théorèmes de Gödel de 1931, au-delà de la logique et des mathématiques :

les caractéristiques métamathématiques de complétude, de décidabilité et d’aptitude à établir la consistance de manière finitiste, sont a priori des propriétés indépendantes d’un système formel ; il se trouve qu’elles ont été simultanément invalidées dans le cas de l’arithmétique récursive[14],
en logique formelle, le sens du mot « incomplétude » ne correspond pas au sens du langage courant selon lequel « il manque quelque chose »,
l’indécidabilité, qui se rapporte à une procédure effective universelle et figée, n’entraîne pas l’insolubilité, en laissant la possibilité de faire appel à une procédure adaptée à l’instance du problème posé,
les théorèmes de Gödel de 1931 et apparentés n’invalident pas la complétude sémantique de tout système formel du calcul des prédicats du 1er ordre [15] ; ils ne s’appliquent certainement pas à tout système logique et mathématique : un certain nombre de théories mathématiques sont décidables ; a fortiori, aucun de ces résultats "négatifs" ne peut s’appliquer à un système dont le domaine d’application est fini,
les limitations fondamentales liées à la démarche même de formalisation sont indéniables, mais elles ne sont pas une conséquence des théorèmes de 1931[16] (elles correspondent aux critères de finitisme retenus a priori pour l’établissement des démonstrations métamathématiques). Elles s’appliquent donc à tous les systèmes formels.

Enfin, concernant les implications philosophiques envisagées de ces théorèmes, il est indispensable d’en distinguer la part de l’ontologie sous-jacente[17]. Cela nous conduit à relativiser la portée des conclusions qui en sont quelquefois déduites, en particulier concernant les limitations de la connaissance qui en résulteraient.

Patrice Pissavin

patrice.pissavin@wanadoo.fr

Doctorant à l’IHPST (Paris I) en philosophie de la logique

9 juillet 2007

1 Qui fait également intervenir le type de logique utilisé : logique classique ou l’une des multiples logiques non classiques.

2 Sinaceur_1990, Awodey-Reck_2002.

3 Vérifiées dans les mêmes conditions (tout en ayant un sens différent).

4 Avec deux réserves vraisemblablement historiquement à l’origine du choix de ce mot. Dans le cas (usuel) de la complétude sémantique, celle-ci se traduit par le fait que tous les énoncés vrais ne peuvent pas être dérivés. Mais le "manque" est alors à relier au sens précis de « vrai » et de « dérivable » en logique formelle. Pour la complétude nommée saturation, le choix du mot de « complétude » peut se comprendre (même si celui de « saturation » paraît justement plus approprié). Mais il s’agit alors de la complétude en un sens à la fois particulier et fort (pour les théories du calcul des prédicats du 1er ordre, la saturation et la complétude syntaxique sont coextensives).

5 Nous disposons d’une procédure, d’un algorithme, effectif : unique, permettant de répondre en un nombre fini d’étapes et de manière certaine, à la question du caractère dérivable ou non de tout énoncé du système formel.

6 Un énoncé indécidable est un énoncé qui ne peut être ni dérivé ni réfuté dans un système formel (dont l’existence traduit donc l’incomplétude syntaxique de ce système formel), cela sans aucune exigence d’effectivité.

7 Un problème est décidable s’il existe une procédure effective : unique, permettant au bout d’un nombre fini de pas, de réponde de façon certaine « oui » ou « non » à la question posée par le problème, pour chacune de ses instances (en nombre infini). Un système formel décidable constitue un cas particulier de problème décidable.

8 Exemple du 10ème problème de Hilbert (sur l’existence d’un algorithme effectif permettant de savoir si toute équation diophantienne possède ou non une solution), résolu (négativement) par Y. Matijasevic en 1970.

9 C’est-à-dire, par exemple, égal à un "Googleplex" (1010 à la puissance 100) états, soit un nombre très supérieur à la quantité d’information contenue dans l’ensemble de l’Univers observable (estimée à 10120).

10 Sa version minimale se traduit par la restriction à un domaine fini et borné (excluant l’induction) ; elle correspond au finitisme initial de D. Hilbert.
Une première extension consiste à admettre un schéma de récursion (récurrence) fini mais non borné et la quantification sur un ensemble fini mais non borné ; elle correspond à un finitisme étendu, qui a été accepté ensuite par D. Hilbert.
Une extension plus importante consiste à admettre l’infini potentiel (en supprimant les bornes du finitisme étendu) ; elle correspond au constructivisme classique (celui de l’intuitionnisme par exemple).
Une extension plus problématique (dont le caractère "intuitif" est controversé) est l’induction transfinie jusqu’à ε0 ; son importance tient au fait qu’elle permet une démonstration de consistance de l’arithmétique (Gentzen_1936).
La limite supérieure, communément admise, est le refus de prendre en compte l’infini en acte (toute totalisation infinie), donc le transfini.

11 Correspondant en pratique à une exigence de récursivité des dérivations.

12 « Les limitations internes des formalismes », § 144 ; Gauthier-Villars ; 1957.

13 Qui ont un lien direct avec le théorème de Church de 1936 (qui peut lui-même être considéré comme une généralisation des théorèmes de Gödel de 1931, via la thèse de Church-Turing).

14 Incomplétude syntaxique (ou sémantique par rapport au modèle de l’arithmétique naturel).

15 Qui s’applique donc également à l’arithmétique récursive (Gödel_1930).

16 Suivant l’image de Martin_1964 : « ceux-ci ne reviennent pas à établir laborieusement qu’il est impossible de se tirer de l’eau en se saisissant soi-même aux cheveux ».

17 Qui constitue une option particulière de philosophie des mathématiques (quelle qu’elle soit).


Gli altri articoli della rubrica Logica :












| 1 | 2 |

6.10.2016