récurrence

Prezbo a écrit:

mathmax a écrit:J’avoue ne pas bien saisir le problème. Dans les 2 cas, on prouve que si P(k) est vraie alors P(k+1) est vraie. Le fait de supposer qu’il existe effectivement un k pour lequel P(k) est vrai ne vient pas invalider cette preuve il me semble, même si c’est superflu. De plus traditionnellement en terminale on a montré avant que P(n0) est vraie.

Montrer que la propriété P est héréditaire, encore une fois, c'est montrer que pour un entier naturel k quelconque, P(k)=>P(k+1), ce qui implique que (Pour tout entier naturel k, P(k)=>P(k+1) ).

Commencer sa rédaction par "Supposons qu'il existe un entier k tel que P(k) est vrai. Montrons que P(k+1) est vraie." d'une part est inutile (voir exemple ci-dessus : il existe des propriétés héréditaires et fausses pour tout entier n), d'autre part semble dans la formulation indiquer que tu te places dans le cas d'un entier k particulier.


Par ailleurs, pour revenir ta dernière remarque, si on a précédemment montré l'initialisation, il n'est pas la peine de supposer qu'il existe un entier k tel que P(k) est vrai : on le sait déjà.

Je suis tout à fait d'accord avec toi ! C'est bien pour ça que cette rédaction m'a horrifiée quand je l'ai vue
Dans toutes les rédactions que je montrais (et découvertes), je ne parlais que de l'hérédité : l'initialisation était faite par ailleurs, sinon, je ne vois même pas comment on pourrait appeler cela une récurrence (bon, hormis pour certains cas très particuliers de récurrence généralisée).

Je réagis en retard là-dessus:

Prezbo a écrit:Commencer sa rédaction par "Supposons qu'il existe un entier k tel que P(k) est vrai. Montrons que P(k+1) est vraie." d'une part est inutile (voir exemple ci-dessus : il existe des propriétés héréditaires et fausses pour tout entier n), d'autre part semble dans la formulation indiquer que tu te places dans le cas d'un entier k particulier.

C'est même pire que cela: le prédicat d'existence « capture » la variable k, qui devient donc liée dans le prédicat P(k) et libre dans le prédicat P(k+1).
Cela revient donc à dire « Supposons qu'il existe un entier n tel que P(n). Montrons P(k+1). », méthode de raisonnement dont on voit clairement l'absurdité (si on y arrive, c'est qu'on n'a pas besoin de récurrence).

Mathador a écrit:@Patatine:
Ce sont peut-être plus les collègues de français qu'il faudrait interroger à ce stade
De mon point de vue, le subjonctif « soit » précise l'existence de n, qu'on caractérise par la suite par les prédicats « appartenant à n » puis « tel que P(n) » (que le Wikitionnaire considère comme une locution adjectivale*).
On se rapproche donc de ton deuxième point.

* si on substitue par un adjectif, on obtient une formulation du type « soit n \in N pair », ou dans un autre domaine « soient (u,v) \in E² colinéaires » (avec E espace vectoriel), dont l'interprétation me semble sans ambiguïté.

J'ai à nouveau plusieurs points de vue à proposer du coup !!
- le "soit précise l'existence de n" : dans ce cas, comment fais-tu pour introduire un quelque soit avec des mots français ?
- le « soit n \in N pair » :
 + si le soit est une existence, c'est clairement "\exists n \in N, n pair" : pas de souci
 + si le soit est un forall, c'est "\forall n \in {k \in N, k pair}", et donc pas du "\forall n \in N, (n pair ...)" : je me sens extrémiste là... y a-t-il vraiment besoin de faire une différence entre "soit n \in N pair" et "soit n \in N, on suppose que n est pair" ? Cela rejoint ton exemple de récurrence "inhabituelle, mais juste".
 + comment faire la différence entre les deux ?!?
- le "soit" ne correspond pas à une existence, mais à l'introduction dans le contexte d'une variable, qui pourra être ensuite transférée à l'aide d'un \forall : « soit (u,v) \in E² colinéaires » se traduit pour moi par \forall (u,v) \in E² ... plus loin (sous-entendu, les u et v existent pour toute la suite, donc début de parenthèse) u R v avec R la relation de colinéarité (ou sinon, on pourrait aussi dire "\exists k \in R, u = k v \/ v = ku", mais ça commence à être très lourd)

Que penses-tu de l'énoncé suivant : soit x \in \varnothing, x \noteq x ? existence ou universel ?

Edit : j'ai oublié une partie : 'pour moi', en mathématiques, on utilise les mots français pour rendre les raisonnements plus compréhensibles, mais les mots n'ont pas forcément le même sens qu'en français habituel (coucou mes 2ndes et la direction des vecteurs). C'est donc à nous, matheux, de définir le sens de chaque mot, ou plutôt d'utiliser le sens mathématique usuel associé à chaque mot français.

Mathador a écrit:Je réagis en retard là-dessus:

Prezbo a écrit:Commencer sa rédaction par "Supposons qu'il existe un entier k tel que P(k) est vrai. Montrons que P(k+1) est vraie." d'une part est inutile (voir exemple ci-dessus : il existe des propriétés héréditaires et fausses pour tout entier n), d'autre part semble dans la formulation indiquer que tu te places dans le cas d'un entier k particulier.

C'est même pire que cela: le prédicat d'existence « capture » la variable k, qui devient donc liée dans le prédicat P(k) et libre dans le prédicat P(k+1).
Cela revient donc à dire « Supposons qu'il existe un entier n tel que P(n). Montrons P(k+1). », méthode de raisonnement dont on voit clairement l'absurdité (si on y arrive, c'est qu'on n'a pas besoin de récurrence).

Il y a un smiley pour mettre un gros pouce vers le haut et vous dire merci ?

Edit : supposer l'existence ne sert même à rien (de toute façon, on ne peut pas l'utiliser, vu que le n n'existe plus à la phrase suivante, comme tu le dis), puisqu'on a montré cette existence à l'initialisation. D'ailleurs, d'où sortirait le $k$ du $P(k+1)$ ? (ou comme dirait un de mes anciens profs : c'est ton ami k ? tu me le présentes ?)

Patatine a écrit:

Mathador a écrit:Je réagis en retard là-dessus:

Prezbo a écrit:Commencer sa rédaction par "Supposons qu'il existe un entier k tel que P(k) est vrai. Montrons que P(k+1) est vraie." d'une part est inutile (voir exemple ci-dessus : il existe des propriétés héréditaires et fausses pour tout entier n), d'autre part semble dans la formulation indiquer que tu te places dans le cas d'un entier k particulier.

C'est même pire que cela: le prédicat d'existence « capture » la variable k, qui devient donc liée dans le prédicat P(k) et libre dans le prédicat P(k+1).
Cela revient donc à dire « Supposons qu'il existe un entier n tel que P(n). Montrons P(k+1). », méthode de raisonnement dont on voit clairement l'absurdité (si on y arrive, c'est qu'on n'a pas besoin de récurrence).

Il y a un smiley pour mettre un gros pouce vers le haut et vous dire merci ?

Edit : supposer l'existence ne sert même à rien (de toute façon, on ne peut pas l'utiliser, vu que le n n'existe plus à la phrase suivante, comme tu le dis), puisqu'on a montré cette existence à l'initialisation. D'ailleurs, d'où sortirait le $k$ du $P(k+1)$ ? (ou comme dirait un de mes anciens profs : c'est ton ami k ? tu me le présentes ?)

Dans la phrase « Supposons qu'il existe un entier k tel que P(k) est vrai. Montrons que P(k+1) est vraie. », il y a le sous entendu usuel dans ce genre de formulation : « Supposons qu'il existe un entier k tel que P(k) est vrai. Fixons un tel entier k et montrons que P(k+1) est vraie. »
La lettre k désigne alors tout entier tel que P(k) soit vrai. C'est donc une façon absolument correcte de montrer l'hérédité (et ce n'est pas non plus mis en défaut par des propositions P(k) qui seraient héréditaires en étant toutes fausses).

Clp a écrit:

Patatine a écrit:

Mathador a écrit:Je réagis en retard là-dessus:

Prezbo a écrit:Commencer sa rédaction par "Supposons qu'il existe un entier k tel que P(k) est vrai. Montrons que P(k+1) est vraie." d'une part est inutile (voir exemple ci-dessus : il existe des propriétés héréditaires et fausses pour tout entier n), d'autre part semble dans la formulation indiquer que tu te places dans le cas d'un entier k particulier.

C'est même pire que cela: le prédicat d'existence « capture » la variable k, qui devient donc liée dans le prédicat P(k) et libre dans le prédicat P(k+1).
Cela revient donc à dire « Supposons qu'il existe un entier n tel que P(n). Montrons P(k+1). », méthode de raisonnement dont on voit clairement l'absurdité (si on y arrive, c'est qu'on n'a pas besoin de récurrence).

Il y a un smiley pour mettre un gros pouce vers le haut et vous dire merci ?

Edit : supposer l'existence ne sert même à rien (de toute façon, on ne peut pas l'utiliser, vu que le n n'existe plus à la phrase suivante, comme tu le dis), puisqu'on a montré cette existence à l'initialisation. D'ailleurs, d'où sortirait le $k$ du $P(k+1)$ ? (ou comme dirait un de mes anciens profs : c'est ton ami k ? tu me le présentes ?)

Dans la phrase « Supposons qu'il existe un entier k tel que P(k) est vrai. Montrons que P(k+1) est vraie. », il y a le sous entendu usuel dans ce genre de formulation : « Supposons qu'il existe un entier k tel que P(k) est vrai. Fixons un tel entier k et montrons que P(k+1) est vraie. »
La lettre k désigne alors tout entier tel que P(k) soit vrai. C'est donc une façon absolument correcte de montrer l'hérédité (et ce n'est pas non plus mis en défaut par des propositions P(k) qui seraient héréditaires en étant toutes fausses).

Que signifie "fixons" ? Choisir une valeur particulière (indistincte ou non => existence) ? Ou une valeur quelconque (pour tout => mais pourquoi traduirait-on un "il existe" par un "pour tout" ?) ?

Plusieurs choses :
- le sous-entendu usuel, non formel, n'existe que parce que nous décidons collectivement (volontairement ou non), de maintenir cette ambigüité. Il semblerait que nous soyons au moins 3 à le refuser.
- un "il existe" a une portée (souvent indiquée par un "tel que", la suite étant des implications qui doivent rester dans la portée du tel que) : \exists k \in N, (...). Soit tu supposes qu'il existe k tel que P(k) => P(k+1) (mais dans ce cas, tu supposes l'hérédité). Soit tu supposes qu'il existe k tel que P(k) (mais une fois la phrase finie, k n'existe plus) (ce qui ne permet pas non plus de faire une récurrence).

Pour abuser un peu, on pourrait imaginer le raisonnement suivant :
Imaginons qu'on essaie de montrer que tous les entiers n \geq 1 ne sont pas divisibles par 3.
Initialisation :
 n = 1, 1 n'est pas divisible par 3 ; la propriété est vraie pour n = 1.
Hérédité :
 Supposons qu'il existe un entier k tel que k n'est pas divisible par 3.
 -> tu sous-entends de le traduire par "fixons un entier k tel que k n'est pas divisible par 3".
 je fixe un entier k tel que k n'est pas divisible par 3. ok, je choisis k = 4 (j'ai le droit : fixer un entier, c'est en choisir un en particulier). J'ai donc fixé un entier k (4) tel que k n'est pas divisible pas 3 : j'ai donc respecté ta supposition.
 k + 1 = 5. 5 n'est pas divisible par 3.
 j'ai donc montré que k+1 n'est pas divisible par 3.
Conclusion : tous les entiers n \geq 1 ne sont pas divisibles par 3.
(Ce n'est pas vraiment le meilleur exemple, mais à cette heure..)

Je pense que cela se voit au-dessus, mais quand on suppose qu'il existe un entier tel que ... , cela induit qu'il existe un tel entier, donc qu'on peut faire le raisonnement avec un tel entier particulier (quantificateur d'existence), c'est-à-dire qu'on peut faire des déductions sur un tel entier. (j'essaie d'entretenir l'ambigüité : le k dans le cas k+1 n'est pas censé pouvoir être référencé).
A l'inverse, si on ne "fixe" pas un entier avec des suppositions, cela signifie qu'on prend un entier absolument quelconque ("on choisit une marche quelconque, et cela peut être absolument n'importe quelle marche"), et qu'on ne peut donc pas déduire quoi que ce soit sur cet entier. L'hérédité consiste alors à dire que si la propriété est vraie pour cet entier ("si on peut attendre cette marche", qui n'a absolument rien de particulier), alors elle est vraie pour l'entier suivant ("on peut attendre la marche suivante").

Le raisonnement peut paraître juste "de loin" si l'on n'utilise aucune propriété de l'entier k. Mais à partir du moment où on suppose qu'il existe (=quantificateur d'existence) un entier tel que... on n'est plus dans un raisonnement par récurrence : P(0) \implies (\forall k, (P(k) \implies P(k+1)) \implies (\forall n, P(n))

Patatine a écrit:

Clp a écrit:

Patatine a écrit:

Mathador a écrit:Je réagis en retard là-dessus:

C'est même pire que cela: le prédicat d'existence « capture » la variable k, qui devient donc liée dans le prédicat P(k) et libre dans le prédicat P(k+1).
Cela revient donc à dire « Supposons qu'il existe un entier n tel que P(n). Montrons P(k+1). », méthode de raisonnement dont on voit clairement l'absurdité (si on y arrive, c'est qu'on n'a pas besoin de récurrence).

Il y a un smiley pour mettre un gros pouce vers le haut et vous dire merci ?

Edit : supposer l'existence ne sert même à rien (de toute façon, on ne peut pas l'utiliser, vu que le n n'existe plus à la phrase suivante, comme tu le dis), puisqu'on a montré cette existence à l'initialisation. D'ailleurs, d'où sortirait le $k$ du $P(k+1)$ ? (ou comme dirait un de mes anciens profs : c'est ton ami k ? tu me le présentes ?)

Dans la phrase « Supposons qu'il existe un entier k tel que P(k) est vrai. Montrons que P(k+1) est vraie. », il y a le sous entendu usuel dans ce genre de formulation : « Supposons qu'il existe un entier k tel que P(k) est vrai. Fixons un tel entier k et montrons que P(k+1) est vraie. »
La lettre k désigne alors tout entier tel que P(k) soit vrai. C'est donc une façon absolument correcte de montrer l'hérédité (et ce n'est pas non plus mis en défaut par des propositions P(k) qui seraient héréditaires en étant toutes fausses).

Imaginons qu'on essaie de montrer que tous les entiers n \geq 1 ne sont pas divisibles par 3.
Initialisation :
 n = 1, 1 n'est pas divisible par 3 -> la propriété est vraie pour n = 3.
Hérédité :
 Supposons qu'il existe un entier k tel que k n'est pas divisible par 3.
 -> tu sous-entends de le traduire par "fixons un entier k tel que k n'est pas divisible par 3".
 je fixe un entier k tel que k n'est pas divisible par 3. ok, je choisis k = 4 (j'ai le droit : fixer un entier, c'est en choisir un en particulier). J'ai donc fixé un entier k (4) tel que k n'est pas divisible pas 3 : j'ai donc respecté ta supposition.
 k + 1 = 5. 5 n'est pas divisible par 3.
 j'ai donc montré que k+1 n'est pas divisible par 3.
Conclusion : tous les entiers n \geq 1 ne sont pas divisibles par 3.
(Ce n'est pas vraiment le meilleur exemple, mais à cette heure..)

Je pense que cela se voit au-dessus, mais quand on suppose qu'il existe un entier, cela induit qu'on peut soit choisir un tel entier, c'est-à-dire qu'on peut faire des déductions sur un tel entier.
A l'inverse, si on ne "fixe" pas un entier avec des suppositions, cela signifie qu'on prend un entier absolument quelconque ("on choisit une marche quelconque, et cela peut être absolument n'importe quelle marche"), et qu'on ne peut donc pas déduire quoi que ce soit sur cet entier. L'hérédité consiste alors à dire que si la propriété est vraie pour cet entier ("si on peut attendre cette marche", qui n'a absolument rien de particulier), alors elle est vraie pour l'entier suivant ("on peut attendre la marche suivante").

Le raisonnement peut paraître juste "de loin" si l'on n'utilise aucune propriété de l'entier k. Mais à partir du moment où on suppose qu'il existe (=quantificateur d'existence) un entier tel que... on n'est plus dans un raisonnement par récurrence : P(0) \implies (\forall k, (P(k) \implies P(k+1)) \implies (\forall n, P(n))

Quand on fixe une variable dans un raisonnement sans plus de précision (ce qui exclut une formulation du type « fixons un entier k tel que P(k), par exemple k=4 »), cela signifie que la suite du raisonnement doit pouvoir s'appliquer à toutes les variables que l'on est en droit de fixer. Donc si je dis : « fixons un entier k tel que P(k) et montrons qu'il vérifie telle propriété », c'est pareil que de dire : « fixons un entier k quelconque tel que P(k) et montrons qu'il vérifie telle propriété », ou encore « soit k tel que P(k) et montrons qu'il vérifie telle propriété ». On pourrait convenir que c'est une sorte d'abus de langage mais tellement usité que c'en n'est plus vraiment un…

Pour ta dernière phrase, je ne comprends pas bien. Pour montrer directement une proposition commençant par « pour tout », il faut bien fixer dans le raisonnement la variable en question, qu'on dise « soit k », « fixons k » ou autre chose…

Edit : je dis que c'est une formulation usuelle parce que tous les mathématiciens que j'ai côtoyés l'emploient de cette façon. Je pense qu'elle est partagée dans de très nombreux ouvrages (mais je ne vais pas vérifier).

Clp a écrit:

Patatine a écrit:

Clp a écrit:

Patatine a écrit:

Il y a un smiley pour mettre un gros pouce vers le haut et vous dire merci ?

Edit : supposer l'existence ne sert même à rien (de toute façon, on ne peut pas l'utiliser, vu que le n n'existe plus à la phrase suivante, comme tu le dis), puisqu'on a montré cette existence à l'initialisation. D'ailleurs, d'où sortirait le $k$ du $P(k+1)$ ? (ou comme dirait un de mes anciens profs : c'est ton ami k ? tu me le présentes ?)

Dans la phrase « Supposons qu'il existe un entier k tel que P(k) est vrai. Montrons que P(k+1) est vraie. », il y a le sous entendu usuel dans ce genre de formulation : « Supposons qu'il existe un entier k tel que P(k) est vrai. Fixons un tel entier k et montrons que P(k+1) est vraie. »
La lettre k désigne alors tout entier tel que P(k) soit vrai. C'est donc une façon absolument correcte de montrer l'hérédité (et ce n'est pas non plus mis en défaut par des propositions P(k) qui seraient héréditaires en étant toutes fausses).

Imaginons qu'on essaie de montrer que tous les entiers n \geq 1 ne sont pas divisibles par 3.
Initialisation :
 n = 1, 1 n'est pas divisible par 3 -> la propriété est vraie pour n = 3.
Hérédité :
 Supposons qu'il existe un entier k tel que k n'est pas divisible par 3.
 -> tu sous-entends de le traduire par "fixons un entier k tel que k n'est pas divisible par 3".
 je fixe un entier k tel que k n'est pas divisible par 3. ok, je choisis k = 4 (j'ai le droit : fixer un entier, c'est en choisir un en particulier). J'ai donc fixé un entier k (4) tel que k n'est pas divisible pas 3 : j'ai donc respecté ta supposition.
 k + 1 = 5. 5 n'est pas divisible par 3.
 j'ai donc montré que k+1 n'est pas divisible par 3.
Conclusion : tous les entiers n \geq 1 ne sont pas divisibles par 3.
(Ce n'est pas vraiment le meilleur exemple, mais à cette heure..)

Je pense que cela se voit au-dessus, mais quand on suppose qu'il existe un entier, cela induit qu'on peut soit choisir un tel entier, c'est-à-dire qu'on peut faire des déductions sur un tel entier.
A l'inverse, si on ne "fixe" pas un entier avec des suppositions, cela signifie qu'on prend un entier absolument quelconque ("on choisit une marche quelconque, et cela peut être absolument n'importe quelle marche"), et qu'on ne peut donc pas déduire quoi que ce soit sur cet entier. L'hérédité consiste alors à dire que si la propriété est vraie pour cet entier ("si on peut attendre cette marche", qui n'a absolument rien de particulier), alors elle est vraie pour l'entier suivant ("on peut attendre la marche suivante").

Le raisonnement peut paraître juste "de loin" si l'on n'utilise aucune propriété de l'entier k. Mais à partir du moment où on suppose qu'il existe (=quantificateur d'existence) un entier tel que... on n'est plus dans un raisonnement par récurrence : P(0) \implies (\forall k, (P(k) \implies P(k+1)) \implies (\forall n, P(n))

Quand on fixe une variable dans un raisonnement sans plus de précision (ce qui exclut une formulation du type « fixons un entier k tel que P(k), par exemple k=4 »), cela signifie que la suite du raisonnement doit pouvoir s'appliquer à toutes les variables que l'on est en droit de fixer. Donc si je dis : « fixons un entier k tel que P(k) et montrons qu'il vérifie telle propriété », c'est pareil que de dire : « fixons un entier k quelconque tel que P(k) et montrons qu'il vérifie telle propriété », ou encore « soit k tel que P(k) et montrons qu'il vérifie telle propriété ». On pourrait convenir que c'est une sorte d'abus de langage mais tellement usité que c'en n'est plus vraiment un…

Pour ta dernière phrase, je ne comprends pas bien. Pour montrer directement une proposition commençant par « pour tout », il faut bien fixer dans le raisonnement la variable en question, qu'on dise « soit k », « fixons k » ou autre chose…

Edit : je dis que c'est une formulation usuelle parce que tous les mathématiciens que j'ai côtoyés l'emploient de cette façon. Je pense qu'elle est partagée dans de très nombreux ouvrages (mais je ne vais pas vérifier).

Si on fixe un entier sans plus de précision , c'est qu'on n'est pas en train d'utiliser un quantificateur d'existence, mais universel, comme le précise ton quelconque. Tu considères donc qu'un "fixons k" est équivalent à un "soit k" (donc à un "pour tout") comme tu le dis dans ta dernière phrase : cela ne me choque pas spécialement, et ça me paraît effectivement un usage habituel (bien que pas le mien) de la formulation.
Mais comment expliques-tu que la formulation "il existe k tel que..." se transforme en "fixons k ..." que tu indiques comme équivalent à "pour tout ..." ?

On en revient encore une fois à comment faire la différence entre un \forall et un \exists dans une formulation en français

Patatine a écrit:Mais comment expliques-tu que la formulation "il existe k tel que..." se transforme en "fixons k ..." que tu indiques comme équivalent à "pour tout ..." ?

Je vais essayer d'être plus précis dans mon propos pour montrer comment on peut passer d'une formulation à l'autre.

Je ne dis évidemment pas qu'« il existe » est équivalent à « pour tout ».

Je dis qu'il y a équivalence logique entre ∀x P(x)=>Q(x) et (∃x P(x)) => (∀x P(x)=>Q(x)).

Si l'on traduit cela en français, cela veut dire que l'on peut reformuler « on se donne un x quelconque, on suppose P(x) et on montre Q(x) » de façon complètement équivalente par « on suppose qu'il existe un x vérifiant P(x), on se donne un x quelconque vérifiant P(x) et on montre Q(x) ».
On peut reformuler cette dernière phrase en : « supposons qu'il existe un x vérifiant P(x), fixons un tel x et montrons Q(x) ».
Alors on commet la plupart du temps le petit abus de langage consistant à raccourcir le propos en : « supposons qu'il existe un x vérifiant P(x) et montrons Q(x) », le x dans Q(x) ne pouvant sans précision supplémentaire désigner que l'un quelconque des candidats que nous donne l'affirmation d'existence.

Clp a écrit:

Patatine a écrit:Mais comment expliques-tu que la formulation "il existe k tel que..." se transforme en "fixons k ..." que tu indiques comme équivalent à "pour tout ..." ?

Je vais essayer d'être plus précis dans mon propos pour montrer comment on peut passer d'une formulation à l'autre.

Je ne dis évidemment pas qu'« il existe » est équivalent à « pour tout ».

Je dis qu'il y a équivalence logique entre ∀x P(x)=>Q(x) et (∃x P(x)) => (∀x P(x)=>Q(x)).

Si l'on traduit cela en français, cela veut dire que l'on peut reformuler « on se donne un x quelconque, on suppose P(x) et on montre Q(x) » de façon complètement équivalente par « on suppose qu'il existe un x vérifiant P(x), on se donne un x quelconque vérifiant P(x) et on montre Q(x) ».
On peut reformuler cette dernière phrase en : « supposons qu'il existe un x vérifiant P(x), fixons un tel x et montrons Q(x) ».
Alors on commet la plupart du temps le petit abus de langage consistant à raccourcir le propos en : « supposons qu'il existe un x vérifiant P(x) et montrons Q(x) », le x dans Q(x) ne pouvant sans précision supplémentaire désigner que l'un quelconque des candidats que nous donne l'affirmation d'existence.

On est d'accord, il y a équivalence logique entre ∀x P(x) \implies Q(x) et (∃y P(y)) \implies (∀x P(x)=>Q(x)). (J'ai juste renommé les variables, pour ne pas perdre de "visibilité").

En rentrant plus en détail sur ta formulation, et la portée des variables, cela donnerait :
"Si l'on traduit cela en français, cela veut dire que l'on peut reformuler « on se donne un x quelconque, on suppose P(x) et on montre Q(x) » de façon complètement équivalente par « on suppose qu'il existe un y vérifiant P(y), on se donne un x quelconque vérifiant P(x) et on montre Q(x) ».
-> A quoi sert cette introduction d'existence avec des variables qui n'ont rien à voir avec celles que l'on va utiliser ? C'est complètement équivalent cependant, effectivement.

On peut reformuler cette dernière phrase en : « supposons qu'il existe un x vérifiant P(x), fixons un tel x et montrons Q(x) ».
-> encore une fois, pourquoi émettre une hypothèse en plus, dont on sait qu'elle est vraie (initialisation) ? Pourquoi ne pas juste fixer un x qui vérifie P(x) (aka "soit x, on suppose P(x)") ? Mais effectivement, il me semble, équivalent.

Il me faut donc préciser les propositions de rédactions : les "..." signifient systématiquement montrons P(k+1), et les raisonnements commencent directement après, sans introduction de variables complémentaires, donc sans "soit k" ni "fixons k" par la suite.

Vous ne dormez jamais ?

Après lecture, je suis d'accord avec Clp : le "Supposons qu'il existe un entier k tel que P(k). Montrons P(k+1)", même s'il est en toute rigueur formellement incorrect pour les raisons données par Mathador, est un abus de langage pour "Supposons qu'il existe un entier k tel que P(k). Montrons que pour tout entier de ce type, P(k+1)", abus tellement courant qu'on ne le note même plus.

Cela dit, vu que la supposition initiale est inutile, il me semble préférable d'écrire. "Soit k un entier naturel. On suppose P(k) vraie, montrons P(k+1)".

Comme souvent, la rédaction la plus claire est la plus concise. Les tentatives d'explications ne font qu'introduire de la confusion, de l’ambiguïté grammaticale et des considérations inutiles.

Il serait évidemment trop fastidieux d'écrire et de lire les démonstrations en langage entièrement formel, mais autant ne pas trop s'en éloigner pour les passages délicats.

En tout cas, c'est cool de reparler un peu de mathématiques et de logique dans le sous-forum maths.

Je ne comprends rien à ce fil et je tenais à le dire

Insiste, plus que tout autre ce fil demande de la suite dans les idées.

Pour revenir à la question initiale : axiome ou théorème ? On a envie de demander comment est construit N. C'est comme la propriété de bon ordre. Axiome ou théorème ? Je remarque qu'on dit souvent principe de récurrence, manière peut-être de ne pas trancher et de laisser le choix dans l'ordre des énoncés.

Quant à "fixer n", c'est tellement parlant pour un élève qu'il serait dommage de s'en priver : On suppose P(n) pour un certain n fixé et on s'occupe de n+1 (même pas honte).

Patatine a écrit:

Mathador a écrit:@Patatine:
Ce sont peut-être plus les collègues de français qu'il faudrait interroger à ce stade
De mon point de vue, le subjonctif « soit » précise l'existence de n, qu'on caractérise par la suite par les prédicats « appartenant à n » puis « tel que P(n) » (que le Wikitionnaire considère comme une locution adjectivale*).
On se rapproche donc de ton deuxième point.

* si on substitue par un adjectif, on obtient une formulation du type « soit n \in N pair », ou dans un autre domaine « soient (u,v) \in E² colinéaires » (avec E espace vectoriel), dont l'interprétation me semble sans ambiguïté.

J'ai à nouveau plusieurs points de vue à proposer du coup !!
- le "soit précise l'existence de n" : dans ce cas, comment fais-tu pour introduire un quelque soit avec des mots français ?
- le « soit n \in N pair » :
 + si le soit est une existence, c'est clairement "\exists n \in N, n pair" : pas de souci
 + si le soit est un forall, c'est "\forall n \in {k \in N, k pair}", et donc pas du "\forall n \in N, (n pair ...)" : je me sens extrémiste là... y a-t-il vraiment besoin de faire une différence entre "soit n \in N pair" et "soit n \in N, on suppose que n est pair" ? Cela rejoint ton exemple de récurrence "inhabituelle, mais juste".
 + comment faire la différence entre les deux ?!?
- le "soit" ne correspond pas à une existence, mais à l'introduction dans le contexte d'une variable, qui pourra être ensuite transférée à l'aide d'un \forall : « soit (u,v) \in E² colinéaires » se traduit pour moi par \forall (u,v) \in E² ... plus loin (sous-entendu, les u et v existent pour toute la suite, donc début de parenthèse) u R v avec R la relation de colinéarité (ou sinon, on pourrait aussi dire "\exists k \in R, u = k v \/ v = ku", mais ça commence à être très lourd)

Que penses-tu de l'énoncé suivant : soit x \in \varnothing, x \noteq x ? existence ou universel ?

Edit : j'ai oublié une partie : 'pour moi', en mathématiques, on utilise les mots français pour rendre les raisonnements plus compréhensibles, mais les mots n'ont pas forcément le même sens qu'en français habituel (coucou mes 2ndes et la direction des vecteurs). C'est donc à nous, matheux, de définir le sens de chaque mot, ou plutôt d'utiliser le sens mathématique usuel associé à chaque mot français.

Le « soit » est une existence à l'intérieur du raisonnement, et un « pour tout » lors de la conclusion.
Si je reprends l'exemple de la propriété d'hérédité:
- on démontre P(k+1) sous les hypothèses k \in N et P(k): ici le « soit » mentionne l'existence de k, et les hypothèses supplémentaires qu'on lui impose (k \in N si on dit « soit k \in N », les deux si on dit « soit k \in N tel que P(k) » (attention: l'existence de k tout court, pas l'existence d'un k vérifiant les hypothèses);
- on a donc démontré (par règle d'introduction de l'implication) la phrase logique k \in N ⇒ (P(k) ⇒ P(k+1)) sans faire d'hypothèse supplémentaire sur k;
- cela fonctionne donc pour tout k, on en déduit donc (règle d'introduction du quantificateur universel) \forall k, k \in N ⇒ (P(k) ⇒ P(k+1)) qu'on écrit plus communément \forall k \in N, P(k) ⇒ P(k+1).

PS:
- je considère donc « Soit k \in N. » et « Soit k. Supposons k \in N. » comme équivalents, de même que « Soit k \in N pair. » et « Soit k \in N. Supposons k pair. »;
- pour ton dernier énoncé, je ne vois pas comment l'interpréter.

Bolzano a écrit:Insiste, plus que tout autre ce fil demande de la suite dans les idées.

Pour revenir à la question initiale : axiome ou théorème ? On a envie de demander comment est construit N. C'est comme la propriété de bon ordre. Axiome ou théorème ? Je remarque qu'on dit souvent principe de récurrence, manière peut-être de ne pas trancher et de laisser le choix dans l'ordre des énoncés.

Quant à "fixer n", c'est tellement parlant pour un élève qu'il serait dommage de s'en priver : On suppose P(n) pour un certain n fixé et on s'occupe de n+1 (même pas honte).

Mouai...Il me semble que ce "fixons n" fait partir des tics de langage mathématiques que nous utilisons par habitude et dont le sens est tout sauf clair si on creuse un peu. Dans le "fixons n", j'ai l'impression que l'on s'apprête à montrer la propriété d'hérédité pour un entier n particulier, alors que nous voulons la montrer un entier n quelconque.

De manière générale, la rédaction usuelle de la démonstration de récurrence sous-entend l'utilisation du principe de généralisation, qui est bien un axiome. On montre que (P(k)=>P(k+1)), on en déduite que (Pour tout entier naturel k, P(k)=>P(k+1)).

Prezbo a écrit:De manière générale, la rédaction usuelle de la démonstration de récurrence sous-entend l'utilisation du principe de généralisation, qui est bien un axiome. On montre que (P(k)=>P(k+1)), on en déduite que (Pour tout entier naturel k, P(k)=>P(k+1)).

En logique formelle, ce n'est pas un axiome mais une règle de déduction, présente notamment telle quelle dans les systèmes LK et NK du calcul des séquents.

Prezbo a écrit:Vous ne dormez jamais ?

Après lecture, je suis d'accord avec Clp : le "Supposons qu'il existe un entier k tel que P(k). Montrons P(k+1)", même s'il est en toute rigueur formellement incorrect pour les raisons données par Mathador, est un abus de langage pour "Supposons qu'il existe un entier k tel que P(k). Montrons que pour tout entier de ce type, P(k+1)", abus tellement courant qu'on ne le note même plus.

Cela dit, vu que la supposition initiale est inutile, il me semble préférable d'écrire. "Soit k un entier naturel. On suppose P(k) vraie, montrons P(k+1)".

Comme souvent, la rédaction la plus claire est la plus concise. Les tentatives d'explications ne font qu'introduire de la confusion, de l’ambiguïté grammaticale et des considérations inutiles.

Il serait évidemment trop fastidieux d'écrire et de lire les démonstrations en langage entièrement formel, mais autant ne pas trop s'en éloigner pour les passages délicats.

En tout cas, c'est cool de reparler un peu de mathématiques et de logique dans le sous-forum maths.

Merci Prezbo et Patatine, je crois qu'on finit par tomber d'accord sur ce point (ou pas loin de l'être)
C'est vrai que c'est agréable de voir le forum maths revivre un peu.

Pour revenir à la question initiale, voici mon avis personnel sur les autres formulations :

Patatine a écrit:
1 - "on suppose qu'il existe un entier k tel que P(k), montrons que P(k+1) est vraie" <- c'est la première qu'on m'a suggérée et qui m'a fait réagir, après, le choc était passé
2 - "on suppose que P(k) est vraie pour k \geq 1, ..."
3 - "on suppose que P(k) est vraie pour un certain k, ..."
4 - "on suppose que ``l'égalité est vérifiée' ' pour k \geq 1, ..."
5 - "soit k \in N tel que P(k) est vraie, ..."

(1) Celle qu'on vient de discuter, correcte modulo une petite circonvolution logique et un un léger abus de langage par omission, assez usitée et facilement compréhensible.
(2 et (4) Faux, car l'hypothèse est « pour tout k, P(k) ». Il manque la précision « un certain k ».
(3) Correct, car le quantificateur sous-entendu est « pour tout k vérifiant P(k) ». [Comme discuté dans le cas de (1), dans un raisonnement du type « fixons un certain k tel que Q(k), alors R(k) », la proposition R(k) est réputé valide pour tous les k vérifiant Q(k).]
(5) Formulation irréprochable me semble-t-il.

Est-ce aussi votre avis ?

Mathador a écrit:

Prezbo a écrit:De manière générale, la rédaction usuelle de la démonstration de récurrence sous-entend l'utilisation du principe de généralisation, qui est bien un axiome. On montre que (P(k)=>P(k+1)), on en déduite que (Pour tout entier naturel k, P(k)=>P(k+1)).

En logique formelle, ce n'est pas un axiome mais une règle de déduction, présente notamment telle quelle dans les systèmes LK et NK du calcul des séquents.

Tu as raison. Je devrais refaire plus de logique.

Mon prof de maths dans ma folle jeunesse disait " les physiciens ont des principes, les mathématiciens ont des axiomes ou des théorèmes"
Selon la construction de N adoptée, la récurrence est un axiome ou un théorème. Mais comme on ne construit plus N au lycée, on ne sait pas la nature exacte que prend la récurrence d'où l'affreux terme de "principe de récurrence". Pour éviter cet écueil, je proposais simplement de dire "démontrons par récurrence", "on a démontré par récurrence"
Quant à "Supposons qu'il existe k tel que P(k) est vrai, démontrons P(k+1)", ce n'est pas du tout équivalent à "Montrons que P(k) implique P(k+1)"
Dans le premier cas, si P(k) est faux pour tout k, la démonstration "tombe". La deuxième formulation est la seule correcte. Si P(k) est vrai, alors ... la démonstration reste valable même si P(k) n'est vérifié pour aucun k.
Par exemple les deux propriétés : pour n entier naturel, P(n) : 3 divise 4^n – 1 et Q(n) : 3 divise 4^n + 1 sont toutes les deux héréditaires. L'une s'initialise pour n = 0 et est donc vraie pour tout entier n naturel, et on peut démontrer (en utilisant cette propriété) que l'autre est toujours fausse (parce que ce n'est pas parce qu'on n'arrive pas à initialiser une propriété héréditaire, qu'elle est automatiquement fausse !)

Voltaire a écrit:Quant à "Supposons qu'il existe k tel que P(k) est vrai, démontrons P(k+1)", ce n'est pas du tout équivalent à "Montrons que P(k) implique P(k+1)"
Dans le premier cas, si P(k) est faux pour tout k, la démonstration "tombe". La deuxième formulation est la seule correcte. Si P(k) est vrai, alors ... la démonstration reste valable même si P(k) n'est vérifié pour aucun k.

Si P(k) est faux pour tout k, cela implique que P(k) ⇒ P(k+1) pour tout k, car toute implication dont le prémisse est faux est vraie.

Clp a écrit:Pour revenir à la question initiale, voici mon avis personnel sur les autres formulations :

Patatine a écrit:
1 - "on suppose qu'il existe un entier k tel que P(k), montrons que P(k+1) est vraie" <- c'est la première qu'on m'a suggérée et qui m'a fait réagir, après, le choc était passé
2 - "on suppose que P(k) est vraie pour k \geq 1, ..."
3 - "on suppose que P(k) est vraie pour un certain k, ..."
4 - "on suppose que ``l'égalité est vérifiée' ' pour k \geq 1, ..."
5 - "soit k \in N tel que P(k) est vraie, ..."

(1) Celle qu'on vient de discuter, correcte modulo une petite circonvolution logique et un un léger abus de langage par omission, assez usitée et facilement compréhensible.
(2 et (4) Faux, car l'hypothèse est « pour tout k, P(k) ». Il manque la précision « un certain k ».
(3) Correct, car le quantificateur sous-entendu est « pour tout k vérifiant P(k) ». [Comme discuté dans le cas de (1), dans un raisonnement du type « fixons un certain k tel que Q(k), alors R(k) », la proposition R(k) est réputé valide pour tous les k vérifiant Q(k).]
(5) Formulation irréprochable me semble-t-il.

Est-ce aussi votre avis ?

Pour le 1 je ne suis pas d'accord, pour la raison que j'ai exprimée plus haut (le k de P(k) et le k de P(k+1) ne sont pas les mêmes, tout comme le x de f(x) et le x de g(x) dans la formule f(x) + intégrale de 0 à 1 de g(x)dx).

Mathador a écrit:Pour le 1 je ne suis pas d'accord, pour la raison que j'ai exprimée plus haut (le k de P(k) et le k de P(k+1) ne sont pas les mêmes, tout comme le x de f(x) et le x de g(x) dans la formule f(x) + intégrale de 0 à 1 de g(x)dx).

Je pense que ce n'est pas tout à fait pareil, parce que dans la formule que tu cites il est interdit de ré-utiliser x comme variable muette. Dans le cas de la proposition (1) qu'on discute, si l'on s'accorde sur le fait qu'est sous-entendu « fixons un tel k » après la première virgule, alors il est licite de ré-utiliser k comme nom de variable puisque la portée de k dans l'énoncé « il existe un entier k tel que P(k) » ne s'étend pas au-delà.

On pourrait aussi bien dire « on suppose qu'il existe un entier k tel que P(k), fixons un tel entier que nous nommerons n, et montrons que P(n+1) est vraie », simplement pour des raisons évidentes il ne serait alors plus possible de sous-entendre la partie centrale de la phrase.

Clp a écrit:

Mathador a écrit:Pour le 1 je ne suis pas d'accord, pour la raison que j'ai exprimée plus haut (le k de P(k) et le k de P(k+1) ne sont pas les mêmes, tout comme le x de f(x) et le x de g(x) dans la formule f(x) + intégrale de 0 à 1 de g(x)dx).

Je pense que ce n'est pas tout à fait pareil, parce que dans la formule que tu cites il est interdit de ré-utiliser x comme variable muette. Dans le cas de la proposition (1) qu'on discute, si l'on s'accorde sur le fait qu'est sous-entendu « fixons un tel k » après la première virgule, alors il est licite de ré-utiliser k comme nom de variable puisque la portée de k dans l'énoncé « il existe un entier k tel que P(k) » ne s'étend pas au-delà.

Tu as effectivement explicité mon point de désaccord: je considère que l'explicitation de cette étape est nécessaire pour « casser » la capture de la variable k par le quantificateur existentiel.
Dans le cas contraire, je considère la phrase logique (\exists k \in N, P(k)) ⇒ P(k+1) tout aussi problématique que la formule avec l'intégrale, pour la même raison: on donne le même nom à une variable libre et une variable liée (ou autrement dit, muette).

Voltaire a écrit:Mon prof de maths dans ma folle jeunesse disait " les physiciens ont des principes, les mathématiciens ont des axiomes ou des théorèmes"
Selon la construction de N adoptée, la récurrence est un axiome ou un théorème. Mais comme on ne construit plus N au lycée, on ne sait pas la nature exacte que prend la récurrence d'où l'affreux terme de "principe de récurrence". Pour éviter cet écueil, je proposais simplement de dire "démontrons par récurrence", "on a démontré par récurrence"
Quant à "Supposons qu'il existe k tel que P(k) est vrai, démontrons P(k+1)", ce n'est pas du tout équivalent à "Montrons que P(k) implique P(k+1)"
Dans le premier cas, si P(k) est faux pour tout k, la démonstration "tombe". La deuxième formulation est la seule correcte. Si P(k) est vrai, alors ... la démonstration reste valable même si P(k) n'est vérifié pour aucun k.

Je ne suis pas d'accord avec ce qui est indiqué en gras : si pour tout entier k P(k) est fausse , alors (Pour tout entier naturel k P(k)=>P(k+1))  est vérifiée et la propriété est de toute façon héréditaire. C'est ce que faisait remarquer Clp je crois en notant que ∀x P(x)=>Q(x) et (∃x P(x)) => (∀x P(x)=>Q(x)) étaient deux propriétés équivalentes.

Cela dit, je pense effectivement que la seconde rédaction est bien supérieure.

Edit : grillé par Mathador.

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).
Et bien sûr l'horreur absolue c'est de dire supposons que quel que soit k, P(k) est vrai et démontrons ... rien du tout, du coup.

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).