Diagonale de Cantor

aspire99

À propos de l'argument de la diagonale de Cantor il y a un point que j'aimerais éclaircir.
J'ai bien compris la démonstration classique par l'absurde sur $[0,1]$. On "inverse" la diagonale pour montrer que le réel ne peut pas être dans la liste puisqu'on applique une fonction qui modifie chaque décimale des réels de la suite et décale ainsi le nombre réel.
Jusque la c'est bon.
Cependant la suite créée en diagonale peut très bien se trouver après puisque la suite de réels est infinie.
Sur un exemple de quelques chiffres de longueur finie c'est ce que l'on observe. La suite créée se trouve après certaine valeur par exemple sur une suite de 3  décimales.
Bref pourquoi dire que la diagonale inversée n'est pas dans la suite infinie ...?

[Utilisateur supprimé]

Parceque par construction, tous les éléments de la liste, ont en nième position un chiffre différent du nombre diagonal.

zeitnot

Oui il n'y pas d'histoire de avant ou après. Et qu'entends-tu par "décale ainsi le nombre réel" ?

stfj

Bonjour, je ne comprends pas bien ce que tu racontes. Écrivons la démonstration. Elle n'est pas longue, si je me rappelle bien. Supposons que $[0,1[\subset \mathbb R$ soit dénombrable. Il existerait alors une suite
\begin{align*}
b_1&=0,a_{1,1}a_{1,2}a_{1,3}\ldots\\
b_2&=0,a_{2,1}a_{2,2}a_{2,3}\ldots\\
b_3&=0,a_{3,1}a_{3,2}a_{3,3}\ldots\\
...
\end{align*} telle que $$\forall x\in [0,1[,\ \exists n\in \mathbb N^*,\ x=b_n$$Cela fait une base pour commencer qu'on corrigera si on le souhaite: j'oublie toujours un argument quand je fais cette démonstration

aspire99

En formalisant un peu j'ai :

e1= 0, a11 a12 a13 a14 ...
e2= 0, a21 a22 a23 a24 ...
e3=  0 a31 a32 a33 a34 ...

et diag= 0, a11 a22 a33 => decalage ou fct qui inverse
   diagInv = 0,b1 b2 b3 b4 ..
   avec b1!=a11 et b2!=a22 et b3!=a33 ...

aspire99

Si j'illustre mon propos sur une suite finie de 3 bits :
000
001
010  => diag inv= 1 1 1 qui apparait après

011
100
101
110
111
Je ne "vois" pas pourquoi ça ne marche pas avec une suite infinie ...? Ou plutôt où est mon erreur de raisonnement ...?

Dom

C’est peut-être dans ce que tu appelles « diagonale inverse » qu’il y a une incompréhension. 
Le réel construit avec la diagonale est un réel dont on connaît le développement décimal (construit par récurrence). On démontre que dans la liste, ce réel n’y est pas. 

Remarque : un fil a été créé au sujet de ce procédé. 

Il est amusant de regarder ce que cela donne avec une suite de nombres décimaux : le procédé crée un nombre non décimal (rationnel au moins). 

Médiat_Suprème

En fait, vous avez démontré que la liste 
0 0 0
0 0 1
0 1 0
est incomplète.

Foys

La preuve habituelle de l'argument diagonal n'est pas un raisonnement par l'absurde.

En voici une démonstration en COQ (qui est intuitionniste donc n'admet pas de raisonnement par l'absurde par défaut).

Section main.

  Variable pseudo_surjection: nat -> nat -> bool.

  Definition diag: nat -> bool :=
    fun (p:nat) => negb (pseudo_surjection p p).
  
  Theorem Cantor: exists f: nat -> bool,
      ~ (exists index:nat, forall n:nat, f n = pseudo_surjection index n).
  Proof.
    exists diag. intro ABS. destruct ABS as (i,e).
    absurd (negb (pseudo_surjection i i) = pseudo_surjection i i).
    destruct (pseudo_surjection i i); simpl; discriminate. apply e with (n:=i). 
  Defined.
  
End main.

Foys

(Dans le langage la commande "absurd" sert juste à appliquer $\perp \Rightarrow X$ où $X$ est l'énoncé que vous voulez; ce type d'inférence ne fait pas appel au raisonnement par l'absurde).

aspire99

Merci a tous pour ces réponses et votre temps.

J'ai eu un début de définition-démonstration, quelques phrases sibyllines, des tentatives d'explication et même une démonstration en logique (qui dépasse mes capacités) , toutes très intéressantes, mais aucune qui ne m'explique bien la ou ma compréhension s’arrête et ou mon intuition est mise en défaut.

Pour revenir a l'objectif initial, que j'ai compris, on construit une énumération d'un réel (a partir d'une suite de réels formé d'entiers) qui ne peut pas exister dans l’énumération que l'on parcourt (ce que je nomme le "avant" ) mais quid de l’après ? l'ensemble étant infini pourquoi supposer que ce réel ne se trouve pas plus loin (il n'y a pas d'ordre, ni de tri dans la liste des réels choisis ...)

gerard0

Bonjour.

La difficulté réside dans ce que tu appelles "plus loin". Soit c'est "plus loin dans l'énumération", donc un élément de l'énumération, qui a donc un indice fini, comme tous les éléments de l'énumération, et donc un chiffre différent de lui-même, ce qui est absurde; soit c'est après l'énumération, mais c'est contradictoire avec l'hypothèse que [0,1] est dénombrable, c'est-à-dire que tous ses éléments sont dans cette énumération.
Donc à toi de dire ce que signifie ton "plus loin" qui n'a pas de sens pour l'instant dans le cadre de cette preuve. Et qui ressemble fortement à une façon de dire "je le vois mais je n'y crois pas".
Cordialement.

NB. Ce n'est pas "une énumération d'un réel", mais la suite des décimales d'un réel entre 0 et 1 ("énumération" est un synonyme de "suite"). Et une énumération des réels entre 0 et 1 est une suite (infinie) comprenant chacun de ces réels une fois et une seule, donc chaque réel a bien un indice, ce qui donne un ordre sur ces réels, différent de l'ordre habituel. Dire "il n'y a pas d'ordre, ni de tri dans la liste des réels choisis" est bizarre, puisqu'il y a un ordre (celui de la suite), et ils ne sont pas choisis, ils y sont tous ; je ne comprends pas le mot "tri" ici.

Cordialement.

gerard0

En complément : Il ne s'agit pas de démontrer qu'il n'existe pas de suite infinie de réels entre 0 et 1 tous différents; seulement de montrer qu'une telle suite ne contient pas tous les réels compris entre 0 et 1.

zeitnot

aspire99 a dit :

Si j'illustre mon propos sur une suite finie de 3 bits :
000
001
010  => diag inv= 1 1 1 qui apparait après

011
100
101
110
111
Je ne "vois" pas pourquoi ça ne marche pas avec une suite infinie ...? Ou plutôt où est mon erreur de raisonnement ...?

J'essaie de comprendre ce que tu ne comprends pas.

L'erreur dans ton exemple vient du fait que dans la démonstration on s'arrête pas à 3, on considère l'écriture décimale infinie de chaque nombre d'une partie dénombrable de $[0; 1[$. Par exemple, la liste dénombrable contient le nombre 0,52, ce sera 0.520000000000000000000000000000 ... avec une infinité de zéros derrière.

Si tu rajoutes une infinités de 0 derrière ta liste, tu vas peut-être voir pourquoi ton argument ne fonctionne pas.
000 000000000000000000..........

001 000000000000000000........

010 000000000000000000..........

011 000000000000000000........

100 000000000000000000..........

101 000000000000000000........

110 000000000000000000..........

111 000000000000000000........
Ton "Diag inv"  devient : 111  111111111111111111111111

Il n'y a pas d'avant pas d'après ! Le nouveau nombre construit tient compte de tous les nombres de l'ensemble dénombrable considéré et n'est pas dans la liste par construction.

gerard0

Ah oui, j'avais zappé ce passage qui montre pourtant que la preuve dont parle Aspire99, il ne l'a pas vraiment lue. Elle parle de la suite infinie des décimales (avec une précision sur le choix pour les décimaux) et d'une suite infinie de réels. 
C'est toujours une mauvaise idée de raisonner sur des exemples finis pour parler de l'infini ! 
Cordialement. 

Foys

aspire99 a dit :
Cependant la suite créée en diagonale peut très bien se trouver après puisque la suite de réels est infinie.

Bonjour; que veut dire le mot "après" dans cette phrase ?

Le théorème en question est très général, ne parle pas de réels, d'entiers ni même d'ensembles infinis.

Soit $E,F$ deux ensembles. Soient $p,q$ deux éléments distincts dans $F$. Soit $i$ une fonction qui à un élément $e$ de $E$ fait correspondre une fonction $i(e)$ éventuellement partielle de $E$ dans $F$ (i.e une fonction qui est définie sur un sous-ensemble $D$ de $E$ et qui prend ses valeurs dans $F$). Le théorème "diagonal" de Cantor dit en fait ceci :

 il existe une fonction totale $g:E\to F$ (i.e. une fonction dont l'ensemble de définition est tout $E$ et qui prend ses valeurs dans $F$) qui n'est pas dans l'image de $i$ (autrement dit telle qu'il n'existe aucun $e\in E$ tel que $i(e) = g$).

Cette fonction est construite en faisant la chose suivante : soit $x\in E$, alors

(i) si $x$ n'est pas dans le domaine de définition de $i(x)$, on pose $g(x):=p$

(ii) si $x$ est dans le domaine de définition de $i(x)$ et si $i(x)(x)=a$, on pose $g(x):=b$

(iii) dans tous les autres cas (i.e. $x$ est dans le domaine de définition de $i(x)$ et $i(x)(x) \neq a$) on pose $g(x)=a$.

Il n'existe pas de $t\in E$ tel que $g = i(t)$. C'est l'argument connu et répété maintes fois plus haut. 

Le théorème est présenté comme "ceci n'est pas en bijection avec cela" mais il faut le voir plutôt comme un procédé constructif qui permet de construire infailliblement une fonction qui n'est pas dans un ensemble donné au préalable (l'image de $i$).

Foys

@aspire99 un autre point de vue.

Alice et Bob jouent au jeu (édité après que votre serviteur a commencé à retrouver ses esprits) suivant:
-Alice choisit une fonction $f$ de $\N \times \N$ dans $\{0,9\}$ (nombres réels entre $0$ et $1$ codés en base $10$)
-Ensuite, Bob choisit une fonction $g$ de $\N$ dans $\{0,9\}$.
-Ensuite Alice choisit $p\in \N$ .
-Ensuite Bob choisit $q\in \N$
Alice gagne si $f(p) (q) = g(q)$ sinon Bob gagne.

Très important: Les joueurs jouent les coups dans l'ordre ci-dessus (c'est la règle et n'est pas négociable; si ce point pose problème ça veut dire que tu as en fait un souci avec les quantificateurs, qu'on pourra d'ailleurs discuter par la suite).

Question : au jeu ci-dessus qui préfères-tu être ? Alice ou Bob ? Si la réponse est "Bob" avec conviction, alors tu es d'accord avec le théorème de Cantor.

aspire99

Tout ça c'est dans la diagonale de Cantor ...?  Je vais me racheter des lunettes : -)

Je vois quand mème mieux ou cela bloque, notamment au niveau de la démonstration. La liste est exhaustive par définition.

Et il n'y a pas de bijection possible entre les indices d'entier infini et les réels listés eux-mêmes infinis.

On construit un réel qui n'existe pas dans la liste de l'énumération infinie des réels d’écriture infinie.

Je le crois et le vois (presque ..!?). Ou je le vois mais je ne le crois pas.

@foys: pour le jeu ma conviction est ... plus ou moins forte.

zeitnot

"La liste est exhaustive par définition."
C'est la liste de quoi qui est exhaustive par définition de quoi ? Je ne comprends pas bien ?

Math Coss

NB : Dans le jeu d'Alice et Bob, une fois qu'Alice a choisi sa fonction, elle la rend publique, de sorte que Bob peut l'utiliser s'il le souhaite pour définir $g$.

NB 2 : $f(p)(q)$ pourrait être noté $f(p,q)$ par quelqu'un d'autre.

aspire99

Mais il n'y a pas de clé publique ou privée dans la diagonale de Cantor