Bonjour, j'ai quelque problème pour comprendre avec la démonstration qui montre que les réel ne sont pas dénombrable à l'aide de la diagonal de cantor :

- Il est évident que dire qu'un nombre n = n+1 ça na pas de sens (on définit n comme étant différent de n, ce qui ne veut rien dire).

- Or dans la démonstration on prend comme hypothèse que R est dénombrable pour faire une preuve par l'absurde.
- On choisit de représenter le nombre R x avec x = 0.D1D2... ou chaque Di = autre chose que Dii (voir sur wiki, ils choisissent des 1 sauf si Dii = 1, alors ils mettent 2) et on obtient un nombre qui ne rentre pas dans le tableau de l'énumération car chaque nombre du tableau a sa décimale diagonale différente de celle de x en même position..
- Or comme on fait l'hypothèse que R est dénombrable, tout R est dans le tableau, et donc le x construit est déjà supposé être dans l'énumération (c'est l'hypothèse), or si on suit la définition de x, on le construit avec lui même (vu que x se construit sur chaqu'un des nombres du tableau, donc avec x), c'est ce point la que je ne comprends pas dans la démonstration.  

On peut très bien avec ce genre de construction montrer que les entiers N ne sont pas eu même dénombrable, il suffit pour cela d'inverser le sens de la représentation des entiers (l'entier 10 devient 01, et comme ça on peut avoir une suite de 0 infinie après l'entier qui n'a aucune influence, comme dans les R) et de construire un entier x dont son i ème chiffre est différent du i ème chiffre du nombre i dans l'énumération, ce qui le rend indénombrable.

Du coup je me dis que je dois être dans le faux quelque part dans ma compréhension, or je ne vois pas où.
Quelqu'un pourrait-il m'aider à faire la lumière la dessus ?

Merci d'avance.

Siron

L'argument diagonal de Cantor est très simple:
Si R est dénombrable, [0,1] est dénombrable et donc on a une bijection de N dans [0,1] n -> s_n donc on a une suite S = (s_n) telle que tout élément de [0, 1] soit élément de la suite S.
Partant de cela, il construit un réel qui est dans [0, 1] et qui n'est pas dans la suite S par construction, ce qui contredit l'hypothèse de départ de dénombrabilité de R.
On peut construire un tel réel x a partir de la suite S = (s_n) en posant: la partie entière de x est 0, et pour la partie décimale:
Si on note s_n(m) la m-ième décimale de l'élément s_n de la suite S, alors on construit x ainsi: la n-ième décimale de x sera s_n(n)+1 si s_n(n) =/= 9 et 0 si s_n(n) == 9 (bref, la n-ième décimale de x est la n-ième décimale de s_n décalée de 1 modulo 10). [note: si s_n a deux représentations décimales, on en choisit une, celle qui a une infinité de 9]
(*) Par construction, x n'est pas dans n, sinon, on aurait x = s_k pour un k, or par construction, la k-ième décimale de x est différente de la k-ième décimale de s_k, et donc x =/= s_k pour tout k. Mais par construction encore, x est dans [0, 1] d'ou la contradiction.
Bon, j'ai donné l'idée, mais il faut en fait affiner le raisonnement pour ne pas être coïncé par la non unicité de la représentation d'un réel comme suite de décimales, qui rend caduc l'argument (*). C'est ce que fait Cantor en utilisant une construction un peu différente pour x, qui évite cet écueil:
Si on note s_n(m) la m-ième décimale de l'élément s_n de la suite S, alors on construit x ainsi: la n-ième décimale de x sera 1 si s_n(n) =/= 1 et 2 si s_n(n) == 1. x n'ayant aucune décimale a 0 ou a 9, on est sur qu'il a une représentation unique. Et l'argumentation exposée en (*) est alors valable.

A+,

En fait la démonstration que tu me donnes est celle de mon cours (mais j'ai fillé celle de wiki pour pas la retaper), et effectivement c'est très simple.  Mais pourtant je ne suis pas d'accord :

Pour construire x, on utilise l'hypothèse de la dénombrabilité de R (principe de l'absurde), ce qui veut dire (on suit l'hypothèse) que tout réel est dans ta suite S, ce qui veut donc dire qu'il existe un s_n (0<n<00) tel que s_n = x.  Or comme on construit x avec un peu de chaque élément de S (on prend l'élément diagonal), on construit x avec un peu de s_n et donc un peu de x lui même.  Ce qui revient à faire n = n+1.

Pour moi, tel que je vois cette démonstration, elle conduit bien à une contradiction mais pas où on le pense, c'est ce que j'aimerais éclaircir.

Edit : En fait ce que je fais c'est prendre le truc dans l'autre sens avec l'hypothèse de dénombrabilité, ce qui montre une contradiction dans la démonstrations à un autre endroits (ou du moins plus tôt que prévu), maintenant ce que je fais est sans doute pas bon, mais je ne vois pas en quoi.

Edit2 : Pour expliciter mon point de vue, je dirais que ce qui me choque dans cette démonstration, c'est que on peut montrer (en faisant la même chose) qu'un ensemble dénombrable infini est lui aussi non dénombrable.

 
Non, parce que tout entier a une suite finie de chiffres qui le constituent.
Comment renverses tu le réel de [0,1] 0,1212...1212... ??
 
Tel que je vois les choses, par ta construction le x obtenu va a priori avoir une infinité de chiffres (et pas que des 0 a la fin) et donc ne va pas être un nombre entier.
A+,

Ce n'est pas comme ça que je voyais mon exemple, je ne remet pas en cause le fait que les réels soient indénombrables et je suis parfaitement conscient du problème de l'infinité des décimales dans les réels (et en discuter sortirait du cadre du topic pour un sujet sur le fondement des maths) , ce que je veux montrer par cet exemple, c'est que on peut arriver à une conclusion similaire au cas des réels avec le dénombrement des entiers en appliquant, tel que je l'ai compris, la démonstration de cantor.

Ce que je reproche dans ma compréhension de la démonstration de cantor c'est :

- On fait l'hypothèse que R est dénombrable (pour construire x).
- On construit un nombre R x (avec la propriété de dénombrabilité), qui, si x est effectivement dénombrable, ne pourrait pas être construit de cette manière (on ne peut construire le nombre z avec z = z+1).
- Puis on dit : oh, regardez la contradiction et on conclut que R n'est pas dénombrable.

Donc je suppose que il y a un truc qui m'échappe, mais quoi ?

Mais c'est pas ça. Je ne sais pas ce que c'est que ce (on ne peut construire le nombre z avec z = z+1). Il n'y a pas de ça ici. Pas plus qu'il n'y a de propriété de dénombrabilité sur x.
 
- On fait l'hypothèse initiale que R est dénombrable.
- On montre que avec cette hypothèse de départ, on peut aboutir à une contradiction: Si R est denombrable, alors il existe x tel que x est élément de [0,1] et x n'est pas élément de [0, 1]
- On en déduit donc que l'hypothèse initiale est fausse.
 
Je ne vois pas ce que ça a de compliqué a comprendre.
 

Et je vous ai expliqué pourquoi ça ne marche pas dans mon post précédent: parce que dans ce cas, le x construit par la méthode de Cantor n'aura pas toutes ses décimales (inversées) à zéro à partir d'un certain rang et donc que ce x construit ne correspondra pas à un entier inversé.
 
A+,

Pas très clair (c'est sûrement là l'erreur de raisonnement) peut tu nous dire ce que devient 21789?

J'ai cru comprendre qu'il en fait 0,9871200..00..
 
A+,

98712, y a rien de compliqué, l'avantage des réels sur des entiers c'est que on peut considérer qu'il sont de toute manière infini au niveau de la réprésentation(si ils sont fini, les décimales sont 0 et donc dans la démonstration de Cantor ça devient 1).  On peut aussi dire que en un sens chaque entier peut être infini => 0000 .... 00001 = 1.
 
Dans mon exemple j'inverse juste la représentation des entiers pour bénéficier du même avantage, mais on peut simplement inverser le sens de lecture, en fait l'exemple était là pour montrer ce à quoi me ramène la démonstration de cantor, mais je vois que ça embrouille plutôt.
 

 
Le problème c'est que l'élément construit x, comme R est dénombrable par hypothèse, se construit avec lui même : il y a un y tel que y = x et donc n_x(z) = n_x(z + 1), ce qui est le même genre d'ineptie que de dire qu'un nombre = ce même nombre + 1.  L'hypothèse de dénombrabilité impose que ce y existe avant même qu'on invalide l'existence de x par la contradiction, et donc la construction de x ne peut se faire.
 
 

 
Je ne tiens pas compte des réels infinis, et la démonstration ne se focalise pas dessus, si on me dit simplement qu'un réel infini ne se dénombre pas et que donc R est indénombrable, Ok, ça me va, mais ici c'est la démonstration que je trouve caduque avec sont principe de construction de x lié à l'hypothèse.
 
 

 
Voila, enlève le "0," et après on peut comme dans les réels mettre autant de 0 que l'on veut et donc pouvoir jouer avec des trucs du genre : chaque nombres est une suite de chiffre c1c2c3... sans ce soucier du fait que le nombre à vraiment un chiffre à la position x.

De toute façon N est la base de la "dénombralité" donc ça n'a aucun sens de vouloir y appliquer une démonstration qui a pour but de prouver la "non-dénombralité". De même que vouloir essayer de transformer n'importe quel N en R en l'inversant et en rajoutant des 0 ça voudrait implicitement dire que N = R ce qui est faux.
 
La démonstration de Cantor consiste à:
 
1) Supposer que les nombres de [0,1] sont dénombrables.
2) Si 1) est vrai on peut donc trouver une manière de placer tous ces nombres dans un tableau, chacun indicé par un Naturel différent.
3) Si on prend maintenant la diagonale et qu'on la modifie, on a un nombre sensé appartenir à [0,1] et donc qui doit se trouver dans le tableau à un indice bien précis.
4) Or par construction il ne peut pas se trouver à la première ligne, ni à la deuxième, ni à la ...
5) Pourtant il est sensé se trouver dans le tableau à un certain indice donc ça voudrait dire qu'il y a trou dans notre tableau avec des éléments sans indices, donc [0,1] n'est pas dénombrable et donc R n'est pas dénombrable.
 
Enfin c'est ça je crois le brol de Cantor, si je me souviens bien    

Je suis parfaitement d'accord avec toi bomberman pour la différence entre les R et N, mon but n'est pas de faire une équivalence, mais de montrer que l'incohérence que je vois dans la diag de cantor peut mener à beaucoup de chose.
 
1 & 2 : Tous les nombres réels sont dans le tableau.
3 : On modifie la diagonale, on crée un nombre à partir d'une décimale de chaque nombre du tableau.
Et c'est la que ça coince pour moi :
 
Par hypothèse 1&2, tout nombre réel est dans la tableau, donc normalement celui qui est crée aussi (c'est l'hypothèse).
Or le nombre créé est créé avec modification d'une décimale de chaque nombre du tableau, donc en partie avec modification de lui même en fait, et donc ce nombre ne peut exister vu que par hypothèse il est dans le tableau, mais par construction il est en dehors du tableau.  La construction viole l'hypothèse purement et simplement, ce n'est pas une question de on a un nombre qui est dans [0..1] par hypothèse, et qui est en dehors de [0..1] par construction, c'est on construit un nombre en violant l'hypothèse, et c'est ça qui ne passe pas.  Pour moi c'est comme si on disait que N n'était pas démontrable car on crée un nombre différent de chacun des nombres du tableau des nombres de N, ce qui peut ce faire de la même manière :  
 
- On inverse la lecture comme dans mon exemple plus haut.
- On crée le nombre z = c1c2c3c4...ci ou ci = cii du tableau.
- Du coups on ne peut pas non plus insérer z dans la tableau car il est différent de chaque nombre du tableau, et donc N est indénombrable (selon la démonstration hein, je ne le pense pas   ).

C'est donc bien ce qu'il me semblait, et on n'obtient alors que des nombres décimaux ainsi.
Le problème, c'est que le nombre que tu obtiens avec l'extraction diagonale n'est pas un nombre décimal (infinité de décimales valant 1 ou 2).

C'est quoi cet argument du  n_x(z) = n_x(z + 1)??  
Ca n'a rien a voir avec la démonstration que je t'ai donnée.
L'élément construit x ne se construit pas avec lui même, mais avec la bijection S de N sur [0,1] (qui existe du fait de la définition de la dénombrabilité hypothétique de R donc de [0, 1]).
A+,

C'est exactement ce que je lui ai dit.
A+,

Non. On construit un nombre de manière récurrente et simple a partir des termes d'une suite.

Pas du tout! Rien dans l'hypothèse n'interdit de construire un tel nombre de cette manière.
A+,

Mais ce n'est pas la mon problème, ce que j'essaye de montrer c'est que je bloque sur le fait que la construction viole l'hypothèse.

 
D'une suite qui est censé par hypothèse avoir tout les nombre, donc le nombre construit.

OK, je n'avais pas lu (j'ai répondu tout de suite au message).

Tout a fait.
Rien de l'hypothèse n'est violé par la construction. C'est ce que tu n'as pas l'air de comprendre. Effectivement, la construction (et le fait qu'elle apporte une contradiction) revient a une étape a construire x comme modification de lui même à une certaine décimale. Mais c'est une construction tout a fait licite du fait de la méthode employée, qui ne viole en rien l'hypothèse R est dénombrable.
A+,

On cherche une contradiction en supposant R dénombrable, donc si on arrive à trouver un nombre non dénombrable à partir de l'hypothèse c'est ce qu'on veut non ?

Pour les réels, tu supposes que tu prends la suite de TOUS les réels de [0,1]. C'est possible si tu suposes l'ensemble dénombrable.
La conclusion est que l'on crée un réels dans [0,1] qui n'est aucun nombre de la suite. D'où la contradiction.
 
Pour les entiers (et donc décimaux de [0,1]), tu supposes également que tu prends la suite de TOUS les dénombrables de [0,1].
Tu crées un élément qui est dans [0,1] ET qui n'est pas dans la suite, MAIS ce nombre n'est pas un décimal. Il n'y a donc AUCUNE CONTRADICTION.
 
En espérant répondre à ta question.

Pour le voir différement, tu peux aussi noter que l'argument de Cantor est en fait un cas particulier d'un théorème beaucoup plus général, également démontré par Cantor :
 

 
 
Démonstration : supposons que E et P(E) soient de même cardinal. Cela signifie qu'il existe une bijection f de E dans P(E). On considère l'ensemble T tel que a appartienne à T ssi a n'appartient pas à f(a). Puisque T est une partie de E et f une bijection, on peut trouver un b de E tel que f(b) = T. Est-ce que b appartient à T ?
 
Si b appartient à T, alors b n'appartient pas à f(b) par définition. Mais f(b) = T, ce qui est contradictoire.
 
Si b n'appartient pas à T, alors b n'appartient pas à T=f(b). Par définition, cela signifie que b est dans T : encore une contradiction.
 
On en déduit qu'il n'existe pas de bijection de E dans P(E).
 
Puisque R peut être vu comme l'ensemble des parties de N, card (R) <> card(N).

Oui je connais cette démonstration, mais je ne savais pas qu'elle était la généralisation de la démonstration avec la diagonale.  
 

Je ne vois absolument pas comment c'est étape est possible, quelque soit la méthode employée, ce sera toujours une contradiction pour moi de définir quelque chose comme étant en partie une modification de lui même.  C'est uniquement ce que je reproche au théorème, et c'est ce qui me bloque.
 
Mais je ne veux pas jour au pingpong sur le topic, merci à ceux qui ont participé au topic   .

Non, parce que dans la construction, au moment ou tu tombes sur l'élément de la suite u_k qui sera plus tard égal a x, x n'est pas encore construit complètement. Donc a cette étape la, tu ne peux dire qu'il est construit par modification de lui même. Des choses sur x, tu ne peux les dire qu'une fois la construction de x achevée.
A+,

C'est bon, avec ta reformulation j'ai compris le point de vue.  Mais c'est parce la suite est infinie et donc la diagonale aussi que la paradoxe peut se créer, or on peut aussi avoir une diagonale dans une série d'entier, qu'est ce qui nous empêche de reproduit la démonstration sur les entiers ?

La contradiction apparait parceque l'ensemble que tu as cru pouvoir dénombrer est par construction "tres gros".
Après avoir viré tous les éléments en bijection avec IN, il en reste encore.
Perso, je vois ca comme une dichotomie qui n'arrive pas à épuiser les éléments de E:
 
En prenant un exemple avec des ensembles finis:
tu prends l'ensemble des octets (il yen a 256 ...) et tu veux prouver qu'il y en a plus de 8.
Tu suppose qu'il yen a 8 que tu numérote de o1 à o8, et tu refais ton raisonnement diagonal qui n'est qu'une dichotomie avortée:
Tu dis que t as des éléments qui n'ont pas le meme 1er bit que o1.
Parmi ceux-ci, il yen a qui n'ont pas le même 2eme bit que o2.
...
...
Enfin parmi ceux qui restent, il yen a (au moins 1) qui n'a pas le même 8eme bit que e8.
 
Donc, tu ne définis par A PRIORI un élément diagonal, mais tu vire (par dichotomie ) tous les éléments qui n'entrent pas en contradiction avec la dénombrabilité.
Le miracle est qu'il t'en reste à la fin.

Mais qu'est ce qui nous empêche de faire le même raisonnement avec IN ?  Bien qu'on puisse dire que IN soit par définition le dénombrable, on peut très bien isoler un élément IN des autres éléments de IN de manière infinie (comme avec la diagonale), ce qui amène au même type de problème que dans IR.

C'est ce qui me perturbe dans cette démonstration, d'un point de vue je construis sur un ensemble fini par abstraction (pas forcément bien placée) et donc y a la contradiction mentionné avant, et de l'autre quand je vois la construction sur l'ensemble infini, la construction est valide mais je ne vois pas ce qui m'empêche de faire pareil avec IN.

Si tu essaie de faire le même raisonnement avec IN:
à la première étape, tu dis que IN possède une partie A1 formée d'éléments qui ont une certaine propriété (pas le même premier chiffre après la virgule que l'élément numero 1).
Ensuite, parmi les éléments de A1, tu dis qu'il ya une partie A2 formée d'éléments qui ont une certaine propriété (pas le même deuxième chiffre aprés la virgule que l'élément A2).
etc etc ....
Le problème, c'est qu'à un certain moment , tu risque de te retrouver avec un ensemble An vide, et tu pourra plus continuer.
Et c'est la structure meme de IR qui te prémunit contre ça.

Tu dis qu'après un certain nombre d'étapes l'ensemble An sera vide, mais les entiers sont également infini, donc je ne crois pas que ce soit si évident que ça (d'ailleur tu utilises bien le mot "risque" ).  Ce que je vois plutôt comme obstacle c'est que le nombre entier construit sera infini, ce qui n'est, contrairement au réel, pas envisageable.

c'est vrai, je me suis mal exprimé ... Les An étant emboités,  
au lieu de "à un certain moment, tu risque de te retrouver avec un An vide", ce qui ne sera pas le cas,
j'aurais du dire: "Tu risque de te retrouver avec l'intersection de tous les An vide"
Ce  qui peut arriver alors que tous les An sont non vide ...

Oui, tout a fait ...
Tes ensemble An sont de la forme ]an,+oo[, avec la suite (an) croissante.
Donc leur intersection est vide, sans qu'aucun ]an;+oo[ ne soit vide.
 
Alors que dans la démonstration de Cantor:
A0, c'est l'intervalle [0;1]
A1, c'est un intervalle du type [0.2;0.3] par exemple
A2, c'est un intervalle du type [0.25,0.26] ...
Etc, et l'intersection de ces intervalles est non vide.

Et bien je te remercie pour tes explications, je n'ai actuellement pas d'autre question, mais je sais que ça va encore gratter un peu dans ma tête sur le sujet (le temps de bien tout analyser ) et peut-être que je vais réetaler à nouveau mon ignorance sur ce sujet prochainement.