En mathématiques, une fonction de couplage, est une méthode permettant d’attribuer de manière unique un entier naturel à un couple d'entiers naturels.
En théorie des ensembles, on peut utiliser n'importe quelle fonction de couplage pour prouver que l'ensemble des entiers relatifs et celui des nombres rationnels ont la même cardinalité que l'ensemble des entiers naturels. En théorie de la calculabilité, la fonction de couplage de Cantor est utilisée pour coder les k-uplets, ainsi une fonction de peut être représentée par une fonction de .
Définition Une fonction de couplage est une bijection calculable de dans .
Fonction de couplage de Cantor
La fonction de couplage de Cantor est définie par
Le théorème de Fueter-Pólya énonce que cette fonction est, avec la fonction , la seule fonction de couplage quadratique. En revanche, savoir s'il s'agit de la seule fonction polynomiale de couplage est encore une question ouverte. On note parfois le résultat de la fonction de couplage sur les entrées et .
La fonction de Cantor peut être généralisée de la manière suivante :
avec
Construction graphique thumb|Cette autre progression en diagonale, analogue mais différente de celle de la fonction de Cantor, fournit une autre fonction de couplage. Ici elle est utilisée pour prouver la dénombrabilité des nombres rationnels.
La fonction de couplage de Cantor est définie en parcourant par diagonales successives.
En suivant l'énumération diagonale par diagonale La fonction de couplage de Cantor vérifie :
ce qui fournit une définition récursive de la fonction (le couple (x + y, x) décroît strictement à chaque appel récursif pour l'ordre lexicographique ).
Pour tout , la diagonale d'équation contient points (de à ). Le nombre de points des diagonales qui précèdent celle du couple est donc égal à (le -ième nombre triangulaire). Par conséquent l'image du couple est donnée par : .
Bijection réciproque
D'après la construction ci-dessus, est bijective, c'est-à-dire que pour tout , il existe un unique couple tel que .
Retrouvons-le par analyse-synthèse en cherchant tel que et .
Ces deux équations impliquent , donc est nécessairement l'unique entier naturel tel que , puis et , ce qui prouve l'injectivité.
Réciproquement, le triplet ainsi construit à partir de vérifie bien les deux équations, ce qui prouve la surjectivité.
La bijection réciproque de est donc donnée par : avec égal à la partie entière du réel (solution de l'équation du second degré ).
Autres fonctions de couplage Via le bon ordre canonique sur ℕ×ℕ
On rencontre fréquemmentVoir par exemple . la méthode suivante pour démontrer que (où est un cardinal infini : un bon ordre est défini sur dont chaque éléments possède prédécesseurs, de sorte que et sont isomorphes comme ensembles ordonnés et sont donc équipotents. Dans le cas plus simple où cette méthode conduit à une bijection .
Via une propriété arithmétique élémentaire Une autre méthode consiste à utiliser la propriété arithmétique suivante : tout entier peut s'écrire d'une façon unique sous la forme du produit d'une puissance de 2 par un nombre impair, soit , où . L'application définie par est ainsi une bijection.
Via l'écriture d'un nombre entier en base 2 Bourbaki utilise une injection , afin de prouver l'équipotence de ces deux ensembles, dans le volume I des Éléments de mathématiques (III §6). Il s'avère que c'est une bijection. Tout possède une unique écriture en base 2 (où sont les chiffres de l'écriture de ), c'est-à-dire : . On observe que si alors , et si alors et . À l'entier on fait correspondre la suite définie par Dit autrement est la suite infinie de 0 et de 1 qui commence par énumérer les chiffres de dans l'ordre inverse de leur écriture puis se poursuit par une infinité de 0, soit . L'application est une bijection := le sous-ensemble de constitué des suites presque nulles (et ).
Par ailleurs, si on définit par et pour tout . L'application est évidemment une bijection .
En conclusion est une bijection .
Donnons un exemple : . On a ; alors
Donc .
Inversement, partant de , on a
Donc .
Notes et références
Bibliographie
Voir aussi Article connexe Déployeur universel Liens externes
Catégorie:Georg Cantor Catégorie:Théorie des ensembles