Comments on Le lemme de Higman expliqué aux enfants

Une petite question: dans la preuve, pourquoi s’embêter à garder le préfixe de la suite qui ne commence pas par la lettre-clé ? Il suffirait de garder seulement les mots qui commencent par la lettre-clé et retirer celle-ci non ? La preuve serait plus simple, du coup je me dis que je rate surement quelque chose qui fait qu'on doit garder ce préfixe…

PS : Ca faisait longtemps que je n'avais pas relu l'entrée de Ruxor. Il parle bien de la différence entre "forcément fini" et "borné". (Après, une double couche avec des mots différents est rarement nuisible…)

@Dyonisos : Ruxor a raison sur le fait que le sujet du "fini" est très subtil, mais peut-être que sa réponse l'est un peu trop, là où un peu de grossier, de terre à terre pourrait être le bon niveau où placer la discussion pour le profane (l'enfant, on disait).

Je vais donc dire ""ce que pense le mathématicien au quotidien"", et qu'on peut ensuite nuancer/remettre en question quand on essaie d'avancer philosophiquement ou (méta-?)mathématiquement sur la question.

Un nombre fini, bah c'est juste un nombre fini. Il y a des nombres finis petits comme 4, et des très grands comme quinze milliards de milliards de milliards de milliards de milliards de milliards (qui n'est pas si grand que ça pour Ruxor, mais c'est grand quand même déjà).

Limite, ça se passe de définition (un peu comme pour le temps, je pense que c'est intéressant de s'interroger sur la définition, mais qu'on atteint souvent une intuition fiable du sujet avant d'en avoir une définition). Un nombre fini, c'est un truc que tu peux écrire comme "1 + 1 + 1 + … + 1". Dans le cas du grand nombre précédent, c'est sûr qu'il te faudra du temps et du papier, mais on y va ! ((Et on y va dans un univers où on est immortel avec un stock illimité de papier et de stylo. Toutefois, malgré tous ces no-limits, il faut qu'on rende la copie à un moment hein : il y a un dernier "+1" sur la copie ! (Sauf si on parle de 0 ou de 1, auquel cas on écrit juste ce nombre et il n'y a pas besoin de +1, mais on s'en fiche, n'est-ce pas ?)))

Eh bien voilà, c'est ça fini !

Et infini, c'est quelque chose qui n'est pas fini : par exemple, si le mec immortel déchire une feuille de papier par jour pendant toute sa vie, bah "à la fin des temps", il a déchiré une quantité infinie de feuilles de papier. Ah, oui problème : pas de "fin des temps" si le temps est "infini", c'est vrai… Eh bien la phrase précédente, on peut lui donner le sens précis suivant : si je considère les feuilles de papier qui, à un certain instant (passé, présent ou futur), sont déchirées, l'ensemble des feuilles de papier que je considère n'est pas fini. ((C'est peut-être légèrement abstrait, mais ça a bien un sens : j'ai défini "fini", et je peux bien m'intéresser aux feuilles dont le destin est d'être déchirée à un moment.))

Donc normalement, voilà : fini a un sens accessible à l'intuition, infini est le contraire de fini, et on a vu plus haut un exemple de chose infinie (autre exemple : l'ensemble de tous les nombres entiers ; car sinon, il y en aurait un plus grand, mais c'est pas possible car on peut lui ajouter 1).

Ensuite, "ce que dit Ruxor", c'est que "fini" ne veut PAS dire "petit" ! Ainsi, si le lemme nous dit qu'en suivant telle stratégie, on sera quand même bloqué au bout d'un nombre fini d'étapes, eh bien c'est vrai (après tout, on l'a démontré), mais il reste malgré tout possible (et oui oui, ça arrive) que ce nombre excède douze milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards de milliards. A cause de cela, même avec de bons ordinateurs, en faisant beaucoup d'étapes par seconde, il est possible que notre stratégie ne soit pas bloquée de notre vivant, ou avant la fin de la vie sur Terre. Elle le sera, mais c'est juste qu'il faut attendre trèèèèèèèèèèès longtemps ! (Et qu'en "pratique", peut-être que l'univers cessera d'exister d'ici-là.)

Je pense que c'est ainsi qu'il faut aborder la chose (et qu'eeensuite, on peut élaborer sur des subtilités, des contrepoints, mais chaque chose en son temps).

Donc en un mot, "fini", bah ça qualifie les nombres entiers quoi (26, ou 1729, ou 45622333258996, ou 89789521269895623226989995699863343465668322464649797752232666443434343343431692956535262622263234416738992827976837257627793429673524824924392579237529732976327969759576527962796), "infini" qualifie ce qui n'est pas fini (exemple : l'ensemble de TOUS les nombres entiers), et on peut être fini mais très très grand.

((Et pour en revenir au message de Dyonisos : ce n'est pas tant que le jeu ne s'épuisera "jamais" mais qu'il s'épuisera peut-être "trèèèèèèèès très tard".))

[Une autre subtilité autour du sujet, c'est la différence entre fini et borné. Considérons des chaussettes, rassemblées en blocs. Si mes blocs sont des paires de chaussettes, eh bien mes chaussettes sont deux par deux. Si je suis un fou du repassage et que je veux repasser mes chaussettes, et qu'une chaussette me prend une minute à repasser, eh bien quel que soit le bloc que tu choisis, je sais à l'avance que je n'ai besoin de me réserver que deux minutes dans mon agenda pour repasser les chaussettes du bloc que tu sélectionneras. Et c'est vrai même si tu as le choix entre une infinité de PAIRES de chaussettes : on s'en fiche complètement en fait, une fois que tu m'auras tendu la paire, seul le nombre de chaussettes à repasser m'importera !

Même remarque si mes blocs comportent chacun 12 chaussettes : je n'ai qu'à bloquer 12 minutes dans mon agenda…

Si maintenant, j'ai un bloc de 1 chaussette, un bloc de 2 chaussettes, un bloc de 3 chaussettes, etc. Et que j'ai de la sorte précisément un bloc de N chaussettes pour chaque entier naturel N, rien de plus, rien de moins… eh bien alors… je suis bien embêté ! Si je me réserve 30000 minutes, tu risques de choisir un bloc de 30001 ou 926222157 chaussettes et je n'aurai pas le temps de tout faire. On dit qu'on est dans une situation où le temps que j'aurai à travailler n'est pas *borné* : ça paraphrase juste le fait que je ne peux pas prévoir à l'avance une surestimation du temps que j'aurai à repasser. Pourtant, ce temps sera fini dans tous les cas : le bloc que tu choisiras aura un certain nombre N de chaussettes, et au bout de N minutes je serai de nouveau libre comme l'air. On a donc un exemple de situation qui se règle toujours en temps fini, mais pas en temps borné. Il faut prendre le temps de digérer cela, mais j'ai tout dit.

Evidemment, un exemple qui serait un peu neuneu serait qu'il y ait un bloc avec une infinité de chaussettes : dans ce cas, tu peux me faire travailler un temps infini, et donc a fortiori le temps n'est pas borné (s'il est possible que je travaille pour toute l'éternité, j'aurai du mal à me fixer une date à partir de de laquelle je suis libre comme l'air, c'est clair ; ce qui est moins clair mais bien possible, on l'a vu, c'est d'avoir quelque chose de toujours fini mais néanmoins non borné).]

Si ça peut aider…

I think this should be filed under the math category <URL: http://www.madore.org/~david/weblog/math.html >.

J'ai commis une erreur en oscillant entre deux cas de figure bien distincts :
1) soit on se donne l'hypohtèse que le nombre écrit est fini bien qu'on n'en observe pas le terme. Alors le lemme doit valoir, et aucune différenciation à établir entre le mathématicien classique et l'intuitionniste.
2) soit on est juste en face de quelqu'un qui prétend qu'il est fini mais ce n'est pas une hypothèse a priori. Probablement que le lemme ne s'applique ni pour le mathématicien classique ni pour l'intuitionniste et qu'on est en dehors de son champ de pertinence car rien ne nous assure qu'on n'est pas en train d'écrire un nombre infini.

ah ok thanks. J'en retiens, à tort ou à raison, que le nombre très grand fini qu'on écrit sans cesse rentre bien dans ce lemme en théorie, même si le jeu ne s'épuise jamais, et que ce lemme dans ce cas n'est ni réfuté ni confirmé. C'est juste qu'il ne s'applique pas vraiment bien que 'dans le monde fini au sens des mathématiciens , d'une certaine manière il devrait s'appliquer si on pouvait prendre un point de vue de Sirius où ce nombre fini par hypothèse se verrait borné. J'ai l'impression persistante que la preuve constructive fini exigée par l'école intuitionniste ne se trouve pas tout à fait remplie ici : à celui qui prétend écrire un mot fini quoiqu'il ajoute sans cesse des lettres, moi, je le suspecterais de vouloir écrire un mot infini qui ne s'arrête jamais et je ne me contenterais pas de sa déclaration d'intention !

Il y a un aspect que j'ai mal saisi dans l'histoire du jeu s'épuisant pour peu que les mots sont finis. Qu'est-ce qui se passerait dans l'hypothèse où quelqu'un écrirait un mot indéfiniment long (par exemple une suite accumulative de a) et prétendait pourtant que le mot n'est pas infini, qu'il a juste en vue un mot plus grand et ainsi de suite et qui pourtant ne s'arrêterait pas ? Je crois qu'on ne pourrait pas dire qu'il ne joue pas la règle du jeu (après tout, on n'a indiqué aucune longueur maximale) et pourtant il ne s'exposerait jamais ainsi à l'épuisement du jeu. Le lemme de Higman a-t-il encore une pertinence dans ce genre de contexte ? A tout hasard, est- ce qu'il y aurait un recoupement possible entre la divergence des intuitionnistes et des mathématiciens classiques sur ce point, les premiers disant non ce lemme n'est pas absolument fondé parce qu'il n'est pas suffisamment constructiviste et les seconds disant "ça ne compte pas, on sait par hypothèse que le mot est fini même s'il est très grand donc le lemme doit valoir aussi ici." Rapprochement sans doute complètement bidon mais je ne saisis vraiment pas de quoi il retourne dans cette expérience de pensée.

Bonjour,

en tant que non informaticien (et donc non totalement matheux) j'ai adoré la première démonstration, j'ai été perdu dans la deuxième.

Deux points:

* J'ai du mal à voir en quoi l'énoncé du lemme en.wikipedia est équivalente à la tienne (d'ailleurs cette dernière je ne la comprends pas vraiment, mais le peu que je comprenne me semble totalement différent)

* pour l'exemple des aaaaaa… au lieu de prendre un grand nombre de a, aaaa et aaaaa me paraîtraient un bon compromis

@Sébastien :

Merci pour ces explications, qui ne font que confirmer ce que j'avais fini par comprendre grâce aux explications de David et à la Wikipédia (l'exemple des irrationnels a et b tels que a^b soit rationnel y est, un peu mieux expliqué, à l'article "Tiers exclu", et c'est un très bon exemple).

Pour "De deux choses, l'une", c'est ce que je suggérais dans mon premier message, et je pense que c'est ce qui est le plus clair en langage naturel.

Pour le "Voyons", c'est toute la différence entre la logique classique et la logique intuitionniste, si j'ai bien compris. Les intuitionnistes disent que si on dit "Voyons", il faut vraiment pouvoir voir ; les classiques disent que c'est juste une façon de parler. Je précise que j''étais intuitionniste malgré moi en rejetant ce "voyons".

@Ruxor : Merci pour ce post !

@Non-matheux : Je ne sais pas si ça éclaire quoi que ce soit, mais j'aurais tendance à dire qu'au lieu de penser en termes d'omniscience (terme peu employé par la majeure partie des mathématiciens au quotidien), tu peux penser en termes de disjonction de cas.

"Deux de chose l'une, soit j'ai 'ça' (n'importe quelle propriété), soit j'ai son contraire. Je vais tester les deux cas et si j'ai ma conclusion, dans un cas comme dans l'autre, la conclusion sera démontrée. Quand bien même il me serait impossible de trancher entre 'ça' et son contraire. D'ailleurs, peut-être même que 'ça' est une propriété qui dépend d'un paramètre (du genre 'tu as fixé un nombre n et te demandes si ce nombre n est pair') et est tantôt vraie, tantôt fausse : peu importe !"

Je pense que ce mode de raisonnement est un peu surprenant la première fois, mais qu'on accepte volontiers sa légitimité une fois que ses règles sont clairement énoncées.

(Une démonstration tordue de ce genre est la suivante. Les matheux trouvent souvent ce côté tordu élégant. Tu veux montrer qu'il existe deux nombres irrationnels (peut-être égaux) A et B tels que A puissance B soit rationnel. Admettons le fait que racine de deux est irrationnel (c'est un théorème). De deux choses l'une. Soit prendre A = racine de deux et B = racine de deux fait l'affaire (auquel cas on a démontré ce qu'on voulait). Soit ce choix de A et B ne fait pas l'affaire. Dans ce cas, on pose A = "racine de deux" puissance "racine de deux", et B = racine de deux. Quand on écrit "A puissance B", on obtient alors "racine de deux" puissance "{racine de deux} fois {racine de deux}", ce qui donne "racine de deux" puissance deux, donc deux. Deux est rationnel, B est irrationnel et, parce qu'on étudie le cas où le premier choix de A et B (racine de deux pour chaque) ne fait pas l'affaire, le nombre A est irrationnel. Donc on a démontré la conclusion recherchée !!)

Cette démonstration est troublante car elle ne nous dit pas du tout quelle solution est la bonne. Elle l'est également car, dans un des deux cas, on travaille sous une hypothèse fausse. Ca fait bizarre, au premier abord, de travailler sur une base fausse en mathématique ! Par exemple, imaginons que racine de deux puissance racine de deux soit rationnel : dans ce cas, la deuxième partie de la démonstration n'est que du flan bâti sur du vide !

(En fait, on sait - mais c'est beaucoup plus dur - si c'est le cas ou pas que ce nombre est rationnel, mais j'ai pas envie de le dire car l'état d'esprit de cette démonstration que d'ignorer ce point et de fournir une démonstration légitime malgré cette ignorance.)

Mais bon… Non, il n'y a pas de problème à travailler sur du vent : seulement, si on veut en tirer du "quelque chose", il faut un certain savoir faire. Une façon de mal brasser du vent est de seulement faire des postulats de départ qui s'avèrent complètement faux et d'en déduire méticuleusement des choses sans jamais atteindre de contradiction (c'est-à-dire sans jamais démontrer une chose et son contraire). A ce stade, la seule utilité de ce résultat est de nous fournir nos conclusions dès qu'on arrive à vérifier en pratique nos postulats… ce qui ne sera jamais le cas puisque nos postulats sont complètement faux !

Notons toutefois que la déduction "Si j'ai ces postulats, alors j'ai telles conclusion" n'en est pas moins correcte. On vient de voir que cette déduction était TOTALEMENT INUTILE ET CREUSE en l'état, soit, mais elle n'est pas fausse pour autant ! Si elle était fausse, ça voudrait dire que je pourrais la contrer, c'est-à-dire avoir ces postulats mais pas une de ces conclusions… ce qui n'est pas possible si les postulats sont faux, impossibles à avoir !

Une bonne façon de brasser du vent est la disjonction de cas. On dit qu'on est dans un cas BLA ou "pas dans le cas BLA". Dans le cas BLA, on démontre CONCLUSION. Dans le cas "pas BLA", on démontre CONCLUSION. Eh bien, à la fin, on obtient bien CONCLUSION, sans la moindre hypothèse : un résultat tangible ! Si on a pu obtenir du tangible à partir de "vent potentiel", c'est grosso modo parce qu'une fois on a fait du vent et l'autre fois de la substance. Ce qui est perturbant, c'est qu'on ne sait jamais à quel moment on fait de la substance… D'où l'importance dans une disjonction de cas d'être certain que nos cas couvrent toutes les possibilités.

(Bon, entre "BLA a lieu" et "BLA n'a pas lieu", il est intuitivement clair qu'on est obligé d'être dans un cas ou dans l'autre. Mais si je dis "On va étudier les cas où l'entier considéré est une puissance de 2, le cas où il est une puissance de 3, le cas où son dernier chiffre est {0, 1, 5 ou 7}, et le cas où mon nombre est supérieur ou égal à 10". Est-ce que je couvre tous les cas ? En l'occurrence, il manque le nombre 6, donc si je veux fonder une démonstration sur cette répartition en cas, je devrais ajouter le cas "mon nombre vaut 6", ou un cas qui englobe 6.)

Une "autre" bonne façon de brasser du vent est le raisonnement par l'absurde expliqué par Ruxor. Tu veux montrer CONCLUSION ? Eh bien pose comme postulat logique de départ que CONCLUSION est faux, et chercher une contradiction (démontre une chose et son contraire). Arrivant à une contradiction, cette fois, tu sais que tu est forcément en train de brasser du vent, du vide ! Si tu n'as fait qu'une hypothèse au départ (en l'occurrence que CONCLUSION est faux), celle-ci se doit d'être erronée… et voilà, tu as démontré quelque chose !

Là encore, si tu as obtenu quelque chose de tangible, c'est parce que tu n'as pas fait QUE brasser du vent : tu as acquis la CERTITUDE que tu étais en train de brasser du vent, en mettant le doigt sur une contradiction.

En gros, dans la mauvaise façon de brasser du vent, tu fais une hypothèse fausse et tu démontres un truc avec : tu as payé 1 (une hypothèse) et reçu 1 (une conclusion)… tu en tires 1-1=0… rien de tangible !

Dans le cas d'un raisonnement par l'absurde, tu fais une hypothèse fausse et tu démontres deux choses avec (une chose et son contraire). Tu en tires 2-1=1 résultat. Il ne faut pas pousser ces calculs trop loin. J'entends dire par là qu'en manipulant mal ce genre de calculs, on peut faire dire de grosses bêtises. Toutefois, en les manipulant bien, on peut sentir, palper des choses pertinentes côté logique.

Côté disjonction de cas, tu considères un certain nombre N de cas, tu démontres dans chaque cas ta conclusion, et tu as préalablement démontré (c'était peut-être très facile, comme quand on considère une chose vs son contraire) que les cas couvraient toutes les possibilités. Tu as donc payé N, reçu N… plus 1 ! Tu reçois 1 par "résultat démontré", et le fait que tous les cas ont été couverts compte ! Tu as "donc" bien un résultat qui tombe à la fin !

Bref, l'unique but de ces calculs est de montrer que le théorème qui arrive à la fin n'arrive pas par magie après avoir agité les mains : tout résultat qui tombe est le fruit d'un travail (parfois petit mais jamais nul). Si on en est à "faire la morale de l'histoire", un truc important à comprendre est "comment bosser rigoureusement sur des postulats qui s'avèrent faux peut servir à produire de la vraie connaissance". J'espère qu'en combinant les explications de Ruxor, les miennes et un peu de réflexion personnelle, ce point devient clair.

Enfin, j'aimerais revenir sur l'histoire d'omniscience. Que veut dire ce terme et que ne veut-il pas dire ? J'ai l'impression que ce que Ruxor voulait juste dire, c'est qu'on part du principe que toute propriété est soit vraie soit fausse. Ce qui est assez naturel (et n'est pas remis en cause par le théorème d'incomplétude). Bien sûr, une propriété dépendant d'un paramètre (genre "l'entier N est pair") peut être tantôt vraie, tantôt fausse. Mais tant que les propriétés sont exprimées dans le langage inambigu des choses mathématiques, quand on choisit des paramètres, c'est soit vrai soit faux ! L'omniscience dont parle Ruxor ne dit pas qu'on sait ce qui est vrai ou faux, seulement que ce "vrai ou faux" "existe quelque part". Bref, tout truc est vrai ou faux, c'est juste qu'on sait pas forcément encore lequel des deux c'est (et peut-être qu'on le saura jamais).

Partant de ce principe, on peut disjoindre des cas par exemple. Alors que si on ne décrète un truc vrai que si on arrive à la démontrer/vérifier par exemple, il se pourrait que des choses ne soient ni vraies ni fausses (fausses voulant dire dans ce cas "de contraire démontrable"). Il s'avère que c'est le cas : il existe des choses "intranchables", "indécidables", "indécises", "inaccessibles" quand on bosse dans le socle mathématique usuel (un socle unique qui convient aussi bien à la démonstration des vérités probabilistes, géométriques, algébriques, etc.). C'est justement ce que dit le théorème d'incomplétude.

Bref, oublions ce théorème un peu compliqué : c'est pas déraisonnable qu'il y ait des choses mathématiques qu'on n'arrive ni à infirmer ni à confirmer. Si ce n'était pas le cas en pratique en tout cas, eh bien ça signifierait que la recherche mathématique serait épuisée, ce qui n'est pas DU TOUT le cas.

Et j'ai l'impression que ton problème avec "voyons", Non-matheux, résidait dans le fait que tu ne voyais pas comment trancher dans un sens ou dans l'autre. Ce à quoi Ruxor a répondu en invoquant l'omniscience, non pour dire qu'on peut tout savoir nous, mais qu'il y a bien quelque part un vrai et un faux bien défini. Ce n'est pas nous qui sommes omniscients (ni en pratique… ni même en principe puisqu'il y a des vérités qui sont démontrées inaccessibles), mais le "quelque part qui dit que le vrai et le faux sont bien définis".

Si le théorème d'incomplétude ne remet pas en cause le fait que le vrai et le faux existent, il est toutefois possible de remettre en cause cela et de ne dire qu'une propriété est vraie ou fausse que quand on arrive à "trouver une procédure de vérification raisonnable qui permettrait de trancher cette question". Raisonnable pouvant par exemple consister à faire tourner un ordinateur "pendant un temps infini" si ça ne te choque pas.

Si tu crois que les objets qui tu manipules "existent pour de vrai", tu seras probablement enclin à accepter que le vrai et le faux existent…

La plupart des mathématiciens travaillent en acceptant que le vrai et le faux existent sans qu'on ait à leur donner un sens à chaque fois.

Bon, il faut que j'y aille. J'espère que ce n'était pas trop obscur et qu'il y avait quelque chose à tirer de mon blabla.

Voici pour conclure un très beau raisonnement par l'absurde !

https://www.youtube.com/watch?v=92WHN-pAFCs

@Ruxor :

* En effet, il serait intéressant de voir d'un point de vue linguistique comment les mathématiciens rédigent « en langage naturel » et en quoi ce que les non matheux lisent diffère de ce que les mathématiciens y lisent. Je pense que les premiers seraient beaucoup plus sensibles à la lettre du texte, parce qu'ils ont l'image des mathématiques comme quelque chose d'extrêmement rigoureux, alors que les mathématiciens s'intéresseront plus à la démarche et au résultat, manipulant certaines conventions sans même s'en apercevoir.

* L'histoire du tiers exclu me rappelle l'histoire de la bataille navale d'Aristote. D'après lui, la phrase « La bataille navale aura lieu demain. » n'est ni vraie ni fausse, parce que si elle était l'un ou l'autre maintenant, cela voudrait dire que le futur est déjà écrit, ce qu'il rejette.

* Cette histoire de Dieu omniscient et menteur à la barre me rappelle la fameuse énigme des dieux dont il faut deviner l'identité en trois questions. La connais-tu ?

@Ruxor :

Merci pour ta réponse.

Je suis suffisamment convaincu par ce que tu dis entre parenthèses (l'équivalence sémantique), parce que tout ça, ce n'est qu'une question de présentation, finalement, et que je m'en remets à ton expertise pour ce qui peut se dire ou pas, parce que les maths, même en langage naturel, ça reste des maths. À choisir, je préfèrerais néanmoins la tournure sans « voyons ».
Est-ce qu'un mathématicien dirait : « Voyons si l'hypothèse de Riemann est vraie : si oui, alors n=0 ; si non, alors n=1 » ? Ne préférerait-il pas : « n vaut 0 si l'hypothèse de Riemann est vraie et 1 si non » ?

Le 2 a l'avantage, à mon sens, de ne pas requérir l'omniscience alors que 1 oui (du moins, si l'hypothèse de Riemann est indémontrable).

C'est un avantage encore plus important pour les non matheux parce que l'omniscience, c'est comme l'infini : même si on peut en parler en langage naturel, ça peut aussi amener à commettre involontairement des sophismes, parce que ça brouille la logique : je pense que les mathématiciens sont bien mieux armés pour ça que les autres même quand le raisonnement se fait avec les mots de tous les jours.

Exemple classique : j'ai un hôtel dont toutes les chambres sont occupées. L'empereur arrive et je dois lui libérer une chambre sans virer aucun client. En toute logique, c'est impossible, mais si mon hôtel a une infinité de chambres, je peux mettre les occupants de la 1 dans la 2, ceux de la 2 dans la 3, etc. Est-ce « logique » ? Oui, au sens où, une fois qu'on a expliqué le truc, n'importe qui peut le comprendre. Non, au sens où si l'hôtel est complet, on ne devrait pas pouvoir libérer une chambre.

Bon, tout ça pour dire que j'ai un peu du mal à être « logique » quand il y a des histoires d'infini, et que je fais confiance aux mathématiciens pour savoir comment on manipule ça logiquement.

Pour l'omniscience, je ne pas sûr d'avoir bien compris ton exemple avec Dieu : si Dieu dit qu'il existe une suite miraculeuse, alors il ment. S'il peut mentir, ça nous fait une belle jambe qu'il soit omniscient : il peut y avoir contradiction entre une vérité et un mensonge… (Je n'ai pas l'impression de raisonner de manière très mathématique, là encore.)

Sinon, aurais-tu un autre exemple (simple) où un mathématicien raisonnera typiquement comme s'il était omniscient ?

@Ruxor :

Ce qui me gêne, c'est qu'autant je conçois facilement qu'on puisse, si l'on dispose d'un temps infini, vérifier si telle suite est merveilleuse ou non, autant j'ai plus de difficulté à voir comment déterminer si tel ou tel mot peut commencer une suite merveilleuse ou non. Dois-je construire l'ensemble (infini) des suites à partir de ce mot et vérifier si parmi elles, il y en a une qui est merveilleuse ? À ce compte-là, je pourrais aussi construire toutes les suites possibles à partir de tous les mots et vérifier si parmi elles, il y en a une qui est merveilleuse…

De même pour « omniscient » : si je suis omniscient, je sais d'emblée s'il existe une suite merveilleuse.

…..

Bon, en fait, en retournant le problème et ta réponse dans ma tête, j'arrive à la conclusion que ce qui m'embarrasse, c'est cette phrase : « essayons de lui retirer sa première lettre, et voyons s'il peut encore commencer une suite miraculeuse (éventuellement complètement différente) ». Je ne dirais pas « voyons si », parce que sinon, je tombe sur les difficultés que je mentionnais plus haut, mais plutôt : « de deux choses l'une : soit ce nouveau mot peut commencer une suite merveilleuse (a), soit il ne le peut pas (b). Je n'ai pas besoin de savoir la réponse, mais si (a), je fais X, si (b), je fais Y. ». Cela suffit pour montrer que si une suite merveilleuse existe, alors une suite merveilleuse minimale existe en droit, même si je ne sais pas la construire.

Je serais intéressé à savoir ce que tu en penses : est-ce que ce « voyons » est gênant pour un mathématicien ou non ?

Mon impression de non matheux : la démonstration se suit très bien, mais semble un peu tordue. En gros, tu réduis ta suite merveilleuse, puis tu montres qu'elle peut être encore réduite, donc la suite merveilleuse n'existe pas. Je te crois sur parole, mais la première méthode de réduction de la suite ne me paraît pas aller de soi, car elle peut donner une suite complètement différente. Du coup, on a l'impression que ce qui n'existe pas, c'est une suite merveilleuse minimale…

Et si je savais vérifier qu'une suite est merveilleuse (en un temps infini), mais pas vérifier que tel ou tel mot peut commencer ou non une suite merveilleuse ?

Ce sont des réflexions de non matheux, hein…

J'aurais envisagé une démonstration comme :
- je prends la plus petite chaîne de ma liste
- je montre qu'il est impossible de construire une infinité de chaînes plus grandes sans répéter au moins une fois les caractères de ma chaîne minimale dans l'ordre (avec éventuellement des caractères entre).
Est-ce qu'une telle démonstration est possible/envisageable ?

[Il y a un "soient" qui devrait être "soit" dans ton texte.]

Formidable, je plébiscite l'idée ! D'ailleurs, j'ai tout lu - lentement - et je crois bien que j'ai compris…

En réponse à un sujet évoqué dans l'intro, à savoir l'utilité des math expliquée aux non matheux, j'aime bien l'analogie avec la musique : certes, la musique est parfois utile - la diffusion de certains types de musique favorise la consommation dans les grandes surfaces, améliore le sentiment de sécurité des parkings, etc. - mais ce n'est pas pour ça que les musiciens font de la musique ! C'est parce que "c'est beau", autrement dit ça doit activer des tas d'hormones liées au plaisir. De mon point de vue, rien ne distingue particulièrement les math d'une activité artistique… si ce n'est que c'est "utile" plus souvent.

Pardon, c'est moi qui ai loupé le (a) en fait.

Tu as laissé "cadabra" dans ta suite miraculeuse minimale sans z initial

Je ne suis pas un non-mathématicien mais je pense que ta démonstration est sans doute bien pour montrer à quoi ressemble une preuve. Par contre le lecteur va sans doute devoir te faire confiance par moment: sans noms de variables c'est un peu difficile à suivre (surtout pour quelqu'un qui n'en a pas l'habitude).