Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 24-02-2023 22:01:55
- JeanMars
- Membre
- Inscription : 04-06-2012
- Messages : 5
Dénombrabilité de l'ensemble des rationnels
Bonsoir à tous,
en voulant expliquer à mon fils de 13 ans la dénombrabilité de [tex]\mathbb{Q}[/tex], je lui ai demandé de trouver une relation entre les entiers [0,1,...] et les fractions de telle sorte que l'on puisse associer de façon unique un entier à une fraction (sans utiliser le terme bijection, fonction, etc.).
En gros, comment partir d'une fraction (p,q) et lui associer un nombre n sans que 2 fractions différentes ne soient associées à ce même n.
Je voulais lui faire découvrir le principe de l'énumération diagonale pour montrer que l'on peut trouver une bijection de [tex]\mathbb{N}[/tex] sur [tex]\mathbb{Q}[/tex].
Dans sa réflexion, il a fini par me dire:
"On n'a qu'à dire que l'on prend l'entier formé par p chiffres '2' suivi de q chiffres '1'."
Par exemple:
(1,1)-->21
(2,1)-->221
(1,2)-->211
(2,2)-->2211
...
(5,2)-->2222211
etc.
Et là, je ne m'y attendais pas et pour autant cela me semble parfaitement correct, on a bien défini une bijection de [tex]\mathbb{Q}[/tex] sur une partie infinie de [tex]\mathbb{N}[/tex] (et donc sur [tex]\mathbb{N}[/tex] car toute partie infinie de N est dénombrable).
Est-ce correct ?
Merci,
Jean
Hors ligne
#3 24-02-2023 22:43:28
- Glozi
- Invité
Re : Dénombrabilité de l'ensemble des rationnels
Bonsoir,
Je trouve ça extrêmement impressionnant venant d'un enfant de 13 ans !
Il faudrait dire qu'on prend la convention qu'on écrit les rationnels sous leur forme irréductible $p/q$ avec $q\in \mathbb{N}^*$ et $p \in \mathbb{Z}$ et $pgcd(p,q)=1.$
Il faudra faire attention au cas où $p$ est négatif (peut être rajouter un $3$ devant si $p<0$ ?).
Alors $f: \mathbb{Q} \to \mathbb{N}, p/q \mapsto \underbrace{3}_{\text{si }p<0}\overbrace{2...2}^{|p| \text{ fois}}\underbrace{1...1}_{q\text{ fois}}$ est bien définie et injective, et donc réalise une bijection $\mathbb{Q} \to f(\mathbb{Q})$.
Cependant attention :
(et donc sur $\mathbb{N}$ car toute partie infinie de $\mathbb{N}$ est dénombrable)
La phrase ci dessus est juste mais a priori non triviale ! (cela se vérifie bien avec l'axiomatique de Peano).
Sinon autre possibilité, le lemme de Cantor-Bernstein (assez intuitif mais pas forcément trivial à démontrer) : si $A$ s'injecte dans $B$ et $B$ s'injecte dans $A$, alors $A$ et $B$ sont en bijection.
Dans tous les cas, quand on n'a pas une bijection explicite il faut utiliser un outil pour conclure.
Bonne soirée
#4 24-02-2023 23:32:09
- JeanMars
- Membre
- Inscription : 04-06-2012
- Messages : 5
Re : Dénombrabilité de l'ensemble des rationnels
Bonsoir de nouveau,
merci pour vos remarques, mon fils a apprécié :-)
Pour les rationnels négatifs, j'avais limité moi-même aux positifs uniquement dans un souci de simplification, mais il avait également pensé à se servir du '3' pour étendre cette relation aux rationnels négatifs.
Pour ma proposition sur le fait que toute partie infinie de [tex]\mathbb{N}[/tex] est en bijection avec [tex]\mathbb{N}[/tex], c'est vrai que je suis allé un peu vite. Pour définir une bijection de [tex]\mathbb{N}[/tex] sur [tex]\mathbb{Q}[/tex] (ou l'inverse), à part l'énumération diagonale, il y a autre chose (de relativement simple quand même !)?
D'ailleurs à ce sujet, est-ce qu'il existe un ensemble infini "plus petit" que [tex]\mathbb{N}[/tex] ? C'est du genre indécidable comme l'hypothèse du continu ou il n'en existe pas?
Bonne soirée,
Jean
Hors ligne
#5 25-02-2023 00:41:56
- Glozi
- Invité
Re : Dénombrabilité de l'ensemble des rationnels
Bonjour,
Déjà il faut dire ce que ça veut dire un ensemble "infini".
Si $A\subset \mathbb{N}$, c'est facile on dit par exemple que $A$ est infini si $A$ n'est pas majoré.
On peut alors construire une bijection entre un $A\subset \mathbb{N}$ infini et $\mathbb{N}$, en considérant $a_0 = \min A$, puis $a_1 = \min A\setminus \{a_0\}$ etc...construction par récurrence).
Mais cela ne fait sens que pour des parties de $\mathbb{N}$ (car on a un joli ordre sur $\mathbb{N}$).
Avec plus de généralité, si $X$ est un ensemble quelconque on a plusieurs définitions de l'infini :
Définition 1 : $X$ est infini au sens usuel s'il n'existe aucun $n\in \mathbb{N}$ tel qu'il existe une bijection entre $X$ et $\{1,2,\dots,n\}$.
(ie $X$ est infini au sens usuel s'il n'est pas fini (en bijection avec un ensemble fini)).
Définition 2 : $X$ est infini au sens de Dedekind s'il existe une injection de $\mathbb{N}$ dans $X$.
(alors, il n'y a pas d'infini strictement plus petit que le dénombrable).
On a toujours $X$ infini au sens de Dedekind implique $X$ infini au sens usuel.
Pour la réciproque, on a besoin de quelque chose en plus (par exemple l'axiome du choix dénombrable) voir https://fr.wikipedia.org/wiki/Ensemble_infini il y a une démo de la réciproque en supposant l'axiome du choix dnb.
Bonne soirée