L'argument de la diagonale de cantor

[inviteb9ece61f]

Bonjour

CONTEXTE
Je me suis à relire récemment un livre de vulgarisation, pour revoir un peu les bases, mais surtout certaines démonstrations basiques qu'on passe un peu pour acquise. J'ai un niveau de Terminal S, donc j'arrive à suivre y compris pour remonter certaines évidences balancé en une phrase. Mais là je bute depuis une semaine sur l'argument de la diagonale de Cantor. Je le connaissais déjà, je l'avais accepté mais sans le comprendre.

QUESTION
Dans la présentation standard de l'argument, on nous présente ceci

Ce qui me dérange c'est que l'on construit un nombre qui n'est pas censé existé dans le tableau, mais que cela passe sous silence les éventuelles égalité entre les différentes "cases" du tableau.
Idem pour la version binaire ou le nombre en question "existe" par ailleurs.
En étant un peu bas de plafond si on prend l'exemple sur 3 "bit"
000
001
010
011
100
101
110
111(si on inverse comme dans l'argument)
Je sais que ce n'est pas l'argument d'origine car on est dans un cadre fini mais la diagonale existe dans ce tableau.

J'ai la sensation que cela à voir avec le rapport entre les deux dimensions du tableau, si on prend effectivement pour 3 bits uniquement trois lignes, l'inversion des valeurs crée une valeur qui n'existe pas dans le tableau mais pas une valeur impossible au regard de la combinatoire. Mais en même temps, ce n'est pas précisé dans l'argumentaire de base, et de même si on considère n'importe quelle principe combinatoire pour identifier les réels, le tableau sera plus long que large (même si ça n'a aucun sens avec des dimensions infinis)

Je ne suis pas entrain de dire que l'ensembre des réel est dénombrable, mais c'est une démonstration (ou la vulgarisation qui en est faite) qui coince car je la trouve un peu expéditive ou pas assez clair pour moi.

Comme je n'ai plus la joie d'être en classe pour poser une question stupide, si quelqu'un pouvait m'éclairer ce serait super. Je sais que cela semblera évident pour nombre d'entre vous, mais si vous pouvez me montrer ce qui cloche (ou même formule les raisonnements implicites que je rate), j'en serais plus que ravi.

Merci à tous.
-----

[Médiat]

Bonsoir,

si on prend effectivement pour 3 bits uniquement trois lignes

C'est bien là qu'est le truc : une bijection entre le nombre d'objets (lignes) et le nombre de colonnes, et justement l'argument diagonal est un raisonnement par l'absurde : on suppose que IR est dénombrable et on en déduit une contradiction

[Deedee81]

Salut,

Bardouli, si cette démonstration te chiffonne, malgré l'explication de Médiat, tu peux te tourner vers une démonstration plus abstraite et plus rigoureuse. Après tout, pas besoin d'avoir trente-six démonstrations pour avoir un théorème : une seule suffit. Elle a l'avantage d'être d'application plus générale (et s'applique aisément au cas des naturels et des réels).

- Soit S en ensemble quelconque et P(S) l'ensemble de ses parties.
- Considérons une application f de S dans P(S).
- Soit l'ensemble A des éléments x de S tels que x n'appartient pas à f(x). A peut être vide, peu importe, dans tous les cas c'est une partie de S.
- Soit un élément a de S tel que f(a) = A. Si on suppose que a appartient à A, alors on en déduit que a n'appartient pas à A et vice versa.
- Par conséquent il n'existe aucun élément dont l'image par f soit A.
- Par conséquent f ne peut pas être surjective
- Et donc il n'est pas possible de construire une bijection entre S et l'ensemble de ses parties.
- Et en particulier, on met aisément les réels en bijection avec les parties de N. Donc il n'existe pas de bijection entre N et R.

J'aime bien cette démonstration qui a l'avantage (outre sa généralité) de ne pas devoir se baser sur la représentation décimale des nombres et même pas besoin de parler de nombres.