Cantor a tort ?

Preudhomme

Bonjour,

J'essaie de démontrer que Cantor s'est trompé dans un de ses théorèmes (L'ensemble P(N) des parties de N n'est pas dénombrable).
N'étant pas mathématicien moi-même je ne pense pas pouvoir déposer une thèse sur le sujet cependant j'aimerais défendre mon opinion.
Comment puis-je procéder ?

Cordialement,

Didier Preud'homme

TheVelho

Tu peux expliciter les raisons intuitives qui te font douter de ce résultat mais tu auras du mal à montrer que Cantor s'est trompé étant donné que c'est un résultat <B>vrai</B>.<BR>

Sylvain

Bonjour,

tu dis que tu n'es pas mathématicien (moi non plus d'ailleurs) et tu entends montrer que Cantor s'est trompé sur la foi de ton "opinion" ?
Sais tu ce que signifie le verbe "démontrer" ?

aleg1

un clone de jamel ??

Preudhomme

En utilisant une astuce mathématique, j'arrive à démontrer que P(N) est énumérable et donc infini dénombrable.

Didier

rémi

SUffit d'écrire ta preuve ici et quelqu'un te convaincra que tu as fait une erreur de raisonnement (désolé) qui peut bien sûr être subtile à déceler.
Si tu n'es pas convaincu après, il sera toujours temps de discuter de la façon de faire découvrir au monde ce que tu penses.

TheVelho

Fais-voir ?

En utilisant une astuce mathématique, Cantor arrive à montrer que $\mathcal{P}(\N)$ est en bijection avec $\R$ et donc non-dénombrable.

Bruno

Bonsoir Didier.

Je connais trois démonstrations du théorème de Cantor qui reposent sur trois méthodes fondamentalements différentes. On peut se tromper une fois, mais commettre trois erreurs différentes est très peu probable. Je serais intéressé de connaître les idées importantes de ta démonstration.

Bruno

Preudhomme

P($\N$) est en bijection avec $\N$, mais pas avec $\R$

Volny DE PASCALE0

Une preuve SVP ? Ou au moins une idée ?

Volny

TheVelho

Quelles sont les grandes idées de tes trois méthodes Bruno ? (Je ne connais qu'une seule méthode.)

Bruno

J'espère que ça va passer, le forum a l'air de très mal fonctionner.

Première, la méthode originelle je pense, tu associes à chaque partie de $\N$ la suite des $0$ et $1$ image de la partie par sa fonction caractéristique. Tu énumères toutes ces images, en supposant $\mathfrak P(\N)$ dénombrable, et par le procédé diagonal (de Cantor) tu construis une suite qui n'est pas dans l'énumération.

Deuxième méthode : Soit une énumération~$\varphi$ des parties de $\N$ et considérons $E = \{n \in \N \mid n \notin \varphi(n)\}$. Et posons $n_0 = \varphi^{-1}(E)$ alors :$$n_0 \in \varphi(n_0) \iff n_0 \notin \varphi(n_0)$$ce qui est une contradiction.

Troisième méthode, $\mathfrak P(\N)$ est en bijection avec~$[0,1]$ si celui-ci est énuméré par~$\varphi$, on peut associer au nombre~$\varphi(n) un intervalle ouvert d'amplitude $\dfrac 1{2^{n + 2}}$ centré en~$\varphi(n)$. Tu as là un recouvremant de $[0,1]$ par des ouverts. D'après Borel Lebesgues, tu recouvres donc cet intervalle par un nombre fini d'ouverts, donc la longueur de $[0,1]$ est strictement inférieure à la somme des amplitudes qui ont étées définie de façon à faire moins que $1$ :-))

Bruno

Bruno

J'espère que ça va passer, le forum a l'air de très mal fonctionner.

Première, la méthode originelle je pense, tu associes à chaque partie de $\N$ la suite des $0$ et $1$ image de la
partie par sa fonction caractéristique. Tu énumères toutes ces images, en supposant $\mathfrak P(\N)$ dénombrable, et
par le procédé diagonal (de Cantor) tu construis une suite qui n'est pas dans l'énumération.

Deuxième méthode : Soit une énumération~$\varphi$ des parties de $\N$ et considérons $E = \{n \in \N \mid n \notin
\varphi(n)\}$. Et posons $n_0 = \varphi^{-1}(E)$ alors :$$n_0 \in \varphi(n_0) \iff n_0 \notin \varphi(n_0)$$ce qui est
une contradiction.

Troisième méthode, $\mathfrak P(\N)$ est en bijection avec~$[0,1]$ si celui-ci est énuméré par~$\varphi$, on peut
associer au nombre~$\varphi(n)$ un intervalle ouvert d'amplitude $\dfrac 1{2^{n + 2}}$ centré en~$\varphi(n)$. Tu as là
un recouvremant de $[0,1]$ par des ouverts. D'après Borel Lebesgues, tu recouvres donc cet intervalle par un nombre
fini d'ouverts, donc la longueur de $[0,1]$ est strictement inférieure à la somme des amplitudes qui ont étées définie
de façon à faire moins que $1$ :-))

Bruno

Preudhomme

Dans ma démonstration, je montre qu'un ensemble p(A) où A est un sous-ensemble de (N) est énumérable en passant par le triangle de Pascal.

Soit A={1,2,3}
P(A) = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Car dans un ensemble un élément est unique et on ne tient pas compte de l'ordre c-à-d :
{1,2,3}={2,1,3}={3,2,1}

On a |P(A)| = |{}|+|{{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}|
= 1 + C3,1 + C3,2 + C3,3
= 1 + 3 + 3 + 1
= 8

où 1 + 3 + 3+ 1 est la 4ème ligne du triangle de Pascal.

Il existe donc une bijection entre P(N) et la dernière ligne du triangle de Pascal.

Sylvain

Sauf qu'il n'y a pas de "dernière" ligne du triangle de Pascal...

Pilz0

Pour Bruno,

ta troisième méthode est ma préférée , elle est très jolie, mais es tu sûr qu'elle ne se mord pas la queue...

Eric Chopin

Cher preud'homme,

tu as juste montré que l'ensemble des partie FINIES de N
est denombrable, ce qui est trivial puisque qu'on peut trouver une
injection de cet ensemble dans les rationnels...

Mais toutes les parties de N ne sont pas finies!

Dommage.... ;-)

a+

eric

joch

exactement, tu fais cette hypothèse implicitement dès le début de ta démo, donc même si tous les autres enchaînements sont bons, là y a un problème...

TheVelho

J'aime bien ta troisième méthode aussi, Bruno.
La deuxième peut se généralier à un ensemble quelconque et je pense aussi que la première est la méthode ``originelle''.

J'en connaissais encore une autre (Ce qui fait donc 4 en tout !) :

L'application
\[
f : \, \frak{P}(\N)\backslash\{\varnothing\} \longrightarrow \, ]0,1], \quad A \longmapsto \sum_{i \in A}10^{-i}
\]
est injective, tout comme
\[
g : \, ]0,1] \longrightarrow \frak{P}(\N)\backslash\{\varnothing\}, \quad 0,a_1a_2a_3... \longmapsto \{ a_i 10^i : i \in \N \}.
\]

Le théorème de Cantor-Bernstein permet alors d'affirmer que $\frak{P}(\N)\backslash\{\varnothing\}$ et $]0,1]$ sont en bijection, ce qui donne le résultat voulu.

(L'écriture décimale des réels de $]0,1]$ est unique si on ne considère que les écritures du style $0,41999 \dotsc$ et non pas $0,42000\dotsc$. Et que personne ne dise que ces deux nombres sont différents !)

Bruno

Bonsoir Pilz,

En quoi se mordrait-elle la queue ?

Bruno

okynox

Bravo Joch, tu as complètement résumé la situation : Tout le raisonnement de Preud'homme s'effondre!
Encore merci pour ta lucidité, maître Joch

Bruno

Pour TheVelho,

Bien sûr la seconde méthode est valable pour tout ensemble X, mais le rasoir d'Occam... La seconde méthode m'a été apprise par Chevalley dans le cours de topologie en 1964-65, je n'en revendique nullement la paternité (ni d'aucune autre d'ailleurs), il avait assez l'air content de notre ébahissement ! C'est étrange j'avais toujours cru que 0,419999... et 0,42000... Bon laissons tomber, je te crois sur parole :-))

Bruno

michael

pour suivre le topic sur mon mail

TheVelho

<http://fr.wikipedia.org/wiki/Rasoir_d'Occam&gt;

dSP0

Pour ceux qui ne connaîtraient pas l'astuce : la décomposition en base 2 définit une bijection de $\N$ sur l'ensemble des parties finies de $\N$.

jobherzt

pour preud'homme :

l'ensemble des parties finis de $\N$ est en effet en bijection avec $\n$, en bijection avec l'ensemble des polynomes, avec l'ensemble des suites nulles au dela d'un certain rang.... mais le "probleme" se presente quand tu passes aux parties infini..

en effet, dans une certaine mesure, tant que tu restes aux parties finies, tu n'as de l'infini que dans "un sens", tandis qu'en prenant les parties infinies, tu as d'une certaine maniere un "double infini" qui apparait, donc tu changes de dimension, d'echelle. je ne sais pas si c'est clair .... par analogie, tant qu'on considere des suites finies de rationnels, on reste dans les rationnels. pour faire apparaitre un reel ( et donc changer de "dimension", passer dans un espace plus grand ) il faut passer a la limite des suites infinies. entre le fini et l'infini, il y a un "saut" fondamental qui n'a rien de trivial en general.

_________________________________________________
Je viens de m'installer en allemagne, et je patine un peu en algebre. aussi, ne soyez pas surpris si je vous sollicite; ce n'est pas par flemme, mais bien parce que j'aimerais faire mes DM en entier

jobherzt

pour preud'homme :

l'ensemble des parties finis de $\N$ est en effet en bijection avec $\N$, en bijection avec l'ensemble des polynomes, avec l'ensemble des suites nulles au dela d'un certain rang.... mais le "probleme" se presente quand tu passes aux parties infini..

en effet, dans une certaine mesure, tant que tu restes aux parties finies, tu n'as de l'infini que dans "un sens", tandis qu'en prenant les parties infinies, tu as d'une certaine maniere un "double infini" qui apparait, donc tu changes de dimension, d'echelle. je ne sais pas si c'est clair .... par analogie, tant qu'on considere des suites finies de rationnels, on reste dans les rationnels. pour faire apparaitre un reel ( et donc changer de "dimension", passer dans un espace plus grand ) il faut passer a la limite des suites infinies. entre le fini et l'infini, il y a un "saut" fondamental qui n'a rien de trivial en general.

_________________________________________________
Je viens de m'installer en allemagne, et je patine un peu en algebre. aussi, ne soyez pas surpris si je vous sollicite; ce n'est pas par flemme, mais bien parce que j'aimerais faire mes DM en entier

jobherzt

en fait, tu as meme demontré que dans le cas fini, si $|P(E)|=\aleph$, alors :
$$|P(E)|=2^{\aleph}$$

sache que cette relation se generalise au cas infini, donc en particulier, pour tout ensemble E fini ou infini :

$$|E| < |P(E)|$$

_________________________________________________
Je viens de m'installer en allemagne, et je patine un peu en algebre. aussi, ne soyez pas surpris si je vous sollicite; ce n'est pas par flemme, mais bien parce que j'aimerais faire mes DM en entier

Lebesgue0

Bonjour

Non mais franchement on lit de ces choses sur ce forum : P(N) dénombrable .... hum
Plus sérieux : Je crois que cette question est encore non résolue :
Si E est un ensemble de cardinal > à celui de R, est-ce qu'un produit dénombrable de E est de cardinal égal à celui de E ?
Sachant que c'est vrai pour E = R, on serait tenté de répondre oui, mais comme le dit Lang (Algèbre p.905) : "Selon la rumeur, la réponse de Solovay serait non"

Alors ?

Ludovic

En tout cas, pour un produit fini c'est vrai.

benn0

Je voulais savoir comment definir une fonction surjective de $\N$ dans les parties finies de $\N$??

benn1

UTILISER LE FAITE QUE TOUT NOMBRE NATUREL n $\geq$ 2 ADMET UNE DECOMPOSITION UNIQUE COMME PRODUIT $p1^n1$$p2^n2$...$pk^nk$ ou k $\geq$ 1

Alain Debreil

Utiliser le fait que tout nombre naturel $n \geq 2$ admet une décomposition unique comme produit $ p_1^{n_1} p_2^{n_2} \ldots p_k^{n_k}$ où $k \geq 1$

Bruno

Bonjour benn.

As-tu répondu à ta propre question ou est-ce une précision de ta demande ?

Bruno

TheVelho

Une bijection entre $\N$ et ses parties finies est, pour $X \in \mathcal{P}_f(\N)$,
\[
X \longmapsto \sum_{n \in X}10^n.
\]

benn1

Dans cette question je dois utiliser le fait que tout nombre se decompose en produit de nombres premiers pour trouver une fonction surjective de N dans les parties finies de N

benn1

Bonjour Bruno, je voulais juste savoir comment definir une telle fonction

jobherzt

soit $(p_i)_{i\geq 0}$ la suite de tous les nombres premiers. tout nombre $n\in \N$ s'ecrit $n=\prod p_i^{N_i}$ ( tu notes que $N_i$ peut etre egal a 0, c'est important). il suffit d'associer a ce nombre, l'ensemble des $N_i$ distincts.. c'est bien une fonction surjective.

_________________________________________________
Je viens de m'installer en allemagne, et je patine un peu en algebre. aussi, ne soyez pas surpris si je vous sollicite; ce n'est pas par flemme, mais bien parce que j'aimerais faire mes DM en entier

Alain Debreil

Bonjour TheVelho

Quel est l'antécédent de 2 dans ta "bijection" ?
Sans doute voulais-tu écrire $ X \longmapsto \sum\limits_{n \in X}2^n $

Alain

Bruno

Bonjour benn.

TheVelo t'a donné une injection de l'ensemble $\mathfrak P_\omega(\N)$ des parties finies de $\N$ dans $\N$. En écrivant des puissances de $2$ au lieu de puissances de $10$, on doit obtenir une bijection.

Selon la méthode qui t'est proposée, on fait correspondre à l'entier $n$ l'ensemble des exposants qui figurent dans sa décomposition en nombres premiers. L'unicité de cette décomposition pour $n > 2$ nous prouve qu'on a une application de $\N \setminus \{0,1\}$ dans $\mathfrak P_\omega(\N)$. Cette application est presque surjective puisque si $X = \{n_1,...,n_p\}$, $X$ est l'image du nombre $2^{n_0}3^{n_1}...q^{n_p}$ où $q$ est le $p$-ème nombre premier. Il reste reste le cas de $\emptyset$ sur lequel on peut envoyer $0$ et $1$.

Bruno

TheVelho

Oui je me suis fourvoyé sur la "bijection'' plus haut et je voulais bien écrire 2 à la place de 10.

benn1

Merci tout le monde, je comprends mieux !!

lili M

Bonjour,

Pour Bruno :
Je ne comprends pas la troisième méthode
"$ \mathfrak P(\mathbb{N})$ est en bijection avec $ [0,1]$".
Ceci revient à déjà à dire que "$ \mathfrak P(\mathbb{N})$ n'est pas dénombrable car $[0,1]$ est en bijection avec $\N$.
Si on part de cette hypothèse, il n'y a rien plus rien à faire, non? Je crois que c'est cela que voulais dire Pilz par "se mord la queue".

Autre hypothèse (assez probable), je n'ai pas compris ce que vous avez écrit, pourriez-vous m'expliquer?

lili.

lili M

Pardon je voulais écrire $[0,1]$ en bijection avec $\R$... si un modérateur passe...

lili.

Bruno

Merci lili M.

Disons que c'est une méthode pour démontrer que $\R$ n'est pas dénombrable... Et comme les deux ensembles $\R$ et $\mathfrak P(\N)$ sont équipotents cette cardinalité rejaillit sur le second.

En me relisant, il me semble clair que je pars de l'idée que j'ignore tout de la cardinalité de $\R$.

Bruno

lili M

Merci Bruno, je comprends mieux. C'est très joli comme méthode, pour montrer que $\R$ n'est pas dénombrable je ne connaissais que le procédé diagonal (pendant de la 1ère méthode) : je préfère cette troisième méthode.

lili.

Bruno

Au passage, si je ne me trompe pas, voici une autre méthode dérivée de la troisième pour montrer que $[0,1]$ n'est pas dénombrable : 'amplitude de l'intervalle est $1$ et on l'enferme dans une suite $I_n$ d'intervalles d'amplitudes $\dfrac 1 {2^n}$. Ce raisonnement doit bien traîner dans la littérature.

Bruno

benn1

Bonjour j'ai un petit pb avec cet exo .

1)
Supposez une énumération e : N -> 2^N. Considérez X={n | n n’appartient pas à e(n) }.
Comme e est surjective, il n’existe nx tel que e(nx)=X et soit nx appartient à X soit nx appartient à X.
Montrez que dans les deux cas on arrive à une contradiction.

2)
On dit qu un ensemble X est dénombrable s’il y a une fonction bijective entre X et les nombres naturels N.

Montrer que l’ensemble des langages sur un alphabet Somme n’est pas dénombrable .

3)
Conclure qu il y a des langages qui ne sont pas semi-decidables.

Bruno

Bonjour benn.

Pour le 1, je l'ai évoqué au-dessus dans le sujet :-)))

Pour le reste, qu'est-ce au'un "alphabet somme"? Et des langages "semi-décidables" ? (sans garantie de réponse)

Bruno

...

une rectification un ensemble est denombrable s'il s'injecte dans N
un ensemble fini est denombrable (denombrable veut juste dire que l'on peut les compter

pour tes langages
comme le nombre de langage sur un alphabet a deux caracteres est 2^N
et que le nombre de langage semi decidable est N (un par algorithme, qui sont, je le rappelle denombrable) il esiste un gros paquet de langages non recursivement enumerable (synonime de semi decidable)

j'espere avoir ete clair

benn1

bonjour, je n'ai pas tres bien compris ton explication .