Comments on Les ordinaux dénombrables

Damien (2006-02-19T11:22:05Z)

Bon, après avoir creusé un peu, effectivement, pas mal de livres de complexité/récursivité abordent plus ou moins les ordinaux (mais pas avec tous les détails que tu as donné).

La bible sur l'hyperarithémtique semble être http://www.springer.com/sgw/cda/frontpage/0,11855,7-40109-22-24469918-0,00.html
mais c'est épuisé, donc je tâcherai de voir ça en bibli à l'occasion…

Damien (2006-02-17T08:33:30Z)

Oui, je parlais bien de celui que cite David
http://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-2055931-0,00.html

Ruxor (2006-02-16T19:28:41Z)

Nick → Je ne pense pas qu'on puisse définir une notion intéressante de décomposition en facteurs premiers sur les ordinaux (ni même d'ordinal premier — on peut bien sûr choisir d'appeler premiers ceux qui ne sont pas le produit de deux ordinaux strictement plus petits autres que 1, mais je crois que ce n'est pas très passionnant). En revanche, il y a une décomposition en base b, pour tout entier naturel b>1 (et aussi au moins pour certains ordinaux b, comme ω, mais je ne suis pas sûr que ça marche pour tous au moins de la façon la plus intuitive). Par exemple, pour l'écriture des ordinaux en binaire, chaque ordinal est, de façon unique, somme décroissante de puissances de 2 distinctes (une puissance de 2 étant un ordinal de la forme 2^x pour un certain x, par exemple ω est une puissance de 2 puisque c'est 2^ω).

bidibulle → Le bouquin le plus standard de référence en théorie des ensembles, c'est *Set Theory* de Jech (qui est maintenant réédité chez Springer dans une édition “troisième millénaire”).

bidibulle (2006-02-16T14:02:59Z)

>Damien, parle-tu de Introduction to Set Theory de Karel Hrbacek et Thomas Jech?

Manu (2006-02-16T12:53:19Z)

C'est vrai qu'on ne peut forcer personne à écrire dans une version de la Wikipedia plutôt qu'une autre, mais ça m'étonne quand-même quand quelqu'un qui, par ailleurs, a l'air intéressé par les langues, dit qu'il ne voit "pas vraiment l'intérêt que ce genre d'articles existe dans plein de langues différentes". Moi qui ai fait mes études seulement en français, je trouve un intérêt énorme à lire un article de maths en français : je ne connais pas du tout le vocabulaire mathématique en anglais… Suis-je le seul ?

Nick (2006-02-16T12:33:53Z)

Une remarque de beotien complet (merci de ne pas repondre "oui c'est completement beotien!" ;-) )

2 est un ordinal. C'est aussi un nombre premier. existe-t-il une notion d'ordinaux premiers? Ce serait quoi l'analogue de la multiplication dans ce cas? Le produit cartesien?

phi (2006-02-16T09:59:24Z)

C'est vrai que Vuillemin a été l'un des plus grands philosophes français. Merci Stranger, je ne connaissais pas le titre de son 2eme volume. En passant, ça me rappelle ce mot de Quine: "le paradoxe des uns fait la définition des autres".

Une question tordue: y a-t-il une structure intermédiaire entre les cardinaux et les ordinaux? qui permettrait de faire des calculs intéressants comme avec les p-adiques. D'ailleurs, les p-adiques peuvenbt-ils servir à compter quelque chose?

Damien (2006-02-16T09:33:55Z)

Merci pour ta réponse. J'ai pas mal de choses sur ces thèmes là, je vais les déterrer pour creuser un peu… Mais je reste surpris qu'il n'y ait (ou alors ça n'est pas connu) pas de textbook classique de maths pures qui aborde ça.

Ruxor (2006-02-16T09:15:51Z)

Ça dépend de quel aspect des ordinaux on cherche à développer… Mais pour ce qui est des grands ordinaux récursifs, par exemple, c'est très lié à la théorie de la calculabilité (cf. le livre de Rogers, qui expliquera par exemple le système des notations ordinales de Kleene) et à la théorie de la démonstration (je n'en connais pas assez pour donner de bonnes références, malheureusement). Sinon, évidemment, on trouve des petites choses éparses sur le Web, comme par exemple <URL: http://www.cs.fsu.edu/~levitz/ords.ps >.

Damien (2006-02-16T08:21:46Z)

Tu as des références sur ce sujet précis des ordinaux ? J'ai le Jech mais je n'ai pas trouvé tous ces détails (ou alors j'ai mal cherché) alors qu'il est considéré comme la "bible"… Il insiste beaucoup plus sur les cardinaux.

Si tu as des livres ou articles qui détaillent un peu plus, je suis intéressé.

n'importe quoi (2006-02-15T18:26:11Z)

Jusqu'a omega^n tout va bien… le plus dur c'est la suite!

Ruxor (2006-02-15T17:50:16Z)

Damien → Comme j'ai déjà dû l'expliquer, je ne vois pas vraiment l'intérêt que ce genre d'articles existe dans plein de langues différentes. Mais si quelqu'un trouve que c'est utile de le traduire en français, en allemand, en japonais ou en swahili, qu'il ne se prive surtout pas. (Et s'il y a un doute sur un mot, j'aiderai, et je suis aussi prêt à relire la traduction.) Mais mes contributions directes à la Wikipédia francophone ne concernent que les choses liées à la France.

momo → Ce n'est pas très facile à expliquer. Disons qu'un ordinal plus petit que celui de Church-Kleene peut se décrire comme un bon ordre récursif (calculé par une certaine machine de Turing) sur les entiers naturels. On peut alors s'interroger sur l'énoncé mathématique qui dit que la machine de Turing en question calcule effectivement un bon ordre, énoncé qui permet de faire de la récursion transfinie sur cet ordinal. Eh bien il existe un ordinal (strictement plus petit que celui de Church-Kleene) à partir duquel un système donné (récursivement axiomatisable et contenant l'arithmétique) ne parvient plus à démontrer la récursion transfinie. Par exemple, pour l'arithmétique de Peano du premier ordre, c'est ε0, tandis que pour la théorie des ensembles de Kripke-Platek c'est l'ordinal de Bachmann-Howard. Et si on rajoute à l'arithmétique de Peano tous les énoncés permettant de récurrer jusqu'à tout ordinal inférieur à celui de Bachmann-Howard (dans son énumération standard), par exemple, eh bien on obtient comme conséquences tous les énoncés arithmétiques qui découlent de la théorie des ensembles de Kripke-Platek. En résumé, tout énoncé arithmétique vrai mais non démontrable est non démontrable précisément parce que le système formel n'arrive pas à atteindre la récurrence transfinie jusqu'à un certain point. (En fait, je triche un peu en disant ça. Il y a bien un théorème de Feferman qui va dans ce sens, mais il va utiliser des énumérations tout à fait tordues des ordinaux. Pour en dire plus, il faudrait introduire le système O des notations ordinales de Kleene.)

Vicnent (2006-02-15T17:07:44Z)

@Damien B :
+1 (c'est le cas de le dire)
je reprends donc :
[…] vu que traitreusement tu ne t'occupes pas de l'article en français.
M'enfin, ce doit être normal puisqu'il ne se sent pas Français : il parait même que la seule chose qui le rattache à la France, ce sont ses amis. Et encore, pour ainsi dire, comme il le dit lui même, à Paris.
<URL: http://www.madore.org/cgi-bin/comment.pl/showcomments?href=http%3a%2f%2fwww.madore.org%2f%7edavid%2fweblog%2f2005-08.html%23d.2005-08-10.1068 >

bidibulle (2006-02-15T13:22:00Z)

C'est très très beau!

Quel écart entre les grands nombres pour les Physiciens et les constructions des mathématiciens!

Stranger (2006-02-15T11:34:20Z)

A ce sujet, je regrette que Vuillemin n'ait pas écrit le deuxième tome de sa philosophie de l'algèbre qui devait être consacré à "L'infini, l'ordre et la structure" ; le premier tome est déjà assez passionnant et il m'a permis, à mio qui n'ait de connaissances mathématiques que restreintes au programme des khâgnes BL, de comprendre pas mal de choses sur la pensée maths.

Damien B (2006-02-15T07:28:40Z)

"Je suis en train de faire plein d'éditions à l'article Wikipédia à ce sujet"

On devrait plutôt dire "à un article de Wikipédia à ce sujet", vu que traitreusement tu ne t'occupes pas de l'article en français.

momo (2006-02-15T06:27:54Z)

je n'ai pas bien compris le lien entre la démontrabilité d'un énoncé arithmetique et le fait de compter "loin", peux tu l'expliquer un peu?