L'infini (partie 2) : Infinis de tailles différentes?

[Invité]

Ceci est la suite de ce sujet:
[Vous devez être inscrit et connecté pour voir ce lien]
Vous ne pourrez pas comprendre ce sujet sans avoir lu le précédent.

Bien, la question que je vous ai posé est : les ensembles infinis ont-ils tous la même taille?
C'est le mathématicien Georges Cantor qui a démontré que non. Eh oui, il existe des infinis de tailles différentes!
Nous allons voir comment est-ce possible.

On dit qu'un ensemble est dénombrable, s'il peut être mis en bijection avec l'ensemble des entiers positifs.
La question revient donc à : tout ensemble infini est-il dénombrable?
Essayons de chercher des ensembles non dénombrables comme l'a fait Cantor!
Pour simplifier les choses, voici un petit problème(donné par Raymond Smullyan):
Considérons que je suis le Diable et que vous êtes quant à vous ma victime des enfers... Je vous fait passer un test.
Je pense à un nombre entier positif. Je l'écrit au dos de cette feuille. Chaque jour, vous n'aurez le droit qu'à une seule tentative pour deviner quel est ce nombre. Si vous tombez juste, vous êtes libre, mais pas avant!
Comment faire pour être sûr de sortir tôt ou tard?
Il suffit de dire le premier jour 1, puis le deuxième jour 2, etc. Vous tomberez forcément sur le bon nombre un jour.
Maintenant, si j'écris sur ma feuille un entier positif OU négatif, comment faire pour être sûr de trouver un jour?
Essayez de chercher la réponse seul! Ne regardez pas tout de suite la solution!

Spoiler:

De cette façon, vous êtes encore sûr de trouver le bon nombre un jour!
A première vue, il semblerait que l'ensemble des entiers relatifs (entiers soit positifs soit négatifs) soit plus grand que l'ensemble des entiers positifs.
Or vous venez de trouver comment mettre ces deux ensembles en bijection, c'est une preuve qu'ils ont exactement la même taille!

Maintenant le test grandit encore en difficulté.
Je vais marquer au dos de ma feuille DEUX nombres entiers positifs, qui peuvent être différents ou bien même être égaux. Je peux écrire donc par exemple {2, 234}, ou bien {43, 6779}, ou encore {23, 23}...
Comment faire pour être sûr de trouver les deux nombres le même jour?
Allez, réfléchissez (c'est pas évident je vous l'accorde)!

Spoiler:

Bien! Maintenant encore plus dur!
Imaginons que je peux marquer au dos de cette feuille un ensemble fini de nombres entiers positifs, de la taille que je souhaite! Cela pourrait être {1, 4}, mais aussi {234, 23, 67, 45, 98}... etc.
Comment faire pour tomber un jour sur cet ensemble?

Spoiler:

Nous avons réussi à prouver que l'ensemble de tous les ensembles finis d'entiers positifs est dénombrable! :box:
Mais à présent pouvez-vous deviner quel ensemble n'est pas dénombrable?

Spoiler:

Nous allons vous le montrer de manière simplifiée encore une fois:
Imaginez un livre contenant un nombre dénombrables de pages : la page 1, la page 2, la page n...
Sur chaque page est écrite la description d'un ensemble d'entiers positifs.
Imaginez que si chaque ensemble d'entier positif se trouvait décrit dans ce livre, vous gagneriez un fabuleux cadeau...
Hé bien vous ne gagnerez rien du tout! Car il y a un ensemble d'entiers positifs qui ne peut être décrit sur aucune page de ce livre!

Si on appelle S₁ l'ensemble décrit à la première page, S₂ celui de la deuxième page, etc., alors l'ensemble S de tous les n tel que n n'appartient pas à S_n, ne peut être décrit sur ce livre! En effet car notre définition implique que pour tout n, S_n est différent de S puisque S contient n que si n ne fait pas partie de S_n! Donc S est toujours différent de S_n!
Donc S n'est pas décrit dans le livre.
On vient de prouver que l'ensemble des ensembles d'entiers positifs finis ou infinis était non dénombrable, donc pas de la même taille que l'ensemble des entiers positifs. Comme l'ensemble des ensembles d'entiers positifs finis est un sous-ensemble de l'ensemble des ensembles d'entiers positifs finis ou infinis, et qu'on l'a déjà mis en bijection avec l'ensemble des entiers positifs... Cela veut dire que l'ensemble des ensembles finis ou infinis d'entiers positifs est plus grand que l'ensemble des entiers positifs. :box:
Nous venons de démontrer qu'il y a des infinis de différentes tailles!

Et en prime, le théorème de Cantor:

Pour tout ensemble A, l'ensemble P(A) de tous les sous-ensembles de A est plus grand que A.

[Geveil]

Tu es un excellent pédagogue, miphum.

[Invité]

Tu es un excellent pédagogue, miphum.

Merci!
J'ai songé plusieurs fois à faire professeur quand j'aurais fini mes études... Je verrai bien...

[Invité]

Excuse moi mais il me semble que ta démonstration est erronée. Tu utilises un cas ressemblant au fameux paradoxe de Russel cf [Vous devez être inscrit et connecté pour voir ce lien]
Pour que ta démonstration soit valable il faudrait par exemple prouver que ton livre existe (ne pas supposer en hypothèse que l'ensemble des ensembles dénombrables soit dénombrable, ce qui est le cas en paginant ton livre).

Mais je peux me tromper, c'est loin tout ça ... :D

[Invité]

Excuse moi mais il me semble que ta démonstration est erronée. Tu utilises un cas ressemblant au fameux paradoxe de Russel cf [Vous devez être inscrit et connecté pour voir ce lien]
Pour que ta démonstration soit valable il faudrait par exemple prouver que ton livre existe (ne pas supposer en hypothèse que l'ensemble des ensembles dénombrables soit dénombrable, ce qui est le cas en paginant ton livre).

Mais je peux me tromper, c'est loin tout ça ... :D

J'y reviendrais, mais l'ensemble de tous les ensembles n'existe pas.
Le livre n'est pas un ensemble. C'est ce qu'on appelle la notion d'univers.
En bref l'univers contient tous les ensembles, mais ce n'est pas un ensemble!
Sinon en effet il y a paradoxe.

[Invité]

Je ne connais la notion d'univers que pour les probabilités. Et un univers est un ensemble d'ensemble, ce qui en fait un ensemble, particulier certes.

Donc ton livre est un ensemble d'ensemble ou de description d'ensemble si tu veux, ce qui revient presqu'au même (parce qu'il y est supposé que l'on puisse décrire tout ensemble dénombrable et en plus sur une page) : en supposant que chaque page correspond à un ensemble dénombrable tu "comptes" ces ensembles (ou descriptions d'ensembles). Donc en posant que ce livre existe, tu poses par hypothèse que cet ensemble est dénombrable en établissant une équipotence entre ce livre-ensemble et les numéros_de_pages-ensemble_des_entiers_naturels.

Donc il me semble qu'il y a quelque chose qui cloche :-)

[Invité]

Je ne connais la notion d'univers que pour les probabilités. Et un univers est un ensemble d'ensemble, ce qui en fait un ensemble, particulier certes.

Donc ton livre est un ensemble d'ensemble : en supposant que chaque page correspond à un ensemble dénombrable tu "comptes" ces ensembles. Donc en posant que ce livre existe, tu pose par hypothèse que cet ensemble est dénombrable en établissant une équipotence entre ce livre-ensemble et les numéros_de_pages-ensemble_des_entiers_naturels.

Donc il me semble qu'il y a quelque chose qui cloche :-)

Non, c'est juste que tu ne veux pas admettre que l'univers n'est pas un ensemble (la notion d'univers n'est pas la même que pour les probabilités ici).

[Invité]

Ah zut on a écrit en même temps :-)

Oh je veux bien admettre ce que tu veux. Explique moi en quoi le livre que tu décris est un univers et pas un ensemble, ça m'intéresse.

Je ne ne cherche pas à chipoter, ne te méprends pas, dans ma jeunesse je m'intéressais beaucoup à ce type de problème mathématiques. Et je trouve tes explications très bien faites ...

Oui je reprend mes remarques j'avais lu un peu vite ta démonstration :

tu supposes l'existence de ton livre
ce livre est un ensemble dénombrable de descriptions d'ensembles d'entiers naturels

tu démontre qu'un ensemble d'entiers particulier ne peut être dans ce livre

donc tu as démontré qu'un livre dénombrable contenant toutes les descriptions d'entiers n'existe pas

donc soit il n'existe pas d'ensemble contenant toutes les descriptions de nombres entiers, soit il n'est pas dénombrable

[Invité]

Oui je reprend mes remarques j'avais lu un peu vite ta démonstration :

tu supposes l'existence de ton livre
ce livre est un ensemble dénombrable de descriptions d'ensembles d'entiers naturels

tu démontre qu'un ensemble d'entiers particulier ne peut être dans ce livre

donc tu as démontré qu'un livre dénombrable contenant toutes les descriptions d'entiers n'existe pas

donc soit il n'existe pas d'ensemble contenant toutes les descriptions de nombres entiers, soit il n'est pas dénombrable

Tu as compris, à une chose près:
dans ta dernière affirmation logique, c'est la deuxième assertion qui est vraie.
En effet, dans le système axiome utilisé ici on considère que pour un ensemble donné (ici R l'ensemble des entiers naturels), l'ensemble de ses parties existe, on le note P(N). Donc ce livre existe forcément! Alors il est indénombrable...

[Invité]

On est d'accord, la conclusion est : "si l'ensemble des parties de N existe il n'est pas dénombrable".

Pour conclure que l'ensemble des parties de N est plus grand qu'un ensemble dénombrable il faut rajouter qques précisions évidentes mais qu'il est plus élégant de ne pas omettre : il faut démontrer que l'ensemble des parties de N contient au moins un sous ensemble dénombrable (paginable) qui ne contiendra pas S (par exemple l'ensemble des ensembles E(n) de multiples de n ) et que S est non vide (un nombre premier suffit) et donc existe.
Enfin il me semble :-))

[Invité]

On est d'accord, la conclusion est : "si l'ensemble des parties de N existe il n'est pas dénombrable".

Oui mais l'ensemble des parties de N existe forcément.

Pour conclure que l'ensemble des parties de N est plus grand qu'un ensemble dénombrable il faut rajouter qques précisions évidentes mais qu'il est plus élégant de ne pas omettre : il faut démontrer que l'ensemble des parties de N contient au moins un sous ensemble dénombrable (paginable) qui ne contiendra pas S (par exemple l'ensemble des ensembles E(n) de multiples de n ) et que S est non vide (un nombre premier suffit) et donc existe.
Enfin il me semble :-))

On a déjà démontré que une des parties de P(N) était dénombrable. Quand on a démontré que l'ensemble des sous-ensembles finis de N était dénombrable.

[Invité]

OK