Récurrence très forte - Page 2 — Les-mathematiques.net The most powerful custom community solution in the world

Récurrence très forte

2»

Réponses

  • 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.
  • @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.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • @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
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • 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?
  • 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 !
  • Merci beaucoup.

    Que signifie cette flèche entre $P(p) $ et $P(n)$?
  • 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.
  • 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.
  • Pas de souci !

    Cordialement.
  • @ 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.
  • 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.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!