Polynômes de Cantor.
Bijections de Nⁿ sur N.

Les deux seuls polynômes de degré 2, des deux variables x et y, qui soient des bijections de N² sur N, sont les polynômes de Cantor (Montré en 1923 par Fueter et Pólya) :

f(x,y)=((x+y)^2+3x+y)/2 et g(x,y)=((x+y)^2+x+3y)/2.

On a naturellement g(x,y)=f(y,x)

Le problème général qui est de déterminer les polynômes de degrés d bijectifs de Nⁿ sur N reste ouvert et semble très difficile.

En composant les polynômes précédents on obtient des bijections de Nⁿ sur N. Par exemple, Les polynômes f(f(x,y),z), f(f(f(x,y),z),t) définissent des bijections de N³ sur N et de N⁴ sur N, mais il y en a bien d'autres.

La table ci-dessous donne quelques valeurs du polynôme : f(x,y)=((x+y)^2+3x+y)/2.

À partir du couple (x, y) on peut calculer son image k = f(x, y) dans N.
Inversement, à partir de k, on peut calculer x et y tels que f(x, y) = k.

S'il existe une bijection de l'ensemble E vers l'ensemble F, on dit que E et T sont équipotents, qu'ils ont le même cardinal, ou encore qu'ils ont exactement le même nombre d'éléments.

Si l'ensemble E est un ensemble fini (ayant un nombre fini d'éléments) et F un sous-ensemble de E, différent de E, il n'existe pas de bijection de E vers F et donc E et F n'ont pas le même nombre d'éléments.
Mais si E est un ensemble infini, c'est possible, un sous-ensemble F de E, différent de E peut avoir autant d'éléments que E.

Par exemple l'ensemble N des entiers naturels est en bijection avec l'ensemble I des naturels impairs, il y a donc exactement autant de naturels impairs que de naturels (pairs ou impairs).

La bijection n --> (n-1)/2 de I dans N est illustrée ci-dessous :

Par contre, l'ensemble N des entiers naturels est un sous-ensemble de l'ensemble R des nombres réels mais N et R ne sont pas équipotents (n'ont pas le même nombre d'éléments).

Les ensembles N des naturels, Q des rationnels et D des décimaux sont équipotents.

Un ensemble E, fini ou infini, n'est jamais équipotent à l'ensemble P(E) de ses parties.

Pages de liens sur Cantor et sur la combinatoire.