@Nombrilist : en fait, tu as raison. Ca ne marche que quand on fait directement tendre n vers l'infini. Sinon, il faudrait ajouter quand même la condition p<=n, q<=n dans la somme de droite.

Tous les infinis n'ont pas la même taille.

Par exemple, une fonction qui, à chaque entier, associe un réel différent, ne peut pas être bijective (dit plus simplement : si on crée des couples du type "un entier + un réel", on aura fini de donner des partenaires à tous les entiers qu'une infinité de réels resteront encore sur le carreau, ou la béquille, je te laisse le choix de l'image).

Le problème parle de ça : peut-on faire rentrer une infinité supplémentaire de gens dans l'infinité de chambres ? Autrement dit, l'infini des nouveaux arrivants est-il du même ordre que l'infini des chambres, ou est-il énorme devant le nombre de chambres ?

On en remet une couche ? Je vais illustrer rapidement ce que tu dis.

J'associe à chaque entier le réel qui lui est égal ; j'obtiens l'infinité de valeurs

... ; -3 ; -2 ; -1 ; 0 ; 1 ; 2 ; 3 ; ...

J'associe à chaque entier le réel qui vaut cet entier plus un demi :

... ; -2,5 ; -1,5 ; -0,5 ; 0,5 ; 1,5 ; 2,5 ; 3,5 ; ...

J'associe à chaque entier le réel qui vaut cet entier plus un centième :

... ; -2,99 ; -1,99 ; -0,99 ; 0,01 ; 1,01 ; 2,01 ; 3,01 ; ...

J'associe à chaque entier le réel qui vaut cet entier plus pi :

... ; -1,8584... ; -0,8584... ; 0,1415... ; 1,1415... ; 2,1415... ; ...

Combien de listes différentes de réels puis-je construire ainsi ? Une infinité. Une infinité de listes infinies. Aouch.

Attention

Notre interprétation usuelle des suites de chiffres par des réels n'est pas une bijection.
C'est juste une surjection. Il y a plus de suites que de réels.


Donc en prouvant que l'ensemble des suites infinies de chiffres de la base dix est indénombrable, on a pas du tout prouvé que l'ensemble des réels est indénombrable.

J'ai beaucoup aimé la diagonale de Cantor a chaque fois que je l'ai rencontrée en cours.

Maintenant moins pour deux raisons :

- dans le cas des réels, on prouve la non-dénombrabilité de suites infinies de chiffres et non des réels. La preuve n'est pas finie. Si on enlève les 9 dans les suites de chiffres, on doit pouvoir mettre en bijection ces suites sans 9 avec un sous ensemble des réels mais ça me semble pas trivial.

- ce n'est pas une preuve constructive. On explique qu'on construit une suite dont on montre qu'elle n'appartient pas aux suites déjà indexées, mais en réalité on ne saurait pas la construire. Moralement, il y a qque chose qui me déplait dans le procédé.

En fait mes deux remarques sont des points qui m'ont vraiment beaucoup perturbé à une époque (euh toujours en fait ^^) et qui font que maintenant encore j'ai beaucoup de mal à vraiment appréhender la notion de réels.

J'ai longtemps considéré que les réels étaient exactement les suites infinies de chiffres de la base 10 car c'est ce qu'on apprend.
Puis j'ai appris que les suites ne sont pas les réels mais des représentations de ces réels.
Puis j'ai appris que cette représentation est redondante (écriture propre et impropre).
Puis j'ai appris qu'on ne peut même pas définir un algorithme d'addition sur cette représentation.
Finalement j'ai carrément douté qu'une suite quelconque de chiffres représente forcément un réel ^^. Mais une amie m'a ramené à la raison.

Mon premier point est vraiment de faire remarquer que la diagonale de Cantor prouve en réalité la non-dénombrabilité des suites infinies et l'on se satisfait trop facilement pour conclure à la non-dénombrabilité des réels directement car il faudrait montrer qu'il y a autant de réels que de suites infinies.

La preuve (je parle encore de Cantor) est non constructive car elle utilise l'absurde donc le tiers exclus. La preuve ne nous aide pas a trouver du sens à ce que l'on veut prouver mais à trouver du non-sens à son sa négation. 
En pratique dans la preuve on suppose l'existence d'une bijection entre suite infinies et entiers (pour la réfuter bien sûr) sans fournir la construction de cette bijection. Ce qui est normal car l'intention est de prouver l'inverse. 



Un dernier point à propos des réels et qui alimente ma perturbation :
On fait véritablement la distinction entre les réels constructifs (appelés aussi calculables) et les réels non-constructifs.
Les réels constructifs sont ceux qu'on sait décrire et dont on parle.  Les réels non-constructifs sont les autres. On ne sait pas les décrire car sinon ils seraient constructifs.
Et on montre que les réels constructifs sont dénombrables.
Au final que sont ces réels qui rendent l'ensemble indénombrable mais qui pourtant sont indescriptibles et qu'on ne rencontre jamais ?

@Mathias: Tu as raison, ce ne sont que les décimaux qui ont 2 écritures. Je me suis pris les pieds dans le tapis mais cela ne change pas le sens de mon propos ci-dessus.

@Nicouj: Je suis d'accord avec toi: la suite des chiffres d'un réel n'est pas le réel lui-même mais un représentation de celui-ci. Mais cela ne change pas la démonstration: on construit la représentation d'un réel existant qui n'est pas encore recensé. Le fait qu'on en construise une représentation équivaut à dire que le réel existe. Tu as raison, cela s'appuie sur la nécessité de prouver l'isomorphisme entre les représentations (propres pour les décimaux) de ce type des réels et les nombres qu'ils représentent mais cela est un autre problème (par ailleurs démontré) et on peut légitimement le supposer vrai dans le cadre de la démonstration de la diagonale de cantor.

Identiquement, la définition des réels par les coupures se fait par une approche de chaque réel. Il n'y a pas vraiment de moyen de définir un réel non rationnel "directement" (à l'aide de ses chiffres). Même pour les nombres algébriques (dénombrables et donc peu nombreux), on les définit à partir d'autre chose: [latex]\sqrt2[/latex]est la solution positive de x^2-2=0. En quoi cela donne-t-il sa valeur? En quoi est-ce meilleur que de dire que c'est la limite de la suite de ses chiffres? Ou la limite d'une suite (Un+1=(Un+2/Un)/2 par exemple) qui donne ses chiffres à chaque itération? Ou encore la limite de 2 suites adjacentes définissant une coupure dans [latex]\mathbb{Q}[/latex]?

Les nombres non-calculables, dont le fameux [latex]\Omega[/latex] sont en effet perturbants au premier abord. Mais en revenant réellement à la notion de nombre ils ne le sont pas tant que ça. C'est simplement que notre "éducation" mathématique nous a conditionné à définir un nombre avec des chiffres: les siens ou ceux d'une équation le définissant (voire même à confondre nombre et chiffre dans les cas extrêmes).
Il faut noter qu'être non-calculable pour un nombre ne veut pas dire qu'on ne connait aucun chiffre de sa représentation, simplement qu'on ne peut les connaitre tous. Il est souvent possible de calculer les premiers chiffres de sa représentation. Mais tous les autres chiffres existent aussi, c'est simplement qu'on ne peut pas les connaitre. La méthode de la diagonale peut donc très bien s'appliquer à eux aussi puisqu'on ne demande PAS de construire le nombre que j'ai appelé x ci-dessus mais seulement de prouver qu'il existerait. S'il emprunte des décimales à certains nombres non-calculables, il serait lui-même non calculable mais n'en existerait pas moins pour autant. C'est d'ailleurs comme cela qu'on démontre que les réels calculables sont dénombrables: grâce à la diagonale de Cantor.

Je trouve de ce point de vue 'i' bien plus perturbant. Quels sont ses chiffres ?
Il n'a pas de représentation habituelle (n'étant pas réel). Mais pourtant il ne nous pose pas de problème.

Merci en tout cas de ces discussions.
Qui aurait pensé que cette énigme nous emmenerait ici...

Je m'agenouille devant Rivas et la surprenante pédagogie de son long monologue, avec lequel je me suis régalé

Bouwah, j'tenais juste à préciser qu'il existe des astuces assez simples pour loger l'infinité de touristes de l'infinité de cars, mais j'vous remercie pour tous les jolis messages échangés plus haut et le coup du 5/2 ^^

Bref en assignant au p-ième bus le p-ième nombre premier et au n-ième passager du bus la puissance n-ième du nombre de son bus, on s'en sort pas mal après avoir précisé que les nombres premiers sont bien un ensemble infini dénombrable ordonnable.

Ce qui nous fait d'ailleurs une répartition avec bien plus de chambres visiblement vides que de chambres remplies et qui a le mérite de faire rêver.

Joyeux Noel et nouvelle année en attendant ^^