Argument diagonal de Cantor

François14

Bonsoir,

classiquement, on présente l'argument de Cantor en numérotant les réels entre 0 et 1 et en numérotant leurs décimales. (On sait qu'historiquement, ce n'était pas tout à fait ça mais ce n'est pas mon propos.)

Un collègue a émis l'objection suivante: ok le réel "diagonal" n'était pas numéroté mais qu'est-ce qui me dit que l'ensemble des réels non-numérotés n'est pas dénombrable? qu'est-ce qui permet par le seul argument diagonal de montrer que [0;1[ n'est pas dénombrable?

Merci de m'avoir lu, je me plonge dans l'immense livre de Mrs Cori et Lascar pour essayer d'attrapper l'argument que je cherche,

F.D.

PS: que je ne m'habitue pas au nouveau forum et combien mon ancien avatar me manque :-(

JLapin

Il n'y a pas besoin de montrer que l'ensemble des réels non numérotés est indénombrable pour faire marcher l'argument diagonal de Cantor.

Il suffit de montrer que cet ensemble est non vide.

raoul.S

François14 a dit :

qu'est-ce qui permet par le seul argument diagonal de montrer que [0;1[ n'est pas dénombrable?

Car dans l'argument diagonal on suppose que $[0,1[$ est dénombrable et on aboutit à une contradiction en exhibant un réel qui n'est pas dans la liste.

C'est tout, nul besoin de se demander s'il y a une infinité non dénombrable de réels qui ne sont pas dans la liste car on a déjà obtenu une contradiction.

Poirot

L'argument diagonal fonctionne de par sa généralité. Quelle que soit l'énumération (dénombrable) de $[0, 1]$, celle-ci est incomplète. Ainsi il n'existe aucune surjection de $\mathbb N \to [0, 1]$. A fortiori l'ensemble des réels qui manquent dans une telle énumération est non dénombrable (sinon $[0, 1]$ serait dénombrable), mais on ne le prouve pas au cas par cas, c'est une conséquence de l'argument général.

FrançoisD0

Merci de vos éclaircissements,

amicalement,

F.D.

Lucjs

Bonjour
Ce que je ne comprends pas, c'est comment on peut définir la diagonale : elle suppose en effet une bijection entre les lignes et les colonnes, bijection inexistante.

Parler d'une "diagonale" c'est un peu comme le paradoxe de Russell.

Qu'est-ce qui empêche de conclure à l'inexistence de la diagonale plutôt qu'à l'inexistence de la liste ?

Poirot

En supposant par l'absurde l'existence de la liste, il y a bijection entre les lignes et les colonnes.

Foys

L'argument diagonal est extrêmement simple et ne suppose quasiment rien. Soit $P$ un énoncé (formule sans variable libre) et $R(\_ ,\_)$ une relation (propriété à deux arguments). Soit $u$ un objet tel que $\forall x, R (x,u) \Leftrightarrow (R (x,x) \Rightarrow P)$. Alors on peut en déduire $P$, en effet en particularisant l'énoncé précédent à $u$ on a $R(u,u) \Leftrightarrow (R(u,u) \Rightarrow P)$ (*). Supposons $(R(u,u))$. Alors $R(u,u) \Rightarrow P$ puis $P$. Donc $(R(u,u) \Rightarrow P)$. Donc (*) $R(u,u)$. Et comme $(R(u,u) \Rightarrow P)$, on a $P$.

Exemples: $P:=\perp$ et $R:= x,y \mapsto x\in y$ (Russel)

$P:=\perp$ et $R:= x,y \mapsto$ "le villageois $y$ rase le villageois $x$" ("Paradoxe du barbier"). Etc.