<foo> simply produces <foo>in the text).
<URL: http://somewhere.tld/ >,
and it will be automatically made into a link.
(Do not try any other way or it might count as an attempt to spam.)mailto: URI,
e.g. mailto:my.email@somewhere.tld,
if you do not have a genuine Web site).
Ruxor (2021-12-02T15:58:31Z)
@glocq: Il est correct que « ψ(ε₀) = ε₀ peut être atteint en appliquant ψ à une valeur <ε₀+1 », mais (dans la définition qui permet de calculer ψ(α)) pour avoir le droit d'appliquer ψ|_α à un ordinal β (ici ε₀), il faut que cet ordinal β ait lui-même été construit au moyen des fonctions d'addition, d'application de ψ|_α et de (γ,ξ)↦Ω^γ·ξ. Autrement dit, on a le droit d'utiliser ψ (dans l'énumération des termes dont ψ(α) est le plus petit exclu) à condition que son argument β soit À LA FOIS déjà construit par les opérations autorisées ET AUSSI <α. Or ici, si α = ε₀+1, on a bien ε₀ < ε₀+1 mais on ne peut pas construire ε₀ par application des fonctions autorisées.
Il est vrai que j'aurais pu être plus clair !
glocq (2021-12-02T15:06:06Z)
Merci pour cet article et les nombreux autres dans ce style sur ce blog. Il n'y a pas assez d'articles qui expliquent des notions techniques sur un ton conversationnel comme ça sur internet.
Je bloque sur un point qui semble être un détail, mais outre lequel je n'arrive pas à passer. C'est dans les paragraphes qui expliquent le fonctionnement de ψ (après « Essayons d'expliquer ce que ça signifie. »)
Si j'ai bien lu le paragraphe :
• Pour tout α < ε₀, ψ(α) = ω^α
• Pour tout α entre ε₀ et Ω, ψ(α) = ε₀.
Ça me semble aboutir à une contradiction ; notamment, il me paraît évident que ψ(ε₀+1) ≠ ε₀. Je donne mon raisonnement très détaillé en espérant que quelqu'un puisse me dire où je me trompe :
ε₀ < ε₀+1, donc ψ(ε₀) = ε₀ peut être atteint en appliquant ψ à une valeur < ε₀+1. Donc ε₀ ne fait pas partie des ordinaux qui ne peuvent pas être atteints par addition, application de ψ|_(ε₀+1) et application de la fonction qui fait intervenir Ω ; en particulier, ça ne peut pas être le plus petit de ces ordinaux, or c'est la définition de ψ(ε₀+1) ; donc ψ(ε₀+1) ≠ ε₀.
Voilà, si une âme charitable peut m'expliquer où je me suis planté, elle aura droit à ma gratitude éternelle.
Ruxor (2019-10-28T13:58:48Z)
@Jacques: Pour simplifier : ① La régularité (ou, aux niveaux au-dessus, la mahloïtude etc.) permet d'assurer que les fonctions qu'on définit sont bien définies, justement : les limites qu'on veut prendre existent automatiquement et ainsi de suite. ② Et de toute façon, ça n'a pas d'intérêt de faire autrement, vu qu'il y a autant de cardinaux réguliers que de cardinaux tout court. (Tout ça est simplifié puisqu'il y a plein de variantes des fonctions d'écrasement et tout est à prendre avec des pincettes, mais ça donne au moins l'idée.)
Jacques (2019-10-28T12:52:50Z)
Y a-t-il une raison particulière pour laquelle on ne s'intéresserait qu'aux écrasements de cardinaux réguliers ou d'ordinaux admissibles, ou pourrait-on aussi écraser des cardinaux singuliers (par exemple le premier γ=א_γ) ou des ordinaux non calculables non admissibles ?
Ruxor (2019-10-27T17:49:43Z)
@Jacques:
1re question → Le mot crucial est « régulier », cf. <URL: http://en.wikipedia.org/wiki/Regular_cardinal > (il faut comprendre la phrase « le premier cardinal régulier / ordinal admissible tel que γ=Ω_γ » comme « le premier cardinal régulier ayant la propriété supplémentaire que γ=Ω_γ (ou bien, si on préfère la version récursive, le premier ordinal admissible tel que γ=Ω_γ en interprétant Ω_γ comme la fonction énumérant les ordinaux admissibles et leurs limites) ». Il n'y a donc pas de contradiction entre le fait que le premier inaccessible κ soit le premier point fixe régulier de la fonction ℵ mais le κ-ième point fixe de cette même fonction.
2e question → Oui, il y a plein de variations entre les auteurs, et ce d'autant plus que le concept d'hyperinaccessible (quelle que soit sa définition exacte) n'a, franchement, pas grand intérêt. Un cardinal κ que certains appellent hyperinaccessible est ce que j'appellerais hyper^κ-inaccessible, et le plus petit serait, je pense, θ(M^M) avec ma notation, tandis que ce que ces gens appelleront un hyper²-inaccessible serait probablement θ(M^{M²}), et le plus petit κ qui soit hyper^κ-inaccessible serait probablement θ(M^{M^M}), bref, tout ça est à vérifier sur les définitions exactes mais on voit l'idée.
Jacques (2019-10-27T15:44:38Z)
Dans le paragraphe "Quelques idées sur des écrasements plus sophistiqués", vous avez écrit :
”θ(M) est le premier inaccessible (le premier cardinal régulier / ordinal admissible tel que γ=Ω_γ)”
Si on interprète Ω_γ comme א_γ , ça voudrait dire que le premier inaccessible serait le premier point fixe de la fonction α → א_α , ou disons le premier point fixe de א pour simplifier.
Or, dans <URL: https://mathoverflow.net/questions/117806/if-k-is-weakly-inaccessible-then-it-is-the-k-th-aleph-fixed-point > il est écrit :
”if κ is weakly inaccessible, then it is the κ-th א fixed point”
(si κ est faiblement inaccessible, alors c’est le κ-ième point fixe de א)
Il me semble qu’il y a une contradiction : selon vous, le premier inaccessible, appelons-le I, serait le premier point fixe de א, or selon le lien mentionné, I serait le I-ième point fixe de א et ne pourrait donc pas être le premier.
Y a-t-il une erreur quelque part ou j’ai mal compris quelque chose ?
D’autre part, vous avez écrit :
”θ(M²) est le premier hyperinaccessible (le premier γ qui soit le γ-ième cardinal inaccessible),"
Or, dans <URL: https://math.stackexchange.com/questions/477314/hyper-inaccessible-cardinals > il est écrit :
”κ is 1-inaccessible if and only if
κ is a limit of inaccessible cardinals if and only if
κ has κ inaccessible below it if and only if
κ is the κ-th inaccessible.”
Donc il semblerait que ce que vous appelez ”hyperinaccessible” soit appelé ”1-inaccessible” par d’autres.
Dans <URL: https://fr.wikipedia.org/wiki/Cardinal_inaccessible > il est écrit :
”Un cardinal κ est dit hyper-inaccessible si κ est κ-inaccessible”.
Cette définition est différente de la vôtre.
Y a-t-il des définitions et dénominations différentes selon les auteurs ?
Ruxor (2018-07-04T23:56:39Z)
@Jacques: Je crois que l'idée que vous proposez à la fin est celle que Feferman ou d'autres appellent les « progressions autonomes » d'une théorie. En faisant quelque chose de ce genre à partir de l'arithmétique de Peano du premier ordre (ou même certains systèmes du second ordre qui, en étant plus expressifs et plus commodes, ne sont pour autant pas plus forts du point de vue de la consistance : voir le système « ATR₀ » des mathématiques à rebours), on obtient une théorie qui permet essentiellement l'itération transfinie le long de tout ordinal dont elle démontre le bon fondement, ou quelque chose comme ça ; et Feferman mesure l'ordinal de preuve de cette théorie comme étant Γ₀ et affirme que cette construction explique que cet ordinal mesure la limite de la prédicativité. (Je dis sans doute un certain nombre de bêtises parce que ce sont des souvenirs assez flous, mais ça devrait au moins expliquer où chercher.) Je pense que l'idée est que si on fait ça à partir d'une théorie ayant un ordinal de preuve α, on doit, au moins dans de bonnes conditions, en obtenir une qui a pour ordinal de preuve le plus petit nombre Γ supérieur à α, ou quelque chose de ce goût-là : c'est certes plus grand que α, mais par rapport à la taille gigantesque des ordinaux considérés, en fait, ce n'est pas un renforcement si significatif (un peu comme prendre 10 puissance le nombre de Graham : certes, c'est beaucoup plus gros, mais en fait, on ferait sans doute mieux en changeant autrement la théorie ; par exemple, s'agissant de ZFC, il est assez clair qu'ajouter un axiome comme l'existence d'un cardinal inaccessible augmente l'ordinal de preuve de façon gigantesquement plus grande que d'essayer de fabriquer des progressions autonomes).
Bon, je ne suis pas très clair, mais ce sont des choses que je connais très mal.
Jacques (2018-07-04T20:02:10Z)
Merci pour cet article très intéressant !
Concernant le paragraphe "Comment on peut tricher pour décrire de grands ordinaux de preuve" :
Si j'ai bien compris l'idée : supposons par exemple que la plus petite preuve par ordre lexicographique p0 démontre qu'une certaine machine de Turing e0 calcule un bon ordre sur les nombres entiers naturels, par exemple l'ordre "naturel" des nombres entiers naturels, associé à l'ordinal ω. Un ordinal inférieur à ω c'est-à-dire un entier x serait représenté par (p0,e0,x). Supposons ensuite que la preuve suivante p1 démontre que la machine de Turing e1 calcule un bon ordre sur les nombres entiers naturels, et que ce bon ordre place 0 au-dessus de tous les autres qui sont ordonnés selon l'ordre "naturel". Ce bon ordre correspond à ω+1. Un ordinal ω+x serait alors représenté par (p1,e1,x+1) et ω2 serait représenté par (p1,e1,0), et ainsi de suite, c'est bien ça?
Dans ce cas il me semble qu'un triplet (p,e,x) désigne de façon précise un ordinal déterminé et réciproquement tout ordinal inférieur à l'ordinal de preuve de ZFC est représenté par un triplet (p,e,x) unique, donc dans ce sens cette notation me paraît explicite. Par contre on peut la trouver tordue, compliquée, non naturelle… ce qui constitue un problème si le but est de mieux comprendre une théorie, et effectivement une telle notation n'apporte aucune information sur la théorie.
Mais la compréhension des théories est-elle la seule raison pour laquelle on peut vouloir décrire de grands ordinaux? N'y a-t-il pas d'autres domaines d'applications dans lesquels le fait qu'une notation soit tordue ne constitue pas un inconvénient?
Je pense par exemple à l'augmentation de la puissance d'une théorie par itération transfinie d'un principe de réflexion qui équivaut à ajouter à la théorie l'axiome de sa propre consistance.
L'itération transfinie d'un principe de réflexion peut être représentée par la formule :
T'= ITPR(T,α)
où T est une théorie telle que ZFC par exemple et α un ordinal, et T' une théorie plus puissante que T, la fonction ITPR étant définie par :
- ITPR(T,0) = T
- ITPR(T,α+1) = ITPR(T,a)+Consis(ITPR(T,α))
- ITPR(T,λ) = union pour tous les entiers n des ITPR(T,λ[n]), si λ est un ordinal limite
où Consis(T) désigne un axiome qui exprime la consistance de T.
A partir d'une théorie T, on pourrait alors construire une théorie plus puissante T' par itération transfinie du principe de réflexion jusqu'à l'ordinal de preuve de T :
T' = ITPR(T,ODP(T))
où ODP(T) représente l'ordinal de preuve de T construit de façon triviale, c'est-à-dire l'ordinal correspondant à l'ensemble des triplets (p,e,x) associés à T.
On pourrait même aller plus loin en définissant une fonction à croissance très rapide ODPITPR_T qui à un ordinal α associe l'ordinal de preuve de l'itération transfinie jusqu'à α d'un principe de réflexion à partir de la théorie T :
ODPITPR_T(α) = ODP(ITPR(T,α))
puis itérer l'application de cette fonction par exemple "ODP(T) fois" pour construire l'ordinal ODPITPR_T^ODP(T)(0) qui serait beaucoup plus grand que l'ordinal de preuve de T, puis la théorie ITPR(T,ODPITPR_T^ODP(T)(0)) qui serait beaucoup plus puissante que T.
Qu'en pensez-vous?
Bob (2018-05-12T14:09:07Z)
Je me suis replongé avec délice dans cette entrée, c'est un formidable travail d'explication que tu as fait là. Ce genre d'informations me semble difficile à trouver dans les livres, c'est d'autant plus utile.
Merci beaucoup !
Alcide Nikopol (2017-09-14T19:27:32Z)
S'agissant de l'ultrafinitisme, ce qui me déconcerte, chez des gens comme Norman Wildberger (pour mentionner un exemple flamboyant), c'est qu'ils subordonnent essentiellement les mathématiques à la physique pour récuser la pertinence de la notion d'infini (ou même des très grands nombres) : c'est bien le cas lorsqu'ils contestent l'intérêt d'envisager des nombres plus grands que le nombre d'atomes de l'univers au prétexte que nos ordinateurs ne peuvent pas, même en principe, les calculer.
Mais tout ce que nous estimons savoir du monde physique procède de notre expérience empirique ainsi que de modèles *mathématiques* nous permettant d'interpréter ladite expérience. Ici se pose déjà un problème de récursivité, pourrait-on dire, quant au fait de subordonner les maths à une discipline - la physique - elle-même dépendante des maths. Plus généralement, la connaissance empirique, dont procède ultimement la physique, ne sera jamais aussi parfaite, dans son principe, que la connaissance *apodictique* (accessible grâce à notre seul esprit) caractérisant les mathématiques. C'est pourquoi il me semble moins problématique de fonder la physique (au moins pour partie) sur les maths que l'inverse.
S'agissant de la notion d'*infini* qui dérange tant Wildberger - je parle sous le contrôle des spécialistes qui fréquentent ce site - le langage formel de la théorie des ensembles n'exige pas absolument cette notion : ce n'est qu'une interprétation pertinente de certaines formules que nous donnons dans le langage courant (?). L'important, c'est que les règles formelles de la théorie des ensembles soient cohérentes, pour fournir un socle solide sur lequel déduire, à partir de ses axiomes, des résultats non-triviaux.
D'ailleurs, concrètement (et vous abordez ce point), je crois qu'il existe des programmes informatiques permettant de vérifier les preuves mathématiques humaines (écrites en langage humain avec les ellipses et imprécisions que ça entraîne souvent) en langage informatique, donc en langage formel "sérieux".
Or, si ces procédures informatiques formelles permettent d'évaluer des raisonnements fondés sur la théorie ZFC, avec ses fameux axiomes admettant l'"infini" (ou ce que les humains désignent ainsi), voilà une validation informatique, sérieuse et impartiale (non sujette aux divagations esthétiques ou métaphysiques que s'autorise le genre humain), qui aurait tout pour satisfaire un Wildberger, m'aurait-il semblé.
Après, ce que je ne suis pas sûr d'avoir compris, c'est si les calculs de logique formelle fondés sur ZFC (ou d'autres théories du même genre) sont parfois eux-mêmes de taille infinie, donc non-terminés en pratique, auquel cas ce serait effectivement gênant et Wildberger marquerait un "point" (de mon point de vue). Mais enfin, je serais étonné qu'il n'y ait aucun moyen d'embrasser par l'abstraction, par des suites de symboles *finies* ET cohérentes, même les plus incroyablement grands ordinaux ou cardinaux (à plus forte raison, il serait fâcheux de ne pouvoir le faire pour d'aussi "petits" cardinaux que ceux de N et de R).
Je ne suis pas du tout spécialiste de ces questions mais, pour ce que j'en comprends, Wildberger pourrait presque me convaincre que les nombres réels (au sens de Cantor ou de Dedekind) ne sont *pas intéressants* (ils comportent "trop" d'éléments "inutiles", qu'on n'observera jamais puisque fondés sur une suite de choix infinie) et qu'il faudrait leur substituer de "meilleures" constructions (comme son idée de "réels d'Aristote" impliquant des intervalles entre rationnels, même si sa propre idée le laisse encore insatisfait). En revanche, ce que je peux pas "acheter", mais qu'il semble bien soutenir, c'est que les mathématiques classiques (avec quelques cardinaux infinis) soient carrément *fausses* ; ce qui ne peut vouloir dire que "logiquement fausses", puisque la vérité ou la fausseté d'un énoncé mathématique dépend de son rapport logique à des axiomes dont il faut se contenter d'exiger la cohérence interne. Quant à la vérité "intrinsèque" desdits axiomes, un mathématicien *formaliste* dira, je suppose, que cette question n'a pas d'intérêt ou du moins qu'elle ne relève pas des mathématiques. Un *platonicien* ne le suivra pas forcément mais on pourrait envisager un "platonisme minimal" admettant une "preuve ontologique" non pas de l'existence de Dieu mais de celle des cardinaux transfinis (j'ai croisé cette idée quelque part) : puisqu'on peut les concevoir (sans contradiction), c'est que leur *idée platonicienne* existe, donc qu'ils existent. Un tel platonisme ne me semblerait pas en pratique différent du "formalisme" et ça ferait un schisme de moins dans les mathématiques^.
jonas (2017-09-07T19:25:45Z)
Re Foenkystos
> Lol le nom en Romaji, puis en Kanji, puis re les furigana au-dessus au cas où :-)
>
> Je suis déçu qu'il y ait pas un lien vers un ficher flac avec différentes prononciations (normale, nez bouché…) et des photos de la position de ta glotte pour chaque syllabe.
This seriously cracked me up. It's such a funny parody of David Madore's thorough writing style that I always enjoy.
Foenkystos (2017-09-05T20:36:37Z)
Lol le nom en Romaji, puis en Kanji, puis re les furigana au-dessus au cas où :-)
Je suis déçu qu'il y ait pas un lien vers un ficher flac avec différentes prononciations (normale, nez bouché…) et des photos de la position de ta glotte pour chaque syllabe.
Super article, encore un que j'arriverai jamais à finir. Faut que je lise celui sur le plan projectif complexe en entier, avant.
ooten (2017-09-03T19:00:44Z)
Y a-t-il encore de grandes questions ouvertes sur le sujet (pour moi l'hypothèse du continue en faisait bien évidemment partie) et même question en informatique en dehors de N=NP ou alors ce ne sont plus que des questions pour les spécialistes.
Ruxor (2017-09-03T18:14:03Z)
@Nick Mandatory: Concernant le bouquin de Pohlers, je le trouve vraiment difficile à lire. Après, mon intérêt pour la question n'est pas tel que je veuille quelque chose de détaillé, plutôt des surveys, et pour ça, j'ai bien aimé les notes de Rathjen intitulées "The Realm of Ordinal Analysis" et "The Art of Ordinal Analysis", et celles d'Arai intitulées "Sneak preview of proof theory of ordinals" (plus anciennes).
Nick Mandatory (2017-09-03T17:44:17Z)
Merci pour tes réponses !
(Finalement, j'ai tout lu, j'ai trouvé ça plutôt très clair, et vraiment très intéressant.)
Tu connais "Proof Theory" de Wolfram Pohlers ? J'ai lu des reviews un peu contradictoires, mais sur le papier ça a l'air d'être une intro intéressante sur le sujet…
Ruxor (2017-09-03T15:24:58Z)
@Nick Mandatory: Excellentes questions.
Le fait que le premier ordinal non calculable (i.e., non représenté par un bon-ordre calculable sur ℕ) coïncide avec le premier ordinal non hyperarithmétique (même définition mutatis mutandis) est en effet remarquable. D'autant plus que ça marche aussi avec des choses plus faibles que "calculable", comme "primitif récursif", ou même (je ne suis pas certain, mais je crois) "calculable en temps polynomial". On pouvait parfaitement imaginer a priori qu'il y ait plein d'ordinaux correspondant au « plus petit ordinal non représenté par un bon ordre appartenant à la classe de calculabilité/complexité <truc> », et c'est assez frappant qu'ils soient en fait tous égaux (ça rend l'ordinal de Church-Kleene d'autant plus remarquable).
Je n'ai pas vraiment d'explication intuitive à ce fait. (J'ai lu des démonstrations, bien sûr, et je peux fournir des références, mais ce n'est pas vraiment transparent : on ne voit pas exactement où la magie se produit.) Je peux quand même fournir deux éléments pour aider à rendre la chose moins mystérieuse :
1º, je pense que la bonne définition de l'ordinal de Church-Kleene est celle avec « hyperarithmétique », parce que les ensembles hyperarithmétiques sont stables par beaucoup d'opérations (et c'est lié au fait que le niveau ω₁^CK de l'univers de Gödel est un modèle de la théorie des ensembles de Kripke-Platek), donc la définition avec « hyperarithmétique » est plus robuste et, en un certain sens, meilleure. Mais avec « calculable », c'est plus facile à expliquer, ce qui explique qu'il soit généralement défini comme ça (puisque, in fine, ça coïncide).
2º, quant à la raison pour laquelle ça coïncide, l'idée très grossière est que, si on veut juste construire un bon ordre ayant un certain ordinal, on peut toujours pousser les entiers très loin dans la construction de l'ordre, i.e., on peut construire cet ordre très « lentement » tout en ayant le même ordinal. Ça explique vaguement pourquoi le fait de descendre en complexité ne change rien au problème (tu vas pouvoir dire, par exemple, que si tes entiers à comparer ne sont pas de la forme 10^10^n tu les compares trivialement, et ça fera juste un ω au début qui ne changera rien, et s'ils sont de cette forme, tu as gagné un facteur exponentiel de complexité pour faire ta comparaison), et je crois que l'astuce en calculabilité est vaguement du même genre, il faudrait vérifier.
Sinon, pour savoir si j'ai fait de la recherche là-dessus, non, pas vraiment. Je garde toujours les ordinaux en tête quand je réfléchis à des choses, j'ai utilisé un prétexte pour en parler dans un article commun avec Colliot-Thélène, et je joue parfois avec des idées farfelues (notamment : pourrait-on développer une cryptographie à clés publiques sur des ordinateurs transfinis ? — ce qui permettrait, par exemple, de rendre rigoureux certains arguments du style « on ne peut pas retrouver <machin> sans connaître <truc> »), mais ça n'a abouti à rien.
Nick Mandatory (2017-09-02T21:16:57Z)
Je sens que je finirai jamais cette entrée, et que je vais quand même me poser des questions, alors je décide de les poser avant la fin (accepte un nombre limite de cardinaux inaccessibles d'excuses si je pose des questions auxquelles tu réponds plus loin dans l'article).
Première question naïve : si je comprends bien ce que tu dis, le premier ordinal non calculable est le même, que l'on prenne la définition normale de calculable ou qu'on la dope jusqu'à vouloir dire calculable par une machine hyperarithmétique. Est-ce qu'il y a une explication simple à cette coïncidence (on aurait pu imaginer que ω_1^CK soit hyperarithmétique et qu'il y ait un premier ordinal non arithmétique ω_1^whatever > ω_1^CK, non ?)
Deuxième question indiscrète : fais-tu, ou envisages-tu de faire de la recherche dans le domaine de la récursion transfinie, ou quelque chose d'autre en lien avec ces sujets qui te tiennent visiblement à cœur ?
Visite au bordel des cardinaux (2017-08-31T17:41:06Z)
C'est un excitant les grands ensembles un peu comme le café ?