Procédé diagonal de cantor

[invite694f6e61]

Bonjour! J'ai juste une petite question sur la démonstration du fait que l'ensemble R est indénombrable. Dans la preuve on prend l'intervalle ]0,1[ par exemple et on montre qu'il est indénombrable (et ainsi R l'est aussi), on suppose une liste de nombres:
0,a1 a2 a3 a4 a5 a6.... (une lettre numérotée est une décimale entre 0 et 9)
0,b1 b2 b3 b4 b5 b6....
0,c1 c2 c3 c4 c5 c6....
0,d1 d2 d3 d4 d5 d6....
0,e1 e2 e3 e4 e5 e6....
0,f1 f2 f3 f4 f5 f6....

Après on forme un autre: 0,a1 b2 c3 d4 e5 f6 selon la diagonale de la liste précédente, on constate qu'il est nouveau, donc la liste n'était pas complète, donc ]0,1[ est indénombrable.
Je ne sais pas s'il manque quelque chose, mais montrer que l'on a échoué à former une liste (pour avoir la bijection avec l'ensemble des naturels) ne signifie pas qu'une liste est impossible à former... A mon avis il manque une étape du raisonnement, ou alors je n'ai pas saisi quelque chose?
La preuve de wikipedia ne m'a pas non plus éclairci les idées, donc merci d'avance pour vos réflexions...
-----

[danyvio]

On forme une diagonale non pas avec a1 b2 etc mais avec les compléments à 9 de ces éléments.

Pour raisonner plus simplement, il vaut mieux écrire la liste en binaire, puis imaginer un élément formé de la diagonale, mais en remplaçant les 0 par 1 et inversement. Si cet élement préexistait dans la liste, il "couperait" la diagonale avec un élément de même valeur. Or c'est impossible, puisqu'on a inversé les éléments. Je me suis pressé faute de temps, et mon explicatijon mérite d'être éclaircie...

[invite42831122]

comme l'explique danyvio, à l'aide de la méthode de la diagonale, on CONSTRUIT un nombre qui n'est pas dans la liste, en raisonant par l'absurde :

si le nombre que l'on a construit se trouve dans la liste à la position n alors (au moins) la n-ième décimale sera differente : le nombre n'est donc pas dans la liste.

Je pense que ce qu'il manquait dans ton raisonement c'est le fait de prendre dans le nombre qui est construit le complément à 9 comme l'explique danyvo :

par exemple :
si 0, a1 b2 c3 ... = 0, 5 6 9 ...
alors le nom qui n'est pas dans la liste commence par 0, 6 7 0 ... (on ajoute 1 à chaque décimale ).. et donc le nombre ainsi construit et différent du nombre numéro n dans la liste par la n-ième décimale au moins ... est ce que c'est clair ??

[invite694f6e61]

Ah merci pour ce point... Mais bon je ne réalise toujours pas en quoi est ce que cela prouve qu'une liste en bijection avec N est impossible? On n'a simplement pas réussi à en fabriquer une...

[A voir en vidéo sur Futura]

[invite4ef352d8]

non on à considére une application de N->R quelconque et on a montré qu'elle n'était pas surjective (puisqu'on à trouvé un element qui était pas atteints). cela prouve qu'il n'existe pas d'application surjective de N->R.

[invite694f6e61]

Ah!! C'était tout bête, on a vu cette démo dans deux cours différents et jamais cet aspect n'a été mentionné... Merci!

[Arkangelsk]

Bonjour,

Je viens de lire plusieurs fils concernant la diagonale de Cantor et il y a au moins quelque chose que je ne comprends pas.

Où intervient l'hypothèse qu'il faut prendre des irrationnels dans la liste de départ ?

Si on choisit par exemple une liste de rationnels, par exemple avec les décimales xn=0 à partir d'un certain rang n.

On construit un nombre en ajoutant 1 sur la diagonale comme Cantor, à partir d'un certain rang, il n'y aura plus que des 1.

Du coup, ce nombre devrait être indexé par un naturel comme Q est dénombrable, lequel ?

[Médiat]

Bonjour,

Si on choisit par exemple une liste de rationnels, par exemple avec les décimales xn=0 à partir d'un certain rang n.

Voulez-vous dire qu'il existe n tel que tous les rationnels pris en compte ont des 0 comme décimales au delà de la n-ième (ensemble fini), ou que vous considérez les décimaux (ensemble dénombrable) ?

[Seirios]

Bonsoir,

Usuellement, on applique le raisonnement de la diagonale de Cantor à une liste quelconque de réels (compris entre 0 et 1). Si on demande à ce que les réels soit irrationnels, on construit un irrationnel qui n'est pas dans la liste, soit un rationnel, donc on ne prouve pas grand chose ; si on demande à ce que les réels représentent tous les décimaux (ie. dont le développement décimal est constant à 0 à partir d'un certain rang), on construit soit un rationnel qui n'est pas un décimal soit un irrationnel, et là encore, on ne montre pas grand chose...

Edit: Doublé, j'ai été un peu long à répondre.

[Arkangelsk]

OK, donc, implicitement, on doit prendre des réels quelconques rationnels ou non dans la liste de départ.

Disons que je prends l'ensemble des décimaux.

Si j'applique le procédé de Cantor, j'obtiens un décimal qui n'est dans dans ma liste de départ. J'ai donc créé une application non surjective, non ?

[Médiat]

Si j'applique le procédé de Cantor, j'obtiens un décimal qui n'est dans dans ma liste de départ. J'ai donc créé une application non surjective, non ?

Comment êtes-vous sûr de ce point ?

[Arkangelsk]

C'est donc forcément un rationnel non décimal ou un irrationnel ?

C'est pas évident pour moi, comment le démontrer ?

[Seirios]

Le procédé permet de créer un nombre qui est différent de tous ceux de la liste, donc si la liste contient tous les décimaux, le nombre créé ne peut pas être un décimal.

[Arkangelsk]

D'accord. Mais quand on prend une liste de réels quelconque, on ne peut avoir qu'un autre réel construit par le procédé, et qui n'est pas dans la liste.

[Seirios]

Tout à fait d'accord, et c'est pour cela que tu ne peux pas lister tous les nombres réels : dès que tu as une liste de nombres réels (ie. un ensemble dénombrable de réels), tu peux construire un réel par procédé de la diagonale de Cantor qui n'est pas dans cette liste.

Cela prouve donc que l'ensemble des réels n'est pas dénombrable.

[Médiat]

Bonjour,

Pour préciser ce qu'écrit Seirios, une liste de tous les réels comporte toutes les combinaisons de décimales possibles, or le procédé diagonal de Cantor fabrique (rait sir IR était dénombrable) un élément qui n'est pas dans la liste supposée complète, d'où la contradiction.

En ne prenant que les décimaux ou que les rationnels, par définition, la liste n'est pas exhaustive, et le procédé diagonal fabrique un élément qui n'est pas dans cette liste incomplète, pas de contradiction.

Une autre précision : la démonstration peut se faire soit en supposant que IR et dénombrable et on aboutit à une contradiction (ci-dessus), ou on montre que toutes listes dénombrables de réels est incomplète (méthode exposée par Seirios)

[Arkangelsk]

Bonjour,

Une autre précision : la démonstration peut se faire soit en supposant que IR et dénombrable et on aboutit à une contradiction (ci-dessus), ou on montre que toutes listes dénombrables de réels est incomplète (méthode exposée par Seirios)

D'accord, je suis OK pour la première démonstration par l'absurde. Pour démontrer que toute liste dénombrable de réels est incomplète, "toute liste" m'embête un peu, suffit t-il de prendre l'ensemble des éléments de Q de [0;1] ?

Autre question qui me vient : peut-on démonter que l'ensemble des irrationnels de [0;1] est indénombrable ? Et en ne faisant pas le sioux en disant que les réels de [0;1] sont indénombrables comme précédemment, et puis comme les rationnels sont dénombrables, donc ....

[Médiat]

Bonjour

D'accord, je suis OK pour la première démonstration par l'absurde. Pour démontrer que toute liste dénombrable de réels est incomplète, "toute liste" m'embête un peu, suffit t-il de prendre l'ensemble des éléments de Q de [0;1] ?

Ben non, puisqu'il faut le montrer pour toutes listes.

Autre question qui me vient : peut-on démonter que l'ensemble des irrationnels de [0;1] est indénombrable ? Et en ne faisant pas le sioux en disant que les réels de [0;1] sont indénombrables comme précédemment, et puis comme les rationnels sont dénombrables, donc ....

Pourquoi cette démonstration simple et élégante ne vous convient-elle pas ?

[Arkangelsk]

Bonjour

Ben non, puisqu'il faut le montrer pour toutes listes.

Je ne vois pas trop comment m'y prendre pour toutes les listes possibles alors.

Pourquoi cette démonstration simple et élégante ne vous convient-elle pas ?

Elle me va bien, c'est intuitif. Je demandais s'il y a un autre moyen de le démontrer sans passer par les réels.

[Médiat]

Je ne vois pas trop comment m'y prendre pour toutes les listes possibles alors.

Regarder le message de Seirios #15

Je demandais s'il y a un autre moyen de le démontrer sans passer par les réels.

Les irrationnels étant définis comme les réels qui ne sont pas rationnels, je ne vois pas comment éviter les réels ...

[inviteea028771]

Les irrationnels étant définis comme les réels qui ne sont pas rationnels, je ne vois pas comment éviter les réels ...

On peut peut être les définir comme les suites de ne sont jamais périodiques à partir d'aucun rang. Un peu artificiel comme construction, mais bon

Le problème, c'est qu'utiliser l'argument diagonal ici va être délicat : ça me semble mal barré de montrer que ce que l'on construit n'est pas périodique à partir d'un certain rang...

[Médiat]

Bonjour,

On peut peut être les définir comme les suites de ne sont jamais périodiques à partir d'aucun rang.

C'est à dire comme des réels non rationnels

[Seirios]

Le problème, c'est qu'utiliser l'argument diagonal ici va être délicat : ça me semble mal barré de montrer que ce que l'on construit n'est pas périodique à partir d'un certain rang...

Je ne pense pas que cela soit si difficile : on choisit un nombre dans pour la première étape du procédé, puis dans pour la deuxième étape, puis dans dans les deux étapes suivantes, puis dans , puis dans dans les trois étapes suivantes, etc.

Le développement décimal ne sera pas périodique.