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

Plus généralement, pour des polynômes qui sont des fonctions de couplage de Nn vers N, vous pouvez consulter la page Polynômes de couplage de N^n dans N - Partie I ou la page provisoireedu wiki de Jeux-et-Mathematiques sur les fonctions de couplage de Skolem. Ce sont des polynômes de degré n. Quelques explications et des algorithmes sont donnés sur la fonction et son inverse inverse ainsi que sur la construction des polynômes.
La fonction de Cantor est le cas particulier que l'on obtient en prenant n=2.
Un choix plus important est proposé à la page provisoire du wiki : Partie II - 2n-2 bijections de Nn vers N. Aucune explication des calculs n'est donnée pour l'instant, sur cette page.

Codage de Nn par des éléments de N

Les deux seuls polynômes de degré 2, des deux variables x et y, qui soient des bijections de N2 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 Nn sur N reste ouvert et semble très difficile.

En composant les polynômes précédents on obtient des bijections de Nn sur N. Les polynômes suivants définissent des bijections de N3 sur N et de N4 sur N, mais il y en a bien d'autres.
f(x,y) = ((x+y)^2+3*x+y)/2     de N2 vers N
       = 1/2*x^2 + x*y + 1/2*y^2 + 3/2*x + 1/2*y

h(x,y,z) = f(f(x,y),z)   de N3 vers N
         = 3/4*(x + y)^2 + 1/8*((x + y)^2 + 3*x + y + 2*z)^2 + 9/4*x + 3/4*y + 1/2*z
         = 1/8*x^4 + 1/2*x^3*y + 3/4*x^2*y^2 + 1/2*x*y^3 + 3/4*x^3 + 7/4*x^2*y + 1/2*x^2*z + 5/4*x*y^2 + 
           x*y*z + 1/2*y^2*z + 15/8*x^2 + 1/8*y^4 + 1/4*y^3 + 9/4*x*y + 3/2*x*z + 7/8*y^2 + 1/2*y*z + 
           1/2*z^2 + 9/4*x + 3/4*y + 1/2*z

k(x,y,z,t) = f(h(x,y,z),t) de N4 vers N
           = 9/8*(x + y)^2 + 3/16*((x + y)^2 + 3*x + y + 2*z)^2 + 1/128*(6*(x + y)^2 + ((x + y)^2 + 3*x + y + 
                  2*z)^2 + 8*t + 18*x + 6*y + 4*z)^2 + 1/2*t + 27/8*x + 9/8*y + 3/4*z

l(x,y,z,t,u) = f(k(x,y,z,t), u)  de N5 vers N
             = 27/16*(x + y)^2 + 9/32*((x + y)^2 + 3*x + y + 2*z)^2 + 3/256*(6*(x + y)^2 + ((x + y)^2 + 3*x + y + 
                  2*z)^2 + 8*t + 18*x + 6*y + 4*z)^2 + 1/32768*(144*(x + y)^2 + 24*((x + y)^2 + 3*x + y + 2*z)^2 + 
                  (6*(x + y)^2 + ((x + y)^2 + 3*x + y + 2*z)^2 + 8*t + 18*x + 6*y + 4*z)^2 + 64*t + 128*u + 432*x + 
                  144*y + 96*z)^2 + 3/4*t + 1/2*u + 81/16*x + 27/16*y + 9/8*z
Les calculs ont été réalisés à l'aide du logiciel libre et "open-source" Sage.
Seules les expressions développées de f(x, y) et de h(x,y,z) sont indiquées, celles de k et de l sont trop longues. Développé et réduit, l(x,y,z,t,u) contient plus d'un millier de monômes différents.

Table de valeurs

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




Calculs

Bijection de N2 sur N

À 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.


x :  y :  f(x,y) : 
   

Bijection de Nn sur N

En composant n-1 fois la bijection ci-dessus de N2 vers N on obtient une bijection de Nn sur N.

Par exemple f3(x, y, z) = f(f(x, y), z) ou encore f4(x, y, z, t) = f(f(f(x, y), z), t)

Cette méthode a pour défaut de donner des polynômes de degrés exponentiels $ \displaymath 2^{n-1} $, alors qu'il existe des polynômes de degré $ n $, certains de ces polynômes sont à la page [Polynômes de couplage de $ \displaymath {\mathbb N}^n $ dans $ \displaymath \mathbb N $ - Partie I], d'autres polynômes de degré $ n $ seront donnés dans des pages à venir du site.


x y z t ... :  n :  fn(x,y,...) : 
   

Ensembles équipotents

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 parfois possible, un sous-ensemble F de E, différent de E peut dans certains cas avoir autant d'éléments que E, (il y a aussi d'autres exemples où ce n'est pas vrai, voir plus bas).

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 :


Naturel impair :  naturel : 
   


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.

Décimation et bijection de N2 vers N

Dans l'exemple suivant il n'est plus question des polynômes de Cantor. Cette fois l'idée sous-jacente est la décimation (Voir la page d'Éric Angelini Decimation-like sequences), mais la mise en œuvre de cette décimation est sensiblement différente.

Méthode de calcul de fn(x, y):

Choisissez une valeur de n au moins égale à 2. En prenant n=10 on comprend mieux le sens du mot décimation. Soit donc n=10 dans l'exemple qui suit et construisons une bijection fn = f10 de N^2 vers N :
Écrivez sur un papier, aussi loin que possible les éléments de N = 0, 1, 2, 3, ....
1) Soulignez le 1er nombre, le n+1=11ème, le 2n+1=21ème... vous aurez successivement les images f10(0,0)=0, f10(0,1) = 10, f10(0,2) = 20... Puis effacez tous les nombres soulignés !
Vous n'avez plus sur votre feuille que 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26 ...
2) Recommencez en soulignant le 1er nombre, le 11ème, le 21ème... vous aurez les images f10(1,0)=1, f10(1, 1)=12, ... Puis effacez tous les nombres soulignés. Il reste 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 16, 17, 18, 19, 21, 22, 24, 25, 26 ...
3) Recommencez le même processus une troisième fois pour obtenir les images f10(2,0)=2, f10(2,1)=14 ... Effacez tous les nombres soulignés.
Et ainsi de suite. (Il ne reste plus qu'à démontrer que l'on obtient effectivement une bijection fn).

Dit plus simplement : On place dans N les éléments successifs, pour y croissant, de fn(0,y), en avançant de n cases libres en n cases, puis ensuite ceux de fn(1,y), puis ceux de fn(2,y)... (Dans une construction pratique on garde x et y inférieurs à un nombre choisi, dans les tableaux construits ci-dessous, cette limite est 10).


n =     x y =        



Ces fonctions fn permettent de construire de nombreuses suites d'entiers dont voici quelques exemples :
Suites fn(x, 0) lorsque x croît
f2(x, 0) : 0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,... OEIS A000225
f3(x, 0) : 0,1,2,4,7,11,17,26,40,61,92,139,209,314,472,709,1064,1597,2396,3595,5393,8090,12136,18205,27308,40963,61445,... OEIS A006999
f4(x, 0) : 0,1,2,3,5,7,10,14,19,26,35,47,63,85,114,153,205,274,366,489,653,871,1162,1550,2067,2757,3677,4903,6538,8718,...
f5(x, 0) : 0,1,2,3,4,6,8,11,14,18,23,29,37,47,59,74,93,117,147,184,231,289,362,453,567,709,887,1109,1387,1734,2168,2711,3389,...
Suites fn(x, 1) lorsque x croît
f2(x, 1) : 2,5,11,23,47,95,191,383,767,1535,3071,6143,12287,24575,49151,98303,...OEIS A055010 et A083329 (sauf le premier terme) 
f3(x, 1) : 3,5,8,13,20,31,47,71,107,161,242,364,547,821,1232,1849,2774,4162,6244,9367,14051,21077,31616,47425,71138,...
f4(x, 1) : 4,6,9,13,18,25,34,46,62,83,111,149,199,266,355,474,633,845,1127,1503,2005,2674,3566,4755,6341,8455,11274,...
Suites fn(x, x) lorsque x croît
f2(x, x) : 0,5,19,55,143,351,831,1919,4351,9727,21503,47103,...
f3(x, x) : 0,5,16,34,67,121,223,382,655,1091,1840,2977,4858,7834,12775,20290,32663,51421,82484,...
f4(x, x) : 0,6,15,31,55,90,147,223,338,509,745,1077,1589,2274,3239,4671,6557,9255,13149,18467,...
Suites fn(1, y) lorsque y croît
f2(1, y) : 1,5,9,13,17,21,25,29,33,37,41,45,49,53,57,61,...OEIS A016813
f3(1, y) : 1,5,10,14,19,23,28,32,37,41,46,50,55,59,64,68,73,77,82,86,91,95,100,104,109,113,118,...
f4(1, y) : 1,6,11,17,22,27,33,38,43,49,54,59,65,70,75,81,86,91,97,102,107,113,118,123,129,134,139,145,150,155,161,166,171,177,182,187,193,...
Suites fn(2, y) lorsque y croît
f2(2, y) : 3,11,19,27,35,43,51,59,67,75,83,91,99,107,115,123,...OEIS A017101 8y+3
f3(2, y) : 2,8,16,22,29,35,43,49,56,62,70,76,83,89,97,103,110,116,124,130,137,143,151,157,164,170,178,...
f4(2, y) : 2,9,15,23,30,37,45,51,58,66,73,79,87,94,101,109,115,122,130,137,143,151,158,165,173,179,186,194,201,207,215,222,229,237,243,250,258,...

Liens

Some remarks on the Cantor pairing function Meri Lisi – "Le Matematiche" Vol. 62 no 1 p. 55-65 (2007) – Cet article contient des résultats et des généralisations de la fonction d'appariement de Cantor.
On n-tupling polynomials of small degrees" Maxim Vsemirnov, (Programme of the 14th Days of Weak Arithmetics St.Petersburg, Russia May 22-24, 1997). (Document incomplet, 1 page seulement).
Georg Cantor (1845-1918): the man who tamed infinity Eric Schechter. (Slides for a lecture about infinity).
À la recherche de la genèse du dernier mémoire mathématique de Georg Cantor: Du côté de la correspondance entre Cantor et Franz Goldscheider (lettre du 18 juin 1886) – Anne-Marie Décaillot Equipe REHSEIS (CNRS, Université Paris-Diderot) – Cette première lettre constitue un véritable exposé introductif des fondements de la théorie cantorienne des ensembles, présentant les notions de cardinaux et d'ordinaux et leurs premières manipulations opératoires.
Cantor Georg Ferdinand russe, 1845-1918 ChronoMath, une chronologie des Mathématiques
Georg CANTOR (1845 - 1918)


















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014