bijection de N² dans N

Est-ce que ta fonction remplit bien les conditions initiales? N'y a-t-il qu'une fonction qui les remplisse...
De là, le résultat tombe tout seul.

Regarde bien, dedekind : on a ordonné $\N^2$ par l'ordre lexicographique ; or cet ordre est un bon ordre puisque l'ordre sur $\N$ est lui-même un bon ordre. Soient donc deux fonctions $f$ et $g$ vérifiant les conditions qui sont imposées, et suppose qu'elles sont distinctes, cela signifie que l'ensemble $\{(m,n) \mid f(m,n) \neq g(m,n)\}$ n'est pas vide ; que peux-tu dire d'une partie non vide d'un ensemble bien ordonné ?

Bruno

Salut

Pour la récurrence je procéderais en posant :

$P_n : \forall (x, y)\in \N^2, x+y\leq n, f(x,y)=\frac{(x+y)(x+y+1)}{2}+x$.

L'hérédité devrait alors ce faire en distinguant 2 cas (à voir en rédigeant).
a+

Pas tout à fait ! Appelons $a$ le premier couple tel que $f(a) \neq g(a)$ ; les fonctions coïncident sur son prédécesseur d'après la définition de $a$, et en appliquant les formules définissant les fonctions, tu constates que $f(a) = g(a)$ ce qui contredit l'hypothèse sur $a$.

De rien.

Bonjour,

On considère la fonction prédécesseur p(x,y) sur tout couple <> (0,0) :
p(0,y) = (y-1,0) pour y>0,
p(x,y) = (x-1,y+1) pour x>0.

On a donc f(0,0)=0 et f(x,y) = f(p(x,y)) + 1 pour (x,y)<>(0,0).
Elle est unique : supposons f et f' vérifiant ces relations et distinctes.
Soit (a,b) tel que f(a,b) <> f'(a,b) et rendant f(x,y) minimum. f(p(a,b)) = f(a,b)-1 est donc inférieur, f(p(a,b)) = f'(p(a,b)) et f(a,b) = f'(a,b), contradiction.

Je reviens avec ma récurrence !

Soit la propriété $P_n : \forall (x, y)\in \N^2, x+y\leq n, f(x,y)=\frac{(x+y)(x+y+1)}{2}+x$ à prouver.

Pour $n=0$ :
$f(0,0)=0$ la formule est valable et donc $P_0$ est vraie.

Supposons $P_n$ vraie à un rang $n\geq 0$.
Soit $(x, y)\in \N^2$ tel que $x+y\leq n+1$. Si l'inégalité est stricte alors $x+y\leq n$ est on conclut avec l'hypothèse de récurrence.
Supposons donc que $x+y=n+1$.
1er cas : $x=0$. On a alors :
$f(0,n+1)=f(n,0)+1$ et on applique alors la formule de récurrence. On obtient bien après calculs la forme voulue.

2ème cas :$x>0$. On a alors :
$f(x,y)=f(x-1,y+1)+1=.... = f(0,y+x)+x = f(y+x-1,0)+x+1$
Comme $y+x-1=n$ on peut appliquer notre formule de récurrence et on obtient après calculs la forme voulue.
Ceci prouve que $P_{n+1}$ est vraie

Plus qu'à conclure.

Voilà me semble-t-il une façon de faire.
a+

a+