Théorème de Cantor

[nodjim]

Oui j'ai pigé. On aurait pu en effet prendre un entier sur 10 pour faire cette fonction, et on aurait eu le même résultat.
J'avais oublié cet aspect.
Merci Ben et Zygomatique.

[nodjim]

Et dans le cas de l'hôtel infini complet ? Je n'ai jamais compris cette parabole parce que je ne comprends pas au départ comment on définit que l'hôtel est complet.

[Ben314]

Le fait que "l'hotel est complet", ça te dit que tu as une bijection entre l'ensemble C des clients et l'ensemble B des chambres.
Les différents sous-entendus de l'énoncé, c'est que :
1) Dire que c'est O.K., ça veut dire trouver une injection de f:C->B qui est la fonction client->chambre_occupée.
C'est bien une fonction vu que personne ne couche dehors et qu'un client n'occupe pas deux chambres simultanément.
Dire qu'on veut qu'elle soit injective signifie qu'on ne veut pas mettre deux clients (différents) dans une même chambre.
A priori, elle peut ne pas être surjective (donc pas bijective), ce qui signifie qu'il reste des chambres vides.
Si l'hotel est complet, ça veut donc dire que la fonction est bijective (exactement un client par chambre)

2) Dire par exemple "qu'il arrive un nouveau client", ça veut dire qu'on considère un nouvel ensemble C'=Cu{x} où x n'est pas déjà dans C (c'est un nouveau client). Pour "le caser", il faut construire une nouvelle injection de C' dans B.
Si l'hôtel n'est pas complet, c'est facile : il y a une chambre y non attribuée et on construit la nouvelle fonction f':C'->B en prenant l'ancienne fonction f définie sur C et en ajoutant f'(x)=y (le nouveau client prend une chambre vide, le reste ne change pas) il est évidement le seul client de cette chambre donc f' est de nouveau injective.
Par contre, si l'hôtel est complet, dans le cas fini, c'est foutu si on veut garder l'injectivité (i.e. pas plus d'un client par chambre) mais dans le cas infini, c'est jouable...

[paquito]

Le problème au départ est: il n'existe pas de surjection de E->P(E); la démonstration est claire et repose sur le fait qu'une proposition ne peut être à la fois vraie et fausse; ce qui semble évident et qui repose sur un axiome fondamental appelé principe du tiers exclus. La démonstration est claire, c'est tout ce qu'on demande.
Quant à utiliser ce résultat pour montrer par exemple que N n'est pas en bijection avec R, ce n'est pas inintéressant, mais hors sujet!

[paquito]

Soit , ensemble des suites qui prennent la valeur 0 ou 1; E est l'indicatrice de P(N) et E est en bijection avec [0;1] si on travaille en binaire et si on exclut les développements impropres. alors [0; 1] est en bijection avec P(N) et donc, d'après le théorème de Cantor, N et [0;1] et a fortiori N et R ne sont pas en bijection.

[alexis6]

Bonsoir,

La réponse de Ben314 était très claire, merci beaucoup. L'exemple avec l'ensemble des naturels N était aussi parlant, je l'avais déjà vu sur wikipédia sans trop approfondir le truc...

Par contre, quand paquito dit que:
" c'est en complète contradiction avec le principe du tiers exlus et par conséquent, D n'existe pas ".

Moi ce que j'avais compris c'était que D existait bel et bien ( justifié par l'axiome de séparation je crois ). En revanche, D n'a pas d'antécédant, c'est cela il me semble qui est montré pas le raisonnement par l'absurde.

La ou c'est pas clair c'est comment justifier que D est non vide pour une applicationf: f: E --> P(E). En effet si D est vide, ça ne prouve rien du tout non?

[Ben314]

Visiblement tu as un problème avec l'ensemble vide....
S'il s'avère que D est vide, ben... ça ne change strictement rien à la preuve... on en déduit juste qu'aucun des f(x) n'est égal à l'ensemble vide. Mais vu ce qu'on fait avec, l'ensemble vide n'est qu'un élément parmi d'autres de P(E) et il ne joue aucun rôle particulier par rapport aux autres éléments de P(E).

Si on reprend l'exemple avec E={1,2,3} et qu'on considère la fonction f définie par
f(1)={1,2} ; f(2)={1,2,3} ; f(3)={3}
alors l'ensemble D est vide car 1f(1) , 2f(2) et 3f(3)
mais ça ne constitue en aucune sorte un "cas particulier" dans le raisonnement.
On a (comme toujours) D différent de f(1), de f(2) et de f(3).

[nodjim]

C'est bon pour moi pour l'hôtel. Il suffit en effet de changer les relations entre C et N et le tour est joué.

[paquito]

Bonsoir,

La réponse de Ben314 était très claire, merci beaucoup. L'exemple avec l'ensemble des naturels N était aussi parlant, je l'avais déjà vu sur wikipédia sans trop approfondir le truc...

Par contre, quand paquito dit que:
" c'est en complète contradiction avec le principe du tiers exlus et par conséquent, D n'existe pas ".

Moi ce que j'avais compris c'était que D existait bel et bien ( justifié par l'axiome de séparation je crois ). En revanche, D n'a pas d'antécédant, c'est cela il me semble qui est montré pas le raisonnement par l'absurde.

La ou c'est pas clair c'est comment justifier que D est non vide pour une applicationf: f: E --> P(E). En effet si D est vide, ça ne prouve rien du tout non?

D existe => vraie et vraie ou fausse et fausse ,

qui est de la formeavec est est toujours fausse, donc on a

avec toujours vraie donc aussi c'est a dire que D n'existe pas.

Si tu dis que pour l'équation tu as dans R, S = vide ça ne te gêne pas.

plus généralement et est toujours fausse;

un autre exemple bien connue qui est de montrer que l'ensemble E des ensembles qui ne se contiennent pas comme élément n'existe pas;

E={XX}; soit F un ensemble, si alors et si alors ,

donc l'existence de E conduit à ce qui est toujours faux et E ne peut pas exister

[Ben314]

...S'il était l'image d'un élément y de E, soit D = f(y), alors...

En (re) regardant le post de départ, je me dit que, comme assez souvent, le truc qui risque de rendre le truc pas trop clair pour certains, c'est le fait qu'on raisonne par l'absurde.
En fait on n'est pas obligé de raisonner par l'absurde pour montrer que D ne peut être égal à aucun des f(x), il suffit de considérer deux cas (ça revient, je le reconnais, quasiment au même que l'absurde) :
On considère un x quelconque de E. Soit il est dans D et, par définition de D, il n'est pas dans f(x), soit il n'est pas dans D et, toujours par définition de D, il est dans f(x).
Dans les deux cas, il est dans un et un seul des deux ensemble D et f(x) ce qui prouve que ces deux ensembles sont différents.

[paquito]

On doit parler de la démonstration par l'absurde qui le plus souvent est une démonstration par contraposée:

; pour montrer que est fausse, on la suppose vraie et on montre qu'une proposition (dans le contexte) est fausse; on a donc: et puisque est fausse, est fausse.

Je pense que ce type de démonstration mérite d'être appelé démonstration par l'absurde.

Mais il y a un autre type de démonstration par l'absurde qui consiste à être en contradiction avec un principe fondamental de logique: il consiste à montrer qu'une proposition conduit à et qui est par principe du tiers exclus est toujours fausse;

C'est le cas du théorème de Cantor et du théorème qui affirme que l'ensemble des ensembles qui ne sont pas élément d'eux mêmes n'existe pas. (j'ai dû voir 2 ou trois exemples en topologie)

Je signale que des logiciens ont essayé de se passer de l'axiome du tiers exclus en accordant à une propriété p une probabilité d'être vraie! L'échec a été immédiat!

[zouzou8]

Bonjour le forum,

Je déterre ce sujet de 2015 car j’ai des difficultés à saisir la preuve de ce théorème, bien que la lecture du fil m'ait beaucoup aidé, notamment l'exemple de Ben314 pour "quand on y pige rien". Je comprends intuitivement le théorème lorsque E est un ensemble fini (par la comparaison des cardinaux), mais la preuve ne "coule" pas.

Du coup, est-ce que ma formulation très « longues phrases de français » ci-dessous est correcte ?

Soit une application de l'ensemble dans , avec l'ensemble des parties de .
Pour montrer que n’est pas surjective, il suffit de trouver un sous-ensemble de qui n’admette pas d’antécédent par dans .
Pour cela, Cantor introduit l'ensemble tel que :
Comme est un sous-ensemble de , alors il est également un sous-ensemble de .
Supposons que ("son représentant" dans ) admette un antécédent dans , c’est-à-dire .
Comme , on a deux cas possibles :
- soit : alors, par définition de , donc .
- soit : alors , donc .
Il y a contradiction donc l’hypothèse « admet un antécédent » est fausse, donc n'est pas surjective.

Merci pour vos retours !

[hdci]

Bonjour,

Comme est un sous-ensemble de , alors il est également un sous-ensemble de .

Attention : si alors : si est un sous-ensemble de , c'est un élément de .
Un sous-ensemble de , c'est un ensemble qui contient des sous-ensembles de .
Par exemple, pour , la paire est un sous-ensemble de et un élément de
Et l'ensemble est un sous-ensemble de

Sinon votre formulation est correcte.

[zouzou8]

Merci beaucoup hdci, votre réponse éclaire justement un point qui était flou pour moi car je mélange les éléments et les sous-ensembles (et du coup, je confonds appartenance et inclusion dans mes écritures).

Du coup, j'ai une question : vous dites qu' "un sous-ensemble de (je nomme ce sous-ensemble ), c'est un ensemble qui contient des sous-ensembles de ". Est-ce que peut ne contenir qu'un seul sous-ensemble de , par exemple l'ensemble vide ?

[Ben314]

Oui, bien sûr.
Pour t’entraîner, dresse la liste (exhaustive) de tout les sous-ensemble de {0,1} (c'est à dire des éléments de P({0,1})) puis la liste de tout les sous-ensembles de P({0,1}) (c'est à dire des éléments de P(P({0,1}))).
Et évidement, pour ne pas en oublier, c'est pas con de commencer par calculer le nombre d'élément de P({0,1}) et de P(P({0,1})).

[zouzou8]

Ah oui, c'est un bon exercice pour comprendre les parties d'un ensemble ! Merci Ben314
Card(P(P({0,1})))=16, donc je ne ferai pas P(P(P({0,1}))))

[hdci]

Effectivement, le cardinal des parties augmente de façon exponentielle !
Si alors donc ...