Récurrence très forte

Chaurien · December 2017

Sur ce forum, chacun peut librement se comparer à chacun, sur tel ou tel sujet. Le jeune étudiant doué et travailleur peut en remontrer à des têtes chenues.

christophe c · December 2017

@gebrane (et peut-être autres lecteurs, j'ai lu en diagonale), ça n'a rien de subtil, écris les choses dualement (c'est à dire remplace les $\forall$ par des $\exists$, etc de manière à passer à la négation tout en gardant les "non" sur les feuilles de l'énoncé) comme un robot automatique.

tu as l'énoncé (en français) <<si A est non vide alors A admet un minimum>> qui écrit formellement donne:

si $\exists x: x\in A$ alors $\exists x: (x\in A$ et $\forall y: (y<x\to y\notin A) )$

dont la contraposée "robotique" est:

si $\forall x: (x\in A$ implique $\exists y: (y<x$ et $ y \in A) )$ alors $\forall x: x\notin A$

qui n'est pas très jolie, mais tu peux encore contraposer la partie après $\forall x$ de l'hypothèse ce qui donne:

si $\forall x: (x\notin A$ est impliqué par $\forall y: (y<x$ implique $ y \notin A) )$ alors $\forall x: x\notin A$

Et pour parfaire la présentation, tu appliques ça à $\N\setminus A$ de manière à remplacer les $\notin $ par des $\in$.

Alors évidemment en un certain sens tu pourrais me dire "bin voui, mais ton discours est long, qu'est-ce qu'on gagne?". En fait, en un certain sens, que je ne détaillerai que sur demande, ce que je viens de détailler est à "coût nul" (autrement dit, je n'ai in some sense, "vraiment rien fait"): pas de duplication d'hypothèse, de raisonnement par l'absurde, de jetage d'hypothèse, d'affaiblissement etc.

gebrane · December 2017

@cc
Je ne voulais pas rallonger ma discussion inutilement , j'avais écrit dans http://www.les-mathematiques.net/phorum/read.php?16,1575410,1576126#msg-1576126

on a à la fois $\forall k <0\ P(k)$ est vrai et $\forall k <0\ P(k)$ est faux

. J’étais négligeant sur les parenthèses, il fallait lire

on a à la fois $\forall k <0\ $ ($P(k)$ est vrai) et $\forall k <0\ $(P(k) est faux)

Apres j'ai trouvé mon message inutile et j'ai dit à Gabu ok et merci

Chelito · April 2021

Est-ce que quelqu'un pourrait avoir la gentillesse de confirmer la reformulation que je propose (ou, si ce n'est pas abuser, de me corriger)?

Je reprends l'exemple qui a ouvert cette discussion et qui feint démontrer $ P(n) \quad \forall k \leq n, A^k . B = B$ par récurrence sur $n \in \mathbb N $.
- la propriété est vraie en zéro car $A^0B=B$
- on suppose qu'elle est vraie pour un entier $n$ naturel, et puis on calcule:
$ A^{n+1}.B=A. A^n . B= AB$ par hypothèse de récurrence mais ensuite on utilise la propriété pour $n=1$, à savoir $AB=B$.
Or cela n'est pas démontré.

Donc, le terme récurrence forte avertit que l'on va utiliser l'hypothèse de récurrence pour des valeurs possiblement distinctes de $n$; et il faut donc initialiser pour autant de valeurs distinctes.

C'est là que vient mon questionnement.

Quand on dit qu'il n'y a pas de récurrence forte mais juste une hypothèse de récurrence bien choisie, on démontre par récurrence sur $n$ naturel une propriété $Q(n) $ qui est :
$ P(0), P(1), ... , et P(n-1) $ impliquent $P(n)$.

Donc quand j'initialise, je dois démontrer que $P(0)$ implique $P(1)$ et je démontre $Q$ par récurrence sur $\mathbb N^*$. Est-ce une reformulation fidèle de ce que dit Gerard0?

gerard0 · April 2021

Bonjour Chelito.

Non, tu ne reformules pas ce que j'ai dit. Je disais qu'on ne doit pas utiliser la conclusion pour la prouver (rejet d'une pratique- et c'est vrai dans toute démonstration), tu dis qu'il faut faire ceci ou cela.
Que ce soit récurrence classique ou récurrence forte, on n'utilise que l'hypothèse de récurrence et éventuellement l'initialisation.

Pour la récurrence forte, on n'utilise que l'hypothèse de récurrence, donc on ne va pas initialiser en prouvant une implication. On prouve $(\forall p\in \mathbb N, p<n,\ P(p))\ \Rightarrow\ P(n)$ (*). Si pour faire cette preuve, on a besoin de P(0), voire de P(0), P(1),..P(10), on les prouve; mais parce que ça fait partie de la preuve.

Cordialement.

(*) propriété automatiquement vérifiée pour n=0. Pratique !

Chelito · April 2021

Merci beaucoup.

Que signifie cette flèche entre $P(p) $ et $P(n)$?

gerard0 · April 2021

Une erreur de frappe, je rectifie.
Mais c'est souvent la flèche simple qui est utilisée pour l'implication, donc il n'y avait pas vraiment d'erreur, ni de doute à avoir.

Cordialement.

Chelito · April 2021

Je te prie de m'excuser d'avoir fait une confusion entre ce que tu disais et d'autres interventions et je te remercie pour tes précisions.

gerard0 · April 2021

Pas de souci !

Cordialement.

SERGE_S · April 2021

@ acetonik
Tu veux démontrer que :

$\forall n \in N,\ P(n),$ où $P(n) = \forall A,\ \forall B \in M_p(K) ,\ A^nB = B$.

Pour $n = 0$, la proposition $\forall A,\ \forall B \in M_p(K),\ A^0B = B$ est trivialement vraie.
Soit $n \ge 1$ et supposons que
$\forall A,\ \forall B \in M_p(K),\ A^1B = B$
$\forall A,\ \forall B \in M_p(K),\ A^2B = B$
...
$\forall A,\ \forall B \in M_p(K),\ A^{n-1}B = B$

Est-ce qu'on peut démontrer que $\forall A,\ \forall B \in M_p(K),\ A^nB = B$ ?

La réponse est non. Pourquoi ? Parce que dans le pas d'induction le $n$ est arbitraire pourvu qu'il soit différent de zéro. Mais pour $n=1$ la proposition $P(1)$ n'est pas vraie. Donc tout tombe à l'eau. Le problème n'est donc pas le raisonnement par récurrence forte ou faible, le problème réside dans la falsité de la proposition $P(n)$ pour $n=1$. D'ailleurs il est impossible de démontrer que $P(0)\Rightarrow P(1)$ est vraie car $P(0)$ est vraie alors que $P(1)$ est fausse.

gerard0 · April 2021

Bonjour Serge_S.

Acetonik savait parfaitement ce qu'il faisait, et le dit dès le début : "Petit amusement du dimanche (désolé pour ceux qui connaissent)" (c'est moi qui souligne). Et vu son niveau mathématique (voir ses messages récents), il maîtrise parfaitement ce sujet. Alors pourquoi lui répondre 3 ans après ?

Cordialement.

Récurrence très forte

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 35