Démonstration prop. construction de N

[kNz]

Bonjour à tous,

Aujourdh'ui j'ai eu un cours sur la construction de |N, et on a démontré quelques trucs que j'ai pas bien compris.

Par exemple, ça (je recopie texto mon cours) :

Pour tous (n,p,r) dans |N³, n+(p+r) = (n+p)+r

On raisonne par récurrence sur r dans |N.

Pour r=0
n+(p+0)=n+p
(n+p)+0=n+p

On suppose n+(p+r)=(n+p)+r pour r dans |N.
On veut le démontrer pour r+1.

n+(p+s(r)) (1)
= n+(s(p+r)) (2)
= s((n+p)+r) (3)
= (n+p)+s(r) (4)

Voilà, ça s'arrête là.

Et je ne comprends pas comment on passe de (2) à (3), si quelqu'un voulait bien m'expliquer

Merci.

A+
-----

[Gwyddon]

C'est peut-être bête, mais c'est quoi s(r) dans la démo ?

Sinon je propose :

n+(p+(r+1)) = n+((p+r)+1) (j'utilise l'hypothèse de récurrence sur 1, il faudra donc vérifier à la main le cas r=1)

n+(p+(r+1)) = (n+(p+r)) + 1 (toujours pareil, encore l'HR avec r=1)
=((n+p)+r)+1 (l'HR sur r)
=(n+p)+(r+1) gagné

[kNz]

D'accord merci, je crois que j'ai un problème, je ne vois pas pourquoi on a le droit d'utiliser l'hypothèse de récurrence... J'ai l'impression d'utiliser un truc que j'veux démontrer, que je tourne en rond.

s c'était une injection de N dans N, s(r) est le successeur de r.

Merci.

[Gwyddon]

Parce que la bonne formulation est "on suppose l'hypothèse de récurrence [celle que tu as écrite] vraie pour tout entier p inférieur ou égal à r, étudions ce qui se passe au rang r+1"

[A voir en vidéo sur Futura]

[kNz]

Ah d'accord merci Gwyddon, je commence à comprendre, on utilise la propriété qu'on a prouvé pour le rang n, pour voir ce qui se passe plus loin en gros... très gros...

Merci, vraiment, j'avais pas vu le chapitre de récurrence en première et premier cour de terminale, le prof s'en sert..

Bref, re-merci, je reviendrais peut être sur ce fil sur le même sujet demain,

A+

[martini_bird]

Salut,

une rédaction complète s'écrirait ainsi :

Soit à démontrer que pour tout triplets d'entiers (n,p,r), n+(p+r) = (n+p)+r. Procédons par récurrence sur r.

Fondation

Pour r=0,
n+(p+0)=n+p,
(n+p)+0=n+p,
donc n+(p+0)=(n+p)+0.

Hérédité

On suppose que n+(p+r)=(n+p)+r pour un certain entier r.
On veut démontrer que la propriété est vraie pour s(r)=r+1, càd que n+(p+s(r))=(n+p)+s(r). Or :

n+(p+s(r))
= n+s(p+r) ..... (x+s(y)=s(x+y) (*) ; à démontrer si ça n'a pas été fait)
= s(n+(p+r)) ..... (même propriété (*) utilisée)
= s((n+p)+r) ..... (utilisation de l'hypothèse de récurrence n+(p+r) = (n+p)+r.)
= (n+p)+s(r) ..... (propriété (*) lue dans l'autre sens)

Conclusion
Pour tout triplet d'entiers (n,p,r), on a la relation d'assiocativité n+(p+r) = (n+p)+r.

________

La démo que tu donnes dans ton premier message est gravement incomplète et il y a des erreurs de raisonnement !

Cordialement.

[Gwyddon]

En gros on a la même, martini ?

Il faut donc démontrer la proposition pour l'entier r=1.

[kNz]

Salut,

Merci pour la démo complète

Mais on a vraiment besoin de démontrer pour r=1 ? Le cas r=0 ne suffit pas ?

[Gwyddon]

Oui tu es obligé puisque tu t'en sers dans la démo. Or si tu n'as pas montré l'amorce pour ce cas, tu n'as rien montré du tout

[kNz]

ReBonjour,

J'ai une autre propriété à démontrer, enfin, démontrée dans mon cours, mais que je ne comprends pas très bien non plus.

Soit à démontrer que pour tout doublet d'entiers (n,p), n + p = p + n. Procédons par récurrence sur n.

Montrons que : p + 0 = 0 + p

Procédons par récurrence sur p.

pour p = 0, on a bien 0 + 0 = 0 = 0 + 0

On suppose que pour un certain entier de rang p, p + 0 = 0 + p.

On veut démontrer que la propriété est vraie pour s(p) = p+1, çàd que s(p) + 0 = 0 + s(p), or :

s(p) + 0
= s(p+0) (propriété (1) admise dans la définition de l'addition que l'on m'a donné)
= s(0+p) (utilisation de l'hypothèse de récurrence sur p)
= 0 + s(p) (1)

On a donc pour tout entier p, p + 0 = 0 + p.

On suppose que pour un certain entier de rang n, n + p = p + n.

On veut démontrer que la propriété est vraie pour s(n) = n+1, çàd que s(n) + p = p + s(n), or :

s(n) + p
= s(n+p) (1)
= s(p+n) (utilisation de l'hypothèse de récurrence sur n)
= p + s(n) (1)

On a donc bien pour tout doublet d'entiers (n,p), n + p = p + n

_________________

C'est moi qui ai fait cette démo (bien sûr en prenant pour exemple la rédaction de martini), donc j'aimerais bien savoir si elle présente des incohérences..

Merci beaucoup.

A+

[kNz]

Oui tu es obligé puisque tu t'en sers dans la démo. Or si tu n'as pas montré l'amorce pour ce cas, tu n'as rien montré du tout

Excuse moi je ne te suis pas on s'en sert où ?

[Gwyddon]

Chez martini, il faut que tu démontres ça :

(x+s(y)=s(x+y) (*) ; à démontrer si ça n'a pas été fait)

Chez moi, il faut que tu démontres ça :

p+(r+1)) = (p+r)+1

Donc il faut bien démontrer un truc en plus

[martini_bird]

Salut,

En gros on a la même, martini ?

Oui, la propriété (*) x+s(y)=s(x+y) étant le cas r=1 : x+(y+1)=(x+y)+1.

J'ai simplement rédigé complètement pour donner un exemple de rédaction pour kNz, qui a su la réutiliser avec brio !

Cordialement.

EDIT : croisement.

[kNz]

Ah oui d'accord, mais ça on me l'a donné dans la définition de l'addition, donc je peux l'utiliser sans le démontrer de mon côté ?

Et puis j'vois pas comment on le démontre

edit : oki merci, j'vais voir si j'en poste d'autres pour m'entraîner.

[kNz]

Re,

Bon j'ai un p'tit exo, que j'poste vite fait :

Posons 2 = s(1) ; 3 = s(2) ; 4 = s(3)
Montrez que 2+2=4

2 + 2
= 2 + s(1)
= s(2+1)
= s(2+s(0))
= s(s(2+0))
= s(s(2))
= s(3)
= s(4)

Voilà.

[kNz]

Je m'entraîne,

Soit à démontrer que pour tout doublet d'entiers (n,p), n * p = p * n

Raisonnons par récurrence sur n.

Fondation

Pour n = 0, on a 0 * p = 0 = p * 0
On a donc bien n * p = p * n pour n = 0.

Hérédité

On suppose que pour un certain entier de rang n, n* p = p * n

On veut démontrer que la propriété est vraie pour s(n) = n+1 càd s(n) * p = p * s(n), or :

p * s(n)
= (p*n) + p (définition de la multiplication (1))
= (n*p) + p (hypothèse de récurrence)
= (n+1) * p (distributivité)
= s(n) * p

Est-ce que c'est correct, j'ai le droit d'utiliser la distrubitivité ??

Merci.

[kNz]

Soit à démontrer que N est bien ordonné, ie toute partie non vide de N admet un plus petit élément.

On pose P(n) : toute partie de N qui admet au moins un élément inférieur à n admet un plus petit élément.

Montrons que pour tout entier n P(n) est vraie par récurrence sur n.

Fondation

P(0) est vraie car si une partie de N contient 0 elle admet un plus petit élément qui est 0.

Hérédité

On suppose que pour un certain entier de rang n, P(n) est vraie.
On cherche à démontrer que la propriété est vraie pour s(n) = n+1, or :

n+1 = n+s(0) = s(n+0) = s(n) >= n

Donc la partie de N qui contient n+1 admet un plus petit élément inférieur à n+1, qui est n.

Donc P(n+1) est vraie.

_______________

Si quelqu'un a le courage de corriger tout ça, je l'en remercie grandement !

A+

[Gwyddon]

Ta dernière démonstration est fausse.

Pour démontrer cette propriété, il faut raisonner par l'absurde il me semble

[kNz]

Ta dernière démonstration est fausse.

:'(

A quel niveau ? désolé je vois pas

A+

edit : ah oui déjà j'ai fait un truc très con, j'ai démontré que n+1 = s(n) alors que j'l'admettais, bref je me perds un peu sur celle là ...

[Gwyddon]

Démontrer P(n+1) signifie démontrer cela :

"Soit une partie quelconque de N admettant au moins un élément inférieur à n+1. Alors elle admet un plus petit élément".

Ton enchaînement logique :

Donc la partie de N qui contient n+1 admet un plus petit élément inférieur à n+1, qui est n.

Donc P(n+1) est vraie.

Ne démontre rien, puisque tu n'as pas précisé "soit A une partie quelconque de n admettant un au moins un élément inférieur à n+1", et tu n'as jamais utilisé l'hypothèse de récurrence ; de plus qu'est-ce qui te permet d'affirmer que n est le plus petit élément de la partie de N que tu as considérée (sans même l'expliciter) ?

A bien y réfléchir, tu pourrais y arriver, mais il te manque plein de choses.

[kNz]

Argh oui, déjà :

Donc la partie de N qui contient n+1 admet un plus petit élément inférieur à n+1, qui est n.

est faux, je dois mettre :

Donc la partie de N qui contient n+1 admet un plus petit élément inférieur à n+1, puisqu'elle admet au moins un élément inférieur à n+1 qui est n.

Sinon,

Démontrer P(n+1) signifie démontrer cela :

"Soit une partie quelconque de N admettant au moins un élément inférieur à n+1. Alors elle admet un plus petit élément".

Je vois mon erreur, en fait, je ne démontre rien, je dois démontrer l'implication...

J'ai du mal avec celle là, je réfléchis un peu mais j'promets rien.

[kNz]

Vraiment je vois pas là, une petite piste ? une toute petite s'iouplaît

Merci,

A+

[Gwyddon]

Cool, tu as compris ton erreur, c'est un grand pas en avant

Maintenant, la suite

[Gwyddon]

Commence par poser clairement les choses :

soit A une partie de N admettant au moins un élément inférieur à l'entier p=n+1.

Tu distingues deux cas :

_ soit la partie A contient deux éléments. Bah c'est fini, elle contient bien un plus petit élément puisque c'est une partie finie (tu peux même l'exhiber )

_ soit la partie A contient plus de deux éléments, donc au moins 3. Et tu sais qu'elle contient au moins un élément inférieur à n+1. Comment peux-tu relier ça à P(n) (ie voir si cette partie A n'aurait pas au moins un élément inférieur à l'entier n) ?

[kNz]

Ba si elle n'a pas d'éléments inférieurs à l'élément inférieur à n+1, càd n, elle admet un plus petit élément, mais sinon ...

J'ai l'impression de complètement perdre pied, désolé ...

[Gwyddon]

Bah sinon... tu continues ta phrase, cela signifie qu'elle a au moins un élément inférieur à l'entier n non ? (d'ailleurs dans le cas 2, c'est toujours le cas si tu y réfléchis bien vu que la partie A possède au moins 3 éléments, donc au pire elle contient n-1,n et n+1 uniquement). Donc tu fais quoi maintenant, si tu regardes l'intitulé de P(n) ?

[kNz]

Désolé, je m'étais absenté..

J'essaie de tout reprendre..

On suppose que P est vérifiée pour un certain entier de rang n.
On veut démontrer que la propriété est vraie pour n+1.

Soit la partie A contient seulement deux éléments, auquel cas A admet un minimum qui est n.

Soit la partie A contient plus de deux éléments, et on distingue encore deux cas :

• Si elle n'a pas d'éléments inférieurs à n, alors elle admet un minimum qui est n.
• Si elle admet au moins un élément inférieur à n, alors d'après l'hypothèse de récurrence, P(n+1) est vraie.

[Gwyddon]

Dans le deuxième cas, il n'y a pas de distinction à faire, il y a forcément un élément inférieur à n puisque ta partie A contient au moins trois éléments ...

Mis à part cette faute de raisonnement, le reste est correct.

[kNz]

Exact, je considérais que n n'était pas forcément le plus grand élément de la partie A mais ça ne change rien, donc en effet il n'y a pas de distinction à faire, merci beaucoup pour ton suivi Gwyddon !

[kNz]

Bonjour !

On souhaite montrer qu'il n'existe pas d'entiers strictement compris entre n et s(n).

On suppose qu'il existe un entier compris entre en n et s(n), on peut alors écrire :

s(n) = n + r

On pose r' = s^-1(r), çad s(r') = r.

On a donc :

s(n)
= n + s(r')
= s(n+r')

Or, il est nécessaire que r' = 0, d'où r = 1, et on sait que s(n) = n + 1, donc il n'existe alors pas d'entiers strictement compris entre n et s(n).

C'est correct ou pas ? J'ai pas la même démo dans mon cours c'est pour ça,

Dites le si j'fais ch*** avec toutes mes démos hein ?