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