diagonale de Cantor, le retour

[invite73192618]

Bonjour,

Après fouille du forum plusieurs discussions existent mais rien que je n'arrive à appliquer à mes questions. J'ai du mal avec deux parties de cette démonstration.

Pour démontrer que R est non dénombrable, il suffit de démontrer la non dénombrabilité du sous-ensemble [0,1] de R, donc de construire, pour toute partie dénombrable D de [0,1], un élément de [0,1] n'appartenant pas à D.

Première partie ok, c'est une conséquence de la bijection de R sur soi-même. Mais la deuxième me laisse perplexe. Appelons P les nombres pairs, Q les multiples de quatre, D les multiples de douze.

Pour démontrer que P est non dénombrable, il suffit de démontrer la non dénombrabilité du sous-ensemble Q de P, donc de construire, pour toute partie dénombrable D de Q, un élément de Q n'appartenant pas à D.


=> Huit est un élément de Q n'appartenant pas à D, CQFD les nombres pairs ne sont pas dénombrables... oups... qu'est-ce qui manque ou qu'est-ce que je comprends de travers pour que ça marche pour R mais pas pour les entiers?

La non-unicité de l'écriture décimale pour les décimaux non nuls (deux écritures sont possibles pour ces nombres, l'une avec toutes les décimales valant 0 sauf un nombre fini, l'autre avec toutes les décimales valant 9 sauf un nombre fini) n'est pas un écueil au raisonnement précédent car le nombre diagonal x ne peut être décimal, puisque son écriture décimale est infinie et ne comporte que les chiffres 1 et 2.

Je ne comprend pas pourquoi ce ne serait pas un écueil dans cette démonstration. S'il suffisait de démontrer qu'il existe un développement décimal manquant pour au moins une énumération, alors il suffirait de prendre l'énumération
1=>0.1000...
2=>0.0100...
3=>0.0010...
...
puis de dire "il existe un nombre avec un 2". Pas besoin de diagonale! En réalité je suppose qu'il faut démontrer qu'il existe un nombre manquant quel que soit l'énumération choisie. Non?

Si c'est bien cela, je ne vois pas en quoi l'existence d'une double écriture pour les nombres ne serait pas problématique. Supposons qu'on se mette en binaire et que l'énumération soit:
1=>0.1000...
2=>0.0100...
3=>0.1100...
4=>0.0010...
5=>0.1010...
6=>0.0110...
7=>0.1110...
...

La diagonale serait alors 0.0011111... tel quel elle ne peut être directement dans la table (son premier chiffre empêche que ce soit la première ligne, son deuxième chiffre empêche que ce soit la seconde ligne, etc), mais à partir du moment où chaque nombre peut être représenté de deux façons (0.0111111111..... == 0.100000....) comment s'assurer que l'absence du développement empêche l'absence du nombre?

Dans mon exemple chaque nombre à deux développements, mais ne faut-il pas exclure non seulement cela, mais également des trucs plus tordus genre développement sur des bases à pas variable?

Bref je confuse et apprécierais un coup de main pour comprendre. Aussi, est-ce que la démonstration a été vérifiée avec un langage formel à la COQ? Si oui quels sont les axiomes?

A+
-----

[Amanuensis]

Annullé......

[Amanuensis]

Mais la deuxième me laisse perplexe. Appelons P les nombres pairs, Q les multiples de quatre, D les multiples de douze.

Pour démontrer que P est non dénombrable, il suffit de démontrer la non dénombrabilité du sous-ensemble Q de P, donc de construire, pour toute partie dénombrable D de Q, un élément de Q n'appartenant pas à D.

Pour toute. Pas "pour une".

=> Huit est un élément de Q n'appartenant pas à D, CQFD les nombres pairs ne sont pas dénombrables...

Ben non, pas CQFD, pas pantoute ! Suffit pas d'exhiber une partie ayant la propriété, il faut le montrer "pour toute".

[Médiat]

Bonjour,

Il va de soi que la démonstration doit porter sur toutes les parties dénombrables et non une, sinon, on pourrait démontrer que tout ensemble dénombrable E serait ... non dénombrable (il suffit de considérer E privé d'un élément pour avoir une partie dénombrable dans laquelle il manque au moins un élément).

Je ne comprend pas pourquoi ce ne serait pas un écueil dans cette démonstration. S'il suffisait de démontrer qu'il existe un développement décimal manquant pour au moins une énumération, alors il suffirait de prendre l'énumération
1=>0.1000...
2=>0.0100...
3=>0.0010...

Ben non puisque ceci est une partie de [0 ; 1[ (mieux que [0 ; 1]) et non toutes.

Pour la suite, je vous refais un sketch de la démonstration :
Soit une partie dénombrable de [0 ; 1[, soit une énumération de cette partie (c'est à dire une bijection entre IN et cette partie), il n'est donc jusqu'ici, nullement question de base.
Ensuite on choisit un entier n > 3 comme base et on applique la méthode de l'article de wikipedia en précisant que l'on ne prend en compte que les écritures propres (donc on écrit 0.12 et non 0.1199), le nombre fabriqué ne comprenant que des 1 et des 2 n'est donc pas sous forme impropre, et il n'existe pas dans notre liste qui est donc incomplète.

PS : wikipedia écrit "le nombre diagonal x ne peut être décimal", j'aurais écrit "le nombre diagonal x ne peut être un décimal"

[A voir en vidéo sur Futura]

[invite73192618]

Suffit pas d'exhiber une partie ayant la propriété, il faut le montrer "pour toute".

Il va de soi que la démonstration doit porter sur toutes les parties dénombrables et non une

Merci bien. Est-ce que, d'après vous, la diagonale de Cantor s'applique à la partie dénombrable ci-dessous (qui est en base 2)?

1=>0.1000...
2=>0.0100...
3=>0.1100...
4=>0.0010...
5=>0.1010...
6=>0.0110...
7=>0.1110...
...

en précisant que l'on ne prend en compte que les écritures propres (donc on écrit 0.12 et non 0.1199)

C'est un élément de la démonstration? Pourrais-tu m'expliquer comment on formalise ce type de phrase? Aussi, est-ce que la démonstration a été vérifiée avec un langage formel à la COQ? Si oui quels sont les axiomes?

[Médiat]

Merci bien. Est-ce que, d'après vous, la diagonale de Cantor s'applique à la partie dénombrable ci-dessous (qui est en base 2)?

1=>0.1000...
2=>0.0100...
3=>0.1100...
4=>0.0010...
5=>0.1010...
6=>0.0110...
7=>0.1110...
...

Pourquoi pas ?

C'est un élément de la démonstration?

Oui, pour supprimer le problème des écritures impropres, mais on peut le supprimer autrement (en disant que l'ensemble des nombres ayant deux écritures est dénombrable, par exemple).

Pourrais-tu m'expliquer comment on formalise ce type de phrase?

Le n^ième chiffre après la virgule de est tout simplement égal à modulo 10 (pour l'application de la méthode en base 10)

Aussi, est-ce que la démonstration a été vérifiée avec un langage formel à la COQ? Si oui quels sont les axiomes?

Aucune idée, mais je vois dans google que ce serait très dur à formaliser en COQ, ce qui me surprend énormément.

Vous avez là : http://forums.futura-sciences.com/ma...ml#post4362438 une formalisation de la diagonale de Cantor dans un cadre plus général.

[toothpick-charlie]

est-ce qu'il y a d'autres démonstrations que celle de Cantor?

[Médiat]

Le document : http://perso.ens-lyon.fr/florian.hatat/hatat_1.pdf donne l'impression que la formalisation en COQ n'est pas si compliquée que cela.
Le document http://graal.ens-lyon.fr/~ecaron/Tea...RFcoquille.pdf dit clairement : "beaucoup trop dur à formaliser en Coq"

Ces deux documents étant issus de l'ENS de Lyon ...

[Seirios]

est-ce qu'il y a d'autres démonstrations que celle de Cantor?

Tu peux également utiliser le théorème de Baire : un espace de Baire (en particulier un espace métrique complet) dénombrable est nécessairement d'intérieur vide.

[toothpick-charlie]

un espace métrique n'est pas égal à son intérieur?

[invite73192618]

Pourquoi pas ?

Hé bien c'est un exemple explicite où la diagonale est dans le tableau, puisqu'elle vaut 0.001111..., c'est-à-dire 0.01 en "écriture propre", qui est à la seconde ligne. Le fait est que cette énumération échappe à l'argument de la diagonale, alors que Il va de soi que la démonstration doit porter sur toutes les parties dénombrables et non une. .

Oui, pour supprimer le problème des écritures impropres, mais on peut le supprimer autrement (en disant que l'ensemble des nombres ayant deux écritures est dénombrable, par exemple).

En quoi est-il justifié de se limiter aux constructions pour lesquelles l'écriture de la diagonale est propre? Si la démonstration doit être valide pour tous les dénombrements, et non le sous-ensemble des dénombrements dont le listing donne une diagonale "propre", alors n'y a-t-il pas un problème?

Je vais l'exprimer autrement: je pensais avoir très bien compris le sketch, ce depuis des années, alors que je l'avais lu sous une forme qui n'incluait aucune limitation aux écritures propres. Maintenant je réalise que mon acceptation se basait sur une croyance intuitive que l'absence d'un développement "décimal" implique l'absence d'un nombre, ce qui est faux. Je ne vois pas comment réparer/compléter la démonstration d'une façon naturelle plutôt que ad hoc/douteuse (en particulier si on considère le cauchemar des bases à pas variables, dont je ne vois pas pourquoi elles ne devraient pas être aussi traitées par l'argument diagonale).

Le n^ième chiffre après la virgule de est tout simplement égal à modulo 10 (pour l'application de la méthode en base 10)

Astucieux merci.

Aucune idée, mais je vois dans google que ce serait très dur à formaliser en COQ, ce qui me surprend énormément.

N'est-ce pas? On pourrait penser que c'est un exercice classique à priori pas trop difficile, ce que sous-entend le premier document de l'ENS en 2006. Trois ans plus tard, de l'ENS toujours, c'est un problème très difficile. La démonstration ne fait pourtant qu'une demi page. Quel est le problème?

est-ce qu'il y a d'autres démonstrations que celle de Cantor?

Oui, et je ne doute pas que la conclusion soit juste. Par contre la validité/complétude de cette démonstration commence à me paraître douteuse.

[Médiat]

Hé bien c'est un exemple explicite où la diagonale est dans le tableau, puisqu'elle vaut 0.001111..., c'est-à-dire 0.01 en "écriture propre", qui est à la seconde ligne. Le fait est que cette énumération échappe à l'argument de la diagonale, alors que Il va de soi que la démonstration doit porter sur toutes les parties dénombrables et non une.

Je n'avais pas vu que c'était là votre point ; il suffit de ne pas prendre une numération en base 2 et le problème est résolu, ou alors :

En quoi est-il justifié de se limiter aux constructions pour lesquelles l'écriture de la diagonale est propre? Si la démonstration doit être valide pour tous les dénombrements, et non le sous-ensemble des dénombrements dont le listing donne une diagonale "propre", alors n'y a-t-il pas un problème?

Ce que je voulais dire c'est que si on peut démontrer que (E - F) est non dénombrable, alors que F est dénombrable, cela démontre que E est non dénombrable (donc ne prenons pas en compte les nombres ayant deux écritures, qui sont trivialement dénombrables.

Je ne vois pas comment réparer/compléter la démonstration d'une façon naturelle plutôt que ad hoc/douteuse (en particulier si on considère le cauchemar des bases à pas variables, dont je ne vois pas pourquoi elles ne devraient pas être aussi traitées par l'argument diagonale).

Mais il suffit de faire la démonstration dans une seule base, les listes que l'on fait ne dépendent pas de la base (comme je l'ai écrit dans ma première intervention), la base n'intervient que dans la contruction du nombre qui n'existe pas dans la liste, et en base 10 la démonstration présentée dans wikipedia évite complètement le problème des écritures impropres.

Vous pouvez le considérer comme ad'hoc (ce qui ne me gêne pas), mais certainement pas comme douteux.

[gg0]

En maths,

il n'y a pas de démonstration "ad hoc", il y a seulement des démonstrations valides et des preuves fausses ou incomplètes.
Le fait de modifier les conditions d'une preuve et de trouver que "ça ne marche pas" n'invalide en rien la justesse de la preuve, de même que l'arrivée du deuxième au "Vendée Globe" n'a pas remis en cause la victoire du premier.

Cordialement.

[toothpick-charlie]

il n'y a pas de démonstration "ad hoc", il y a seulement des démonstrations valides et des preuves fausses ou incomplètes.

j'approuve. Et je complète : il y a aussi des preuves jolies ou pas.

Par exemple je trouve plus jolie la preuve - qui fait usage de l'argument diagonal - du fait qu'il n'y a pas de surjection d'un ensemble E dans P(E). Elle est d'une simplicité biblique.

[Seirios]

un espace métrique n'est pas égal à son intérieur?

Si, justement, cela permet de montrer qu'il n'existe pas d'espace métrique complet, dénombrable et sans points isolés (j'ai oublié cette hypothèse dans mon message précédent, sans quoi serait un contre-exemple).

[invite73192618]

Je n'avais pas vu que c'était là votre point ; il suffit de ne pas prendre une numération en base 2 et le problème est résolu

Quelle est la différence entre "limitons nous aux énumérations en base >3" et "limitons nous aux énumérations des multiples de 12"?

Ce que je voulais dire c'est que si on peut démontrer que (E - F) est non dénombrable, alors que F est dénombrable, cela démontre que E est non dénombrable (donc ne prenons pas en compte les nombres ayant deux écritures, qui sont trivialement dénombrables.

Explicitons STP: E ce sont les nombres n'ayant pas deux écritures décimales. F ce sont les nombres ayant deux écritures décimales. Admettons que F soit dénombrable, d'une façon si triviale qu'elle n'a pas besoin d'être expliquée, même à quelqu'un qui ne comprend pas la démonstration de Cantor.

Si on prend la liste des nombres n'ayant pas deux écritures, alors les diagonalisations de E ne sont pas dans E.

C'est une représentation correcte de ton argument? Si oui 1) ne faut-il pas prouver que E n'est pas l'ensemble vide? 2) si la diagonale n'est pas dans E, alors ne faut-il pas prouver, avant de conclure que E est indénombrable, que les diagonales ne sont pas dans F non plus? Si oui cela impose une base >2, et on retombe sur exactement la difficulté auquel cet argument devait répondre.

il suffit de faire la démonstration dans une seule base, les listes que l'on fait ne dépendent pas de la base

Pourquoi serait-ce suffisant?

[toothpick-charlie]

Quelle est la différence entre "limitons nous aux énumérations en base >3" et "limitons nous aux énumérations des multiples de 12"?

peut-être que c'est que tout nombre peut s'écrire en base b>3 mais tout nombre n'est pas multiple de 12

[toothpick-charlie]

Explicitons STP: E ce sont les nombres n'ayant pas deux écritures décimales. F ce sont les nombres ayant deux écritures décimales. Admettons que F soit dénombrable, d'une façon si triviale qu'elle n'a pas besoin d'être expliquée, même à quelqu'un qui ne comprend pas la démonstration de Cantor.

en fait tu n'as pas besoin de démontrer que F est dénombrable. S'il est non dénombrable tu as prouvé le théorème, et s'il est dénombrable tu travailles sur E-F.

[Médiat]

Quelle est la différence entre "limitons nous aux énumérations en base >3" et "limitons nous aux énumérations des multiples de 12"?

1) Je ne considère pas les listes en base 3 mais l'ensemble des nombres quelque soit la façon dont on décide de les écrire.
2) Choisir une base, c'est choisir une façon d'écrire les nombres, pas les nombres.
3) Choisir les multiples de 12, c'est choisir les nombres (et non la façon de les écrire)
4) parler de base c'est une façon simplifiée de décrire l'algorithme, mais avec la formule que je vous ai donnée, il n'est jamais question de base.

Explicitons STP: E ce sont les nombres n'ayant pas deux écritures décimales. F ce sont les nombres ayant deux écritures décimales. Admettons que F soit dénombrable, d'une façon si triviale qu'elle n'a pas besoin d'être expliquée, même à quelqu'un qui ne comprend pas la démonstration de Cantor.

E c'est tous les nombres de [0; 1[, F sont les nombres qui ont 2 écritures décimales (ou binaire, ou octal ou ... suivant ce que l'on veut faire par la suite), c'est à dire les nombres dont une des écritures est finie (si on ne tient pas compte des 0, ce sont donc les suites à support fini, ou encore les suites finies de chiffres entre 0 et 9), c'est donc dénombrable.

Si on prend la liste des nombres n'ayant pas deux écritures, alors les diagonalisations de E ne sont pas dans E.

Oui, presque (les diagonalisations de E-F ne sont pas dans E-F).

1) ne faut-il pas prouver que E n'est pas l'ensemble vide?

Vous parlez sans doute de E - F, alors 0.1 (en base 10) est dans E-F

2) si la diagonale n'est pas dans E, alors ne faut-il pas prouver, avant de conclure que E est indénombrable, que les diagonales ne sont pas dans F non plus?

Il faut montrer que les diagonales ne sont pas dans E-F

Si oui cela impose une base >2, et on retombe sur exactement la difficulté auquel cet argument devait répondre.

Non, cela marche très bien pour la base 2 (on remplace les 1 par des 0 et les 0 par des 1)

[invite73192618]

Désolé pour la confusion entre E et E-F. Je reprendrais cela ce soir à tête reposée. Juste un petite question: pourquoi considérer que 0.1 est dans F, alors qu'il représente le nombre 1 donc ne fait pas partie de E? N'y-a-t-il pas là confusion entre les nombres qui ont une représentation décimale entre [0;1[ et les nombres qui sont dans [0;1[ ?

[Médiat]

Désolé pour la confusion entre E et E-F. Je reprendrais cela ce soir à tête reposée. Juste un petite question: pourquoi considérer que 0.1 est dans F, alors qu'il représente le nombre 1 donc ne fait pas partie de E?

J'ai bien précisé "en base 10", alors 0.1 = 1/9

N'y-a-t-il pas là confusion entre les nombres qui ont une représentation décimale entre [0;1[ et les nombres qui sont dans [0;1[

J'ai bien peur que vous fassiez cette confusion, or "les nombres qui ont une représentation décimale entre [0;1[" ne veut rien dire.

[invite73192618]

J'ai bien précisé "en base 10", alors 0.1 = 1/9

Ok, je pensais que c'était un typo (voir un trait d'humour). Tu mentionnes que ta technique marche très bien pour la base 2. Ne dois-tu pas alors montrer que E-F n'est pas vide, même avec une notation en base 2?

[Médiat]

Par exemple 0.01 (en base 2 cette fois)

[invite73192618]

Ok disons qu'on est le soir et voyons si j'ai bien compris:

Pour prouver que R est indénombrable il suffit de prouver qu'une de ses parties est indénombrable.
Soit E le sous-ensemble de R constitué des nombres inclus dans [0; 1[.
Soit F le sous-ensemble de E constitué des nombres qui terminent par une infinité de chiffres consécutifs identiques.
Soit E-F le sous-ensemble de E constitué des nombres tels 0.01 qui n'appartiennent pas à F.

Si F est indénombrable, alors E est indénombrable (oeuf corse, merci toothpick-charlie).
Si F est dénombrable, alors il suffit que E-F soit indénombrable pour que E soit indénombrable.

On applique ensuite l'argument de la diagonale à E-F:
Quelle que soit la façon d'énumérer les nombres de E-F, on considère la diagonalisation produite en remplaçant chaque chiffre de la diagonale par 0 (ou 1 si le chiffre est 0). Le résultat est dans E mais n'est ni dans F ni dans l'énumération de E-F, CQFD E est indénombrable.

Nope. Manque un truc. La diagonalisation n'est pas prouvée dans E.

On applique ensuite l'argument de la diagonale à E-F:
Quelle que soit la façon d'énumérer les nombres de E-F, en commençant sans perte de généralité par 0.10 ou n'importe quel nombre de E-F dont la première décimale est 1 de telle manière que la diagonale soit obligatoirement dans E, on considère la diagonalisation produite en remplaçant chaque chiffre de la diagonale par 0 (ou 1 si le chiffre est 0). Le résultat est dans E mais n'est ni dans F ni dans l'énumération de E-F, CQFD E est indénombrable.

Presque mais nope II. Comment prouver que la diagonalisation n'est pas dans F? (ou pourquoi peut-on se passer de le prouver?)

[Médiat]

Soit F le sous-ensemble de E constitué des nombres qui terminent par une infinité de chiffres consécutifs identiques

Non, F est constitué des nombres qui se terminent par une infinité de 0 consécutifs ou une infinité de 9 consécutifs (en base 10)

[invite73192618]

Non, F est constitué des nombres qui se terminent par une infinité de 0 ou de 9 consécutifs (en base 10)

Tu peux l'appeler F' si tu veux, c'est juste pour cleaner toute référence à la base (ou tu penses que cela introduit une erreur?)

[Médiat]

Bon je reprends :
Soit E = [0 ; 1[, et F = ensemble des décimaux (qui sont les nombres ayant une écriture impropre en base 10).

Si on démontre que E - F n'est pas dénombrable, à l'évidence E ne le sera pas.

Soit G une partie dénombrable quelconque de E - F, on fabrique le nombre diagonal x associé à G pour une bijection f de IN dans G tel que la n^ième décimale de x est 1 si la n^ième décimale de f(n) est différente de 1 et 2 si elle est égal à 1. Clairement x appartient à E, pas à F, donc à E - F, mais pas à G, qui n'est donc pas gal à E - F CQFD.

Vous pourriez objecter que l'on ne sait pas si E - F est dénombrable, donc difficile de considérer ses parties dénombrables, il suffit de considérer :
0.01
0.001
0.0001
etc.
qui est bien dénombrable et dans E - F

[invite73192618]

Ta démonstration est supposé marcher pour n'importe quelle base y compris binaire n'est-ce pas?

Clairement, x peut ne pas appartenir à E

0.1
0.01
0.001
0.0001

=>0.2, c'est-à-dire 1 en base 3

Clairement, x peut ne pas appartenir à F.

0.01
0.011
0.0111
0.01111

=> 0.02, c'est-à-dire 0.1 en base 3

[Médiat]

On se fout complètement de la base, je l'ai faite en base 10, la messe est dite CQFD.

[invite73192618]

correction de coquille:

Clairement, x peut appartenir à F.

Il est facile de modifier la démonstration pour s'assurer que x appartienne à E, ce que j'ai fait plus haut. Par contre s'assurer que x n'appartient pas à F n'est absolument pas clair.