récurrence

Voltaire a écrit:Dans la formulation supposons qu'il existe k tel que P(k) vrai, démontrons P(k +1) vrai, P (k +1) n'est démontré que pour de tels k. Si aucun n'existe, P(k + 1) n'est jamais démontré.
C'est très différent de dire que, pour tout k, P(k) vrai entraine P(k + 1) vrai, qui ne suppose pas l'existence d'un k tel que P(k) soit vrai (la ponctuation est essentielle).

Je suis bien d'accord : dans le premier cas, P(k+1) n'est jamais démontré, et effectivement pour tout entier k il est faux. Mais cela n'empêche pas la propriété d'être héréditaire : pour tout k, P(k)=>P(k+1) est valide. Et démontrer l'implication pour les entiers k pour lesquels P(k) est vraie suffit pour la démontrer en général (pour les entiers k tel que P(k) est faux, l'implication est évidemment vraie).

Si une propriété est héréditaire (c'est à dire si on arrive à prouver : pour tout k, P(k) vrai entraine P(k+1) vrai), il y a deux possibilités :
- soit on arrive à l'initialiser pour une certaine valeur disons k0, alors elle est vraie pour tout les entiers supérieurs ou égaux à ce k0
- soit on n'arrive pas à l'initialiser, et dans ce cas on ne sait rien du tout sur la propriété. Si on veut démontrer qu'elle est fausse, il faut le faire "à la main" ou alors démontrer que (non P) est héréditaire ... (voir mon exemple ci dessus)

Voltaire a écrit:Si une propriété est héréditaire (c'est à dire si on arrive à prouver : pour tout k, P(k) vrai entraine P(k+1) vrai), il y a deux possibilités :
- soit on arrive à l'initialiser pour une certaine valeur disons k0, alors elle est vraie pour tout les entiers supérieurs ou égaux à ce k0
- soit on n'arrive pas à l'initialiser, et dans ce cas on ne sait rien du tout sur la propriété. Si on veut démontrer qu'elle est fausse, il faut le faire "à la main" ou alors démontrer que (non P) est héréditaire ... (voir mon exemple ci dessus)

Je suis toujours d'accord, mais ça n'invalide pas ce qui est dit ci-dessus. Ce que nous sommes plusieurs à faire remarquer est que si P(k) est faux, l'implication P(k)=>P(k+1) est vraie, donc qu'il suffit de montrer que cette implication est vraie pour les entiers k pour lesquels P(k) est vrai.

Évidemment, c'est sans intérêt pédagogique, mieux vaut apprendre directement la "bpnne" rédaction, mais toute les rédactions alambiquées ne sont pas nécessairement incorrectes.

Si on y réfléchit, cela peut permettre de faire des démonstrations d'hérédité amusantes. Par exemple, la propriété "k est strictement négatif" est héréditaire sur l'ensemble N.

k < 0 équivaut à k <= - 1 et alors k + 1 <=0 donc ce n'est pas héréditaire, k + 1 est négatif, mais pas strictement ...

@Prezbo a précisé « sur N », ce n'est pas un détail.
Si on prend x réel, l'implication (x<0 ⇒ x+1<0) est équivalente à (x≥0 ou x+1<0), elle est donc vraie sur R\[-1,0[; en particulier, elle est vraie sur N.

Voltaire a écrit:k < 0 équivaut à k <= - 1 et alors k + 1 <=0 donc ce n'est pas héréditaire, k + 1 est négatif, mais pas strictement ...

Mais si, elle est héréditaire sur N et c'est facile à prouver.

Soit k un entier naturel : k<0 est faux, donc l'implication (k<0 => k+1<0) est vérifiée.

De manière générale, pour toute proposition P fausse et toute proposition Q, l'implication P=>Q est vraie.

Une propriété est héréditaire si P(k) => P (k + 1)
Si P (k) est "k est strictement négatif", P(k + 1) est " k + 1 est strictement négatif"
On démontre P(k +1) sous l'hypothèse P(k), indépendamment de savoir si P(k) peut ou ne peut pas être vrai.
Ici ce n'est pas possible, sous l'hypothèse P(k), de démontrer P(k +1). Et cela n'a rien à voir avec le fait que P(k) soit fausse dans le cas où k est un entier naturel (ce serait une initialisation impossible, ça n'a rien à voir).

Je suis bien d'accord que si Q fausse, Q => P est vrai, mais précisément pour l'hérédité, on est obligé de partir de Q vraie, que ce soit possible ou non.
Autrement dit si P(k) est faux, P(k) => P(k+1) est vrai. Mais ce n'est pas de l'hérédité.
L'hérédité, c'est P(k) vrai => P(k +1) vrai (sinon tout est héréditaire, bien sûr)

Voltaire a écrit:Ici ce n'est pas possible, sous l'hypothèse P(k), de démontrer P(k +1). Et cela n'a rien à voir avec le fait que P(k) soit fausse dans le cas où k est un entier naturel (ce serait une initialisation impossible, ça n'a rien à voir).

Ben si, c'est possible:
Supposons k<0. Or k est un entier naturel, ce n'est pas possible donc on a une contradiction.
Donc k+1<0 par principe d'explosion.
Par contre cela ne peut pas conduire à une démonstration par récurrence valable pour des raisons évidentes (sauf si on travaille dans une axiomatique contradictoire, mais dans ce cas…).

Voltaire a écrit:Une propriété est héréditaire si P(k) => P (k + 1)
Si P (k) est "k est strictement négatif", P(k + 1) est " k + 1 est strictement négatif"
On démontre P(k +1) sous l'hypothèse P(k), indépendamment de savoir si P(k) peut ou ne peut pas être vrai.
Ici ce n'est pas possible, sous l'hypothèse P(k), de démontrer P(k +1). Et cela n'a rien à voir avec le fait que P(k) soit fausse dans le cas où k est un entier naturel (ce serait une initialisation impossible, ça n'a rien à voir).

Je suis bien d'accord que si Q fausse, Q => P est vrai, mais précisément pour l'hérédité, on est obligé de partir de Q vraie, que ce soit possible ou non.
Autrement dit si P(k) est faux, P(k) => P(k+1) est vrai. Mais ce n'est pas de l'hérédité.
L'hérédité, c'est P(k) vrai => P(k +1) vrai (sinon tout est héréditaire, bien sûr)

Tu te fais des nœuds au cerveau : il n'y a pas de différence entre montrer que P(k) vraie=> P(k+1) vraie et montrer que P(k)=> P(k+1). Evidemment, la manière usuelle de le montrer est de déduire P(k+1) de P(k), mais montrer que P(k) est faux suffit, même si c'est peu intuitif.

Par contre, cela n'implique pas que tout soit héritable. Par exemple, la propriété "k est pair" n'est pas héritable,parce qu'il existe des entiers k tel que P(k) est vraie et P(k+1) fausse. Cela implique juste qu'une propriété telle que pour tout k P(k) est fausse est héritable. Une autre manière de le voir est de remarquer que pour une telle propriété, l'ensemble des k tel que P(k) est vérifié est vide, dont qu'il n'existe aucun entier k pour lequel il n'est nécessaire de démontrer que P(k+1) est vraie.

Deux manières de démontrer une propriété notoirement héritable : 10^k+1 est divisible par k.

1) Soit k un entier naturel. Supposons que 10^k soit divisible par k. On a
10^(k+1)+1=10*10^k+1=10*(10^k+1-1)+1=10*(10^k+1)-10+1=10*(10^k+1)-9.

10^k+1 est divisible par 3 par hypothèse de récurrence et 9 est divisible par 3, donc 10^(k+1)+1 est divisible par 3 et la propriété est vraie au rang k+1.

2) Soit k un entier naturel. 10^k+1 est congru à 2 modulo 3, donc la propriété est fausse au rang k et P(k)=>P(k+1) est vraie.

Je maintiens que les deux démonstrations sont correctes. La première est plus piégeuse car elle dissimule le fait que pour tout k P(k) est fausse, et ressemble plus à une démonstration par récurrence classique, donc peut laisser penser que la propriété est vraie si on négligé l'initialisation.

Encore une fois, une propriété héritable n'est pas vraie, ni vraie pour au moins un entier k. Elle est vraie à partir d'un rang où on peut l'initialiser. Si ce rang n'existe pas, pour tout k, elle est fausse.

Prezbo a écrit:

Tu te fais des nœuds au cerveau : il n'y a pas de différence entre montrer que P(k) vraie=> P(k+1) vraie et montrer que P(k)=> P(k+1). Evidemment, la manière usuelle de le montrer est de déduire P(k+1) de P(k), mais montrer que P(k) est faux suffit, même si c'est peu intuitif.

Je n'ai rajouté "vrai" que pour une meilleure compréhension
Il y a tout de même une différence pour l'hérédité, on montre (P(k) et P(k) => P(k+1)), pas simplement (P(k) => P(k+1))

Prezbo a écrit:Par contre, cela n'implique pas que tout soit héritable. Par exemple, la propriété "k est pair" n'est pas héritable,parce qu'il existe des entiers k tel que P(k) est vraie et P(k+1) fausse. Cela implique juste qu'une propriété telle que pour tout k P(k) est fausse est héritable. Une autre manière de le voir est de remarquer que pour une telle propriété, l'ensemble des k tel que P(k) est vérifié est vide, dont qu'il n'existe aucun entier k pour lequel il n'est nécessaire de démontrer que P(k+1) est vraie.

C'est bien là que réside notre point de désaccord, puisque, pour moi, on ne peut démontrer l'héritabilité que d'une propriété supposée vraie au rang k (que ce soit possible ou non), pour la transmettre au rang k + 1. On ne peut pas hériter de quelque chose que son ancêtre n'a pas ...

Prezbo a écrit:Deux manières de démontrer une propriété notoirement héritable : 10^k+1 est divisible par k.

10^k+1 est divisible par 3

Prezbo a écrit:1) Soit k un entier naturel. Supposons que 10^k soit divisible par k3. On a
10^(k+1)+1=10*10^k+1=10*(10^k+1-1)+1=10*(10^k+1)-10+1=10*(10^k+1)-9.

10^k+1 est divisible par 3 par hypothèse de récurrence et 9 est divisible par 3, donc 10^(k+1)+1 est divisible par 3 et la propriété est vraie au rang k+1.

2) Soit k un entier naturel. 10^k+1 est congru à 2 modulo 3, donc la propriété est fausse au rang k et P(k)=>P(k+1) est vraie.

1) Tu as bien supposé P(k) vraie pour démontrer, sous cette hypothèse, que P(k+1) est vrai (sans présupposer à aucun moment qu'un tel k existe)
2) Je ne vois aucun intérêt à ajouter cette affirmation : P(k)=>P(k+1) est vraie dans le cadre d'une démonstration directe.

Prezbo a écrit:Je maintiens que les deux démonstrations sont correctes. La première est plus piégeuse car elle dissimule le fait que pour tout k P(k) est fausse, et ressemble plus à une démonstration par récurrence classique, donc peut laisser penser que la propriété est vraie si on négligé l'initialisation.

Certes, les deux démonstrations sont correctes, mais que prouvent-elles ?
1) prouve que la propriété est héréditaire pour tout k.
2) prouve que la propriété est fausse pour tout k.
Si on veut démontrer qu'une propriété héréditaire est fausse, c'est assez compliqué (puisqu'on ne peut pas le faire par récurrence, justement !). Donc 1) ne fait pas tellement avancer le schmilblick.

Prezbo a écrit:
Encore une fois, une propriété héritable n'est pas vraie, ni vraie pour au moins un entier k. Elle est vraie à partir d'un rang où on peut l'initialiser. Si ce rang n'existe pas, pour tout k, elle est fausse.

Par exemple 2^n >= (n + 2)^2 est vraie pour n >=6 (et se démontre aisément par récurrence)
Mais je persiste : on ne peut pas démontrer par récurrence qu'une propriété même héréditaire, est fausse (parce qu'il faut démontrer qu'elle n'est pas initialisable, donc qu'elle est toujours fausse, ce qui revient à démontrer directement qu'elle est fausse ...)

Voltaire a écrit:Mais je persiste : on ne peut pas démontrer par récurrence qu'une propriété même héréditaire, est fausse (parce qu'il faut démontrer qu'elle n'est pas initialisable, donc qu'elle est toujours fausse, ce qui revient à démontrer directement qu'elle est fausse ...)

Personne n'a prétendu le contraire.
Si on veut démontrer que P est fausse par récurrence, on démontre que non P est initialisable et héréditaire (ce qui revient, par contraposition, à faire une descente infinie de Fermat et donc à démontrer P(k+1)⇒P(k) plutôt que P(k)⇒P(k+1)).
Mais ce n'est pas ce que moi et @Prezbo avançons: nous expliquons simplement que si on montre (pas par récurrence) que P est fausse, cela permet d'en déduire que P est héréditaire (mais on ne pourra évidemment pas en déduire que P est vraie, sauf à travailler dans une axiomatique contradictoire).

Voltaire a écrit:

Prezbo a écrit:

Tu te fais des nœuds au cerveau : il n'y a pas de différence entre montrer que P(k) vraie=> P(k+1) vraie et montrer que P(k)=> P(k+1). Evidemment, la manière usuelle de le montrer est de déduire P(k+1) de P(k), mais montrer que P(k) est faux suffit, même si c'est peu intuitif.

Je n'ai rajouté "vrai" que pour une meilleure compréhension
Il y a tout de même une différence pour l'hérédité, on montre (P(k) et P(k) => P(k+1)), pas simplement (P(k) => P(k+1))

Je ne comprends pas comment tu parenthèses. Si tu veux dire que pour l'hérédité, on montrer que P(k) et (P(k)=>P(k+1)) c'est faux et c'est même une erreur majeure. Pour montrer l'hérédité, il n'est pas nécessaire de montrer P(k), d'une part parce que si on l'a déjà montré le reste de la démonstration est inutile, d'autre part parce que ça peut être faux. Il existe des propriétés héréditaires et fausse, voir exemples ci-dessus.

L'hérédité, c'est juste P(k)=>P(k+1), et cela suffit à démontrer le principe de récurrence dans tout système d'axiomes pour lequel (N,<=) est un ensemble bien ordonné, c'est-à-dire un ensemble dont toute partie non vide  admet un plus petit élément.

Démonstration : soit P(k) une propriété héréditaire ( c'est-à-dire telle que P(k)=>P(k+1) et pour laquelle un existe un entier k_0 tel que P(k_0) est vraie. Montrons que pour tout k>=k_0, P(k) est vraie.

On procède par l'absurde : supposons qu'il existe un entier k>=k_0 tel que P(k) soit faux. On note E l'ensemble de ces tels entiers. E est non vide par hypothèse, il admet donc un plus petit élément l. De plus, comme P(k_0) est vraie, l>k_0. L'entier l étant le plus petit élément de E, l-1 n'appartient pas à E donc P(l-1) est vraie. Par hérédité, on en déduite que P(l) est vraie, d'où une contradiction.

Prezbo a écrit:Par contre, cela n'implique pas que tout soit héritable. Par exemple, la propriété "k est pair" n'est pas héritable,parce qu'il existe des entiers k tel que P(k) est vraie et P(k+1) fausse. Cela implique juste qu'une propriété telle que pour tout k P(k) est fausse est héritable. Une autre manière de le voir est de remarquer que pour une telle propriété, l'ensemble des k tel que P(k) est vérifié est vide, dont qu'il n'existe aucun entier k pour lequel il n'est nécessaire de démontrer que P(k+1) est vraie.

C'est bien là que réside notre point de désaccord, puisque, pour moi, on ne peut démontrer l'héritabilité que d'une propriété supposée vraie au rang k (que ce soit possible ou non), pour la transmettre au rang k + 1. On ne peut pas hériter de quelque chose que son ancêtre n'a pas ...

Prezbo a écrit:Deux manières de démontrer une propriété notoirement héritable : 10^k+1 est divisible par k.

10^k+1 est divisible par 3

Prezbo a écrit:1) Soit k un entier naturel. Supposons que 10^k soit divisible par k3. On a
10^(k+1)+1=10*10^k+1=10*(10^k+1-1)+1=10*(10^k+1)-10+1=10*(10^k+1)-9.

10^k+1 est divisible par 3 par hypothèse de récurrence et 9 est divisible par 3, donc 10^(k+1)+1 est divisible par 3 et la propriété est vraie au rang k+1.

2) Soit k un entier naturel. 10^k+1 est congru à 2 modulo 3, donc la propriété est fausse au rang k et P(k)=>P(k+1) est vraie.

1) Tu as bien supposé P(k) vraie pour démontrer, sous cette hypothèse, que P(k+1) est vrai (sans présupposer à aucun moment qu'un tel k existe)
2) Je ne vois aucun intérêt à ajouter cette affirmation : P(k)=>P(k+1) est vraie dans le cadre d'une démonstration directe.

Prezbo a écrit:Je maintiens que les deux démonstrations sont correctes. La première est plus piégeuse car elle dissimule le fait que pour tout k P(k) est fausse, et ressemble plus à une démonstration par récurrence classique, donc peut laisser penser que la propriété est vraie si on négligé l'initialisation.

Certes, les deux démonstrations sont correctes, mais que prouvent-elles ?
1) prouve que la propriété est héréditaire pour tout k.
2) prouve que la propriété est fausse pour tout k.
Si on veut démontrer qu'une propriété héréditaire est fausse, c'est assez compliqué (puisqu'on ne peut pas le faire par récurrence, justement !). Donc 1) ne fait pas tellement avancer le schmilblick.

Non, les deux démonstrations montrent que la propriété est héréditaire, seule la méthode employée diffère. La seconde ne montre pas que la propriété est fausse pour tout k, elle utilise que la propriété est fausse pour tout k pour montrer qu'elle est héréditaire. Effectivement, du point de vu logique, une propriété telle que pour tout k P(k) est fausse est héréditaire.


Pour filer ta métaphore : si ton ancêtre n'a pas la propriété, tu n'en hérites pas. Ce qui ne l'empêche pas d'être héréditaire. La seule manière de prouver qu'une propriété n'est pas héréditaire est de prouver un entier k tel que (P(k) vraie et P(k+1) fausse).

Que penses-tu de la démonstration de Mathador plus haut qui montre que (k<0) est héréditaire sur N en utilisant le principe d!explosion ? En quoi serait- elle incorrecte ? (Pour mémoire, le principe d'explosion permet d'affirmer que si pour une propriété P, on parvient à démontrer (P et non P), alors pour tout propriété Q, on peut en déduire Q.

Honnêtement, je pense avoir donné pas mal d'argument (et avoir quelques souvenirs de logique), je pense que le blocage est surtout psychologique.

Pour moi, le problème dans "supposons qu'il existe k tel que P(k) vrai, démontrons P(k +1) vrai", que je lis "Supposons (\exists k \in \n, P(k)), démontrons (P(k+1))" c'est l'absence de quantificateur sur le k dans la deuxième moitié de la phrase. En réalité la seule interprétation non absurde est "supposons qu'il existe k tel que P(k) vrai, pour tout tel k démontrons P(k +1)" qui est une reformulation de l'hérédité en y incorporant de manière redondante un bout d'initialisation (moche mais à la limite ça implique bien la récurrence).

De manière générale je n'aime pas que l'on pose une variable avec un quantificateur. Pour moi la durée de vie d'un quantificateur se limite à la proposition mathématique qui le suit, et je mets un "Soit", un "Posons", ou quelque chose du genre pour poser une variable dont la durée de vie se prolonge à plusieurs lignes.
Exemple : "Comme f est continue, il existe \delta>0 tel que |f(x) - f(y)| < \delta. On pose \delta' = \delta/1000". Je n'aime pas.
Je préfère "Par continuité de f, soit \delta>0 tel que |f(x) - f(y)| < \delta. On pose \delta' = \delta/1000".
Ou à la limite "Comme f est continue, il existe \delta>0 tel que |f(x) - f(y)| < \delta. Fixons un tel \delta et posons \delta' = \delta/1000".

Même avec un "pour tout" je trouve ça un incorrect même si c'est moins grave.

Je suis du même avis, et cela colle aux règles syntaxiques de la logique formelle du premier ordre. Le « fixons » peut alors être vu comme une extension de Henkin ou de Skolem.