Articles

9.3: Le Théorème de Cantor et ses conséquences

Compétences à développer

  • Expliquer le théorème de Cantor

Une fois que Cantor a montré qu’il y avait deux types d’infini (dénombrable et dénombrable), la question suivante était naturelle: « Tous les ensembles dénombrables ont-ils la même cardinalité? »

Tout comme tous les « non-chiens » ne sont pas des chats, il n’y a aucune raison de croire que tous les ensembles innombrables devraient avoir la même taille. Cependant, construire des ensembles innombrables de différentes tailles n’est pas aussi facile qu’il n’y paraît.

Par exemple, qu’en est-il du segment de ligne représenté par l’intervalle \(\) et du carré représenté par l’ensemble \(× = \{(x, y) / 0 ≤ x, y ≤ 1 \}\). Certes, le carré bidimensionnel doit être un ensemble infini plus grand que le segment de ligne unidimensionnel. Remarquablement, Cantor a montré que ces deux ensembles étaient la même cardinalité. Dans sa correspondance de 1877 de ce résultat à son ami et collègue mathématicien, Richard Dedekind, même Cantor a fait remarquer: « Je le vois, mais je n’y crois pas! »

 fig 9.3.1.png

Figure \(\PageIndex{1}\): Richard Dedekind

Ce qui suit donne l’idée originale de la preuve de Cantor. Cantor a conçu la fonction suivante \(f: × →\). Tout d’abord, nous représentons les coordonnées de tout point \((x, y) ∈ × \) par leurs représentations décimales \(x = 0.a_1a_2a_3…\) et \(y = 0.b_1b_2b_3….\) Même les décimales terminales peuvent être écrites de cette façon comme nous pourrions écrire \(0.5 = 0.5000….\) On peut alors définir \(f(x, y)\) par

\

Cette idée relativement simple présente quelques difficultés techniques liées au résultat suivant.

Exercice \(\PageIndex{1}\)

Considérez la séquence \((0.9,0.99,0.999,…)\). Déterminez que cette séquence converge et, en fait, elle converge vers \(1\). Cela suggère que \(0,999… = 1\).

De même, nous avons \(0.04999… = 0.05000…\), etc. Pour rendre unique la représentation décimale d’un nombre réel en \(\), nous devons faire un choix cohérent d’écrire une décimale de fin comme une décimale qui se termine par une chaîne infinie de zéros ou une chaîne infinie de neuf. Peu importe le choix que nous faisons, nous ne pourrions jamais faire cette fonction. Par exemple, \(109/1100 = 0,09909090…\) aurait comme pré-image \((0.0999…,0.9000…)\) qui serait un mélange des deux conventions.

Cantor a pu surmonter cette technicité pour démontrer une correspondance un à un, mais nous noterons plutôt que dans l’une ou l’autre des conventions, la fonction est un à un, donc cela dit que l’ensemble \(×\) est la même cardinalité que certains sous-ensembles (innombrables) de \(\mathbb{R}\). Le fait que cela ait la même cardinalité que \(\mathbb{R}\) est quelque chose auquel nous reviendrons. Mais d’abord, nous allons essayer de construire un ensemble non dénombrable qui n’a pas la même cardinalité que \(\mathbb{R}\). Pour résoudre ce problème, Cantor a prouvé ce qui suit en 1891.

Théorème \(\PageIndex{1}\): Théorème de Cantor

Soit \(S\) un ensemble quelconque. Ensuite, il n’y a pas de correspondance individuelle entre \(S\) et \(P(S) \), l’ensemble de tous les sous-ensembles de \(S\).

Puisque \(S\) peut être mis en correspondance un à un avec un sous-ensemble de \(P(S)(a→ \{a\})\), alors cela dit que \(P(S)\) est au moins aussi grand que \(S\). Dans le cas fini, \(|P(S) /\) est strictement supérieur à \(/S/\) comme le montre le problème suivant. Il montre également pourquoi \(P(S)\) est appelé l’ensemble de puissance de \(S\).

Exercice \(\PageIndex{2}\)

Prouver: Si \(/S|= n\), alors \(|P(S)/=2n\)

Indice

Soit \(S= a_1, a_2,…, a_n\). Considérons la correspondance suivante entre les éléments de \(P(S)\) et l’ensemble \(T\) de tous les \(n\)-tuples de yes(\(Y\)) ou no(\(N\)):

\

Combien d’éléments sont dans \(T\) ?

Exercice \(\PageIndex{3}\)

Prouvez le théorème de Cantor.

Indice

Supposons pour contradiction, qu’il existe une correspondance un à un \(f: S → P(S) \). Considérons \(A = \{x ∈ S / x \ non {∈} f(x)\}\). Puisque \(f\) est sur, alors il y a \(a ∈ A\) tel que \(A = f(a)\). Est-ce que \(a∈ A\) ou est-ce que \(a\ not {∈} A\) ?

En fait, il s’avère que \(\mathbb{R}\) et \(P(\mathbb{N})\) ont la même cardinalité. Cela peut être vu de manière détournée en utilisant certaines des idées ci-dessus de l’exercice \(\PageIndex{2}\). Plus précisément, soit \(T\) l’ensemble de toutes les séquences de zéros ou de uns (vous pouvez utiliser \(Y\)s ou \(N\)s, si vous préférez). Ensuite, il est simple de voir que \(T\) et \(P(\mathbb{N})\) ont la même cardinalité.

Si nous considérons \((0,1]\), qui a la même cardinalité que \(\mathbb{R}\), alors nous pouvons voir que cela a également la même cardinalité que \(T\). Plus précisément, si nous pensons aux nombres en binaire, alors chaque nombre réel dans \(\) peut être écrit comme \(\sum_{j = 1}^{\infty}\frac{a_j}{2^j} =(a_1,a_2, \cdots)\) où \(a_j ∈\{0,1\}\). Nous devons tenir compte du fait que des représentations binaires telles que \(0.0111…\) et \(0.1000…\) représentent le même nombre réel (disons qu’aucune représentation ne se terminera par une chaîne infinie de zéros), alors nous pouvons voir que \(\) a la même cardinalité que \(T-U\), où \(U\) est l’ensemble de toutes les séquences se terminant par une chaîne infinie de zéros. Il s’avère que \(U\) lui-même est un ensemble dénombrable.

Exercice \(\PageIndex{4}\)

Soit \(U_n = \{(a_1, a_2, a_3, …) / a_j ∈\{0,1\}\) et \(a_ {n+1} = a_{n+2} = ··· = 0\}\). Montrez que pour chaque \(n\), \(U_n\) est fini et utilisez ceci pour conclure que \(U\) est dénombrable infini.

Les deux problèmes suivants montrent que la suppression d’un ensemble dénombrable d’un ensemble dénombrable ne modifie pas sa cardinalité.

Exercice \(\PageIndex{5}\)

Soit \(S\) un ensemble infini. Prouvez que \(S\) contient un sous-ensemble infini dénombrable.

Exercice \(\PageIndex{6}\)

Supposons que \(X\) soit un ensemble non dénombrable et que \(Y ⊂ X\) soit infini dénombrable. Prouvez que \(X\) et \(X-Y\) ont la même cardinalité.

Indice

Let\(Y = Y_0\). Si \(X-Y_0\) est un ensemble infini, alors par le problème précédent, il contient un ensemble infini dénombrable \(Y_1\). De même, si \(X-(Y_0 ∪ Y_1)\) est infini, il contient également un ensemble infini \(Y_2\). Encore une fois, si \(X-(Y_0 ∪ Y_1 ∪ Y_2)\) est un ensemble infini alors il contient un ensemble infini \(Y_3\), etc. Pour \(n = 1,2,3,…, \) soit \(f_n:Y_{n-1} → Y_n\) une correspondance un à un et définissons \(f: X → X-Y\) par

\

Montrez que \(f\) est un à un et sur.

Les problèmes ci-dessus disent que \(R\), \(T-U\), \(T\) et \(P(N)\) ont tous la même cardinalité.

Comme cela a été indiqué précédemment, les travaux de Cantor sur les ensembles infinis ont eu un impact profond sur les mathématiques au début du XXe siècle. Par exemple, en examinant la preuve du théorème de Cantor, l’éminent logicien Bertrand Russell a conçu son célèbre paradoxe en 1901. Avant cette époque, un ensemble était naïvement considéré comme une simple collection d’objets. Grâce au travail de Cantor et d’autres, les ensembles devenaient un objet d’étude central en mathématiques car de nombreux concepts mathématiques étaient reformulés en termes d’ensembles. L’idée était que la théorie des ensembles devait être un thème unificateur des mathématiques. Ce paradoxe a mis le monde mathématique à l’oreille.

Paradoxe de Russell

Considérons l’ensemble de tous les ensembles qui ne sont pas des éléments d’eux-mêmes. Nous appelons cet ensemble \(D\) et demandons: « Est-ce que \(D ∈ D\)? » Symboliquement, cet ensemble est

\

Si \(D ∈ D\), alors par définition, \(D\ not {∈} D\). Si D 6∈ D, alors par définition, \(D ∈ D\).

Si vous regardez la preuve du théorème de Cantor, c’est essentiellement l’idée qui nous a donné la contradiction. Qu’une telle contradiction se produise au niveau le plus élémentaire des mathématiques était scandaleux. Cela a forcé un certain nombre de mathématiciens et de logiciens à concevoir soigneusement les axiomes par lesquels les ensembles pouvaient être construits. Pour être honnête, la plupart des mathématiciens abordent toujours la théorie des ensembles d’un point de vue naïf, car les ensembles que nous traitons généralement relèvent de la catégorie de ce que nous appellerions des « ensembles normaux. »En fait, une telle approche est officiellement appelée Théorie Naïve des Ensembles (par opposition à la Théorie Axiomatique des ensembles). Cependant, les tentatives de mettre la théorie des ensembles et la logique sur des bases solides ont conduit à l’étude moderne de la logique symbolique et, finalement, à la conception de la logique informatique (machine).

Un autre endroit où le travail de Cantor a eu une profonde influence dans la logique moderne vient de quelque chose auquel nous avons fait allusion auparavant. Nous avons montré auparavant que le carré unitaire \(×\) avait la même cardinalité qu’un sous-ensemble non dénombrable de \(\mathbb{R}\). En fait, Cantor a montré que le carré unitaire avait la même cardinalité que \(\mathbb{R}\) lui-même et a été déplacé pour avancer ce qui suit en 1878.

Conjecture (L’hypothèse du continu)

Chaque sous-ensemble non dénombrable de \(\mathbb{R}\) a la même cardinalité que \(\mathbb{R}\).

Cantor était incapable de prouver ou de réfuter cette conjecture (avec tous les autres mathématiciens). En fait, prouver ou réfuter cette conjecture, qui a été surnommée l’Hypothèse du Continuum, était l’un des célèbres problèmes de Hilbert \(23\) présentés comme un défi aux mathématiciens au Congrès international des Mathématiciens en 1900.

Puisque \(\mathbb{R}\) a la même cardinalité que \(P(N)\), alors l’hypothèse du continu a été généralisée à la:

Conjecture (L’Hypothèse du Continu Généralisé)

Étant donné un ensemble infini \(S\), il n’y a pas d’ensemble infini qui ait une cardinalité strictement entre celle de \(S\) et son ensemble de puissance \(P(S)\).

Les efforts pour prouver ou réfuter cela ont été vains et avec raison. En 1940, le logicien Kurt Gödel a montré que l’Hypothèse du Continu ne pouvait être réfutée à partir des Axiomes de Zermelo-Fraenkel de la théorie des ensembles 1. En 1963, Paul Cohen a montré que l’Hypothèse du Continu ne pouvait pas être prouvée en utilisant les Axiomes de Zermelo-Fraenkel. En d’autres termes, les axiomes de Zermelo-Fraenkel ne contiennent pas suffisamment d’informations pour décider de la véracité de l’hypothèse.

Nous sommes prêts à parier qu’à ce stade, votre tête pourrait nager un peu avec l’incertitude. Si c’est le cas, sachez que ce sont les mêmes sentiments que la communauté mathématique a éprouvés au milieu du XXe siècle. Dans le passé, les mathématiques étaient considérées comme un modèle de certitude logique. Il est déconcertant de constater qu’il y a des déclarations qui sont « indécidables. »En fait, Gödel a prouvé en 1931 qu’un système d’axiomes finis cohérent contenant les axiomes de l’arithmétique contiendrait toujours des énoncés indécidables qui ne pourraient être prouvés ni vrais ni faux avec ces axiomes. Les connaissances mathématiques seraient toujours incomplètes.

 fig 9.3.2.png

Figure \(\PageIndex{2}\): Kurt Gödel

Ainsi, en essayant de poser les bases du calcul sur un sol solide, nous sommes arrivés à un point où nous ne pouvons jamais obtenir de certitude mathématique. Cela signifie-t-il que nous devrions lever les mains et concéder la défaite? Devrions-nous être paralysés par la peur d’essayer quoi que ce soit? Certainement pas! Comme nous l’avons mentionné précédemment, la plupart des mathématiciens réussissent bien en adoptant une approche pragmatique: utiliser leurs mathématiques pour résoudre les problèmes qu’ils rencontrent. En fait, ce sont généralement les problèmes qui motivent les mathématiques. Il est vrai que les mathématiciens prennent des risques qui ne sont pas toujours couronnés de succès, mais ils les prennent quand même, souvent avec succès. Même lorsque les succès mènent à plus de questions, comme ils le font généralement, aborder ces questions conduit généralement à une compréhension plus profonde. À tout le moins, notre compréhension incomplète signifie que nous aurons toujours plus de questions à répondre, plus de problèmes à résoudre.

Que pourrait demander d’autre un mathématicien ?