Théorème de Cantor ' théorème de Cantor

Résumé

Georg Cantor a prouvé de nombreux théorèmes, mais celui généralement appelé théorème de Cantor est le premier théorème non trivial de la nouvelle théorie des ensembles de Cantor: certains infinis sont plus grands que d’autres; en particulier, tout nombre cardinal infini (ou ensemble infini) en génère un plus grand en prenant l’ensemble de puissance.

(Le théorème s’applique à tous les ensembles, pas seulement aux ensembles infinis, bien que ce soit assez évident pour les ensembles finis.)

Le théorème de Cantor ne doit pas être confondu avec le théorème de Cantor “Schroeder“ de Bernstein (voir nombre cardinal), qui est différent (mais lié, car il est important de justifier l’interprétation de Cantor de son théorème).

Histoire

Avant Cantor, les gens avaient tendance à penser l’infini (qu’ils y croyaient ou non) comme un concept absolu: tous les infinis sont équivalents. On avait remarqué (par Galilée, par exemple) qu’il est possible de donner à un ensemble infini une auto-injection qui n’est pas une surjection; par exemple, l’inclusion des entiers pairs dans les entiers par doublement. Voici donc deux infinités  € “l’infini EE des entiers pairs et l’infini NN de tous les entiers ⠀” qui sont réellement équivalents, même si à première vue, il semblerait que EE soit plus petit.

Cantor a montré qu’une telle équivalence échoue avec les nombres réels RR : aucune carte de NN à RR ne peut être surjective (de sorte que RR est indénombrable). Son premier argument était ad hoc, mais il a ensuite généralisé cela avec l’argument diagonal pour montrer qu’aucune carte d’un ensemble SS à son ensemble de puissance ðmath ’”S\mathcal{P} S ne pouvait être surjective. (Cela couvrait l’invraisemblance de RR, puisque Cantor a trouvé une bijection entre RR et ðmath'”N\mathcal{P}N, que nous pouvons maintenant considérer comme une instance du théorème de Bernstein de Cantor.) Comme il existe une carte injective évidente (la carte singleton) de SS à ðmath ’”S\mathcal{P} S, Cantor a conclu que la cardinalité de l’un est strictement plus petite que la cardinalité de l’autre.

L’argument de Cantor, comme toute sa théorie des ensembles, était controversé à l’époque. Ceux qui, comme Kronecker, croyaient que toutes les mathématiques devraient être des mathématiques finies, le considéraient comme dénué de sens. Les premiers constructivistes encore plus modérés, tels que Brouwer et Weyl, ont trouvé que cela avait peu d’intérêt. (En particulier, il ne dit rien directement sur RR, car la bijection entre RR et ðmath'”N\mathcal{P}N n’est pas valable de manière constructive, bien que la preuve originale de Cantor que RR est incalculable puisse fonctionner.)

Cependant, les versions du théorème énoncées ci-dessous sont valables de manière constructive, et le théorème est même valide de manière prédictive (tant que l’on a des ensembles de fonctions); les constructivistes modernes les acceptent généralement comme des théorèmes. (L’interprétation, cependant, n’est pas si claire.) Ce sont en fait des théorèmes dans le langage interne de tout topos (et le théorème est un théorème dans tout Î\Pi-pretopos).

Déclarations et preuves

( Cela se généralise au théorème du point fixe de Lawvere.)

La présence de la carte diagonale ΔS\Delta_S explique ici pourquoi cette preuve est appelée argument diagonal. (Cette explication est anachronique mais moralement correcte. La preuve de Lawvere’ explique également (en fait généralise) le combinateur YY‑ ou point fixe dans le lambda-calcul non typé, où Y(n) Y(n) est un point fixe pour tout terme nn.

Il s’ensuit immédiatement (même de manière constructive) que si VV a un auto-mappage sans point fixe, alors aucune carte de SS à S→ VS\ to V ne peut être une surjection. En fait, nous avons quelque chose de légèrement plus fort que (mais classiquement équivalent à) l’échec de ff à être une surjection: il existe en fait un élément gg de S→ VS\ to V qui n’est égal à aucune valeur dans la plage de ff. (Si VV a une relation d’éloignement, vous pouvez obtenir un résultat encore plus fort pour une hypothèse correspondante sur nn, mais cela ne s’applique pas aux versions ci-dessous.)

Notez que bien que la négation n’ait pas toutes ses propriétés habituelles en mathématiques constructives, p=Âpp=\neg{p} est toujours impossible.

La version suivante est classiquement équivalente à la version précédente (du moins si vous vérifiez que ðmath’”S\mathcal{P}S est habité), mais pas de manière constructive équivalente. (En effet, contrairement au Théorème, il n’a apparemment pas d’analogue constructif lorsque ðmath ’”S\mathcal{P}S est remplacé par V SV ^S.) Cet argument provient de la Proposition 2.8.8 des Fondements pratiques de Taylor (bien que je ne sache pas s’il est vraiment né là).

Si ii est une injection, alors ff est une rétraction de ii et donc une surjection, ce qui est impossible par le théorème.

Bien sûr, Cantor a également prouvé le théorème, mais sa preuve n’était pas constructive.

Nous pouvons combiner des théorèmes et dans l’énoncé encore plus général suivant, tiré de D4.1.8 de l’Éléphant de Johnstone.

Interprétation

Notez qu’il existe une injection de SS vers ðmath'”S\mathcal{P}S, donnée par la carte singleton. Ainsi, dans l’arithmétique des nombres cardinaux, nous avons

Mais comme il n’y a pas une telle surjection, il n’y a certainement pas de bijection, et nous avons

Nous concluons donc que

C’est-à-dire que chaque ensemble est strictement plus petit en cardinalité que son ensemble de puissance.

Cette interprétation repose sur une bonne relation entre ‰¤\leq et == sur la classe des nombres cardinaux ; en particulier, le théorème de Cantor–Schroeder⠀“ de Bernstein selon lequel ‰¤\leq est antisymétrique. En mathématiques constructives, cette relation fait défaut, et il est tout à fait possible que deux ensembles soient strictement plus petits l’un que l’autre au sens ci-dessus. Grâce à Theorem, cela n’est pas possible pour un ensemble et son ensemble de puissance, mais cela signifie que l’interprétation de <\lt en tant que taille relative est problématique ⠀” en effet presque aussi problématique que l’idée qu’il y a moins d’entiers pairs que d’entiers!

Paul Taylor a soutenu que la valeur essentielle du Théorème de Cantor est le lemme, implicite dans la preuve de Cantor, que Bill Lawvere a isolé en tant que Théorème. Comme l’interprétation principale du théorème n’a de sens que dans un contexte spécifique de théorie des ensembles (en particulier celui où le théorème de Cantor “Schroeder“ de Bernstein est valable), il peut ne pas survivre à une révolution qui renverse la primauté de ce contexte. Mais le lemme de Lawvere survivra, car il fait le travail alors que le théorème de Cantor prend le crédit. (Voir Taylor 2009 ci-dessous pour une discussion plus approfondie sur les lemmes qui font le travail et les théorèmes qui prennent le crédit.)

Dans les posets

Un théorème analogue au théorème des ensembles de Cantor peut être formulé pour d’autres catégories fermées cartésiennes. En particulier, on peut se demander s’il est possible d’avoir une surjection X→2 XX\ à 2^X entre posets, où la base 22 n’est pas le poset discret {0,1}\{0, 1\} mais plutôt l’ordre {0≤1}\{0\leq 1\}.

La réponse est qu’il n’y a pas une telle surjection f: X→2 Xf: X\à 2^X, mais cela ne découle pas d’une simple application du théorème du point fixe de Lawvere’, où l’on essaie d’exclure une telle ff en invoquant l’existence d’une carte 2†’22\ à 2 qui n’a pas de point fixe (il n’existe pas une telle carte poset 2†’22\ à 2!). Nous ne pouvons pas non plus faire appel à un argument de cardinalité grossier ; par exemple, si XX est l’ordinal ω\omega, alors 2 X2^X est l’ordre ⊥⊔ω op\bot\sqcup\omega^{op} (jouxtant librement un élément inférieur ⊥\bot à ω op\omega^{op}), qui a la même cardinalité. Il faut donc chercher une autre preuve.

Prouver qu’il n’y a pas de surjection X→2 XX\ à 2^X est un exercice amusant. Une ligne d’attaque (qui s’intériorise à n’importe quel topos) peut être trouvée ici.

• Théorème du point fixe de Lawvere