Démonstration par induction

[invitea821f6eb]

Bonjour,

Je suis actuellement en train d'étudier la logique propositionnelle, et je suis tombée sur une partie sur la démonstration par induction.
Je pense avoir compris le principe dans l'ensemble, mais lorsque je tente de faire l'exercice proposé, je bloque.

Voici l'énoncé :

On se situe dans l'ensemble Nat définit comme étant le plus petit ensemble tel que 0 ∈ Nat et si n ∈ Nat, alors suc(n) ∈ Nat.
Note: suc(n) est une autre manière d’écrire n + 1.

On dispose des axiomes suivants :
Cas Zéro [eq. Z] : 0 + m = m
Cas Successeur [eq. S] : suc(n) + m = suc(n + m)

On a également démontré précédemment le prédicat suivant :
∀n.(n + 0 = n)

L'exercice consiste à démontre la commutativité de l'addition, autrement dit, que ∀n.∀m.(n + m = m + n)

Voilà où j'en suis rendu :

1. Identifier le prédicat -> P(n) ≡ (n + m = m + n)
2. Preuve pour le cas de base -> P(0), donc: 0 + m = m + 0 (oui, par eq. Z + prédicat précédent)
3. Preuve d'hérédité -> Hypothèse d'induction : n + m = m + n
montrer que suc(n) + m = m + suc(n)
suc(n) + m = suc(n + m) (par eq. S)
suc(n + m) = suc(m + n) (par eq. H)
suc(m + n) = suc(m) + n (par eq. S)

Sauf que voilà, arrivé là, je suis bloqué, tout simplement...
Je n'attends pas que l'on me donne la réponse, ce serait dommage, et pour autant que je sache ce n'est pas la politique du forum.
Seulement dans un premier temps, j'aimerais connaître mon erreur... Est-ce que l'erreur est vraiment située dans mon raisonnement, est-ce que j'ai oublié quelque chose ? Est-ce qu'il manquerait un axiome que j'aurais zappé ?

Merci d'avance,
R.


EDIT : Au passage, voici un extrait du cours que je lis :Que signifie le caractère ⋈ ?
-----

[Médiat]

Bonjour,

Merci de lire ceci : http://forums.futura-sciences.com/ma...s-jointes.html.

J'ai modifié votre lien et l'ai remplacé par un image chez nous.

Médiat, pour la modération


Dans votre exemple ⋈ ne signifie rien de particulier, et comme justement vous ne pouvez pas le ramener aux règles de formation de FORM, c'est que la proposition n'appartient pas à FORM.

Votre démonstration n'est pas fausse, elle est juste incomplète ; je vous suggère de démontrer un lemme préalable : suc(n+m) = n + suc(m), par une récurrence sur n.

[invitea821f6eb]

Navré pour l'image, je tâcherai de m'en souvenir.

Pour le prédicat, ça donne ça, non ?

1. P(n) ≡ suc(n + m) = n + suc(m)
2. P(0), donc: suc(0 + m) = 0 + suc(m) (Par eq.Z)
3. Hypothèse d'induction : suc(n + m) = n + suc(m)
montrer que suc(suc(n) + m) = suc(n) + suc(m)
suc(suc(n) + m) = suc(suc(n + m)) (par eq. S)
suc(suc(n + m)) = suc(n + suc(m)) (par eq. H)
suc(n + suc(m)) = suc(n) + suc(m) (par eq. S)

Du coup ma démonstration précédente devient

1. Identifier le prédicat -> P(n) ≡ (n + m = m + n)
2. Preuve pour le cas de base -> P(0), donc: 0 + m = m + 0 (oui, par eq. Z + prédicat précédent)
3. Preuve d'hérédité -> Hypothèse d'induction : n + m = m + n
montrer que suc(n) + m = m + suc(n)
suc(n) + m = suc(n + m) (par eq. S)
suc(n + m) = suc(m + n) (par eq. H)
suc(m + n) = m + suc(n) (par Prédicat précédent)

Merci beaucoup.