N et N² sont équipotents

Bonjour, je cherche à montrer qu’il existe une bijection de $\mathbf N^2$ dans $\mathbf N$ (et inversement, évidemment).

De tête, je n’arrivais pas à trouver, donc pour simplifier le problème j’ai cherché sur internet une telle application et j’ai trouvé un topic qui demande justement de montrer que l’application $f : \mathbf N^2 \to \mathbf N : (n, k) \mapsto \dfrac{(n + k)(n + k + 1)}{2} + k$ est bijective.

Il y a plusieurs corrections disponibles mais un peu brouillons et puis je préfère réfléchir par moi-même et avoir mon propre raisonnement, quitte à demander quelques indices ici.

Je remarque que $f(n, k)$ est la somme de $1$ à $n + k$ augmentée de $k$.

Mais même avec cette info je n’arrive pas à trouver une piste de départ…

Une idée?

Merci pour ta réponse Holosmos, en fait c’est la construction un peu inhabituelle de la fonction qui me bloque alors que la surjectivité et l’injectivité reste ce que ça a toujours été…

@Demandred : Bien vu, je vais dessiner donc.

L’idée est d’essayer de trouver comment construire une fonction qui relie les deux, comme la fonction que tu proposes. Cela t’aidera peut-être pour mieux visualiser la chose et imaginer ta propre fonction (et ensuite d’en démontrer effectivement la bijectivité).

Que représentent les flèches rouges sur ton schéma?

En fait, j’ai construit un damier dans lequel, par exemple, pour la case de coordonnées (1, 2) j’attribut le nombre 1 + 2 + 3 + 2 = 8.

Salut,

Tu peux aussi essayer d’écrire chaque nombre sous la forme d’une puissance de deux fois un nombre impair.

@Universite : Non, pas la solution…

EDIT : Bon, tu peux la mettre en secret au moins?…

EDIT 2 : Merci, comme ça je ne serai pas spoiler…

Que signifie ce symbole $\mathbf{Z}_{\geq 0}^{\infty}$?

Ok, je reviendrai sur l’histoire du dessin après car je pense avoir trouvé une solution algébrique pour la surjectivité.

Tu peux aussi essayer d’écrire chaque nombre sous la forme d’une puissance de deux fois un nombre impair.

Pourquoi ?

En prenant $\varphi(k, l) = 2^k(2l + 1)$ on a une bijection de $\mathbb N^2$ dans $\mathbb N^*$ assez simple à montrer.

Personnellement je trouve plus élégant de regarder l’injection $(k,l)\mapsto 2^k3^l$. Ça donne une injection de $\mathbf N^2$ dans $\mathbf N$. Comme on a une injection de $\mathbf N$ dans $\mathbf N^2$ (de façon évidente), il y a un résultat général montrant que les deux sont équipotents.

Ça peut paraître plus difficile, mais au moins on peut généraliser la chose à tous les $\mathbf N^k$ juste en prenant $k$ nombres premiers entre eux … et puis le fait que deux injections donne une bijection c’est trop important pour être ignoré.

En effet, et finalement ça revient quasiment à la fin du message de @Universite sur les nombres premiers pour la généralisation (sur le principe, mais pas sur la manière dont l’idée est utilisée).

Par contre, la représentation graphique se voit un peu moins bien.

Voici ma version :

Si $f$ est surjective alors $\forall y \in \mathbf N, \exists (n, k) \in \mathbf N^2 : y = f(n, k)$.

On cherche donc à trouver une expression des antécédents n et k :

$y = \dfrac{(n + k)(n + k + 1)}{2} + k \iff y = \tau(n + k) + k$ où $\tau(n + k)$ représente la somme des nombres compris entre 1 et n + k.

Soit $p$ un entier naturel tel que $\tau(p) \leq y < \tau(p + 1)$ quel que soit $y$. Ce $p$ est unique puisque la suite $(\tau_n)_{n \in \mathbf N}$ définie par $\tau_n = \dfrac{n(n + 1)}{2}$ est strictement croissante et tend vers l’infini positif.

Posons $n + k = p$, ensuite $k = y - \tau(n + k) = y - \tau(p) = y - \dfrac{p(p + 1)}{2}$, et par suite, $n = p - k = p - y + \dfrac{p(p + 1)}{2} = \dfrac{p(p + 3)}{2} - y$.

D’une part, on a bien $k \in \mathbf N$ puisque $y \geq \tau(p)$ et $n \in \mathbf N$ car $p \geq k$.

D’autre part, $f(\dfrac{p(p + 3)}{2} - y, y - \dfrac{p(p + 1)}{2}) = y$ (je ne détaille volontairement pas car c’est trop long à écrire avec Latex).

Donc f est surjective.

Puisque p est unique, $\tau(p)$ l’est aussi donc en fixant $y \in \mathbf N$ on a bien $k = y - \tau(p)$ unique, il en va donc de même pour $n = p - k$, ce qui conclut.

Soit $p$ un entier naturel tel que $\tau(p) \leq y < \tau(p + 1)$ quel que soit $y$. Ce $p$ est unique puisque la suite $(\tau_n)_{n \in \mathbf N}$ définie par $\tau_n = \dfrac{n(n + 1)}{2}$ est strictement croissante et tend vers l’infini positif.

Il faut rajouter à l’unicité l’existence. Toutes les suites strictement croissantes tendant vers l’infini ne vérifient pas cette propriété. (Par exemple si on avait $\tau(p) = 10$, alors $y=9$ n’aurait pas de tel $p$.)

Posons $n + k = p$, ensuite $k = y - \tau(n + k) = y - \tau(p) = y - \dfrac{p(p + 1)}{2}$

C’est périlleux de poser une addition comme étant égale à une quantité prescrite. Il faut que tu discutes de l’existence et dde $(n,k)$ tel que $n+k=p$ et $k = y-\tau(p)$.

Puisque p est unique, $\tau(p)$ l’est aussi donc en fixant $y \in \mathbf N$ on a bien $k = y - \tau(p)$ unique, il en va donc de même pour $n = p - k$, ce qui conclut.

Qu’est-ce que tu veux dire par $\tau(p)$ est unique ?

Il faut rajouter à l’unicité l’existence.

Faut-il que j’exhibe un tel $p$?

Il faut que tu montres qu’il existe. Que ça soit en l’exhibant ou en montrant que ça ne peut pas être autrement, ça c’est comme tu veux.

Ok, avant de corriger, je voudrais revenir sur l’existence de (n, k) dont tu parles.

Si je montre que $f(n, k)$ est compris entre $\tau(n + k)$ et $\tau(n + k + 1)$ alors je pourrais écrire que $n + k = p$ et au passage montrer que n et k sont uniques (puisque p l’est)?

Tu peux écrire $n+k=p$ en effet. En revanche $n,k$ ne sont pas nécessairement uniques juste à partir de $n+k=p$. Contre exemple : $1+2 =3$ et $2+1=3$ et même $3+0=3$ et même $0+3=3$. Il y a généralement plein de solutions à $n+k=p$.

Oui mais pour montrer que $f$ est surjective, on a pris $y \in \mathbf N$ tel que $y = f(n, k) \iff y = \tau(n + k) + k$ donc $k = y - \tau(n + k)$.

Dès lors, on peut écrire $n + k = p$ et $k = y - \tau(n + k)$ ce qui permet d’en déduire les solutions qui sont bien uniques?

De tête ça me paraît pas tout à fait évident, pourtant je suis pas spécialement fatigué. Donc d’après le baromètre Holosmos tu dois rédiger plus que ça.

De tête, il me semble qu’il faut au moins utiliser l’injectivité de $k\mapsto \tau(n+k)$.