Ordinaux, encore
Bon, ça commence franchement à m'énerver qu'à chaque fois que je vois un $\omega$, j'arrête de comprendre ce qu'il se passe. Je n'ai jamais vu les ordinaux pendant mes études, donc je travaille avec des informations fragmentées, et en conséquence je ne suis jamais sûr de ce que je sais vraiment.
Je pars de là (seconde définition). Je sais qu'il y a des réponses plus ou moins complètes dans l'article, mais pour diverses raisons, je ne trouve pas ça clair.
Dans ZFC, on peut construire une chaîne d'ensembles ordinaux en partant de $\varnothing$. Ils forment un ensemble, dans ZFC, lui aussi ordinal, noté $\omega$. Première question : si tout ce qu'on fait après, c'est poser $0 = \varnothing$, $1 = \{0\}$ etc, quelle est la différence entre $\omega$ et $\mathbb{N}$ (rhétorique : j'ai lu que ce n'est PAS juste ce qu'on fait, mais alors, c'est quoi le truc ici ?) ? J'ai l'impression que $\omega = (\mathbb{N}, \in)$, donc $\omega$ désigne en fait un ensemble ordonné et $\mathbb{N}$ désignerait "juste" l'ensemble sous-jacent (sur lequel on "redéfinit" un ordre $\leqslant$ après - guillemets intentionnels). Dans tous les cas, grâce à l'axiome de l'infini, ce fameux $\omega$ est le premier ensemble ordinal dit transfini. Je ne comprends pas l'intérêt de ne pas dire "premier ordinal infini", pourquoi introduire un autre mot ici.
Ensuite : on définit $\omega + 1 = \omega \cup \{\omega\}$. Dans l'article, ils mentionnent une addition sur les ordinaux. Puisque je n'ai pas encore compris le lien entre $\omega$ et $\mathbb{N}$, je ne sais pas trop si je dois comprendre $1$ comme un ordinal ou non. Je pense que oui ?
Je vais commencer à shtamer un peu... $\omega + \omega$, qui devrait être défini d'après la suite de l'article (j'ai lu sans trop comprendre les histoires d'additions d'ordinaux), ça me fait penser à une limite de $\omega + n$, avec $n \in \mathbb{N}$. Je m'imagine ça comme une sorte de $\mathbb{N} \times \mathbb{N}$ pour l'instant. Dans tous les cas, ces bestioles m'ont l'air de rester dénombrables... le premier ordinal non dénombrable, c'est pour après.
Puisque mon anniversaire approche doucement, et que mes parents n'ont aucune idée de quoi m'offrir, je me suis dit, peut-être qu'un livre qui détaille vraiment bien tout ce qui est "vraiment fondamental", ça pourrait être bien. Je pense à la théorie des ensembles (et les cardinaux/ordinaux, donc), mais aussi la logique (langage logique, systèmes de déduction, sémantique, syntaxe, coupures, calcul des propositions, calcul des prédicats, histoires de complétude etc). Ce sont tous des thèmes sur lesquels j'ai travaillé à différents degrés par moi-même par le passé, principalement avec Wikipédia et des sources éparpillées trouvées sur Google. Je travaille mieux avec un bouquin, et je sais qu'il y a des bouquins que certains recommandent chaudement. Le Dehornoy m'a été conseillé plus d'une fois, il doit y en avoir d'autres.
Je pars de là (seconde définition). Je sais qu'il y a des réponses plus ou moins complètes dans l'article, mais pour diverses raisons, je ne trouve pas ça clair.
Dans ZFC, on peut construire une chaîne d'ensembles ordinaux en partant de $\varnothing$. Ils forment un ensemble, dans ZFC, lui aussi ordinal, noté $\omega$. Première question : si tout ce qu'on fait après, c'est poser $0 = \varnothing$, $1 = \{0\}$ etc, quelle est la différence entre $\omega$ et $\mathbb{N}$ (rhétorique : j'ai lu que ce n'est PAS juste ce qu'on fait, mais alors, c'est quoi le truc ici ?) ? J'ai l'impression que $\omega = (\mathbb{N}, \in)$, donc $\omega$ désigne en fait un ensemble ordonné et $\mathbb{N}$ désignerait "juste" l'ensemble sous-jacent (sur lequel on "redéfinit" un ordre $\leqslant$ après - guillemets intentionnels). Dans tous les cas, grâce à l'axiome de l'infini, ce fameux $\omega$ est le premier ensemble ordinal dit transfini. Je ne comprends pas l'intérêt de ne pas dire "premier ordinal infini", pourquoi introduire un autre mot ici.
Ensuite : on définit $\omega + 1 = \omega \cup \{\omega\}$. Dans l'article, ils mentionnent une addition sur les ordinaux. Puisque je n'ai pas encore compris le lien entre $\omega$ et $\mathbb{N}$, je ne sais pas trop si je dois comprendre $1$ comme un ordinal ou non. Je pense que oui ?
Je vais commencer à shtamer un peu... $\omega + \omega$, qui devrait être défini d'après la suite de l'article (j'ai lu sans trop comprendre les histoires d'additions d'ordinaux), ça me fait penser à une limite de $\omega + n$, avec $n \in \mathbb{N}$. Je m'imagine ça comme une sorte de $\mathbb{N} \times \mathbb{N}$ pour l'instant. Dans tous les cas, ces bestioles m'ont l'air de rester dénombrables... le premier ordinal non dénombrable, c'est pour après.
Puisque mon anniversaire approche doucement, et que mes parents n'ont aucune idée de quoi m'offrir, je me suis dit, peut-être qu'un livre qui détaille vraiment bien tout ce qui est "vraiment fondamental", ça pourrait être bien. Je pense à la théorie des ensembles (et les cardinaux/ordinaux, donc), mais aussi la logique (langage logique, systèmes de déduction, sémantique, syntaxe, coupures, calcul des propositions, calcul des prédicats, histoires de complétude etc). Ce sont tous des thèmes sur lesquels j'ai travaillé à différents degrés par moi-même par le passé, principalement avec Wikipédia et des sources éparpillées trouvées sur Google. Je travaille mieux avec un bouquin, et je sais qu'il y a des bouquins que certains recommandent chaudement. Le Dehornoy m'a été conseillé plus d'une fois, il doit y en avoir d'autres.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pour t'éviter de te perdre, une idée très intuitive : tu connais la différence entre les combinaisons et les arrangements. Il y a le même genre d'idée entre les cardinaux et les ordinaux. Une autre idée évidente : les adjectifs cardinaux sont zéro, un, deux, trois, ... et les ordinaux sont premier, deuxième, troisième, ...
Regarde bien où intervient l'ordre.
Cordialement.
J'arrête là, je vais me faire taper sur les doigts comme c'est déjà arrivé par ceux qui ne comprennent pas "intuitif" et l'usage du français flou de tout le monde.
Cordialement.
(*) donc pas d'ordre.
La définition de Von Neumann est intéressante quand on a conscience de ce qu'on construit : Un ensemble bien ordonné. Donc pas un simple ensemble.
Donc ce qui te manque peut-être est la notion de "bon ordre".
Et peut-être le fait qu'on présente généralement $\mathbb N$ avec son ordre d'énumération qui est un bon ordre. Mais chaque fois que tu mets un ensemble dénombrable en bijection avec $\mathbb N$, tu auras tendance à transporter avec la bijection le bon ordre. Tu vois un bon ordre sur $\mathbb Q$ ?
Dans un premier temps, utiliser les deux définitions en même temps peut permettre de donner du sens.
Cordialement.
J'ai acheté le Dehornoy et je peux te dire ce que j'ai cru comprendre en lisant les premiers chapitres.
La théorie des ensembles permet de représenter en tant qu'ensembles quasiment tous les objets mathématiques qu'on connait, dont les nombres entiers. Ce qu'on note $\omega$ est la représentation comme ensemble de $\mathbb{N}$ qui est "l'ensemble" (entre guillemets car ce n'est pas un objet de la théorie ZFC) des entiers naturels.
Voici une copie d'un passage du livre pour être plus clair :
L'existence de cette copie des entiers (il parle de $\omega$) à l'intérieur du monde des ensembles purs invite évidemment à représenter chaque entier naturel $n$ par l'ordinal $\underline{n}$, et l'ensemble $\mathbb{N}$ des entiers par l'ordinal $\omega$. En revanche, notons dès à présent que rien à ce point ne démontre ni même ne suggère que les entiers sont les ordinaux finis, et que, par exemple, l'entier 2 est l'ordinal $\underline{2}$, qui a été contruit comme l'ensemble $\{\underline{0},\underline{1}\}$.
https://sites.google.com/view/martial-leroy
L'avantage c'est qu'on part de rien, juste d'une certaine habitude de faire des maths. On présente rapidement la théorie naïve, puis on montre son inconsistance et la nécessité de la méthode axiomatique. Tu peux zapper le Chap 4 en première lecture si la logique te saoule. A partir du Chap 5 on découvre les axiomes au fur et à mesure qu'on en a besoin (contrairement à certains auteurs qui te balancent tout dans la tronche dès la page 2 du livre sans aucune explication). Petit à petit tu découvriras les ordinaux et les cardinaux, et si tu vas suffisamment loin tu découvriras la différence (subtile) entre $\N$ et $\omega$. Et l'avantage c'est que si tu ne comprends pas un truc ce sera plus facile pour moi de t'expliquer.
A noter que je me suis beaucoup servi du livre de Patrick Dehornoy (entre autres), mais je n'ai pas utilisé ses notations avec les $n$ soulignés, je trouvais ça trop relou.
Seul inconvénient de cette méthode : comme c'est gratos il va falloir que tes parents trouvent une autre idée de cadeau, lol
on ne les définit pas. Ce sont les entiers "intuitifs" ceux que tout le monde intuite... on ne peut qu'essayer de les représenter. C'est comme les couleurs ?
Mais je pense qu'il faut vraiment lire un livre de quelqu'un qui s'y connait comme celui de Martial ou Dehornoy.
Je n'ai jamais vu les éléments de $\mathbb{N}$ supposés être des "trucs" primitifs en maths. On utilise l'axiome de l'infini pour les construire (enfin, du coup, pour en construire des copies) et dire qu'ils forment un ensemble. Pour moi ça fait assez peu de sens, pour l'instant...
Une nuance qu'on peut vouloir introduire, est que $\mathbb N$ est très structuré : c'est un semi-anneau ordonné blabla: donc on pourrait dire que $\mathbb N$ est le tuple $(\omega, +,\times, 0,1, <)$ en tant que structure (du premier ordre disons). Mais à part ça, il n'y a aucune distinction à faire en maths.
J'ai pas lu tout ce qui s'est dit, donc désolé si je répète, mais je vais essayer de prendre les choses dans l'ordre.
$\omega$ est un ensemble, rien de plus. Il s'avère (quelle chance :-D) que $\in$ est un bon ordre dessus, c'est tout.
Oui, dans $\omega +1$, le $1$ peut être compris comme l'ordinal $1 = \{\emptyset\}$. Je mets "peut", parce qu'en fait quand on construit la théorie des ordinaux, on définit en général le successeur $s(\alpha) := \alpha\cup \{\alpha\}$, et on a tendance à le noter $\alpha +1$ parce qu'il s'avère que ça coïncide avec la somme ordinale. Mais tu peux donc aussi le voir comme le successeur, i.e. le plus petit ordinal strictement plus grand que $\omega$.
Il est bon de savoir que la somme ordinale est une "décatégorification" de la somme de bons ordres. Bon j'utilise un gros mot, donc je me permets de le préciser : ce que j'entends par là, c'est qu'étant donnés deux bons ordres $E,F$, on peut définir $E\oplus F$. Ensuite, il y a un théorème qui dit qu'étant donné un bon ordre, il existe un unique ordinal $\alpha$ qui lui est isomorphe. Du coup on peut définir $\alpha+\beta$ comme cet ordinal pour $\alpha \oplus \beta$, et ça redonne la même construction.
$\omega+\omega$ c'est tu commences par $\omega$ (donc tu comptes dans ta tête $0,1,2,3,...$, et chaque $n$ tu le comptes en $1/2^n$ secondes); après 2 secondes tu as épuisé tous les entiers, bah tu recommences une deuxième fois.
Du coup ça fait $0,1,2,3,4,..... 0,1,2,3,....$
(j'ai mis un temps uniquement pour expliquer comment faire en pratique ;-) )
Mais tu as raison, ça reste parfaitement dénombrable. $\omega\omega = \omega^2$ (et lui peut-être naturellement représenté par un bon ordre sur $\mathbb N\times \mathbb N$) est lui aussi dénombrable etc.
Tu as aussi de voir $\omega+\omega$ comme une limite de $\omega+n, n\in \omega$ : c'est leur borne supérieure ! Donc dans la topologie de l'ordre, c'est véritablement leur limite (et l'idée de "limite" est partout en théorie des ordinaux, on parle même de continuité etc.)
Finalement pour un livre, je te conseille (je vais finir par avoir l'impression que je fais leur pub !) Logique Mathématique, de Cori et Lascar.
C'est cher, mais il y a plein de choses dedans, et moi c'est comme ça que j'ai appris la logique.
Je peux aussi te joindre un document que j'avais écrit il y a longtemps pour un ami en introduction aux ordinaux (je crois que je l'ai déjà partagé sur le forum, je ne sais plus quand). La fin part en cacahuète, puisque je parle de théorie des modèles mais qu'il n'y connaissait rien, donc c'est pas précis. Mais le début (bons ordres, ordinaux, cardinaux) est précis et ne part pas en cachuète. ça suit essentiellement les présentations usuelles de ce sujet
(Je ne prétends pas que ce soit au niveau de ce qu'a écrit Martial, et je n'entends aucunement lui faire de compétition ;-) mais je te donne une autre source)
2/ $\omega + 1$ c'est juste $\omega \cup \{\omega\}$
3/ C'est plutôt l'inverse de ce que tu as écrit qui est vrai. Pour les gens $\N$, c'est un peu comme $\R$, ils y pensent avec sa structure. Tandis que $\omega$ non. C'est clair et pur.
4/ Les ordinaux (comme tout autre objet mathématique, mais eux c'est clair) sont des ensembles et non pas des ensembles ordonnés. Ils sont ordonnables, si tu veux, de manière évidente par $\in$.
5/ Attention, c'est très naturel et psychanalysant: les gens "ne savaient pas" pourquoi ils considéraient les entiers en premier, et on a approfondi et compris. Ce n'est pas l'inverse, par exemple qui dirait "on code les entiers ou autre" dans les ensembles. Par exemple "ajouter 1", il fallait identifier ce que ça veut dire, sinon on était dans la vacuité verbale à toujours dire que toutes les notions sont premières.
6/ Un entier, C'EST un ordinal fini, et l'additoin (cardinale), C'EST le fait de calculer $card(A\cup =: card(A)+card(B)$ pour $A,B$ disjoints (de même que le produit, C'EST le fait de mathématiser $card(A\times =:card(A)\times_{numerique} card(B)$ et non l'inverse. D'ailleurs, c'est ce que les enfants font, ils apprennent à compter comme ça et heureusement pour eux :-D qu'ils ne sont pas introduit à ça avec les algorithmes de réécriture de suites de chiffres. De même que $n!$ C'EST le cardinal de $Bijections(n\to n)$, etc. Et non l'inverse.
Tu m'as un peu perdu avec des ordinaux isomorphes à des relations d'ordre, je pense qu'il y a un énoncé nettement plus précis que ce que tu as dit, mais tu as sans doute fait exprès de ne pas détailler un énoncé précis.
Je lirai ça quand j'aurai le temps !
On ne recommence pas à $0$. C'est comme si tu disais que pour comprendre $\Z$, y a juste à connaitre $\Z/3\Z$ et qu'on recommence à $0$, une fois arrivé à 3 :-D
Cela dit un des articles que j'ai publié calcule des "modulo omega" d'objets assez inattendus, mais bref...
Concernant ZF, c'est un non sens d'essayer de comprendre sa genèse montante, car elle n'existe pas vraiment.
C'est sa genèse descendante qui est la source. On est parti du naturel:
$$ \forall R\exists a\forall x: [R(x)=(x\in a)] $$
c'était contradictoire, alors on a viré quelques $R$.
Cependant, la philosophie ZF, et c'est pour ça que toute la science s'est construite dessus, c'est qu'elle a viré SEULEMENT LES GROSSES $R$. Toutes les petites sont autorisées.
Ainsi s'opère une identification entre $GROSSEUR$ et contradiction. Les grosse, c'est pas qu'elles n'existent pas, c'est qu'elles forcent $0=1$. Donc, on les chatouille pas trop, parce qu'elles font peur comme un orage.
Les autres tentatives sont des usines à gaz qui ont échoué parce qu'elles sont fabriquées artificiellement en vue de récupérer (même en chuchotant) un peu de consistance garantie, et donc cherchent à esquiver des .. réalités mathématiques qui s'imposent par la fenêtre si on leur ferme la porte. Dans ZF, si on perçoit bien la "franche censure des grosses" comme appelée pour préserve la consistance, l'effort est resté très naif, et figé dans l'histoire. (Bon on remonte un peu avec les grands cardinaux, mais idem, on tire de la grosse kalach-platonicienne)
Je faisais référence à ça.
@Max : c'est marrant, je viens de télécharger ton papier, et je m'aperçois que je l'avais déjà téléchargé, Dieu sait quand. Je ne sais pas s'il est d'un niveau supérieur ou inférieur à mon livre, c'est difficilement comparable puisque je parle de beaucoup de choses alors que dans ton papier tu te focalises sur les ordinaux, mais de loin j'ai l'impression que tu as fait un truc très pédagogique pour les néophytes.
Je rappelle rapidement:
1/ Il n'y a pas d'ensemble $E$ qui soit égal à $P(E)$
2/ Il y a deux ensembles $E$ tels que $E = P(E)\setminus \{E\}$, qui sont cruciaux et révélateurs dans les maths.
3/ Il y a tout plein plein d'ensembles tels que $E = (P(E) \cap Transitif) \setminus \{E\}$. Ce sont les ordinaux.
On pourrait varier les plaisirs, mais on a là 3 gros morceaux.
Avec cette définition, quelques lignes suffisent pour avoir toutes les propriétés des ordinaux, par exemple que tout ensemble non vide a un minimum qui est son intersection, etc.
D'ailleurs la théorie ZF est définie de manière équivalente par "il existe $E,F$ assez indiscernables tels que $P(E)\subset F$".
Au passage comme l'a dit Max, $\omega \cup \{\omega\}$ est égal à $\omega + 1$, où $\omega + 1$ est, par définition de l'addition ordinale, l'ordinal isomorphe à l'ensemble $(\omega \times \{1\}) \cup (1 \times \{2\})$ muni de l'ordre défini par $(x, 1) < (y, 1)$ si $x < y$ et $(x,1) < (y, 2)$. Moralement, je mets les éléments de $\omega$ en premier, et je mets les éléments de $1$ (bon il en a qu'un... :-D ) tout à droite. Par contre $1 + \omega = \omega$.
Il y a effectivement un énoncé précis, mais il est un peu technique à écrire, et on va pas se casser la tête à te le réécrire ici alors que tu l'as sous la main. (Voir mon Chap 8, de mémoire).
"quand j'ai appris que l'axiome de l'infini était dans la liste des axiomes de ZF parce que "ben, on a essayé de construire les entiers naturels dans la TDE sans rien, et on n'y est jamais arrivé, alors on s'est donné un axiome qui en fournit assez directement une copie", ça m'avait bien fait sourire."
Tant mieux que ça te fasse sourire, mais c'est pas ça. On a mis l'axiome de l'infini dans ZF parce qu'on NE PEUT PAS faire autrement. Si tu appelles ZF-Schtroumpf la théorie ZF privée de l'axiome de l'infini, il est possible (et même très facile) de construire un modèle de ZF-Schtroumpf dans lequel "tout est fini". En clair (c'est-à-dire modulo le théorème de complétude, mais bref), ça veut dire que l'axiome de l'infini ne peut pas se déduire du reste. Et Hilbert avait eu une intuition géniale quand il avait dit que la prétendue "démonstration philosophique" de Dedekind de l'existence de l'infini lui paraissait chelou. Et pourtant, j'ai une admiration sans bornes pour Dedekind.
Purée, on se tue la tête à te donner des outils, et tu veux pas t'en servir !
P.S. : Galilée avait très bien senti les choses. S'il avait disposé de notre formalisme (disons, s'il avait vécu au XXième siècle),il aurait peut-être pu être comparé à Dedekind, Cantor, Gödel ou Cohen.
Tu te moques de moi ? Il est tard le soir, je bosse à temps plein et je me lève tôt, on m'a donné deux liens vers des documents longs dans les deux dernières heures, et parce que j'écris des choses informelles en attendant d'avoir eu le temps de lire les choses en détail, tu commences directement à me voir comme un gamin impatient ? Eh ben merci !
Quant à "on a mis l'axiome de l'infini dans ZF parce qu'on ne peut pas faire autrement", c'est exactement ce que j'ai dit.
Et puis tu pourrais m'épargner des réflexions du genre "Tu te moques de moi ?".
D'abord c'est pas mon genre, et puis ça se fait pas.
Je n'ai pas vérifié de visu mais ça a l'air de marcher.
Si le tout n'est qu'un bête malentendu, autant se donner un mea culpa mutuel tout de suite et passer à autre chose, ça sera plus productif. Je ne suis ni trop bête, ni trop fier, ni trop rancunier pour ça.
Ce que j'essayais de t'expliquer (parce qu'en plus ça avait l'air de te faire marrer), c'est que ce n'est pas ça.
C'est tout.
Moi non plus je ne suis ni tebê, ni rancunier ni machin.
Quand tu as le temps essaye quand même de réfléchir à tout ça (je parle de la TDE, pas de nos engueulades inutiles).
Buenas noches
Non, tu interprètes mal ce que je dis. Je pense que tu n'as juste pas encore assez l'habitude de moi et mes commentaires pour savoir à peu près quelle intonation j'ai en tête quand j'écris (normal).
Je pense que c'était extrêmement naturel comme idée, à l'époque de la crise des fondements, de vouloir créer un système d'axiomes "pour toutes les mathématiques" dans lequel on faisait le maximum de choses de manière constructive, et donc en particulier, essayer de trouver un système dans lequel on peut construire les entiers naturels. Sauf qu'effectivement, ça ne marche pas, ils ont essayé mais jamais réussi (forcément, puisque ça ne marche pas). Ce qui m'amuse dans l'histoire, c'est que les entiers naturels sont "tellement naturels" qu'on ne peut pas construire un système qui marche sans que ce système ne contienne dès le départ "au moins une copie" des entiers naturels. Philosophiquement, je trouve ça franchement pas anodin, quand même ! Le concept de quantité est "tellement intrinsèque" à la logique qu'on n'arrive pas à le construire, seulement à en construire des représentations/interprétations. Moi, ça me fait sourire, ce genre de chose, ça me donne un effet de "t'as vu comment c'est dingue, en fait, les nombres ?"
Introduction à la logique : Théorie de la démonstration - Cours et exercices corrigés de R.David, K.Nour et C.Raffali.
https://www.amazon.fr/Introduction-logique-démonstration-exercices-corrigés/dp/2100067966
Christophe désolé de pinailler mais tu devrais plutôt dire : "Pour moi Christophe, un entier EST un ordinal fini". Car pour Dehornoy ce n'est pas le cas par exemple :
Comme il le dit lui même, si un jour on utilise un autre système fondationnel pour les mathématiques, les nombres entiers seront représentés d'une autre façon.
Voili voilou... (:P)
En gros je crois avoir cerné ton problème : tu te prends la tête sur des questions de circularité qui n'ont pas vraiment de solution, même pour les spécialistes. Disons pour simplifier c'est un peu l'histoire de l'oeuf et de la poule : pour faire de la logique il faut connaître un tout petit peu de TDE (disons au moins disposer de l'ensemble $\N$). Mais pour faire de la TDE on a besoin de la logique, puisque ZF est une théorie comme une autre, elle doit obéir aux théorèmes de complétude et d'incomplétude.
Tu devrais peut-être commencer par des choses, plus simples, genre bien comprendre les axiomes de ZFC, les ordinaux, les cardinaux et leurs propriétés etc.
A ce propos je commence par préciser un résultat que tu trouvais trop vague hier dans les propos de Christophe. Soient $(E,R)$ et $(F,S)$ 2 ensembles bien ordonnés. On dit qu'ils sont isomorphes s'il existe une bijection $\varphi : E \rightarrow F$ telle que $\forall x,y \in E, xRy \Leftrightarrow \varphi(x) S \varphi(y)$. Et le résultat cité par Christophe c'est que pour tout ensemble bien ordonné $(E,R)$ il existe un unique ordinal $\alpha$ tel que $(E,R)$ soit isomorphe à $(\alpha, \in)$, et en plus l'isomorphisme est unique.
Mais attention : ce résultat est fortement non trivial, au sens où il utilise de façon cruciale le schéma de remplacement. En l'absence de ce dernier il se peut très bien que les seuls ordinaux de l'univers soient $0,1,2,..., \omega, \omega +1, ..., \omega +n, ...$ et que $\omega + \omega$ n'existe pas.
"Christophe désolé de pinailler mais tu devrais plutôt dire : "Pour moi Christophe, un entier EST un ordinal fini"."
Ch'est pas cha.
Ch'est : "Pour moi, ZF, un entier EST un ordinal fini".
Bien sûr, Dehornoy a raison, on a tout à fait le droit de travailller dans autre chose que ZF, auquel cas un entier est une blablature inhérente à la théorie ambiante.
Tu vas peut-être me rétorquer que c'est justement parce que Dieu nous les a donnés qu'on est infoutus de les définir. Si c'est ça ça me paraît au contraire "petit". Je ne suis pas croyant, mais Cantor l'était beaucoup et, s'il faut admettre l'existence de Dieu, je préfère encore la version de Cantor avec l'infini absolu : celui qui est tout au bout des ordinaux ou des cardinaux. Celui-là, effectivement seul Dieu peut le cerner.
Enfin, il faudra m'expliquer un jour en quoi cette phrase mythique de Kronecker peut faire avancer le schmilblic en quelque façon que ce soit.
Kronecker était un intuitionniste avant l'heure et cette boutade visait principalement un de ses étudiants, Cantor lui-même.
Par ailleurs, ses travaux sur l'équation du cinquième degré et en théorie algébrique des nombres en font un des précurseurs de l'algèbre moderne vue sous le prisme galoisien.
Quant à la logique, ZF et les cardinaux "usuels", ça va, je sais me débrouiller avec. Les cardinaux inaccessibles et autres cardinaux "extérieurs à ZFC" (dans le sens, qyi nécessitent d'ajouter des axiomes) j'ai plus de mal. C'est vraiment les ordinaux qu'il faut que je creuse. J'avais espéré des réponses courtes et simples, sinon je n'aurais pas ouvert ce fil. Au lieu de ça, on m'a donné des dizaines de pages de lecture, je vais avoir du boulot ! Il me faudra le temps...
Tu considères la formule à deux variables libres $F(n,y)$ qui dit que $n \in \omega \land y= \omega + n$.
Cette formule est clairement fonctionnelle en $n$.
Par le schéma de remplacement (et parce que $\omega$ est un ensemble), il existe un ensemble $A = \{y : \exists n \in \omega, F(n,y) \}$.
En d'autres termes, $A = \{\omega + n : n \in \omega \}$.
Maintenant que tu sais que $A$ est un ensemble, l'axiome de la réunion te fournit l'existence d'un ensemble
$$ \bigcup A = \bigcup \limits_{n \in \omega} (\omega + n).$$
Par construction, cet ensemble est un ordinal, et il contient strictement tous les $\omega + n$.
Tu l'appelles $\omega + \omega$, et tu écris
$$\omega + \omega = sup \{\omega +n : n \in \omega \},$$
et le tour est joué.
Tu avais aussi conseillé "Les démonstrations et les algorithmes" de Dowek que j'ai acheté mais que je n'ai pas encore vraiment ouvert...
Quelles sont les différences avec le livre de David and co ?
Regarde bien $\omega$. Il a 2 propriétés bien spécifiques (je vois tous les $n$ comme des cardinaux $< \omega$) :
1) Si $n< \omega$, alors $2^n < \omega$.
2)Pour tout $n < \omega$, il n'existe pas d'application non bornée de $n$ dans $\omega$.
Maintenant, tu vois aisément que cela ne marche plus pour tous les cardinaux non dénombrables qu'on sait construire "à la main". Par exemple, la propriété 1) tombe en défaut pour $\omega_1$, puisque $2^{\omega} \geq \omega_1$.
Pour $\omega_{\omega}$ c'est la propriété 2) qui tombe en défaut, puisque l'application $f : \omega \rightarrow \omega_{\omega}$ définie par $f(n)= \omega_n$ est clairement non bornée dans $\omega_{\omega}$.
Et tu as le même problème avec tous les cardinaux usuels :
Pour les successeurs c'est 1) qui foire. Pour les limites c'est 2).
D'où la définition : soit $\kappa$ un cardinal infini non dénombrable. On dit que $\kappa$ est fortement inaccessible si :
1) Si $\lambda$ est un cardinal et si $\lambda < \kappa$, alors $2^{\lambda} < \kappa$
2) Pour tout cardinal $\lambda <\kappa$, il n'existe pas d'application non bornée de $\lambda$ dans $\kappa$.
Pour les faiblement inaccessibles c'est pareil, en remplaçant $2^{\lambda}$ par $\lambda^+$ dans la condition 1).
Tu ne serais pas un peu grognon dans ton genre?
La définition d'ordinal fait une ligne: c'est un ensemble égal à l'ensemble de ses parties transitives qui ne sont pas lui.
1/ Le fait qu'ils soient bien ordonnés par l'inclusion:
Soit $E$ un ensemble non vide d'ordinaux. L'intersection $X$ des éléments de $E$, qui est transitive, est l'ensemble de ses parties transitives, et il reste à voir que $X\notin X$. Exercice
2/ Le fait que parmi deux ordinaux différents, il y en a un qui est élément de l'autre, idem. Exercice
3/ Soit $E$ un ensemble d'ordinaux (MERCI FOYS). Sa réunion est un ordinal. Exercice
4/ Prouve aussi que $x\cup \{x\}$ est le plus petit ordinal strictement supérieur à $x$.
5/ Vocabulaire: les ordinaux qui ne sont successeurs de personne sont appelés "limite". Tout ordinal s'écrit comme un ordinal limite + un entier.
6/ Les cardinaux sont les ordinaux qui ne s'injectent dans aucun ordinal plus petit.
Après ça, tu es "comme nous", tu n'as plus qu'à t'amuser avec.
7/ Les constructions par récurrence ordinale: soit $f$. Soit $L$ l'ensemble des $g$ telles que pour tout ordinal $a$, ou bien $g$ n'est pas définie en $a$ ou bien $g(a) = f(g_{|a})$. Et bien la réunion des $g$ pour $g\in L$ est une fonction $h$ telle que pour tout ordinal $a: h(a) = f(h_{|a})$.
8/ Ca marche comme les entiers, sauf qu'on n'a pas recours "au prédécesseur", ie on ne dit pas "$u(n)$ est définie en fonction de $u(n-1)$ par blabla". On dit "$u(n)$ est définie en fonction de $u_{|n}$ par blabla"
9/ Avec ça, tu as tout et ça ne te prendra même pas 2H.
10/ Remarque: tu peux passer par les cardinaux si tu veux pour avoir une "échelle éternelle" qui monte jusqu'en haut de l'univers. Le lemme de Zorn les rend bien ordonnés de manière évidente:
soit $E$ un ensemble non vide d'ensembles non vides. Soit $L$ un ensemble maximal de fonctions choix 2 à 2 disjointes sur $E$. Il existe donc $A\in E$ tel que $\forall x\in A\exists ! f_x\in L: f_x(A)=x$. Soit $B\in E$. Alors :
$$ x\in A\mapsto f_x(B)$$
est une injection de $A$ dans $B$.
Du coup la structure est la même que pour les ordinaux et il y a une bijection croissante canonique (nommée $Aleph$) des ordinaux dans les cardinaux.
Attention: tout ceci utilise abondamment l'axiome du choix.
-le livre de David/Nour/Raffali est plus "scolaire" et spécifiquement dédié à la théorie de la démonstration proprement dite, avec beaucoup d'exos et un exposé détaillé sur ce qu'est le raisonnement intuitionniste (pour répondre en plus à une autre demande d'Homo Topi)
-le livre de Dowek contient des chapitres sur les fonctions récursives et la réécriture, ce que ne fait pas l'autre livre. Après c'est une affaire de goût mais le deuxième livre serait pour des gens ayant moins besoin d'être tenus par la main peut-être.
Un ordinal est un ensemble $E$ qui a les propriétés suivantes:
i) pour tout $x$, si $x\in E$ alors $x$ est aussi inclus dans $E$
ii) pour toute partie non vide $X$ de $E$, il existe $a\in X$ "minimal" (i.e. tel qu'il n'y a aucun élément de $a$ appartenant à $X$)
iii) pour tous $a,b,c\in E$, si $a\in b$ et $b\in c$ alors $a \in c$
********
L'appartenance est une relation de bon ordre strict sur $E$. En effet si $E$ vérifie les axiomes ci-dessus alors:
iv) pour tous $a,b\in E$, on n'a jamais $A\in B$ et $B\in A$ (NB: notamment on n'a $X\in X$ pour aucun $X$ dans $E$.)
(résulte de l'application de ii) à $\{a,b\}$)
v) on a $x\notin x$ pour tout $x\in E$ (appliquer à nouveau ii) à $\{x\}$)
Ainsi, en posant pour tous $x,y\in E$, $x\leq y$ si $x=y$ ou $x\in y$, on se retrouve avec une relation d'ordre pour laquelle chaque partie non vide de $E$ possède un plus petit élément (cf ii). L'importance de cette relation d'ordre est que les ordinaux servent entre autres à classer les ensembles bien ordonnés (pour tout ensemble bien ordonné, il existe un unique ordinal en bijection croissante avec ledit ensemble).
Un ensemble d'ordinaux tu veux dire? la réunion de $ \{\{\emptyset\}, \{\{1,2,3\} \}\}$ n'est pas un ordinal (mais un ensemble à deux éléments dont l'un est de cardinal 1 et l'autre 3)