Discussion :

[patolin2]

Bonjour, comment demontrer(par l'absurde) qu'un ensemble de suites de binaires illimités, (c'est à dir b=b0,b1,b2,....) n'est pas dénombrable et à partir de cette raisonament déduire que R (ensemble des réels) n'est pas dénombrable non plus,


Merci beaucoup de votre aide.

[fumidu]

Je suppose que les suites infinies de binaires sont dénombrables.
On peut donc toutes les écrire dans un tableau :

suite 0 :b00,b01,b02,b03,b04...
suite 1 :b10,b11,b12,b13,b14...
suite 2 :b20,b21,b22,b23,b24...
...

Je considère maintenant la suite de nombres binaires suivante
1-b00,1-b11,1-b22,1-b33...
(je prend l'inverse des nombres de la diagonale)
Cette suite n'est pas dans le tableau, car elle a au moins un bit de différence avec chacune des lignes (le nième bit sera différent de bnn).
Donc toutes les suites ne sont pas dans le tableau : contradiction, donc les suites infinies de bits ne sont pas dénombrables.

On peut écrire tout nombre réel compris entre 0 et 1 comme une suite de binaires. Il suffit de l'écrire en base 2 (0.5(10) = 0.1000000...(2) par exemple). Et réciproquement. C'est une bijection. Donc si les suites de binaires sont indénombrables, les réels compris entre 0 et 1 aussi, et comme [0,1] € IR, IR aussi est indénombrable.

[pseudocode]

bravo !

Toutes mes felicitations a Cantor.

Heu, pardon. Toutes mes felicitations a fumidu.

[Zavonen]

Une variante ...
Il est démontré dans tous les bons bouquins de maths qu'un ensemble ne peut être équipotent à l'ensemble de ses parties.
Bref card(E) < card(P(E))
Or toute partie de N est en bijection avec sa fonction caractèristique qui est une suite de 0 et de 1, donc binaire:
par exemple la partie {1;4} est associée à :010010000000....
Toutefois pour reprendre la seconde partie de la démo, c'est un peu plus dur que ça. L'intervalle ]0;1[ n'est pas en bijection directe avec les suites binaires par l'écriture en base 2. c'est un peu plus compliqué que cela à cause des développements dits 'impropres' (on va pas revenir sur 0.99999....)
Bref, CERTAINS REELS ont deux développements.
Et ces réels sont justement les rationnels dont le dénominateur est une puissance de 2. Il suffit donc pour parachever le travail de démontrer que cet ensemble est dénombrable. Or c'est une réunion dénombrable d'ensembles finis, donc un ensemble dénombrable. On peut aussi dire que ça résulte du simple fait qu'il sont rationnels).
Pour démontrer que R est non dénombrable on part du fait que R est commensurable à un ensemble (les réels 'propres') dont la réunion avec un ensemble dénombrable (les réels impropres) donne un ensemble non dénombrable P(N).
Le résultat provient donc du fait que si R était dénombrable, P(N) le serait aussi comme réunion de deux ensembles dénombrables.
CQFD

[patolin2]

Merci à tous...

[fumidu]

bravo !

Toutes mes felicitations a Cantor.

Heu, pardon. Toutes mes felicitations a fumidu.

Honte à moi, j'aurais effectivement du citer l'auteur de la démo.

[Nemerle]

Pour démontrer que R est non dénombrable on part du fait que R est commensurable à un ensemble (les réels 'propres') dont la réunion avec un ensemble dénombrable (les réels impropres) donne un ensemble non dénombrable P(N).
Le résultat provient donc du fait que si R était dénombrable, P(N) le serait aussi comme réunion de deux ensembles dénombrables.
CQFD

Je ne comprends pas cette conclusion, qui ne me semble pas une preuve, voir pas relié à ce que ce dit avant (et pourquoi compliquer les choses avec la commensurabilité et les nombres dyadiques?). Par ailleurs, 3 remarques:

1. Les nombres dyadiques a/2^n sont effectivement les seuls nombres admettant deux développements (illimité & impropre), MAIS CECI EN BASE DEUX.

2. E est dénombrable ssi il existe une surjection de N sur E (ou ssi il existe une injection de E sur N)

3. Notons S l'ensemble des suites binaires. Généralement (mais chacun fait ce qu'il veut ), on utilise la non dénombrabilté de S (facile à montrer directement via 2) pour montrer la non dénombrabilité de P(N), car S est en bijection naturelle avec l'ensemble des fonctions de N vers {0,1}, lui-même naturellement en bijection avec P(N) via la notion de fonction caractéristique que tu as indiqué!
-