Affichage des résultats 1 à 5 sur 5

Indénombrabilité de R et diagonale de Cantor



  1. #1
    nicola.levoilier

    Indénombrabilité de R et diagonale de Cantor


    ------

    Bonjour à tous,

    Voici la raison qui m'anime sur ce forum !

    Je m'interroge sur la preuve par diagonalisation de Cantor.
    Je me demande en fait si on ne peut pas en tirer un argument d'indécidabilité concernant les problèmes formulés sur un intervalle de R.
    Ces interrogations me sont venues à la suite de la lecture d'une autre preuve par diagonalisation : celle de l'indécidabilité de l'arrêt d'une machine
    de Turing. Je me suis imposé la rigueur de tout formaliser (pour chercher d'évnentuelles erreurs) mais pour des raisons de lisibilité sur le forum je
    donne ici une version informelle de ma question.

    1. La preuve de Cantor par diagonalisation de l'indénombrabilité de R.

    Voici le schéma de la preuve de Cantor telle que je l'ai comprise (attention je précise que je n'ai pas lu l'original, mais des versions dans des
    livres, des forums et des sites web).
    Soit l'ensemble K des suites qui construisent l'intervalle I=[0,1[ de R (i.e dont la limite tend vers une valeur de cet intervalle).
    Démontrer qu'une des séquences construites sur cet ensemble est indénombrable revient à démontrer que I=[0,1[ l'est aussi.
    On considère donc une séquence S quelconque établie sur les suites de K et on va montrer qu'à chaque fois qu'on tente d'établir une procédure
    qui "compte" les éléments de S, on peut construire une élément D de K qui échappe à cette procédure d'énumération.

    Voici les étapes :
    On suppose que cette séquence S est dénombrable, c'est à dire qu'il existe une bijection f entre N et S telle que pour tout élément s de S, il existe
    un unique n dans N tel que f(n) = s (n est l'indice de s).
    On construit l'élement diagonal D qui est différent des éléments de S (on a une procédure qui l'exibe pour toute séquence S).
    Cet élément diagonal n'est pas énuméré par f, il échappe donc au dénombrement... Il existe donc une infinité d'éléments qui échappent à toute procédure
    d'énumération de I=[0,1[.

    2. Mon interprétation

    A mon sens, pour toute propriété P formulable sur les réels de [0,1[, Cantor parvient a construire un élément qui échappe à la vérification de
    cette propriété P (1).

    Je donne un exemple pour la remarque (1) :
    On considère le sous-ensemble E des éléments e de [0,1[ de I qui vérifient une propriété P (on a P(e)=1) et
    le sous-ensemble E' de ceux qui NE vérifient PAS la propriété P (on a P(e)=0).
    On construit l'élément diagonal D à partir de la réunion des éléments de E et de ceux de E' (D existe puisqu'on l'a construit !).
    Cet élément n'étant pas dans E, on en déduit que P(D) n'est pas égal à 1.
    Cet élément n'étant pas dans E', on en déduit que P(D) n'est pas égal à 0.
    P(D) n'est ni vraie, ni fausse pour cet élément D. Donc, pour toute propriété P on peut construire un élément diagonal D de [0,1[ qui rend P(D)
    indécidable.

    En généralisant le principe (1), on peut reformuler la preuve de Cantor en considérant l'ensemble J des sous-ensembles de [0,1[ et que
    pour toute propriété P' formulée sur les éléments de J on peut construire un autre élément de J qui ne partage pas cette propriété P'.
    Si on considère J1 l'ensemble des éléments E de J tels que P'(E) = "E est dénombrable" soit vrai, on peut construire par diagonalisation un élément D de
    J qui échappe à la vérification de P. Donc la dénombrabilité de l'ensemble D est indécidable. Et comme cet élément est un sous-ensemble
    de [0,1[, on en conclut que la dénombrabilité de [0,1[ est indécidable.

    3. Mes questions

    Je trouve très, très bizarre cette conclusion : pour tous les problèmes P qu'on peut se poser sur R, il existe un élément de R pour lequel on ne peut
    résoudre P... C'est déconcertant, et évidemment je me doute qu'il y a une erreur quelque part... Si vous la voyez... Idem pour l'indécidabilité
    de la dénombrabilité de [0,1[... Quand je relis les preuves de non dénombrabilité, elles me conviennent pourtant très bien. On est logiquement conduit
    à la conclusion d'indénombrabilité. Tout ceci me dérange beaucoup.

    Autre question : savez vous s'il existe un lien bien mis en évidence entre indécidabilité et indénombrabilité ? Des articles là dessus ?

    Quels sont les arguments en faveur des mathématiques intuitionnistes, ou encore de la logique intuitionniste qui considère que l'axiome du tiers exclus
    est inacceptable ? Quels sont les mathématiciens qui réfutent/appuient ce pan des mathématiques ?

    Merci à l'avance de votre aide (c'est vertigineux!)

    Nicola Levoilier

    -----

  2. Publicité
  3. #2
    Invité

    Re : Indénombrabilité de R et diagonale de Cantor

    bonjour Nicolas

    la version que tu présentes de l'argument diagonal est remarquablement complexe...
    j'avoue avoir décroché...
    La version que je retiens est plus simple: elle consiste à supposer la bijection entre N et R[0,1[ et ensuite à construire un élément de ce deuxième ensemble qui diffère de tous les éléments de la liste supposée complète, en posant par construction qu'il diffère du premier élément par (au moins) la première décimale, du deuxième par la deuxième décimale etc...

    Je suppose que tu connais cette version simple ?

    Donc il ne me semble pas que la non dénombrabilité de R soit indécidable... il me semble que la version simple de l'argument diagonal le montre ?

    mais je suis prêt à me corriger si nécessaire

  4. #3
    nicola.levoilier

    Re : Indénombrabilité de R et diagonale de Cantor

    Oui absolument je la connais.
    Justement, c'est à partir de cette preuve que je me suis posé ces questions.

    Donc on établit la liste des éléments de R (on les énumère) et on construit un élément "diagonal" qui n'est pas dans la liste (donc il ne fait pas partie de l'énumération). Donc, les éléments de R ne peuvent être énuméré.

    Maintenant on considère ces conclusions très justes sous un autre angle :

    On formule une propriété P sur R.
    On construit la liste L qui contient tous les éléments de R qui vérifient cette propriété P (dans un ordre quelconque).
    On construit la liste L' des éléments pour lesquels P est fausse (encore dans un ordre quelconque).
    On construit l'élément diagonal D à partir de la liste obtenue par réunion de ces deux listes.
    Il n'est donc pas dans L ni dans L'.
    Donc, P(D) n'est ni vraie, ni fausse.
    Donc, pour toute propriété P formulée sur R, il existe un élément D (constructible par diagonalisation) pour lequel P(D) est indécidable.

    Voila, je trouve ça abérant... Et je comprends pas.
    Qu'en penses tu ?

    Nicola Levoilier

  5. #4
    Médiat

    Re : Indénombrabilité de R et diagonale de Cantor

    Bonjour,

    Je ne comprends pas ce que tu veux dire par :
    On construit l'élément diagonal D à partir de la liste obtenue par réunion de ces deux listes.
    L'un, au moins, de tes deux ensembles (que je préfère à liste) est non dénombrable (puisque la réunion est IR complet, en tout cas dans le cadre de la logique classique), cela ne va pas être facile de construire un "élément diagonal".
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  6. A voir en vidéo sur Futura
  7. #5
    nicola.levoilier

    Re : Indénombrabilité de R et diagonale de Cantor

    Ok j'ai compris l'erreur !
    On ne peut construire cet élément diagonal que si l'ensemble est dénombrable ... (bien sur...)
    merci pour vos réactions

Discussions similaires

  1. Matrice a diagonale strictement dominante
    Par exilim dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 12/11/2007, 00h50
  2. Diagonale de Cantor
    Par hedonyPower dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 20/09/2007, 09h05
  3. Complétude et indénombrabilité
    Par Bloud dans le forum Mathématiques du supérieur
    Réponses: 14
    Dernier message: 08/08/2007, 20h16
  4. Ensemble de Cantor
    Par Quinto dans le forum Mathématiques du supérieur
    Réponses: 18
    Dernier message: 27/06/2005, 17h15