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)$.
@Karnaj : Ok, j’avais compris une puissance de (deux fois un nombre impair), ce qui donnait $(2×(2l+1))^k$.
Ce genre de fonction s’appelle une « pairing function ». On trouve aussi sur wikipédia une généralisation de ta fonction @Ozmox : ici (fin de la page, même idée en plus de dimensions).
Mais sinon un ensemble est dénombrable dès que ses éléments sont descriptibles dans un langage fini, pas besoin de dépendre de la structure de $ℤ$ (facteurs premiers).
@Ozmox : Tu peux aussi caractériser $ℕ$ comme l’unique ensemble infini totalement ordonné tel que chaque partie non vide ait un plus petit élément et chaque partie majorée non vide ait un plus grand élément (à isomorphisme unique près). Il faut construire sur $ℕ^2$ un tel ordre. Tu peux déjà prouver qu’une union (disjointe) dénombrable d’ensembles finis est dénombrable (en utilisant ça), puis écrire $ℕ^2$ comme une union disjointe dénombrable (selon les lignes diagonales).
@Holosmos : Ok, je vais commencer par l’existence de p, l’unicité découlant de la stricte monotonie et de la divergence vers l’infini positif de la suite $(\tau_n)$.
Soit $P(p)$ l’assertion $\forall y \in \mathbf N, \exists p \in \mathbf N : \tau(p) \leq y < \tau(p + 1)$.
Par récurrence :
Init. Pour p = 0, y = 0 convient.
Induction. Supposons $P(p)$ vraie i.e. pour $p \in \mathbf N$, on a $\tau(p) \leq y < \tau(p + 1)$ quel que soit y.
Au rang suivant, on a pour $y = \tau(p + 1) + 1$, $\tau(p + 1) \leq y < \tau(p + 2)$.
Donc P(p) est vraie. Récurrence établie.
@blo yhg : En fait, je commence à peine la leçon sur le dénombrement (j’en suis encore qu’à la première sous-partie) donc j’y reviendrai plus tard. 
Mais j’y reviendrai, hein. 
Tu as terriblement mal posé ton assertion. Déjà parce qu’elle ne dépend pas de $p$ et en plus parce que dans ta preuve, ce qui t’intéresse c’est pas l’existence de $y$ mais de $p$.
En effet, c’est bien $P(y)$ que l’on cherche à montrer puisque pour chaque naturel $y$ on veux exhiber un naturel $p$.
Non, ta proposition ne dépend pas non plus de $y$ puisque tu l’as mutifiée avec le quantificateur $\forall$.
Et si je pose $y \in \mathbf N$ et que j’ai l’assertion $P(y) \equiv \exists p \in \mathbf N : \tau(p) \leq y < \tau (p + 1)$, je peux raisonner par récurrence pour montrer que l’assertion est vraie quel que soit y?
@Holosmos Si j’ai bien compris Ozmox a raison dans sa démonstration (celle de départ), puisque toute suite $(a_n)$ à valeur dans $\mathbf{Z}_{ \geq 0 }$ strictement croissante tel que $a_0 = 0$, vérifie $\bigcup_{i = 0}^{\infty} [\![a_i, a_{i+1} ]\!] = \mathbf{Z}_{\geq 0}$ donc on a bien l’existence…
@Holosmos Si j’ai bien compris Ozmox a raison dans sa démonstration (celle de départ), puisque toute suite $(a_n)$ à valeur dans $\mathbf{Z}_{ \geq 0 }$ strictement croissante tel que $a_0 = 0$, vérifie $\bigcup_{i = 0}^{\infty} [\![a_i, a_{i+1} ]\!] = \mathbf{Z}_{\geq 0}$ donc on a bien l’existence…
Certains arguments étaient bons, mais la démonstration fausse. Par ailleurs la question porte plus actuellement sur l’unicité dans la décomposition $p=n+k$ que l’existence.
Et si je pose $y \in \mathbf N$ et que j’ai l’assertion $P(y) \equiv \exists p \in \mathbf N : \tau(p) \leq y < \tau (p + 1)$, je peux raisonner par récurrence pour montrer que l’assertion est vraie quel que soit y?
Techniquement il ne faut pas poser $y\in \mathbf N$. En revanche tu peux dire que $y$ est astreinte aux entiers. Parce que poser $y\in \mathbf N$ signifie fixer sa valeur sur un entier, et c’est pas ce que tu veux.
De toute façon, ça tu l’avais déjà compris qu’il existe $p$ te donnant l’encadrement. Ton problème actuellement c’est de justifier l’égalité $p = n+k$.
Ok, du coup j’ai modifié mon raisonnement par récurrence pour montrer l’existence de p et j’ai exhiber ce p :
Soit $y \in \mathbf N$. Soit $P(y)$ l’assertion $\exists p \in \mathbf N : \tau(p) \leq y < \tau(p + 1)$.
Par récurrence :
Init. Pour y = 0, p = 0 convient.
Induction. Supposons $P(y)$ vraie i.e. on a $p \in \mathbf N$ tel que $\tau(p) \leq y < \tau(p + 1) \iff \dfrac{p(p+1)}{2} \leq y < \dfrac{(p + 1)(p + 2)}{2} \iff p^2 + p - 2y \leq 0 \space \text{et} \space p^2 + 3p + 2(1 - y) > 0 \iff p \leq \dfrac{-1 + \sqrt{1 + 8y}}{2} < p + 1$ d’où $p = \left\lfloor \dfrac{-1 + \sqrt{1 + 8y}}{2} \right\rfloor$.
De ce fait, au rang suivant, $p = \left\lfloor \dfrac{-1 + \sqrt{1 + 8(y + 1)}}{2} \right\rfloor$ convient.
Donc $P(y) \implies P(y + 1)$.
Ainsi, P(p) est vraie, récurrence établie.
La récurrence ne sert pas à grand chose ici 
Soit $y \in \mathbf N$.
Même remarque que précédemment ....
Soit $P(y)$ l’assertion $\exists p \in \mathbf N : \tau(p) \leq y < \tau(p + 1)$.
Par récurrence :
Init. Pour y = 0, p = 0 convient.
Induction. Supposons $P(y)$ vraie i.e. on a $p \in \mathbf N$ tel que $\tau(p) \leq y < \tau(p + 1) \iff \dfrac{p(p+1)}{2} \leq y < \dfrac{(p + 1)(p + 2)}{2} \iff p^2 + p - 2y \leq 0 \space \text{et} \space p^2 + 3p + 2(1 - y) > 0 \iff p \leq \dfrac{-1 + \sqrt{1 + 8y}}{2} < p + 1$ d’où $p = \left\lfloor \dfrac{-1 + \sqrt{1 + 8y}}{2} \right\rfloor$.
De ce fait, au rang suivant, $p = \left\lfloor \dfrac{-1 + \sqrt{1 + 8(y + 1)}}{2} \right\rfloor$ convient.
Donc $P(y) \implies P(y + 1)$.
Ainsi, P(p) est vraie, récurrence établie.
Pourquoi pas .... mais quelle longueur pour si peu !
Ton premier raisonnement consistant à dire que la suite était strictement croissante suffisait presque. Comme l’a dit @Universite, rajoute le fait que pour $p=0$ on a $0$ et tu peux conclure avec moins de calcul inutile. C’était ce détail là que j’attendais.
Comme l’a dit @Universite, rajoute le fait que pour $p = 0$ on a $0$ et tu peux conclure avec moins de calcul inutile. C’était ce détail là que j’attendais.
Ah… Oui… Ouups… 
Pour l’existence de p = n + k :
$y = \tau(n + k) + k \in [[\tau(n + k), \tau(n + k + 1)[[$ or $\forall y \in \mathbf N, \exists ! p \in \mathbf N : y \in [[\tau(p), \tau(p + 1)[[$ donc $n + k = p$.
Ensuite on a $y = f(n, k) = \tau(n + k) + k \iff k = y - \tau(n + k)$.
Or, $k \mapsto \tau(n + k)$ est injective donc pour $k' \in \mathbf N$, on a $y + \tau(n + k) = y + \tau(n + k') \implies \tau(n + k) = \tau(n + k') \implies k = k'$.
Ainsi, $k$ est unique et il en va de même pour $n = p - k$ (puisque $p$ est unique).
De ce fait, f est bien bijective.
Doucement sur le flood … ça devient pénible à lire pour ceux qui ne suivent pas minute par minute.
$y = \tau(n + k) + k \in [[\tau(n + k), \tau(n + k + 1)[[$
C’est quoi $n$ et $k$ ? Tu les introduis comment ici ?
or $\forall y \in \mathbf N, \exists ! p \in \mathbf N : y \in [[\tau(p), \tau(p + 1)[[$
Tu n’as pas démontré l’unicité de $p$ jusque là, seulement l’existence. Il n’y a qu’un petit truc à dire en plus pour avoir l’unicité mais tu ne l’as pas encore formulé correctement.
donc $n + k = p$.
La validité de ta phrase dépend maintenant de la façon dont tu introduis $n$ et $k$. J’ai l’impression que tu es parti du principe que $y= \tau(n+k)+k$ mais c’est la conclusion que tu cherches à atteindre et c’est pas dans les hypothèses données …
Or, $k \mapsto \tau(n + k)$ est injective
Pourquoi ? C’est pas justifié.
C’est quoi $n$ et $k$ ? Tu les introduis comment ici ?
A ce stade de la preuve, on est en train de montrer que f est surjective.
Donc je suppose $y = f(n, k) = \tau(n + k) + k$ et je cherche à exhiber une expression de n et de k en fonction de y (on veux montrer que chaque naturel y a deux antécédents par f).
Or, f(n, k) est compris entre $\tau(p)$ et $\tau(p + 1)$.
J’ai démontré l’existence de p plus loin, donc $n + k = p$.
Quant à l’unicité, procédons par l’absurde :
Pour $y \in \mathbf N$, supposons qu’il existe $(p, p') \in \mathbf N^2$ tel que $y \in [[ \tau(p), \tau(p + 1)[[$ et $y \in [[ \tau(p'), \tau(p' + 1)[[$.
Donc $p = p'$.
Sinon, pour s’affranchir de tout plein de calculs et simplement montrer que $\mathbf N^2$ et $\mathbf N$ sont en bijection, le mieux c’est de montrer que n + k = p comme au-dessus (sans parler de y) et de dire que l’ensemble des n + k = p a des éléments de la forme (p - a, a) où a est compris entre 0 et p. Bref, rebondir sur la preuve de @Universite.
Je ne comprend pas pourquoi ton raisonnement PA, tu aboutis à $y < p'$ ? et à $y \geq p'+1$ ? Sinon au lieu de faire tout ça tu peux tout simplement dire que chacun des intervalles $[\![\tau(p), \tau(p+1) -1 ]\!]$ est disjoint, leur intersection est donc nulle, et on a bien l’unicité.
J’ai mal écrit pardon, c’est $y < \tau(p')$ et $y \geq \tau(p' + 1)$.
Sinon au lieu de faire tout ça tu peux tout simplement dire que chacun des intervalles $[[τ(p),τ(p+1)−1]]$ est disjoint, leur intersection est donc nulle, et on a bien l’unicité.
Hum, je ne comprend pas.
Si on a une suite strictement croissante d’entiers $a_0, a_1, ..., a_n$, et bien il est évident que chacun des intervalles de la forme $[\![a_i, a_{i+1} -1]\!]$ est disjoint des autres. Donc par définition un élément ne peut pas appartenir à deux intervalles disjoints.
Oui mais pourquoi $[\![a_i, a_{i+1} -1]\!]$ et pas $[\![a_i, a_{i+1}]\!]$?
A ce stade de la preuve, on est en train de montrer que f est surjective.
Donc je suppose $y = f(n, k) = \tau(n + k) + k$ et je cherche à exhiber une expression de n et de k en fonction de y (on veux montrer que chaque naturel y a deux antécédents par f).
Non, malheureux ! Si tu supposes que $y=f(n,k)$, ça signifie que tu as déjà supposé la surjectivité !
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte
