Autant d'éléments dans N et Q ?

[antoineg]

Bonsoir,

Un ami m'a dit qu'il avait été démontré qu'il y aurait autant d'éléments dans N (entiers naturels) et dans Q (rationnels).

Je ne peux pas y croire sans le voir.

Je ne parviens pas à trouver la démonstration via google; et je ne connais pas le nom du mathématicien.

Pourriez vous m'indiquer où trouver cette demo svp ? (Si elle existe!)

J'espère qu'il ne m'a pas fait une blague...

Merci à vous.
-----

[Tiky]

Il faut s'entendre sur qu'on entend par "autant d'éléments". Cantor a démontré que était équipotent à , c'est-à-dire qu'il existe une bijection de vers . C'est ce que ton ami a voulu dire.

http://www.bibmath.net/dico/index.ph...nombrable.html

[antoineg]

Je ne connaissais pas la défition de équipotent. Il s'agit de cela en effet.

Je vais me renseigner sur le procédé diagonal de Cantor donc.
Merci à toi!

[breukin]

Sans ça, on peut compter (énumérer) les rationnels ainsi :

0 ; –1, 1
–2, 2 ; –3/2, –1/2, 1/2, 3/2
–3, 3 ; –5/2, 5/2 ; –8/3, –7/3, –5/3, –4/3, –2/3, –1/3, 1/3, 2/3, 4/3, 5/3, 7/3, 8/3
–4, 4 ; –7/2, 7/2 ; –11/3, –10/3, 10/3, 11/3 ; –15/4, –13/4, –11/4, –9/4, –7/4, –5/4, –3/4, –1/4, 1/4, 3/4, 5/4, 7/4, 9/4, 11/4, 13/4, 15/4
...

à chaque étape, destinée à compter les fractions k/n dans [–n,n], on complète d'une unité à gauche et à droite, on complète les fractions d'ordre inférieur à n, avant de compter les fractions k/n.
On voit ainsi qu'on va bien passer par tous les rationnels.

[A voir en vidéo sur Futura]

[antoineg]

Ca me semble beaucoup plus facile (est ce la même chose ?) que la diagonale.
Je vois donc que l'on peut énumerer tout les éléments de Q avec ceux de N.

Cela marche t il pour le procédé inverse ? Afin d'avoir une bijection.

Je trouve vraiment incroyable ce théorème. Et j'ai beaucoup de mal à le croire.

[breukin]

Ce que j'ai décrit est une bijection par construction, puisque dans le comptage expliqué, on évite bien entendu de recompter deux fois le même rationnel. Comme vous le voyez, j'ai omis –14/4, –12/4, etc. parce que –7/2, –3, etc. sont déjà passés.

[antoineg]

Ha oui en effet!

Mais l'application va de N*N dans Q il me semble ?

J'ai le sentiment que vous avez besoins de tous les couples d'entiers pour créer tous les rationnels.
Comment est-ce une bijection de N vers Q; et non pas de N*N vers Q ?

[Seirios]

Bonjour,

Je trouve vraiment incroyable ce théorème. Et j'ai beaucoup de mal à le croire.

Il faut garder à l'esprit que dire que N et Q ont autant d'élément se fait dans un cadre précis. Cela signifie que N et Q ont le même cardinal (au sens de Cantor), c'est-à-dire qu'il existe une bijection entre N et Q (autrement dit, il est possible de "compter" les rationnels), mais on pourrait également dire que Q a plus d'éléments que N dans le sens où N est strictement inclus dans Q.
Donc si vous avez du mal à croire à se résultat, c'est peut-être parce que vous donnez une signification différente à l'expression "autant que" que celle donnée par Cantor.

[breukin]

Ma bijection va de N dans Q, puisque je compte les rationnels sous forme d'une liste énumérative :
0 : 0
1 : –1
2 : 1
3 : –2
4 : 2
5 : –3/2
6 : –1/2
7 : 1/2
8 : 3/2
9 : –3
10 : 3
11 : –5/2
12 : 5/2
13 : –8/3
14 : –7/3
15 : –5/3
16 : –4/3
17 : –2/3
18 : –1/3
19 : 1/3
20 : 2/3
21 : 4/3
22 : 5/3
23 : 7/3
24 : 8/3
...
Cet algorithme de comptage va passer par tous les rationnels.

[antoineg]

je vois bien maintenant !

J'essayais de faire le raisonnement sur une partie finie de N (un segment) et je voyais une infinité de rationnels entre chaque nombre entier. (entre 0 et 1; puis 1 et 2 etc...)
On voit bien d'ailleur avec votre algo que la partie dans N va "plus vite".
D'où ce qu'a dit Phys2: il s'agit de créer une bijection de N tout entier vers Q...
Ca reste étonnant considérant qu'il existe une infinité de nombres dans Q entre chaque entier. Mais je comprends maintenant!

[invite986312212]

Je vais me renseigner sur le procédé diagonal de Cantor donc.

le procédé diagonal de Cantor c'est plutôt pour montrer que deux ensemble ne sont pas équipotents.