Théorème de Cantor

[alexis6]

Bonjour,

Je ne comprends pas la démonstration de ce théorème...

La voici:

Soit f une application d'un ensemble E dans son ensemble des parties P(E). Alors le sous-ensemble des éléments de E qui n'appartiennent pas à leur image par f :



n'a pas d'antécédent, c'est-à-dire n'est l'image par f d'aucun élément de E. On le déduit du raisonnement par l'absurde suivant. S'il était l'image d'un élément y de E, soit D = f(y), alors :
si y est dans D, par construction de D, y n'appartient pas à son image ... c'est-à-dire que y n'appartient pas à D ; si y n'est pas dans D, toujours d'après la construction de D, y doit appartenir à son image ... c'est-à-dire à D.

Je pige pas comment on peut avoir un ensemble dont les éléments sont dans E et en même temps pas dans f(x), donc pas dans P(E). Comment justifier que cet ensemble existe et est non vide?

Sinon, on cherche à montrer qu'un ensemble: " x appartient à E " " n'est l'image par f d'aucun élément de E ". Si x appertient à E, alors il fait parti des antécédents, pas des images non?

Bref, j'y comprends rien, help!

[mathelot]

Bonjour,

Je ne comprends pas la démonstration de ce théorème...

La voici:

Soit f une application d'un ensemble E dans son ensemble des parties P(E). Alors le sous-ensemble des éléments de E qui n'appartiennent pas à leur image par f :



n'a pas d'antécédent, c'est-à-dire n'est l'image par f d'aucun élément de E. On le déduit du raisonnement par l'absurde suivant. S'il était l'image d'un élément y de E, soit D = f(y), alors :
si y est dans D, par construction de D, y n'appartient pas à son image ... c'est-à-dire que y n'appartient pas à D ; si y n'est pas dans D, toujours d'après la construction de D, y doit appartenir à son image ... c'est-à-dire à D.

Je pige pas ....

Si D est une image par f, alors équivaut à
la conclusion indique que D n'est pas un ensemble.

finalement l'exercice démontre que card(P(E))> card(E)

[paquito]

C'est ce qu'on appelle une vraie démonstration par l'absurde qui contredit le principe du tiers exclus:

soit p une proposition mathématique, alors:
si p est vraie alors est fausse et
si p est fausse alors est vraie; il n'y a pas une troisième possibilité.

Si on reprend le théorème de Cantor:

soit , si alors et
si alors

Dans le premier cas on affirme qu'une proposition prend obligatoirement l'une des 2 propriétés:{vraie, fausse}

Dans le 2° cas on a établi: , donc qu'une proposition sérait équivalente à sa négation, soit deux propositions simultanément vraies ou fausses.

C'est en complète contradiction avec le principe du tiers exlus et par conséquent, D n'existe pas.

[Ben314]

Salut,
Comme TOUJOURS, quand on y pige rien, ben on prend un exemple pour voir ce que ça donne...

Comme P(E) est très rapidement "très gros", on prend un "petit" E, par exemple E={1,2,3}.
donc P(E)={ , {1} , {2} , {3} , {1,2} , {1,3} , {2,3} , {1,2,3} }

On prend maintenant au pif une application f de E dans P(E), par exemple
f(1)={2,3} ; f(2)={1,2,3} ; f(3)= (les différent f(x) sont bien des éléments de P(E))

Déterminons dans ce cas qui est le fameux :
- Si x=1 alors f(1)={2,3} et donc 1 est dans D
- Si x=2 alors f(2)={1,2,3} et donc 2 n'est pas dans D
- Si x=3 alors f(3)= et donc 3 est dans D

Bilan : D={1,3} et il s'avère que {1,3} n'est égal ni à f(1)={2,3}, ni a f(2)={1,2,3}, ni a f(3)=.

La preuve en question montre que ce n'est pas par hasard que D ne soit égal à aucun des f(x) et surtout, elle montre que ç'est vrai quelque soit la taille de l'ensemble E (en particulier si E est infini) et quelque soit la fonction f.

En particulier, on peut noter que la preuve est sans grand intérêt dans le cas où E est fini vu qu'on sait déjà que, si l'ensemble E est de cardinal n alors l'ensemble P(E) est de cardinal 2^n et, vu que 2^n>n quelque soit n, il ne peut pas y avoir de surjection de E dans P(E) : Dans l'exemple précédent, E a 3 éléments alors que P(E) en a 8, donc il est évident qu'il existe un élément de P(E) qui n'est égal ni à f(1), ni a f(2), ni à f(3) et ceci, quelque soit la fonction f considérée.

[mathelot]

ce qu'il faudrait pour nier l'énoncé de Cantor,
c'est de dire que l'appartenance à un ensemble E est
décrit par une probabilité d'appartenance.
là, les bords pourraient être non vides.

[Ben314]

En fait, dans le cas où E=N, il y a une autre façon de présenter la preuve qui la rend plus facile à comprendre (mais c'est exactement la même preuve).
Il me semble me rappeler (à vérifier) que c'est par là que Cantor à commencé (chercher "processus diagonal de Cantor" sur le net...)

On suppose qu'on a une application de N dans P(N), c'est à dire en fait une suite d'ensemble (une suite indexée sur les entier n'est jamais qu'une application de N dans ???. Il n'y a que la notation qui change vu qu'on écrit à la place de )

Imaginons maintenant un tableau à deux entrées i,j (i,j dans N) où, dans la case situé sur la ligne i et la colonne j, on met V (vrai) ou F (faux) selon que l'entier j est ou pas dans l'ensemble .
Par exemple, si est l'ensemble des nombres pairs, la première ligne du tableau sera : V F V F V F...
Si est l'ensemble des nombres premiers, la deuxième ligne sera : F F V V F V F V F F F V ...

On fabrique alors une nouvelle ligne dans le tableau (on pourrait dire qu'on la rajoute "en bas du tableau, mais c'est un peu compliqué de trouver le "bas" du tableau, donc on va plutôt imaginer qu'on la rajoute au dessus...)
Pour fabriquer cette nouvelle ligne, on met dans sa i-ième case (i partant de 0) la négation (VF) de ce que contient la case (i,i) du tableau.
En procédant de la sorte, on est certain que la nouvelle ligne sera différente de la i-ième ligne du tableau et comme on utilise le même procédé pour tout i, cette nouvelle ligne est forcément différente de toutes celles du tableau.
Cela montre que l'ensemble D auquel "correspond" cette nouvelle ligne est différent des ensemble c'est à dire en fait que l'application de N dans P(N) qui à n associe n'est pas surjective.

Essaye de bien comprendre ce qu'il y a au dessus et tu verra que le D construit çi dessus est bien l'ensemble

Pour reprendre l'exemple du post précédent, avec f(1)={2,3} ; f(2)={1,2,3} ; f(3)= ça donnerais ça :
1 2 3
f(1) F V V
f(2) V V V
f(3) F F F

D V F V
La ligne ajoutée est, par construction même, différente des 3 du tableau.

[nodjim]

Pour montrer qu'il y a plus de réels dans [0,1] que d'entiers naturels, est ce qu'on ne peut s'y prendre comme ça ?
On considére les réels: 0,1;0,01;0,001;......
Chaque rang du 1 peut être mis en relation avec un entier, qui est son ordinal. Et comme il y a bien plus de réels que ces seuls nombres, alors les réels sont plus nombreux que les entiers.

[paquito]

Et 0, 09999999999 Qu'est ce que ça veut dire plus nombreux? N est 2 fois plus grand que 2N?

[Ben314]

Non, ça ne marche pas.
Ce que tu utilise là, c'est le fait que, si un ensemble A a autant d'élément qu'une partie stricte de B alors forcément A a strictement moins d'élément que B (au sens mathématique, les termes "autant" et "strictement moins" sont à remplacer par "il existe une bijection" et "il n'existe pas de surjection")
C'est vrai pour les ensembles finis (si je rajoute ne serait-ce qu'un élément à A, l'ensemble obtenu a strictement plus d'élément), mais c'est faux pour les ensembles infinis :

Si on "ajoute" à N* (N privé de 0) l'élément 0, on obtient N, or la fonction n->n+1 fourni une bijection de N sur N* ce qui montre que N et N* ont le même nombre d'éléments.
On peut même constater que, d'une certaine façon, ça semble être une caractérisation des ensembles infinis : si on leur rajoute un élément, ben le nouvel ensemble obtenu aura autant d'éléments que celui de départ (on peut démontrer que c'est vrai)
J'ai la flemme de chercher un/des liens, mais sur le net, tu trouvera des trucs marrant concernant la façon de faire rentrer une infinité de clients dans un hotel infini. Les chambres sont toutes occupées et un nouveau client arrive : no problem...
Il arrive ensuite un bus avec une infinité de nouveau clients dedans : no problem...
Et une infinité de bus avec une infinité de clients dans chaque bus ? Toujours pas de problème...
(pour les puristes, les "infinités" en question sont évidement toutes dénombrables)

Quand on veut manipuler les notion de "autant d'élément" , "plus d'éléments" , "strictement plus d'élément" dans le cas des ensembles infinis, il faut au départ bien se méfier de l'intuition : nombre de résultat valables dans le cas finis ne sont plus valables dans ce contexte (et c'est un peu pour ça qu'on préfère utiliser le vocabulaire plus technique "il existe une bijection" ou "il existe une injection", ...)
Un dernier exemple de truc "bizarre" : dans le cas fini, il est évident que si l'ensemble A a plus d'élément que B et que B a plus d'élément que A alors ils en ont autant.
Modulo les traductions (injection/bijection), ça reste vrai avec des ensembles infinis, mais c'est pas trivial du tout : ç'est le (fameux) théorème de Cantor-Bernstein dont la preuve n'est pas super simple à comprendre.

[nodjim]

Je sais que la définition d'un ensemble infini, c'est de dire qu'il y a des bijections (au moins une) entre l'ensemble complet et une de ses parties, par exemple entre n et 2n.
Mais ici ce n'est pas tout à fait le cas. Je fais une bijection entre les éléments de N une partie de R. C'est à dire qu'à un entier donné, je lui fais correspondre le réel dont le 1 est le rang de cet entier. Et donc tous les entiers sont occupés par cette affectation. Je raisonne mal ?
Idem pour l'hôtel: on dit qu'il est complet. Alors, j'imagine bien par exemple que à chaque entier on fait correspondre la clé d'une chambre qui porte ce numéro. Et ainsi, "complet" prend tout son sens: A chaque entier, la clé de la chambre est prise, et l'hôtel est bien complet, il n'y a plus aucune chambre disponible. Si mon raisonnement est faux, comment peut on exprimer que l'hôtel est complet ?

[Ben314]

Non, tu raisonne correctement, mais cela montre uniquement qu'il y a "plus" (au sens large) d'éléments dans [0,1] que dans N.
La grosse difficultée (et le truc vraiment interessant), c'est de montrer qu'il y a "strictement plus" d'éléments dans [0,1] que dans N.
Et le fait qu'avec ta fonction particulière certains réels n'ont pas été atteints ne prouve pas qu'il en est de même avec tout autre fonction (alors que dans le cas fini, ça le prouverais)

[nodjim]

Euh...tu peux préciser ?

[Ben314]

J'ai rallongé le post précédent.
C'est plus clair ou toujours pas ?

[nodjim]

Oui et non. J'aurais dit comme ça qu'une seule fonction particulière suffisait à démontrer la différence de cardinal.
Cette fonction que j'ai avancée est bijective: A l'entier n , je fais correspondre le réel constitué que de zéros et d'un seul 1 au rang n. Et inversement, il y a suffisamment de réels de ce format pour occuper tous les entiers (est ce à cet endroit que l'affirmation est à prouver ?).

[Ben314]

On va préciser le vocabulaire :
Si A et B sont deux ensembles (fini ou pas) on va dire que dit :
- L'ensemble A a moins d'élément que B lorsqu'il existe une injection de A dans B.
- L'ensemble A a plus d'élément que B lorsqu'il existe une surjection de A dans B.
- L'ensemble A a autant d'élément que B lorsqu'il existe une bijection de A dans B.

Bon, déjà, là où ça commence fort, c'est que, pour montrer que "A a plus d'éléments que B" équivaut à "B a moins d'éléments que A" il faut l'axiome du choix.

Ensuite, autant l'implication
A a autant d'élément que B => A a moins d'éléments que B et B a moins d'éléments que A
est triviale vu les définition, autant la réciproque est assez subtile (Cantor-Bernstein)

Enfin, on continue les définitions en disant que
- L'ensemble A a strictement moins d'élément que B lorsqu'il en a moins mais pas autant, c'est à dire lorsqu'il existe une injection de A dans B mais qu'il n'existe pas de bijection de A dans B.

Toi, ce que tu montre, c'est qu'il existe une injection de N dans [0,1] et que cette injection là n'est pas une bijection. Ca ne constitue (évidement) pas une preuve du fait qu'il n'existe aucune bijection de N dans [0,1].

[paquito]

Je disais ça pour plaisanter.Un ensemble E est infini ssi il existe une bijection de E dans une partie propre de E; ainsi N est en bijection avec et si on considère l'écriture propre de],

[ est en bijection avec qui d'après le théorème de Cantor est en bijection avec P(N)!

[Ben314]

Oui et non. J'aurais dit comme ça qu'une seule fonction particulière suffisait à démontrer la différence de cardinal.
Cette fonction que j'ai avancée est bijective: A l'entier n , je fais correspondre le réel constitué que de zéros et d'un seul 1 au rang n. Et inversement, il y a suffisamment de réels de ce format pour occuper tous les entiers (est ce à cet endroit que l'affirmation est à prouver ?).

Dans le cas infini, de produire une injection de A->B qui n'est pas une bijection ne suffit pas à prouver qu'il n'existe aucune bijection de A->B (par contre c'est O.K. si A et B sont finis)
Toujours le même exemple : si A=N* et B=N alors N*->N;n->n est injective mais pas bijective (0 n'est pas atteint) ce qui n'empêche pas qu'il existe des bijections de N* dans N, par exemple N*->N;n->n-1.

Donc je le redit : ta fonction montre qu'il y a au moins autant de réel dans [0,1] que d'entier naturels, mais ça ne montre pas qu'il y a strictement plus de réels dans [0,1] que d'entiers naturels.

[zygomatique]

salut

tu construis une bijection de quoi dans quoi ?

je ne vois qu'une bijection de l'ensemble des entiers non nuls dans l'ensemble des inverses des puissances de 10 différentes de 1

....


notons la f ... donc telle que

je te propose :: telle

g(2n) = f(n)
g(2n + 1) = f(n) + 1/(2n + 1)

alors g est une bijection de N dans un sous-ensemble de [0, 1]

peux-tu mettre en bijection f(N) et g(N) ?

et pourtant g(N) "a deux fois plus d'éléments" que f(N)

:lol3:

[nodjim]

D'accord, je crois que je commence à comprendre.

[Ben314]

Si on veut le dire de façon légèrement différente, dans le cas fini, si un ensemble est strictement inclu dans un autre alors son nombre d'élément est strictement plus petit. Mais c'est faux dans le cas infini.
Ta fonction f montre qu'il y a autant d'entier que de réels dans une partie A strictement inclue [0,1] (A étant les réels de la forme 0,0...01) sauf qu'il est possible que, bien que strictement inclue dans [0,1], ta partie A ait autant d'éléments que [0,1].