Fonction réciproque

[Deeprod]

Bonjour,
je suis en train de faire une étude sur les cardinaux et je recontre quelques difficultés notament à propos de la diagonalisation de Cantor.

Nous avons définis la fonction suivante φ définie par:

φ : N² → N
(m,n) ↦ φ[(m,n)]=1/2 (m+n)(m+n+1)+m

Cette fonction, nous permet d'associer à tout couples de N² un rang (diagonalisation de Cantor).

Nous devons démontrer que cette fonction est bijective. Ainsi, si elle est bijective, nous pourrons affirmer que N² et N sont équipotents et par conséquent que N² est dénombrable et que card(N²) = card(N) = ℵ0.

Pouvez m'aider à démontrer que cette fonction est bijective?? il serait préférable défénir une fonction réciproque de N dans N² pour avoir ainsi une fonction qui nous permette à partir d'un rang de retrouver le couple associé.

je suis dans une école d'ingénieur informatique et nous devons faire un petit prog qui nous permette de faire le décodage et le codage...

je remercie par avance pour votre aide...

Deeprod
-----

[G13]

Si on compte les couples (m,n) en commencant par (0,0) puis tous ceux de somme 1 (c-à-d (1,0) puis (0,1)) puis tous ceux de somme 2 (c-a-d (2,0) puis (1,1) puis (0,2)), etc...,on obtient la fonction . (a une inversion pres de m et n je crois)

[Médiat]

Si le but est de calculer la réciproque à l'aide d'un programme, c'est à dire de trouver m et n quand on connaît l'image y ; il suffit de poser m+n =x, de résoudre x(x+1) <= 2y, de choisir le plus grand x possible (partie entière de la solution positive de l'équation ci-dessus) ; calculer m à partir du calcul précédent est très simple, et comme n = x - m, c'est fini.
Pour démontrer la bijectivité, il faut juste montrer que les opérations ci-dessus sont toujours possibles.