Recension du livre « Forever Undecided » de Raymond Smullyan

un livre que Smullyan dédicace à tous les croyants cohérents qui ne sauront jamais qu’ils sont cohérents
samedi 19 décembre 2015
par  Alain BUSSER

Le livre de Smullyan est une parabole. Bon, évidemment, il ne ressemble pas spécialement à ça :

Non, il s’agit d’une parabole (rhétorique), basée sur le fait que syntaxiquement parlant, les deux opérateurs modaux suivants se ressemblent beaucoup :

  • je peux démontrer que p
  • je crois que p

Par exemple, si on croit que p est vraie, en général, on croit aussi qu’on le croit. De même, si on peut démontrer p, on démontre ainsi sa démontrabilité. Raymond Smullyan, comme d’habitude, essaye d’expliquer par parabole les théorèmes d’incomplétude de Gödel, mais cette fois-ci, il insiste plus sur le second théorème d’incomplétude (si l’arithmétique est cohérente, on ne peut pas démontrer arithmétiquement la cohérence de l’arithmétique), et dans les faits, toute la partie centrale de ce livre est une excellente introduction à la logique doxastique.

JPEG - 141.2 ko
Olivier Rameau explique à ses amis du monde onirique de rêverose comment il conçoit la logique doxastique rêverosienne, dans « les disparus du bayou Plala » (dessins de Dany, scénario de Greg)

Cette recension insistera donc sur la logique doxastique plus que sur les travaux de Gödel.

Décrire l’auteur est une véritable aventure en soi, tant sa vie est exceptionnelle :

Il a commencé comme virtuose du piano :

Puis il est devenu prestidigitateur :

Il a même vendu des aspirateurs

Lors de l’entretien d’embauche, une des questions était

Verriez-vous une objection à dire quelques mensonges ?

Ce à quoi, pour obtenir le travail, il a répondu « non ». Mentait-il alors ?

Puis il a étudié les mathématiques, notamment avec Rudolf Carnap, qui l’a orienté vers la logique, et plus particulièrement vers Alonzo Church qui fut son directeur de thèse. En plus de sa passion pour le jeu d’échecs, il a publié aussi beaucoup d’ouvrages, la plupart de vulgarisation, sur la logique et plus particulièrement sur les questions d’indécidabilité. Il est également connu comme auteur de l’énigme la plus difficile du monde. Certaines de ses énigmes sont en ligne. Smullyan est également l’auteur de plusieurs ouvrages sur le taoïsme...

Il adore aussi les blagues sur les maths

Une histoire qu’il aime raconter est celle-ci : Deux logiciens arrivent en avance à un colloque et l’amphithéatre est vide, mais sur le tableau figure cette inscription à la craie :

Le premier dit à l’autre : « Tu y crois à ça » ? Ce à quoi le second répond « Non ! Seul un idiot peut croire en une telle phrase ! »

Smullyan est aussi celui qui a fait connaître les blagues sur la légendaire distraction de Norbert Wiener et l’attitude surprenante de John Von Neumann


La première partie du livre traite des purs et des pires :

  • Les purs disent toujours la vérité ;
  • Les pires mentent toujours [1]

Voici les traductions françaises de la plupart d’entre eux :

exercices traduits en français le source
PDF - 66.1 ko
LaTeX - 6 ko

On peut les résoudre avec le calcul booléen en Prolog.

Solution avec CoffeeScript

Les exemples en CoffeeScript ci-dessous sont prévus pour être utilisés avec alcoffeethmique. Ceci, pour programmer les boucles en français et afficher directement dans la page web.

On peut explorer les différentes variantes avec des boucles (chaque variable « A », « B » et « C » prenant alternativement les valeurs « faux » et « vrai »). On commence par définir des utilitaires :

  • l’objet « purs » définit une valeur booléenne (initialement « faux ») pour chacun des insulaires A, B et C
purs = { "A": false, "B": false, "C": false}
  • une fonction d’affichage qui pour chaque personnage A, B et C, dit « est un pur » si sa pureté est « true » et « est un pire » sinon :
dit_solution = (obj) ->
        texte = ""
        for  X of obj
                texte += "#{X} est #{tab[obj[X]]}, "
        affiche texte
  • le tableau sur lequel on va boucler est résumé en « V » :
V = [true,false]
  • Un autre tableau, appelé « tab », sert dans la fonction d’affichage :
tab = [ ]
tab[true] = "est un pur"
tab[false] = "est un pire"
  • enfin la fonction essentielle, décrivant le fonctionnement de la parole :
dit = (X,p) -> purs[X]==p

En effet, X dit que p si et seulement p est équivalent à la pureté de X, soit :

  1. X est pur et p est vrai,
  2. ou X est pire et p est faux.

Voici les ébauches de solutions des premiers exercices du pdf joint à ce article, traduits en CoffeeScript :

Tout d’abord, les utilitaires « tout-en-un » :

purs = { "A": false, "B": false, "C": false}
dit_solution = (obj) ->
        texte = ""
        for  X of obj
                texte += "#{X} est #{tab[obj[X]]}, "
        affiche texte
V = [true,false]
tab = [ ]
tab[true] = "est un pur"
tab[false] = "est un pire"
dit = (X,p) -> purs[X]==p
Albert, Bernard et Charles sont dans un jardin. Un passant demande à Albert : « êtes-vous un Pur ou un Pire ? ». Albert répond mais le passant n’entend pas bien la réponse ; alors il demande à Bernard « qu’est-ce qu’il a dit ? ». Bernard répond : « il a dit qu’il est un Pire ». Mais Charles dit alors « ne croyez pas ce que dit Bernard, il ment ».

On veut savoir ce que sont B et C (pour A on ne peut pas savoir) :

pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                pour c dans V
                        purs.C = c
                        si dit("B",dit("A",not purs.A)) et dit("C",not purs["B"]) et dit("C",dit("A",purs["A"]))
                                dit_solution purs

Le script donne deux réponses, mais seule la nature de A diffère entre les deux, ce qui répond à la question.

Albert, Boris et Christian sont dans un jardin ; un passant demande à Albert « combien y a-t-il de Purs parmi vous ? » . Mais il n’entend pas bien la réponse et le passant demande à Boris « qu’est-ce qu’il a dit ? ». Boris répond « il a dit qu’il y a un Pur parmi nous ». Mais Christian dit alors « ne croyez pas ce que dit Boris, il ment ».

On demande la nature de B et de C.

pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                pour c dans V
                        purs.C = c
                        si dit("B",purs.A ou purs.B ou purs.C) et dit("C",not purs.B)
                                dit_solution purs

Comme précédemment, ce script donne deux solutions, qui là encore, ne différent que par la nature de A.

Achille et Bellerophon discutent. Achille dit « au moins l’un de nous est un Pire »

On demande leur nature. Ici l’objet « purs » ne comporte que deux clés, A et B. Et on ne boucle que sur 4 possibilités :

pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                si dit("A",not purs.A or not purs.B)
                        dit_solution purs

Il n’y a bien qu’une seule solution.

Adrien dit « ou bien je suis un Pire, ou bien Bastien est un Pire ».

L’unique solution est donnée par

pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                si dit("A",not purs.A or not purs.B)
                        dit_solution purs
Variante mais A dit « ou bien je suis un Pire, ou bien 2+2=5 »

Il n’y a pas de solution :

pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                si dit("A",not purs.A or 2+2==5)
                        dit_solution purs
Adèle, Barbara et Camille sont interviewées. Adèle dit « nous sommes toutes des Pires ». Barbara dit « une seule d’entre nous est une Pure ».

L’affirmation de B est longue à écrire (disjoonction de conjonctions avec négations). Mais la variante « une au moins est pure » donne deux solutions, entre lesquelles il est facile de trouver la bonne :

pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                pour c dans V
                        purs.C = c
                        si dit("A",not purs.A et not purs.B et not purs.C) et dit("B",purs.A ou purs.B ou purs.C)
                                dit_solution purs
Variante mais l’affirmation de Barbara est « une seule d’entre nous est une Pire »

Comme précédemment, la version simplifiée « l’une au moins de nous est une pire » a deux solutions mais une seule des deux comprend une seule pire. On peut donc trouver laquelle :

pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                pour c dans V
                        purs.C = c
                        si dit("A",not purs.A et not purs.B et not purs.C) et dit("B",not purs.A ou not purs.B ou not purs.C)
                                dit_solution purs
Alain et Bertrand rencontrent un journaliste. Alain dit « je suis un Pire mais Bertrand ne l’est pas ».
pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                si dit("A",not purs.A et purs.B)
                        dit_solution purs
Alice, Béatrice et Carine sont interviewées. « Alice dit Béatrice est une Pire ». Béatrice répond « Alice et Carine sont pareilles ».

Seule la nature de C est demandée ; en effet le script suivant donne deux solutions :

pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                pour c dans V
                        purs.C = c
                        si dit("A",not purs.B) et dit("B",purs.A == purs.C)
                                dit_solution purs
Variante où Alice dit « Béatrice et Carine sont pareilles ». La journaliste demande alors à Carine « Est-ce qu’Aline et Béatrice sont pareilles » ?

Il y a 4 solutions avec ce script :

pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                pour c dans V
                        purs.C = c
                        si dit("A",purs.B == purs.C) et dit("B",purs.A == purs.C)
                                dit_solution purs

Smullyan commence donc par donner des énigmes basées sur les purs, les pires, les martiens et les vénusiens (qui est pur ? qui est pire ? quelle question poser pour savoir quelque chose, sans connaître la nature de son interlocuteur ?) et s’en sert pour introduire la logique propositionnelle. Par exemple, si A dit « si je suis un pur alors B aussi », on peut traduire l’énoncé ainsi (A est un pire ou B est un pur aussi) :

pour a dans V
        purs.A = a
        pour b dans V
                purs.B = b
                si dit("A",not purs.A ou purs.B)
                       dit_solution purs

Il clôt cette partie consacrée à la logique propositionnelle par la définition de l’incohérence (ou inconsistence) d’une théorie : Une théorie est incohérente si on peut y démontrer que 2+2=5.


La partie consacrée aux logiques modales commence par ce paradoxe :

L’autre jour, je suis allé à Puropira, et j’ai rencontré un habitant qui m’a dit : « Tu ne croiras jamais que je suis un pur ».

Faut-il me croire quand je raconte cette histoire ?

Cette situation est impossible si on remplace « croire » par « savoir ». Dans la suite, la lettre B sera mise devant une proposition pour dire qu’on y croit [2]. Par exemple, si je crois que 2+2=5 j’écrirai en abrégé B(2+2=5).

Je crois qu’il y a plusieurs sortes de croyants

Pour étudier ce paradoxe, Smullyan introduit une classification des croyants.

  1. Type 1 : Un croyant de type 1 croit en toutes les tautologies et dès qu’il croit en p et en p⇒q, alors il croit aussi en q. Autrement dit, si Bp et B(p⇒q) alors Bq.
  2. Un croyant est régulier si chaque fois qu’il croit B(p⇒q), il croit Bp⇒Bq.
  3. Type 1* : Un croyant est de type 1* s’il est régulier de type 1.
  4. Type 2 : Un croyant de type 1 est un croyant tel que Bp ∧ B(p⇒q) ⇒ Bq. Il est de type 2 si en plus il croit que Bp ∧ B(p⇒q) ⇒ Bq.
  5. Un croyant est normal si chaque fois qu’il croit p, il croit aussi Bp ; autrement dit, Bp⇒BBp.
  6. Type 3 : Un croyant de type 3 est un croyant normal de type 2.
  7. Type 4 : Un croyant de type 4 est un croyant de type 3 qui croit être normal ; autrement dit, B(Bp⇒BBp).
  8. Un croyant est correct vis-à-vis de p si le seul fait qu’il croit p vraie, rend p vraie.
  9. Un croyant est spécial si il croit en une proposition p mais en même temps, il croit qu’il ne croit pas en p.
  10. Un croyant est vaniteux si il croit ne pas être spécial (ce qui ne veut pas dire qu’il n’est pas spécial !).
  11. Un croyant est cohérent si l’ensemble de ses croyances est cohérent.
  12. Un croyant est réflexif si pour toute proposition p, il y a une proposition q telle que le seul fait de croire en q implique que p soit vraie.
  13. Un croyant est modeste si pour toute proposition p, s’il croit que Bp⇒p alors il croit que p.
  14. Un croyant de type 4 est de type Gödel s’il croit être modeste, autrement dit, si pour toute proposition p, B(Bp⇒p)⇒Bp.
  15. Un croyant est « presque de type Gödel » s’il croit en tout ce à croient les croyants de type Gödel, et si ses croyances sont closes par rapport au modus ponens.
  16. Un croyant est stable si BBp⇒Bp.
  17. Un croyant est étrange s’il croit être incohérent.

Alors un croyant qui croit être incohérent n’est pas nécessairement incohérent. Mais un croyant spécial de type 3 est incohérent. Un croyant de type 4 croit être de type 4. C’est une forme de conscience de soi. De plus, si un croyant de type 4 est cohérent, il ne peut pas savoir qu’il est cohérent. Ceci, parce qu’il a entendu la phrase « tu ne sauras jamais que je suis un pur ».

En d’autres termes, si un croyant de type 4 croit être cohérent, alors il est incohérent. C’est le second théorème d’incomplétude de Gödel, transposé dans la logique doxastique. On notera qu’un croyant de type 4 croit en ce résultat.

Si un croyant de type 4 croit que le simple fait de croire qu’il est incohérent, le rend incohérent, alors il est incohérent. Ce résultat rappelle le paradoxe de Curry en ce que le simple fait de croire en une chose peut rendre cette chose vraie [3].

Smullyan considère ensuite une île différente de Puropira, appelée « île de Löb », peuplée elle aussi de Purs et de Pires, et sur laquelle, pour chaque proposition p, il existe au moins un habitant capable de dire « si tu crois que je suis un Pur alors p est vraie ». Cette île lui sert à résoudre un problème de Leon Henkin posé ainsi : Un habitant de l’île de Löb dit « tu peux croire que je suis un Pur » à un croyant de type 4. Peut-on savoir si cet habitant est un Pur ou un Pire ? La réponse [4] surprenante est : Oui, on peut savoir ! Autre théorème inspiré par Löb : Si un croyant réflexif de type 4 croit que la croyance en une proposition p entraîne sa vérité, alors ce croyant croit en la proposition p.

Un résultat de Saul Kripke entre autres, dit que si un croyant de type 3 croit être modeste alors il est de type 4. Et un croyant de type Gödel qui croit être modeste, est modeste. Une propriété des croyants de type Gödel (et plus généralement de type 1* cohérents et modestes) est qu’il n’existe aucune proposition p telle qu’il ne peut pas croire en p. Si un croyant modeste croit être stable, alors il est instable ou incohérent.

Application à la théologie

Un professeur de théologie dit à un de ses étudiants : « Dieu existe si et seulement si tu ne le sais pas ».

Variante : « Dieu existe si et seulement si tu sais qu’il n’existe pas »

Ces deux propositions sont paradoxales mais « Dieu existe si et seulement si tu ne crois pas en son existence » ne l’est plus : Si l’étudiant croit le professeur, il est spécial, et si de plus le professeur dit la vérité, Dieu existe et l’étudiant ne peut y croire.

On a vu que si l’étudiant est un croyant de type 4 alors il ne peut croire en sa cohérence sans devenir incohérent. Mais il lui reste un moyen d’échapper à ce paradoxe : Ne pas croire en son professeur !

Concernant le premier théorème d’incomplétude de Gödel (qu’on obtient en remplaçant « croire » par « pouvoir démontrer » dans la phrase ci-dessus, et « Dieu » par une proposition dite « gödelienne »), Smullyan cite André Weil : « Dieu existe puisque l’arithmétique est cohérente ; le Diable existe aussi puisque nous ne pourrons jamais le prouver ».

Le chapitre sur le théorème de Löb permet d’aborder le pari de Pascal dans une version non probabiliste : L’étudiant pose deux questions :

  1. « Dieu existe-t-il ? »
  2. « Serai-je sauvé ? »

Alors le professeur donne 4 réponses :

  1. « Si tu crois que tu seras sauvé, alors tu seras sauvé ».
  2. « Si Dieu existe et que tu crois qu’il existe, alors tu seras sauvé ».
  3. « Si Dieu n’existe pas, alors tu croiras qu’il existe ».
  4. « Tu ne seras sauvé que si Dieu existe ».

Alors si l’étudiant est de type 4 et qu’il croit en son professeur, d’une part, il croira en son salut, d’autre part, si le professeur dit vrai, l’étudiant sera effectivement sauvé.

Le premier théorème d’incomplétude de Gödel se traduit, dans ce contexte, par l’existence d’une proposition p telle qu’un croyant ne croit ni en p, ni en sa négation. Un exemple est donné : Le fameux « tu ne croiras jamais que je suis un pur ». Un autre exemple, pour un croyant cohérent, est la croyance en sa propre cohérence. Un autre encore est d’Alfred Tarski : On suppose qu’un croyant nommé Paul [5] ne croit jamais quelque chose de faux. Alors le simple fait qu’un habitant de Puropira dise « Paul ne croira jamais que je suis un Pur » suffit pour conclure que Paul est indécis. Pour parler de façon plus précise de ce qu’est la démontrabilité, Smullyan évoque ensuite la sémantique des mondes possibles.

Influence de Lewis Carroll

Une question à laquelle Lewis Carroll s’était intéressé, est celle-ci : Est-ce que ∀x, F(x)⇒B(x) est encore vrai s’il n’existe aucun x vérifiant le prédicat F ?

Smullyan propose un exemple très « frenchy » : « Tous les français de cette association portent un béret ». Du point de vue d’une association où il n’y a aucun français, on est dubitatif, vu que la négation de cette phrase est ∃x, F(x) ∧ ¬ B(x). S’il n’y a aucun français, il semble aussi vrai de dire que tous les français portent un béret, que de dire que tous les français portent une casquette. Comme Lewis Carroll, Smullyan fait le choix de dire que même dans une association vide, ∀x, F(x)⇒B(x) est vrai.

Un croyant de type Gödel, on l’a vu, ne peut pas croire qu’il est cohérent sans devenir incohérent. Un croyant qui est presque de type Gödel, par contre, peut croire qu’il est cohérent et être quand même cohérent. Mais dans ce cas il est anormal !

Tout croyant étrange est normal. Un croyant étrange est un croyant qui croit être incohérent. Mais un tel croyant peut très bien être cohérent !


Le livre en VO

Le fichier pdf a été coupé en trois parties pour l’alléger :

  1. introduction au calcul propositionnel, avec les purs et le pires ;
  2. Les théorèmes de Löb et de Gödel, vus sous l’angle de la logique doxastique ;
  3. Le premier théorème d’incomplétude et la calculabilité.
les pur et les pires second théorème de Gödel premier théorème de Gödel
PDF - 748.2 ko
PDF - 1.4 Mo
PDF - 1.3 Mo

[1Selon l’apôtre Saint-Paul (Epître à Tite), l’île de Puropira serait en fait la Crète : il y en a beaucoup, surtout parmi ceux de la circoncision, qui sont insoumis, vains parleurs, et séducteurs des âmes, auxquels il faut fermer la bouche, car ils bouleversent des maisons entières, enseignant ce qu'il ne faut pas, en vue d'un gain honteux. Un d'entre eux, leur propre prophète, a dit: Les Crétois sont toujours menteurs, méchantes bêtes, ventres paresseux. Ce témoignage est vrai... Tout est pur pour ceux qui sont purs; pour ceux qui sont souillés et infidèles rien n'est pur, mais leur raison et leur conscience sont souillées. Celui que Saint-Paul appelle « leur prophète » est Epiménide, autrement dit le paradoxe d’Épiménide se traduit en Puropira par « je suis un Pire ».

[2c’est la première lettre du mot « believe » mais aussi la lettre utilisée par Gödel pour désigner la démontrabilité (« beweisbar »)

[3On pense aussi à la méthode Coué et au théorème de Löb.

[4On peut lire l’article originel de Löb.

[5prénom choisi par Smullyan, peut-être en rapport avec la remarque ci-dessus sur les crétois ?


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 8 février 2017, 14h-18h, campus du Tampon, amphi 120 B
- Mercredi 8 mars 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 12 avril 2017, 14h-18h, campus du Tampon
- Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mardi 13 juin 2017, 14h-18h, campus du Tampon
- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6

Semaine des mathématiques

Du 23 mars au 4 avril 2017 dans l’académie de la Réunion.


Brèves

Travailler à plusieurs

lundi 19 décembre 2016

Les enseignements d’exploration au lycée imposent aux enseignants de travailler ensemble. Chantal Tuffery-Rochdi a analysé dans sa thèse les pratiques des enseignants de MPS (méthodes et pratiques scientifiques). Elle répond aux questions des Cahiers pédagogiques.

Un document sur Eduscol

mardi 19 mai 2015

Un document clarifiant bien la façon dont les mêmes concepts vivent en mathématiques et dans les sciences « exactes » les utilisant, publié par Eduscol en octobre 2014. Citons-les :
« Le document proposé ci-dessous s’adresse aux professeurs de mathématiques, physique-chimie et sciences de l’ingénieur intervenant dans le segment [Bac-3 ; Bac+3]. Il vise à les informer des différences de présentation et d’interprétation qui sont faites de certains concepts mathématiques dans les autres disciplines. Ces éclaircissements peuvent contribuer à harmoniser et à clarifier l’utilisation de ces notions auprès des élèves. »

Les métiers des mathématiques et de l’informatique

dimanche 22 mars 2015

Une brochure de l’ONISEP réalisée à l’initiative des cinq sociétés savantes, Femmes & Mathématiques, Société informatique de France, Société française de statistique, Société de mathématiques appliquées et industrielles, Société mathématique de France, représentant l’ensemble de la communauté française d’informatique et de mathématiques.

Histoire de la comptabilité

vendredi 28 décembre 2012

Sur ce site (en anglais) dédié à la comptabilité, on trouve des informations intéressantes sur l’histoire et les pratiques de ce domaine, qui peuvent être utiles aux professeurs enseignant des mathématiques financières (et aussi aux autres...).

La CGE et la réforme des lycées

lundi 16 janvier 2012

La Conférence des Grandes Écoles publie 19 préconisations pour la réforme du lycée.

Sur le Web : Les 19 préconisations

Pratique des mathématiques en série STD2A

lundi 16 janvier 2012

Le site de l’IGEN offre des recommandations et des ressources pour enseigner les mathématiques en série STD2A. Les thèmes abordés (couleurs et nuances de gris, arcs et architecture, jeux vidéos, photo et tableur, perspectives parallèles...) sont de nature à donner aussi des idées d’activités aux enseignants des autres séries !

En cheminant avec Kakeya

lundi 16 janvier 2012

Un livre (à télécharger) de Vincent Borelli et Jean-Luc Rullière qui présente le calcul intégral et la dérivation en s’appuyant sur la question de Kakeya. Pour les lycéens, les étudiants et tous les esprits curieux qui souhaitent voir les mathématiques sous un jour différent.

Sur le Web : Livre à télécharger

Bicentenaire Galois

lundi 12 septembre 2011

À l’occasion du bicentenaire de la naissance d’Évariste Galois (1811-2011), l’Institut Henri Poincaré et la Société mathématique de France organisent un ensemble de manifestations et proposent un site contenant diverses ressources documentaires susceptibles d’intéresser les enseignants.

Statistiques

Dernière mise à jour

jeudi 23 février 2017

Publication

732 Articles
Aucun album photo
125 Brèves
11 Sites Web
126 Auteurs

Visites

603 aujourd'hui
1112 hier
1932480 depuis le début
36 visiteurs actuellement connectés