Diagonale de Cantor
Répondre à la discussion
Affichage des résultats 1 à 16 sur 16

Diagonale de Cantor



  1. #1
    zalteck

    Diagonale de Cantor


    ------

    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

    -----

  2. #2
    Médiat

    Re : Diagonale de Cantor

    Bonjour,
    Citation Envoyé par zalteck Voir le message
    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à ?).


    Citation Envoyé par zalteck Voir le message
    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    zalteck

    Re : Diagonale de Cantor

    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.

  4. #4
    Médiat

    Re : Diagonale de Cantor

    Citation Envoyé par zalteck Voir le message
    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 ?)).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  5. A voir en vidéo sur Futura
  6. #5
    zalteck

    Re : Diagonale de Cantor

    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 ?

  7. #6
    Deedee81
    Modérateur

    Re : Diagonale de Cantor

    Salut,

    Citation Envoyé par zalteck Voir le message
    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.
    "Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)

  8. #7
    gg0
    Animateur Mathématiques

    Re : Diagonale de Cantor

    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]
    Dernière modification par gg0 ; 29/05/2012 à 11h25.

  9. #8
    zalteck

    Re : Diagonale de Cantor

    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???

  10. #9
    Médiat

    Re : Diagonale de Cantor

    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.
    Dernière modification par Médiat ; 29/05/2012 à 13h32.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #10
    Deedee81
    Modérateur

    Re : Diagonale de Cantor

    Citation Envoyé par zalteck Voir le message
    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 ???
    "Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)

  12. #11
    zalteck

    Re : Diagonale de Cantor

    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 ... ???

  13. #12
    Médiat

    Re : Diagonale de Cantor

    Citation Envoyé par zalteck Voir le message
    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 ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #13
    Médiat

    Re : Diagonale de Cantor

    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 ?
    Dernière modification par Médiat ; 29/05/2012 à 14h08.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. #14
    gg0
    Animateur Mathématiques

    Re : Diagonale de Cantor

    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.

  16. #15
    Deedee81
    Modérateur

    Re : Diagonale de Cantor

    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.
    "Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)

  17. #16
    zalteck

    Re : Diagonale de Cantor

    ok. J'ai compris...
    Effectivement il y a une différence entre la recherche algorithmique de la solution (qui s'appliquerait au fur et a mesure, cas discret) et l’hypothèse mathématique (dans son ensemble)
    Merci "infiniment" pour ces explications.

Discussions similaires

  1. la diagonale de cantor
    Par physiquantique dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 18/11/2011, 22h35
  2. Matrice diagonale
    Par brady32 dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 23/04/2010, 13h15
  3. Matrice diagonale
    Par invite16343f37 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 27/11/2008, 08h38
  4. Diagonale de Cantor
    Par invite3443c7ee dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 20/09/2007, 09h05
  5. Indénombrabilité de R et diagonale de Cantor
    Par invite17fb38b6 dans le forum Epistémologie et Logique (archives)
    Réponses: 4
    Dernier message: 14/12/2006, 17h46