Théorème de dénombrement
Bonjour,
Dans mon livre, le théorème de dénombrement dit : "Tout ensemble bien ordonné est semblable à un nombre ordinal unique". (semblable = il existe une bijection croissante entre les deux)
Par ailleurs, le théorème du bon ordre dit : "Tout ensemble peut être bien ordonné".
La conclusion que j'en tire est : "Tout ensemble peut être rendu semblable à un nombre ordinal". Par exemple $\mathbb R$.
Bizarre. Car si $\mathbb R$ est semblable à un nombre ordinal, ses éléments sont en bijection avec les éléments d'un nombre ordinal, qui sont des nombres ordinaux, et qui se construit par successeur, donc qui est dénombrable (enfin je pense). Or on sait bien que $\mathbb R$ n'est pas dénombrable. Qu'en pensez-vous ? Où est l'erreur ?
Merci d'avance.
Dans mon livre, le théorème de dénombrement dit : "Tout ensemble bien ordonné est semblable à un nombre ordinal unique". (semblable = il existe une bijection croissante entre les deux)
Par ailleurs, le théorème du bon ordre dit : "Tout ensemble peut être bien ordonné".
La conclusion que j'en tire est : "Tout ensemble peut être rendu semblable à un nombre ordinal". Par exemple $\mathbb R$.
Bizarre. Car si $\mathbb R$ est semblable à un nombre ordinal, ses éléments sont en bijection avec les éléments d'un nombre ordinal, qui sont des nombres ordinaux, et qui se construit par successeur, donc qui est dénombrable (enfin je pense). Or on sait bien que $\mathbb R$ n'est pas dénombrable. Qu'en pensez-vous ? Où est l'erreur ?
Merci d'avance.
Réponses
-
@JP : bonjour. Tu lis encore le Halmos qui est imbitable. Par semblable à, il faut comprendre isomorphe à. Mieux vaut se focaliser sur ceci.Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
-
Les ordinaux ne sont pas tous dénombrables. C'est la conséquence (avec $E:=\N$) du résultat ci-dessous.
Il n'existe aucun ensemble $E$ tel que tout ordinal est équipotent à une partie de $E$. Sinon (schéma de remplacement) considérons $X:= \{(P,R) \in \mathcal P(E) \times \mathcal P (E^2)\mid R\text{ et un bon ordre sur } P \}$. Alors la formule de variables libres $x,y$: $F(x,y):= y\text{ est un ordinal isomorphe à } x$ est une relation fonctionnelle et l'image $Y$ de $X$ par $F$ (donnée par le schéma de remplacement) est l'ensemble de tous les ordinaux or une telle chose ne peut exister ($Y$ serait de fait lui-même un ordinal avec $Y\in Y$ ce qui est impossible).Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$. -
Avec (AC) et en acceptant la définition usuelle du bon ordre (mais beaucoup trop restrictive à mon goût), il existe bien un bon ordre $\leqslant_{\Bbb{R}}$ sur $\Bbb{R}$. Si tu possèdes le Dehornoy, je t'invite à aller aux pages 71, 74 et 76. Il n'y a pas que l'opération successeur qui permet d'obtenir des ordinaux.Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
-
OuiCar si R est semblable à un nombre ordinal, IR est en bijection avec un nombre ordinal
Non, $\omega_1$, par exemple est le plus petit ordinal non dénombrable (et, avec HC, il est en bijection avec IR)qui se construit par successeur, donc qui est dénombrable (enfin je pense).
Un ordinal peut être successeur, ou limite. -
Bonjour TP et merci. Je vais bientôt finir le Halmos, je passerai sur le livre de Dehornoy ensuite. En parcourant rapidement le chapitre 2 de ce livre, ce qu'il est dit dans ce chapitre correspond, en plus détaillé, à ce qu'il est dit dans le livre de Halmos. Dans le livre de Dehornoy, il s'agit du théorème de comparaison.
Ma question reste donc. Je comprends mieux maintenant pourquoi l'axiome du choix, qui induit que tout ensemble peut être bien ordonné, est décrié. Dans le livre de Halmos, cette démonstration est très superficielle.
EDIT : je n'ai pas lu vos messages depuis le 1er message de TP, je vais les lire attentivement. -
Ah oui, quand on passe des éléments de $\omega$ à $\omega$ lui-même, ce n'est pas un successeur. Je pressentais que la faille se trouvait là. Merci.
-
@Julia : tu considères l'ensemble de tous les bons ordres sur $\omega$. Par le théorème dont tu parles, à chacun de ces bons ordres correspond un ordinal. Par le schéma de remplacement tu as le droit de parler du sup de cette famille d'ordinaux. Ce sup est appelé $\omega_1$. C'est donc un ordinal qui, par définition, est strictement plus grand que tous les ordinaux dénombrables. Donc il n'est pas dénombrable.
-
Ensuite tu peux regarder l'ensemble de tous les bons ordres sur $\omega_1$, qui sera leur borne supérieure ? etc. (:D
-
"The guy who made the joke :
$$\mathbb N, \mathcal P(\mathbb N), \mathcal P(\mathcal P(\mathbb N)), \mathcal P(\mathcal P(\mathcal P(\mathbb N))), ...$$
The guy who made the same joke, but louder:
$$\omega, \omega_1, \omega_2, \omega_3, ....., \omega_\omega, \omega_{\omega +1}, ..., \omega_{\omega_1}, ...$$" -
Merci beaucoup Martial. L'axiome de remplacement permet de former une fonction sur $\omega$ qui attribue un ordinal à chaque bon ordre sur cet ensemble. Cela forme une famille, et le sup de cette famille d'ordinaux (qui forme une chaîne comme toute collection d'ordinaux) est l'union des ordinaux de la collection, qui est lui-même un ordinal. C'est cela ?
Donc il est strictement plus grand que tous les ordinaux dénombrables (mon livre n'utilise pas ce terme, du moins je ne l'ai pas encore vu, je suppose qu'on les obtient tous avec les ordres sur $\omega$ (qui sont tous des bons ordres ? mais peu importe, on ne considère que les bons ordres sur $\omega$)) ; donc il n'est pas dénombrable car un ordinal ne peut pas appartenir à lui-même.
On obtient donc un ordinal non dénombrable.
Ok, je crois que je faisais un peu une confusion entre dénombrable et nombre ordinal.
Et avec l'hypothèse du continu, $\mathbb R$ est isomorphe à $\omega_1$, ordinal non dénombrable.
Merci à tous. -
@JP : je dirais plutôt que l'on a une fonction définie sur l'ensemble de tous les bons ordres sur $\omega$ à valeur dans la partie $\mbox{On}$ au sens intuitif d'un certain univers, partie formée de tous les ordinaux uniquement.Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
-
Attention, les ordres sur $\omega$ ne sont pas tous des bons ordres. Par contre les bons ordres sur $\omega$ forment la collection des ordinaux dénombrables (ou plus formellement, l'ensemble des ces bons ordres est en bijection avec cette collection).
Dire que $\mathbb R$ est isomorphe à $\omega_1$ sous l'hypothèse du continu n'est pas tout à fait correct car parler d'isomorphisme sous-entend un isomorphisme de structure ordonnée, et ce n'est pas le cas pour la structure usuelle sur $\mathbb R$. C'est plutôt qu'il existe une bijection entre $\mathbb R$ et $\omega_1$, ou en d'autres termes, qu'il existe un bon ordre sur $\mathbb R$ de type $\omega_1$. -
Poirot : non, en principe la.collection de ces bons ordres est beaucoup plus grosse , c'est "modulo isomorphisme" qu'elle est en bijection avec $\omega_1$
(D'ailleurs, en fait, elle est de taille $2^\omega$ si on ne quotiente pas, exercice ;-) ) -
Oui tu as raison bien sûr. Ce que j'avais à l'esprit c'était que les éléments de $\omega_1$ sont les types d'ordre des bons ordres sur $\omega$, autrement dit, $\omega_1$ est un plutôt quotient de l'ensemble dont je parle.
-
@Julia : Fondamentalement, je crois que tu as tout compris. Tu peux maintenant passer à autre chose.
Maintenant, si on n'est pas trop potes avec le schéma de remplacement mais si on accepte l'axiome du choix, on peut voir $\omega_1$ autrement. Soit $\leq$ un bon ordre sur $\mathbb{R}$ fourni par Zermelo (donc par AC). On peut se demander si toute partie stricte de $(\mathbb{R}, \leq)$ est dénombrable. Si oui, tant mieux. Sinon, on considère l'ensemble $E$ de tous les $\alpha \in \mathbb{R}$ tels que $[0, \alpha[$ est fini ou dénombrable. Cet ensemble n'est pas vide car $\emptyset$ lui appartient. Donc cet ensemble a un plus petit élément, noté $\beta$. $\beta$ est donc un ensemble bien ordonné non dénombrable dont toute section commençante est dénombrable. Et $\beta$ est exactement $\omega_1$.
C''est une mauvaise méthode, car AC n'est pas nécessaire pour définir $\omega_1$, mais dans un 1er temps ça peut aider à comprendre. -
Une petite question : pourquoi l'ordinal union des ordinaux de la collection obtenue en considérant tous les bons ordres sur $\omega$ est strictement plus grand que chacun de ces ordinaux.
En effet, une union d'ordinaux est un ordinal plus grand que chacun des ordinaux de l'union, mais pas forcément strictement plus grand (exemple : $3 \cup 5 = 5$). On sait que l'un au moins est infini (avec l'ordre naturel sur $\omega$), comment sont les autres ?
Exemple : quel est l'ordinal associé à $\omega = P \cup I$, avec l'ordre où on a rangé d'abord les pairs (avec leur ordre naturel) puis les impairs (idem) ? -
Martial, j'aurais dit qu'être dénombrable ou non est indépendant de l'ordre choisi sur l'ensemble ? (je n'ai pas encore vu cette partie). Dans ce cas, on sait qu'il existe des parties strictes de $\mathbb R$ non dénombrables (l'ensemble de ses nombres transcendants par exemple).
Puis pourquoi $E$ non vide induit qu'il a un plus petit élément (ce n'est pas forcément $0$ pour un ordre autre que l'ordre naturel, et pour l'ordre naturel, il faut se restreindre à $E \cap \mathbb R^+$) ? -
Soit $\alpha$ l'union des ordinaux de la collection obtenue en considérant tous les bons ordres sur $\omega$. Si $\alpha$ peut s'obtenir comme bon ordre sur $\omega$, alors il est dénombrable, donc $\alpha +1$ aussi, donc $\alpha+1$ peut s'obtenir comme bon ordre sur $\omega$. Par définition de $\alpha$, on a alors $\alpha+1 \subset \alpha$. Contradiction.
-
$P \cup I= \omega \times 2$.
-
Poirot, oui par exemple l'ordre $\geq$ n'est pas un bon ordre sur $\omega$.
Maxtimax et Poirot, ok, $(\mathbb R, \leq)$ est en bijection avec $\omega_1$, pas isomorphe. Mais il existe un bon ordre sur $\mathbb R$ qui le rend isomorphe à $\omega_1$, c'est ça ? -
Merci à tous. Je reviendrai sur cette discussion plus tard, n'ayant pas vu le lien entre ordre et dénombrabilité, ni les opérations sur les nombres ordinaux (autres que ceux finis) pour comprendre $\omega \times 2$.
-
C'est la même chose que $\omega + \omega$, c'est à dire :comprendre $\omega×2$.
0, 1, 2, 3, ... 0, 1, 2, 3, ...
ou plutôt
0, 1, 2, 3, ... 0', 1', 2', 3', ... -
Julia Paule : a priori ils ne sont même pas en bijection: "on ne sait pas" s'ils le sont. Enfin, on sait qu'ils peuvent l'être et peuvent ne pas l'être.
-
Et l'on retombe inévitablement sur ceci.Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
-
Thierry : je ne suis pas d'accord avec ton edit de mon post. Je voulais bien dire "et"
-
@Maxtimax : bonjour. J'espère que tu vas bien. C'est rétabli ; il y a donc une chose qui a dû m'échapper. Toutes mes excuses.Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
-
@Martial : Oui c'est ça.
@Julia Paule : Ce que voulait dire Martial est "On peut se demander si tout segment initial strict de $(\mathbb R, \leq)$ est dénombrable". Un segment initial étant de la forme $[m, \alpha[ = \{x \in \mathbb R \mid m \leq x < \alpha\}$ avec $m$ le plus petit élément de $\mathbb R$ et $\alpha \in \mathbb R$ (je rappelle que $\leq$ n'est pas l'ordre usuel, mais un bon ordre donné par Zermelo/AC sur $\mathbb R$). La dénombrabilité est bien sûr indépendante d'un quelconque ordre (on a justement dit qu'il existe une infinité non dénombrable de bons ordres dénombrables !). -
Pour compléter :
$\omega_1 +1$ est de même cardinal que $\omega_1$, mais possède un segment initial propre non dénombrable ($\omega_1$) -
Poirot et Martial, ah ok, ... pour tout segment initial strict ... (ce que mon livre appelle "section commençante"). Je relirai avec ce nouvel éclairage.
-
@JP : bonsoir. Pour la défense de Halmos, c'est le traducteur qui est fautif. Il a même pris le parti de supprimer des paragraphes entiers de l'original. Voici un énoncé original que tu sauras apprécier, j'en suis certain. Laisse tomber cette traduction complètement pourrie.Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
-
Bonsoir et merci TP. Oui le texte original est différent, rrr..., notamment dans le paragraphe où j'ai relevé une erreur dans la traduction de la démonstration de ce théorème : "le supremum (borne supérieure) des prédécesseurs de $a$ est $a$ lui-même" est faux : $\sup \{x \in X\mid x < a \}$ n'est pas forcément $a$, par exemple pour $a$ entier naturel, c'est $a-1$.
Donc j'ai supposé qu'il s'agissait des prédécesseurs au sens large : $\sup \{x \in X\mid x \leq a \}$, et le reste de la démonstration semble coller.
Bah je vais terminer ce livre, je n'ai plus trop le temps avant la rentrée. Mais je ne comprends pas qu'il soit tellement apprécié. -
Pour : http://www.les-mathematiques.net/phorum/read.php?16,2290174,2290388#msg-2290388, ok pour $E$ bien ordonné a un plus petit élément $\beta$. $E = \{ \alpha \in \mathbb R, [0, \alpha [$ est fini ou dénombrable $\}$, avec $\leq$ un bon ordre sur $\mathbb R$. Donc $ [0, \beta [$ est fini ou dénombrable, mais je ne vois pas comment on en déduit que $\beta$ est un ensemble bien ordonné, non dénombrable.
Car $\beta$ est un élément (i.e. un ensemble dans la théorie des ensembles) de $\mathbb R$, mais $\beta \in \mathbb R$ veut dire $\beta$ est inclus dans un ensemble dont l'ensemble des parties est $\mathbb R$ ?
Ma question est plus générale : si $x$ et $y$ sont des réels, que signifie $x \cup y$, ou plus simplement que signifie $x$ en tant qu'ensemble ? -
@JP : voici une maison d'édition qui nous permet de télécharger gratuitement les versions PDF de nombreux livres, dont ceux de Halmos qui ont été revus et corrigés. Pour ma part, je vais acheter cette nouvelle version via Amazon.Le chat ouvrit les yeux, le soleil y entra. Le chat ferma les yeux, le soleil y resta. Voilà pourquoi le soir, quand le chat se réveille, j'aperçois dans le noir deux morceaux de soleil. (Maurice Carême).
-
@JP : Dans le message de Martial, il y a des abus de notations que l'on fait quand on passe son temps à faire de la théorie des ensembles. (:P)
Martial identifie $\mathbb R$ à un ordinal (disons $\gamma$) avec le bon ordre dont l'existence est garantie par Zermelo/AC, de sorte que ses éléments soient eux-mêmes des ordinaux, en particulier des ensembles ordonnés. C'est aussi pour ça qu'il appelle $0$ le minimum de $\mathbb R$ (en réalité de $\gamma$) là où je l'avais appelé $m$ dans ce message, car j'avais conservé le "point de vue $\mathbb R$". Il faut bien comprendre que "ce" $0$ n'a aucune raison d'être le $0$ de $\mathbb R$ (même si, si on y tient vraiment, on peut bidouiller notre bon ordre de sorte que $0$ soit le minimum de $\mathbb R$, mais passons). -
Poirot a raison, j'ai grave abusé des notations, je vais essayer de rédiger ça correctement. Soit $\preceq$ un bon ordre sur $\mathbb{R}$, fourni par Zermelo/AC. (J'emploie exprès une notation spécifique pour ne pas le confondre avec $\leq$).
Premier cas : tout segment initial strict de $(\mathbb{R}, \prec)$ est fini ou dénombrable. Dans ce cas on a bien montré l'existence d'un ensemble non dénombrable dont toute section commençante est finie ou dénombrable.
Deuxième cas : le premier cas n'a pas lieu. C'est donc que l'ensemble
$$E=\{x \in \mathbb{R} : [0,x[ \text{ n'est pas dénombrable}\}$$
est non vide, où $[0,x[ = \{y \in \mathbb{R} : 0 \preceq y \prec x\}.$
Comme $(\mathbb{R}, \preceq)$ est bien ordonné, $E$ a un plus petit élément, disons $x_0$. C'est donc que $[0,x_0[$ n'est pas dénombrable, mais que toute section commençante stricte de $[0,x_0[$ est finie ou dénombrable.
Dans tous les cas on a bien prouvé (via AC) l'existence d'un ensemble $(X, \preceq)$ bien ordonné non dénombrable dont toute section commençante stricte est finie ou dénombrable.
A noter que jusqu'à présent on n'a pas utilisé le schéma de remplacement. C'est maintenant qu'on va s'en servir : par le counting theorem fourni par Thierry on sait qu'il existe un unique ordinal $\beta$ tel que $(\beta, \in)$ soit isomorphe à $(X, \prec)$. $\beta$ est donc un ordinal non dénombrable dont toute section commençante stricte (c'est-à-dire aussi tout élément) est dénombrable. Ce $\beta$, on l'appelle $\omega_1$.
Conclusion : le $\omega_1$ construit ci-dessus est le plus petit ordinal non dénombrable, et il est constitué précisément de tous les ordinaux finis ou dénombrables. -
Poirot, "Martial identifie R à un ordinal" grâce au bon ordre : ah, je vais relire à la lueur de cette nouvelle information. Vous avez une longueur d'avance sur moi !
-
Presque par définition, il existe un bon ordre sur un ensemble $E$ si et seulement s'il existe une bijection entre $E$ et un ordinal. Cet ordinal est un "représentant canonique" du type d'ordre en question.
-
Désolée pour mon retard, j'étais occupée à autre chose. Ok pour la démonstration de Martial (grosso modo, car j'ai du mal à comprendre à la base l'existence d'un bon ordre sur $\mathbb R$ vu que la démonstration du théorème du bon ordre : "tout ensemble peut être bien ordonné", qui utilise le lemme de Zorn, est plutôt imprécise dans mon livre).
Ok pour ta remarque, Poirot :
- s'il existe un bon ordre sur $E$, vu que tout ensemble bien ordonné est isomorphe à un nombre ordinal unique, alors il existe une bijection (croissante) entre $E$ et cet ordinal,
- s'il existe une bijection entre $E$ et un ordinal, vu que tout ordinal est un ensemble de nombres ordinaux, donc est bien ordonné, ce bon ordre peut se transmettre à $E$ via la bijection, ce qui fait de $E$ un ensemble bien ordonné. -
@Julia : tu trouveras dans ce chapitre (pages 28/29) une démonstration moins imprécise du fait que Zorn implique le théorème du bon ordre : tout est expliqué.
https://drive.google.com/file/d/1J8CNydU0YF3UeIs2G73YWFWKYBdShLn9/view -
Merci Martial, je vais regarder.
-
Pour $\mathbb R$ muni d'un bon ordre $\preceq$, et soit $0$ son plus petit élément. Soit $x$, tel que $0 \prec x$, un élément de $\mathbb R$. Quel est le plus petit élément de $]0,x [$ ?
-
Si $\R$ est muni d'un bon ordre, cela veut dire qu'il existe une bijection croissante de $\R$ vers un ordinal, soit $f$ cette bijection, donc $f(]0, x[)$ possède un plus petit élément $\alpha$, le plus petit élément de $]0, x[$ est $f^{-1}(\alpha)$.
-
Merci Médiat, ça marche.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 41
+30 Invités