Le théorème de Cantor

[@MrZefredo]

J'ai été interrogateur pendant trois ans au concours d'entrée de ton école. Je m'efforçais de trier entre les candidats - qui ne connaissait pas l'astuce - qui connaissait l'astuce sans plus - qui essaye de retrouver l'astuce et la trouve, les derniers ayant la meilleure note toute chose autre égale évidemment. Tes vidéos me montre que tu fais partie de la troisième catégorie.

[@MathsEtoile]

Merci beaucoup ça fait très plaisir :)

[@sirmephis5999]

C'est vraiment incroyable , très rapide et efficace

[@fredogator9479]

L'idée de l'ensemble A n'est pas de Cantor mais de Bertrand Russell. Il semble que Zermelo en avait eu également l'idée. Merci beaucoup en tout cas pour vos vidéos qui me rappellent mes lointains souvenirs de prépa et qui sont extrêmement bien faites. Je ne saurais trop les conseiller à tous les étudiants de prépa. D'ailleurs même dans cette vidéo un peu anecdotique vous essayez de mettre en lumière l'idée d'intuition indispensable à la résolution des exos de prépa, même si dans le cas présent nous sommes dans le contre exemple typique avec une idée géniale venue à peu près de nulle part. BRAVO

[@Pacobios]

J'adore ce genre de vidéos où tu présentes et prouve un théorème. Tu fais un excellent travail!

[@bilmag182]

Incroyable une des meilleures vidéo que j'ai vu

[@stuga12397]

Si tu veux un peu plus de contexte et d'intuition, le plus simple c'est encore de revenir à un cas plus facile : le cas le plus simple où on utilise un argument diagonal de ce type là, c'est pour montrer que N < [0,1] (ce qui est juste un cas particulier du théorème de Cantor, d'ailleurs). Le principe est de construire un réel x qui n'a pas d'antécédent par f, et on construit x à partir de son développement décimal : On veut que le développement décimal de x et de f(n) diffère à au moins un endroit, pour tout n. Ce qu'on peut faire, c'est définir le nième chiffre de x comme étant 0 si le nième chiffre de f(n) est différent de 0, et 1 sinon. Tu vois bien que du coup que x n'est pas dans Im(f). Ce cas particulier est déjà pas évident, mais c'est loin d'être aussi magique que ce que tu présentes. Une fois qu'on comprend ce cas particulier, on peut essayer d'adapter ça au cas général : pour ça, on identifie P(E) à {0,1}^E (et donc si S € P(E) et x € E, S_x = 1 si x € S, 0 sinon) , et on veut construire un élément x qui n'a pas d'antécédent par f. On fait la même astuce qu'avant : on construit un élément S de {0,1}^E qui diffère de f(x) à au moins un endroit, pour tout x. On veut donc que f(x)_x != S_x, en d'autres termes, S_x = 0 si f(x)_x = 1, S_x = 1 sinon. Pour les mêmes raisons qu'au dessus, S n'est pas dans Im(f), et si tu t'intéresses à l'ensemble qu'on vient de definir, on a pris tous les éléments de E tels que f(x)_x = 0, ie x otin f(x), c'est exactement ton ensemble A ! Les arguments diagonaux sont toujours compliqués à comprendre au début, mais une fois que t'en fais quelques uns c'est beaucoup plus évident (comme à peu près tout en maths au final). Si ce genre de raisonnements t'intéresse, regarde du côté des théorèmes de Godel qui se prouvent par des arguments diagonaux aussi (bon c'est quand même plus compliqué que ce qu'on vient de faire mais la preuve est très jolie)

[@francamentebrasileiro6511]

Merci. Tres clair

[@twentyc192]

Vidéo incroyable comme d'habitude merci pour cette qualité de 4:19 que tu nous offres

[@reouven5501]

Incroyable !!!

[@francoisgirardot6277]

Bravo pour la demonstration , il fallait y penser

[@annonyme8529]

Trop bien !

[@fredericmazoit1441]

Pour moi, c'est une généralisation très naturelle de l'argument diagonal classique. Prenons une fonction de f:N\to 2^N. On peut la voir comme une matrice infinie M de 0 et de 1 de la façon suivante. La i-ième ligne est l'indicatrice de f(i), i.e. M(i, j)=1 ssi j\in f(i). L'argument diagonal consiste à regarder la diagonale de M et à changer les 0 et 1 et inversement. De cette façon, on construit l'ensemble A={i / M(i, i)=0}. Par construction de M, si A=f(j), alors j\in A ssi M(j, j)=1. Mais si M(j, j)=1, i.e. j\in A, alors par construction de A, j otin A. Et si M(j, j)=0, i.e. j otin A, alors j\in A. Il reste à comprendre comment Cantor a trouvé l'argument diagonal classique.

[@fredericmazoit1441]

Sinon, je trouve intéressant de regarder la première preuve de Cantor du fait que les réels ne sont pas dénombrables. Je n'ai plus la preuve originale bien en tête mais l'idée est la suivante. On se donne une suite u_n de réels et on construit une suite I_n de segments fermé emboités telle que I_n ne contient aucun u_m pour m

[@wlopace1015]

@@fredericmazoit1441 Et cette manipulation de segments emboîtés donnera plus tard l'une des caractérisation de la complétude de R (indépendamment de Dedekind et Cauchy). Mais je n'ai jamais entendu parler de cette première démo, une ref ?

[@fredericmazoit1441]

@@wlopace1015 Pffff, youtube n'aime pas les références externes et a supprimé ma réponse. Il y a un papier sur arxiv dont le titre est On Cantor's important proofs de W. Mueckenheim.

[@wayy8927]

Vous faites des études de maths ?

[@fredericmazoit1441]

​@@wayy8927 Pas au sens où vous l'entendez. Je suis enseignant chercheur.

[@michelbernard9092]

Pour le truc magique utilisé, j'ai de suite pensé au paradoxe de Russel : " l'ensemble des ensembles n'appartenant pas à eux-mêmes appartient-il à lui-même " ou on retrouve presque la même écriture. Voir sur wikipédia ou je recopie 3 lignes : "La démonstration du paradoxe de Russell repose sur un argument diagonal, elle est très semblable à la démonstration du théorème de Cantor : le cardinal de l'ensemble des parties d'un ensemble (infini) E est strictement plus grand que celui de cet ensemble. Rappelons que pour démontrer ce théorème, on montre qu'une fonction f de E dans P(E), l'ensemble des parties de E, ne peut être surjective" Mais j'ignore ce qui a été démontré en premier.

[@paulb9115]

Très clair, en attente de la preuve du théorème de Cantor-Bernstein

[@MathsEtoile]

Super idée ! Je ferai bien aussi le lemme de Zorn, dans la même veine

[@ilyes3881]

Bonne video!👌

[@sardanapale2302]

Pas mal de réponses plus bas donnent comme motivation de l'ensemble A le paradoxe de Russel. Ce sont toutes des bonnes réponses, les deus sont intimement liés. Par contre, tu donnes toi-aussi, au début de ta vidéo, les bonnes réponses quand tu dis que 1) "l'ensemble des parties est une manière de construire à partir d'un ensemble, un ensemble strictement plus grand" et 2) quand tu fais la relation avec l'argument diagonal (voir un autre commentaire plus bas) Fondamentalement c'est ça l'idée derrière le théorème de Cantor et le paradoxe de Russel. En fait, c'est ça l'idée derrière ZF ou ZFC qui sont des axiomes qui te permettent à partir d'ensembles de construire d'autres ensembles, tout en restant dans la classe des ensembles (classe des ensembles qui elle n'est pas un ensemble, cf Russel pour faire court, ou le schèma d'axiomes de substitution cf Krivine, que comme plus bas, je recommande). L'ensemble A apparait "naturellement", en fait, c'est l'ensemble non trivial le plus simple que tu puisses construire à partir des données du problème.

[@rubikcraft5182]

Trop bien les vidéos de théorie des ensembles! ce serait génial si t'en faisais d'autres et aussi, ou est passé la petite musique de l'intro? :(

[@vegetossgss1114]

c'est mieux sans musique.

[@foxlolo38]

2:46 R^R ? A quoi cela correspond ?

[@eglvoland4162]

L'ensemble des fonctions de R dans R.

[@fredericmazoit1441]

Pour préciser la réponse d'Eglvoland, si tu prends une fonction de B->A avec a et B finis, combien y a-t-il de fonction ? Ben pour la première valeur de B, tu as |A| choix possible (|A| désigne le cardinal de A). Et pour la 2e valeur de B, tu as |A| choix possible et ainsi de suite. Tu as donc |A|^|B| fonctions. Après, on fait des abus de notation. On peut voir les sous-ensembles d'un ensemble X comme des fonctions de X->{0, 1} (f(x)=1 si x est dans l'ensemble). On note pas 2^X l'ensemble des sous-ensembles de X. Donc R^R désigne l'en semble des fonctions de R->R.

[@MichelSLAGMULDER]

Moi je ne l'aurais pas présenté comme ça. J'aurais dit que A est un sous ensemble de E par définition (au pire l'ensemble vide), Il est donc un élément de P(E). Comme la fonction est supposée subjective, il existe forcement un y tel que f(y) = A. Après la disjonction des cas montre l'absurdité. Je trouve que de faire comme ça c'est plus clair, mais ça revient au même.

[@foudilbenouci482]

Un ensemble à plus de parties que d'éléments

[@octobrerouge1997]

❤❤Magie noire ❤❤😂😂

[@stephanebiwole103]

Un corollaire intéressant du théorème de Cantor c’est la non-existence de l’ensemble des cardinaux(finis ou infinis). En fait si l’ensemble des cardinaux existait alors le cardinal de l’ensemble des parties de cet ensemble ne serait pas de cet ensemble par le théorème de Cantor. Ce qui est absurde. L’ensemble des cardinaux finis existent par contre (l’ensemble des entiers naturels.

[@Porculoide]

Est ce que la démonstration n'est pas déjà dans la 2è ligne !? n

[@YoanMaurelDiako]

non car il existe des ensembles non dénombrables comme l'ensemble des réels R .

[@hamzachater3431]

Charmant Théorème

[@leporcquirit]

Il manque « ZFC - 01 » dans le titre 😉

[@MathsEtoile]

T'es sacrément efficace ce soir dis moi 😂 Je règlerai tout ça demain, merci beaucoup !

[@leporcquirit]

​@@MathsEtoile J'ai leech toute la chaîne (pour visu ultérieure) et consulter la liste des fichiers dans l'ordre alphabétique de l'explorateur est redoutable 😁 Tant que j'y suis : il n'y a pas de playlist pour ZFC.

[@MichelSLAGMULDER]

Je pense avoir une piste pour comprendre comment il a trouvé cette astuce. Pour ça je vais donner un exemple. Supposons que E soit un ensemble d'oranges et je veux fabriquer un sous - ensemble absurde. Je choisis le sous-ensemble E dont les éléments sont des pommes. Et là j'ai un problème, je me rends compte que ce sous-ensemble n'a rien d'absurde. Alors que l'énoncée semble absurde ce sous ensemble existe et c'est l'ensemble vide. Donc je ne suis pas avancé. Il faut donc aller plus loin. Il faut construire un ensemble structurellement absurde. Et qu'elle est la première idée qui vient à l'esprit. Quelle est l'absurdité la plus facile à mettre en place, l'ensemble autoréférent contradictoire en d'autre terme la contradiction du barbier. Je sais pas si c'est bien clair.

[@drecland]

J'ai une idée sur pourquoi cette idée lui est venue : Quand on veut traiter la surjectivité, cela implique de regarder l'ensemble d'arriver de notre fonction, hors si l'on veux que la fonction ne soit pas dans l'ensemble d'arriver, il suffie et même il est nécéssaire de spécifier qu'il n'y ait pas . C'est surement en prenant un raisonnement de la sorte que lui ait venue l'idée de cette preuve. Après si on ne peux pas prendre de fonction surjective vers un ensemble plus grand, cela ne veux pas dire qu'il n'existe pas d'ensemble limite à tous les ensemble, ce qui est démontrable assez facilement en supposant qu'il existe un ensemble qui peut prendre n'importe quel ensemble existant et réduire en un point les éléments de l'ensemble par une relation appliquer par une fonction ( que je nomme fonction algorithmique car je ne sais si ce genre d'objet existe )

[@marzinsouad2728]

Bonjour, dans la ligne ou vous supposez que: Si y n'appartient pas à A, normalement vous dites que y n'appartient pas à E d'après la définition de A. Ce qui est contradictoire. J'espère que c'est clair. Cordialement.

[@danielpont3907]

A partir de chaque élément x de E ; on peut construire au moins 2 parties de E : le singleton {x} et son complémentaire dans E. Or par définition une application n’admet pour chaque élément de l’ensemble de départ, un seul élément dans l’ensemble d’arrivée. D'où la contradiction qui montre qu'il n'existe pas de surjection de E vers l'ensemble de ses parties.

[@henritpe2718]

Comment sait-on que A n’est pas l’ensemble vide ?

[@merwan.houiralami]

peu importe si A est l’ensemble vide on peut quand meme conclure

[@evar5638]

A n'est pas l'ensemble vide car f est surjective, donc il existe y tel que f(y) est l'ensemble vide qui appartient a P(E). Donc si A est vide, alors y appartient a f(y) donc y n'existe pas donc f(y) non plus et c'est absurde. De ce que j'ai compris c'est ça 😅.

[@wlopace1015]

Je désapprouve le 'ZFC' en miniature. Je comprends l'idée mais : 1/ L'axiome du choix est clairement pas indispensable (il est même indépendant de ZF). Mais à la limite je m'en fous. 2/ Quand on parle d'étudier ZFC, on se demande si on peut trouver des modèles de cette théorie, et si on peut rajouter des choses dedans. Typiquement, l'axiome de fondation. Si tu veux avoir une idée, je te conseille "Théorie des ensembles" de Jean-Louis Krivine. Le meilleur bouquin (au sens pédagogique/mathématique) qu'il m'ait jamais été donné de lire tout thème confondu.

[@wlopace1015]

Par ailleurs, c'est moins précis (même si équivalent), mais je pense que c'est plus "parlant" de parler de bijection. Ca permet de parler de correspondance biunivoque, et permet à des matheux moins aguerris de s'accrocher.

[@evar5638]

Je ne comprends pas pourquoi la non-existence de A montre le théorème. Pourquoi est-il impossible de créer une surjection telle que pour tout x de E on a x dans f(x) ?

[@monkey_tm4651]

Même si on pouvait construire une fonction f telle que pour tout x dans E, on ait x dans f(x) cet argument montre que f ne peut être une surjection (en fait dans ce cas on aurait A = vide donc y n’est pas dans A, (i.e y quelconque dans E), et donc par définition de A, y est dans f(y) = A ce qui est évidement absurde)

[@monkey_tm4651]

L’argument tient « simplement » du fait qu’aucune application de E sans P(E) ne peut atteindre toutes les parties possibles, car on est capable d’en construire une qui n’est jamais atteinte (en l’occurrence A)

[@evar5638]

@@monkey_tm4651 Ah ok merci, en effet j'avais pas compris pourquoi A est nécessairement non-vide. Je m'attendais pas à que ce soit toi qui me répondes mdr (je te connais de TM).

[@foudilbenouci482]

A existe bien mais n'a pas d'antécédent , ce qui est différent...

[@corbonmaths9597]

L'idée que j'ai trouvé, c'est de partitionner P(E) en deux sous-ensembles (disjoints donc), Im f et son complémentaire dans P(E). Ensuite on s'arrange pour que A soit dans le complémentaire de Im f (dans P(E)). Alors dans les deux cas, on obtient une contradiction parce que f est surjective i.e. on est sûr que f(y) [qui appartient à Im f] appartient à A [qui appartient au complémentaire de Im f dans P(E)].

[@vegetossgss1114]

x n'appartient pas à f(x). Comment ça? f(x) est un ensemble?

[@MathsEtoile]

Oui ! Comme f va de E dans P(E), f(x) est un élément de P(E), c'est a dire une partie de E

[@vegetossgss1114]

@@MathsEtoile Est-ce qu'on parle de {f(x)}, de f({x}) ou d'autre chose?

[@MathsEtoile]

@@vegetossgss1114 Ni l'un ni l'autre, on parle bien de l'élément f(x). Comme f est a valeurs dans P(E), f(x) est bien un ensemble

[@vegetossgss1114]

@@MathsEtoile Merci!

[@foudilbenouci482]

cette application associe un élément d'un ensemble à une partie de cette ensemble

[@elpistolero4857]

Quelqu'un peut-il m'éclairer sur le sens de "x appartient à f(x)" ? Merci

[@abcdef71167]

La fonction f associe à tout élément x de E une partie de E, il faut donc voir f(x) comme un ensemble d'éléments de E (qui est quelconque). x étant un élément de E, on peut donc se poser la question de l'appartenance de x à cet ensemble noté f(x).

[@elpistolero4857]

@@abcdef71167 Merci beaucoup !

[@ahoj7720]

Le paradoxe du menteur n’en est pas un. Il commence par « dans un village… » et se conclut par « …donc contradiction ». La conclusion est donc que l’hypothèse de départ est fausse, à savoir qu’un tel village n’existe pas.

[@nathanhanen3634]

magie noire

[@yoannliegard3533]

Le paradoxe du menteur,.les énoncés indecidables, le théorème d'incompletude de Godel, c'est très intéressant, presque philosophique.