David Madore's WebLog

This WebLog is bilingual, some entries are in English and others are in French. A few of them have a version in either language. Other than that, the French entries are not translations of the English ones or vice versa. Of course, if you understand only English, the English entries ought to be quite understandable without reading the French ones.

Ce WebLog est bilingue, certaines entrées sont en anglais et d'autres sont en français. Quelques-unes ont une version dans chaque langue. À part ça, les entrées en français ne sont pas des traductions de celles en anglais ou vice versa. Bien sûr, si vous ne comprenez que le français, les entrées en français devraient être assez compréhensibles sans lire celles en anglais.

Note that the first entry comes last! Notez que la première entrée vient en dernier !

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

(dimanche)

Quelques théorèmes de points fixes

Je suis un peu débordé en ce moment par la préparation de deux cours[#] qui commencent dans deux semaines et dont je n'ai pour l'instant que des notes très éparses et inachevées, d'autant plus que j'enseigne autre chose en ce moment. Mais pendant la préparation d'un de ces cours, je suis tombé sur une difficulté mathématique au sujet de laquelle j'aimerais l'avis de mes lecteurs mathématiciens (il doit bien y en avoir) ou amateurs de mathématiques : ce n'est pas que je ne sache pas démontrer quelque chose, mais que je m'étonne de la façon dont je le démontre, et je trouve qu'il y a quelque chose de surprenant dans toute l'histoire. Bref, je vais commenter les ressemblances et différences entre quelques énoncés apparemment très semblables et surtout différentes démonstrations des énoncés en question.

[#] L'un de ces cours concerne la théorie des jeux ; ou plutôt les théories des jeux, parce qu'il y a plusieurs domaines que leurs spécialistes appellent théorie des jeux, selon le type de jeux étudiés, et dont l'intersection est relativement faible : pensez à celle (que je ne sais pas nommer plus précisément) qui cherche des équilibres de Nash et celle (en gros, la théorie combinatoire des jeux) qui cherche à calculer des valeurs de Sprague-Grundy, par exemple, chacune a tendance à se définir comme « la » théorie des jeux, et d'ailleurs ça m'énerve, en tout cas je voudrais parler des deux et de quelques autres encore. Mes notes en cours d'écriture sont ici. L'autre cours concerne les courbes algébriques, pour lequel il va s'agir de remanier profondément un cours de géométrie algébrique (anciennes notes ici) que je donnais déjà.

Voici quatre énoncés mathématiques très simples, en théorie élémentaire des ensembles, que je pourrais regrouper sous le label général de théorèmes de points fixes, et que je vais appeler successivement (P), (P$), (F) et (F$) :

(P) Soit X un ensemble : on note 𝒫(X) son ensemble des parties. Soit Ψ:𝒫(X)→𝒫(X) une application vérifiant les deux propriétés suivantes : (i) Ψ est progressive, c'est-à-dire que Ψ(A)⊇A pour tout A∈𝒫(X), et (ii) Ψ est croissante, c'est-à-dire que si AB alors Ψ(A)⊇Ψ(B). Alors il existe un plus petit A∈𝒫(X) tel que Ψ(A)=A (c'est-à-dire un A tel que Ψ(A)=A et que si A′ vérifie aussi Ψ(A′)=A′ alors AA′).

(P$) [Exactement le même énoncé que (P) sans supposer (i).] Soit X un ensemble : on note 𝒫(X) son ensemble des parties. Soit Ψ:𝒫(X)→𝒫(X) une application vérifiant la propriété suivante : Ψ est croissante, c'est-à-dire que si AB alors Ψ(A)⊇Ψ(B). Alors il existe un plus petit A∈𝒫(X) tel que Ψ(A)=A. [Un peu mieux : il existe un plus petit A tel que Ψ(A)⊆A, et ce A vérifie Ψ(A)=A.]

Pour les deux énoncés suivants, j'ai besoin de rappeler la notion de fonction partielle : si X et Z sont deux ensembles, une fonction partielle XZ est une fonction définie sur une partie de X et à valeurs dans Z ; on peut aussi la voir comme une partie de X×Z (à savoir, le graphe de la fonction) qui soit fonctionnelle au sens où si elle contient à la fois (x,z₁) et (x,z₂) pour le même xX alors forcément z₁=z₂. La relation fg entre fonctions partielles signifie alors que la fonction f prolonge la fonction g (i.e., que f est définie partout où g l'est, et qu'alors leurs valeurs coïncident).

(F) [Exactement le même énoncé que (P) avec des fonctions partielles XZ au lieu de parties de X.] Soient X et Z deux ensembles : on note 𝒟 l'ensemble des fonctions partielles XZ. Soit Ψ:𝒟→𝒟 une application vérifiant les deux propriétés suivantes : (i) Ψ est progressive, c'est-à-dire que Ψ(f)⊇f pour tout f∈𝒟, et (ii) Ψ est croissante, c'est-à-dire que si fg alors Ψ(f)⊇Ψ(g). Alors il existe une plus petite f∈𝒟 telle que Ψ(f)=f (c'est-à-dire un f tel que Ψ(f)=f et que si f′ vérifie aussi Ψ(f′)=f′ alors ff′).

(F$) [Exactement le même énoncé que (F) sans supposer (i), donc exactement le même que (P$) avec des fonctions partielles au lieu de parties.] Soient X et Z deux ensembles : on note 𝒟 l'ensemble des fonctions partielles XZ. Soit Ψ:𝒟→𝒟 une application vérifiant la propriété suivante : Ψ est croissante, c'est-à-dire que si fg alors Ψ(f)⊇Ψ(g). Alors il existe une plus petite f∈𝒟 telle que Ψ(f)=f. [Un peu mieux : il existe un plus petit f tel que Ψ(f)⊆f, et ce f vérifie Ψ(f)=f.]

(Nomenclature : j'appelle (P) et (P$) les énoncés sur les Parties, (F) et (F$) ceux sur les Fonctions partielles, et (P$) et (F$) les énoncés qui vous en donnent plus pour votre argent.) J'espère que j'ai écrit ces énoncés de façon à ce qu'il n'y ait pas le moindre doute sur leur signification formelle. L'objet dont chacun de ces énoncés affirme l'existence peut être qualifié de plus petit point fixe de Ψ.

Commentaires : Le sens intuitif de ces résultats est quelque chose comme le suivant : on a une opération Ψ qui, pour prendre l'exemple de l'énoncé (F), prend une fonction f et l'étend en une fonction peut-être définie sur un peu plus de points, et par ailleurs, Ψ possède une propriété de cohérence, à savoir que si on étend f, on étend aussi le résultat de l'opération Ψ(f) ; alors il existe une « clôture du vide » pour l'opération Ψ, c'est-à-dire qu'en partant de rien, l'opération Ψ vous permet d'arriver à une certaine fonction f à partir de laquelle l'opération Ψ ne la fait plus grandir. Pour donner un exemple d'application de (P$), considérer l'ensemble X=ℕ des entiers naturels, et l'opération Ψ qui à un ensemble A de naturels associe l'ensemble formé des entiers 2, 3 et tous les produits de deux éléments de A : le plus petit point fixe sera alors l'ensemble de tous les entiers qu'on peut fabriquer en multipliant 2 et 3 autant qu'on veut ensemble (à savoir l'ensemble des 2i·3j avec au moins un de i et j non-nul, mais peu importe) ; plus généralement, (P) ou (P$) peut servir à montrer l'existence de toutes sortes de « clôtures » sous des opérations variées. Généralement parlant, le concept de plus petit point fixe (ou de point fixe en général) apparaît très souvent en mathématiques, et il existe tout un labyrinthe — mais je crois vraiment que les énoncés que j'ai cités ci-dessus sont parmi les plus naturels.

Il est complètement évident que (P$)⇒(P) (parce qu'on suppose quelque chose de plus fort dans (P) pour arriver à la même conclusion) et de même que (F$)⇒(F). Il est aussi facile de voir que (F)⇒(P) et (F$)⇒(P$) grâce à l'« astuce » (si on peut l'appeler comme ça…) consistant à prendre pour Z un singleton (:=ensemble ayant un seul élément), de sorte qu'une fonction partielle XZ est essentiellement la même chose qu'une partie de X (à savoir la partie sur laquelle la fonction est définie). Du coup, (F$) est assurément le résultat le plus fort des quatre. (Les remarques que j'ai introduites par un peu mieux sont encore plus fortes que (P$) et (F$), on pourrait les appeler (P€) et (F€), mais en fait elles ne m'intéressent pas tellement en tant que telles : c'est juste que je ne sais pas démontrer (P$) ou (F$) sans obtenir directement ces résultats plus forts, et par ailleurs ils aident vaguement à comprendre comment les choses se passent.)

Mais si je prends la peine d'énoncer quatre résultats différents, c'est que le résultat (P) est extrêmement facile à démontrer :

Démonstration de (P) : Il existe des A tels que Ψ(A)=A (puisque l'ensemble X tout entier en est un). Soit C l'intersection de tous ces A. Alors C est inclus dans chacun de ces A, donc par (ii), Ψ(C) est inclus dans chacun des Ψ(A)=A ; du coup, Ψ(C) est inclus dans l'intersection des A en question, qui est justement C, et comme (i) donne l'inclusion dans l'autre sens, on a Ψ(C)=C. La construction même de C fait qu'il est bien le plus petit.

Je pense que n'importe quel mathématicien non seulement sait démontrer le résultat (P) à la lecture, mais tombera de plus essentiellement sur la démonstration que je viens de dire. Dans n'importe quel livre de maths, la démonstration serait simplement condensée en quelque chose comme l'intersection des points fixes de Ψ est elle-même un point fixe de Ψ comme on le vérifie facilement, et c'est donc le plus petit pour l'inclusion.

Bon, autant vous en donner un peu plus pour votre argent et démontrer (P$). Je vais le faire de deux façons différentes :

Démonstration de (P$) en utilisant (P) : Je suppose que Ψ seulement croissante (i.e., vérifiant (ii)), et j'appelle Ψ₁(A) := AΨ(A). Alors Ψ₁ vérifie (i) et (ii), donc par (P), il existe un plus petit A tel que Ψ₁(A)=A, ce qui signifie exactement Ψ(A)⊆A. Comme du coup (ii) donne Ψ(Ψ(A))⊆Ψ(A), le fait que A soit le plus petit à vérifier Ψ(A′)⊆A′ garantit AΨ(A), et on a bien Ψ(A)=A (et comme tout A′ qui vérifie Ψ(A′)=A′ vérifie en particulier Ψ(A′)⊆A′, il est bien inclus dans A, qui est donc le plus petit à vérifier Ψ(A′)=A′).

Démonstration directe de (P$) : Il existe des A tels que Ψ(A)⊆A (puisque l'ensemble X tout entier en est un). Soit C l'intersection de tous ces A. Alors C est inclus dans chacun de ces A, donc par croissance, Ψ(C) est inclus dans chacun des Ψ(A)⊆A ; du coup, Ψ(C) est inclus dans l'intersection des A en question, qui est justement C, ce qui prouve Ψ(C)⊆C. Par croissance, on a aussi Ψ(Ψ(C))⊆Ψ(C). Du coup, Ψ(C) est l'un des A qu'on a intersectés pour former C, ce qui montre Ψ(C)⊇C, et donc Ψ(C)=C. La construction même de C fait qu'il est le plus petit A′ tel que Ψ(A′)⊆A′, et comme tout A′ qui vérifie Ψ(A′)=A′ vérifie en particulier Ψ(A′)⊆A′, il est bien inclus dans C, qui est donc le plus petit à vérifier Ψ(A′)=A′.

Ça reste très simple même si je trouve ça un chouïa moins transparent. Mais là où les choses sont bizarres, c'est quand on considère (F) et (F$). C'est ici que j'invite mes lecteurs mathématiciens à faire une pause pour se demander comment ils démontreraient ces énoncés, parce que je serais vraiment curieux de savoir à quoi ils penseront spontanément. Je n'arrive pas à décider s'il y a une vraie difficulté ou pas : vue la tête de l'énoncé et vue les démonstrations que j'ai données de (P) et (P$), on se dit que (F) et (F$) ne doivent pas être difficiles. Mais l'idée qu'on a envie d'essayer en premier est sans doute de prendre l'intersection de toutes les fonctions partielles f telles que Ψ(f)⊆f, et elle se heurte à l'obstacle qu'il n'est pas évident a priori qu'il existe un tel f (i.e., qui soit une fonction partielle) ; ou alors, on peut être tenté de prendre l'intersection de toutes les parties A de X×Z telles que Ψ(A)⊆A (en prolongeant un peu intelligemment Ψ de 𝒟 à 𝒫(X×Z)), mais alors il n'est pas du tout évident que cette intersection soit une fonction. Non, vraiment, réfléchissez-y avant de lire la suite !

Voici maintenant une démonstration de (F$), que je trouve presque hallucinante, même s'il faut admettre qu'elle a une certaine beauté :

Démonstration de (F$) :

Montrons d'abord que si il existe une fonction partielle f∈𝒟 telle que Ψ(f)=f, ou même simplement Ψ(f)⊆f, alors il en existe une plus petite. Pour cela, il suffit de considérer l'intersection h de toutes les f telles que Ψ(f)⊆f (considérées comme des parties de X×Z) : dès lors qu'il existe au moins un f∈𝒟 tel que Ψ(f)⊆f, cette intersection h est bien définie et est bien un élément de 𝒟. Si Ψ(f)⊆f alors hf (puisque h est l'intersection des f), donc Ψ(h)⊆Ψ(f) (par croissance de Ψ), donc Ψ(h)⊆f (par transitivité), et comme ceci est vrai pour tous les f dont l'intersection est h, on a finalement Ψ(h)⊆h ; mais la croissance de Ψ donne alors aussi Ψ(Ψ(h))⊆Ψ(h), et du coup Ψ(h) est l'une des f qu'on a intersectées pour former h, et on a ainsi hΨ(h) ; bref, Ψ(h)=h, et h est à la fois le plus petit élément f∈𝒟 vérifiant Ψ(f)⊆f (de par sa construction) et le plus petit vérifiant Ψ(f)=f (puisqu'il vérifie cette propriété plus forte).

Reste à montrer qu'il existe bien une fonction partielle f telle que Ψ(f)=f, ou même simplement Ψ(f)⊆f. Pour cela, on introduit l'ensemble ℰ des f∈𝒟 qui vérifient Ψ(f)⊇f (inclusion dans le sens opposé du précédent !). Notons que ℰ n'est pas vide puisque ∅∈ℰ (où ∅ est la fonction vide, définie nulle part).

Soit maintenant 𝔐 l'ensemble des applications (totales !) T:ℰ→ℰ qui vérifient (i) T(f)⊇f pour tout f∈ℰ et (ii) si fg alors T(f)⊇T(g). Ainsi id∈𝔐 (trivialement) et Ψ∈𝔐 (par définition de ℰ et par croissance de Ψ) ; et si T,T′∈𝔐 on a T′∘T ∈ 𝔐 (en notant T′∘T la composée). L'observation suivante sera cruciale : si g∈ℰ et T,T′∈𝔐, alors on a à la fois (T′∘T)(g) ⊇ T(g) (d'après (i) pour T′) et (T′∘T)(g) ⊇ T′(g) (d'après (i) pour T et (ii) pour T′).

Affirmation : si g∈ℰ alors la réunion des T(g) pour tous les T∈𝔐 est, en fait, une fonction partielle. En effet, l'observation faite ci-dessus montre que si T,T′ ∈ 𝔐 alors les fonctions partielles T(g) et T′(g) sont toutes deux restrictions d'une même fonction partielle (T′∘T)(g), donc il ne peut pas y avoir de conflit entre leurs valeurs (au sens où si toutes les deux sont définies en un x∈ X, elles y coïncident) — c'est exactement ce qui permet de dire que la réunion est encore une fonction partielle. Notons U(g) := ⋃T∈𝔐(T(g)) cette réunion. On a au moins U(g)∈𝒟. Mais en fait, comme U(g) prolonge tous les T(g), la croissance de Ψ assure que Ψ(U(g)) prolonge tous les Ψ(T(g)), qui prolongent eux-mêmes les T(g) (puisque T(g) ∈ ℰ), bref Ψ(U(g)) ⊇ U(g) et ainsi U(g)∈ℰ.

Mais alors U∈𝔐 (on vient de voir que U est une fonction ℰ→ℰ, et les propriétés (i) et (ii) sont claires). En particulier, ΨU∈𝔐, donc (ΨU)(g) est l'une des T(g) dont U(g) est la réunion, et on a donc (ΨU)(g) ⊆ U(g), l'inclusion réciproque ayant déjà été vue (et de toute façon on n'en a pas besoin). On a donc bien trouvé une fonction partielle f := U(∅) telle que Ψ(f)⊆f (même Ψ(f)=f).

C'est quand même bizarrement compliqué, comme façon de faire ! (D'ailleurs, je veux quand même bien qu'on me confirme que c'est correct et compréhensible, comme démonstration.)

Bon, ceci étant, le David Madore étant un grand fan des ordinaux, on peut aussi procéder comme ceci :

Seconde démonstration de (F$) (utilisant les ordinaux) :

On pose f0 = ∅, et par induction sur l'ordinal α on définit fα+1 = Ψ(fα) et si δ est un ordinal limite alors fδ = ⋃γ<δ fγ. On montre simultanément par induction sur α que fα est bien définie, est une fonction partielle, et, grâce à la croissance de Ψ, prolonge fβ pour chaque β<α (c'est ce dernier point qui permet de conclure que ⋃γ<δ fγ est une fonction partielle lorsque δ est un ordinal limite : la réunion d'une famille totalement ordonnée pour l'inclusion de fonctions partielles est encore une fonction partielle). Les inclusions fβfα pour β<α ne peuvent pas être toutes strictes sans quoi on aurait une surjection d'un ensemble sur la classe des ordinaux. Il existe donc τ tel que fτ+1 = fτ, c'est-à-dire Ψ(fτ) = fτ. D'autre part, si Ψ(h) = h, alors par induction sur α on montre fαh pour chaque α (l'étape successeur étant que si fαh alors fα+1 = Ψ(fα) ⊆ Ψ(h) = h), donc en particulier fτh, et fτ est bien le plus petit f tel que Ψ(f) = f.

Oui, c'est beaucoup plus simple. Ça pourrait servir de pub pour les ordinaux, je devrais m'en réjouir.

Mais là, je me dis : ce n'est pas moral : l'énoncé élémentaire (F$), qui ne fait pas intervenir d'ordinaux, ne devrait pas en avoir besoin pour sa démonstration, et de fait, (P$) n'en avait pas besoin. Comment se fait-il que la démonstration de (P$) sans ordinaux se complique immensément quand on passe à (F$), alors qu'avec les ordinaux les quatre énoncés se démontrent exactement pareil (construire l'itération transfinie de Ψ, et constater que c'est l'objet recherché). J'ai passé beaucoup de temps à me gratter la tête sur comment « enlever » les ordinaux dans la démonstration ci-dessus, sans succès.

Il y a sans doute aussi moyen de s'en sortir en invoquant astucieusement le lemme de Zorn. Mais c'est encore pire, comme atteinte aux bonnes mœurs mathématiques : le résultat ne dépend en aucune manière de l'Axiome du Choix (et l'objet construit est complètement canonique), il est scandaleux de se servir du Choix pour abréger la démonstration. Au contraire, le genre de théorèmes de points fixes que j'ai cités peut servir à démontrer le lemme de Zorn à partir de l'Axiome du Choix.

J'ai aussi passé pas mal de temps à chercher à passer de (F) à (F$) un peu de la manière dont je suis passé de (P) à (P$) ci-dessus, là aussi sans succès (si on tente de définir Ψ₁(f) := fΨ(f), rien ne garanti que c'est une fonction ; si on cherche à se limiter aux f pour lesquels ç'en est une, il me semble que ça ne marche vraiment pas).

Donc, quelque chose me gêne vraiment dans l'histoire, pas tellement au niveau mathématique mais au niveau métamathématique. Parfois l'histoire ne s'arrête pas à démontrer un théorème, mais à comprendre les différentes façons de le démontrer, et comment elles se relient les unes aux autres.

Mais il faut que j'admette que j'ai caché quelque chose dans l'histoire, parce que j'en sais plus que je ne l'ai dit : c'est le contenu de cet article d'Andrej Bauer et Peter LeFanu Lumsdaine (On the Bourbaki-Witt Principle in Toposes), duquel d'ailleurs (cf. leur théorème 3.2, qui n'est pas de ces auteurs mais que j'ai appris par eux) je tire essentiellement la première démonstration (« hallucinante ») de (F$) donnée ci-dessus. Pour décoder un peu ce qu'ils racontent, ils s'intéressent à des principes affirmant l'existence de points fixes d'opérateurs Ψ:𝒟→𝒟 (où 𝒟 est un ensemble partiellement ordonné) en supposant soit (i) que Ψ est progressif, i.e., xΨ(x) pour tout x, soit (ii) que Ψ est croissant, i.e., que xy implique Ψ(x)≤Ψ(y), et en supposant que 𝒟 admet des bornes supérieures soit (a) quelconques, soit (b) de parties dirigées (:=dans lesquelles un nombre fini quelconque d'éléments admettent toujours un majorant), soit (c) de chaînes (:=parties totalement ordonnées). Cela donne six principes de points fixes en combinant les hypothèses (i) et (ii) avec les hypothèses (a), (b) et (c) : parmi eux, (i.a) est trivial, (ii.a) et (ii.b) sont démontrables de façon « constructive » (valables dans un « topos élémentaire »), c'est-à-dire sans utiliser le tiers exclu ni l'Axiome de Remplacement[#2], tandis que ni (i.b) et (i.c) (qui sont équivalents, et qu'ils appellent théorème de Bourbaki-Witt) ni (ii.c) (qu'ils appellent théorème de Knaster-Tarski) ne sont démontrables « constructivement », et ce défaut de constructivité passe par une question d'existence d'assez d'ordinaux (et la démonstration non-« constructive » se fait par induction transfinie exactement comme ci-dessus). • Le rapport avec ce que je disais au-dessus, c'est que l'ensemble des parties d'un ensemble X vérifie l'hypothèse (a) d'existence de bornes supérieures quelconques, tandis que l'ensemble des fonctions partielles XZ vérifie seulement (b) (et du coup (c) aussi, qui est plus faible). Ceci fournit une certaine lumière sur le problème : d'abord, ceci « explique » pourquoi (P) est plus simple que (P$), parce que la démonstration de l'existence d'un point fixe dans le cas (i.a) est triviale, on prend juste le plus grand élément de 𝒟, alors que dans le cadre (ii.a) il faut réfléchir un petit peu plus ; d'autre part, les ordinaux permettent d'utiliser la démonstration de (ii.c), tandis que si on veut éviter le Remplacement qu'ils utilisent intrinsèquement, il faut passer par (ii.b), or l'hypothèse (b) est plus délicate à mettre en œuvre que (c) (on n'a pas juste à prendre des unions de familles totalement ordonnées de fonctions, mais des familles dirigées de fonctions, et c'est ce que fait la démonstration qui explique que T(g) et T′(g) sont toutes deux restrictions d'une même fonction partielle (T′∘T)(g), donc il ne peut pas y avoir de conflit entre leurs valeurs). • Mais ceci ne clarifie pas complètement les choses, parce que le cadre dans lequel je me place est quand même différent : d'abord, je n'ai aucune objection à utiliser le tiers exclu, d'autre part, pour ce qui est de (F) je suis prêt à prendre (i) et (ii) comme hypothèses, pas juste l'une des deux, ensuite je me place dans un cadre où il y a des bornes inférieures représentées par les intersections, et de fait, je demande le plus petit point fixe, et enfin, il est parfaitement imaginable qu'une démonstration beaucoup plus simple existe dans le cadre concret d'un ensemble de fonctions partielles que dans le cadre abstrait d'un ensemble partiellement ordonné fût-il complet en tel ou tel sens. Donc je ne peux pas dire que j'aie la clé du mystère métamathématique.

[#2] En fait, je crois que ce n'est pas tant un question de tiers exclu, et moralement la démonstration vers les ordinaux ne l'utilise pas plus que les autres, que de Remplacement, qui fait marcher les ordinaux, donc constructif n'est peut-être pas le bon terme (c'est le terme standard, mais il suggère la mauvaise idée — moralement, les ordinaux même immenses sont parfaitement constructifs, c'est juste que le cadre métamathématique qu'on utilise pour faire des maths constructives limite aussi les ordinaux, et du coup on en est venu à utiliser un même terme pour une combinaison de choses différentes). Mais j'avoue que mes idées sur le rôle de Remplacement de l'affaire sont très incertaines : notamment, est-ce que l'énoncé (ii.c) si Ψ:𝒟→𝒟 est une application croissante où 𝒟 est un ensemble partiellement ordonné dans lequel toutes les chaînes admettent une borne supérieure, alors Ψ a un point fixe est un théorème de la théorie des ensembles de Zermelo ?

(mercredi)

Jouons un peu avec les subordonnées relatives

L'entrée précédente contenait le bout de phrase

…dans le cadre d'un cours dont j'enseigne à un groupe…

que j'affirme être correcte (j'enseigne à un groupe [d'élèves] de ce cours) mais qui a fait réagir le genre de grincheux dont j'imagine qu'ils doivent lire des blogs sans aucun intérêt pour le fond, par simple plaisir de pinailler sur la grammaire. Penchons-nous donc un instant sur les subordonnées relatives en français. [En vérité, l'avant-dernière phrase est surtout là pour fournir quelques exemples intéressants in situ de subordonnées compliquées : la phrase que j'affirme être correcte et les grincheux dont j'imagine qu'ils doivent lire des blogs blablabla.]

La subordonnée relative, dans les langues que je connais assez bien pour m'exprimer à leur sujet, a pour fonction de prendre deux phrases faisant intervenir le même concept, plus exactement un groupe nominal (ou un pronom), et d'imbriquer une dans l'autre (l'imbriquée devient donc la proposition subordonnée tandis que l'imbriquante devient la proposition principale) en explicitant le fait que c'est bien le même concept qui intervient dans les deux phrases. Exemple extrêmement simple :

{J'aime la maison} # {Je vois la maison} → {J'aime la maison {que je vois}}

(L'opération n'est pas commutative : dans l'autre sens on obtiendrait Je vois la maison {que j'aime}, ce qui a un sens subtilement différent, mais je vais y revenir.)

Le mot que indiqué en rouge est le pronom relatif ; il a un double rôle : (A) introduire la subordonnée (marquer son début, c'est-à-dire, débuter l'imbrication) et (B) préciser la fonction occupée par le groupe commun (l'antécédent de la relative) dans cette subordonnée. On va voir ci-dessous que ces rôles sont un peu en conflit et qu'il serait beaucoup plus clair d'avoir deux mots séparés pour les remplir. Le point à souligner dans (B) est que normalement en français la fonction d'un groupe nominal est indiquée par l'ordre des mots, mais comme on a réordonnée les mots pour mettre le pronom relatif en premier (à cause de son rôle (A)), cette fonction n'est plus apparente, et on la manifeste, à la place, par la forme du pronom. Pour reprendre un exemple très simple, comparer :

{Le garçon fait de la muscu} # {Le garçon drague Kévin} → {Le garçon {qui drague Kévin} fait de la muscu}

{Le garçon fait de la muscu} # {Kévin drague le garçon} → {Le garçon {que drague Kévin} fait de la muscu}

— la fonction (sujet ou objet) du groupe nominal commun dans la seconde phrase est indiquée par son emplacement quand la phrase est autonome, mais par la forme du pronom relatif (reste de déclinaison latine) quand elle est transformée en subordonnée.

Ajout () : J'aurais sans doute dû signaler que dans la seconde version, le garçon {que drague Kévin} fait de la muscu, on peut aussi utiliser l'ordre des mots le garçon {que Kévin drague} fait de la muscu, alors que dans la première il n'y a pas de choix : on peut donc préciser la fonction dans la subordonnée par le choix du pronom ou par l'ordre des mots. Il faudrait chercher un exemple où on ne peut pas jouer avec l'ordre des mots.

✱ Le français a plusieurs systèmes de pronoms relatifs (formant un tout assez incohérent) : à coté de qui, que et de quelques autres, on a tout un jeu de variations de lequel, laquelle, lesquel(le)s, l'emploi de ces deux systèmes étant subtilement et incompréhensiblement différent. Prenons par exemple :

{Ce système est assez incohérent} # {Je mesure la complexité de ce système}

→ (i) {Ce système {dont je mesure la complexité} est assez incohérent}

→ (ii) {Ce système {duquel je mesure la complexité} est assez incohérent}

mais

{Ce système est assez incohérent} # {Je suis confronté à la complexité de ce système}

→ (iii) {Ce système {dont je suis confronté à la complexité} est assez incohérent}

→ (iv) {Ce système {à la complexité duquel je suis confronté} est assez incohérent}

Dans la phrase (iv), le pronom relatif duquel prend une place différente (celle qui correspond à sa fonction dans la subordonnée) sans doute selon la logique que le rôle (B) d'indiquer clairement comment le groupe commun s'articule dans la subordonnée devient prépondérant sur le rôle (A) d'introduire la subordonnée, qui, ici, est en quelque sorte dévolu à la préposition à ; en revanche, dans (i)–(iii), le pronom relatif se place bien en premier pour tenir son rôle (A) (encore que je pourrais défendre la phrase ce système {la complexité duquel je mesure} est assez incohérent). Les grincheux qui ont critiqué la phrase de l'entrée précédente citée en tout premier dans cette entrée-ci pensent peut-être que (iii) est incorrecte vu qu'elle est construite selon exactement le même modèle (ce système {dont je suis confronté à la complexité} est assez incohérent et dans le cadre d'un cours {dont j'enseigne à un groupe}). Je sais pourtant que ce type de tournure est employé non seulement par moi mais par quantité d'autres locuteurs natifs du français et que je l'ai relevé chez les meilleurs auteurs — comme on le comprend à la lecture de la présente entrée, j'aime bien analyser mentalement la syntaxe des phrases que j'entends —, donc je suppose que ça fait partie des délires des linguistes prescriptivistes qui ont décidé que ça ne sa faisait pas selon leurs règles dont on voit bien, et c'est une des choses que je veux démontrer ici, qu'elles sont incodifiables. [Tiens, encore une phrase qui se finit par une subordonnée intéressante.]

✱ Tout ce système de pronoms relatifs et de syntaxes de subordination est, il faut bien le dire, invraisemblablement merdique, et une des difficultés qui va survenir est qu'il n'y a tout simplement pas assez de pronoms relatifs pour indiquer toutes les fonctions que pourrait occuper le groupe commun dans la phrase (qu'on transforme en) subordonnée. La bonne façon de faire, si on devait inventer une langue logique et claire, serait de procéder comme on fait en mathématiques, à savoir introduire une variable de liaison (genre x) répétée deux fois dans les deux fonctions et d'utiliser un marqueur unique (disons tel que) pour le rôle (A) : autrement dit, cela donnerait quelque chose comme

{Le garçon fait de la muscu} # {Le garçon drague Kévin} → {Le garçon x {tel que x drague Kévin} fait de la muscu}

{Le garçon fait de la muscu} # {Kévin drague le garçon} → {Le garçon x {tel que Kévin drague x} fait de la muscu}

C'est-à-dire que la notion de subordonnée relative est essentiellement (à des subtilités sémantiques sur lesquelles je vais revenir) le tel que des matheux avec une syntaxe alambiquée.

J'ignore s'il y a des langues naturelles qui ont un tel concept de « variable locale », c'est-à-dire de pronoms (pronoms locaux ?) dont un bout de phrase pourrait affecter la valeur dont un autre bout de phrase pourrait la reprendre. [Remarquer au passage un autre type de difficulté subtile dans la dernière relative de la phrase précédente.] L'avantage de ce système est qu'il permet des imbrications arbitrairement complexes :

{Ce système est assez incohérent} # {Je suis confronté à la complexité de ce système} → {Ce système x {tel que je suis confronté à la complexité de x} est assez incohérent}

{J'aime les subordonnées} # {J'écris une entrée dans mon blog pour me plaindre de la difficulté à combiner des phrases d'une complexité arbitrairement grande en subordonnées}

→ {J'aime les subordonnées {j'écris une entrée dans mon blog pour me plaindre de la difficulté à combiner des phrases d'une complexité arbitrairement grande en lesquelles}} (†)

→ {J'aime les subordonnées x {telles que j'écris une entrée dans mon blog pour me plaindre de la difficulté à combiner des phrases d'une complexité arbitrairement grande en x}}

— y compris reprendre des groupes qui sont eux-mêmes cachés dans une une subordonnée de la phrase qu'on cherche à subordonner :

{Le livre est sur la table} # {Je vois {que tu as fini le livre}}

→ {Le livre {que je vois {que tu as fini}} est sur la table} (passe encore)

→ {Le livre x {tel que je vois {que tu as fini x}} est sur la table}

Mais :

{Les gens sont maintenant vieux} # {{Quand les gens étaient petits} la seconde guerre mondiale s'est terminée}

→ {Les gens {{quand lesquels étaient petits} la seconde guerre mondiale s'est terminée} sont maintenant vieux} (†) (Oui, je sais bien que sur cet exemple comme sur quantité d'autres on peut trouver une façon de reformuler la phrase : vu que {quand les gens étaient petits} la seconde guerre mondiale s'est terminée équivaut essentiellement à les gens étaient petits {quand la seconde guerre mondiale s'est terminée}, la phrase impossible ci-dessus peut se redire en les gens {qui étaient petits {quand la seconde guerre mondiale s'est terminée}} sont maintenant vieux — phrase tout à fait naturelle en français, mais ce n'est plus la même syntaxe.)

→ {Les gens x {tels que {quand x étaient petits} la seconde guerre mondiale s'est terminée} sont maintenant vieux}

Cela marche(rait) même quand la subordonnée-dans-la-subordonnée est elle-même relative :

{Je suis amoureux de Kévin} # {Le garçon {qui drague Kévin} fait de la muscu} → {Je suis amoureux de Kévin {que le garçon {qui drague} fait de la muscu}} (†?) (Oui, de nouveau, on peut trouver une façon de retourner les choses : en remplaçant le garçon {qui drague Kévin} fait de la muscu par le garçon {qui fait de la muscu} drague Kévin, ce qui est presque pareil, on transforme la phrase impossible en je suis amoureux de Kévin {que le garçon {qui fait de la muscu} drague} — mais on a subtilement retourné syntaxe de la phrase.)

{Je suis amoureux de Kévin} # {Le garçon {qui drague Kévin} fait de la muscu} → {Je suis amoureux de Kévin k {tel que le garçon {qui drague k} fait de la muscu}}

— voire, en utilisant le même mécanisme à tous les niveaux :

{Je suis amoureux de Kévin} # {Le garçon x {tel que x drague Kévin} fait de la muscu} → {Je suis amoureux de Kévin k {tel que le garçon x {tel que x drague k} fait de la muscu}}

Les matheux ont l'habitude de voir et de comprendre des phrases avec des introductions de variables ainsi imbriquées (les réels t {tels que les réels x {tels que x>t} vérifient x≥0} vérifient t≥0, construite selon le même modèle que la phrase ci-dessus, et par ailleurs juste). Comme je le disais, je ne sais pas si une langue naturelle a un système de ce genre (avec vraiment plusieurs jeux de variables), mais je suis tout à fait persuadé qu'il y a des langues avec une notion de subordonnée relative et qui, au moins, séparent en deux mots les rôles (A) et (B) du pronom relatif français.

✱ Mais même en français, en fait, dans le cas fréquent où la phrase à subordonner fait intervenir un verbe du genre penser que ou affirmer que introduisant le groupe commun, on peut souvent utiliser une « astuce » qui consiste à (A) introduire la subordonnée par dont dans un sens de au sujet duquel [je peux faire l'affirmation suivante] et d'utiliser ensuite un pronom normal (il, le) pour la fonction (B) (à la place de la variable x de mes exemples précédents). Ceci permet de former des subordonnées compliquées qui ne seraient autrement pas vraiment possibles avec la syntaxe du français. Démonstration :

{Cette mesure ne sera pas adoptée} # {Je pense {que cette mesure est liberticide}}

• en essayant naïvement :

→ {Cette mesure {je pense {que laquelle est liberticide}} ne sera pas adoptée} (†)

• en remaniant la syntaxe grâce à la magie des propositions infinitives (changer je pense {que cette mesure est liberticide} en je pense {cette mesure être liberticide}) :

→ {Cette mesure {que je pense {être liberticide}} ne sera pas adoptée}

• en utilisant l'« astuce » que je viens d'expliquer :

→ {Cette mesure {dont(A) je pense {qu'elle(B) est liberticide}} ne sera pas adoptée}

• en utilisant le mécanisme général exposé plus haut :

→ {Cette mesure x {telle que(A) je pense {que x(B) est liberticide}} ne sera pas adoptée}

Ici j'ai choisi un exemple où on peut s'en sortir avec la magie des infinitives, mais si on envisage une phrase comme cette mesure {dont je suis persuadé {que les Français l'appellent de leurs vœux}} ne sera pas adoptée, on voit qu'on peut arriver à des choses assez complexes et néanmoins tout à fait compréhensibles grâce à l'« astuce du dont ». Je ne sais pas si ce type de tournure (dont je raffole de l'emploi, et il y en a plusieurs exemples dans cette entrée) a un nom classique, mais elle est extrêmement pratique.

Clarification () : Je ne prétends pas que cette « astuce » repose sur une anomalie de syntaxe : je réécris simplement la phrase à subordonner, par exemple je pense {que cette mesure est liberticide} peut être transformé en je pense de cette mesure {qu'elle est liberticide} (c'est une façon de donner à cette mesure une fonction « bidon » mais non imbriquée), et du coup on peut faire la transformation en cette mesure {dont je pense {qu'elle est liberticide}} ne sera pas adoptée. Néanmoins, ce type de réécriture est très général (dès qu'on a affaire à un verbe comme penser, croire, affirmer, etc., où on peut penser, croire ou affirmer quelque chose [au sujet] de quelque chose). Idéalement, il faudrait en français un « complément bidon » qui n'aurait aucun sens (une préposition qui servirait juste à introduire un groupe nominal à ignorer), ce qui permettrait de réaliser l'astuce dans tous les cas : la construction ici est ce qui s'en approche le plus.

✱ Il faut que j'évoque encore une difficulté bizarre de la syntaxe française (ou plutôt, du fait de fusionner les rôles (A) et (B) du pronom relatif), c'est quand le même groupe occupe deux fonctions distinctes dans la phrase à subordonner. Par exemple :

{J'aime les concepts} # {Le nom des concepts éclaire les concepts} → {J'aime les concepts x {tels que le nom de x éclaire x}}

{J'aime les concepts} # {Le nom des concepts éclaire les concepts} [≡ {Le nom des concepts les éclaire}] → {J'aime les concepts {dont le nom les éclaire}}

{J'aime les concepts} # {Le nom des concepts éclaire les concepts} [≡ {Leur nom éclaire les concepts}] → {J'aime les concepts {que leur nom éclaire}}

En principe, il n'y a aucune difficulté particulière : les deux phrases j'aime les concepts {dont le nom les éclaire} et j'aime les concepts {que leur nom éclaire} sont tout à fait conformes à la syntaxe générale, et essentiellement équivalentes. (Remarquons que selon l'« astuce du dont » évoquée plus haut, on pourrait aussi défendre : j'aime les concepts {dont leur nom les éclaire}.) En pratique, on est généralement gêné quand on rencontre l'une de ces formulations, parce qu'on a dans le cerveau quelque chose qui hurle non, on n'a pas le droit de reprendre l'antécédent de la relative par autre chose que le pronom relatif !, et du coup, on a la sensation que quelque chose « ne va pas » et on cherche à éliminer les deux occurrences, malheureusement ni la phrase j'aime les concepts {dont le nom éclaire} [éclaire quoi ?] ni j'aime les concepts {que le nom éclaire} [le nom de quoi ?] n'a le sens qu'on veut ! Et du coup, quand les deux fonctions sont tout à fait parallèles, alors cette fois on a tendance à « faire d'une pierre deux coups » (ou d'un pronom relatif deux emplois) et ne reprendre qu'une fois :

{J'aime les concepts} # {Le nom des concepts éclaire le sens des concepts} → {J'aime les concepts x {tels que le nom de x éclaire le sens de x}}

• Logiquement on devrait écrire :

{J'aime les concepts} # {Le nom des concepts éclaire le sens des concepts} [≡ {Le nom des concepts éclaire leur sens}] → {J'aime les concepts {dont le nom éclaire leur sens}}

{J'aime les concepts} # {Le nom des concepts éclaire le sens des concepts} [≡ {Leur nom éclaire le sens des concepts}] → {J'aime les concepts {dont leur nom éclaire le sens}}

• Mais en pratique, on écrit plutôt, « d'une pierre deux coups » :

{J'aime les concepts} # {Le nom des concepts éclaire le sens des concepts} → {J'aime les concepts {dont le nom éclaire le sens}}

Pourquoi tant de haine ?

✱ Je peux aussi rapprocher de la difficulté précédente le problème particulier posé par la situation où la phrase à subordonner est en plusieurs morceaux qui vont logiquement ensemble mais où le groupe commun qui va devenir antécédent n'apparaît que dans un de ces morceaux. Je donne un exemple :

{Voici le texte} # ({Je vais étudier la syntaxe du texte,} et {j'ai l'intention de la comprendre parfaitement à la fin}) → {Voici le texte {dont je vais étudier la syntaxe,} et {dont j'ai l'intention de la comprendre parfaitement à la fin}}

— ici la difficulté est que le texte n'a aucune fonction dans la deuxième proposition de la phrase à subordonner (autrement que comme déterminant de la syntaxe qui est repris par un pronom). Du coup, on ne sait vraiment pas quel pronom relatif choisir (j'ai choisi dont un peu selon la logique de l'« astuce » générale évoquée plus haut : il faut imaginer un pronom relatif qui n'introduit aucune fonction particulière). Bien sûr, on peut faire une subordonnée unique (voici le texte {dont je vais étudier la syntaxe, et j'ai l'intention de la comprendre parfaitement à la fin}), mais selon la longueur des termes cela peut être plus ou moins maladroit. Le lecteur attentif aura remarqué que j'ai déjà utilisé dans cette entrée une tournure comme celle de la phrase ci-dessus.

✱ J'ai pour l'instant été assez vague sur le sens des subordonnées, mais il faut préciser qu'il y a deux sens principaux la frontière entre lesquels n'est pas toujours parfaitement nette : dans un premier sens, qu'on appelle restrictif ou déterminatif, il faut comprendre que les foobars {tels que blabla} limitent, à l'intérieur des foobars, ceux qui vérifient blabla, tandis que dans le second sens, qu'on appelle non-restrictif ou explicatif, il faut comprendre qu'on apporte deux informations sur l'ensemble de tous les foobars. La différence de sens, qui est en gros celle entre ∀x(P(x)⇒Q(x)) et ∀x(P(x)∧Q(x)), sauf que les choses ne sont jamais aussi claires dans les langues naturelles, tend à être indiquée, au moins en français et en anglais, par une virgule :

{Les lecteurs de ce blog me comprendront bien} # {Les lecteurs de ce blog maîtrisent la logique}

→ {Les lecteurs de ce blog {qui maîtrisent la logique} me comprendront bien} (i.e., parmi les lecteurs de blog, le sous-ensemble de ceux qui maîtrisent la logique me comprendra bien)

→ {Les lecteurs de ce blog, {qui maîtrisent la logique}, me comprendront bien} (i.e., les lecteurs de blog maîtrisent la logique et me comprendront bien)

La différence est moins claire au singulier (si de toute façon il existe un unique foobar, étant donné que le langage naturel a horreur de parler de l'ensemble vide, cela n'a pas trop de sens de se demander si on restreint son ensemble ou si on apporte une information de plus à son sujet). Dans toute la discussion précédente j'ai volontairement ignoré la différence entre ces deux sens puisque je me préoccupais uniquement de la syntaxe du mécanisme de subordination, pas de son sens.

La virgule censée marquer la différence peut disparaître à cause d'une incise : si j'écris les lecteurs de ce blog, je veux parler du mien, qui maîtrisent la logique, ce domaine si important, me comprendront bien, on ne sait plus dans quel cas de figure on est. À l'oral on la marque par une différence d'intonation, qui peut être plus ou moins évidente ou subtile selon le contexte, le locuteur, etc. En allemand (mais pas en néerlandais !, du moins il me semble), à l'écrit, toute subordonnée est introduite par une virgule, et du coup la différence entre le sens restrictif et non-restrictif des relatives n'est pas marquée : cela peut être gênant pour la compréhension, et c'est d'ailleurs étonnant pour une langue habituellement si précise (je suppose qu'un grammairien prescriptiviste imbécile a un jour décidé que la virgule avant les subordonnées était une bonne chose et qu'il allait la décréter obligatoire, sans réfléchir aux conséquences que cela entraînait) ; mais on peut parfois s'en sortir en changeant le démonstratif (par exemple derjenige suggère fortement le sens restrictif) et/ou le pronom relatif (welcher au lieu de der).

✱ Il faut que je dise encore un mot des subordonnées qui ne sont pas des relatives, que le français appelle subordonnées conjonctives, même si ce n'est sans doute pas une bonne idée de regrouper dans le même sac celles qui occupent une fonction essentielle dans la principale/subordonnante (comme je vois {que tu as embrouillé tes lecteurs}, à ne pas confondre avec la relative dans je vois les lecteurs {que tu as embrouillés}) et celles qui marquent une circonstance non-essentielle (comme tu devrais lire plus lentement {quand les choses sont compliquées}). Le sujet est un peu trop vaste pour que j'en parle en général, mais je veux évoquer un type particulier de subordonnées dont je crois qu'on ne les classe pas avec les relatives [que je crois qu'on ne classe pas avec les relatives ?], à savoir celles du discours indirect : il s'agit de phrases comme je veux savoir {qui tu as embrouillé} ou je veux savoir {quel lecteur tu as embrouillé}, qui sont différentes à la fois des relatives ((1) je comprends les lecteurs {que tu as embrouillés} : la subordonnée qualifie le groupe nominal les lecteurs) et des conjonctives « ordinaires » ((2) je comprends {que tu as embrouillé tes lecteurs} : la totalité du fait désigné par la subordonnée remplit la fonction d'objet dans la principale), puisqu'ici c'est l'identité de quelque chose, ou la réponse à une question indirecte, qui joue une fonction dans la principale ((3) je comprends {qui tu as embrouillé} : l'objet de comprendre n'est ni la personne qualifiée par la subordonnée comme dans l'exemple (1), ni le fait tout entier comme dans l'exemple (2), c'est l'identité de la personne, i.e., la réponse à la question qui as-tu embrouillé ?).

La raison pour laquelle je fais ce distinguo est qu'il y a des situations où on peut avoir ambiguïté. En effet, une subordonnée relative peut occuper toute seule une fonction dans la phrase principale, parce que celui (la personne) dans celui qui peut être omis : dans {qui veut voyager loin} ménage sa monture, il n'y a pas d'antécédent explicite à la subordonnée, il faut comprendre celui / la personne {qui veut voyager loin} ménage sa monture. De façon illogique, d'ailleurs celui que peut aussi se dire qui, c'est-à-dire que la forme qui du pronom est relatif est utilisée pour marquer l'omission de celui plutôt que pour indiquer la fonction dans la subordonnée. Et là les choses deviennent dangereusement confusantes : dans la phrase j'ai rencontré {qui tu aimes} on a affaire à une subordonnée relative et le sens est j'ai rencontré celui {que tu aimes} (l'objet de rencontrer est la personne désignée par la relative), alors que dans la phrase je sais {qui tu aimes}, on a une interrogative indirecte et l'objet de savoir est l'identité de la personne en question. Du coup, la phrase je vois qui tu aimes peut se comprendre de deux façons différentes en français : soit avec une relative je vois {qui tu aimes} c'est-à-dire je vois celui {que tu aimes}, soit avec une interrogative indirecte je vois {qui tu aimes}, i.e., je vois (=je comprends) l'identité de la personne que tu aimes. (Les deux sont d'ailleurs bien différentes de je vois {que tu aimes}.)

Si mon latin n'est pas trop pourri, je vois {qui tu aimes} (avec une relative) doit se dire video [eum] {quem amas} alors que je vois {qui tu aimes} (avec une interrogative indirecte) doit se dire video {quem ames}, la différence venant du fait que les interrogatives indirectes, en latin, prennent un verbe au subjonctif. (C'est en réfléchissant à ce que cela signifiait que je suis tombé sur cet exemple.)

Mais le plus bizarre, c'est le ce que du français : il peut s'analyser comme le pronom démonstratif neutre ce suivi du pronom relatif que, mais aussi comme un pronom interrogatif ce que (enfin, une « locution pronominale » interrogative, si on veut être pédant), auquel cas le ce est impossible à analyser autrement que comme un bout du tout, sans doute apparu par confusion avec la situation du pronom relatif. Ceci fait que la phrase j'ignore ce qu'il me dit peut s'analyser, exactement comme je vois qui tu aimes, de deux façons différentes : soit avec une relative, j'ignore ce {qu'il me dit} (c'est-à-dire qu'il me dit quelque chose, que je l'entends peut-être et que je le comprends peut-être mais que je décide d'ignorer cette chose qu'il me dit ; pour souligner : j'ignore ce qu'il me dit, je n'en tiens aucun compte), ou bien avec une interrogative, j'ignore {ce qu'il me dit} (c'est-à-dire que je suis ignorant de l'identité de ce qu'il me dit, par exemple parce que je ne l'entends pas : j'ignore la réponse à la question que me dit-il ? ; pour souligner : j'ignore ce qu'il me dit, je ne sais même pas quelle langue il parle). De même : je vois ce {que tu aimes} (avec une relative), i.e. je vois la chose que tu aimes, est différent de je vois {ce que tu aimes}, i.e., je vois (=je comprends) l'identité de la chose que tu aimes ; si mon latin n'est pas trop pourri, video [id] {quod amas} contre video {quid ames} (sur ce cas précis, le pronom aussi est différent). (De nouveau, les deux sont bien différentes de je vois {que tu aimes}.) La même ambiguïté doit exister pour ce qui. Mais il faut remarquer que parfois la différence sémantique est fine comme une lame de rasoir : entre les deux analyses possibles de j'ai entendu ce qu'il disait (relative ou interrogative indirecte, j'ai entendu la parole qu'il disait ou j'ai entendu l'identité de ce qu'il disait, audivi {quod dicebat} ou audivi {quid diceret} — je crois que le latin va nettement préférer l'interrogative), le sens est presque exactement le même, et c'est sans doute ce qui fait qu'il y a eu confusion.

✱ Ajout () : suite à une question/remarque intéressante en commentaire, il faut que je dise encore un mot sur le cas du français. Il me semble que ce même mot peut introduire (1) une subordonnée relative, comme dans voici l'endroit { nous nous sommes rencontrés}, même si dans ce cas la nature exacte de la phrase subordonnée n'est pas entièrement claire (nous nous sommes rencontrés à cet endroit ? ou en cet endroit ?), peut-être (2) une subordonnée conjonctive circonstancielle (i.e., non-essentielle), comme dans je reviens { nous nous sommes rencontrés}, analyse que je calque sur le modèle de j'étais heureux {quand nous nous sommes rencontrés}, mais on pourrait aussi préférer l'analyser comme une relative portant sur un adverbe implicite, i.e., je reviens [] { nous nous sommes rencontrés} comme je revois [celui] {qui nous a rencontrés}, ou enfin (3) une interrogative indirecte, comme je sais { nous nous sommes rencontrés}. • Les cas (1) et (3) sont assez peu problématiques, même si on peut certainement fabriquer des phrases ambiguës comme je l'ai fait au point précédent avec qui et ce que. En revanche, la question de savoir si je reviens où nous nous sommes rencontrés doit s'analyser comme une subordonnée relative avec un implicite ou comme une subordonnée circonstancielle de lieu ressemble à une question byzantine : apparemment les grammaires françaises (du moins celles que je trouve en ligne) ont choisi l'analyse comme une relative (et vont jusqu'à nier l'existence des subordonnées circonstancielles de lieu), mais aucune en prend le soin d'expliquer pourquoi cette analyse leur semble préférable (ou si c'est un choix purement arbitraire), on a l'impression que c'est comme ça semble être un argument suffisant dans le monde bizarre de ces grammaires. • En tout état de cause (et indépendamment de l'analyse qu'on en fait), j'ai toujours été choqué par le caractère hideusement asymétrique de la manière dont le français exprime les subordonnées indiquant le lieu et le temps, par exemple si je compare : d'une part, je serai présent où tu auras besoin de moi (peu importe qu'on l'analyse d'une manière ou d'une autre) avec je serai présent quand tu auras besoin de moi (l'analyse est forcément je serai présent {quand tu auras besoin de moi}), et d'autre part, je serai présent à l'endroit { tu auras besoin de moi} avec je serai présent au moment { tu auras besoin de moi}. Pourquoi dans un cas exprime-t-on le lieu avec et le temps avec quand alors que dans le second on exprime les deux avec  ? C'est peut-être un argument (celui que les grammaires omettent d'expliciter !) pour défendre l'analyse de je serai présent où tu auras besoin de moi comme une relative, mais en tout cas c'est une vraie bizarrerie du français. (En anglais, on dit fort logiquement : the place where you need me and the time when you need me, complètement parallèle de I am where you need me, when you need me, et il n'y a donc, en anglais, aucune raison de douter que l'analyse de where soit différente de celle de when.)

Il reste encore un certain nombre de subtilités que je n'ai pas évoquées, mais je crois que je vais m'en tenir là. Je vous laisse imaginer, cependant, à quel point j'ai pu emmerder mes instituteurs et profs de français (et d'autres langues, d'ailleurs) au collège et lycée, à explorer systématiquement les exemples tordus, les constructions bizarres, les cas non couverts par les règles qui venaient d'être énoncées, etc.

(samedi)

Petites notes sur la calculabilité, et quelques remarques à ce sujet

Je donnais jeudi matin une très courte[#] introduction à la calculabilité, dans le cadre d'un cours intitulé Théorie des Langages (donc un sujet plutôt connexe que contenant) dont j'enseigne à un groupe ; des circonstances anecdotiques (des feutres manquants[#2] au début de la séance, les élèves qui filent pour aller à un partiel à la fin) ont fait que je n'ai pas pu la finir correctement. J'ai donc envoyé des notes écrites[#3] aux élèves, auxquelles je n'ai pas résisté à la tentation d'ajouter quelques compléments en petits caractères. Comme ces notes (qui sont très basiques et passablement informelles même par rapport à ce que j'ai pu raconter sur le sujet sur ce blog) peuvent peut-être intéresser d'autres gens, je les mets en ligne ici. L'approche choisie consiste à ne pas chercher à définir formellement ce qu'est un algorithme (que ce soit par une machine de Turing ou autrement), vu que de toute façon on ne demandera à personne de programmer une machine de Turing, et pédagogiquement il semble que si on formalise un modèle de calcul, cela paralyse les étudiants au point qu'ils ne comprennent plus la notion d'algorithme alors qu'en entrant ils savaient.

[#] Et je trouve véritablement triste que dans une grande école dont l'informatique est une des spécialités, le seul contact que tous les élèves auront avec des notions aussi fondamentales que le problème de l'arrêt ou la notion de problèmes décidable et semi-décidable, c'est une séance d'une heure et demie dans le cadre d'un cours plutôt consacré à autre chose (et sur laquelle il est donc difficile de les interroger à l'examen).

[#2] Obtenir des feutres qui marchent au début de chaque cours peut être une véritable quête du graal.

[#3] Ils ont aussi un poly de cours (il n'a pas l'air d'être disponible publiquement), mais j'ai suivi une présentation différente dans mon exposé, suivant le principe qu'on comprend parfois mieux quand les choses sont expliquées deux fois de façon différente, et du coup j'ai repris mes notations dans ces notes.

Mais même en racontant des choses très basiques, on peut apprendre des choses ou s'éclaircir les idées. Notamment sur deux points, tous deux plus ou moins liés à l'énumération φ0,φ1,φ2,… des fonctions calculables partielles ℕ⇢ℕ. Il faut comprendre qu'on numéroté les programmes, par exemple par taille puis par ordre lexicographique, et que φe(n1,…,nk) est le résultat de l'exécution du e-ième programme auquel on fournit les arguments n1,…,nk, la valeur étant indéfinie si le programme ne (s'exécute pas correctement ou) ne termine pas. Un point important est qu'il existe un programme universel, c'est-à-dire que la fonction (e,n) ↦ φe(n) est elle-même calculable (informatiquement, cela signifie qu'on peut écrire un « interpréteur », qui prend un programme e et un paramètre n et exécute le programme sur cette entrée ; philosophiquement, cela signifie que le fait d'exécuter un algorithme est lui-même algorithmique). Les deux points qui m'avaient un peu échappés sont les suivants :

✱ Le premier point concerne le théorème s-m-n de Kleene. Si h(m,n)=φe(m,n) est une fonction calculable des deux variables m,n, alors pour chaque valeur de m elle est calculable dans la variable n : ça c'est plus ou moins une évidence ; mais ce qui l'est moins, c'est qu'on peut algorithmiquement fabriquer un indice s(e,m) pour cette fonction, au sens où φs(e,m)(n) = φe(m,n) avec s une fonction calculable — c'est ça que dit le théorème s-m-n. Informatiquement, cela signifie qu'il y a une transformation algorithmique (le s en question) qui prend un programme e prenant deux arguments m et n (ou en fait, deux jeux d'arguments), et une valeur à donner au premier, et qui renvoie un nouveau programme s(e,m) où ces arguments ont été fixés à cette valeur. Dans toute formalisme de calcul précis (que ce soit les machines de Turing, ou un langage de programmation réel), c'est plus ou moins évident — dans un langage de programmation fonctionnel, par exemple, cela signifie curryfier la fonction et appliquer à une constante — et la fonction s sera mieux que calculable (elle sera primitive récursive, et certainement beaucoup mieux que ça, parce que ce n'est pas un problème algorithmiquement difficile de substituer une valeur dans un programme !). Mais comme je n'introduisais pas de modèle de calcul précis, je me suis demandé si ça pouvait se démontrer in abstracto, à partir de la simple existence de l'énumération des fonctions calculables partielles et l'existence d'un programme universel.

La réponse est non, il existe des numérotations des fonctions calculables partielles qui vérifient le théorème d'universalité mais pas le théorème s-m-n. Un contre-exemple est fourni en définissant à partir d'une numérotation standard φe une nouvelle numérotation ψv+1,e(0)=v (et ψv,e(0) non définie), et sinon, ψv,e(n)=φe(n) (dans tout ça, ‹x,y› désigne un codage quelconque des couples d'entiers naturels par des entiers naturels) : autrement dit, dans la numérotation ψ, on précise séparément la valeur en 0 de la fonction (y compris « non définie ») et ses autres valeurs via une numérotation standard. Sur cet exemple, toute fonction calculable partielle apparaît bien dans les ψ, mais on ne peut pas calculer, à partir de d'un indice e d'une fonction calculable partielle h parmi les ψ, un tel indice pour la fonction constante de valeur h(1), car il faudrait pour cela déterminer si h(1) est défini (i.e., termine), donc résoudre le problème de l'arrêt. Donc on ne peut pas faire de substitution dans les ψ de façon algorithmique.

Pour raconter ce contre-exemple dans des termes informatiques, imaginons un langage de programmation permettant de coder des fonctions ℕ⇢ℕ (ou ℕk⇢ℕ, enfin peu importe) et qui est un langage tout à fait banal à une particularité près : la valeur en 0 de la fonction (qu'il s'agisse d'un entier ou du fait de partir en boucle infinie) doit être précisée par une instruction spéciale au début du programme, la seule instruction qui sera lue pour calculer cette valeur en 0, les autres valeurs étant calculées par un programme « normal » (par ailleurs, cette bizarrerie ne s'applique qu'à la fonction main, si j'ose dire, du programme). Interpréter ce langage, ou le compiler vers un autre, ne pose pas de problème particulier, et ce langage permet de représenter toutes les fonctions calculables partielles, ou d'ailleurs d'écrire un interpréteur pour un langage standard (une machine de Turing, disons) ou quelque chose comme ça. Mais il ne vérifie pas le théorème s-m-n, et ceci cause des bizarreries : on ne peut pas, par exemple, compiler un programme vers ce langage sauf à calculer à la compilation la valeur de la fonction en 0, ce qui risque de provoquer une boucle infinie ; et on ne peut pas algorithmiquement remplacer un programme dans ce langage par le programme qui calcule la (fonction constante égale à la) valeur en 1 de cette fonction. Ceci suggère que le terme Turing-complet est défini de façon un peu trop vague : à mon avis, ce qui importe est que l'énumération des fonctions partielles calculées par le langage considéré soit non seulement l'ensemble de toutes les fonctions calculables partielles, mais aussi que la numérotation soit acceptable au sens où on peut de façon calculable convertir une machine de Turing en le langage en question, et on peut montrer que cela revient exactement à vérifier le théorème s-m-n (avec une fonction s calculable).

(Référence pour tout ça : Soare, Recursively Enumerable Sets and Degrees, 1987, chapitre I, exercices 5.9 à 5.11. C'est de là que je tire le contre-exemple au théorème s-m-n.)

✱ Le second point concerne la fonction « castor affairé », qui à n associe le plus long temps d'exécution possible d'une machine de Turing à ≤n états et qui termine effectivement (en partant d'un ruban vide). Il est facile de voir que fonction, appelons-la h, dépasse infiniment souvent n'importe quelle fonction calculable [totale] f, au sens où, quelle que soit f calculable, il existe une infinité de n tels que h(n)≥f(n). (En effet si ce n'est pas le cas pour une certaine fonction f, quitte à modifier un nombre fini de valeurs de celle-ci, on a h(n)≤f(n) pour tout n, et on peut alors résoudre le problème de l'arrêt pour une machine de Turing — partant d'un ruban vide — en attendant f(n) étapes où n est son nombre d'états : si la machine ne s'est pas arrêtée au bout de ce temps-là, elle ne s'arrêtera jamais.) Mais le résultat classique dû à Tibor Radó est plus fort : la fonction h du « castor affairé » finit par dominer n'importe quelle fonction calculable f, au sens où, quelle que soit f calculable, l'inégalité h(n)≥f(n) est toujours vraie à partir d'un certain point, et je n'avais pas vraiment fait attention au fait que ce n'est pas trivial de passer de l'un à l'autre.

La démonstration d'origine de ce résultat (trouvable ici) est d'une part assez peu lisible (j'arrive à la suivre pas à pas, mais l'idée générale m'échappait) et d'autre part très spécifique au cas de la fonction « castor affairé » sur les machines de Turing en comptant leurs états. Par exemple, si on définit la fonction h en appelant h(n) la plus grande des valeurs φe(0) (ou φe(e), peu importe) qui soient définies pour 0≤en (l'argument montrant qu'elle dépasse infiniment souvent toute fonction calculable marche essentiellement pareil), alors est-il encore vrai que h finit par dominer n'importe quelle fonction calculable ? La réponse est oui, comme il résulte d'un échange sur math.stackexchange (je n'ai pas osé aller sur MathOverflow pour cette question), où on a pu m'expliquer beaucoup plus clairement l'argument de Radó, ce qui m'a permis de le généraliser facilement.

(J'en ai profité pour apprendre ce qu'est un degré de Turing hyperimmune, à savoir qu'il calcule une fonction qui dépasse infiniment souvent n'importe quelle fonction calculable, ce qui n'implique pas automatiquement qu'il calcule une fonction qui finit par dominer n'importe quelle fonction calculable.)

✱ Sinon, de fil en aiguille, je suis tombé par accident sur la relation suivante : pour A et B deux ensembles d'entiers naturels, notons AB lorsqu'il existe deux fonctions calculables partielles ℕ⇢ℕ qui se restreignent en des bijections réciproques entre ces deux ensembles. C'est une notion qui me semble extrêmement naturelle, mais qui n'est pas ce qu'on appelle de façon standard un isomorphisme calculable entre les deux ensembles. Mais ce qui me frappe, c'est que je n'ai réussi à en trouver aucune mention dans la littérature.

(mardi)

Après le rhinovirus, le norovirus

Remarque préliminaire : Même si je ne compte de toute façon pas entrer dans les détails, je rappelle à tout hasard que non seulement la lecture de mon blog n'est obligatoire pour personne, mais en plus la lecture d'une entrée particulière n'est pas nécessaire même si on veut lire la suite : il n'y a pas de contrôle de connaissances à la sortie. Je dis ça, parce qu'il y a régulièrement des vieux grincheux qui trouvent que tel ou tel sujet les incommode et qui s'en plaignent après coup dans les commentaires. D'ailleurs, de toute façon, l'information ne peut pas avoir de valeur négative, n'est-ce pas ? Ah non, zut.

Donc, juste après que j'ai posté une entrée pour me plaindre que les rhumes sont pénibles, un autre charmant virus est venu me rendre visite. Comme j'ai déjà posté il y a quelques années des remarques sur son mode de transmission, je ne vais pas les répéter. J'ai aussi déjà dit à cette occasion que je suis émétophobe, et d'ailleurs je crois que ça empire avec le temps, pas au point que ça affecte ma vie quotidienne, mais quand j'ai une gastro, l'anxiété à l'idée que je vais peut-être vomir est un désagrément comparable au mal au cœur lui-même. D'autant plus que quand il s'agit bien d'un virus (et a posteriori je n'ai aucun doute, même si j'ai aussi eu des aventures bactériennes — d'ailleurs passablement mystérieuses — par le passé), vomir n'aide absolument pas. Du coup, je n'hésite pas à prendre un antiémétique, en espérant que l'infection soit effectivement virale. En l'occurrence, la métopimazine. Qui est disponible en vente libre en France sous le nom de Vogalib® (en fait, il semble qu'il n'y ait quasiment qu'en France qu'on utilise la métopimazine, et je me demande bien pourquoi ; à ce sujet, il y a en eu une rupture de stock il y a quelques années qui a duré un bon nombre de mois, je me suis inquiété de tomber malade pendant ce temps, mais heureusement ce n'est pas arrivé). Après, peut-être que le fait qu'il soit en vente libre signifie qu'il est sans effet autre que placébo, je ne sais pas.

Mais il y a une chose qui est fascinante avec ce type d'infection, c'est sa régularité : je tiens un journal quotidien assez précis, et pour ce genre de maladie je note à quelle heure je commence à sentir quelque chose, à quelle heure je me sens mieux, etc. Et, même si ça ne m'arrive pas très souvent, heureusement, la progression semble toujours la même : ça commence par l'impression d'avoir trop mangé, mais elle ne passe pas, l'idée de manger ou la moindre odeur de nourriture deviennent de plus en plus répugnants, et le mal au cœur se développe progressivement, malgré des phases de répit occasionnelles, pendant assez précisément 14 heures (à compter des premiers symptômes) ; à ce moment-là, ça s'améliore assez soudainement (dans mon dernier cas, c'était vers 4h du matin dans la nuit de dimanche à lundi), même s'il faut encore huit à dix heures pour que j'aie envie de manger légèrement, et encore dix à douze heures supplémentaires, pendant lesquelles je reste très fatigué, avant d'être vraiment rétabli. Mais si ce planning est assez précis, ce que je n'ai jamais réussi à savoir dans aucun de mes cas de gastro, c'est comment je l'ai attrapée : apparemment, le virus incube pendant 12 à 48 heures avant l'apparition des premiers symptômes, et évidemment, avec un intervalle aussi imprécis en comparaison à la chronologie bien réglée que j'ai décrite, ce n'est pas facile de retrouver le poit de départ.

(dimanche)

De l'agacement provoqué par un téléviseur dont la télécommande ne marche plus

Il y a un peu moins de deux ans, j'ai remplacé l'antique téléviseur à écran cathodique que j'avais depuis une éternité (et qui m'avait d'ailleurs été offert par des gens à qui j'ai prêté mon appartement). Il marchait encore sans problème, c'est juste que ce n'était pas très pratigue d'utiliser un décodeur TNT externe. Apparemment, d'ailleurs, les télés CRT intéressaient encore des gens en 2014, parce que quand mon poussinet a mis la télé devant l'immeuble, le temps qu'il rentre chercher un papier sur lequel écrire le numéro d'enlèvement auprès du service des objets encombrants de la mairie de Paris, ce qui a pris environ une minute parce que nous habitons au rez-de-chaussée, la télé avait déjà disparu.

À la place, j'ai acheté un appareil LCD qui fait aussi décodeur TNT, magnétoscope numérique, moniteur, et sans doute d'autres formes de café, et qui coûtait 130€…

…chiffre à peu près représentatif de ce qu'il valait, c'est-à-dire, une proverbiale cheap plastic imitation, certainement chinoise. Ce n'est pas juste que je pense le plus grand mal des écrans LCD en général, mais à peu près tout était visiblement programmé en vitesse par des singes sous-payés. Par exemple, l'affichage des noms des émissions et autres informations de la TNT révélait un problème d'encodage des caractères (un peu dans ce genre-là, sauf que nous n'avons jamais réussi à deviner quels pouvaient être les deux jeux de caractères impliqués dans la confusion). Autre exemple, si on enregistre une émission sur clé USB et que le fichier stocké dépasse les 2Go, la télé plante et reboote (et reste allumée, et le fichier enregistré est, bien sûr, tronqué) : alors oui, je sais que le format FAT ne permet pas de stocker des fichiers de plus de 2Go (et que son successeur est totalement verrouillé par Microsoft donc essentiellement inutilisable), mais un appareil correctement programmé aurait pu, par exemple, couper tout seul le fichier en plusieurs morceaux en s'approchant de la limite fatidique. Encore un exemple, le réglage du son est linéaire et non logarithmique, donc quand on écoute la télé on a le choix entre 8 (pas assez fort) et 9 (trop fort) unités arbitraires alors que quand on écoute quasiment n'importe quelle vidéo, il faut mettre le réglage vers 90 ou au maximum et souvent ça ne suffit même pas. (Je me demande d'ailleurs pourquoi le niveau de mixage du son est si différent entre la TNT et la plupart des vidéos qu'on peut récupérer en ligne, mais ça au moins ce n'est pas la faute de la télé.) La télé met aussi un temps très long à changer de chaîne (c'est peut-être la faute de la TNT, je ne sais pas vraiment) et à s'allumer (ça c'est certainement plus la faute de la télé). Bref, je ne vais pas faire la liste de tout ce qui ne va pas dessus, vous avez déjà eu droit aux griefs sur mon réveil, vous pouvez imaginer le même genre de choses.

Si vous voulez le même modèle, ça s'appelle une Akira modèle LED-B81HU19F, terme dont la recherche donne un nombre ridiculement faible de résultats dans Google et bizarrement surtout en français (pourtant, l'interface n'est pas uniquement disponible en français).

Mais bon, mon poussinet et moi n'utilisons la télé que pour la regarder un petit peu pendant le dîner, ou très occasionnellement pour enregistrer une émission, ou pour changer un peu de l'ordinateur pour regarder une vidéo téléchargée sur Internet (du moins, si la télé sait en décoder le format, ce qui n'est pas le cas des MKV). Donc ce n'est pas très grave qu'elle soit merdique, et je l'ai achetée en connaissance de cause.

Seulement, il y a deux semaines, la télécommande est morte. Ce ne sont pas les piles, ce n'est pas non plus le capteur infrarouge sur le téléviseur, c'est bien la télécommande elle-même qui est morte. Je ne sais pas comment c'est possible que quelque chose d'aussi idiot tombe en panne, mais apparemment ça l'est. (Et elle n'a pas non plus subi de choc ou quoi que ce soit.)

Bon, le téléviseur n'est pas totalement inutilisable sans télécommande, il y a quelques boutons dessus qui permettent de l'allumer, de changer de chaîne (uniquement par ±1), de régler le volume, et même de faire apparaître un menu, mais plus moyen d'enregistrer, de changer la langue ou de faire apparaître les sous-titres. C'est un peu trop limité.

Pourquoi ne pas acheter une télécommande universelle ? Le truc est que la marque, et à plus forte raison le modèle, de notre téléviseur sont tellement obscurs qu'ils semblent en-dehors du champ d'application du mot universel (d'après la liste des marques indiquée au dos), et je n'ai pas envie de payer >10% du prix du téléviseur pour confirmer que la télécommande universelle ne fonctionne pas avec. Nous n'avons pas non plus de smartphone avec émetteur infrarouge qui permettrait de servir de télécommande universelle. (Et ma calculatrice HP48 de quand j'étais en prépa ne s'allume plus.) Il y a des gadgets infrarouge sur USB, mais sans les codes émis par la télécommande d'origine, ce ne serait pas évident d'en faire quoi que ce soit. <Insérer ici un rant selon lequel la commercialisation de n'importe quel appareil disposant d'une télécommande devrait obliger le fabriquant à publier l'intégralité des codes émis par cette télécommande sous un format facilement réutilisable par des émetteurs infrarouge.>

Nous avons aussi essayé, à tout hasard, de brancher un clavier sur le port USB du téléviseur, histoire de voir s'il réagissait à quelque chose (comme les combinaisons Alt+SysRq), mais apparemment pas.

Bref, tout ça a quelque chose de plus frustrant que si la télévision était entièrement tombée en panne. Ce n'est pas grave, je rachèterai une autre merde chinoise à une centaine d'euros qui tombera en panne dans deux ans, et nous mettrons celle que nous avons dehors où elle disparaîtra dans la minute — mais c'est quand même idiot.

(samedi)

Un médicament qui a peut-être de l'effet, ou peut-être pas

Je suis très souvent enrhumé (en tout cas, trop souvent à mon goût, peut-être trois fois dans une année typique). Même si les symptômes n'en sont pas très graves, la fatigue qu'ils provoquent, combinée au fait qu'ils empêchent aussi de bien dormir, rendent l'expérience quand même bien pénible, surtout quand elle tombe pendant une période où j'enseigne (d'où nécessité de se lever à une heure fixée, et d'exercer sa voix ce qui fatigue et assèche la gorge). Et les médicaments pour soigner ces symptômes sont d'une efficacité franchement très limitée. Alors quand ma maman m'a fait la pub de ce qu'elle m'a décrit comme un médicament miracle contre le rhume, je me suis dit que je n'y croyais pas du tout (j'ai un peu tendance à penser que presque aucun médicament en vente libre n'a le moindre effet, parce que s'ils avaient de l'effet ils auraient des effets nocifs et que du coup le principe de précaution ferait qu'ils ne seraient pas en vente libre), mais que, après tout, un placebo en plus dans mon arsenal, ça ne fera sans doute pas de mal. (Après, je n'ai jamais eu de réponse très claire à la question de savoir si un placebo peut fonctionner même si le patient est persuadé qu'il ne fera rien.)

Le médicament en question est un spray nasal qui porte en France le nom commercial de SurbroncViral : le principe actif est le ι-carraghénane qui a une activité antivirale. Peut-être. L'emballage publicitaire du médicament met surtout en valeur le fait qu'il réduit la durée du rhume. Il y a en effet quelques études publiées qui concluent à un effet bénéfique (par exemple Eccles, Meier &al, Efficacy and safety of an antiviral Iota-Carrageenan nasal spray […], Respiratory Research 11 (2010), ou plus récemment Ludwig, Enzenhofer &al. Efficacy of a Carrageenan nasal spray in patients with common cold […], Respiratory Research 14 (2013) ; il y en a encore un paquet d'autres) ; sauf que ces études sont financées par la boîte qui commercialise le produit, et la plupart des auteurs sont employés par elle… Après, je crois qu'en fouillant j'avais fini par trouver une étude où le conflit d'intérêt était, disons, moins évident, et dont le résultat était moins clair mais néanmoins positif, alors que je n'en ai pas trouvé qui annonce un résultat négatif, donc peut-être quand même que ma méta-analyse à 0.02¤ était positive. (Mais les revues médicales publient-elles facilement des articles qui concluent à une absence de résultat ? C'est un peu un problème intrinsèque de la publication scientifique qu'il biaise les résultats visibles en direction de ce qui sera considéré comme « intéressant ».) Et puis, finalement, c'est peut-être moi qui suis biaisé à trop me méfier.

Après tout, ce n'est pas une question si grave : même si le médicament coûte un prix un peu exorbitant, pourquoi ne pas juste me faire une idée par moi-même ?

J'ai eu un énorme rhume la semaine passée. J'ai utilisé le SurbroncViral™ comme indiqué par la notice. Ce que j'ai observé est que (A) mon rhume m'a encore plus fatigué que d'habitude (je ne prétends pas du tout que le médicament y soit pour quelque chose, bien sûr !, c'est plutôt un signe que c'était un « gros » rhume), (B) il a duré à peu près le temps que mes rhumes durent habituellement, (C) j'ai eu beaucoup moins le nez bouché que d'habitude (normalement je passe trois nuits entières à respirer par la bouche, là juste quelques heures, et encore, mon nez n'était pas complètement bouché), mon rhume a surtout pris la forme d'une sensation de froid, de fatigue, de maux de tête et de sinus douloureux, (D) j'ai aussi un peu moins toussé dans l'ensemble, et (E) j'ai l'impression que mon système imunitaire a maintenant éliminé le virus mais que mon nez continue à couler plus que normal et en tout cas mes sinus sont toujours enflammés. Est-ce que tout ceci est significatif ? Non, sans doute pas — à part peut-être le (C), toutes ces variations tombent à l'intérieur des fluctuations statistiques des mes rhumes typiques. (Dont je me demande, d'ailleurs, si elles sont plutôt dues à la différence entre souches de virus ou dans la réaction immunitaire de mon corps d'une fois sur l'autre.)

Bref, je ne sais pas quoi conclure. Peut-être que le médicament a fait de l'effet en me laissant le nez plus dégagé. Peut-être pas. Pour faire une étude scientifique, il faut un échantillon statistiquement représentatif, il faut faire les choses en double aveugle. Là, je n'ai pas d'échantillon représentatif, et je ne veux certainement pas faire les choses en double aveugle (je m'en fous de comparer à un effet placebo, l'effet placebo[#] m'intéresse autant que l'effet « réel »). Je déteste prendre des décisions avec des informations trop incomplètes — mais bon, c'est presque la définition de la vie, ça. Bref, je vais continuer à utiliser ce produit comme je continue à prendre beaucoup de vitamine C pendant mes rhumes : même si je ne crois pas vraiment que ça fasse du bien, je crois encore beaucoup moins que ça fasse du mal.

[#] Enfin, on ne devrait pas dire l'effet placebo, parce qu'il y en a plein : un effet purement psychologique (je prends un médicament, je me dis que je vais mieux), un effet somatique de cet effet psychologique (je me dis que je vais mieux, je me mets objectivement à aller mieux), et sans doute encore plein d'autres.

(mercredi)

Quelques clarifications sur l'intuitionnisme et l'ultrafinitisme

En relisant l'entrée précédente que j'ai écrite et un ou deux commentaires qui ont été postés dessus, j'ai peur d'avoir pu laisser imaginer que je considérais les mathématiques intuitionnistes/constructives comme aussi farfelues que l'existence d'un entier strictement compris entre 3 et 4, ou même, qu'un nombre non-négligeable de mathématiciens pourraient le considérer. Ce n'est certainement pas le cas : la seule chose que je compare, c'est la frustration que peut ressentir (superficiellement) un mathématicien classique devant ces mondes étranges (comment ça, il n'est pas toujours vrai que tout nombre réel x vérifie x≥0 ou x≤0 ???). Mais il vaut la peine de se demander pourquoi, au juste, parmi les trois « abandons » suivants,

la première donne indiscutablement lieu à des mathématiques sérieuses, la seconde peut-être mais peut-être pas, et la troisième certainement pas.

Ce que veut avant tout le mathématicien, c'est que les règles du jeu soient claires. Même si on ne prend pas la position formaliste extrême qui considère les maths comme un jeu typographique formel consistant à manipuler des successions de symboles dénués de sens selon des règles arbitraires mais relativement simples[#], les mathématiciens seront sans doute unanimes pour dire qu'il est essentiel dans la pratique des mathématiques qu'il existe des règles objectives et inambiguës sur les manipulations autorisées dans l'écriture d'une démonstration, suffisamment claires pour qu'on puisse toujours, avec assez de patience, trancher un différend sur la validité d'une démonstration en détaillant n'importe quel passage incriminé jusqu'à l'application mécanique de ces règles.

Or les mathématiques intuitionnistes/constructives ont des règles claires : ce ne sont pas les mêmes que les mathématiques classiques (plus exactement ce sont un sous-ensemble, ou une restriction, selon la présentation exacte choisie ; mais du coup, on peut ajouter des axiomes supplémentaires pour compenser qui contrediraient les mathématiques classiques), mais au moins — dans leur formulation moderne[#2] — ce sont des règles indiscutablement bien formulées et objectives. Plus exactement, le mathématicien classique peut comprendre les règles des mathématiques intuitionnistes/constructives par plusieurs mécanismes :

(Ces deux approches sont elles-mêmes reliées par des théorèmes de validité et de complétude : je ne rentre pas dans les détails.) On peut par ailleurs relier la logique intuitionniste à d'autres logiques alternatives mais classiques et bien comprises (par des procédés comme ci-dessus), par exemple la logique modale S4.

[Ajout ] Je peux au moins donner une idée de ce dont je parle sous la forme suivante. En mathématiques classiques, si on décide d'interpréter les connecteurs logiques PQ, PQ et ¬P comme décrivant l'intersection, la réunion, et le complémentaire de parties P et Q d'un ensemble T fixé, alors certainement on a ¬¬P=P (le complémentaire du complémentaire d'une partie est la partie elle-même, justement parce qu'on travaille en logique classique) et ¬(PQ)=(¬P)∨(¬Q) ; maintenant, changeons un peu le contexte, et considérons T un espace topologique, imaginons que P et Q sont des ouverts de T, que PQ et PQ désignent l'intersection et la réunion de deux ouverts, mais maintenant ¬P désigne l'intérieur du complémentaire de P (=le plus grand ouvert disjoint de P ; et plus généralement, on peut noter PQ pour l'intérieur de la réunion de Q avec le complémentaire de P, c'est-à-dire l'ouvert des points au voisinage desquels P est inclus dans Q) : alors ¬¬P ne coïncide plus forcément avec P, c'est le « régularisé » de P (=l'intérieur de son adhérence), et de même ¬(PQ) ne coïncide plus forcément avec (¬P)∨(¬Q) (alors que ¬(PQ), lui, coïncide toujours avec (¬P)∧(¬Q)) ; en fait, les règles valables en général dans cette interprétation sont précisément celles du calcul propositionnel intuitionniste, et sont une manière dont le mathématicien classique peut les comprendre (sémantiquement) : comme des affirmations sur les ouverts d'un espace topologique (classique).

D'autre part, les mêmes choses sont valables dans l'autre sens, c'est-à-dire que si on peut « expliquer » les mathématiques intuitionnistes aux mathématiciens classiques comme ci-dessus, on peut aussi « expliquer » les mathématiques classiques aux mathématiciens intuitionnistes (par exemple par l'insertion de doubles négations à des endroits stratégiques). Du coup, les mathématiciens classiques et intuitionnistes ne seront peut-être pas d'accord sur l'intérêt ou la signification des énoncés qu'ils démontrent, mais au moins chacun peut-il expliquer son travail aux autres. (Dans la pratique, bien entendu, les « mathématiciens classiques » et à plus forte raison les « mathématiciens intuitionnistes » ne sont que des archétypes idéalisés : tout le monde est capable de faire sa traduction mentale dans un sens ou dans l'autre, quelle que soit sa représentation préférée de l'Univers.)

Pour dire les choses de façon plus concise : les mathématiques classiques et intuitionnistes sont peut-être différentes, mais leur métamathématique est compatible.

Il en va tout autrement de l'idée qu'il existerait un entier strictement entre 3 et 4 : cette idée fictionnelle est présentée sans être accompagnée de règles permettant de travailler avec et de lui donner un sens. Il n'est pas exclu que de telles règles puissent exister (par exemple : en fait, ce qu'on appelle entier ici est un élément de ℕ[√13] = {u+v·√13 : u,v∈ℕ} (approche sémantique), et il faudrait remplacer les axiomes de Peano par une axiomatisation des faits les plus évidents de la théorie du premier ordre de ℕ[√13] (approche syntaxique)), et qui du coup ferait disparaître le mystère de cette idée (à défaut de lui donner un intérêt…). Mais telle quelle, l'idée est dépourvue de sens aux yeux des mathématiciens parce qu'elle est dépourvue de règles précises.

L'idée intermédiaire (l'ultrafinitisme, j'en ai déjà parlé) occupe une position intermédiaire : on peut peut-être donner un sens à l'ultrafinitisme, mais l'idée est radicale en ce sens qu'elle nécessite de changer non seulement les mathématiques mais aussi les métamathématiques. Notamment, pour refuser l'existence du nombre 10↑(10↑100), il faut refuser l'idée qu'une démonstration puisse occuper un tel nombre de symboles — or les métamathématiques classiques l'admettent (certes, on ne va pas l'écrire explicitement, mais les métamathématiques classiques admettent de considérer comme démonstrations valables des objets qui ne pourraient pas être écrits en pratique, au moins si on en a une description raisonnablement (méta)manipulable) ; pire, il faut probablement refuser l'idée qu'une démonstration puisse occuper seulement 10↑100 symboles (parce qu'en environ ce nombre là de symboles, je peux démontrer l'existence de 10↑(10↑100) à quelqu'un qui admet que la multiplication sur les entiers est totale, ce que de nombreux ultrafinitistes admettent, ce qui permet d'écrire des choses comme 10×10×10×⋯×10), et il faut donc probablement refuser l'idée même d'utiliser « librement » l'arithmétique pour faire des métamathématiques. Je ne suis moi-même pas à l'aise avec l'ultrafinitisme (j'ai vraiment du mal à ne pas considérer la position comme simplement ridicule), mais voici ce qu'écrivent Cherubin & Mannucci dans A very short history of ultrafinitism (in : Kennedy & Kossak (eds.), Set Theory, Arithmetic, and Foundations of Mathematics (Cambridge 2011)) :

First, the rejection of infinitary methods, even the ones based on the so-called potential infinite, must be applied at all levels, including that of the meta-mathematics and that of the logical rules. Both syntax and semantics must fit the ultrafinitistic paradigm. Approaches such as Finite Model Theory are simply not radical enough for the task at hand, as they are still grounded in a semantics and syntax that are saturated with infinite concepts.

Second, barring one term in the dichotomy finite-infinite, is, paradoxically, an admission of guilt: the denier implicitly agrees that the dichotomy itself is valid. But is it? Perhaps what is here black and white should be replaced with various shades of grey.

Bref, même si le programme ultrafinitiste peut sembler à quelqu'un comme moi aussi fantaisiste que l'idée qu'il y aurait peut-être un entier à découvrir strictement entre 3 et 4, il faut avoir la modestie d'admettre que peut-être des règles du jeu précises peuvent en être données, fussent-elles des règles qui imposent de réévaluer aussi les métamathématiques : peut-être le programme peut-il être éclairci comme l'intuitionnisme l'a été, et peut-être sera-t-il possible aux mathématiciens « idéalistes » de comprendre précisément les ultrafinitistes (à défaut d'être d'accord avec eux).

[#] Je ne vais pas faire l'exercice ici et maintenant, mais il est parfaitement possible de présenter un ensemble des « règles du jeu » qui soit compréhensible par à peu près n'importe qui (disons, pas plus compliqué que les règles des échecs ou du tarot) et qui, appliquées mécaniquement, permette de démontrer tous les théorèmes des mathématiques « standard » (ZFC) et uniquement ceux-ci. En ce sens, donc, n'importe qui peut faire des maths formelles : la difficulté du travail du mathématicien est de se faire une idée d'où on va dans ce jeu et comment on peut atteindre un but, et communiquer à d'autres le fait qu'on l'a atteint, sans écrire toutes les étapes intermédiaires.

[#2] Dans leur formulation moderne, c'est-à-dire, je crois, depuis les travaux de Gödel, Heyting, Kolmogorov et d'autres. Lorsque Brouwer a initialement introduit ses idées, il n'était probablement pas clair qu'elles pouvaient être rigoureusement formalisées, d'autant qu'il était lui-même profondément hostile à l'idée de formaliser les mathématiques, de les priver de leur aspect créatif/intuitif ou de les réduire à un jeu typographique ; et c'est peut-être pour ça que ces idées ont d'abord suscité une telle hostilité (non seulement elles étaient radicales, mais en outre elles n'étaient sans doute pas bien définies aux yeux de mathématiciens comme Hilbert).

(vendredi)

L'entier caché entre 3 et 4, et autres réflexions idiotes

J'avais déblatéré il y a quelques années sur la question mensaphilosophique [:= de philosophie de comptoir] de savoir si les mathématiques pourraient être différentes : je m'étonne de ne pas y avoir fait de lien vers la nouvelle The Secret Number d'Igor Teper qui évoque la possibilité d'un entier secret (bleem) caché strictement entre trois et quatre. Je crois pourtant que je connaissais cette nouvelle à ce moment-là ; ce que j'ai appris tout récemment, en revanche, c'est que cette nouvelle a été adaptée sous forme de court-métrage (ici sur Vimeo, ici sur YouTube) : je ne sais pas si je trouve l'adaptation (ni la nouvelle pour commencer) terriblement efficace dans son traitement de la prémisse, mais l'atmosphère un peu angoissante n'est pas mal rendue, et en tout cas ça se laisse regarder.

Assurément, cette prémisse à quelque chose de délicieusement provoquant dans son absurdité : comment pourrait-il exister un entier strictement entre trois et quatre, fût-ce dans une version alternative des mathématiques ou dans un monde fictionnel ? Car dans toute présentation raisonnable, la définition de l'entier quatre est qu'il est le successeur de trois, donc à moins de supposer que les noms ont juste été décalés d'un cran (ce qui sous-tend la notion mathématique d'isomorphisme de structures, i.e., un simple renommage de la même structure), disons si on est d'accord que les opérations usuelles sur les entiers donnent leurs résultats attendus par tout le monde, il ne peut rien y avoir d'inattendu entre trois et quatre. D'ailleurs, s'il y avait une telle chose, on aurait envie de poser tellement de question (combien font bleem moins trois ? bleem fois deux ? bleem sur deux ? bleem est-il pair ou impair ? bleem virgule zéro est-il avant ou après trois virgule cinq ? combien y a-t-il d'entiers entre un et dix inclus en comptant bleem d'une part, et sans compter bleem de l'autre ? et au fait, comment un entier pourrait-il être supprimé et par qui ? que sont devenus les animaux à bleem paires de pattes ? pourquoi un dé à six faces ne tombe-t-il jamais sur la face bleem ? et d'ailleurs, s'il ne tombe jamais dessus, pourquoi ne tombe-t-il pas une fois sur cinq sur chacune des six moins une égale cinq faces restantes ?). Mais bien sûr, en posant ces questions, je fais partie du vaste complot des mathématiciens qui cherchent à vous faire croire que bleem n'existe pas. 😈

Mais ces questions, et l'impuissance qu'on ressent face à quelqu'un qui affirmerait dur comme fer qu'il y a un entier strictement entre

trois et quatre

sont intéressants parce qu'ils soulignent la difficulté qu'il y a, et le sentiment d'impuissance qu'on ressent, à débattre avec quelqu'un qui soutient une thèse qu'on juge logiquement absurde. Qu'il s'agisse de l'existence d'un entier strictement entre trois et quatre qu'il ne peut pas vous montrer, ou le fait que la Terre soit vieille d'environ 6000 ans, ou le fait que le nombre 10↑(10↑100) n'existe pas ou que les mathématiques sont une invention humaine. Et il faut alors se rappeler qu'à ses yeux, c'est le contraire qui vaut (c'est moi qui essaye de convaincre que 10↑(10↑100) existe, par exemple, alors que je suis incapable de le montrer ou même de l'écrire !). Et malgré ça, il ne faut pas céder au relativisme extrême qui voudrait que chacun a sa petite vérité à lui et qu'il n'y a rien de moins valable à croire qu'il y a un entier strictement entre trois et quatre ou que la Terre est vieille d'environ 6000 ans, ou autres idées dans le même genre. (Ou, pour reprendre un thème que j'ai abordé récemment, que les mathématiques seraient contradictoires.) Contre la stupidité, les dieux eux-mêmes luttent en vain.

Mais ce qui est amusant dans l'affaire, c'est aussi que je tombe sur ce film au moment où je lis des textes mathématiques[#] sur l'intuitionnisme/constructivisme (je ne veux pas rentrer dans les explications sur la différence entre ces deux termes, qui dépend d'ailleurs des auteurs), ce monde parallèle bizarre où le tiers exclu ne s'applique pas forcément, avec toutes les conséquences bizarres que cela entraîne, ou plutôt, toutes les conséquences habituelles cela n'entraîne plus[#2]. Le mathématicien classique ne partageant pas les principes philosophiques du constructivisme (et je fais partie de ces mathématiciens classiques) peut se demander quel est l'intérêt de considérer ce monde étrange et exotique qui peut sembler aussi déstabilisant que l'existence d'un entier strictement entre trois et quatre : à mon avis il est double, (A) côté positif, si on arrive à montrer un résultat de façon purement constructive (sans faire appel au tiers exclu), on obtient souvent plus que sa validité classique (par exemple, on obtient souvent un algorithme construisant un objet dont on aurait démontré l'existence ; on obtient aussi automatiquement le résultat dans des contextes différents comme des catégories de faisceaux, et ainsi de suite), et (B) côté négatif, si le résultat n'est pas valable constructivement, cela informe sur certaines formes de raisonnement qu'on sera obligé de faire, et globalement l'exercice de chercher à démontrer des résultats bien connus (par exemple de l'analyse de première année de licence) dans le cadre constructif aide à prendre conscience de la structure des raisonnements qu'on fait (notamment, l'emploi de l'axiome du choix et du tiers exclu). Bref, parfois les fictions selon lesquelles les mathématiques peuvent être différentes sont intéressantes et bien fondées !

[#] Petite biblographie à toutes fins utiles : • Anne S. Troelstra & Dirk van Dalen, Constructivism in Mathematics (An Introduction) (North-Holland, 1988, deux volumes), une introduction assez agréable à lire et qui donne de bonnes explications intuitives (y compris pour le mathématicien habitué à la logique classique, contrairement à d'autres textes intuitionnistes/constructivistes qui font comme si tout le monde partageait naturellement ce point de vue) et des notes historiques. • Michael J. Beeson, Foundations of Constructive Mathematics (Metamathematical Studies) (Springer, 1985) • Errett Bishop & Douglas Bridges, Constructive Analysis (Springer, 1985) • Douglas Bridges & Fred Richman, Varieties of Constructive Mathematics (Cambridge University Press, 1987) • James Lipton, Realizability, Set Theory and Term Extraction, in : de Groote, The Curry-Howard Isomorphism (1995) (en ligne ici) • Jaap van Oosten, Realizability: An Introduction to its Categorical Side (Eslevier, 2008), qui décrit essentiellement un modèle non-classique très important des mathématiques constructives (le topos effectif)

[#2] Quelques exemples : on ne peut pas montrer qu'il existe des fonctions ℕ→ℕ non calculables, ni qu'il existe des fonctions ℝ→ℝ discontinues, ni qu'il n'existe pas d'injection ℝ→ℕ ; on ne peut pas montrer que pour tout x réel on a x≥0 ou x≤0, même si ceci est quand même le cas pour les rationnels ; on ne peut pas montrer que les constructions des réels à partir des rationnels par coupures de Dedekind et par suites de Cauchy coïncident, ni que toute suite bornée croissante de réels converge ; on ne peut pas montrer que l'ensemble des parties d'un singleton est fini, ni même « subdénombrable », et on ne peut pas montrer que l'image d'un ensemble fini par une fonction est fini, il est seulement « subfini ».

Bon, quoi qu'il en soit, je souhaite à tous mes lecteurs une excellente année 2015½ pleine de santé et de bonheur !

(lundi)

Comment utiliser les points comme parenthèses ?

Dans une expression mathématique comme

(2+2+2)×(3+4)

les parenthèses servent à indiquer quelles sous-expressions doivent être calculées en premier (la convention, en leur absence, étant qu'on évalue les multiplications avant les additions, si bien que 2+2+2×3+4 sans parenthèses se comprend comme 2+2+(2×3)+4). Mais il existe d'autres manières possibles d'indiquer l'ordre des opérations sans utiliser de parenthèses — ou en tout cas pas sous cette forme. Une possibilité consisterait à utiliser la notation préfixe (où le symbole d'une opération binaire précède les deux quantités sur lesquelles elles s'applique, ce qui donne dans ce cas : × + + 2 2 2 + 3 4) ou bien postfixe (où l'opération binaire suit les deux quantités sur lesquelles elle s'applique, donc 2 2 + 2 + 3 4 + × comme on le taperait sur une calculatrice à notation polonaise inversée), mais ces conventions sont extrêmement peu lisibles pour un humain.

Une autre façon de noter les choses, qui me semble assez intéressante ou en tout cas instructive, même si elle n'a jamais vraiment été utilisée en-dehors de la logique, consiste à utiliser les points comme parenthèses, que je veux présenter et discuter un peu. Sur mon exemple, cette notation donnerait :

2+2+2.×.3+4

avec des points autour du symbole de multiplication pour marquer qu'il doit être effectué après les additions. (On va supposer que le point n'est pas utilisé comme séparateur décimal, ou qu'il y a quelque magie typographique qui évite l'ambiguïté : ni ici ni ailleurs dans cette entrée il n'y a de nombres fractionnaires.)

La manière dont on lit une telle expression est la suivante : on commence par la séparer aux endroits où se trouve des points, on évalue tous les morceaux qui ont un sens en tant qu'expression (en l'occurrence, 2+2+2 et 3+4), puis on réattache les morceaux remplacés par leur valeur (ce qui donne 6×7).

Lorsqu'il y a plusieurs niveaux d'imbrications, on utilise des groupes formés d'un nombre de points croissant pour séparer les niveaux : la règle est alors qu'on commence par regrouper les morceaux séparés par un seul point, puis par un groupe de deux, puis de trois, et ainsi de suite. (Ainsi, un groupe d'un plus grand nombre de points correspond à un niveau de parenthésage plus « extérieur ».) Par exemple,

(14/(1+1))×(6+7)×(30−(6+5))

peut se réécrire dans la notation « ponctuée » comme

14/.1+1:×.6+7.×:30−.6+5

et pour l'évaluer, on commence par calculer les morceaux séparés par des points qui ont un sens tout seuls (1+1, 6+7 et 6+5), puis on regroupe les morceaux séparés par de simples points (14/.1+1 soit 14/2, et 30−.6+5 soit 30−11), et enfin on regroupe les morceaux séparés par deux points. Pour plus de symétrie quant au niveau d'opération × dans le facteur central, on peut préférer écrire

14/.1+1:×:6+7:×:30−.6+5

ce qui est peut-être plus lisible, surtout si on reflète le nombre de points dans l'espacement de la formule :

14/.1+1 :×: 6+7 :×: 30−.6+5

On peut bien sûr utiliser des symboles pour les groupes de deux, trois, quatre points et ainsi de suite : si je récupère des symboles Unicode pas vraiment fait pour, l'expression 6−(5−(4−(3−(2−1)))) peut se ponctuer en 6−∷5−∴4−:3−.2−1, mais généralement on se contente de mettre plusieurs caractères ‘.’ ou ‘:’ d'affilée pour représenter un groupe, comme 6−::5−:.4−:3−.2−1 (il faut traiter ces deux écritures comme parfaitement synonymes).

Les points servent donc à la fois de parenthèses ouvrantes et fermantes : il n'y a en fait pas d'ambiguïté car la directionalité est indiquée par la position par rapport aux symboles d'opérations (si je vois 20−.1+1, cela ne peut signifier que 20−(1+1) car (20−)1+1 n'a pas de sens) ; plus exactement, chaque groupe de points doit être adjacent à un symbole d'opération (sauf si on omet la multiplication, cf. ci-dessous), et correspond à une parenthèse soit ouvrante soit fermante selon qu'il est immédiatement après ou avant l'opération. Et la parenthèse court jusqu'au prochain groupe de points (vers la droite ou vers la gauche, selon le cas évoqué) dont le nombre de points est supérieur ou égal à celui considéré, ou à l'extrémité de l'expression (où se sous-entend un nombre infini de points, si on veut ; ainsi, sur mon premier exemple, on écrit 2+2+2.×.3+4 et non .2+2+2.×.3+4.).

Pour ceux qui veulent des règles plus formelles, je propose les suivantes. En écriture, si on a un arbre d'analyse formé d'opérations possiblement associatives, disons x1x2⋆…⋆xk (pour une certaine opération ici notée ⋆, et avec k=2 si l'opération ⋆ n'est pas supposée avoir d'association par défaut), pour la transformer en « expression ponctuée », on écrit de façon récursive chacun des sous-arbres x1,x2,…,xk comme expression ponctuée, et on concatène ces écritures en plaçant à gauche de chaque symbole ⋆ un groupe de points dont le nombre est strictement supérieur au nombre de points de n'importe quel groupe apparaissant dans l'écriture de la sous-expression gauche (si celle-ci est un atome = une feuille de l'arbre, c'est-à-dire un nombre ou une variable, on peut ne mettre aucun point) ; et de même à droite. Il est admissible de mettre plus de points que nécessaire, par exemple si on veut mettre le même nombre à gauche et à droite de chaque ⋆ intervenant à un niveau donné. On peut, bien sûr, avoir des règles supplémentaires lorsqu'on suppose une certaine priorité des opérations (par exemple, (3×2)+1 peut être noté 3×2+1 si on admet que la multiplication est prioritaire sur l'addition ; toutefois, ceci ne s'applique essentiellement qu'au niveau le plus bas : (3×(1+1))+1 devra certainement être noté 3×.1+1:+1, parce qu'on ne gagnerait rien que de la confusion à le noter 3×.1+1.+1). • Inversement, pour décoder une telle expression, on va, pour n allant de 0 au nombre maximum de points dans un groupe, remplacer chaque expression maximale de la forme x1x2⋆…⋆xk avec les xi des sous-arbres déjà constitués (ou des atomes), en ignorant les groupes de ≤n points pouvant intervenir à gauche ou à droite de l'opération ⋆, par un sous-arbre (ou un bloc parenthésé, si on préfère).

Ce système de notations ne recouvre pas tous les cas possibles d'usage des parenthèses. Disons qu'il nécessite plus ou moins qu'il y ait des symboles d'opérations dans l'histoire : si on a affaire à un contexte mathématique dans lequel on donne un sens différent aux notations u(v) et (u)v (ce qui, honnêtement, ressemble à une très mauvaise idée), ou à u et (u) (même remarque), alors on ne peut pas utiliser des points à la place des parenthèses.

Néanmoins, il marche dans des situations un peu plus générales que ce que j'ai présenté ci-dessus. Par exemple, il continue de fonctionner même si on décide de ne pas écrire le symbole × de multiplication : notamment, si dans la version parenthésée, au lieu de (14/(1+1))×(6+7)×(30−(6+5)) je décide d'écrire (14/(1+1))(6+7)(30−(6+5)), alors de même dans la version ponctuée, au lieu de 14/.1+1:×.6+7.×:30−.6+5 j'écris 14/.1+1:6+7:30−.6+5 et il n'y a pas d'ambiguïté dans le fait que quand un groupe de points apparaît directement entre deux atomes (nombres ou variables), il représente une multiplication (et comme 6.7 représente 6×7, de même 2+2+2.3+4 représente (2+2+2)×(3+4) ; tandis que 2+2+(2×3)+4 s'écrira 2+2+:2.3:+4 ou même, un peu audacieusement, 2.+.2.+.2.3.+.4 si on décide que la multiplication est prioritaire sur l'addition). Ceci fonctionne encore même si on suppose que la multiplication omise n'est pas associative : on distingue bien u(vw) de (uv)w comme u.vw et uv.w respectivement.

Par rapport aux règles formelles que j'ai proposées ci-dessus, l'omission du symbole de multiplication se traite ainsi lors de l'écriture : (a) on écrit toujours au moins un point pour la multiplication quand elle est entre deux chiffres, et (b) au lieu de mettre un groupe de points à gauche et à droite du symbole ⋆ (qui doit être omis), on en met un seul, avec un nombre de points commun, supérieur à celui de tout groupe intervenant dans n'importe quelle sous-expression parmi les x1,x2,…,xk (avec cette règle, 2(x+y)(t⋆(u+v)) s'écrit 2:x+y:t⋆.u+v plutôt que 2.x+y:t⋆.u+v si on veut vraiment placer les trois facteurs 2, x+y et t⋆(u+v) au même niveau).

Il n'y a pas non plus de problème avec les opérations unaires, qu'elles soient écrites de façon préfixe ou postfixe. Il y a, cependant, un problème si on a une opération qui peut être aussi bien unaire que binaire et que le symbole de multiplication est omis : c'est le cas avec le signe moins si on veut pouvoir écrire (2/3)(−3) (qui vaudrait −2 par multiplication implicite) et le distinguer de (2/3)−3 (qui vaut −7/3), les deux étant a priori ponctués comme 2/3.−3 ; on peut résoudre ce problème de différentes façons, par exemple en imposant que pour les opérations binaires qui peuvent aussi être unaires, le nombre de points à gauche et à droite soit égal quand elles fonctionnent comme opérations binaires (donc (2/3)−3 se ponctuerait comme 2/3.−.3, qui se lit sans ambiguïté), et/ou que le signe de multiplication ne peut pas être omis devant une opération unaire (donc (2/3)(−3) devrait s'écrire 2/3.×.−3).

Il me semble par ailleurs qu'il n'y a pas de problème particulier avec une opération ternaire (par exemple si je décide que t?u!v signifie si t=0 alors v et sinon u — je change légèrement la notation du C parce que les deux points sont pris par le sujet de cette entrée — alors il n'y a pas de problème à écrire de façon ponctuée des expressions contenant cette expression imbriquée en elle-même de façon arbitraire). Ceci étant, je n'ai pas forcément pensé à toutes les bizarreries des notations mathématiques, peut-être qu'il y a des cas où le système de points ne fonctionnera pas alors que les parenthèses fonctionnent (outre ceux que j'ai déjà mentionnés).

Il faut que j'en profite pour signaler qu'il y a toutes sortes de petites variations possibles dans le système, j'en ai déjà implicitement signalé quelques unes. Je mentionne notamment la suivante, qui est plus économique dans le nombre de points utilisés, au détriment de la lisibilité de l'ensemble, et qui me semble plutôt une mauvaise idée. Plus haut j'ai signalé que 6−(5−(4−(3−(2−1)))) s'écrit 6−::5−:.4−:3−.2−1 (et c'est ce qui résulte des règles formelles que j'ai proposées), mais on peut aussi imaginer l'écrire simplement come 6−.5−.4−.3−.2−1 ce qui est après tout inambigu vu que chaque ‘.’ suivant immédiatement un symbole d'opération doit représenter une parenthèse ouvrante. (La modification des règles formelles que j'ai proposées doit être quelque chose comme ceci. En écriture, on place à gauche de chaque symbole ⋆ un groupe de points dont le nombre est immédiatement strictement supérieur au plus grand nombre de points de n'importe quel groupe qui apparaît, dans l'écriture de la sous-expression gauche, immédiatement à droite d'un symbole d'opération — ou comme symbole de multiplication omis — en ignorant donc les groupes de points qui apparaissent immédiatement à gauche d'un symbole d'opération ; et symétriquement pour la droite. Et en lecture, pour chaque niveau n de points, on doit grosso modo répéter tant que possible la recherche d'une expression x1x2⋆…⋆xk avec les xi des sous-arbres déjà constitués, la remplacer par un sous-arbre, et retirer les éventuels groupes de n points — mais pas plus — qui seraient adjacents à l'expression.)

Comme je l'ai dit plus haut, je crois que les points comme parenthèses n'ont été véritablement employés que dans des textes de logique (et uniquement entre les connecteurs logiques, pas dans les expressions arithmétiques comme sur les exemples que j'ai pris), même s'il n'y a pas de raison de la lier à ce contexte précis. Je ne sais pas exactement qui a inventé cette notation : peut-être Peano dans ses Arithmetices principia: nova methodo ; mais je sais surtout qu'elle est utilisée dans les Principia Mathematica de Russell et Whitehead dont elle contribue à la réputation d'illisibilité même si je crois que c'est loin d'être ce qui les rend le plus difficile (on pourra jeter un coup d'œil à la page des Principia que j'ai déjà évoquée sur ce blog, et utiliser cette page pour quelques indications sur comment décoder tout ça). J'ai d'ailleurs l'impression que les philosophes qui s'intéressent à la logique mathématique ont, plus que les logiciens vraiment matheux, tendance à utiliser des notations vieillotes (il y a peut-être une raison sociologique à creuser), et en particulier ces points-comme-parenthèses. Il y a aussi l'épouvantable symbole ‘⊃’ utilisé à la place de ‘⇒’ pour l'implication, que la grande majorité des matheux ont abandonné il y a belle lurette, et que des philosophes s'obstinent, Apollon sait pourquoi, à utiliser.

Mais l'autre question à se poser, bien sûr, c'est : ce système de notation avec des points à la place des parenthèses a-t-il des avantages ? Je sais qu'a priori il semble plus compliqué que les parenthèses. Peut-être l'est-il intrinsèquement, mais je crois que c'est essentiellement une question d'habitude (c'est difficile d'être sûr vu que je n'en ai moi-même guère la pratique). Je vois trois principaux arguments qu'on peut avancer pour défendre le système de points : (1) il est légèrement plus compact (quand on discute une opération non associative, il est plus léger d'écrire uv.w que (uv)w, par exemple), (2) on repère plus rapidement le niveau d'imbrication des choses (qui n'a jamais peiné, dans une expression parenthésée, à retrouver où chaque parenthèse se ferme ?), et (3) il est, finalement, relativement analogue à la ponctuation d'un texte en langage naturel (où, grossièrement parlant, on regroupe d'abord les mots non séparés par une ponctuation, puis les groupes séparés par des virgules, puis ceux séparés par des points-virgules, et enfin ceux séparés par des points), rendu plus logique. Le principal inconvénient que je lui vois, c'est que si on veut remplacer, dans une expression, une valeur par une autre expression, on va possiblement devoir incrémenter le nombre de points partout dans l'expression, alors que les parenthèses assurent que tout se passe forcément bien.

Bien entendu, je ne propose pas de changer une notation mathématique bien établie (les parenthèses sont quand même pratiques, finalement), mais il peut être intéressant de se rappeler qu'il y a, ou qu'il y avait a priori, d'autres notations possibles et pas forcément idiotes. Se le rappeler peut aider à mieux comprendre l'analyse syntaxique, à la fois des expressions mathématiques et des phrases ponctuées en langage naturel (cf. mon point (3) ci-dessus) ; et cela peut aussi suggérer comment faciliter la lecture d'une expression mathématique par des enrichissements typographiques (typiquement : mettre à chaque endroit possible un espacement proportionnel au nombre de points qu'on aurait dans la notation avec les points comme parenthèses).

(jeudi)

De l'identification de souvenirs enfouis

C'est un trope abusé de mauvais films entre la science-fiction et l'espionnage qu'un personnage a vécu quelque chose d'Abominable ou d'Affreusement Secret dans sa jeunesse et que ses souvenirs ont été effacés ou refoulés ou quelque chose du genre. Ce cliché est particulièrement pénible sur le plan artistique (je déteste ces films où le héros va faire un rêve, présenté sous forme de flashs décousus, dont on doit comprendre qu'il apporte des bribes d'information sur quelque chose d'important sur son identité), et en plus il est essentiellement basé sur un mythe, à savoir, qu'on a tendance à supprimer inconsciemment les souvenirs particulièrement traumatiques. Le problème avec la mémoire incertaine est plutôt qu'on a tendance à fabriquer des faux souvenirs, ou à en déformer des vrais, et qu'on ne sait plus démêler le vrai du faux. J'ai déjà parlé de mon impression de voyager entre univers parallèles, mais elle est particulièrement marquée quand je retourne à des endroits où j'ai été par le passé et où je m'énerve de voir que les choses ne collent pas avec mon souvenir (est-ce que l'endroit a changé pendant ce temps ? me suis-je mal rappelé comment les choses étaient ? ou, hypothèse beaucoup plus crédible, suis-je passé dans un monde parallèle ?).

Par exemple, il y a quelques jours, comme mon poussinet et moi nous promenions dans le coin, j'ai voulu retracer un chemin que j'ai suivi plusieurs fois en 1996 : je passais les concours des ENS, dont les écrits avaient lieu au parc floral de Paris (dans le bois de Vincennes), ma maman m'avait trouvé un logement au Centre International de Séjour de Paris (avenue Maurice Ravel), et je faisais le matin un trajet pour aller de l'un à l'autre, passant en-dessous du périph', à travers un petit bout de Saint-Mandé et à côté du lac du même nom jusqu'au château de Vincennes ; mais quand j'ai cherché à retrouver le chemin exact que je suivais, toutes sortes de petites incohérences se sont manifestées entre mon souvenir des lieux et la réalité. (Il est vrai que je faisais ce chemin, il y a vingt ans, le matin à la fin du printemps, et que j'ai cherché à le retrouver le soir à la fin de l'automne : ceci peut beaucoup affecter l'apparence de cerains endroits.) • D'autres cas du même genre se sont présentés quand je suis allé voir mon Poussinet à Toronto en 2007 et que j'ai voulu retrouver toutes sortes d'endroits dont je me souvenais de mes passages précédents dans cette ville (souvenirs souvent mélangés entre eux, notamment pour ce qui est de leur ordre) : j'ai pu retrouver un bon nombre de choses, mais il y a des choses qui restent mystérieuses pour moi, notamment le chemin d'une promenade que je faisais régulièrement avec mon père en '84–'85 et dont je sais parfaitement bien où elle commençait mais que je n'ai réussi à retracer que jusqu'à un certain point après quoi mes souvenirs ne collaient vraiment plus avec la réalité.

En fait, ma tendance à revenir sur des lieux où j'ai marché autrefois et à chercher à replacer les endroits est tellement marquée que je fais régulièrement des rêves à ce sujet : des rêves dans lesquels je cherche à retrouver un endroit où j'ai pu aller ou une promenade que j'ai pu faire ; seulement, dans le rêve, tout est imaginaire : je ne rêve pas que je cherche à retrouver une promenade bien précise qui aurait pu exister en réalité, je rêve que j'ai un souvenir vague, et ce souvenir est lui-même imaginaire ! (Zut, j'en ai déjà parlé.)

Parfois, un peu comme le héros hypothétique du mauvais film que j'évoque ci-dessus, il me revient des flashs de souvenirs extrêmement précis sur lesquels je vais ensuite chercher désespérément à retrouver une date, un lieu, une circonstance. Récemment, alors que je parcourais des articles Wikipédia sur les expositions universelles (j'ai déjà dit qu'elles pouvaient me fasciner, et mon poussinet m'a offert un beau livre sur celle de Paris en 1900), j'ai été frappé par le souvenir incroyablement précis d'avoir été à celle de 1986 à Vancouver (Expo 86), et même d'avoir échangé quelques mots avec le robot mascotte de l'exposition, Ernie, et d'être revenu avec un paquet de cartes à jouer miniatures en souvenir, dont le dos représentait un des logos de l'exposition (Ernie en jetpack). Un souvenir aussi extrêmement précis peut-il être faux ? Il n'est pas invraisemblable, mon grand-père paternel habitait Vancouver et nous aurions pu aller lui rendre visite cette année-là, mais ma mère m'assure que, d'après les carnets qu'elle tient, ce n'est pas le cas. Peut-être suis-je aller à Vancouver plus tard et qu'il restait des choses de l'exposition, mais il me semble qu'à part de grandes structures on démonte rapidement les expositions universelles, et en tout cas on ne garde pas leur mascotte et on ne continue pas à faire des jeux de cartes à leur effigie, donc je ne sais pas trop quoi penser. Il faudrait retrouver ce jeu de cartes pour savoir si je ne délire pas, mais les chances sont assez minces avec tout ce qui a été jeté.

C'est entre autres pour m'éviter de m'arracher ainsi les cheveux que je tiens maintenant (et depuis 2001) un journal factuel assez précis de tout ce que je fais, jour par jour : ce n'est pas toujours évident de rechercher quelque chose dedans si je ne sais plus la date, mais au moins y a-t-il un espoir.

J'avais un souvenir précis qui me hantait depuis longtemps, et qui était à l'origine, je pense, ou en tout cas qui a pu nourrir, mes rêves de labyrinthes : je me revois avec mes parents en train de visiter une maison bizarre, gigantesque et dont la plupart des pièces sont dénuées de fenêtres, éclairée surtout en rouge, et qui est une sorte de musée d'objets hétéroclites et insensés, dont peut-être des poupées — je me rappelle une visite qui me semblait interminable, où le guide nous faisait traverser pièce après pièce, selon un chemin qui tournait dans tous les sens, et je commençais à me demander s'il y avait une sortie, et si cette maison avait une fin.

J'ai posé la question à mes parents : ma mère se souvenait vaguement de quelque chose de semblable, et associait ça à une visite que nous aurions faite à une tante de mon père qui habitait du côté de Madison, Wisconsin (son mari était avocat — argh, j'ai un avocat américain dans ma famille), et nous aurions pu aller voir un musée dans le coin. J'ai parcouru beaucoup de descriptions de musées à Madison ou dans les environs sans réussir à trouver quoi que ce soit qui colle, et comme je ne savais pas quoi googler vu que mes souvenirs étaient très vagues, je n'ai jamais réussi à mettre le doigt dessus.

Et tout d'un coup, tout à l'heure, j'ai eu la clé de l'énigme en regardant une vidéo YouTube d'un canal consacré à des endroits bizarres sur la Terre et aux surprises de la géographie : je suis quasiment certain que la maison labyrinthique de mon souvenir est la House on the Rock, une expérimentation artistico-architecturale à la décoration kitsch et tordue, située à une centaine de kilomètres de Madison, et dont les images renvoyées par Google collent parfaitement avec celles dans ma mémoire, notamment les poupées un peu effrayantes, les instruments musicaux bizarres et les nombreuses pièces sans fenêtres organisées selon un plan labyrinthique. Quelle satisfaction d'avoir enfin réussi à replacer un souvenir tellement flou !

(mardi)

Deux remarques sur l'intuition du théorème de Gödel

C'est un théorème bien connu, et que j'ai expliqué il y a quelques années dans cette longue entrée, que ZFC (:= le système d'axiomes standard de la théorie des ensembles), s'il est consistant, ne peut pas démontrer que ZFC est consistant. C'est là le « second » théorème d'incomplétude de Gödel dans le cas particulier de ZFC. De même, PA (:= l'arithmétique de Peano du premier ordre) ne peut pas démontrer que PA est consistant. (Dans les deux cas, l'affirmation que le système est consistant signifie qu'il n'existe pas de suite finie de symboles partant des axiomes et suivant les règles de la logique pour arriver à la conclusion absurde 0=1 : et on a le droit de parler de suites finies de symboles parce qu'elles peuvent se remplacer par des entiers grâce à ce qu'on appelle le codage de Gödel. Je ne rentre pas dans les détails puisque j'ai déjà expliqué ça et qu'il y a déjà quantité de bonne vulgarisation sur le sujet.)

Du coup, on peut être tenté d'ajouter à ZFC un nouvel axiome Consis(ZFC), qui affirme ZFC est consistant, formant un nouveau système ZFC₁ ; puis, comme le théorème de Gödel s'applique aussi à lui, on peut encore ajouter un nouvel axiome Consis(ZFC₁) qui affirme que celui-là est consistant, formant un nouveau système ZFC₂ ; « et ainsi de suite ». (En réalité, il y a beaucoup de subtilités ici dans le ainsi de suite, et de toute façon ce n'est pas une bonne façon d'enrichir ZFC, ces axiomes étant à la fois beaucoup moins forts, moins maniables et moins intéressants, que les axiomes de grands cardinaux par lesquels on l'étend usuellement. S'agissant de PA, on peut aussi faire cette construction, en gardant à l'esprit que PA, PA₁, PA₂, etc., et leurs consistance, sont de toute façon des conséquences (théorèmes) de ZFC.)

Ce point est bien connu, donc, et peut-être même trop connu, à tel point qu'on fait dire à ce théorème de Gödel un peu n'importe quoi. Les deux faits suivants, en revanche, sont bien moins connus, et mériteraient pourtant de l'être autant, parce qu'ils invitent à reconsidérer la manière dont on interprète (au moins sur le plan intuitif ou philosophique) ce théorème d'incomplétude. J'ai mentionné ces faits en passant lors de l'entrée passée vers laquelle je viens de faire un lien, mais je pense que je n'ai pas assez attiré l'attention dessus, ce qui est dommage.

(Les deux points suivants sont indépendants l'un de l'autre.)

✱ Le premier fait, c'est qu'on peut tout à fait fabriquer une théorie ZFC† dont les axiomes sont ceux de ZFC plus un axiome supplémentaire qui dit ZFC† est consistant. Oui, c'est circulaire (la théorie affirme sa propre consistance), mais ce n'est pas très difficile d'arriver à formaliser ça en utilisant les astuces de points fixes habituelles. Et de même, on peut former PA† dont les axiomes sont ceux de PA (Peano) plus un axiome supplémentaire qui dit que PA† est consistant. Il s'agit d'une façon assez naturelle d'essayer de contourner le théorème d'incomplétude (au moins quand on a mal compris celui-ci), en se disant puisque je ne peux pas démontrer que mon système formel est consistant, je vais l'ajouter comme axiome (et affirmer directement que l'ensemble est consistant plutôt qu'ajouter un axiome qui dit que la théorie de départ est consistante, puis un autre qui dit que cette nouvelle théorie est encore consistante, et encore un autre qui dit que celle-ci est consistante « et ainsi de suite »).

Bref, on peut fabriquer cette théorie ZFC† ou PA†, mais le problème c'est elle est inconsistante (elle démontre 0=1). Parce que le théorème de Gödel s'applique à elle aussi, et comme il affirme que si la théorie est consistante elle ne peut pas démontrer sa consistance, et qu'elle démontre effectivement sa consistance (puisque c'est un axiome, et qu'un axiome compte bien comme une démonstration), du coup, elle n'est pas consistante.

Alors voilà, ce n'est pas bien passionnant, certes : j'ai construit une théorie et j'ai expliqué qu'elle ne marchait pas — mais je pense que c'est quand même instructif, au moins sur le plan de l'intuition. Quand on présente le théorème d'incomplétude de Gödel, que ce soit au grand public, à des mathématiciens non-spécialistes, ou à des débutants en logique, l'idée qui en résulte typiquement — et je ne prétends pas qu'elle soit fausse — est qu'un système formel consistant T (récursivement axiomatisable, et contenant un fragment suffisant de l'arithmétique) n'est jamais assez « puissant » pour démontrer sa propre consistance, mais que (a) il s'agit d'une notion un peu constructive de démonstration, et (b) la raison pour laquelle on est conduit à ajouter des axiomes qui disent T est consistant et cette théorie-là est consistance et cette théorie- est consistante, « et ainsi de suite », est qu'on ne peut jamais tout faire d'un coup. Or l'exemple de la construction que je viens de donner montre qu'il faut se méfier de cette intuition : (b) on peut tout à fait écrire une théorie qui affirme sa propre consistance, et (a) cette théorie est forcément inconsistante parce que le théorème de Gödel interdit à une théorie consistante (récursivement axiomatisable, et contenant un fragment suffisant de l'arithmétique) non seulement démontre sa propre consistance, mais même simplement qu'il l'affirme (un axiome compte bien comme une démonstration). Je vais citer la présentation de Torkel Franzén (Inexhaustibility, 2004, chap. 12) parce que je trouve qu'il est particulièrement clair :

It is often emphasized that the resources of a theory T do not themselves suffice to enable a proof of the consistency of T. Again it is only by “going outside the system” than one can prove that T is consistent.

A weakness of this emphasis is that it doesn't take into account that the relevant concept of proof is a very liberal one. The consistency of T is provable in the theory T+Consis(T). This is not because any new fundamental principle has been introduced or because the theory T+Consis(T) incorporates any new insight that goes beyond those expressed in T, but simply because the consistency of T has been postulated. We don't require any more of a proof, as the term is used in logic. Accordingly, the second incompleteness theorem makes a stronger statement than one might naturally suppose. The consistency of T not only cannot be derived from the basic principles embodied in T, it cannot even be consistently asserted in T. A theory cannot consistently postulate its own consistency. By the diagonal lemma, we can produce a formula φ formalizing This sentence is consistent with T, but since T+φ then proves its own consistency, we know that in fact it is inconsistent.

Why is it impossible for T to consistently postulate Consis(T)? Because a paradox results from such a postulate, or so Gödel's proof of the second theorem suggests. If T asserts its own consistency, it must both assert and deny the provability of the sentence formalizing This sentence is not provable in T. It's not just a matter of T lacking the resources to establish a particular truth (that T is consistent) but of it being impossible to consistently sneak in this truth as an assertion or postulate in the theory itself. Saying that one must go outside the system to prove the consistency of T conveys the suggestion that T metaphorically speaking has a kind of “blind spot”, that it cannot reflect on or understand or inspect itself sufficiently to establish its own consistency—and indeed in extrapolations from the incompleteness theorem to other fields (religion, physics, psychology) this suggestion is frequently made explicit. The fact that T cannot even consistently assert its own consistency, without attempting any inspection or justification whatever, would seem to indicate that this suggestion is a bit of a red herring.

Je trouve que cela illustre très bien la manière dont on a tendance à mal se représenter le théorème d'incomplétude comme traduisant un problème profond de « manque de force » — alors qu'il s'agit de quelque chose d'à la fois plus trivial et plus profond. (Bien sûr, tout ceci est juste une question d'interprétation intuitive : il n'y a aucune difficulté ou subtilité mathématique dans tout ce que j'ai écrit.)

Mais si ce point est un peu trivial et en quelque sorte négatif, le suivant est beaucoup plus intéressant mathématiquement, et il est plutôt positif. Par ailleurs, il concerne spécifiquement ZFC et PA (pas que ce soient les seules théories auxquelles il s'applique, mais il ne s'applique pas à « à peu près n'importe quoi » comme le point que je viens de faire).

✱ J'en viens donc au second fait que je voulais signaler. Il faut d'abord que je rappelle que ZFC et PA ont un nombre infini d'axiomes : ils comportent en effet des schémas d'axiomes (le principe de récurrence dans le cas de PA, et pour ce qui est de ZFC, les schémas de séparation (=compréhension, =sélection) et ceux de remplacement). Ces axiomes veulent affirmer certains faits pour toute propriété P (des entiers naturels dans le cas de PA, ou des ensembles dans le cas de ZFC) : comme la logique du premier ordre ne permet pas de quantifier sur les propriétés, on s'en tire en postulant tous les énoncés dans lesquels P est remplacé par n'importe quelle formule explicitement écrite dans le langage où on se place — ce qui fait donc une infinité d'axiomes.

(Digression : Il y a d'autres façons de faire, consistant plus ou moins à faire de la logique du second ordre, et qui permettent de ramener cette infinité d'axiomes à un nombre fini au prix d'une complication de la logique, et parfois un renforcement du système : ce sont par exemple la théorie des ensembles de Gödel-Bernays, essentiellement aussi forte que ZFC, ou celle, strictement plus forte, de Morse-Kelley, les deux permettant de parler de classes, ce qui revient à permettre de quantifier sur les propriétés, et, s'agissant de l'arithmétique, le système ACA qui est exactement parallèle de Gödel-Bernays et l'arithmétique du second ordre Z₂=PA² qui est exactement parallèle de Morse-Kelley. Mais je vais m'abstenir de plus parler de toutes ces théories, d'autant que ça devient vite technique quand il s'agit de distinguer la vraie logique du second ordre de la logique du second ordre « réifiée » au premier ordre au sens où on a une logique du premier ordre à deux types d'objets qui fait semblant d'être une logique du second ordre en décrétant que l'un de ces types est le type des « classes » ou « propriétés » de l'autre type, ce qui revient finalement au même sauf que la notion de modèle et toute la sémantique qui va avec est différente.)

Un point qui me semble très important, et qui est rarement suffisamment souligné dans les cours élémentaires de logique, est le suivant :

Chacun de ZFC et de PA prouve la consistance de tous ses sous-ensembles finis d'axiomes.

Autrement dit, ZFC ne prouve pas la consistance de ZFC (c'est ce par quoi j'ai commencé : le second théorème d'incomplétude), mais ZFC prouve la consistance de n'importe quel ensemble fini d'axiomes de ZFC. Et la même chose vaut pour PA. On dit que ce sont des théories réflexives. En fait, il y a mieux : n'importe quelle extension de l'une ou l'autre de ces théories, écrite dans le même langage, est elle-même réflexive (on dit que ZFC et PA sont essentiellement réflexives : dans le cas de PA, c'est un théorème de 1952 dû à Andrzej Mostowski, et dans le cas de ZFC, je crois que le résultat est dû à Richard Montague et/ou Azriel Lévy vers 1960).

Une des conséquences de ce théorème est que ni ZFC ni PA, s'ils sont consistants, ne peut pas être axiomatisé par un nombre fini d'axiomes (si un ensemble fini T₀ de théorèmes de ZFC, ou du coup, d'axiomes de ZFC, suffisait à impliquer tous les axiomes de ZFC, alors ZFC prouverait la consistance de T₀, donc T₀ prouverait la consistance de T₀, et en prenant T₀ assez fort pour faire de l'arithmétique basique — je ne rentre pas dans les détails — ceci contredit le théorème de Gödel appliqué à la théorie T₀ ; et exactement le même raisonnement vaut pour PA). Mieux : comme ZFC et PA sont essentiellement réflexifs, aucune théorie consistante contenant ZFC ou PA et écrite dans le même langage ne peut être axiomatisée par un nombre fini d'axiomes. Mais ce n'est pas vraiment de ça que je veux parler.

Le résultat ci-dessus doit surprendre, parce qu'il paraît contredire le théorème de Gödel. L'argument serait le suivant : s'il y avait une contradiction dans ZFC, la démonstration de cette contradiction n'utiliserait qu'un nombre fini d'axiomes de ZFC (si on veut, c'est le théorème de compacité syntaxique, mais c'est une trivialité : une démonstration, étant de longueur finie, ne peut faire appel qu'à un nombre fini d'axiomes !) ; mais d'après ce que j'ai dit, ZFC prouve que ceci ne peut pas se produire (tout ensemble fini d'axiomes de ZFC est consistant) — du coup, ZFC est consistant, et on semble avoir prouvé ce fait dans ZFC ! Quelle est l'arnaque ?

L'arnaque est que le théorème de réflexivité ci-dessus est un métathéorème ; plus exactement, donné un ensemble T₀ quelconque d'axiomes de ZFC, on a une recette tout à fait explicite qui fabrique une démonstration à partir des axiomes de ZFC dont la conclusion est T₀ est consistant, et c'est un théorème (de ZFC, PA ou de systèmes encore plus faibles) que cette recette marche, i.e., l'énoncé encadré ci-dessus est bien un théorème. Mais, s'il est vrai que pour tout T₀ fini ⊆ZFC, T₀ est consistant est un théorème de ZFC, et que ceci est aussi un théorème de ZFC ou PA (i.e., pour tout T₀ fini ⊆ZFC, T₀ est consistant est un théorème de ZFC), en revanche, l'affirmation pour tout T₀ fini ⊆ZFC, T₀ est consistant, elle, n'est pas un théorème de ZFC (si ce dernier est consistant), car elle implique la consistance de ZFC d'après le raisonnement que j'ai fait au paragraphe ci-dessus.

Je répète : pour tout ensemble fini T₀ d'axiomes de ZFC, on sait fabriquer une démonstration dans ZFC que cet ensemble T₀ est consistant, et on sait montrer dans ZFC (ou PA ou moins) que ce procédé marche bien, mais on ne peut pas en conclure dans ZFC que tout ensemble fini T₀ d'axiomes de ZFC est consistant. On peut résumer cette situation ainsi : il est vrai que pour tout ensemble fini T₀ d'axiomes de ZFC, ZFC démontre la consistance de T₀, mais il ne le fait pas uniformément en T₀. C'est un cas du phénomène appelé la ω-incomplétude : pour tout n on démontre P(n) selon une recette générale et explicite, mais on ne peut pas démontrer ∀n.P(n) (ici, s'imaginer que n est un codage de T₀ et P(n) est l'affirmation que ce T₀ est consistant).

Absolument tout ceci vaut en remplaçant ZFC par PA partout (i.e., pour tout sous-système fini T₀ de PA, PA démontre que T₀ est consistant, mais ne le fait pas de façon uniforme). Ce fait est, d'ailleurs, étonnamment difficile à trouver écrit dans des bouquins de logique arithmétique.

Pour autant, pour tout usage philosophique ou épistémologique, je suis tenté de dire que ce qui précède (je veux dire, le résultat encadré ci-dessus) est exactement aussi bien qu'une démonstration de la consistance de ZFC dans ZFC, resp. de PA dans PA. Je ne sais pas au juste ce qu'on espérerait accomplir à avoir une démonstration de la consistance de ZFC dans ZFC ou de celle de PA dans PA (le projet de Hilbert était plutôt d'avoir une démonstration de la consistance d'un système fort dans un système faible, donc disons quelque chose comme celle de ZFC dans PA, or ça c'est vraiment hors de question). Mais je suppose que l'idée serait quelque chose comme je suis prêt à admettre comme mathématiquement vrais et certains les résultats — au moins arithmétiques — dont j'ai une démonstration dans ZFC, et je me sentirais plus rassuré si j'étais certain qu'il n'y a pas de démonstration de résultats absurdes dans ZFC, ce qui n'est pas si idiot que ça même si c'est circulaire (admettre que ZFC est vrai — ne serait-ce qu'arithmétiquement — est beaucoup plus fort qu'admettre qu'il est consistant, donc à partir du moment où on l'admet comme vrai, l'étape épistémologique à l'admettre comme consistant devrait être gratuite). Le principe de réflexion que j'ai encadré ci-dessus rend la réticence à admettre que ZFC est consistant encore plus bizarre dans ce contexte : si je suis prêt à admettre la consistance de tous ses sous-systèmes finis, je devrais bien admettre la consistance de la théorie tout entière ; plus exactement, si on me fournit un modèle simple permettant de construire, pour tout ensemble fini T₀ d'axiomes de ZFC, une preuve du fait que T₀ est consistant (et en outre, une méta-preuve du fait, d'ailleurs plus ou moins évident, que ce procédé fonctionne bien), il serait extrêmement bizarre de ne pas en admettre la conclusion, à savoir que tout ensemble fini T₀ d'axiomes de ZFC est consistant.

(dimanche)

Une méta-critique des épisodes I-II-III de Star Wars (PAS le nouveau)

Je n'ai pas encore vu l'épisode-que-tout-le-monde-attendait, donc je ne vais pas en parler (et je ne risque pas de spoiler), mais je voudrais profiter de sa sortie pour livrer de nouveau des réflexions décousues à 20 millizorkmids sur la place de l'œuvre de fiction dans l'imaginaire comme je l'avais fait au sujet de Tolkien.

La « trilogie originale » (pour ceux qui vivent vraiment dans une galaxie lointaine, très lointaine, il s'agit des épisodes numérotés IV (A New Hope), V (The Empire Strikes Back) et VI (Return of the Jedi), et qui sont les premiers à être sortis, respectivement en 1977, 1980 et 1983), fait, pour beaucoup de ma génération, partie des référents culturels avec lesquels nous avons grandi, et évoque surtout un sentiment de nostalgie de l'époque : il devient essentiellement impossible de les juger pour leur mérite propre ou même simplement de les regarder d'un œil neuf. Je ne peux pas penser à Star Wars sans penser à toutes sortes de scènes ou de réflexions de mon enfance qui y sont inextricablement liées dans mon esprit : la terreur quand j'ai vu le VI à sa sortie (j'avais six ans) que m'inspirait le personnage de l'Empereur, la confusion dans laquelle j'étais quant au nombre de films constituant la série (il faut dire que la numérotation n'aide pas, et je pensais qu'il y avait au moins six films à voir), ma fascination pour la musique et les efforts que j'ai faits pour la retrouver de mémoire à la flûte à bec, l'excitation quand j'ai enfin pu me faire acheter les VHS en coffret, etc. Je ne peux pas dire que j'aie été un « fan » de Star Wars (je n'ai jamais collectionné les figurines, lu des livres de l'« univers étendu », joué aux jeux de rôles basés dessus ni été capable de dire la longueur d'un star destroyer), mais j'ai certainement vu chacun de ces films au moins douze fois. (En français avant de les revoir en anglais : alors que maintenant je refuse catégoriquement de voir un film doublé, pour ceux-ci spécifiquement, la VF a une certaine valeur nostalgique à mes oreilles. Ceci dit, je ne crois pas que j'aie entendu la version où Luc s'appelait encore Courleciel.)

J'ai eu une sorte d'épiphanie quand, beaucoup plus tard, j'ai vu le film Battlestar Galactica (je parle du film de 1978, pas de la série TV de l'époque et dont il est plus ou moins le pilote, encore moins de la série TV beaucoup plus récente). Ce film est à peu près contemporain du premier Star Wars, je ne sais pas s'il en est fortement inspiré ou si c'est juste le genre de l'époque, mais les costumes sont dans le même style, la musique est dans le même genre, les deux principaux héros ont plein de ressemblances avec Luke Skywalker et Han Solo, et les effets spéciaux sont autant réalisés avec des bouts de ficelle. Et ce film est vraiment mauvais (suffisamment mauvais pour devenir bon au second degré, i.e., un nanar) : c'est comme ça que je me suis rendu compte que Star Wars, au moins son épisode IV (le premier, donc), était franchement nanaresque, mais que son impact culturel forçait à le ranger dans une autre catégorie que Battlestar Galactica.

Je trouve intéressante la danse qui peut se mettre en place entre une œuvre de fiction et notre imagination : avant même que nous ne voyions ou lisions l'œuvre (je l'ai raconté à propos de Tolkien), mais surtout après, quand nous l'incorporons à notre monde des rêves et de la fantaisie. Quand j'étais ado, j'ai écrit un roman(?), Castor et Pollux, dont la trame était inspirée, voire complètement décalquée, de celle de Star Wars (mélangée à un gloubi-boulga métaphysico-ésotérique que je savais pondre au kilomètre à cet âge-là — sans doute faut-il comprendre que l'histoire de Castor et Pollux est une métaphore tarabiscotée pour la manière dont l'œuvre de fiction peut capturer son propre créateur, auquel cas cette métaphore pourrait avoir une certaine pertinence dans le cas de George Lucas) ; d'ailleurs, l'inspiration n'était pas un secret, les chapitres portent les noms des films de Star Wars traduits en latin (! on va dire que je suis parfois un peu autocaricatural). Toutes sortes de fans avaient certainement développé leur propre imaginaire concernant le passé et le futur de l'Univers de Star Wars.

Peut-être, d'ailleurs, tout cet Univers est-il assez malsain. Énormément d'œuvres de fantastique sont manichéennes dans leur construction, mais le mysticisme de Star Wars atteint un niveau de manichéisme vaguement inquiétant — un niveau où le Bien et le Mal ne sont plus le Bien et le Mal pour des raisons précises mais simplement parce qu'ils sont essentiellement le Bien et le Mal, si bien qu'il n'y a plus à s'interroger sur leurs actions ou leurs motivations, et ceci est la base de bien des formes de fanatisme. (Et on peut lire toute l'histoire des épisodes IV-V-VI comme celle de la radicalisation de Luke Skywalker.) Mais ce mysticisme a pour contrepoint des personnages qui ne sont pas tout blancs ou tout noirs (Han dans l'épisode IV, Lando dans l'épisode V, Vader dans l'épisode VI) et le thème de la rédemption est finalement plus fort que le manichéisme. Au final, la culture pop s'est approprié la trilogie avec peut-être plus d'humour et de légereté qu'elle n'en contient elle-même. Je ne vais laisser ici qu'un exemple, mais je pense que c'est un véritable bijou : le court-métrage George Lucas in Love (visible ici sur YouTube), à mon avis la meilleure fan-fiction sur Star Wars, justement parce qu'il n'est pas de la science-fiction (ni, a fortiori, situé dans l'univers de Star Wars).

Et puis George Lucas est arrivé avec ses épisodes I-II-III (en 1999, 2002 et 2005), et il a tout gâché.

Il y a toujours une certaine violence émotionnelle ressentie quand on s'attache à une œuvre de fiction, qu'on en imagine des extensions, et que l'auteur vient, avec son autorité ex cathedra vous raconter quelque chose de différent — vient casser la construction qu'on s'est faite en rêve pour la remplacer par la sienne, « canonique ». (De nouveau, j'ai parlé de mon expérience personnelle avec Tolkien, mais pour donner un autre exemple, cette année, 55 ans après la publication du roman d'origine, est sortie la suite du classique To Kill a Mockingbird : les réactions ont été assez partagées, pas seulement à cause des circonstances un peu bizarres de cette parution, mais aussi parce que cette suite forçait à réévaluer un personnage qu'on avait peut-être jugé trop favorablement.)

Mais dans le cas de la « prélogie » de Star Wars, à cette violence émotionnelle s'ajoute le choc de découvrir à quel point elle est mauvaise de tout point de vue. Mais le problème n'est pas seulement qu'elle est incohérente, mal écrite, mal mise en scène, mal jouée et mal montée (comme le démontrent par le détail les critiques vers lequel je vais faire des liens ci-dessous) : le problème est surtout qu'elle dissone profondément avec la trilogie des épisodes IV-V-VI, pas seulement sur tel ou tel point de l'intrigue mais, ce qui est beaucoup plus grave, sur le ton général de l'œuvre et de l'univers où elle doit se dérouler. Les fans ont été particulièrement heurtés, par exemple, d'apprendre que la « Force », ce machin mystique central à la saga, était en fait créé par des créatures microscopiques appelées midi-chloriens(?), révélation qui semblait casser toute la poésie de la chose — et révélation d'autant plus agaçante qu'elle n'avait absolument aucune sorte d'intérêt pour l'intrigue du film où elle s'inscrivait. Mais ce n'est que la partie émergée de l'iceberg : énormément de choses, dans ces nouveaux films, vient détruire la poésie des anciens en changeant le regard qu'on porte sur ses personnages, parce que le ton général est tellement différent. (Je donne juste l'exemple de Yoda : il était beaucoup plus intéressant de l'imaginer comme ayant toujours vécu sur sa planète marécageuse et pas à la tête d'un conseil dirigeant des jedis — en fait, le ton des films IV-V-VI suggérait plutôt que les jedis n'avaient pas d'organisation centrale ou de conseil dirigeant ; et il était beaucoup plus intéressant d'imaginer que jamais Yoda n'aurait eu besoin d'utiliser une arme, parce que sa puissance est d'une tout autre nature. Tout ceci me semble plus significatif que l'incohérence qu'on peut soulever dans le fait que dans les épisodes V et VI il est clair que Vader n'a aucune idée de l'existence de Yoda alors que dans les I à III les personnages se croisent à de nombreuses reprises.)

Bien sûr, quantité d'autres œuvres de l'histoire du cinéma ont été « gâchées » par une suite ou un prequel merdiques. Généralement, cependant, cela vient plutôt du studio, qui veut exploiter la franchise, que du réalisateur supposément visionnaire. Il est bizarre qu'ici ce soit George Lucas qui ait saboté sa propre œuvre. (En prétendant, d'ailleurs, avoir suivi ce qui était sa vision dès l'origine : je dois dire que je ne le crois pas du tout. Je ne le crois même pas quand il prétend qu'il avait décidé ce qui se passerait dans l'épisode V lorsqu'il tournait le IV ou le VI quand il tournait le V — si c'était le cas, je pense qu'il n'aurait pas laissé quelques scènes qui prennent rétrospectivement un parfum suspect d'inceste.)

Mais mon propos n'est pas de me plaindre que les épisodes I-II-III de Star Wars sont mauvais : ça ne sert à rien de tirer sur les ambulances. Cela pourrait être plus intéressant d'essayer de comprendre pourquoi ce fiasco : comment se fait-il qu'un créateur disposant de moyens essentiellement illimités et sans aucune contrainte pour exprimer son imagination ni quiconque pour le contredire produise quelque chose d'aussi nul ? Une explication est que c'est justement la difficulté qui fait que l'art est intéressant ; une variante, plus terre-à-terre, est que personne n'osait signaler à George Lucas (comme il était le grand chef, à la fois réalisateur, superproducteur et clé de tout le financement), fût-ce diplomatiquement, que ses idées étaient nulles, si bien qu'il s'est retrouvé complètement déconnecté de la réalité ; ou peut-être qu'il était tellement obnubilé par les possibilités offertes par les effets spéciaux et par tout ce qui apporterait de l'argent en produits dérivés qu'il ne voyait plus que ça. Ou peut-être enfin que les épisodes IV-V-VI ne sont finalement pas mieux que les I-II-III (ni que Battlestar Galactica) mais que nous les jugeons différemment parce que nous nous y sommes habitués et qu'ils sont devenus des références culturelles ? Je ne sais pas. Mais en tout cas, il peut être intéressant d'étudier un peu en détails ce qui n'allait pas bien : critiquer des mauvaises œuvres d'art peut être finalement plus instructif que louer les bonnes. (Et peut-être que dans les cours de litérature on devrait un peu faire la place, au milieu des Shakespeare, Goethe et Racine, pour des écrivains médiocres ou carrément mauvais, afin d'expliquer justement pourquoi ils ne sont pas Shakespeare, Goethe ou Racine. Ou pourquoi les écrivains mauvais ne sont même pas médiocres. Ou pourquoi certains sont encore plus que mauvais. Mais je digresse.)

Bref, je voudrais ici proposer des liens vers trois critiques des épisodes I-II-III de Star Wars qui me semblent vraiment intéressantes : après tout, si s'est farci les sept heures de ces films, autant chercher à comprendre ce qui n'allait pas avec, surtout que ça peut être très drôle d'énumérer les contradictions et les invraisemblances. En fait, ces critiques sont en elles-mêmes des œuvres très construites qui peuvent presque se regarder comme des films. (D'ailleurs, s'agissant de celle de Mr. Plinkett, il y a eu des critiques de la critique, même si je suis tenté de critiquer ces critiques de la critique en disant qu'elles n'étaient généralement pas terribles.)

Ajout () : Je dois encore faire un lien vers la théorie amusante proposée par le webcomic Wondermark : il faut imaginer que les épisodes I-II-III ne représentent pas forcément des événements qui se sont vraiment déroulés dans l'univers de Star Wars mais qu'ils sont une fiction de cet univers, ayant autant de rapport avec la réalité de l'ascension et de la chute de Vader que Pocahontas avec les événements historiques dans notre univers.

(jeudi)

Les adjectifs dans les langues germaniques

Puisque j'en ai parlé dans l'entrée précédente, je vais raconter des choses sur l'inflexion des adjectifs dans les langues germaniques. (Si vous lisez cet article jusqu'au bout, félicitations, vous aurez vous aussi gagné le super pouvoir de passer pour la personne la plus ennuyeuse dans n'importe quelle soirée.)

Les langues germaniques sont une sous-branche des langues indo-européennes. Je commence donc par rappeler certains éléments grammaticaux importants généralement communs à ces langues. Pour commencer, ce sont des langues à cas (au moins à l'origine — beaucoup d'entre elles ont perdu les cas ultérieurement), c'est-à-dire que les noms ou groupes nominaux portent des inflexions qui indiquent la fonction de ces groupes par rapport au verbe de la phrase. (Les cas à l'origine sont : nominatif, vocatif, accusatif, instrumental, datif, ablatif, génitif et locatif ; peu importe la liste exacte, mais je veux surtout souligner qu'ils sont en nombre relativement petit et bien défini, à la différence des langues comme le finnois ou le hongrois où cette liste n'a pas vraiment de fin.) Ces cas sont marqués presque uniquement à la fin du mot (on parle de désinences). De plus, du point de vue de ces cas, les langues indo-européennes font une distinction principale nominatif-accusatif plutôt qu'absolutif-ergatif : disons pour simplifier que cela signifie que dans une phrase comme Pierre frappe Paul, le nom qui effectue l'action désignée par le verbe frapper (Pierre, qui sera au cas appelé nominatif ou cas « sujet ») aura un rôle grammatical plus central que le nom qui la subit (Paul, qui sera au cas appelé accusatif) — cette centralité se voit dans le fait que s'il y a une seule personne connectée à l'action (Jacques tombe), le cas de cette personne sera le même que le cas de la personne qui effectue l'action (donc, le nominatif), que si le verbe s'accorde dans cette situation (Jacques tombeJacques et Jules tombent) alors il s'accorde de la même façon avec le « sujet » de l'action (Pierre et Luc frappent Paul contre Pierre frappe Paul et Marc sans variation), et que si la même personne effectue deux actions on peut faire une ellipse (la phrase Pierre frappe Paul et Pierre tombe peut se redire en Pierre frappe Paul et tombe, alors que Pierre frappe Paul et Paul tombe ne peut pas se redire avec ellipse) ; à l'inverse, dans une langue à opposition absolutif-ergatif, c'est le cas de Paul dans Pierre frappe Paul, appelé absolutif, qui est utilisé pour Jacques tombe et non celui de Pierre (l'ergatif), mais je digresse.

Une autre caractéristique grammaticale des langues indo-européennes est que les adjectifs sont plus ou moins rapprochés des noms : comme les noms, les adjectifs peuvent varier selon le cas, ils s'accordent aussi en nombre et en genre avec le nom (cf. ci-dessous), en revanche ils n'ont pas les dimensions d'inflexion qui caractérisent les verbes (mode, temps, aspect) ; par comparaison, en japonais, les adjectifs (au moins les adjectifs en -い) ressemblent plus à des verbes, et peuvent se mettre, par exemple, au passé. Ceci peut s'analyser en disant que dans les langues indo-européennes, la fonction « normale » de l'adjectif est épithète (la mer bleue) alors que dans d'autres langues la fonction « normale » serait d'être attribut (la mer est-bleue, l'adjectif signifiant être-bleu).

Enfin, les langues indo-européennes distinguent trois nombres, le singulier, le duel et le pluriel, même si le duel est réduit à l'état de trace ou d'archaïsme dans quasiment toutes les langues indo-européennes vivantes (désolé, le slovène !). Et elles distinguent trois genres, le masculin, le féminin, et le neutre, même si plusieurs ou tous ces genres ont pu fusionner dans beaucoup de langues encore vivantes, et même si à l'origine le statut du féminin n'est pas clair (il est probablement dérivé d'une forme de collectif, ce qui explique pourquoi le neutre pluriel et le féminin singulier ont une grande parenté).

J'en profite pour noter que quasiment tout ce que je viens de dire — l'existence de cas, l'opposition nominatif/accusatif, avec variation du verbe selon le sujet, plutôt qu'absolutif/ergatif, l'opposition nom/verbe avec rapprochement des adjectifs aux noms, l'existence d'une distinction de nombre et peut-être même singulier/duel/pluriel, et l'existence d'une distinction de genre avec une similitude entre le féminin singulier et l'inanimé pluriel (jusqu'à l'accord des verbes au singulier dans cette situation) — est aussi vrai pour les langues sémitiques comme l'arabe. Je trouve qu'il s'agit d'indices assez forts pour penser qu'il y a, sinon parenté, du moins influence grammaticale, entre ces deux familles de langues, et je trouve ça beaucoup plus remarquable que d'éventuels rapprochements entre racines lexicales douteuses. Mais de nouveau, je digresse complètement.

Le schéma général de l'adjectif dans les langues indo-européennes est, donc, est qu'il s'accorde en genre, nombre et cas avec le nom auquel il se rapporte. L'accord en nombre n'appelle pas spécialement à commentaire (je me retiens très fort de vous parler des numéraux dans les langues slaves). L'accord en cas n'en mérite pas non plus si l'adjectif est épithète (pour la mer bleue, le bleu sera au même cas que mer, que ce groupe soit sujet, objet, objet indirect, ou tout autre cas) : dans le cas de l'attribut (la mer est bleue), le cas est a priori nominatif, même s'il faut évoquer la possibilité d'un attribut du complément d'objet (la mer, je l'imagine bleue) auquel cas l'adjectif devrait logiquement être à l'accusatif, mais je n'ai pas assez de recul sur un ensemble raisonnable de langues indo-européennes à cas pour pouvoir dire si cette logique est largement suivie. (Par ailleurs, la règle de l'attribut du sujet au nominatif ne s'applique pas que pour un adjectif mais si l'attribut est lui-même un nom ou un groupe nominal : Socrate est un homme mettra normalement un homme au nominatif dans les langues indo-européennes. Cependant, cette logique ne vaut que pour la forme la plus basique, et parfois omise, du verbe être : en russe, par exemple, Socrate est un homme se dit Сократ — человек, mais Socrate était un homme donne Сократ был человеком, l'attribut passant du cas nominatif человек au cas instrumental человеком ; de nouveau, je trouve amusant qu'on voie un phénomène analogue en arabe classique où l'attribut marqué sans verbe commande le cas nominatif tandis que l'attribut marqué avec le verbe كان, par exemple pour exprimer le passé, commande le cas accusatif/direct. Zut, j'ai encore digressé.)

L'accord en genre mérite l'explication suivante que le genre dans les langues indo-européennes a plusieurs visages ou recouvre plusieurs phénomènes. (1) Il est une caractéristique lexicale intrinsèque des noms communs, c'est-à-dire que chaque nom commun (si la langue a gardé des genres) appartient à tel ou tel genre, et ce, de façon essentiellement arbitraire : en français, le soleil est lexicalement masculin, la lune est lexicalement féminin, tandis qu'en allemand, die Sonne (le soleil) est féminin et der Mond (la lune) est masculin. (2) Il est aussi un élément sémantique lorsqu'il se rapporte à une personne, indiquant à quel sexe il est considéré par le locuteur comme appartenir : c'est-à-dire que certains énoncés, nonobstant le (1) ci-dessus, apportent une information sur le sexe du locuteur ou de la personne à laquelle il s'adresse, ou de tiers désignés par des prénoms ou des noms épicènes. (Ainsi, en français, écrire tu es fou plutôt que tu es folle reflète l'information qu'on s'adresse à une personne considérée comme de sexe masculin. Il ne s'agit pas ici du genre lexical d'un nom commun.) (3) Dans le cas des adjectifs (ou apparentés : formes verbales à participes), le genre est un élément d'accord, reflétant le genre (au sens (1) ou (2)) du nom auquel l'adjectif se rapporte. (4) Le genre commande aussi à un choix de pronoms (en français, il contre elle, en anglais he contre she). • En clair, (1) un nom commun est masculin, féminin ou neutre (selon ce que la langue admet comme genres), mais toujours du même genre pour le même nom (à de rares exceptions près), tandis que (3) un adjectif est accordé au masculin, féminin ou neutre selon le nom auquel il se rapporte. Un nom a un genre intrinsèque, un adjectif n'en a pas. Et dans des cas comme celui où l'adjectif se rapport non pas à un nom mais à un pronom ou un nom propre (p.ex., prénom), l'accord est sémantique (c'est le point (2)). (Quant au choix (4) des pronoms pour reprendre un nom, il dépend (1) du genre lexical du nom et/ou (2) de la sémantique, typiquement quand il s'agit d'une personne.)

Au niveau inflexionnel, les langues indo-européennes ont donné aux adjectifs des désinences masculines, féminines et neutres calquées sur les paradigmes des noms les plus souvent du genre correspondant. Ainsi, en latin, le masculin bonus se décline comme dominus (classe de noms majoritairement masculins), le féminin bona comme rosa (classe de noms majoritairement féminins), et le neutre bonum comme templum (classe de noms exclusivement neutres) : les désinences de trois classes de noms différents se retrouvent dans une seule classe d'adjectifs pour former les trois genres. (Mais l'accord est véritablement selon le genre et pas selon la classe flexionnelle du mot : ainsi dans les rares situations de noms féminins du paradigme dominus ou de masculins du paradigme bona, on accorde bien l'adjectif avec le genre, par exemple Sequana longus est, la Seine est longue, le nom du fleuve Sequana étant masculin en latin malgré sa terminaison en -a et bien qu'il ait donné un féminin en français.)

⁂ Tout ceci concernait les langues indo-européennes en général. Les langues germaniques apportent l'innovation qu'en plus de faire varier les adjectifs en genre, nombre et cas, elles introduisent une dimension de plus à leur inflexion, la distinction indéterminé/déterminé. Cette distinction concerne uniquement les adjectifs (les langues scandinaves ont innové en introduisant une distinction similaire pour les noms, j'y reviendrai) ; et elle à l'origine a un caractère sémantique : elle distingue le beau garçon et un beau garçon (si j'arrive à pipoter correctement le vieil allemand, ça devrait être scōno knabo et scōni knabo respectivement), autrement dit, à l'origine, le choix d'accorder l'adjectif en indéterminé ou en déterminé va apporter une vraie différence de sens. Mais les langues germaniques ont ensuite repris des démonstratifs comme articles, rendant cette distinction redondante avec la présence de l'article défini : ceci transforme alors une distinction sémantique en un accord grammatical selon la présence ou non de tel ou tel article. (Exemple toujours en vieil allemand mais avec l'article explicitement écrit, dër scōno knabo, soit en allemand moderne der schöne Knabe, le beau garçon, contre scōni knabo, ein schöner Knabe, un beau garçon ; ou pour reprendre exactement les mêmes mots en vieil anglais, se scēna cnafa contre scēne cnafa, ce qui en anglais moderne-mais-précieux serait [the] sheen knave, mais les désinences ont alors totalement disparu.)

Zut, je voulais reprendre le vers du Roi des aulnes pour mon exemple, mais je me suis mal rappelé celui-ci : dans le poème de Goethe, c'est feiner Knabe (pour ma défense, schöner Knabe scanderait tout aussi bien). Comme fein ne semble pas venir d'une racine germanique, je ne change pas.

Cette distinction déterminé/indéterminé à l'adjectif est une spécificité des langues germaniques qui ne se retrouve pas dans les autres langues indo-européennes, même s'il y a quelque chose de vaguement semblable dans la famille balto-slavique (une sorte de déterminant postposé qui explique notamment pourquoi les adjectifs épithètes en russe ont une déclinaison manifestement double), mais je ne développe pas plus.

J'ai écrit ci-dessus que les langues indo-européennes avaient utilisé les désinences de diverses classes de noms (généralement masculins, généralement féminins, neutres) pour calquer les désinences des adjectifs au masculin, féminin et neutre : un phénomène analogue s'est produit pour fabriquer les désinences des adjectifs à la forme indéterminée et déterminée dans les langues germaniques. Plus exactement, il existe deux grandes déclinaisons de noms dans les langues germaniques, celle appelée forte et celle appelée faible (il en reste des traces en allemand moderne sous la forme des « masculins faibles » qui prennent une désinence -en à toutes les formes infléchies) : la déclinaison faible prend un -n- à quasiment toutes ses formes infléchies alors que la déclinaison forte a un modèle plus varié, avec notamment un -s au génitif singulier et un -(u)m au datif pluriel (je ne donne que des tendances : les détails dépendent évidemment de la langue, du genre et du mot précis). Par exemple, en vieil anglais, je vois l'homme, l'homme est grand se dit īc sēo þone mann, se mann biþ micel (mann est un masculin fort, qui reste identique à l'accusatif) tandis que je vois le garçon, le garçon est grand est īc sēo þone cnafan, se cnafa biþ micel (cnafa est un masculin faible, qui prend un -n à l'accusatif ; c'est encore le cas en allemand moderne — pour autant que Knabe soit considéré comme de l'allemand moderne : ich sehe den Knaben, der Knabe ist groß). Ce sont les noms forts qui ont donné les désinences indéterminées des adjectifs et les noms faibles (ceux avec -n) qui ont donné les désinences déterminées des adjectifs. Du coup, on parle souvent de désinences fortes et faibles des adjectifs pour ces deux cas (mais il n'y a pas d'accord de l'adjectif avec le nom en la matière : si je parle d'un beau garçon, le fait que le garçon est un masculin faible n'a aucune incidence sur le fait que l'adjectif prend la déclinaison forte parce qu'indéterminée).

Tout ceci donne un système assez complexe : même si le nombre de cas des langues germaniques s'est réduit de huit à quatre (nominatif, accusatif, datif et génitif — et parfois de vagues restes d'instrumental), et que le duel a de toute façon été perdu très tôt, il reste que quatre cas fois deux nombres fois trois genres fois deux niveaux de détermination fait encore 48 combinaisons à apprendre pour les adjectifs. Heureusement, toutes les langues modernes ont beaucoup simplifié ce système, l'islandais gardant encore le plus haut niveau de complexité avec une trentaine de combinaisons.

D'abord, certaines langues ont fusionné des genres : en anglais on sait bien que les genres ont totalement disparu, mais il est plus courant d'avoir fusionné le masculin et le féminin en un genre commun qui s'oppose au neutre. (On ne sait pas trop comment l'appeler, ce genre : commun serait bien sauf qu'un nom commun désigne déjà quelque chose, et peut donc prêter à confusion si je dis que la plupart des noms communs sont communs ; non-neutre est lourd parce que c'est une double négation, et qu'à l'oral non-neutre se confond avec nom neutre ce qui est gênant ; et utre est logique et cohérent puisque étymologiquement, neuter veut dire ni l'un ni l'autre en latin, de uter qui veut dire l'un ou l'autre, mais malheureusement ce terme est inhabituel et provoque souvent l'incompréhension.) Cette fusion du masculin et du féminin s'est produite en néerlandais et dans les langues scandinaves, en convenant que l'islandais n'est pas une langue scandinave ; mais comme d'habitude en linguistique, il y a des nuances. (Le féminin a disparu, en tant que caractéristique lexicale, du néerlandais parlé aux Pays-Bas, c'est un peu moins vrai pour le flamand de Belgique, où certains noms utres vont être repris par le pronom ze au lieu de hij, même si ceci n'a pas d'impact sur les adjectifs qui me concernent principalement ici. Et si le masculin et le féminin ont bien fusionné en tant que caractéristiques lexicales en danois et en suédois, en norvégien ils sont encore plus ou moins séparés selon les dialectes : disons grosso modo qu'il y a trois genres lexicaux en nynorsk tandis que pour ce qui est du bokmål les formes « masculines » et « féminines » sont en variation libre, mais de toute façon les formes du masculin et du féminin de l'adjectif y coïncident sauf pour l'adjectif irrégulier liten, signifiant petit, qui devient lita au féminin.) L'allemand et l'islandais modernes, pour leur part, gardent complètement les trois genres.

Notons que quand je parle de fusion des genres grammaticaux, je veux parler uniquement du genre en tant que caractéristique lexicale des noms (ce que j'appelais (1) ci-dessus) et en tant que reflet sur l'accord des adjectifs ((3) ci-dessus). Il subsiste en anglais, néerlandais, suédois, etc., un genre sémantique ((2) ci-dessus) qui se marque par le choix des pronoms ((4) ci-dessus) pour désigner les personnes, i.e., il ou elle. • En anglais, il y a donc trois genres sémantiques : le masculin (pronom de 3e personne du singulier he), le féminin (pronom she) et l'inanimé (pronom it), avec une hésitation sur ce qu'on doit faire des êtres animés qui ne sont pas des personnes. En allemand (comme dans beaucoup de langues indo-européennes à la base), il y a mélange entre le genre lexical et le genre sémantique, puisqu'on a un pronom de 3e personne du singulier er qui sert à reprendre une personne de sexe masculin ou un nom commun de genre lexical masculin, un pronom sie qui sert à reprendre une personne de sexe féminin ou un nom commun de genre lexical féminin, et enfin un pronom es qui sert à reprendre un nom commun de genre lexical neutre. (Notons qu'une personne peut tout à fait être désignée par un nom neutre en allemand, puisque tous les diminutifs sont neutres : mais on n'utilise es pour désigner une personne que quand un tel nom est explicitement présent — sauf évidemment par volonté stylistique particulière.) En néerlandais, le même mélange se produit, sauf que comme l'alternance lexicale masculin/féminin a disparu, c'est hij, le pronom « masculin » qui va servir à reprendre un nom lexicalement utre, tandis que ze se retrouve limité au genre sémantique (grosso modo aux Pays-Bas : je l'ai dit ci-dessus, en Belgique, ze peut servir à reprendre des noms de genre utre). • Les langues scandinaves, pour leur part, évitent le mélange entre genres lexicaux et genres sémantiques et ont donc un répertoire complet de pronoms : en suédois, le pronom de la troisième personne du singulier est han pour reprendre une personne de sexe masculin, hon pour reprendre une personne de sexe féminin, den pour reprendre un nom lexicalement utre désignant un être inanimé (ou en tout cas pas une personne), et det pour reprendre un nom lexicalement neutre ; auxquels quatre pronoms on peut en ajouter un cinquième de facture récente, hen, utilisé pour reprendre une personne sans référence à son sexe — ce qui est assez logique : on se retrouve donc avec cinq pronoms correspondant aux genres masculin, féminin, utre, neutre et épicène. (Soit dit en passant, le système scandinave fonctionne beaucoup mieux dans mon cerveau que le système de l'allemand, parce que quand je parle allemand mon cerveau a toujours envie de reprendre les objets inanimés par es, même quand je connais bien leur genre lexical, parce que ça me choque de dire er ou sie pour autre chose qu'une personne, sans doute à cause de l'influence de l'anglais.) • Mais tout ceci est une longue digression puisque, en ce qui concerne les adjectifs, il n'y a tout simplement pas de différence entre masculin et féminin en néerlandais ou dans les langues scandinaves (si on veut bien oublier l'adjectif liten en norvégien nynorsk). Que je sache, à part un point optionnel en suédois sur lequel je vais revenir, il n'y a qu'en islandais parmi les langues modernes que le genre sémantique (2) se reflète sur l'accord des adjectifs (3) (tu es fou, i.e., si on s'adresse à un homme, se dit en islandais þu ert brjálaður, tandis que tu es folle, i.e., si on s'adresse à une femme, donne þu ert brjálað), or de toute façon l'islandais a gardé les trois genres.

Voici quelques unes des autres évolutions, principalement simplificatrices, qui ont eu lieu. Toutes les langues vivantes que je viens de citer à l'exception de l'islandais fusionnent tous les genres au pluriel (je parle toujours des adjectifs !, je veux dire que dès lors qu'un nom est pluriel, son genre n'a plus d'importance pour l'accord de l'adjectif, je ne prétends pas que le genre n'a pas un impact sur la formation du pluriel du nom lui-même) ; ceci permet donc de traiter le pluriel comme si c'était un genre additionnel plutôt qu'une dimension supplémentaire. • Le néerlandais comme les langues scandinaves ont à peu près perdu les cas (il reste toujours des traces de génitif çà et là, d'ailleurs il en reste dans le possessif en 's de l'anglais, et certains dialectes norvégiens ont encore un datif, mais grosso modo ça a disparu). • Par ailleurs, les langues dérivées du vieux norrois (les langues scandinaves et l'islandais) ont perdu le -n- qui caractérisait les désinences faibles : celles-ci deviennent essentiellement vocaliques. • Mais à l'inverse, ces langues nordiques ont une innovation par rapport aux autres langues germaniques, qui est l'article défini postposé, à l'origine un simple placement de l'article défini après le nom plutôt qu'avant, mais qui se transforme en désinence grammaticale, et qui fait qu'à côté de la distinction définie/indéfinie sur l'adjectif, il y a maintenant une distinction de même type sur le nom, — distinction que je vais appeler articulée/inarticulée plutôt que définie/indéfinie pour éviter la confusion. (Chose amusante, cet article défini postposé ressemble superficiellement à une réapparition du -n qui avait disparu de la désinence faible des adjectifs.) • Enfin, les langues qui dérivent du vieil allemand (c'est-à-dire essentiellement : l'allemand et le néerlandais) ont perdu l'accord des adjectifs attributs, considérés comme quasi-adverbiaux (en allemand moderne, cet homme est grand, cette maison est grande, ces enfants sont grands se dit dieser Mann ist groß, dieses Haus ist groß, diese Kinder sind groß avec partout la même forme groß, alors qu'en suédois on a den här mannen är stor, det här huset är stort, de här barnen är stora montrant qu'il y a bien un accord de stor selon que le sujet est utre singulier, neutre singulier ou pluriel).

L'allemand (à partir du moyen allemand) a réinterprété la règle permettant de décider si on utilise les désinences fortes ou faibles de l'adjectif, et en ce faisant, elle l'a transformée. À l'origine, comme je l'ai expliqué, on utilise les désinences faibles quand le nom est déterminé (précédé d'un article défini ou d'un démonstratif, ou éventuellement d'un possessif), et les désinences fortes dans les autres cas. En allemand moderne, la situation est différente. D'abord, il faut noter que les noms ont quasiment perdu leur déclinaison (à l'exception de certains noms dits faibles ou mixtes, il ne reste que les désinences -s au génitif singulier des masculins et neutres, et -en au datif pluriel de tous les genres, plus des traces d'un -e optionnel au datif singulier de certains mots) : la marque du genre et du cas est essentiellement portée par l'article (ou autre déterminant : démonstratif, possessif…) et éventuellement par l'adjectif qui est ce dont je veux parler. La règle de base de l'allemand moderne pour l'inflexion des adjectifs est : on place sur l'adjectif épithète la désinence qu'on mettrait sur l'article défini si celle-ci n'y est pas et sinon l'adjectif prend la désinence « faible » (qui est -en à tous les cas infléchis et -e aux cas non-infléchis, où par « non-infléchi » je veux dire un cas identique à un nominatif singulier). Ainsi, la distinction ne se fait plus sur le fait qu'on ait ou non l'article défini, mais sur le fait qu'on ait ou non une désinence marquant le genre et le cas : même si cette désinence est sur l'article indéfini, elle entraîne quand même les désinences faibles à l'adjectif. Pour donner un exemple, précisons que la préposition mit (avec) régit le datif et que la désinence normale (« forte ») du datif masculin/neutre singulier est un -m : on écrit ainsi mit starkem Willen, avec [une] puissante volonté, la désinence « forte » -m étant présente parce qu'elle n'est pas portée ailleurs, mais mit dem starken Mann, avec l'homme puissant, la désinence faible -en étant présente parce que le -m est marqué ailleurs : sur ces exemples, il n'y a aucune différence avec la distinction déterminé/indéterminé, mais elle apparaît si je donne le troisième exemple, mit einem starken Mann, avec un homme puissant, où on a la désinence faible -en à l'adjectif parce que la forte -em est présente à l'article indéfini, bien que celui-ci soit indéfini (et bien qu'en vieil allemand on aureût eu mit einemu starkemu manne, forme indéterminée, contre mit dëmu starken manne, forme déterminée essentiellement identique à l'allemand moderne). • Par ailleurs, la règle fonctionne normalement quand l'adjectif est substantivé (par exemple, der Deutsche, l'Allemand, i.e., la personne allemande, donne mit einem Deutschen, prenant la désinence faible puisque la forte est déjà sur le déterminant).

Ce qui complique les choses en allemand, par rapport à la règle que j'ai énoncée ci-dessus, c'est que certains déterminants « ne comptent pas » au sens où même s'ils portent la désinence forte, l'adjectif ne passe pas pour autant à la désinence faible : c'est ici que ressort la distinction sémantique déterminé/indéterminé à travers la règle réinterprétée par l'allemand. Ainsi, on écrit alle guten Menschen, tous les hommes bons (avec la désinence faible parce que porte la désinence forte du pluriel) mais viele gute Menschen, beaucoup d'hommes bons, parce, que Wotan sait pourquoi, viel est un de ces mots qui ne comptent pas, i.e., préserve la déclinaison forte de l'adjectif : les grammaires allemandes doivent donc proposer des tables et des commentaires sur ces différents mots.

Le néerlandais moderne est de quasiment tout point de vue une version simplifiée de l'allemand moderne : pas de cas, fusion des genres masculin et féminin en un genre utre, et bien sûr, comme l'allemand moderne, les adjectifs attributs sont invariables. Il devient un peu difficile de parler de désinences faible ou forte sur l'adjectif, vu qu'il n'y a qu'une seule désinence possible, -e, qui est utilisé sur l'adjectif épithète sauf quand il se rapporte à un neutre singulier indéfini (indéfini voulant dire ici : précédé de l'article indéfini een ou de pas d'article du tout — ou de quelques autres choses comme geen signifiant pas de ou veel signifiant beaucoup). En appliquant cette règle (et en sachant que het huis, la maison, est neutre comme attesté par l'article défini het, tandis que de vrouw, la femme, est utre comme attesté par l'article défini de), on peut donc prévoir : het huis is groot (la maison est grande), de vrouw is groot (la femme est grande), de huizen zijn groot (les maisons sont grandes), de vrouwen zijn groot (les femmes sont grandes), het grote huis (la grande maison), de grote vrouw (la grande femme), de grote huizen (les grandes maisons), de grote vrouwen (les grandes femmes), een groot huis (une grande maison), een grote vrouw (une grande femme), grote huizen (de grandes maisons), grote vrouwen (de grandes femmes). En fait, le problème avec le néerlandais est peut-être que cette règle est trop simple, du coup on ne sait pas trop à quoi la rattacher. J'ai tendance à la retenir sous la forme suivante : comme l'article indéfini een ne change pas selon le genre, on marque le genre sur l'adjectif en retirant la désinence -e au neutre — sous cette forme, c'est à peu près la même logique que l'allemand. Mais je souligne quand même une différence avec l'allemand moderne (et qui heurte la logique que je viens de proposer) : c'est qu'en néerlandais (comme en vieil allemand) les noms précédés de possessifs sont considérés comme déterminés, donc on dira m'n grote huis is een groot huis (ma grande maison est une grande maison — oui, c'est idiot, mais c'est juste pour souligner que l'adjectif prend deux formes différentes, une fois déterminée et une fois indéterminée) alors qu'en allemand cette même phrase est mein großes Haus ist ein großes Haus (avec deux fois les désinences fortes parce qu'elles ne sont pas sur le déterminant).

Les langues scandinaves reflètent bien le mécanisme général des langues germaniques (historique, c'est-à-dire sans la réinterprétation qu'en a faite l'allemand) : dans le cas défini, quelle que soit le genre ou le nombre, l'adjectif prend la désinence faible/définie, qui est un -e sauf en suédois où c'est le plus souvent un -a ; et dans le cas indéfini, il prend la désinence forte/indéfinie, qui est respectivement - [rien] au genre utre, -t au neutre, et normalement identique à la désinence faible (-e ou -a) au pluriel. Contrairement à l'allemand et au néerlandais où les adjectifs attributs sont invariables, ils prennent dans les langues scandinaves les désinences fortes/indéfinies. Concernant le choix de la désinence -a/-e en suédois, c'est normalement un -a, sauf pour les participes passés en -ad (→-ade), pour les superlatifs en -ast (→-aste), et quand le nom qualifié est singulier et se réfère à un individu masculin (il s'agit ici d'un genre sémantique et non grammatical), mais encore ce dernier point est-il optionnel dans la plupart des cas (sauf pour un adjectif substantivé). Dans les autres langues scandinaves, la désinence faible et pluriel est simplement -e. En norvégien, dans la mesure où il existe une distinction entre masculin et féminin (plus ou moins marquée selon les dialectes, et absente du danois et du suédois), elle ne se traduit de toute façon pas sur l'adjectif (sauf, je l'ai dit, pour liten, petit, qui devient lita au féminin).

Là où il y a une subtilité, c'est que, comme je l'ai mentionné, dans les langues scandinaves, les noms eux-mêmes ont une alternance définie/indéfinie que je vais plutôt appeler articulée/inarticulée (par exemple, dans toutes ces langues, hus, maison, forme inarticulée, mais huset, la maison, forme articulée). La forme articulée du nom vient d'un article défini postposé en vieux norrois, qui lui-même se déclinait (en plus de la déclinaison du nom lui-même), et on peut débattre de la question de savoir si dans les langues scandinaves modernes cette marque de définition est un mot clitique ou une désinence : à mon avis ce débat n'a aucun intérêt. (En revanche, on peut prendre le soin de remarquer que la dichotomie défini/indéfini pour l'adjectif et la dichotomie articulé/inarticulé pour le nom n'ont pas la même origine et pas tout à fait le même rôle : pour l'adjectif, c'est une caractéristique des langues germaniques qui vient d'une déclinaison faible comme je l'ai expliqué en détail, tandis que pour le nom c'est une spécificité des langues nordiques qui vient d'un article défini postposé, et pour ce qui est du rôle, je vais expliquer la différence dans un instant.) Toujours est-il qu'on a bien quatre formes du nom : le singulier inarticulé, le singulier articulé, le pluriel inarticulé et le pluriel articulé. Et il y a différentes classes d'inflexion de noms selon les terminaisons exactes, même si le modèle général, dans l'ordre que je viens de dire, ressemble grossièrement à -;-en;-ar;-arna au genre utre et -;-et;-;-en au neutre (à quoi il faut encore ajouter -;-a;-ar;-ane pour le féminin en norvégien). • Comme l'adjectif s'accorde en genre et en nombre avec le nom, on peut être tenté de croire qu'il s'accorde aussi en définition : or ce n'est pas tout à fait le cas, on peut avoir un adjectif défini qualifiant un nom inarticulé. Plus exactement, lorsqu'un nom qualifié par un adjectif veut être utilisé de façon définie, toutes les langues scandinaves utilisent un article défini préposé (den au genre utre, det au neutre, de au pluriel) : en danois, cet article défini préposé fait disparaître l'article défini postposé, c'est-à-dire que le nom sera à la forme inarticulée, tandis que l'adjectif sera à la forme définie (huset, la maison, mais det store hus, la grande maison) ; en suédois, au contraire, on utilise à la fois l'article préposé et l'article postposé, on parle de double détermination, qui est même plutôt triple puisque l'adjectif est aussi à la forme déterminée (det stora huset, la grande maison) — il y a donc bien ici coïncidence entre forme articulée du nom et forme définie de l'adjectif, mais dans d'autres situations, comme après un possessif, on utilise quand même la forme définie de l'adjectif avec la forme inarticulée du nom (min stora hus, ma grande maison) ; quant au norvégien, comme souvent, il hésite, selon les dialectes, entre ce que fait le danois et ce que fait le suédois (en penchant quand même plus côté suédois). Il faudrait aussi mentionner la situation où on a un adjectif substantivé : on utilise alors l'article défini préposé (den / det / de) pour marquer la détermination, on ne se contente pas de la forme déterminée de l'adjectif : ceci exhibe une différence de plus avec les noms (où la forme articulée s'emploie seule pour marquer la détermination).

Pour faire une discussion complète, il y aurait 18 possibilités à envisager selon la présence de l'article défini préposé, d'un autre déterminant ou rien, selon que la forme de l'adjectif est définie ou indéfinie ou qu'il n'y a pas d'adjectif, et selon que la forme du nom est articulée ou inarticulée. Il faudrait considérer chacune de ces 18 combinaisons dans les différentes langues scandinaves modernes, aussi bien dans ses formes « standard » que dans des formes « dialectales », et chercher si elle se trouve régulièrement, seulement dans des expressions figées ou isolées, ou essentiellement jamais. Je n'ai évidemment pas la compétence de mener une telle étude : ce que je trouve de plus proche est l'article d'Östen Dahl, Definite articles in Scandinavian: Competing grammaticalization processes in standard and non-standard varieties.

Si je reprends les mêmes exemples que j'ai donnés pour le néerlandais, et si par miracle je ne me suis pas trompé dans le copier-coller, ils donnent en suédois : huset är stort (la maison est grande), kvinnan är stor (la femme est grande), husen är stora (les maisons sont grandes), kvinnorna är stora (les femmes sont grandes), det stora huset (la grande maison), den stora kvinnan (la grande femme), de stora husen (les grandes maisons), de stora kvinnorna (les grandes femmes), ett stort hus (une grande maison), en stor kvinna (une grande femme), stora hus (de grandes maisons), stora kvinnor (de grandes femmes). Et en danois : huset er stort (la maison est grande), kvinden er stor (la femme est grande), husene er store (les maisons sont grandes), kvinderne er store (les femmes sont grandes), det store hus (la grande maison), den store kvinde (la grande femme), de store huse (les grandes maisons), de store kvinder (les grandes femmes), ett stort hus (une grande maison), en stor kvinde (une grande femme), store huse (de grandes maisons), store kvinder (de grandes femmes).

Bon, je pense que je suis entré dans suffisamment de détails, je ne vais pas vous raconter les histoires de comparatifs et de superlatifs (ben oui, j'ai triché en disant qu'il y avait 4 cas fois 2 nombres fois 3 genres fois 2 niveaux de détermination = 48 combinaisons : il faut encore multiplier par 3 degrés de comparaison), et des langues qui ont décidé de façon purement vexatoire de ne pas être d'accord sur la question de savoir si les comparatifs s'infléchissent (et hop, une variable booléenne à mettre de plus dans la fonction que le cerveau doit évaluer à toute vitesse : est-ce ce machin est un comparatif et est-ce que dans la langue que je suis en train de parler en ce moment les comparatifs s'accordent ?). Je ne m'étends pas non plus sur la grammaire de l'islandais, qui colle de toute façon avec le système historique que j'ai présenté plus haut.

Si vous vouliez juste un conseil quant à savoir quelle langue apprendre, apprenez l'anglais : il n'est peut-être pas idéal au niveau vocabulaire et prononciation, mais au moins il ne vous demande pas de réfléchir dix secondes à chaque fois que vous voulez utiliser un adjectif. Moi je vais réviser mon norvégien en regardant Okkupert ce soir à la télé.

(lundi)

Le cerveau et les fonctions booléennes (idées d'expériences)

Je me dis souvent que j'aimerais avoir un tas de cobayes humains pour faire toutes sortes d'expériences cognitives dessus (et pas que des sciences cognitives, d'ailleurs : j'aimerais aussi faire toutes sortes d'expériences sociales, ou simplement de sondages sur un échantillon représentatif de la population française). Malheureusement, je ne suis pas un savant fou qui aurait des centaines de sujets d'expérience prisonniers dans sa cave, je n'ai pas non plus les accréditations (ou encore moins la patience) pour demander les financements permettant de monter des expériences dans des conditions scientifiques, alors je ne peux que lancer les idées en l'air en soupirant ce serait bien de faire ce genre d'expérience et spéculer de façon totalement gratuite sur le résultat (et me dire au passage que l'avantage des mathématiques sur d'autres domaines scientifiques, c'est quand même qu'on n'a pas besoin d'avoir des objets d'expérience prisonniers dans sa cave, dans une boîte de Petri ou dans un synchrotron à 10 giga-euros). Zut, je suis encore en train de digresser.

Une expérience que j'aimerais bien mener, donc, c'est d'essayer de mesurer le temps que le cerveau prend pour évaluer des fonctions booléennes (je vais expliquer dans un instant ce dont il s'agit) et essayer de modéliser la manière dont il s'y prend. Notamment : est-ce que ce temps dépend fortement des individus, est-ce qu'il dépend fortement de la fonction évaluée, à quelle vitesse « apprend-on » une fonction booléenne (c'est-à-dire, à quelle vitesse en acquiert-on un automatisme) et cette acquisition est-elle dépendente de la manière dont les entrées de la fonction sont présentées. Et aussi : dans quelle mesure est-ce que les animaux peuvent apprendre des fonctions un peu complexes.

Je m'explique.

Voici un premier jeu d'expériences imaginables. Commençons par l'expérience la plus triviale qui soit, et qui peut servir de mesure de base à laquelle comparer les autres  : le sujet a une lumière devant lui et un bouton. Toutes les secondes (disons), la lumière va aléatoirement passer dans l'état « éteint » ou « allumé » : le sujet a pour mission d'appuyer sur le bouton si la lumière est allumée. Cette tâche est extrêmement simple, et il est à prévoir qu'on y arrive très rapidement (au niveau du temps de réflexe), et avec très peu d'erreurs : il peut cependant être intéressant de faire varier certains paramètres (lumière qui peut prendre deux couleurs au lieu d'être éteinte/allumée, deux boutons entre lesquels il faut choisir, cadencement choisi par le sujet au lieu d'être à vitesse fixe, que sais-je encore). Maintenant, l'idée serait de mettre plus de lampes et de demander au sujet de réagir selon des conditions plus complexes. Une telle condition est appelée fonction booléenne.

Par exemple : s'il y a deux lampes, on peut demander au sujet d'apuyer sur le bouton si la lampe de gauche est allumée ; ou si les deux le sont ; ou si l'une des deux l'est ; ou si la lampe de gauche est éteinte ; ou encore : si la lampe de gauche est allumée ou que celle de droite est éteinte. En tout, il y aurait 16 fonctions booléennes à tester sur 2 lampes, même si certaines n'ont aucun intérêt (demander d'appuyer à tous les coups sur le bouton n'est pas franchement passionnant) et d'autres peuvent certainement être regroupées pour des raisons de symétrie (je doute qu'on réagisse plus rapidement ou plus fiablement à des conditions portant sur la lampe de gauche qu'à celles sur la lampe de droite ou vice versa). J'imagine qu'on aurait beaucoup plus de facilité à exécuter rapidement et fiablement la tâche appuyer sur le bouton si l'une ou l'autre lampe est allumée que appuyer sur le bouton si la lampe de gauche est allumée ou la lampe de droite éteinte, mais ce qui m'intéresse, entre autres, est de quantifier cette différence et d'essayer de modéliser ce qui rend certaines tâches plus faciles que d'autres. Il faudrait savoir, aussi, si le temps dépend de la manière dont on a formulé la phrase (pour des fonctions booléennes équivalentes) : est-il plus facile de appuyer sur le bouton si la lampe de gauche est allumée et la lampe de droite éteinte ou de appuyer sur le bouton si la lampe de gauche est allumée sauf si la lampe de droite l'est aussi ? Et si on donne les instructions sans mots mais avec autant d'exemples que nécessaire ?

Sur un plus grand nombre de lampes, je suis tout à fait certain qu'on irait beaucoup plus vite sur les tâches qui s'expriment très simplement avec des nombres, par exemple appuyer sur le bouton si au moins trois lampes sont allumées, mais il serait intéressant de comparer avec d'autres tâches d'assez basse complexité booléenne, notamment des fonctions positives, du genre appuyer sur le bouton si l'une des deux lampes de gauche est allumée et que l'une des deux lampes de droite l'est (mettons qu'il y en ait quatre au total). Une fonction booléenne est dite positive lorsque le fait de changer une de ses variables de fausse à vraie (i.e., allumer une lampe) ne peut pas rendre faux le résultat (i.e., faire qu'on ne doive plus appuyer sur le bouton) : a-t-on globalement plus de facilité à calculer de telles fonctions que pour des fonctions qui peuvent comporter des négations ?

Mais bien sûr, il ne faut pas se contenter d'expérimenter avec des lampes (allumées/éteintes) et des boutons. Je voudrais aussi savoir, notamment, comment le temps de réponse est affecté si les entrées de la fonction booléenne sont hétérogènes : si je demande au sujet d'appuyer sur un bouton si on lui présente une forme qui est un carré ou qui est rouge, est-ce que la différence de temps de réaction par rapport à juste détecter un carré ou juste détecter du rouge est comparable à celle qu'on aurait mesuré pour la fonction booléenne ou à deux lampes ? Et pour une tâche du genre appuyer sur le bouton si la forme de gauche est un carré ou qu'elle est rouge, et que la forme de droite est un triangle ou qu'elle est bleue, est-ce que le fait de s'être préalablement entraîné à exécuter la tâche appuyer sur le bouton si l'une des deux lampes de gauche est allumée et que l'une des deux lampes de droite l'est va fournir un avantage ? Autrement dit, notre cerveau est-il capable de précompiler des fonctions booléennes polymorphes ? ou bien chaque fonction est-elle apprise uniquement pour une situation bien précise et non réutilisable ? Et si je fais subir au même cobaye des mois et des mois de tâches différentes toujours avec la même fonction booléenne ([x ou y] et [u ou v]), va-t-il quand même finir par en acquérir un automatisme ?

Le nombre de questions que je me pose est très élevé, je ne vais pas toutes les écrire parce que ce serait assez fastidieux, d'autant que certaines dépendent de résultats des expériences antérieures, mais vous voyez le genre d'idées.

Pourquoi est-ce que je m'intéresse à ça ? Parce que j'ai l'impression que je me retrouve régulièrement à exécuter des tâches de ce genre : fouiller mentalement ou visuellement dans un ensemble d'items pour trouver ceux qui remplissent certains critères exprimés comme combinaisons booléennes d'autres critères, et je trouve qu'il y a décidément une certaine fatigue mentale spécifique associée à ce travail.

Mais je pense aussi à un type particulier de tâches : l'application des règles de grammaire. En écrivant cette entrée, j'ai commencé ici une longue digression sur l'inflexion des adjectifs dans les langues germaniques : finalement, je l'ai coupée et j'en ferai sans doute une entrée séparée qui n'intéressera personne, mais voici juste l'exemple de la règle (un peu simplifiée) permettant de savoir si on doit mettre la désinence -e (la seule possible) sur un adjectif en néerlandais : on ajoute cette désinence lorsque l'adjectif est épithète et que le nom qualifié est non-neutre ou pluriel ou précédé de l'article défini. (A contrario, ceci signifie qu'on ne met pas la désinence lorsque l'adjectif est attribut ou que le nom est neutre singulier précédé de [l'article indéfini ou d'une absence d'article].) Ce n'est pas une fonction booléenne terriblement compliquée (c'est en tout cas beaucoup plus simple que la multitude de cases à envisager en allemand ou en islandais, et c'est aussi un peu plus simple que la règle correspondante pour le danois ou le suédois), mais pour parler une langue à une vitesse raisonnable, il faut arriver à calculer ce genre de fonctions très efficacement et de façon complètement automatique (i.e., sans y réfléchir consciemment) : et avant que l'automatisme s'installe, ce qui demande énormément de pratique, on passe par une longue phase assez fastidieuse où chaque utilisation d'un adjectif implique une petite gymnastique mentale (est-ce que mon adjectif est épithète ? est-ce qu'il y a un article ? est-ce que cet article est défini ? est-ce que le nom est neutre ?). Je trouve qu'il serait intéressant de faire des expériences sur des gens n'ayant aucune connaissance préalable du néerlandais du temps nécessaire pour appliquer cette règle booléenne.

Bon, souvent, quand on considère les règles de grammaire, il ne s'agit plus tellement de fonctions booléennes au sens strict, c'est-à-dire que les entrées de la fonction ne sont plus obligatoirement de nature vrai/faux, mais peuvent être dans des ensembles de valeurs un petit peu plus gros, comme les trois genres — masculin, féminin et neutre — ou les quatre cas grammaticaux — nominatif, accusatif, datif et génitif — de l'allemand. Bien sûr, cette distinction est un peu byzantine, mais je pense en revanche qu'il y a une vraie distinction à faire, dans le processus mental, entre d'une part les fonctions booléennes ou « presque », avec des entrées qui prennent deux ou un petit nombre de valeurs possibles, et d'autre part des tableaux morphologiques comme des tables de conjugaison ou de déclinaison.

Si je m'écarte un peu des fonctions booléennes ou à petites entrées finies considérées ci-dessus, on pourrait aussi regarder les automates finis simples. Je pense par exemple à l'exercice mental que constitue la lecture d'une portée musicale avec beaucoup d'altérations (:= dièzes et bémols) et de changements d'altérations : la convention d'écriture est que la portée porte un certain nombre d'altérations « par défaut », et que chaque fois qu'une modification est faite, elle vaut pour la mesure en cours jusqu'à la fin de celle-ci : on peut voir ça comme l'application d'un automate fini, et il serait intéressant de mesurer la rapidité à laquelle on arrive à effectuer cette tâche sans entraînement préalable.

Bon, je devrais sans doute écrire des pages JavaScript qui proposent toutes sortes d'exercices dans ce genre et qui mesurent le temps et la fiabilité des réponses — comme ça, à défaut d'avoir des cobayes sur lesquels tester, je pourrais au moins me tester moi-même.

(vendredi)

Pourquoi les ordinaux me fascinent (une introspection psychologico-mathématique)

J'ai déjà récemment écrit une entrée sur mon obsession pour la symétrie, qui est certainement responsable d'une bonne partie de l'attrait que les mathématiques ont pour moi, et qui déborde sur ma fascination pour certaines formes de mysticisme assez visible notamment dans les œuvres littéraires que j'ai tenté d'écrire quand j'étais plus jeune. Mais il y un autre aspect des mathématiques qui me hante et sur lequel je n'arrive pas vraiment à placer un nom : disons, faute de mieux, la grandeur. Je ne sais pas non plus expliquer exactement en quoi cela consiste (pour être clair, je ne parle pas d'un concept mathématique, mais du ressenti commun que j'ai de certaines parties des mathématiques) ; j'ai tendance à penser que c'est le contrepoids de la symétrie, donc peut-être que hiérarchie serait un meilleur terme. Si je devais écrire sérieusement une œuvre dont j'ai déjà publié certains fragments aléatoires, et imaginer un monde allant avec, où les mathématiques donneraient des pouvoirs arcanes, il y aurait sans doute deux types de pouvoirs et d'utilisateurs de ceux-ci : les magiciens, qui utiliseraient la symétrie, et les clercs (pour reprendre la terminologie rôliste) qui utiliseraient la hiérarchie. Maintenant, c'est peut-être mon obsession pour la symétrie qui me fait proposer cette classification : néanmoins, il est certain que, si je dois faire le chemin des mathématiques au mysticisme, la symétrie m'évoque clairement une forme de magie pour les raisons que j'ai déjà expliquées dans l'entrée que je lui ai consacrée, tandis que ce dont je veux parler ici a une saveur, disons, plus religieuse, et cela transparaît notamment dans la Théorie de la Totalité Transfinie de Turing que je décrivais dans cette entrée.

Je ne sais pas quel est le phénomène mathématique sous-jacent à cette impression mentale de « grandeur » ou « hiérarchie », donc, mais je sais quel est le concept qui la réalise le plus parfaitement : il s'agit des ordinaux. J'ai déjà écrit ici une vulgarisation de ce concept (et j'ai même fait un visualisateur permettant de naviguer parmi les plus petits d'entre eux, quoiqu'il faille admettre qu'on n'y voit rien), donc mon but ici n'est pas de parler de mathématiques (même s'il est à prévoir que je n'y résisterai pas : j'invite alors le lecteur non intéressé par les questions techniques à ignorer ces passages, ou de lire en diagonale). Ce que je veux présenter aujourd'hui est l'effet psychologique qu'ont sur moi les ordinaux — une sorte de psychanalyse de l'infini, si on veut, si ce n'est que je ne prétends pas vraiment être sérieux.

C'est une réalisation fascinante pour beaucoup d'enfants, lorsqu'ils apprennent à compter, qu'il n'y a pas de plus grand nombre : j'ai déjà écrit des choses à ce sujet, je ne vais pas revenir sur cette fascination du fait que dans le jeu qui peut dire le nombre le plus grand, quand quelqu'un dit N, quelqu'un d'autre peut dire N+1 (ou N×2, ou N², ce qui en langage d'enfants signifie transformer un zilliard en un zilliard de zilliards ; je note qu'une compréhension des opérations les plus importantes des fonctions arithmétiques « élémentaires » vient assez tôt). La grande-cousine de mon poussinet nous racontait récemment, en parlant de son petit-fils, que ce dernier était passionné par savoir qui compte le plus loin. Et j'ai le souvenir assez net d'avoir joué à ces jeux (qui peut dire le nombre le plus grand, et qui peut compter le plus loin) quand j'étais petit. Je pense que c'est un signe que les mathématiques peuvent exercer un véritable attrait sur les enfants — avant qu'on les rende chiantes pour eux en leur faisant faire des calculs pénibles et mécaniques à en dégoûter n'importe qui. Et je me souviens aussi d'avoir eu des discussions, quand je jouais à ces jeux, pour savoir si quelqu'un avait le droit de dire l'infini, et si l'infini plus un (ou l'infini plus l'infini ou l'infini d'infinis) était alors une réponse légitime, entre ceux qui pensaient que ça n'existait pas, ceux qui pensaient que c'était de toute façon pareil que l'infini, et ceux qui pensaient que c'était encore plus grand. (Et en un certain sens, tous ont raison : il y a différentes sortes d'infinis mathématiques selon l'usage qu'on veut en faire ; mais les ordinaux vont plutôt donner raison aux derniers, et pousser la logique.)

Mais il n'y a pas que cette fascination pour les nombres à laquelle je pense chez les petits enfants. Il y en a une autre, que je pourrais traduire comme l'idée que beaucoup de choses doivent être totalement ordonnées : l'autre jour, dans une brasserie où je déjeunais, j'entendis un enfant demander à son père qui était le plus fort entre Darth Vader (enfin, Dark Vador, vu qu'il parlait français) et je n'ai pas entendu le deuxième terme mais j'imagine volontiers que c'était un super-héros quelconque. Par coïncidence (coïncidence certes un peu limitée vue la sortie prochaine d'un film très attendu), j'ai entendu, le même jour dans la rue, un autre gamin poser exactement la même question entre Darth Vader et un camion lancé à toute allure contre lui (question bizarre, mais je crois bien que c'est ça). Je ne sais pas si cette croyance que la puissance des super-héros ou des choses est totalement ordonnée (par la relation gagne un combat contre ?) est enracinée dans le développement de notre cerveau ou si c'est culturel[#] (par exemple, à force de se faire entrendre dire que Foo est plus Zippyesque que Bar dans la publicité, dans la fiction, etc.), mais il est certain que, petits, nous avons un certain goût pour les relations d'ordre total et que ce goût ne disparaît pas totalement, en tout cas pas chez moi, quand nous découvrons qu'en fait le monde n'est pas si simple, et que deux choses ne sont pas toujours comparables.

[#] Spontanément, j'aurais plutôt tendance à imaginer que c'est culturel ; mais d'un autre côté, beaucoup du Mahābhārata, de ce que j'en ai retenu, est consacré à comparaison de personnages guerriers chaque fois plus puissants et moralement plus droits que tous ceux qui ont précédé, et à la vérification de ces comparaisons au cours de combats. Donc même si les auteurs épiques prennent ensuite plaisir à trahir les attentes qu'on peut avoir sur les résultats de ces comparaisons, et à introduire des ordres cycliques ou autrement paradoxaux, je soupçonne que la présupposition de l'ordre total se trouve bien dans la culture qui a engendré cette épopée.

Les ordinaux sont en quelque sorte la sublimation de ces jeux d'enfants : de deux ordinaux, il y a toujours un plus grand (plus fort, plus puissant, plus infini), d'ailleurs dans quasiment tous les cas qu'on rencontre, le plus grand est tellement monstrueusement plus grand que le plus petit, que le plus petit pourrait essentiellement être le nombre 1 ; et à chaque fois qu'on a un ensemble d'ordinaux, il y en a un qui est le plus petit de l'ensemble, et il y a un ordinal qui est plus grand que tous ceux qu'on s'est donné. Si on appelle ω la réponse que fait l'enfant qui dit l'infini en réponse aux milliards et milliards de milliards que les autres ont proposés (techniquement, donc, le plus petit ordinal supérieur à tous les ordinaux finis), alors il y aura des ordinaux ω+1 (l'infini plus un), ω·2 (l'infini plus l'infini) et ω² (l'infini d'infinis) et encore d'autres choses plus grandes.

Mais je ne vais pas expliquer mon obsession pour les ordinaux uniquement à partir de ces jeux d'enfants. Il y a aussi une élégance intellectuelle dans la manière dont les ordinaux sont construits qui ne peut pas ne pas susciter l'admiration : le même genre d'élégance qui fait qu'on comprend que compter à partir de zéro est la bonne façon de faire (et d'ailleurs les ordinaux commencent à zéro). J'ai tenté d'expliquer ça dans l'entrée de vulgarisation que je leur ai consacrée, mais je pourrais résumer la construction des ordinaux en :

À chaque fois qu'on a construit les ordinaux jusqu'à un certain point, on crée un nouvel ordinal qui vient juste après tous ceux-là.

Cette idée est tellement génialement simple qu'on a du mal à se rendre compte de sa puissance. Initialement, je ne sais pas du tout ce que c'est qu'un ordinal, donc je n'en ai aucun : selon le principe que je viens d'énoncer, je crée donc un premier ordinal qui vient après rien du tout (i.e., c'est le plus petit de tous les ordinaux), et que j'appelle 0. Je connais maintenant donc un seul ordinal, qui s'appelle 0, et selon le principe de construction que j'ai énoncé, j'en crée donc un autre qui vient juste après 0, et je l'appelle 1. À ce stade-là, je connais donc 0 et 1, et je crée donc un nouvel ordinal qui vient juste après eux, et je l'appelle 2. En procédant de la sorte, je crée des ordinaux correspondant aux entiers naturels (0, 1, 2, 3, 4, 5… 42, 43, 44… 1000… 10↑42…), qui n'ont déjà pas de fin. Mais contrairement à la fabrication des entiers naturels (en gros, je fabrique 0, puis si je fabrique n, alors je fabrique aussi n+1), le principe que j'ai énoncé ci-dessus continue de s'appliquer : maintenant que je connais les entiers naturels, je crée un nouvel ordinal qui vient juste après tous ceux-là et je l'appelle ω, ce qui donne à son tour naissance à ω+1 et ainsi de suite.

Ce principe de construction est merveilleux parce que c'est exactement le même qui s'applique à chaque fois, et qui ne cesse jamais de s'appliquer, et malgré cela il donne naissance à une richesse et une diversité extraordinaires, mais je vais y revenir. Et les choses se déroulent ex nihilo, à partir du rien (comme je viens de le dire, le principe marche dès le début : on n'a pas d'ordinaux pour commencer, donc on crée un ordinal 0, il n'y a pas de règle spéciale pour 0 comme il y a pour les entiers naturels). On comprend que Cantor, quand il a découvert le concept, ait été ébloui par ce sur quoi il venait de mettre le doigt. (Et on comprend aussi que cette idée ait suscité la réticence, pour ne pas dire l'hostilité, de la communauté mathématique de l'époque, selon un modèle assez bien résumé par ce webcomic ; David Hilbert a bien eu raison en parlant — au sujet de la théorie des ensembles, mais certainement des ordinaux et cardinaux en particulier — d'un paradis que Cantor a créé et dont il ne faut pas que les mathématiciens nous chassions nous-mêmes.) Mais la construction a été rendue encore plus éblouissante par von Neumann, qui a proposé (Zur Einführung der transfiniten Zahlen, Acta Litt. ac Scient. Univ. Hung. 1, 199–208, en 1923 — l'auteur était âgé de même pas vingt ans !) la réalisation suivante des ordinaux, maintenant complètement standard :

Un ordinal est l'ensemble des ordinaux plus petits que lui.

Ainsi 0 est l'ensemble vide (∅) puisqu'il n'y a pas d'ordinaux plus petits, tandis que 1 est l'ensemble {0} = {∅} ayant pour seul élément 0=∅ puisque ce dernier est le seul ordinal plus petit, et 2 est l'ensemble {0,1} = {∅,{∅}} ayant les éléments 0 et 1, et ainsi de suite ; et ω = {0,1,2,3,…} est l'ensemble des entiers naturels. Ce n'est pas terriblement important pour la nature des ordinaux qu'ils soient « réalisés » comme par la définition de von Neumann, mais cela ajoute encore énormément à l'élégance fascinante de la construction, et au sentiment qu'elle se fabrique toute seule à partir de rien.

Il est certain que cette idée ne pouvait que susciter lors de son introduction des réactions assez vives, centrées sur le caractère légitime ou non d'admettre l'infini (l'infini actuel, c'est-à-dire réalisé, et non seulement potentiel) comme objet mathématique légitime, et le fait que la construction soit littéralement ex nihilo n'améliorait certainement pas les choses. J'ai mentionné ci-dessus qu'elle a suscité une très vive opposition, y compris de la part de certains des esprits les plus brillants du monde mathématique, comme Poincaré ou Weyl (et pas seulement des mathématiciens : Wittgenstein était profondément hostile à la théorie des ensembles), tandis que d'autres, non moins brillants, comme Hilbert ou von Neumann, l'ont accueillie avec enthousiasme. Pour la défense des sceptiques et détracteurs de la théorie des ensembles en général, et des ordinaux en particulier, il faut dire que toutes sortes de paradoxes (celui de Burali-Forti qui invite à considérer l'ensemble de tous les ordinaux, je vais y revenir, et celui de Russell qui invite à considérer l'ensemble de tous les ensembles qui n'appartiennent pas à eux-mêmes) ont été découverts dans la première formulation, pré-axiomatique, de la théorie des ensembles, et ces paradoxes pouvaient s'interpréter comme une impossibilité absolue de traiter directement des quantités infinies sans arriver à des contradictions. De nos jours, tout le monde ou presque admet que la difficulté était simplement de codifier rigoureusement les règles par lesquelles on a le droit de manipuler des ensembles et des infinis, et qu'une fois ces règles bien fixées (comme elles l'ont été par Ernst Zermelo et Abraham Fraenkel), la contradiction disparaît sûrement. (« Sûrement », même si on sait depuis Gödel qu'on ne peut jamais être totalement certain que la contradiction n'existe pas, et à chaque fois qu'on ajoute un infini plus grand, on ne peut qu'en être moins certain.) Ce qui est certain, c'est que la théorie des ensembles, et notamment la notion d'ordinal, fait partie des mathématiques maintenant considérées comme standard, même si cela n'empêche pas les crackpots de se concentrer dessus et de chercher à contredire différents passages de ce qu'ils ne comprennent pas, et spécifiquement les résultats de Cantor (typiquement, l'argument diagonal, même si celui-ci ne parle pas vraiment d'ordinaux). Et s'il y a une contradiction dans la théorie des ensembles, elle ne doit pas être si évidente que ça, vu le plaisir avec lequel des raisonnements d'une sophistication incroyable sont menés dedans et ne sont jamais encore tombés dans une contradiction[#2].

[#2] Digression technique : Des gens savants peuvent ici me rétorquer : mais si, on est tombé dans une contradiction !, en postulant l'existence d'un cardinal Reinhardt. Je ne sais pas si ça mérite vraiment une réponse autre que oui, à force de chercher vraiment très fort à introduire des axiomes aussi forts que possible et aussi proches que possible d'une contradiction, on a fini par en trouver une (repassez quand vous aurez une contradiction dans ZFC), i.e., je ne sais pas si l'existence d'un cardinal Reinhardt a sérieusement été avancée comme « vraie ». Cela n'a pas empêché de très grands théoriciens des ensembles (je pense à Hugh Woodin) de se livrer à une analyse mathématique et philosophique approfondie de pourquoi cette contradiction et ce qu'elle signifie sur la taille de l'infini — voir par exemple l'article de Woodin intitulé The Realm of the Infinite — et voir d'ailleurs aussi les commentaires et explications de Peter Koellner sur ce texte. En tout état de cause, cette histoire va plutôt dans le sens que quand on trouve une contradiction dans la théorie des ensembles, elle n'est pas spécialement difficile à exhiber (la preuve de la contradiction de ZFC + « il existe un cardinal Reinhardt » a été trouvée rapidement, et elle n'est ni longue ni très subtile), donc j'ai tendance à croire que savoir jusqu'où on a pu aller trop loin donne plutôt confiance en la solidité de l'édifice. (Alternativement, on peut défendre la thèse que la contradiction ne vient pas du grand cardinal supposé mais de l'axiome du choix qui limiterait la taille possible de l'infini, comme l'axiome de constructibilité place la limite beaucoup plus bas — en-dessous d'un cardinal mesurable.)

Mais il est vrai que tous ces concepts fleurent bon la contradiction tant ils semblent jouer avec elle et tourner autour d'elle en l'évitant tout juste. C'est le cas de façon générale de la logique mathématique (le théorème de Gödel s'approche dangereusement du paradoxe de la phrase qui dit cette phrase est fausse, et nous invite à contempler attentivement la différence entre vérité et démontrabilité — j'ai écrit de la vulgarisation à ce sujet ici), mais quand on ajoute les infinis dans l'histoire et la difficulté à se les imaginer intuitivement, on comprend que certains ne se sentent pas du tout à l'aise. Pour en revenir à mon propos initial, je pense que c'est justement pour cela que, une fois admis que le sujet n'est pas contradictoire, on le trouve d'autant plus stimulant. Arriver à suivre certains raisonnements en logique ou théorie des ensembles, bien plus que dans d'autres branches des mathématiques, peut être comparable à un roman policier où tout le monde réussit à tromper le détective tout en disant la plus stricte vérité.

Une conséquence de la construction des ordinaux (que ce soit celle de Cantor ou celle, plus précise, de von Neumann), est qu'on ne peut jamais en contempler la totalité : parler de la totalité des ordinaux contredit immédiatement le principe même de construction des ordinaux, puisque cette totalité devrait s'exposer immédiatement à définir un nouvel ordinal plus grand qu'eux (dans la construction de von Neumann : l'ensemble de tous les ordinaux), ce qui définit un nouvel ordinal, contredisant la totalité de la totalité supposée ! C'est là essentiellement le paradoxe de Burali-Forti. La résolution moderne technique est que les ordinaux ne forment en effet pas un ensemble, ils ne sont pas regroupables en ensemble — si on veut donner un nom à tous les ordinaux, ce sera une classe — et la construction des ordinaux ne s'applique qu'aux ensembles. Mais le contenu intuitif de cette explication technique est le suivant : on ne peut en effet jamais contempler la totalité des ordinaux, il faut donc décider d'arrêter de les construire à un certain moment (mais il vaut mieux choisir un moment raisonnablement « robuste », et c'est essentiellement cela que permettent les axiomes de la théorie des ensembles), après quoi l'ordinal qui vient immédiatement après s'appelle la classe des ordinaux et on fait semblant que ce n'est pas un ordinal, pas plus que ceux qui viendraient après ; des propriétés plus ou moins compliquées, ajoutées sous forme d'axiomes, permettent de décider jusqu'où on impose d'aller dans la construction des ordinaux. Bref, on a effectivement affaire à quelque chose qui n'est jamais achevé, qui ne peut jamais l'être par sa définition même, il faut juste décider à quel moment on a quelque chose de « suffisamment achevé », i.e., robuste, pour ce qu'on veut en faire. Là aussi, il s'agit d'une perspective extrêmement dérangeante, et donc d'autant plus fascinante quand on arrive à l'accepter mentalement : quand on dit les ordinaux, il y a toujours quelque chose d'inachevé dans l'histoire. Et en fait, quand on examine de plus près la logique, on se rend compte, et je vais essayer d'en dire un mot plus bas même si c'est un peu complexe, que cet « inachèvement » ne concerne pas que la notion de tous les ordinaux mais même des ordinaux bien précis, disons ω₁ ou même ωCK (voire ω ?), ce qui rend tout le panorama encore plus mystérieux.

Dans ces conditions, il ne me surprend pas que Cantor soit devenu mystique. Une rumeur persistante veut qu'il ait été fou, ce qui va certainement dans le sens de démolir ad hominem ses théories : la vérité est surtout qu'il a souffert de dépression, notamment à cause du rejet de ses idées. Mais il est vrai qu'il a été habité d'idées tout à fait mystiques, comme l'affirmation que c'était Dieu qui lui avait inspiré l'idée des nombres transfinis, et que leur existence (actuelle et non simplement potentielle) apportait une lumière sur l'existence ou sur la pensée de Dieu. Et il a écrit plusieurs lettres à des prêtres catholiques, dont le pape Léon XIII, au sujet de théologie et de rapports entre théologie et mathématiques. Même Hilbert utilise le terme de paradis (Paradies) pour décrire le monde de la théorie des ensembles ouvert par Cantor, avec ses infinis et ses raisonnements non-constructifs, et ce n'est certainement pas un hasard. Moi-même je ne peux que plaider coupable en ce qui concerne le mysticisme (même si, je l'ai déjà expliqué, pour moi le mysticisme est avant tout intéressant artistiquement, par exemple comme prémisse pour une œuvre littéraire) : ma fascination pour les ordinaux a indiscutablement une origine à peu près mystique, et quand je propose une interprétation eschatologique du paradis cantorien (encore une fois, la Théorie de la Totalité Transfinie de Turing), c'est du mysticisme à 0.02¤ (voire à (1/ω).

Mais c'est là que je veux, pour expliquer le mécanisme psychologique qui joue, rejoindre le mot que j'ai utilisé plus haut : grandeur. J'ai déjà dit que je fais souvent des rêves de vastes labyrinthes à explorer et j'ai déjà comparé les mathématiques à un palais magnifique et extraordinairement beau en même temps que labyrinthique : si la symétrie est ce qui fait la beauté du palais, la grandeur joue beaucoup pour qu'on ait envie de l'explorer. Les ordinaux sont le terrain de jeu ultime pour ce qui est de la grandeur, et comme un gosse qui découvre un nouveau terrain d'aventure, j'ai envie de m'y lancer.

Or ce terrain est déroutant. Un peu à la façon de l'ensemble de Mandelbrot (autre vaste terrain de jeu à explorer, dont j'ai fait une petite démonstration artistique à travers plusieurs vidéos parmi tant d'autres trouvables sur le sujet sur YouTube), les ordinaux ont une structure que j'ai envie de qualifier de fractale, même si je ne saurais pas justifier précisément le sens mathématique de ce mot. Grosso modo, je veux dire que si on comprend comment sont fabriqués les entiers naturels (i.e., ω), on recommence tout ceci pour passer de ω à ω+ω = ω·2, puis de nouveau pour passer à ω·3, et toutes ces répétitions sont elles-mêmes répétées ω fois pour fabriquer ω², et tout ça est encore fait ω fois pour fabriquer ω³, et ainsi de suite : non seulement chaque ordinal est l'ensemble des ordinaux qui précèdent mais aussi chaque construction permettant de fabriquer des ordinaux est répétée de façon de plus en plus complexe, de plus en plus imbriquée et de plus en plus délicate pour fabriquer des ordinaux plus grands. Les images présentées par mon petit navigateur d'ordinaux ne sont qu'un pâle reflet de cette structure fractale qui m'évoque la façon dont l'ensemble de Mandelbrot se retrouve partout dans l'ensemble de Mandelbrot (je répète que ceci n'est pas censé être une affirmation mathématique mais une impression psychologique). J'ai le souvenir d'avoir fait un rêve, évidemment impossible à raconter dans lequel on me montre ω₁ (dans le rêve, on me disait ℵ₁, mais c'est la même chose), qui prend en l'occurrence la forme d'une sorte de sculpture moitié gothique, moitié sarrasine et semble l'œuvre fantastique des Sylphes, des Fées, des Génies et des Gnomes réunis (avec mes excuses à E. A. Poe).

Les ordinaux, aussi, sont liés de façon profonde à l'univers constructible de Gödel : la vulgarisation que j'ai tenté d'en faire dans cette entrée passée est assez mauvaise, je trouve, et je ne vais pas tenter de l'améliorer maintenant, mais disons juste ceci. De façon orthodoxe, les mathématiques sont fondées sur la théorie des ensembles, c'est-à-dire que tout objet mathématique « est » un ensemble (un peu de la manière dont les objets informatiques « sont » des suites de 0 et de 1 : pour passer de la sémantique qu'on veut donner à l'objet à cette représentation « de bas niveau », il y a une étape de codage qu'on s'empresse d'oublier quand on a développé les outils pour travailler « à haut niveau » sur l'objet). Mais si on croit à l'« axiome de constructibilité », alors en fait on pourrait tout coder sous forme d'ordinaux (et axiomatiser les mathématiques pour parler uniquement d'ordinaux, sans passer par les ensembles : je ne crois pas que quiconque l'ait fait explicitement). Cet axiome de constructibilité a des conséquences mathématiques tangibles (j'en ai cité quelques unes dans l'entrée évoquée ci-dessus), mais généralement parlant on peut quand même l'ignorer : si on est prêt à l'admettre, on peut dire que tout le monde mathématique est formé d'ordinaux plutôt que d'ensembles. Mais l'axiome de constructibilité est aussi intimement lié à la notion de calculs sur les ordinaux. (Il faut toujours que j'écrive une entrée pour expliquer comment on peut définir la calculabilité sur des ordinaux et programmer des ordinateurs transfinis qui les manipulent, mais j'ai au moins donné une formulation équivalente à la première étape intéressante de cette hiérarchie en parlant de machines hyperarithmétiques.) Si on croit à cet axiome[#3], donc, non seulement le monde mathématique devient peuplé d'ordinaux, mais il devient « opérationnel », comme formé de programmes tournant sur des ordinateurs inimaginablement puissants, ou plutôt sur des séquences transfinis d'ordinateurs de plus en plus puissants. La description que je viens de faire est plus métaphorique que scientifique, bien sûr, mais elle est destinée à expliquer pourquoi l'univers constructible me fascine, et comment cela se relie aux ordinaux : je ne peux pas rester insensible à cette vision du monde mathématique comme une gigantesque machine de calcul.

[#3] En fait, on ne croit pas à cet axiome V=L, ou du moins, les théoriciens des ensembles assez « platoniciens » pour avoir un avis sur la question (de savoir si un énoncé indécidable dans ZFC peut avoir une valeur de vérité) croient essentiellement tous qu'il est faux, parce qu'il limite la taille de l'infini. (Ceci dit, je ne sais pas pourquoi on n'applique pas la même logique pour conclure que l'axiome du choix est faux, cf. ma note précédente.) À la place, on cherche à trouver un remplacement de L qui assure aussi une structure forte et ordonnée de l'univers des ensembles et qui soit compatible avec les plus grands cardinaux : c'est ce qu'on appelle le core model program (ou inner model program, je ne sais pas dans quelle mesure c'est synonyme) ; de ce que je comprends, on sait définir des analogues de L pour certains grands cardinaux, mais la question cruciale est de savoir si on peut atteindre un cardinal supercompact, parce que si on y arrive, le modèle en question peut rendre compte de tous les grands cardinaux (même ceux qui sont beaucoup plus grands/forts qu'un cardinal supercompact) et Woodin appelle ça le L ultime. Maintenant, je ne sais pas dans quelle mesure ce « modèle-cœur » peut être considéré sous l'angle de la calculabilité (il est vrai que 0 est une sorte de super-giga-saut-de-Turing, donc ça pourrait le laisser croire) ; j'ai plusieurs fois fait des timides tentatives pour essayer d'apprendre ce sujet, mais il est invraisemblablement technique (il y a des souris, des présouris, des protosouris, des phalanges, des belettes, et même des belettes stablement universelles ! — je ne plaisante pas, regardez cet article). Pour un survey sur la question, on pourra par exemple se tourner vers le texte de Woodin, Strong Axioms of Infinity and the search for V.

Mais revenons aux ordinaux eux-mêmes. Ce qui est décevant, c'est que ce monde est tellement vaste qu'on ne peut en explorer qu'une infinitésimale partie. J'aime bien donner l'image de ω₁ comme un escalier littéralement interminable : même si vous avez le pouvoir de vous déplacer en un temps aussi court que vous voulez à n'importe quel échelon de l'escalier, et même si vous avez un temps infiniment long pour monter, il y aura toujours un échelon que vous n'atteindrez pas. (Alors que pour les entiers naturels, on peut passer une seconde sur le premier échelon, ½ seconde sur le suivant, ¼ sur le suivant et ainsi de suite, et donc franchir tous les entiers naturels en deux secondes.)

Le premier endroit où j'ai appris un peu sérieusement ce que sont les ordinaux, c'est dans le joli petit livre Naïve Set Theory de Halmos, que mon papa m'avait prêté. Comme la plupart des gens qui entendent parler des ordinaux pour la première fois, mon intuition a buté contre ε₀ (la limite de ω, ωω, ωωω, etc.), mais comme le sujet me titillait, j'ai insisté jusqu'à comprendre correctement cet ordinal, c'est-à-dire, redécouvrir par moi-même ce qui est essentiellement la forme normale de Cantor ; puis j'ai poussé jusqu'à comprendre ε₁ (la principale difficulté est de réussir à se désembrouiller des différentes expressions comme εε = ωωε₀·2), et j'ai extrapolé en me disant que du coup je comprenais εγ en général. Je me suis ensuite dit que sûrement la limite de ε₀, εε, εεε, etc., devait être ω₁ (Halmos note d'ailleurs ce dernier, de façon un peu vieillote, Ω), et que du coup j'avais compris les ordinaux dénombrables, ouf ! Ce n'est que plus tard que je me suis aperçu de mon erreur : la limite de ε₀, εε, εεε, etc. ne peut pas être ω₁, parce que ωne peut pas être obtenu comme limite d'une suite d'ordinaux plus petits (c'est ce que j'essaie de dire dans le paragraphe précédent) : toute suite à valeurs dans ω₁ est bornée ! J'ai alors eu un vertige en comprenant à quel point ω₁ est impossible à appréhender — et ce n'est que le premier cardinal après ω !

Mais ce qui est surtout décevant, c'est que les mathématiques elles-mêmes sous-utilisent les ordinaux. De façon basique, si on regarde les ordinaux (dénombrables, pour éviter des discussions oiseuses) utilisés dans des constructions ou démonstrations mathématiques en-dehors de la théorie des ensembles elle-même, on s'aperçoit qu'ils ont tendance à ne pas être très grands. Pour être plus précis : il existe une branche des mathématiques appelée théorie de la démonstration, dont une sous-branche appelée analyse ordinale s'attache à attribuer à une théorie mathématique (comme les axiomes de Peano) un certain ordinal (dénombrable et même « récursif ») qui mesure sa force (je vais rester insupportablement vague, mais la force de l'arithmétique de Peano est essentiellement mesurée par l'ordinal ε₀) ; en quelque sorte, cela signifie que la théorie n'est pas capable d'« utiliser » un ordinal plus grand, ou de façon un tout petit peu moins vague, de formaliser une induction transfinie (sorte de généralisation de la récurrence) sur cet ordinal ou un ordinal plus grand quelconque. Dans le cas de la théorie des ensembles, cet ordinal est extrêmement grand (quoique plus petit que ωCK) et on ne sait pas le décrire autrement que l'ordinal qui mesure la force de ZFC. Mais un consensus des logiciens est qu'essentiellement toutes les mathématiques usuelles peuvent se faire dans des théories logiques dont la force (mesurée par un ordinal comme je viens de le dire) est finalement très petite : ε₀ ou même peut-être ωω voire moins (voir par exemple le papier Number Theory and Elementary Arithmetic de Jeremy Avigad pour un énoncé précis). Ce que cela signifie concrètement est que : les mathématiques ne savent pas vraiment utiliser les ordinaux très puissants qu'elles définissent (ni toute la force de la théorie des ensembles, loin de là). Ceci m'amène évidemment à me demander ce que seraient les mathématiques si nous pouvions/savions réellement faire usage des ordinaux plus grands (que nous pouvons décrire et discuter mais sans les « comprendre » ou les « utiliser » en profondeur) ; le petit indice que nous pouvons tirer des quelques théorèmes (comme celui-ci) dont la force logique qui dépassent la « force usuelle » des mathématiques, suggère que ce serait certainement intéressant.

J'ai commencé cette entrée en rappelant ma fascination pour la symétrie. Les ordinaux sont tout le contraire de symétriques : ils sont rigides (il n'y aucune façon de changer l'ordre des éléments — c'est-à-dire des ordinaux plus petits — d'un ordinal, parce que le plus petit est identifié comme le plus petit, le suivant est identifié comme le suivant après lui, et ainsi de suite ; pour ceux qui veulent un théorème précis : tout ensemble bien-ordonné est isomorphe à un unique ordinal, et l'isomorphisme est lui-même unique). Il faut un jour que j'écrive une entrée sur la question semi-mathématique et semi-philosophique de savoir quand deux objets mathématiques sont le même et de pourquoi les symétries posent problème dans ce contexte[#4], toujours est-il que pour les ordinaux, cette question ne doit pas se poser : l'ordinal ω, par exemple, qui est le plus petit infini, est le même pour tout le monde, et l'ordinal ω₁, qui est le plus petit indénombrable, devrait aussi l'être (devrait, parce qu'il y a des mentions légales auxquelles je viens dans un instant). En un certain sens, c'est mentalement rassurant : si nous devions parler d'ordinaux avec des extra-terrestres, la question de savoir si nous parlons du même ordinal a un sens parfaitement bien défini, pas comme si nous parlions de gauche et de droite où se posent toutes sortes de questions, à cause de l'existence de symétries (les réflexions de l'espace) sur l'orientation de l'espace et comment savoir si gauche et droite ont le même sens pour nous et pour eux.

[#4] Digression (technique) à ce sujet : il y a des gens qui insistent (et ils ont sans doute raison…) sur le fait qu'on doit écrire une clôture algébrique du corps k et non la clôture algébrique du corps k, parce que la clôture algébrique n'est définie qu'à isomorphisme non-unique près. (Un cas frappant est celui de ℚ : on en fabrique une clôture algébrique en le plongeant dans ℂ, c'est-à-dire en considérant les nombres complexes qui sont racine d'un polynôme à coefficients rationnels ; mais on en fabrique une autre clôture algébrique en le plongeant dans ℂp pour chaque nombre premier p, c'est-à-dire en utilisant une construction du même style sur les p-adiques — on peut la rendre tout à fait explicite, je ne rentre pas dans les détails : mon point est qu'on obtient des présentations très différentes de clôtures algébriques de ℚ, et bien qu'il existe un isomorphisme entre les deux même en l'absence de l'axiome du choix, cet isomorphisme n'est pas du tout explicite.) D'un autre côté, on parle bien du corps des nombres complexes, alors qu'il n'est défini, même sur les réels, qu'à un isomorphisme près qui peut prendre deux valeurs possibles (conjuguées complexes l'une de l'autre), et j'ai tendance à trouver que pour ce qui est de la clôture algébrique d'un corps fini il est également légitime de dire la. Tout ceci est donc un peu délicat, parce qu'est délicate, à la base, la question de savoir de quelles structures on dote un objet mathématique. (Je sais que V. Voevodsky est censé résoudre toutes ces difficultés grâce aux merveilles de la théorie homotopique des types, mais moi je ne suis qu'un vulgaire algébriste aux sympathies pour la logique classique et qui continue à croire bêtement que ZFC est consistant et à travailler dedans, du coup ces merveilles m'échappent.)

Mais en fait il y a une subtilité, c'est que s'il n'y a pas de symétries dans le monde des ordinaux, il y a des « fausses symétries », ce que j'avais appelé dans mon entrée consacrée à la constructibilité, un « jeu de miroir » : il y a des ordinaux qui « font semblant » d'être d'autres ordinaux ou d'être la classe de tous les ordinaux ! Il est difficile d'expliquer ce que cela veut dire au juste. (Pour ceux qui connaissent la théorie des ensembles, je fais référence à des choses dans le style de Löwenheim-Skolem : notamment, au fait que Lα peut être un sous-modèle élémentaire ou un sous-k-modèle élémentaire d'un autre, voire un sous-k-modèle élémentaire de L tout entier, ou encore, peut vérifier un bon bout des axiomes de la théorie des ensembles ; ou éventuellement les mêmes choses avec V à la place de L, même si j'ai plutôt L que V à l'esprit.) Mais disons en gros qu'il y a toutes sortes de manières dont l'ensemble des ordinaux inférieurs à un certain α (c'est-à-dire, selon la définition des ordinaux à la von Neumann, α lui-même…) peut ressembler à l'ensemble des ordinaux inférieurs à un certain β>α quand on ne regarde pas de trop près (et « pas de trop près » a tendance à être lui-même quantifié par un autre ordinal). Par exemple, il y a toutes sortes d'ordinaux qui vont donner temporairement l'impression (plus ou moins fortement convaincante) d'être ω₁, puis, quand on va un peu plus loin, on va se rendre compte qu'en fait, non, ce n'est pas ω₁. (Il est difficile de donner ne serait-ce qu'une idée de ce qui se passe au juste, mais pour proposer un début de commencement d'embryon d'idée, on peut penser au fait que ε₀ et ε₁, ou tous les ε en général, sont essentiellement impossibles à distinguer quand on regarde les ordinaux plus petits et qu'on se permet seulement de faire des additions, multiplications et exponentiations — parce que l'ordinal qui est au-dessus est inatteignable par ces opérations ; je peux aussi évoquer le fait que ωCK fait un peu semblant[#5] d'être ω₁, d'où le nom, en ce que toute suite d'ordinaux à valeurs dans ω₁ est bornée, tandis que la même chose est vraie pour une suite récursive dans ωCK.) Tout ce phénomène est assez subtil et assez labyrinthique, et assez déstabilisant, mais en même temps intellectuellement fascinant : le monde des ordinaux, que je qualifiais de fractal ci-dessus, contient en effet des copies de lui-même en miniature, des copies de qualité arbitrairement précise, dans un « jeu de miroir » vertigineux.

Et cela pose des questions à mes yeux profondes de philosophie des mathématiques : vu qu'il y a toutes sortes d'ordinaux qui se succèdent pour « faire semblant » d'être ω₁, on se demande si le vrai ω₁ existe « vraiment », et ce que cette question veut dire. Ou peut-être que ω₁ est quelque chose comme la classe de tous les ordinaux : quelque chose de perpétuellement inachevé, qu'on n'en finit pas de compléter. (Pour ceux qui en savent plus, voici le genre de phénomènes auxquels je pense : s'il existe un modèle bien-fondé de ZFC, il existe un plus petit modèle transitif dénombrable M de ZFC, et l'ordinal ωM qui joue le rôle de ω₁ dans ce modèle est un « faux » ω₁ puisqu'il est dénombrable ; formellement, on passe de ωM à ω₁ en ajoutant ω₁ échelons à la fin, mais il est sans doute plus juste de s'imaginer qu'on les ajoute à toutes sortes d'endroits au milieu parce qu'on a mieux regardé ωM et qu'on s'est dit il y a un trou là, là et là. Une extension de forcing sur M peut écraser ωM, et, selon le point de vue qu'on adopte, le rendre dénombrable, ou exhiber le fait qu'il l'était dès le début, sans que l'ordinal lui-même change.) Et le problème philosophique devient encore plus épineux quand on commence à se demander quel est le plus petit ordinal qui peut se permettre d'être inachevé (ce n'est certainement pas 42 : je crois quand même que s'il manquait un nombre entre 0 et 41, quelqu'un s'en serait aperçu ! 😉), et ce que cette question veut dire. Malheureusement, les philosophes se sont assez peu penchés sur ces problèmes, ni les mathématiciens, ni même ceux qui ont la double casquette (comme Hugh Woodin dont je parlais plus haut, ou Hilary Putnam, qui a pourtant étudié des problèmes remarquablement proches ; il y a bien Joel D. Hamkins — un ancien étudiant de Woodin — qui a beaucoup dit des choses sur la conception « multivers » de la vérité ensembliste, mais son point de vue est un peu différent, je ne rentre pas dans les détails).

[#5] Il y aussi le phénomène suivant : j'ai déjà évoqué, par exemple dans cette entrée (même s'il faudra un jour que j'y revienne plus précisément) qu'il y a des phénomènes de « reflet » pas totalement bien compris entre (0) les grands entiers naturels (i.e., les ordinaux <ω), (1) les grands ordinaux constructifs (i.e., les ordinaux <ωCK), (2) les grands ordinaux dénombrables [dans l'univers constructible] (i.e., les ordinaux <ωL), et (3) les grands cardinaux [qui ont le droit d'exister dans l'univers constructible]. Par exemple, un cardinal inaccessible (dans la catégorie (3)) permet de définir par analogie la notion d'ordinal récursivement inaccessible (dans la catégorie (2)), qui permet à son tour de définir par « écrasement » de très grands ordinaux récursifs (i.e., dans la catégorie (1)) mesurant la force ordinale d'un système formel KPI garantissant l'existence d'ordinaux récursivement inaccessibles, et ceux-ci permettent à leur tour de définir de très grands entiers (essentiellement des valeurs de fonctions calculables dont KPI démontre la terminaison, même si on peut les décrire de façon beaucoup plus explicite grâce à (1)). Le lien entre ces quatre objets est subtil, mais des questions philosophiques qui se posent sont : sachant qu'on n'a pas besoin formellement que (3) existe (l'existence de cardinaux inaccessibles n'est pas démontrable par ZFC) pour que (2) existe, ni (2) pour (1), ni (1) pour (0), mais qu'on en a besoin pour motiver la construction, qu'est-ce que ceci nous apprend sur la plausibilité de l'existence de (3) ? et d'autre part, est-ce que le fait de « trouver » de « nouveaux » ordinaux, voire de nouveaux ordinaux récursifs, voire de nouveaux entiers naturels, par ce procédé, signifie que ω₁, voire ωCK, voire ω, étaient inachevés ?

Comme je m'en doutais, je me suis perdu dans un certain nombre de digressions techniques, mais si je dois synthétiser tout ça en une raison supplémentaire pour laquelle les ordinaux me fascinent, c'est que leur construction a la beauté des fractales (même si cette fractale ne peut se voir qu'avec l'esprit), où des imitations de plus ou moins bonne qualité des ordinaux se retrouvent sans arrêt dans d'autres ordinaux comme des copies de l'ensemble de Mandelbrot dans l'ensemble de Mandelbrot ; mais avec les ordinaux, ces phénomènes deviennent sans cesse plus riches, plus complexes et plus subtils, jusqu'à l'infini et au-delà, de sorte que non seulement l'ensemble est d'une très grande beauté, mais aussi qu'il soulève des problèmes philosophiques profondément troublants si on prend la peine d'y réfléchir soigneusement.

(samedi)

Le cérémonial de la thèse (bis)

J'ai assisté pour la première fois à une soutenance de thèse en lettres. (J'écris lettres au sens large, i.e., par opposition aux sciences : en l'occurrence, il s'agissait d'histoire — et probablement d'archéologie ou d'histoire de l'art, je ne suis pas sûr de la classification exacte, mais le titre était Homère dans la culture romaine entre la fin de la République et la fin de la dynastie julio-claudienne. En fait, je me rends compte, en écrivant ça, que je ne sais même pas dans quelle mesure les doctorats sont officiellement classifiés et étiquetés par disciplines, et le cas échéant quelle est la liste des disciplines possibles : cela ne semble pas suivre, par exemple, la liste des sections du Conseil national des Universités puisque je ne crois pas avoir vu de distinction entre doctorats de mathématiques et doctorats de mathématiques appliquées, et il me semble que la plupart des matheux seraient hostiles à ce qu'il soit pratiqué une telle distinction.)

Toujours est-il que ce fut pour moi (et pour les autres amis de la doctorante venus du milieu universitaire scientifique) de remarquer les différences dans le cérémonial de la thèse entre sciences et lettres — ou du moins, entre les disciplines que j'ai pu observer de part et d'autre.

En sciences, le déroulement d'une thèse en France est à peu près le suivant. L'impétrant fait face au public, debout, et les membres du jury, généralement en nombre autour de 6, prennent place au premier rang face à lui (donc tournés dans le même sens que le public). Le président du jury invite l'impétrant à présenter ses travaux en une quarantaine de minutes. L'exposé porte généralement sur un sous-ensemble des travaux de thèse, afin de pouvoir l'expliquer plus en profondeur (mais il arrive qu'on parle de tout). Il s'appuie le plus souvent sur des transparents (transparents voulant ici en fait dire des pages de PDF affichées par un vidéoprojecteur, mais les véritables transparents projetés par rétroprojecteur n'ont peut-être pas encore totalement disparu) ; en mathématiques, cependant, on préfère encore le tableau noir. Parfois, une courte pause a lieu à la fin de cet exposé, afin que les membres de l'auditoire qui le veulent puissent s'enfuir. • Ensuite viennent les questions du jury : c'est là qu'il y a le plus de différences entre disciplines scientifiques, et j'ai assisté à des soutenances en maths où le jury n'a pas trouvé utile de poser de questions (peut-être aussi était-ce parce que le président du jury était un peu « vieille école »). Mais généralement parlant, chaque membre du jury se croit obligé de poser une question : le président leur donne la parole tour à tour, en commençant typiquement par ceux qui viennent de loin ou par les rapporteurs, et en finissant par le directeur de thèse (qui le plus souvent ne pose pas de vraie question et se contente de dire qu'il a apprécié de travailler avec ce doctorant) et par lui-même. Selon les disciplines, ces questions peuvent être de la pure forme, qu'elles soient complètement cadeau comme que comptez-vous faire maintenant ?, quelles nouvelles directions de recherche voyez-vous après ce travail ?, duquel de vos résultats êtes-vous le plus fier ?, ou posées juste pour dire quelque chose comme comment compareriez-vous votre approche avec celle de Duschmock ?, finalement, après vos travaux, quelle approche conseilleriez-vous pour frobniquer les foobars ? ; ou au contraire elles peuvent être très pointues, voire presque agressives. Les questions durent quelque part entre une demi-heure (voire moins) et une heure et demie. • Puis le jury se retire pour délibérer, c'est-à-dire pour échanger les derniers potins et se rappeler qu'ils doivent écrire un rapport de soutenance. Ce rapport est presque toujours écrit dans un langage très élogieux, même si des petites phrases cachées peuvent, sous une apparence bénigne, trahir le fait que le jury n'était pas satisfait du travail de thèse ou de la soutenance [voir aussi cette entrée récente] : par exemple, si on écrit que le candidat a montré son aptitude à l'enseignement, cela signifie en creux qu'il fera un mauvais chercheur. Après un temps généralement de l'ordre d'une demi-heure ou trois quarts d'heure, le jury revient, le public se lève (pas toujours), le président du jury lit les phrases essentielles du rapport et conclut par quelque chose comme pour ces raisons, nous vous décernons le grade de docteur de foobarologie de l'Université de Paris XLII avec la mention très honorable et nous vous félicitons (beaucoup d'écoles doctorales ne permettent pas de décerner les félicitations du jury, donc à la place, le jury joue sur la sémantique et félicite à titre privé l'impétrant). Enfin, le nouveau lauréat serre la main des membres du jury, dit quelques mots de remerciement et invite tout le monde à passer dans une salle voisine pour un pot bien mérité.

Voici ce que j'ai pu discerner comme différences dans la soutenance, en lettres donc, à laquelle j'ai assisté cet après-midi. Je pourrais commencer, en fait, par remarquer qu'elle a eu lieu un samedi, ce qui serait, je crois, hautement inhabituel en sciences. Mais la raison ne tient peut-être qu'indirectement à la discipline : la doctorante est enseignante dans le secondaire puisque sa thèse a duré bien plus longtemps que les 3 ans réglementaires et financés mais qui, de ce que je comprends, sont presque systématiquement contournés en lettres (après, je ne peux pas jeter la pierre : ma propre thèse a duré environ 5 ans) ; du coup, il lui était sans doute plus difficile de se dégager un autre jour. • Le jury était assis face au public, et l'impétrante face à eux, donc dos au public, également assise. Elle a été invitée par le président du jury à présenter ses travaux, ce qui a duré environ 25 minutes : cet exposé a été fait oralement, sans aucun support visuel ni écrit, et consistait en fait en la lecture d'un résumé, ou plutôt d'un plan modérément détaillé, du mémoire de thèse (lequel fait environ 500 pages, plus une centaine de pages supplémentaire d'annexes). • Ensuite, chaque membre du jury a pris la parole sur l'invitation du président, en commençant par le directeur de thèse et les rapporteurs et en finissant par le président du jury lui-même. Chacun d'eux a parlé environ 25–30 minutes, et comme ils étaient cinq, on en conclut que la soutenance a duré environ trois heures — même s'il y a eu une pause d'un quart d'heure au milieu. À part que le directeur de thèse a commencé par résumer brièvement la carrière de la doctorante, chacune de ces interventions a pris la forme d'un résumé de la thèse (on a donc écouté six résumés différents de la même thèse !) suivi d'une critique sur tel ou tel aspect du travail. • Et, de ce que j'ai pu en juger, les critiques avaient essentiellement toutes la forme votre travail était très bon, sauf dans <le domaine dont je suis spécialiste>, où il aurait dû être plus approfondi, et vous auriez dû faire un plus grand effort de bibliographie, par exemple pour citer Machin. Il y avait bien sûr des différences : un membre du jury a été beaucoup plus sévère que les autres dans son appréciation (votre travail a été trop ambitieux et du coup beaucoup trop superficiel) tandis qu'un autre, qui d'ailleurs n'était pas français, a été très élogieux (votre travail représente une synthèse admirable et fait véritablement avancer notre connaissance) ; et aussi des rapprochements : tous ont apprécié le style de la rédaction, tous ont souligné l'excellente qualité de la partie 3 du travail, et tous ont trouvé les deux premiers chapitres inférieurs au reste. Mais le gros des reproches était quand même de ne pas avoir consulté l'ouvrage de Truc, de ne pas avoir cité Machin ou de ne pas avoir mentionné Bidule. À chaque fois, la réponse de l'impétrante était de remercier pour les remarques et de promettre d'en tenir compte (je n'ai pas compris si en tenir compte signifie que la version officiellement déposée du manuscrit sera modifiée ou si ce sera une version publiée ultérieurement de façon privée). • Enfin, après trois heures de soutenance, le jury s'est retiré pour délibérer, ce qui a pris encore une heure. Mais le résultat de cette délibération était anticlimactique [je ne sais pas dire ça en bon français] au possible : le président a juste dit à l'impétrante qu'on lui décernait le titre (ou le grade ?) de docteur de l'Université de Paris Sorbonne avec la mention très honorable et les félicitations du jury — si rapport en langage codé il y a eu, il ne nous en a pas été donné lecture. (Pour finir, signalons que le pot était à la hauteur des quatre heures d'attente.)

J'aurais pu commencer mon descriptif en amont de la soutenance elle-même : normalement, en sciences, les rapporteurs ne devraient pas avoir de reproches majeurs à faire lors de la soutenance (même si je répète que j'ai donné un contre-exemple), puisque cette soutenance est autorisée sur la base de leurs rapports contre un manuscrit préliminaire, et le manuscrit finalement soutenu doit tenir compte de toutes leurs remarques substantielles. Ici, apparemment, la doctorante n'avait eu le temps que d'écrire quelques errata mais pas de modifier vraiment le manuscrit avant la soutenance.

Toutes ces différences de forme reflètent certainement des différences plus profondes entre la conception même du travail doctoral en sciences et en lettres. Je ne vais pas répéter ce qu'a expliqué mon ami David Monniaux (notamment ici et ) sur le fait que les littéraires ont tendance à considérer qu'un travail de 3 ans est beaucoup trop court pour être véritablement approfondi, et je pense que les remarques du jury sur la bibliographie insuffisante dans le travail dont j'ai assisté à la soutenance sont symptomatiques de cette vision — ce n'est jamais assez complet, jamais assez exhaustif, jamais assez approfondi. Je ne saurais dire si cette différence d'approche est inextricablement liée à la discipline (on pourrait dire qu'en sciences, grossièrement, on construit une démonstration, une théorie bien encadrée, une expérience, tandis qu'en lettres, tout aussi grossièrement, on documente, on structure, on organise : le premier type d'activité se prête mieux à une délimitation finie que le second ; mais tout ceci est peut-être complètement bidon) ; ou s'il s'agit de différences plutôt sociologiques (les remarques faites par le membre britannique du jury étaient beaucoup plus valorisantes que les autres, c'est sans doute le signe d'une différence à ce niveau).

Il serait certainement intéressant de faire une thèse de sociologie sur le cérémonial des soutenances de thèse et la manière dont il varie selon les disciplines, selon les pays (je sais par exemple qu'aux Pays-Bas la tradition est que la soutenance est interrompue au moment où le temps est écoulé — à la seconde près — par quelqu'un qui entre pour mettre fin aux festivités ; dans d'autres pays, il n'y a pas vraiment de soutenance, ou bien il y en a deux, une substantielle devant des chercheurs et une de pure forme devant le public), et selon les époques (je suppose qu'une soutenance de thèse, même en mathématiques et en France, ne prenait pas du tout la même forme en 1815, en 1865, en 1915 et en 1965 que maintenant). Et bien sûr, le cérémonial de la soutenance d'une telle thèse serait lui-même intéressant à observer, parce que tout le monde se sentirait à la fois sujet et objet d'étude !

(lundi)

L'économie de l'attention, et l'information à valeur négative

En principe, une information ne peut pas avoir une valeur négative, à cause de l'argument suivant : on peut toujours l'ignorer ou la jeter. En tirant sur les cheveux, on pourrait même formaliser cet argument en invoquant la logique linéaire, en définissant une information comme un terme A qu'on peut reproduire arbitrairement, y compris le jeter, c'est-à-dire tel que A soit identifiable, ou interconvertible, à !A (la signification intuitive de cette construction de la logique linéaire étant, en gros, autant de fois A que je veux). En pratique, il peut y avoir toutes sortes de raisons pour lesquelles cet argument échoue (essentiellement parce que l'information dont on parle n'est jamais une pure information, il y a toujours, au minimum, la nécessité de la stocker et/ou de la transférer et/ou de la traiter), et l'information peut se retrouver à ressembler à un objet encombrant dont il coûte de se débarrasser ou qu'il est problématique de recevoir.

Si on parle de l'aspect social de la chose, je pense que le nom raisonnable qu'on pourrait donner au coût associé à la réception d'une information est l'attention dont il faut faire preuve en échange (i.e., le temps mental pour recevoir et comprendre cette information, ou au moins pour la classifier comme (in)intéressante). Une information à valeur négative est donc en fait une information dont la valeur intrinsèque (positive mais essentiellement nulle) est inférieure au coût en attention (positif et petit, mais légèrement plus grand) associé à sa réception. Généralement, l'idée est que l'émetteur tire un gain du fait que certaines personnes reçoivent cette information, et probablement cette information sera positive pour ces destinataires particuliers, mais comme l'émetteur ne peut pas ou ne veut pas cibler plus particulièrement le récepteur, la valeur moyenne sur l'ensemble des récepteurs peut être négative pour eux.

Vous allez me dire, j'ai expliqué de façon incroyablement pédante ce qu'est une publicité. ☺

C'est un peu ça. Mais en fait, la notion dépasse largement le cadre commercial de la publicité, et je pense qu'on gagne à y réfléchir en ces termes plus généraux. La ressource précieuse sur Internet n'est généralement pas l'information, c'est l'attention des internautes : et cette idée a été développée dans le concept de l'économie de l'attention. Je ne prétends pas que l'information ne soit jamais, ni même rarement, le facteur limitant, mais personnellement je me trouve plus souvent dans la situation où je suis face à plus d'information que je ne pourrais en comprendre, analyser ou consommer, et c'est donc mon temps qui devient la quantité précieuse à rationner (ou en tout cas, à utiliser le plus efficacement possible, quitte à pratiquer la lecture en diagonale) ; le lien entre ces deux situations est généralement fourni par la méta-information qui consiste à isoler l'information la plus importante dans le tas (et l'attention consiste essentiellement à consommer du temps pour produire cette méta-information précieuse).

Le cadre commercial, essentiellement celui de la publicité, est évidemment important, et Facebook, Google et d'autres vendent essentiellement cette denrée dont ils sont devenus les dealers. Mais même en-dehors du cadre commercial, l'attention continue à être précieuse, par exemple pour des raisons de statut social. Ce phénomène est illustré dans toute sa splendeur par le site d'échange de liens Reddit, dont le principe est que tous les utilisateurs peuvent poster des liens ou des textes (catégorisés par subreddit) sur lesquels les autres utilisateurs pourront voter, faisant monter ou descendre ces posts dans le classement (de la page principale ou de la page d'un subreddit), leur faisant ainsi gagner ou perdre de la visibilité, en même temps que l'auteur du lien ou du texte gagne ou perd des points virtuels appelés karma et qui déterminent ipso facto une sorte de statut social sur Reddit. L'attention portée à un post sur Reddit se convertit dans le score du post, qui lui permet à son tour de gagner de l'attention : j'ai déjà parlé du fait que le succès dans toutes sortes de matières est bien plus dû à un effet « boule de neige » (aléatoire et non reproductible), c'est-à-dire à l'auto-entraînement du succès, qu'aux vertus intrinsèques de l'objet ou de l'idée qui a du succès, mais Reddit en est probablement l'exemple le plus parfait : ce qui permet véritablement à un post d'avoir du succès, ce n'est pas tant son intérêt que l'attention qui lui est portée, qui vient elle-même du succès auprès des premiers utilisateurs qui le lisent. Et la même chose se produit au niveau des utilisateurs : celui qui poste des liens haut placés aura d'autant plus de chances que d'autres utilisateurs se mettent à le suivre, et donc à donner de l'attention à ses prochains posts[#]. La dynamique de Twitter (que je ne connais qu'indirectement puisque je n'y ai pas de compte) est sans doute essentiellement la même, avec des petites variations : pas de score ou de karma, mais la possibilité de retweeter et un système de suivi plus formalisé que sur Reddit. Le succès de ces sites eux-mêmes obéit à un effet boule de neige d'accumulation de l'attention (je n'ai pas d'exemple évident pour Reddit ou Twitter, mais Facebook a été précédé, je l'ai déjà raconté à diverses reprises, par des sites dont la fonctionnalité était exactement la même et qui n'ont simplement pas eu l'attention initiale pour démarrer la boule de neige, sans doute parce qu'ils ne sont pas venus précisément au bon moment), mais on rejoint ici bien sûr l'aspect complètement commercial.

[#] Une affaire qui illustre à merveille le ridicule de la situation est le cas de /r/Unidan, raconté ici par exemple. À la fois la manière dont il a agi pour avoir plus de karma (ou l'attention qui va avec) et la réaction des autres utilisateurs quand la « tricherie »(?) a été découverte, sont très révélateurs de la façon dont on traite l'attention comme une valeur précieuse.

Même en-dehors des situations où elle fait boule de neige, l'attention est souvent en situation de demande. Même si ce blog me sert essentiellement (cf. notamment ici) de bloc-notes pour pouvoir écrire ce que j'ai compris sur un certain sujet et l'oublier ensuite en sachant que je pourrai le relire plus tard, je ne peux pas prétendre que le fait d'avoir des lecteurs me soit totalement indifférent : pour commencer, si tel était le cas, je ne publierais pas ces textes, et en tout cas je n'aurais pas de système de commentaires. Il m'arrive d'ailleurs d'essayer de faire de la publicité pour une entrée, de me dire que je vais écrire ceci ou cela pour capter l'attention du lecteur auquel je suis, au final, en train d'essayer de revendre des idées (par exemple, quand je parle de machines hyperarithmétiques, j'essaie assurément de vendre l'idée que ces machines sont dignes d'intérêt et donc d'attention — et ensuite, je suis déçu du manque de succès). Et inversement, sur le système de commentaires d'un blog quelconque, on voit presque toujours bien plus de commentaires exprimant des idées complémentaires que posant des questions : ils sont donc là pour demander de l'attention plus que de l'information. On recoupe ici l'idée du « mème égoïste », l'information qui essaie de se reproduire autant que possible en colonisant de nouveaux nootopes (le nootope étant au mème et à l'information ce que le biotope est au gène et à l'être vivant : donc en pratique, un cerveau, un site Web, ou quelque chose de ce genre).

En déviant vers une problématique plus large, si je considère l'ensemble des emails que j'échange, je constate que dans la grande majorité des cas, qu'il s'agisse des courriers que j'ai reçus ou envoyés, l'émetteur est en un certain sens « demandeur ». (Il est vrai qu'on dépasse ici le cadre de ce que je discutais avant : parfois l'émetteur est demandeur d'information, mais dans tous les cas il est demandeur d'attention.) Ou, pour dire les choses autrement : la grande majorité des courriers que je reçois m'apportent une forme de désagrément, même quand il ne s'agit pas de spams (il faudra faire quelque chose, ou au moins faire attention à quelque chose). Et je connais peu de gens qui se désolent d'en recevoir trop peu. Même s'agissant d'un téléphone mobile, j'avais été frappé quand on m'avait fait cette réflexion : qu'en avoir un (au moins dans sa fonction de téléphone) sert plus à rendre service aux autres qu'au propriétaire du mobile — on rend service en étant disponible à tout moment, c'est-à-dire, en permettant qu'on se saisisse de votre attention. Enfin, c'est une évidence que plus une personne est célèbre, et donc plus son attention a de la valeur, plus elle sera sollicitée par tous les canaux de communication possibles.

Je rejoins ici certaines des idées de mon collègue Jean-Louis Dessalles sur l'évolution du langage, du moins telles que je les comprends (s'il y a quelque chose d'intelligent dans ce que je raconte, c'est sans doute de lui que ça vient, et s'il y a quelque chose de stupide, c'est sans doute ma propre invention) : quand on se penche sur la question de pourquoi nous parlons, on se rend compte que l'histoire est beaucoup plus complexe que communiquer de l'information, et en tout cas, la thèse selon laquelle la communication serait altruiste (l'émetteur offrant généreusement de l'information au récepteur, générosité qu'on pourrait ensuite expliquer biologiquement) ne tient pas debout, ou du moins, ne suffit pas : on est inévitablement amené à conclure que l'émetteur tire quelque chose du fait de communiquer, et il faut analyser ce « quelque chose » — par exemple comme la réception d'un certain statut social qui va avec l'attention d'autrui.

Merci de votre attention. 😁

(dimanche)

Est-il toujours rationnel d'être rationnel ?

Lorsque — au hasard — un attentat terroriste frappe un pays, il est suivi d'une déferlante de débats et discussions sur ce qu'on aurait pu ou dû faire pour l'éviter. Des experts qui prêchent ordinairement dans le désert aux hommes politiques cherchant à tout prix à suivre le sens du vent du jour, tout le monde a un avis à donner : on doit faire la guerre aux terroristes, ou au contraire on ne doit pas tomber dans le piège du conflit de civilisations où ils veulent justement nous entraîner ; on doit les assécher financièrement ; on doit s'allier avec la Bordurie, ou au contraire avec la Syldavie ; on doit augmenter les pouvoirs de la police, on doit interdire la cryptographie, on doit surveiller Internet, on doit protéger nos libertés, on doit, on doit, on doit…

Mais je n'entends essentiellement personne tenir la thèse qu'on devrait faire exactement ceci :

rien

— rien, c'est-à-dire pleurer les morts, se moquer des extrémistes, refuser de se laisser terroriser, reprendre les fils de la vie qui n'ont pas été brisés, et ensuite admettre que l'événement se reproduira certainement et qu'on ne peut pas forcément y faire quelque chose. La plupart des fléaux qui touchent l'homme ont ceci en commun : que si on peut parfois y faire quelque chose, ce quelque chose est très difficile, nécessite un travail très long et au résultat incertain, et surtout, qui doit être mené bien en amont du moment où le fléau frappe — il ne faut pas espérer une solution facile.

Dans les mots passablement gnomiques d'un célèbre romancier français :

Il y a eu dans le monde autant de pestes que de guerres. Et pourtant pestes et guerres trouvent les gens toujours aussi dépourvus. […] Quand une guerre éclate, les gens disent : Ça ne durera pas, c'est trop bête. Et sans doute une guerre est certainement trop bête, mais cela ne l'empêche pas de durer. La bêtise insiste toujours, on s'en apercevrait si l'on ne pensait pas toujours à soi. Nos concitoyens à cet égard étaient comme tout le monde, ils pensaient à eux-mêmes, autrement dit ils étaient humanistes : ils ne croyaient pas aux fléaux. Le fléau n'est pas à la mesure de l'homme, on se dit donc que le fléau est irréel, c'est un mauvais rêve qui va passer. Mais il ne passe pas toujours et, de mauvais rêve en mauvais rêve, ce sont les hommes qui passent, et les humanistes en premier lieu, parce qu'ils n'ont pas pris leurs précautions. Nos concitoyens n'étaient pas plus coupables que d'autres, ils oubliaient d'être modestes, voilà tout, et ils pensaient que tout était encore possible pour eux, ce qui supposait que les fléaux étaient impossibles. Ils continuaient de faire des affaires, ils préparaient des voyages et ils avaient des opinions. […] Ils se croyaient libres et personne ne sera jamais libre tant qu'il y aura des fléaux.

— Albert Camus, La Peste

Pour être bien clair, je ne prends pas spécialement parti pour l'inaction, ni en général ni dans un cas précis. La seule chose dont je suis certain, c'est qu'il ne faut pas agir de façon précipitée ou irréfléchie en géopolitique, pour les raisons que Jon Stewart résumait de façon hilarante dans cette séquence du Daily Show (America in the Middle East — Learning Curves Are for Pussies, 2015-02-06, durée 9′29″). Ça ne signifie pas qu'on ne doive jamais rien faire. Mais avant de se demander quoi faire, il est opportun de se demander si on doit vraiment faire quelque chose, ou simplement admettre le contraire comme une option à envisager et à comparer : il serait donc opportun d'écouter ce qu'on peut dire pour défendre cette thèse.

Car avant de s'élancer gaiement sur un chemin tout pavé de bonnes intentions, il faut écouter la voix sévère et rébarbative de la rationalité utilitariste. Qui nous dit essentiellement que nous devons traiter en priorité les problèmes pour lesquels on peut le plus efficacement sauver des vies (ou minimiser le malheur, ou autres variations selon la fonction d'utilité précise qu'on prétend maximiser) : et qu'avant de dépenser des efforts ou des euros pour lutter contre tel ou tel problème il faut se demander si ces efforts et ces euros, quelle que soit leur source, ne pourraient pas être investis plus utilement (toujours selon la fonction d'utilité qu'on s'est fixée) dans une autre action, ou pour la résolution d'un autre problème.

Cette voix est assurément déplaisante à entendre. Nous aimons tous tenir les opinions contradictoires que toutes les vies humaines sont égales mais que certaines morts sont plus révoltantes que d'autres — et nous aimons penser que certains problèmes sont symboliquement plus importants qu'un décompte numérique de leurs victimes. (A contrario, Bruce Schneier aime dire — en plaisantant, mais pas uniquement en plaisantant — que si un événement fait l'actualité, on ne doit pas s'en inquiéter, puisque par définition, l'actualité rapporte des événements inhabituels, c'est-à-dire, rares, or les choses dont on doit s'inquiéter sont celles qui sont fréquentes, par exemple, celles qui causent le plus de morts.) Les chiffres eux-mêmes, bien sûr, sont toujours délicats à peser : d'après le dernier rapport d'Europol, les actes terroristes ont fait quatre morts dans l'Union européenne en 2014 (ça doit être moins que la foudre…) : s'ils en ont fait beaucoup plus en 2015, la question se pose de comment interpréter cette évolution (un changement durable, un phénomène passager, une déviation statistique ?), et cela peut évidemment nourrir l'argument selon lequel on aurait eu tort de penser que le phénomène était insignifiant sur la base du nombre de morts en 2014. Le choix de la fonction d'utilité peut aussi donner lieu à des débats un peu sordides (est-il pertinent de faire perdre, par exemple, une heure par an à cinquante millions de personnes, si on peut en ce faisant sauver cent vies par an — sachant que ces cent vies représentent certainement moins de cinquante millions d'heures ? et quel poids le gouvernement d'un pays doit-il donner aux vies dans d'autres pays ?) : on a d'autant moins envie d'écouter l'utilitarisme dans ces conditions.

Les raisons pour lesquelles nous aimons être irrationnels sont difficiles à analyser. J'ai déjà parlé du chercheur en économie comportementale Dan Ariely, qui se spécialise dans l'étude de l'irrationalité prévisible et reproductible de l'homme, mais il s'agit chez lui plutôt de microéconomie. La raison pour laquelle nous mettons en place, par exemple, des mesures de sécurité totalement bidon, par exemple dans l'aérien, sont sans doute plus complexes à comprendre et à catégoriser. À un certain niveau, il s'agit certainement de rassurer les gens (raison pour laquelle on parle de security theater, et j'aime beaucoup l'illustration qu'en fait le sketch d'Adam Conover que je viens de lier) : le fait est que ça ne marche pas de rassurer les gens en leur disant arrêter de vous inquiéter pour les bombes dans les avions, vous avez considérablement plus de chances de mourir d'un cancer (et d'ailleurs, même s'agissant du cancer, vous ne vous comportez certainement pas de façon rationnelle…) : je n'arrive pas à convaincre mon propre gestalt émotionnel avec de tels arguments, alors je me vois mal convaincre quelqu'un d'autre. D'un autre côté, je ne suis même pas persuadé que ce genre de mesures fonctionne pour rassurer les gens (est-ce qu'on se sent plus en sécurité quand on voit des militaires partout patrouillant une ville, vraiment ?).

Bon, je ne sais plus où je voulais en venir avec mes propos confus (mais ce n'est pas le genre de choses qui m'empêche de ranter ☺). Donnons juste la morale suivante : pour qu'un débat public ne soit pas truqué et que les termes en soient clairement définis, il faut au moins examiner, et écouter les arguments qui se présentent pour, la plus grande variété des options, dont celle de l'inaction. Il est permis de penser qu'on ne doive pas suivre les choix « rationnels », c'est-à-dire, utilitaristes (il y a une nouvelle intéressante d'Asimov sur un thème assez proche, d'ailleurs : The Greatest Asset). Mais cette décision doit être consciente et éclairée, et, pour cela, il faut écouter cette voix même si on n'aime pas ce qu'elle dit.

(lundi)

Qu'est-ce qu'une machine hyperarithmétique ?

Voici un concept mathématique (voire, informatique ?) dont je suis tout étonné de découvrir que je ne l'ai jamais encore proprement défini sur ce blog, alors même que ça aurait été logique et pertinent de le faire dans différentes entrées que j'ai déjà écrites. (Par exemple, j'y fais explicitement référence dans cette entrée, et il aurait été logique d'en parler dans celle-ci ; et au sujet de cette entrée récente, je pourrais dire qu'il s'agit exactement de la puissance de calcul du niveau ωCK de la « Théorie de la Totalité Transfinie de Turing ».) Je voudrais donc réparer ce manque, d'autant plus que je trouve que le sujet devrait être standard, et connu, notamment, de tous les informaticiens théoriciens vaguement préoccupés de calculabilité ou de complexité (or je suis sûr que ce n'est pas le cas[#]) : une machine hyperarithmétique est un type d'ordinateur théorique strictement plus puissant que les machines de Turing, et il me semble qu'avoir en tête à la fois la notion de fonctions hyperarithmétiques (plus générales que les fonctions calculables au sens de Church-Turing, donc) et la notion de fonctions primitives récursives (plus restreintes) aide à mieux comprendre les contours de la calculabilité (y compris si on ne s'intéresse, in fine, qu'aux machines de Turing). Il me semble par ailleurs qu'il s'agit d'une notion relativement intuitive (je vais donc essayer de la présenter comme telle), qu'il est donc dommage de laisser cachée dans des textes de calculabilité supérieure un peu oubliés et au formalisme souvent obscur.

Je commence par rappeler[#2] ce que c'est que la calculabilité au sens habituel, i.e., de Church-Turing : les lecteurs pour lesquels ce concept est familier peuvent sauter jusqu'au symbole ♠ plus bas.

En bref, [une fonction] calculable (sous-entendu : au sens de Church-Turing) signifie [une fonction] qui pourrait être calculé(e), en principe, par un algorithme tournant sur un ordinateur — sachant que cet ordinateur n'a aucune limite sur la quantité de mémoire qu'il peut utiliser, ni sur le temps qu'il peut prendre, à part que le temps doit être fini (et la mémoire, du coup, automatiquement aussi).

Pour donner une définition plus précise, il y a plein de possibilités : la première qui ait été introduite historiquement, vers 1930, est le lambda-calcul de Church, mais même si elle est utile pour modéliser les langages de programmation fonctionnels, elle n'est pas très parlante intuitivement ; la seconde définition est venue par les fonctions générales récursives (je n'ai pas réussi à comprendre exactement quelle en était l'histoire, mais elles doivent être associées à un ensemble intersectant les noms suivants : Herbrand, Gödel, et Kleene) ; mais la définition de la calculabilité qui a vraiment achevé de convaincre le monde des mathématiciens qu'il s'agissait de la bonne notion est venue en 1936 quand Turing a défini la machine qui porte maintenant son nom. Quantité d'autres définitions ont été données depuis (par exemple avec des machines à registres). J'en donnerai moi-même une (illisible) ci-dessous comme produit dérivé d'une définition rigoureuse du sujet principal de cette entrée (pour les fonctions calculables, retirer la clause (vii) qui me sert à définir les fonctions hyperarithmétiques). Le point important est que toutes ces définitions sont équivalentes au sens où elles conduisent à la même classe de fonctions « calculables » : la fameuse thèse de Church-Turing affirme que n'importe quelle tentative pour définir la notion de « fonction calculable par un algorithme » aboutira, in fine, à cette même classe des fonctions calculables (au sens de Church-Turing, donc), étant bien entendu que l'« algorithme » doit manipuler à tout instant des données finies, et terminer en temps fini (et, par ailleurs, ne peut pas faire appel au hasard, ou en tout cas le résultat final ne doit pas en dépendre).

Ainsi, la notion de fonction calculable est une de ces notions qu'il vaut sans doute mieux ne pas définir formellement : parce qu'il est beaucoup plus efficace de décrire des algorithmes de façon informelle (informel ne voulant pas dire imprécis !) que de faire appel à un modèle particulier de calcul (personne n'a vraiment envie de programmer une machine de Turing). Par exemple, si je veux expliquer que la fonction décide si un entier n est un nombre premier (i.e., renvoie 1 si oui et 0 si non) est calculable, le mieux est de dire c'est bien le cas, parce qu'on peut tester pour tout 1<i<n si i divise n en calculant le reste de la division que d'écrire un programme explicite ou une fonction générale récursive ou que sais-je encore. C'est d'ailleurs ça qui rend le style des articles de Post très agréable et ceux de Kleene illisibles. Néanmoins, si on tient vraiment à définir formellement la notion, on peut partir d'essentiellement n'importe quel langage de programmation informatique réel ou simplifié[#3], et supposer qu'il tourne sur un ordinateur sur lequel la mémoire ne viendra jamais à manquer (on va aussi supposer, pour éviter des difficultés, que les entiers peuvent prendre des valeurs arbitrairement grandes, et par ailleurs il faut interdire l'appel à un générateur aléatoire) : Douglas Hofstadter a, par exemple, défini exprès le langage FlooP dans son célèbre ouvrage de vulgarisation Gödel, Escher, Bach (l'intérêt est en outre qu'il l'accompagne du langage BlooP qui permet, lui, d'exprimer exactement l'ensemble plus limité des fonctions primitives récursives). À partir du moment où le langage peut faire des opérations arithmétiques, des tests et des boucles, il est quasiment garanti d'être « Turing-complet », i.e., de définir justement les fonctions calculables au sens de Church-Turing. Les fonctions calculables au sens de Church-Turing sont donc bien celles qui sont calculables par un algorithme, ou, si on préfère, implémentables dans n'importe quel langage de programmation idéalisé (idéalisé au sens où on aurait retiré les limites évidentes d'implémentation).

Bref, la notion de calculabilité est en fait connue de toute personne qui a déjà étudié ou écrit un algorithme ou un programme. Il y a néanmoins quelque chose que je dois souligner : quelle que soit l'approche choisie (lambda-calcul, fonctions générales récursives, machines de Turing, ou tel ou tel autre langage ou modèle de calcul), pour définir les fonctions calculables, il faut nécessairement définir au passage des fonctions « partielles », c'est-à-dire, qui ne sont pas forcément définies partout. La raison en est que l'algorithme qui les calcule ne termine pas forcément en temps fini, et comme je vais l'expliquer il peut être impossible de le savoir en général : on laissera donc la valeur de la fonction non définie si l'algorithme censé la calculer ne termine pas. • Je crois que cette subtilité est ce qui a été le principal obstacle historique à dégager la notion de calculabilité : on a d'abord tenté de formaliser des concepts d'algorithmes qui terminent forcément (par exemple, la notion de fonction primitive récursive, dont je ne connais pas non plus exactement l'histoire), Ackermann a montré que ce concept n'était pas exhaustif, et on voyait bien que quelle que soit la notion d'algorithme-terminant-forcément qu'on dégage, l'argument diagonal va donner un nouvel algorithme terminant forcément mais qui n'est pas décrit par cette notion. Depuis Church et Turing, le point de vue est différent : on définit les fonctions calculables partielles, c'est-à-dire celles qui sont calculées par un algorithme pouvant terminer ou non (s'il ne termine pas en temps fini, la fonction n'est juste pas définie), et parmi ces fonctions, celles qui ont le bon goût d'être effectivement définies partout sont dites calculables [totales]. Et ce que Turing montre avec l'argument diagonal (que je vais reproduire ci-dessous en substance), c'est qu'il n'est justement pas algorithmiquement faisable, i.e., pas calculable, de décider si un programme donné s'arrête (sur une entrée donnée, ou, en fait, sur une entrée fixée quelconque) : c'est ce qu'on appelle le problème de l'arrêt. Finalement, en admettant la possibilité de fonctions calculables non totales, l'argument diagonal, au lieu de montrer que la notion de calculabilité ne capture pas toutes les fonctions algorithmiquement calculables, montre maintenant qu'il existe des fonctions qui ne sont pas calculables.

 Maintenant, imaginons qu'on veuille définir des machines strictement plus puissantes que les machines de Turing. On peut certainement le faire de façon ad hoc : par exemple, comme les machines de Turing ne peuvent pas résoudre le problème de l'arrêt (i.e., décider en temps fini si une — autre — machine de Turing donnée s'arrêtera en temps fini ou non), on peut donner à la machine la possibilité supplémentaire d'avoir cette information ; on définit ainsi une machine de Turing « avec l'oracle de l'arrêt », qui peut faire ce que peut faire une machine de Turing ordinaire, mais qui peut aussi à tout moment « consulter l'oracle », ce qui signifie que la machine présente à l'oracle une machine de Turing ordinaire (et éventuellement une bande initiale finie, mais ce n'est pas important), et l'oracle répondra (instantanément !) si cette machine termine en temps fini ou non. Ou, si on préfère imaginer un langage de programmation idéalisé plutôt qu'une machine de Turing, ce langage est enrichi par une fonction (magique !) halting_oracle(), qui prend en argument un programme ou une fonction f du même langage, mais n'utilisant pas la fonction halting_oracle() en question, et elle renvoie (instantanément !) vrai ou faux selon que le calcul de f(0) termine en temps fini ou pas (le 0 est sans importance ici : ça ne changerait fondamentalement rien de mettre une autre valeur, de ne pas en mettre du tout — ou de prendre la valeur à passer en argument en paramètre à halting_oracle(), ce qui est peut-être plus standard).

Il va de soi qu'une telle machine n'est pas réalisable physiquement (ou en tout cas, on ne sait pas comment, et ce serait vraiment extrêmement surprenant qu'elle le soit[#4]), mais elle est néanmoins mathématiquement bien définie. La famille des fonctions qu'elle sait calculer (i.e., les fonctions « calculables à partir de l'oracle de l'arrêt ») est strictement plus vaste que celle des fonctions calculables au sens de Church-Turing (i.e., sans cet oracle de l'arrêt). Par définition, l'oracle de l'arrêt permet de résoudre le problème de l'arrêt (des machines de Turing ordinaires), mais en fait, il permet de répondre à énormément d'autres questions. Par exemple, si je veux savoir si la conjecture de Goldbach (celle qui affirme que tout nombre pair est la somme de deux nombres premiers) est vraie, j'écris un programme qui énumère les nombres pairs n et, pour chacun d'eux, énumère tous les entiers impairs k plus petits et teste si k et nk sont tous les deux premiers : si oui, le programme passe au n suivant (i.e., n+2) ; tandis que si pour un n donné on ne trouve pas de k tel que k et nk soient premiers, le programme s'arrête ; ainsi, ce programme tournera indéfiniment si la conjecture de Goldbach est vraie, et s'arrêtera si elle est fausse ; en utilisant l'oracle de l'arrêt sur ce programme, on décide donc la question. Et énormément de problèmes mathématiques sont ainsi décidables par une telle machine (autre exemple, l'hypothèse de Riemann, même s'il faut travailler un peu plus pour le voir). En outre, une machine disposant de l'oracle de l'arrêt permet de décider si n'importe quel énoncé mathématique est ou n'est pas un théorème [de ZFC] (il suffit d'appliquer l'oracle de l'arrêt à un programme qui énumère toutes les démonstrations mathématiques possibles [dans ZFC] — par exemple en énumérant toutes les chaînes de caractères possibles et en ignorant celles qui ne vérifient pas toutes les lois de la logique — et s'arrête s'il trouve une démonstration de l'énoncé proposé) : je renvoie à cette entrée passée sur la distinction entre être vrai et être un théorème, qui est très importante dans cette phrase. En tout cas, l'oracle de l'arrêt est extrêmement puissant.

Pourtant, l'oracle de l'arrêt a ses limites : les machines de Turing-avec-oracle-de-l'arrêt peuvent (par définition) résoudre le problème de l'arrêt des machines de Turing ordinaires, mais pas le problème de l'arrêt des machines de Turing-avec-oracle-de-l'arrêt. Autrement dit, on obtient quelque chose d'encore plus puissant si on permet de décider l'arrêt de ces machines-là. Ou, si on préfère, j'ai représenté ci-dessus l'oracle de l'arrêt comme une fonction halting_oracle() qui prend en argument une fonction f et décide si cette fonction termine en temps fini, mais à condition que f ne fasse pas appel à halting_oracle() : on peut introduire une fonction plus puissante, halting_oracle_2(), qui fonctionne même si f fait appel à halting_oracle() — mais pas, cette fois, à halting_oracle_2(). Grâce à cet oracle plus puissant, on peut décider d'autres problèmes mathématiques, par exemple la question de si PNP (en gros, on applique halting_oracle_2() à un programme qui énumère tous les algorithmes possibles et toutes les bornes polynomiales possibles et qui, pour chaque paire, utilise halting_oracle() pour décider si l'algorithme résout bien toutes les instances d'un problème NP-complet (fixé) en temps imparti). • On peut continuer ainsi à accumuler les niveaux finis d'oracles, ce qui correspond en gros à la hiérarchie arithmétique. Mais comme le nom le suggère, une machine hyperarithmétique est encore plus puissante que tout ça. (Elle est même strictement plus puissante que la possibilité d'appeler halting_oracle_omega(), qui fonctionne avec les programmes utilisant n'importe quel niveau de halting_oracle_n().)

Pourquoi, me demandera-t-on peut-être, ne pas directement imaginer une fonction halting_oracle_ultimate() qui fonctionnerait sur les fonctions f pouvant faire appel à halting_oracle_ultimate() ? Tout simplement parce que ceci serait immédiatement contradictoire : en utilisant une technique proche des quines (c'est-à-dire les programmes qui écrivent leur propre code source : cf. cette page où j'explique très en détail comment une telle chose se fait), on pourrait écrire un programme qui demande à la fonction halting_oracle_ultimate() est-ce que je vais m'arrêter ?, et, si la fonction répond oui, lancer une boucle infinie, tandis que si elle répond non, s'arrêter, ce qui contredit la réponse de l'oracle et montre que celui-ci n'est pas bien défini (vu qu'il est circulaire, ce n'est pas très surprenant). Ce que je viens d'expliquer, d'ailleurs, montre en particulier pourquoi le problème de l'arrêt ordinaire n'est pas résoluble par une machine de Turing ordinaire, ou pourquoi essentiellement aucune sorte de machine ne peut résoudre le problème de l'arrêt de sa propre classe (bon, il y a quelques hypothèses implicites sur la classe de calculabilité dans ce raisonnement, mais pas grand-chose). La machine hyperarithmétique va passer aussi près qu'elle peut de cette impossibilité en l'évitant subtilement : une machine hyperarithmétique ne pourra pas déterminer si une machine hyperarithmétique s'arrête, mais elle pourra faire « presque aussi bien » en considérant une infinité de valeurs simultanément.

Pour comprendre comment, considérons une autre capacité par laquelle on pourrait enrichir une machine de Turing (ou un langage de programmation idéalisé, ou tout autre modèle du genre). Cette fois, je vais lui donner la capacité de détecter, pour une fonction f (prenant des valeurs entières positives et renvoyant des valeurs entières positives) si la fonction f prend une valeur non-nulle ou non. Si je me place dans l'optique d'un langage de programmation, je suppose donc que j'ai une fonction « magique », non_zero(), qui, quand on lui fournit en argument une fonction f, va considérer l'infinité de valeurs f(0), f(1), f(2), etc., et si l'une est différente de 0 va renvoyer vrai (1, disons), et sinon va renvoyer faux (0, disons) ; si l'un des calculs de f(i) ne termine pas (i.e., la valeur n'est pas définie), alors non_zero(f) peut ne pas terminer non plus (pour le moment, disons qu'on n'a aucune garantie) ; en revanche, si tous sont définis, alors on obtient une réponse (instantanément !), bien qu'il y ait une infinité de valeurs à considérer. • Si la fonction f n'a pas elle-même le droit de faire appel à non_zero(), alors cette fonction magique non_zero() est tout à fait équivalente à l'oracle halting_oracle() considéré plus haut : en effet, dans un sens, si j'ai accès à halting_oracle(), je peux programmer non_zero() (il suffit de considérer le programme qui calcule successivement f(0), f(1), f(2), etc., et qui s'arrête dès qu'il calcule une valeur ≠0, et de demander à halting_oracle() si ce programme s'arrête), et dans l'autre sens, si j'ai accès à non_zero(), je peux programmer halting_oracle() (il suffit, pour décider si un programme s'arrête, de faire une fonction f(n), qui exécute les n premiers pas de ce programme et renvoie 1 si le programme est terminé à ce moment-là, et 0 sinon).

Maintenant, une machine hyperarithmétique, c'est une machine qui peut faire appel à cette fonction non_zero(), y compris sur une fonction f qui peut elle-même faire appel à la fonction non_zero(), i.e., y compris sur une fonction hyperarithmétique. Autrement dit :

Une machine hyperarithmétique est une machine capable des mêmes opérations qu'une machine de Turing ordinaire, mais aussi de tester la nullité d'une infinité de valeurs d'une fonction f elle-même calculée par une machine hyperarithmétique. I.e., une fonction hyperarithmétique est une fonction calculable par une machine, qui, en plus des capacités d'une machine de Turing, a la capacité d'examiner simultanément une infinité (f(0), f(1), f(2), etc.) de valeurs calculées par une fonction hyperarithmétique f, à condition que toutes ces valeurs soient bien définies, et de décider si elles sont toutes nulles ou s'il y en a une non-nulle (bien sûr, dans ce cas, on peut aussi lui donner la capacité de trouver le premier indice pour lequel f(i)≠0, ça ne changera rien). Si l'une au moins des valeurs f(i) n'est pas définie (i.e., si son calcul ne termine pas), alors une tentative pour en examiner toute ses valeurs sera elle-même non-définie. Cette définition est circulaire (une fonction peut très bien examiner une infinité de ses propres valeurs), mais ce n'est pas problématique, parce que contrairement à l'hypothétique fonction halting_oracle_ultimate() plus haut, on évite le paradoxe puisque la fonction peut ne pas être définie. Par exemple, si j'essaye d'écrire une fonction f qui va examiner ses propres valeurs et renvoyer 0 (pour toute entrée) si elles sont non-nulles et vice versa, la fonction f sera tout simplement non-définie partout (exactement comme, dans un langage de programmation ordinaire, une fonction f dont la valeur en i serait définie récursivement par f(i) = f(i) + 1 ou quelque chose comme ça : c'est juste une récursion qui ne termine pas). • Pour donner une définition mathématiquement plus rigoureuse, il faudrait dire : la notion de terminaison et de valeur des fonctions hyperarithmétiques est la plus petite (au sens de l'inclusion) telle que, (entre autres règles communes avec la calculabilité au sens de Church-Turing ordinaire,) si f(i) est défini pour tout i alors non_zero(f) est défini et vaut 0 lorsque chaque f(i) vaut 0, et 1 sinon.

Ajout/clarification : mon poussinet se plaint que cette définition avec la plus petite notion n'explique pas vraiment les choses (et que la définition formelle qui suit immédiatement n'aide pas vraiment). Voici une tentative pour expliquer comment la circularité de la définition est brisée : (0) on part d'un langage équivalent aux machines de Turing, et pour l'instant non_zero(f) n'est jamais défini (la fonction ne fonctionne pas) ; puis, si f(i) est défini pour tout i (ce f est alors, forcément, calculable au sens de Church-Turing), (1) on définit non_zero(f) (valant 0 ou 1 selon que f ne prend que des valeurs 0 ou pas) dans ce cas précis, ce qui fait terminer plus de calculs ; et (2) on répète l'opération : si f(i) est défini pour tout i (pour la terminaison qui vient d'être un peu étendue), alors on définit non_zero(f) pour ces nouveaux cas ; et (3) on répète ; et (4) encore, et (5) encore, et (6) encore… Et on doit parcourir des ordinaux transfinis dans l'opération (par exemple, parce que la terminaison f(i) pourrait avoir été obtenue après i étapes pour chaque i, ce qui donne un sens à non_zero(f) seulement à l'étape (ω)) : mais les ordinaux finissant toujours par gagner, la définition finit par se stabiliser : ceci définit les fonctions/machines hyperarithmétiques, et l'ordinal auquel la définition se stabilise est le ωCK qui va réapparaître occasionnellement dans ce qui suit.

Pour ceux qui veulent vraiment une définition mathématique parfaitement rigoureuse, en voici une possible. Je vais noter ‹m:a› pour une représentation des couples d'entiers naturels par des entiers naturels non nuls, disons ‹m:a› := 2m·(2a+1), et ‹m1,…,mk› := ‹m1:‹…:‹mk:0›…›› (il sera éventuellement utile de poser aussi ‹m1,…,mk:a› := ‹m1:‹…:‹mk:a›…››). J'appelle alors le plus petit ensemble d'entiers naturels qui vérifie les propriétés suivantes : (o) ‹‹0›, a, a› ∈ pour tout a ; (i) ‹‹1,q›, a, q› ∈ pour tous q et a ; (ii) ‹‹2›, ‹x:a›, x+1› ∈ pour tous x et a ; (iii) ‹‹3,k›, ‹x1,…,xk:a›, xk› ∈ pour tous k≥1 et tous x1,…,xk et a ; (iv) ‹‹4›, ‹x,x,u,v›, u› ∈ pour tous x,u,v et ‹‹4›, ‹x,y,u,v›, v› pour tous xy,u,v ; (v) si ‹pi, a, vi› ∈ pour tout 1≤ik et ‹q, ‹v1,…,vk›, w› ∈ , alors ‹‹5,q,p1,…,pk›, a, w› ∈  ; (vi) si ‹p, a, v› ∈ alors ‹‹6›, ‹p:a›, v› ∈  ; et (vii) si, pour un certain p on a, pour tout i, que ‹p, ‹i›, 0› ∈ , alors ‹‹7›, ‹p›, 0› ∈ , tandis que si (toujours pour un certain p) on a, pour tout i, que ‹p, ‹i›, vi› ∈ vi≠0, alors ‹‹7›, ‹p›, 1› ∈ . Cet ensemble est bien défini (car les conditions sont positives, donc une intersection quelconque d'ensembles d'entiers naturels qui les satisfait le satisfait encore, et il en existe bien un plus petit). • L'interprétation de ‹p, a, v› ∈ est censée être le programme p, quand on l'exécute sur la liste d'arguments a (normalement, ‹x1,…,xk›), termine et renvoie la valeur v : le (i) exprime le fait que les fonctions constantes sont calculables, le (ii) que la fonction successeur l'est, le (iii) que les fonctions sélectionnant tel ou tel argument (i.e., les projections) le sont, le (iv) permet de faire des tests d'égalité, le (v) des compositions de fonctions, le (vi) des invocations de programmes passés en argument (donc, in fine, des boucles par invocation récursive), le (o), qui n'est probablement pas nécessaire mais peut-être utile pour utiliser le (vi), assure qu'on peut calculer la fonction ‹m:a› elle-même, et le (vii) est justement la spécificité des fonctions hyperarithmétiques (le non_zero() ci-dessus). • On peut montrer que, pour p et a fixés, la propriété ‹p, a, v› ∈ ne peut être vérifiée que pour au plus un v. On dira donc alors qu'une fonction f:ℕ→ℕ (ou une fonction partielle f:ℕ⇢ℕ) est hyperarithmétique lorsqu'il existe p entier naturel tel que pour tout i on ait équivalence entre ‹p, ‹i›, v› et v=f(i) (ce qui sous-entend que f(i) soit définie). • Une remarque (♣) plus bas fera remarquer qu'on peut, sans changer les fonctions hyperarithmétiques (mais en changeant l'ensemble ), modifier (vii) en : (vii) si, pour un certain p on a, pour tout i, que ‹p, ‹i›, 0› ∈ , alors ‹‹7›, ‹p›, 0› ∈ , tandis que si pour un certain p, un certain i et un certain v on a que ‹p, ‹i›, v› ∈ v≠0, alors ‹‹7›, ‹p›, 1› ∈ . • Si on supprime carrément le (vii), on doit obtenir une définition des fonctions calculables au sens de Church-Turing (c'est, en quelque sorte, une vérification du fait que je ne me suis pas trompé[#4½] ; mais même si je me suis trompé, il est certainement facile de corriger (i)–(vi) pour obtenir les fonctions calculables au sens de Church-Turing, et l'ajout de la condition (vii) devrait définir les fonctions hyperarithmétiques).

Ces machines hyperarithmétiques sont extrêmement puissantes : comme je l'ai expliqué plus haut, elles peuvent résoudre non seulement le problème de l'arrêt pour les machines de Turing ordinaires, mais aussi pour les machines de Turing disposant de cet oracle-là, et ainsi de suite jusqu'à un nombre d'itérations d'oracles donné par un ordinal ωCK (appelé ordinal de Church-Kleene) qui n'est pas évident à décrire puisque justement il n'est pas manipulable par les machines de Turing ni même par les machines hyperarithmétiques. En particulier, elles peuvent décider tous les énoncés arithmétiques (que je définis par exemple dans cette entrée). • Par ailleurs, une machine hyperarithmétique peut manipuler des données infinies (des suites d'entiers, c'est-à-dire, si on préfère, des nombres réels) comme si elles étaient finies : pas « n'importe quelle » suite entière / « n'importe quel » nombre réel, certes, seulement justement ceux qui sont hyperarithmétiques, mais ça en fait quand même beaucoup, et ce qui est intéressant, c'est qu'une machine hyperarithmétique peut non seulement effectuer toutes les opérations algébriques et transcendantes usuelles (et quantité d'autres choses) sur les réels hyperarithmétiques, mais elle peut aussi tester leur égalité de façon exacte (en comparaison, une machine de Turing peut certes manipuler dans une certaine mesure les réels calculables, mais elle ne peut pas tester leur égalité exacte). En fait, une machine hyperarithmétique peut faire plus que manipuler des réels : elle peut manipuler — de façon exacte — toutes sortes d'ensembles (qu'on peut appeler les ensembles hyperarithmétiques, et qui sont en fait le niveau ωCK de l'univers constructible de Gödel) ; ces ensembles ne vérifient pas tous les axiomes de Zermelo-Fraenkel, mais ils en vérifient un bout déjà intéressant (la théorie des ensembles de Kripke-Platek avec infini).

Une question qu'on risque sans doute de me poser, c'est si une machine hyperarithmétique dispose d'une mémoire infinie : la réponse est surtout que la question n'a pas vraiment de sens (la définition des machines hyperarithmétiques n'utilise pas vraiment le paradigme « mémoire », et d'ailleurs la définition rigoureuse que j'ai proposée ne fait aucune mention de ce terme) ; mais intuitivement, il faut s'imaginer que la réponse est plutôt : oui, à condition que la donnée stockée sur cette mémoire infinie soit hyperarithmétique (c'est la condition permettant de manipuler une donnée infinie : elle sera juste stockée sous la forme de la fonction hyperarithmétique qui la calcule, mais pour beaucoup d'opérations on peut faire comme si elle était stockée intégralement en mémoire et la manipuler en bloc comme une donnée infinie).

Malgré toute cette puissance, les machines hyperarithmétiques ont leurs limitations. Elles ne peuvent pas, bien sûr, résoudre leur propre problème de l'arrêt (l'argument diagonal s'applique toujours). Mais, de façon peut-être plus surprenante, les ordinaux que peut « manipuler » (pour à peu près n'importe quel sens de ce mot) une machine hyperarithmétique sont exactement les mêmes qu'une machine de Turing ordinaire (dans les deux cas, ce sont précisément les ordinaux strictement inférieurs à l'ordinal ωCK de Church-Kleene — ceci est plus une définition de ce dernier qu'un théorème). Une machine hyperarithmétique n'est pas capable en général de décider si un graphe orienté dénombrable défini par une machine de Turing possède un chemin infini (même si ce graphe est supposé être un ordre total, i.e., la machine arithmétique n'est pas capable en général de décider si un ordre total calculable sur les entiers est un bon ordre). Et une machine hyperarithmétique n'est pas capable en genéral de décider si une suite hyperarithmétique (i.e., comme ci-dessus, f(0), f(1), f(2), etc., avec f hyperarithmétique) a une infinité de valeurs non-nulles (de fait, si on donne à la machine la capacité de répondre à cette question, on obtient un type de machine encore plus puissant, dont l'ordinal assez naturellement associé est le premier ordinal dit « récursivement inaccessible » au lieu de ωCK qui est plus petit).

Mais je veux aussi défendre l'idée que les machines hyperarithmétiques sont quelque chose d'assez naturel : même si dans le monde physique dans lequel nous vivons, la machine de Turing est le modèle de calcul qui s'impose, mathématiquement, la machine hyperarithmétique est peut-être bien aussi naturelle. Un argument dans ce sens est qu'il y a, comme pour les fonctions calculables au sens de Church-Turing, toutes sortes de définitions possibles des fonctions hyperarithmétiques. J'en ai donné une ci-dessus (qui s'inscrit dans le cadre de ce qui s'appelle formellement la calculabilité [au sens de Kleene] en une fonctionnelle de type 2, la fonctionnelle de type 2 en question étant ici la fonction E = non_zero, qui à une fonction f:ℕ→ℕ associe[#5] 0 ou 1 selon que f est constamment égale à 0 ou non). Une autre description possible est qu'il s'agit du niveau Δ¹₁ de la hiérarchie analytique, mais je ne veux pas expliquer ici ce que ça signifie (par contre, c'est ce qu'on a le plus de chances de trouver dans un livre un peu standard de calculabilité — ce qui est con, parce que c'est une notion fort peu intuitive) ; l'équivalence avec la notion que j'ai définie ci-dessus est un résultat de Kleene de 1959. Encore une autre définition consiste à considérer des machines (à registres, disons, mais il y a encore toutes sortes de variantes possibles) qui, au lieu de manipuler des entiers, manipulent des ordinaux, et qui peuvent effectuer des boucles dont le temps va jusqu'à l'ordinal ωCK (le plus petit ordinal qui n'est pas calculable : on remarquera qu'il réapparaît régulièrement dans cette entrée[#6]) : les fonctions sur les entiers qui sont calculables par une telle machine ordinale sont précisément les fonctions hyperarithmétiques. Enfin, on peut accumuler les « sauts de Turing », c'est-à-dire les niveaux de l'oracle de l'arrêt, jusqu'à ce qu'on observe quelque chose de nouveau (là aussi, je préfère rester vague), et ça se produit précisément quand on atteint le niveau ωCK et les fonctions hyperarithmétiques. En quelque sorte, les machines hyperarithmétiques sont les plus simples, ou les moins puissantes, du monde de la calculabilité supérieure. Enfin, comme je le remarque ci-dessus, on peut les définir comme l'extension la plus simple de la machine de Turing qui ait la capacité à comparer deux réels qu'elles-mêmes calculent, ce qui est certainement une condition naturelle.

Il y a encore un point un peu technique que je veux signaler, parce que je pense qu'il joue pour expliquer que les machines hyperarithmétiques sont quelque chose de naturel. J'ai défini ci-dessus les machines hyperarithmétiques comme des machines analogues à celles de Turing mais auxquelles on ajoute la capacité (l'appel à non_zero(f)) d'examiner simultanément une infinité (f(0), f(1), f(2), etc.) de valeurs calculées par une fonction hyperarithmétique f, à condition que toutes ces valeurs soient bien définies, et de décider si elles sont toutes nulles ou s'il y en a une qui est non-nulle. Si ne serait-ce qu'une seule des f(i) est non-définie, alors l'examen de toutes les valeurs échoue, i.e., le calcul ne termine pas et le résultat n'est pas défini. Mais il est possible de rendre cette contrainte moins rigoureuse et d'obtenir au final exactement la même notion de machine hyperarithmétique. Par exemple, il est facile de voir que cela ne change rien au final si on décide que les valeurs f(0), f(1), f(2), etc., seront examinées dans cet ordre, et que l'examen s'arrêtera si f(i) est définie et non-nulle et que les f(j) pour j<i sont définies (auquel cas non_zero(f) renvoie 1=vrai), ou bien si tous les f(i) sont définies et nulles (auquel cas non_zero(f) renvoie 0=faux). Pour s'en convaincre, il suffit, avant l'opération (i.e., avant le calcul de non_zero(f)) de remplacer f par une fonction g telle que g(i) calcule successivement les f(j) et s'arrête si elle trouve une valeur non-nulle, en renvoyant cette valeur, ou bien si j atteint la valeur i, auquel cas elle renvoie 0. • Ce qui est nettement plus subtil, c'est (♣) qu'on ne change rien non plus à la notion de machine hyperarithmétique si on suppose que l'examen des valeurs f(0), f(1), f(2), etc., termine dès qu'il y a une quelconque valeur qui est définie et non-nulle (auquel cas le résultat sera 1=vrai), ou que toutes les valeurs sont définies et nulles (auquel cas le résultat sera 0=faux). Si on a l'habitude des machines de Turing, on aurait envie de dire oui, ce n'est pas surprenant, il suffit d'écrire une fonction g qui lance l'exécution de f de façon parallèle déployée, mais en fait ce n'est pas si simple, parce que la notion d'un pas d'exécution d'une machine hyperarithmétique n'est pas du tout évidente (vu que ce pas pourrait faire lui-même appel à l'examen d'une infinité de valeurs d'une autre fonction, etc.) ! Pourtant, le résultat est correct, mais il fait appel à un théorème de sélection non-trivial, qui est vrai aussi bien pour les machines de Turing (auquel cas il est facile) que pour les machines hyperarithmétiques (où il est nettement moins facile) : à savoir, il est possible d'écrire un programme qui prend en entrée une fonction f (d'un paramètre entier i) et qui, si f(i) termine pour au moins une valeur de i, termine lui-même en renvoyant une telle valeur de i. Dans le cas hyperarithmétique (défini tel que je l'ai fait ci-dessus), ce résultat s'appelle le théorème de sélection de Gandy (ceux qui veulent voir une preuve peuvent la trouver en VI.4.1 du livre de Hinman de 1978, Recursion-Theoretic Hierarchies, ou dans un contexte un petit peu différent, X.4.1 du livre de Sacks de 1990, Higher Recursion Theory).

Voici encore une façon de présenter les machines hyperarithmétiques : ce sont des machines qui ont la capacité de calculer des conjonctions (=et logiques), ou de façon équivalente des disjonctions (=ou logiques), infinies, à condition que les termes de la conjonction/disjonction soient eux-mêmes calculés par une machine hyperarithmétique. (Le paragraphe précédent, en petits caractères, explique en substance (♣) que cela ne change rien si qu'on suppose ou non que la machine évalue ces conjonctions et disjonctions infinies de façon minimale, c'est-à-dire qu'une disjonction renvoie vrai dès qu'un des termes est vrai, même si les autres ne sont pas définis.) Ceci donne aux machines hyperarithmétiques un lien fort avec certaines logiques infinitaires, et notamment avec le théorème de compacité de Barwise (dont un énoncé très très très grossier serait que si on remplace fini par hyperarithmétique, une des propriétés essentielles de la logique usuelle reste valable).

⁂ J'espère avoir convaincu que les machines hyperarithmétiques sont une notion relativement naturelle. Mais je veux aussi souligner qu'il est à mon avis intéressant de la comprendre parce que la notion de fonctions calculables au sens de Church-Turing est encadrée par la notion (plus restreinte) de fonctions primitives récursives et la notion (plus générale) de fonctions hyperarithmétiques que je viens de définir. Or ces deux bornes présentent une certaine similarité : la classe des fonctions primitives récursives fait une sorte de pont entre les classes de complexité et la théorie de la calculabilité (c'est une classe de complexité, parce qu'une fonction est primitive récursive ssi elle est calculable en temps ou en espace donné par une fonction primitive récursive ; bien sûr, en tant que telle, c'est une classe énorme ; mais c'est aussi le début de la calculabilité, parce que cette classe se définit syntaxiquement et sans avoir besoin de parler de complexité) ; et la classe des fonctions hyperarithmétiques fait une sorte de pont entre la théorie de la calculabilité et la logique (c'est une classe de calculabilité, manifestement, mais c'est le début de la calculabilité supérieure qui s'inscrit plus naturellement dans la vision de l'univers constructible de Gödel). Et la similarité va plus loin : on peut partir des fonctions primitives récursives et créer des fonctions de plus en plus puissantes par diagonalisation (il n'existe pas de machine universelle pour les fonctions primitives récursives : si on en ajoute un, on crée une classe plus puissante, et on peut recommencer l'opération de façon transfinie ; dans cette entrée j'appelais ça le saut de Kleene, ce qui est un très mauvais terme pour plein de raisons — j'aurais dû dire saut d'Ackermann —, mais en tout cas le concept est important), ceci fabrique ce qu'on appelle les hiérarchies sous-récursives ; tandis qu'on peut partir des fonctions calculables au sens de Church-Turing et créer des fonctions de plus en plus puissantes par une autre forme de diagonalisation (ajouter le problème de l'arrêt de façon répétée et transfinie), ce qui fabrique la hiérarchie hyperarithmétique. Il existe certes des différences importantes entre ces deux constructions[#7], mais la similarité est assez significative pour mériter l'attention. Je pense qu'on comprend bien mieux la notion de fonction calculable au sens de Church-Turing en ayant ces autres notions présentes à l'esprit.

[#] Pour commencer, le terme machine hyperarithmétique n'est pas vraiment standard : celui de fonction hyperarithmétique l'est, mais pour trouver une description explicite d'une machine qui calcule ces fonctions, il faut fouiller dans des livres (parfois poussiéreux) de calculabilité supérieure. La description des fonctions hyperarithmétiques qu'on trouvera dans la plupart des livres sur la calculabilité est de les présenter comme le niveau Δ¹₁ de la hiérarchie analytique (lightface) : mais franchement, quand on décrit les choses comme ça, je pense qu'il est absolument impossible pour un débutant de s'en faire une intuition, encore moins de comprendre pourquoi les niveaux Δ¹₁ et Δ¹₂ sont beaucoup plus importants que tout ce qui vient après (ni pourquoi ce sont les ensembles Π¹₁, et pas les Σ¹₁, qui se comportent un peu comme les ensembles récursivement énumérables =Σ⁰₁).

[#2] Ceci dit, je voudrais bien lancer le défi de définir de la façon la plus compréhensible / intuitive, et néanmoins concise, cette notion de calculabilité (imaginer, pour fixer les idées, qu'on s'adresse à quelqu'un qui est scientifique et sait se servir d'un ordinateur, peut-être même programmer, mais n'est pas vraiment mathématicien ni informaticien : comment expliquer le concept efficacement ?). Je demande notamment, parce qu'à Télécom ParisMachinBiduleTech, je participe à un enseignement (appelé théorie des langages) où le concept doit être rapidement introduit, et pour l'instant nous n'avons pas vraiment trouvé de façon de faire comprendre aux élèves qu'il s'agit d'une notion que, fondamentalement, ils connaissent déjà parce que tout ce pour quoi ils peuvent imaginer un algorithme est ipso facto calculable. (Par exemple, si on leur demande si l'ensemble des mots (=chaînes de caractères) qui sont des palindromes est calculable, il y en a bien la moitié qui ne savent pas répondre ou qui répondent au pif, au lieu d'écrire oui, bien sûr que ce n'est pas difficile d'écrire un programme qui teste si une chaîne de caractères est la même à l'envers !.) La difficulté, à la base, c'est que si on donne une définition informelle, les élèves ont l'impression que c'est de l'agitage de main et qu'on ne peut rien prouver dessus, et si on donne une définition formelle, ils n'y voient rien : on voit bien, à la lecture de la présente entrée, que je me débats avec cette difficulté.

[#3] Bon, en toute honnêteté, si je dois donner rapidement une définition formelle des fonctions calculables, je crois que je le ferai par une approche proche de ce que je fais ici même pour les fonctions hyperarithmétiques, et il faut admettre que c'est illisible dans le style de Kleene.

[#4] En fait, il y a des physiciens qui spéculent sur le fait que la thèse de Church-Turing « physique » serait fausse, et que la relativité générale permettrait, en fait, d'effectuer certains « hyper-calculs » : voir ce exposé de Mark Hogarth pour des explications à ce sujet. Je pense en fait que la notion de fonction hyperarithmétique serait justement adaptée à son propos (je devrais peut-être le lui signaler).

[#4½] Par acquit de conscience, j'ai voulu vérifier que j'arrivais au moins à « programmer » la fonction d'addition dans l'espèce de langage de programmation que je définis avec les clauses (i)–(vi) (le (o) n'est sans doute pas utile ; il aurait été nécessaire si j'avais écrit le (vi) sous la forme (vi′) si ‹p, a, v› alors ‹‹6›, ‹p,a›, v› ∈ — avec ‘,’ au lieu de ‘:’). Et il faut admettre que c'était plus dur que ce que je pensais (ça ressemble beaucoup à programmer en Unlambda, et ce n'est d'ailleurs pas complètement un hasard). Je suis arrivé à p := ‹5, ‹5, ‹6›, ‹5, ‹4›, ‹3, 4›, ‹3, 3›, ‹1, ‹3, 2››, ‹1, ‹5, ‹2›, ‹5, ‹6›, ‹3, 1›, ‹3, 1›, ‹3, 2›, ‹3, 3›, ‹5, ‹2›, ‹3, 4››››››, ‹3, 1›, ‹3, 2›, ‹3, 3›, ‹3, 4››, ‹1, ‹5, ‹6›, ‹5, ‹4›, ‹3, 4›, ‹3, 3›, ‹1, ‹3, 2››, ‹1, ‹5, ‹2›, ‹5, ‹6›, ‹3, 1›, ‹3, 1›, ‹3, 2›, ‹3, 3›, ‹5, ‹2›, ‹3, 4››››››, ‹3, 1›, ‹3, 2›, ‹3, 3›, ‹3, 4›››, ‹3, 1›, ‹3, 2›, ‹1, 0››, pour lequel on a ‹p, ‹x,y›, x+y› ∈ pour tous x,y∈ℕ. Pour ceux qui voudraient le vérifier, voici un programme Scheme qui interprète ce langage bizarre : (define (ev prgm args) (if (not (list? prgm)) (error "prgm is not a list")) (let ((inst (car prgm))) (case inst ((0) args) ((1) (cadr prgm)) ((2) (+ (car args) 1)) ((3) (list-ref args (- (cadr prgm) 1))) ((4) (if (= (car args) (cadr args)) (caddr args) (cadddr args))) ((5) (let ((vals (map (lambda (p) (ev p args)) (cddr prgm)))) (ev (cadr prgm) vals))) ((6) (ev (car args) (cdr args))) (else (error "unknown instruction"))))) (pour donner un exemple, si on fait (define plusprg '(5 (5 (6) (5 (4) (3 4) (3 3) (1 (3 2)) (1 (5 (2) (5 (6) (3 1) (3 1) (3 2) (3 3) (5 (2) (3 4)))))) (3 1) (3 2) (3 3) (3 4)) (1 (5 (6) (5 (4) (3 4) (3 3) (1 (3 2)) (1 (5 (2) (5 (6) (3 1) (3 1) (3 2) (3 3) (5 (2) (3 4)))))) (3 1) (3 2) (3 3) (3 4))) (3 1) (3 2) (1 0))), alors (ev plusprg '(30 12)) renvoie 42) ; et pour ceux qui voudraient essayer de comprendre comment ce programme p=plusprg est foutu, il est obtenu en faisant une sorte de traduction de la fonction Scheme suivante : (lambda (x y) ((lambda (f x y z) ((if (= z y) (lambda (f x y z) x) (lambda (f x y z) (+ (f f x y (+ z 1)) 1))) f x y z)) (lambda (f x y z) ((if (= z y) (lambda (f x y z) x) (lambda (f x y z) (+ (f f x y (+ z 1)) 1))) f x y z)) x y 0)) (dont on peut vérifier qu'elle calcule bien la somme de deux entiers naturels passés en argument, sans utiliser autre chose que des λ, des applications, la fonction successeur, et un if qui a même le droit d'évaluer toutes ses branches complètement). On remarquera au passage que j'ai codé les listes d'entiers à partir des paires, à savoir ‹m1,…,mk› := ‹m1:‹…:‹mk:0›…››, sur l'inspiration de Lisp/Scheme. Bref, ayant fait cet exercice, je suis raisonnablement convaincu que je capture toutes les fonctions générales récursives avec les clauses (i)–(vi), mais je ne prétends pas forcément que c'était la façon la plus intelligente de s'y prendre (même avec la contrainte supplémentaire de se généraliser facilement aux fonctions hyperarithmétiques par l'ajout d'une clause supplémentaire).

[#5] Je crois qu'en fait le plus standard est de décider que E(f) vaut 0 si f:ℕ→ℕ prend au moins une fois la valeur 0, et 1 si elle est constamment non-nulle. Ceci n'a, évidemment, aucune importance fondamentale.

[#6] On pourrait du coup objecter que ma notion de fonction/machine hyperarithmétique n'est pas si naturelle que ça, puisqu'elle dépend de cet ordinal ωCK. (Et il est vrai que d'autres ordinaux sont naturellement associés à d'autres notions de calculabilité elles aussi plus ou moins naturelles : je mentionnais par exemple le plus petit ordinal « récursivement inaccessible », qui est associé aux machines qui ont la capacité de décider si une suite f(0), f(1), f(2), etc. calculée par elles-mêmes, comporte une infinité de valeurs non-nulles ; beaucoup de résultats que je mentionne se transposent à de telles machines — mais pas tous, parce que par exemple cela change alors des choses de relaxer la contrainte que tous les f(i) soient définis : le point (♣) du corps du texte ne s'applique pas ici tel quel.) Néanmoins, le choix de ωCK est un choix particulièrement important et naturel : c'est le plus petit ordinal qui n'est pas manipulable par une machine de Turing ordinaire (au sens où aucun bon ordre sur les entiers calculable par une machine de Turing n'a pour type ωCK, alors qu'ils peuvent avoir pour type tous les ordinaux plus petits) ; et après l'ordinal ω des entiers naturels, c'est le plus petit pour lequel on ait une notion de calculabilité qui se comporte vraiment bien.

[#7] Notamment parce que les hiérarchies sous-récursives, i.e., la diagonalisation itérée à partir des fonctions primitives récursives, se construisent non pas à partir d'ordinaux mais à partir de notations ordinales, et il est en gros impossible d'atteindre toutes les fonctions calculables de la sorte ; alors que la hiérarchie hyperarithmétique se construit vraiment à partir d'ordinaux (elle ne dépend pas de la notation choisie pour un ordinal donné) et elle atteint toutes les fonctions hyperarithmétiques.

(samedi)

Tout va bien pour moi

Puisque j'ai reçu des messages de quelques personnes s'inquiétant pour moi après les événements d'hier soir à Paris, il est peut-être utile que je précise que ni moi ni mon poussinet (ni, pour autant que je sache pour l'instant, personne que je connaisse) ne faisons partie des victimes. Pour ne pas céder à la terreur, nous avons tenu à passer notre samedi normalement (manger au restaurant, nous promener), ou du moins aussi normalement que possible étant donné que les cinémas sont fermés, comme les parcs et jardins, et beaucoup de commerces.

Only the 20 most recent entries were included above. Continue to older entries.

Seules les 20 plus récentes entrées ont été incluses ici. Continuer à lire les entrées plus anciennes.


Entries by month / Entrées par mois:

2016 Jan 2016
2015 Jan 2015 Feb 2015 Mar 2015 Apr 2015 May 2015 Jun 2015 Jul 2015 Aug 2015 Sep 2015 Oct 2015 Nov 2015 Dec 2015
2014 Jan 2014 Feb 2014 Mar 2014 Apr 2014 May 2014 Jun 2014 Jul 2014 Aug 2014 Sep 2014 Oct 2014 Nov 2014 Dec 2014
2013 Jan 2013 Feb 2013 Mar 2013 Apr 2013 May 2013 Jun 2013 Jul 2013 Aug 2013 Sep 2013 Oct 2013 Nov 2013 Dec 2013
2012 Jan 2012 Feb 2012 Mar 2012 Apr 2012 May 2012 Jun 2012 Jul 2012 Aug 2012 Sep 2012 Oct 2012 Nov 2012 Dec 2012
2011 Jan 2011 Feb 2011 Mar 2011 Apr 2011 May 2011 Jun 2011 Jul 2011 Aug 2011 Sep 2011 Oct 2011 Nov 2011 Dec 2011
2010 Jan 2010 Feb 2010 Mar 2010 Apr 2010 May 2010 Jun 2010 Jul 2010 Aug 2010 Sep 2010 Oct 2010 Nov 2010 Dec 2010
2009 Jan 2009 Feb 2009 Mar 2009 Apr 2009 May 2009 Jun 2009 Jul 2009 Aug 2009 Sep 2009 Oct 2009 Nov 2009 Dec 2009
2008 Jan 2008 Feb 2008 Mar 2008 Apr 2008 May 2008 Jun 2008 Jul 2008 Aug 2008 Sep 2008 Oct 2008 Nov 2008 Dec 2008
2007 Jan 2007 Feb 2007 Mar 2007 Apr 2007 May 2007 Jun 2007 Jul 2007 Aug 2007 Sep 2007 Oct 2007 Nov 2007 Dec 2007
2006 Jan 2006 Feb 2006 Mar 2006 Apr 2006 May 2006 Jun 2006 Jul 2006 Aug 2006 Sep 2006 Oct 2006 Nov 2006 Dec 2006
2005 Jan 2005 Feb 2005 Mar 2005 Apr 2005 May 2005 Jun 2005 Jul 2005 Aug 2005 Sep 2005 Oct 2005 Nov 2005 Dec 2005
2004 Jan 2004 Feb 2004 Mar 2004 Apr 2004 May 2004 Jun 2004 Jul 2004 Aug 2004 Sep 2004 Oct 2004 Nov 2004 Dec 2004
2003 May 2003 Jun 2003 Jul 2003 Aug 2003 Sep 2003 Oct 2003 Nov 2003 Dec 2003