Diagonale de Cantor

[zalteck]

Bonjour

Actuellement je travaille sur les ensembles infinis et plus particulièrement sur le théorème de Cantor.
Après lecture de plusieurs articles sur l'argument de la diagonale de Cantor, dont celui de wikipedia (), je m'interroge sur la demo de la non dénombrabilité des réels.
C'est une démonstration par l'absurde dont j'ai bien compris le principe.
En revanche je ne saisis pas l'argument de la diagonale : on construit un nombre qui ne peut pas être dans la liste des éléments déjà énumérés ! Certes, mais la liste est infinie, celui-ci pourrait être après. De plus il n'y a pas de notion d'ordre dans la liste de départ donc rien ne garantit que ce nombre ne se trouve pas dans la suite et ne serait pas dénombrable (au sens pas de bijection de N sur E).
merci

[Médiat]

Bonjour,

En revanche je ne saisis pas l'argument de la diagonale : on construit un nombre qui ne peut pas être dans la liste des éléments déjà énumérés ! Certes, mais la liste est infinie, celui-ci pourrait être après.

Les nombres de la liste sont indexés par la bijection avec IN qui existe par hypothèse (et c'est cette hypothèse qui sera montrée absurde), et on montre que l'élément construit n'appartient pas à la liste et pas seulement à ceux "déjà énumérés" (qu'entendez-vous par là ?).

De plus il n'y a pas de notion d'ordre dans la liste de départ donc rien ne garantit que ce nombre ne se trouve pas dans la suite et ne serait pas dénombrable (au sens pas de bijection de N sur E).

Si, cette liste est ordonnée par l'ordre de IN induit par la bijection.

[zalteck]

Dans la démo que j'ai lue (version simplifiée sur [0,1]),
1/ la liste des réels est quelconque (pas d'ordre)
2/ on construit un nombre qui appartient a l'intervalle et qui ne peut pas dans la liste énumérée précédemment par construction
On en déduit que l'ensemble n'est pas dénombrable
J'ai du mal a comprendre l'argument utilisé la. Pour moi la liste est infinie et sans ordre initial on ne peut pas conclure.

[Médiat]

Dans la démo que j'ai lue (version simplifiée sur [0,1]),
1/ la liste des réels est quelconque (pas d'ordre)

Si : l'ordre induit par l'existence d'une bijection avec IN (que vous invoquez en disant "Liste" (ce n'est pas l'ordre naturel sur les réels (quel serait le successeur de 0 ?)).

[zalteck]

Comme je ne suis pas sur de comprendre la question, je reproduis la demo:

Pour démontrer que \mathbb{R} est non dénombrable, il suffit de démontrer la non dénombrabilité du sous-ensemble [0,1] de \mathbb{R}, donc de construire, pour toute partie dénombrable D de [0,1], un élément de [0,1] n'appartenant pas à D.

Soit donc une partie dénombrable de [0,1] énumérée à l'aide d'une suite r = (r1, r2, r3, … ). Chaque terme de cette suite a une écriture décimale avec une infinité de chiffres après la virgule (éventuellement une infinité de zéros pour un nombre décimal), soit :

ri = 0, ri1 ri2 … rin …

On construit maintenant un nombre réel x dans [0,1] en considérant le nième chiffre après la virgule de rn. Par exemple, pour la suite r :

r1 = 0, 0 1 0 5 1 1 0 …
r2 = 0, 4 1 3 2 0 4 3 …
r3 = 0, 8 2 4 5 0 2 6 …
r4 = 0, 2 3 3 0 1 2 6 …
r5 = 0, 4 1 0 7 2 4 6 …
r6 = 0, 9 9 3 7 8 1 8 …
r7 = 0, 0 1 0 5 1 3 0 …

…

Le nombre réel x est construit par la donnée de ses décimales suivant la règle : si la nième décimale de rn est différente de 1, alors la nième décimale de x est 1, sinon la nième est 2. Par exemple avec la suite ci-dessus, la règle donne x = 0, 1 2 1 1 1 2 1 …

Le nombre x est clairement dans l'intervalle [0, 1] mais ne peut pas être dans la suite ( r1, r2, r3, … ), car il n'est égal à aucun des nombres de la suite : il ne peut pas être égal à r1 car la première décimale de x est différente de celle de r1, de même pour r2 en considérant la deuxième décimale, etc.

Comment arrive-t-on a la non-dénombrabilité par cette preuve ?

[Deedee81]

Salut,

Comment arrive-t-on a la non-dénombrabilité par cette preuve ?

On montre qu'un nombre réel appartenant à [0,1] n'est pas dans la partie dénombrable de réels extraite de l'intervalle [0,1]. Ceci étant vrai pour toute partie dénombrable, cela signifie qu'il n'existe pas de partie dénombrable de cet intervalle qui reprenne tous les réels de cet intervalle. Donc l'ensemble des réels dans cet intervalle n'est pas dénombrable.

[gg0]

Bonjour Zaltek.

On y arrive immédiatement : Aucune partie dénombrable de [0;1] ne contient tous ses éléments. Donc :

Puis on contrapose.

Cordialement.

NB : [0;1] est une partie de [0;1]

[zalteck]

Merci pour toutes ces précisions.
Et je pense avoir compris le raisonnement sur les parties dénombrables.
En revanche je coince encore sur l'argument technique :

Le nombre x est clairement dans l'intervalle [0, 1] mais ne peut pas être dans la suite ( r1, r2, r3, … ), car il n'est égal à aucun des nombres de la suite...

La suite considérée (r1,r2,r3...) est infinie. L'algo de construction du nombre (infini lui meme mais passons) ne s'applique qu'a la partie finie de la suite.
Pourquoi x ne serait pas dans le reste de la suite infinie ?
huuum???

[Médiat]

Le nombre fabriqué (noté )peut-il être égal à l'un des ? Non, parce que pour tout , la nième décimale de est différente de la nième décimale de .

Si n'est égal à aucun des , cela montre bien qu'il n'est pas dans la liste.

L'algorithme de construction s'applique bien à toutes les décimales et pas seulement à une partie finie de ces décimales.

[Deedee81]

La suite considérée (r1,r2,r3...) est infinie. L'algo de construction du nombre (infini lui meme mais passons) ne s'applique qu'a la partie finie de la suite.
Pourquoi x ne serait pas dans le reste de la suite infinie ?
huuum???

Non, non, l'algo (qui doit plutôt être vu comme une définition du nombre x plutôt que comme algorithme séquentiel se déroulant en un certain temps) s'applique bien à toute la liste. Je ne comprend pas pourquoi tu as l'impression que cela ne s'applique qu'à une partie finie de la liste ???

[zalteck]

J'adore les math qui me font faire du français

@Mediat: ok pour toutes les décimales du nombre réel.
@Deedee81 : effectivement c'est plutot l'aspect fini de la chose dans le contexte infini que j'ai du mal a comprendre.
Mais j'en reviens a une vue plus algorithmique du problème :
ce qui me pose un problème ici, c'est la condition d’arrêt de l'algo, il ne pourra répondre que sur la partie déjà passée des arguments.
Pour résumer sur un ensemble fini, pas de souci la démo est claire mais sur un ensemble infini ...???
Dit autrement pourquoi x construit sur toute la liste ne serait pas dans la liste infinie ... ???

[Médiat]

Dit autrement pourquoi x construit sur toute la liste ne serait pas dans la liste infinie ... ???

je repose ma question : lequel serait-ce, s'il l'était ?

[Médiat]

Je vous propose une autre question, qui va vous montrer que toucher à l'infini oblige à laisser de côté certains réflexes (et certaines intuitions) :

Un train s'arrête à toutes les stations d'une ligne infinie, les stations n'ont pas de nom, elle sont numérotées 1, 2, ..., bref par les entiers.

A chaque station 10 personnes rentrent dans la rame et une personne en sort (et dire que des personnes se plaignent du métro parisien).

Après être passée dans toutes les stations, dans quel état se trouve la rame ? Pleine d'une infinité de personnes, vide, remplie avec 10 personnes, avec 127, autre solution ?

[gg0]

Zalteck

Mais j'en reviens a une vue plus algorithmique du problème :
ce qui me pose un problème ici, c'est la condition d’arrêt de l'algo, il ne pourra répondre que sur la partie déjà passée des arguments.

C'est ça qui te perturbe : Il ne s'agit pas d'un algorithme, mais d'une preuve mathématique (infinitiste).
Avec un algorithme, tu ne peux pas traiter un ensemble dénombrable (seulement prouver qu'il l'est parce que l'algorithme ne s'arrête jamais). Donc il faut te sortir cette idée de la tête et faire des maths, pas de l'informatique.

Cordialement.

NB : "On construit maintenant un nombre réel x dans [0,1] ..." n'est pas la définition d'un algorithme.

[Deedee81]

Salut,

Je vais insister sur cette histoire d'algo et d'arrêt. Ce n'est PAS un algorithme. C'est la définition du nombre x.

Supposons que je définisse une application dans les naturels, comme suit :
1 <-> 2
2 <-> 4
3 <-> 6
etc...
on devine aisément la suite.

Il serait absurde de dire que l'application est finie car l'algorithme de mise en correspondance doit bien s'arrêter un jour. La description ici permet de voir comment s'applique l'application sur l'ensemble des éléments de N, d'un seul coup.

Il en est de même de la description du nombre x. On décrit le lien entre ses décimales et celles des nombres de la liste. Tout comme la correspondance ci-dessus entre nombres entiers. Et ce lien s'applique à l'ensemble des éléments de la liste, d'un coup. Ce qui définit le nombre x.

Il en est de même pour le raisonnement disant que x n'appartient pas à la liste.