Une récurrence (un peu) trop simple

a marqué ce sujet comme résolu.

Bonjour, je suis coincé avec une récurrence assez atypique. En fait, elle semble tellement simple qu’elle s’apparenterait plus à un axiome. La voici :

Montrer que tout entier naturel différent de 00 possède un unique prédécesseur.

Prérequis

On note N\mathbf N l’ensemble des entiers naturels qui vérifie les axiomes de Peano :

  1. 0∈N0 \in \mathbf N
  2. ∀n∈N, σ(n)∈N\forall n \in \mathbf N, \ \sigma(n) \in \mathbf N (σ(n)\sigma(n) est le succésseur de nn)
  3. ∀n∈N, σ(n)≠0\forall n \in \mathbf N, \ \sigma(n) \neq 0
  4. ∀n,m∈N, σ(n)=σ(m)  ⟹  n=m\forall n, m \in \mathbf N, \ \sigma(n) = \sigma(m) \implies n = m
  5. Soit P(n)\mathcal P(n) une propriété dépendant de nn, nous avons (principe de récurrence) : [P(0)  et  P(n)  ⟹  P(σ(n))]  ⟹  ∀n∈N, P(n)[\mathcal P(0) \ \ \text{et} \ \ \mathcal P(n) \implies \mathcal P(\sigma(n))] \implies \forall n \in \mathbf N, \ \mathcal P(n)

Notion de prédécesseur

Dire qu’un entier nn possède un prédécesseur revient en fait à dire qu’il est le succèsseur d’un entier naturel mm.

Ma preuve

Soit P(n)\mathcal P(n) la propriété qui indique que soit nn est égale à 00 ou soit il possède un prédécesseur.

  • P(0)\mathcal P(0) est vrai car 0=00 = 0 ;
  • Supposons que P(n)\mathcal P(n) soit vraie… Bah en fait σ(n)\sigma(n) est le succésseur de nn (donc son prédécesseur est nn) et ce peu importe que P(n)\mathcal P(n) soit vraie ou non…

Du coup, récurrence établie…? Comment une récurrence où l’hypothèse n’est pas utilisée peut être valide ?

Le résultat est tellement basique que ça en devient difficile à rédiger.

L’unicité quant à elle s’explique par l'axiome 4 et ne semble pas poser de problème ici.

Une aide me serait vraiment utile.

+0 -0

Salut,

Je pense qu’on te demande exactement ce que tu dis à la fin: prouver l’unicité. Avec ton P(n) tu prouves juste que tout n != 0 a un prédécesseur, ce qui n’a effectivement pas besoin de récurrence…

(Et oui la preuve ne devrait pas être très compliquée à la fin ;) )

+2 -0

Je dis ça par ressenti, mais ça ne ressemble pas à quelque chose qui devrait être prouvé par l’absurde ?

Moté

Ah oui, j’ai oublié de préciser que c’est un exercice tiré du livre Analysis I par Terrence Tao.

Il s’agit, plus exactement, de cet énoncé :

Il est donc indiqué d’utiliser un raisonnement par récurrence (ou induction). De plus, les quelques conversations que j’ai pu trouver au sujet de cet exercice sur StackExchange font mention d’un raisonnement par récurrence.

Mais y a-t-il un raisonnement à avoir si ce n’est tirer conclusion directement des axiomes ?

+0 -0

Les deux preuves (existence et unicite) de ton message initial sont celles attendues, a mon avis. C’est effectivement pas standard de ne pas utiliser l’hypothese de recurrence (mais en meme temps c’est pas standard de prouver ce genre de choses).

+0 -0

Supposons que P(n) soit vraie… Bah en fait σ(n) est le succésseur de n (donc son prédécesseur est n) et ce peu importe que P(n) soit vraie ou non…

Tu n’as pas montré que si m∈N∖{0}m\in \mathbb N\setminus\{0\} alors m=σ(n)m = \sigma(n), c’est bien tout le problème.

T’es passé à côté de l’exercice, car tu n’as pas correctement lu les axiomes. Ça n’est pas trivial à partir des axiomes que N={0}∪{σ(n),  ∀n}\mathbb N = \{0\}\cup\{\sigma(n),\; \forall n\}

En fait, ici, il s’agit d’utiliser l’axiome 5. Qui est bien ce qu’on appelle principe d’induction en général, mais prend un sens intéressant dans ce contexte

+1 -1

Merci pour ton retour @Holosmos. J’ai donc tenté une preuve un peu plus détaillée :

Existence

Soit P(n)\mathcal P(n) la propriété suivante :

n=0  ou  ∃m∈N : σ(m)=nn = 0 \ \ \text{ou} \ \ \exists m \in \mathbf N \, : \, \sigma(m) = n

Et on appelle l’entier naturel mm le prédécesseur de nn.

  • P(0)\mathcal P(0) est vraie car 0=00 = 0 ;
  • Supposons que P(n)\mathcal P(n) soit vraie, alors :

Nous savons d’après l'axiome n°3 que σ(n)≠0\sigma(n) \neq 0, il s’agit donc de montrer que σ(n)\sigma(n) possède un prédécesseur.

  • Si n=0n = 0 alors σ(n)=σ(0)=1\sigma(n) = \sigma(0) = 1 donc σ(n)\sigma(n) possède bien un prédécesseur qui est 00 ;

  • Sinon, alors on note mm le prédécesseur de nn et on a :

    σ(n)=σ(σ(m))\sigma(n) = \sigma(\sigma(m))

    donc σ(n)\sigma(n) possède bien un prédécesseur qui est σ(m)\sigma(m).

Ainsi par l'axiome n°5 nous avons ∀n∈N, P(n)\forall n \in \mathbf N, \ \mathcal P(n)

Unicité

Soit nn un entier naturel et soit m,lm, l deux prédécesseurs de nn. Ainsi, nous avons :

σ(m)=σ(l)=n\sigma(m) = \sigma(l) = n s’en suit m=lm = l par l'axiome n°4.

+0 -0

C’est mieux.

Tu peux encore progresser sur la rédaction.

En l’occurrence tu as écris de façon trop alambiquée la preuve de P(σ(n))\mathcal P(\sigma(n)), alors que comme tu l’as remarqué, cette proposition est immédiatement vraie car par définition nn est prédécesseur de σ(n)\sigma(n).

Donc il s’agit de mieux lire l’axiome 5.

  1. Soit P(n)\mathcal P(n) une propriété dépendant de nn, nous avons (principe de récurrence) : [P(0)  et  P(n)  ⟹  P(σ(n))]  ⟹  ∀n∈N, P(n)[\mathcal P(0) \ \ \text{et} \ \ \mathcal P(n) \implies \mathcal P(\sigma(n))] \implies \forall n \in \mathbf N, \ \mathcal P(n)

Pour appliquer l’axiome 55 il faut :

  • vérifier P(0)\mathcal P(0) (ce que tu as fait correctement)
  • vérifier P(n)  ⟹  P(σ(n))\mathcal P(n) \implies \mathcal P(\sigma(n)) et c’est cette implication que tu devrais mieux rédiger.

L’implication P(n)  ⟹  P(σ(n))\mathcal P(n) \implies \mathcal P(\sigma(n)) est vraie dès que P(σ(n))\mathcal P(\sigma(n)) est vraie, et c’est effectivement ce que tu avais remarqué.

Donc pour montrer P(n)  ⟹  P(σ(n))\mathcal P(n) \implies \mathcal P(\sigma(n)) tu te contentes de justifier que P(σ(n))\mathcal P(\sigma(n)) est vraie.

Ensuite, l’axiome 5 te permet d’en conclure P(n)\mathcal P(n) pour tout n∈Nn\in\mathbb N, qui est bien l’énoncé que tu voulais.

Sur une note plus personnelle j’aimerais expliquer pourquoi je trouve cet exercice assez joli et intéressant.

C’est pas du tout clair a priori pourquoi les axiomes de Peano permettent bien d’identifier l’ensemble N\mathbf N que chacun connaît. Cet ensemble, on le connaît avant d’aborder les axiomes, donc ce n’est pas une question facile en principe de vérifier que les axiomes sont les bons.

Notamment, les axiomes expriment essentiellement que l’ensemble délimité, disons AA pour l’instant (le but est de justifier A=NA=\mathbf N), est défini par induction 0∈A0\in A et σ(n)∈A\sigma(n)\in A dès que n∈An\in A.

Mais du coup, et c’est tout le but de l’axiome 5, il faut arriver à écarter un cas de figure où on aurait, par exemple 12∈A\frac 12\in A, et tous les n+12∈An+\frac 12 \in A. Pour écarter ça, il faut arriver à cibler le fait que non seulement σ(n)∈A\sigma(n)\in A quand n∈An\in A mais n=σ(k)n=\sigma(k) si n∈An\in A pour un k∈Ak\in A, et c’est beaucoup plus fin. Donc l’axiome 5, il faut vraiment le lire comme un façon de passer d’une propriété sur les {σ(n)}∪{0}\{\sigma(n)\}\cup \{0\} à une propriété sur tout AA.

Et là intervient un principe en logique formelle : si toute proposition vraie sur un ensemble AA est vraie sur un ensemble BB alors A=BA=B. Donc en fait l’axiome 5 dit qu’on peut identifier formellement {σ(n)}∪{0}\{\sigma(n)\}\cup\{0\} avec AA. Or, {σ(n)}∪{0}\{\sigma(n)\}\cup\{0\} est beaucoup plus proche de l’intuition qu’on a de N\mathbf N, et donc on se rapproche fortement de A=NA=\mathbf N.

+4 -0

Merci pour ta réponse Holosmos ! L’axiome est en effet bien plus clair expliqué ainsi.

Sinon, le problème revient-il en fait à montrer que N={σ(n)}∪{0}\mathbf N = \{\sigma(n)\} \cup \{0\} ? Cela me semble plutôt logique d’après l’énoncé pour tout entier naturel, soit il est égal à 0, soit c’est un successeur.

Cela permet-il donc d’exclure les éléments parasites : par exemple

N≠{0, 1, 1, 2, 2, 3, … }\mathbf N \neq \{0, \, 1, \, \sqrt{1}, \, 2, \, \sqrt{2}, \, 3, \, \dots\}

Si on définit les entiers naturels "que l’on connaît" ainsi :

1:=σ(0), 2:=σ(1), 3:=σ(2), …1 := \sigma(0), \ 2 := \sigma(1), \ 3 := \sigma(2), \ \dots

alors puisque N={σ(n)}∪{0}\mathbf N = \{\sigma(n)\} \cup \{0\} les racines carrées ne sont jamais atteintes.

Cela doit se montrer plus formellement par induction mais c’est l’idée, j’imagine.

+1 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

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