la diagonale de cantor

[invite76db3c86]

Bonjour ,

j'ai apercu la démonstration de la non dénombrabilité de P(IN) par la diagonale de Cantor aujourdh'ui : la démarche était la suivante (d'après ce qui me reste).
On utilise une "aplication" qui associe une partie de IN à une suite de {0,1}^N tq le terme n de la suite est égal à 1 si l'élement a_n est dans cette partie et 0 sinon . Il me semble que l'on note V_A cette suite pour une partie A de IN (je suppose que V doit etre une bijection ...)
Par l'absurde , on suppose l'existence d'une bijection de IN dans P(IN) qui à n associe f(n) codée par une suite comme précédemment .
alors on construit un "tableau" des f(n) , et on note V' la suite définie à partir de la diagonale du tableau comme suit : le terme de la suite au i eme rang est 0 si l'élement à la ième colonne ième ligne est 1 et vis-versa .
on montre alors que f(n) n'est pas surjective car V' n'admet pas "d'antécédent" dans IN ...

La démonstration me semble infaillible , seulement j'ai du mal à visualiser ... J'ai l'impression qu'on ne peut construire des parties de IN à partir de nombres n assez "vite" pour pouvoir toutes les considérer ... C'est la seule façon que j'ai de voir cette démonstration.

COmment peut on visualiser mieux cette démonstration ?

Merci d'avance .
-----

[invitec3143530]

Dans l'article de Wikipédia, tu peux visualiser la démonstration (utilisée pour prouver la non dénombrabilité de R) : http://fr.wikipedia.org/wiki/Argumen...nale_de_Cantor

Pour ta démonstration, c'est exactement le même principe, au lieu des suites de décimales d'un nombre, tu as des suites de 0 et de 1 représentant des parties de N.

[invite76db3c86]

sauf que j'arrive toujours pas à bien saisir cette démonstration , en profondeur ... sinon je te remercie , meme si mon cours est , je pense , bien mieux fait que l'article de wikipédia qui est un peu trop formel ...
en tout cas ,j'ai l'impression qu'on doit une "fière chandelle" à cantor ...

[invitec3143530]

Je ne vois pas pourquoi tu ne comprends pas cette démonstration... Une partie de N est une suite de N dans {0,1} on est d'accord ? Il suffit de prouver maintenant qu'une suite de parties de N, c'est à dire une suite de suites de {0,1} n'est jamais surjective, on part d'une suite (ri) quelconque :

r1 = 0 0 1 0 1 1 1 0 …
r2 = 0 1 1 0 0 1 1 …
r3 = 0 1 1 0 1 1 0...
r4 = 0 0 1 0 1 1 1 0...
r5 = 0 0 1 1 0 1 1 0...
r6 = 0 1 1 1 0 1 0 0...
r7 = 0 0 1 0 1 0 1 1...

Et on construit une suite dont le premier élément est différent du premier élément de r1, le 2nd élément différent du 2nd élément de r2 etc, ainsi cette suite n'est égale à aucune ri, donc aucune suite d'éléments de P(N) n'est surjective.

Dans cet exemple la suite commence par1001100...

[A voir en vidéo sur Futura]

[invited5b2473a]

sauf que j'arrive toujours pas à bien saisir cette démonstration , en profondeur ... sinon je te remercie , meme si mon cours est , je pense , bien mieux fait que l'article de wikipédia qui est un peu trop formel ...
en tout cas ,j'ai l'impression qu'on doit une "fière chandelle" à cantor ...

Il existe une autre démonstration de la non dénombrabilité de IR en utilisant le théorème des segments emboîtés.