Démonstration d’induction noethérienne

alaeshimi
Modifié (December 2023) dans Fondements et Logique
Bonsoir j'ai du mal avec la démonstration du principe  d’induction noetherienne suivante : 
Soit A l’ensemble des x ∈ E qui ne vérifient pas P ( x ) . Supposons A non vide. Il admet alors un élément minimal x . Ainsi, pour tout y<x , y non ∈ A , autrement dit, P ( y ) . D’après la condition d’hérédité, on a donc P ( x ) , or y rien qui prouve qu'il existe y < x.

Réponses

  • Foys
    Modifié (December 2023)
    Il n'y a pas besoin qu'il existe un tel $y$.  L'hypothèse $\forall y < x, P(y)$, i.e. $\forall y \left [y < x \Rightarrow P(y) \right ]$, signifie exactement (en logique classique) $\neg \left [ \exists y  \neg \neg \big ( y < x \wedge \neg P(y) \big ) \right]$ ou encore: $\neg\left [ \exists y \big ( y < x \wedge \neg P(y) \big ) \right] $(édité) (puisque "$A \Rightarrow B$":= $\neg (A \wedge \neg B )$ i.e.: il est impossible qu'à la fois $A$ arrive et $B$ n'arrive pas. Lorsque $A$ est faux cette circonstance est automatiquement vérifiée).

    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Merci pour votre réponse mais j'ai toujours du mal à comprendre, si x est le minimal de E alors y n’existe pas et je vois aucune condition qui exige que x est different de minimal de E
  • Foys
    Modifié (December 2023)
    J'ai édité mon message qui contenait une faute.
    Il n'y a aucun problème. On veut montrer que la négation de $\forall x P(x)$ est fausse.
    Supposons cette négation (*). Il y a un $x$ tel que $\neg P(x)$ (**) et qui est minimal avec cette propriété. La condition de noethérianité dit: pour tous $y<x$, si $P(y)$ alors $P(x)$ (***).  (***) ne dit pas autre chose que $\neg \left [ \left ( \neg \left [ \exists y, y<x \wedge \neg P(y)\right ] \right ) \wedge \neg P(x) \right ]$. Comme on a par hypothèse $\neg P(x)$, (***) entraîne $\neg \neg \left (\exists y, y<x \wedge \neg P(y) \right) $ et donc $\exists y, y<x \wedge \neg P(y)$. On a donc un $y$ tel que $\neg P(y)$ et $y<x$. Mais ceci contredit la minimalité de $x$ annoncée en (**). (*) n'est pas possible.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Congru
    Modifié (December 2023)
    Je dirais qu'il manque pas mal d'hypothèses pour le problème. Je félicite @Foys d'avoir quand même su combler les hypothèses manquantes.
    Serait-il possible que quelqu'un donne toutes les hypothèses manquantes à l'énoncé initial. (le problème a l'air intéressant).
    N.B. J'aurais bientôt besoin des avis de mes amis logiciens sur ce forum dans un nouveau fil.
  • Bonjour,
    L'hypothèse est qu'on a un ordre strict $(E,<)$ bien fondé : pour toute partie non vide $S$ de $E$, il existe $x\in S$ qui est minimal dans $S$, c.-à-d. qu'il n'y a aucun $y\in S$ tel que $y<x$.
    La terminologie "noethérienne" vient du fait qu'un anneau noethérien est un anneau commutatif dont l'ensemble des idéaux avec l'ordre opposé à l'inclusion stricte est bien fondé.
  • Merci @GaBuZoMeu. Ainsi, je comprends que l'initiateur du fil se pose le problème de démontrer le théorème d'induction.
    Je connais ce théorème sur les relations bienfondés-setlike dont la classe des ordinaux munie de l'appartenance restreinte est un cas particulier.
    Un problème culturel avec l'application de ce théorème, c'est que les utilisateurs n'arrêtent pas de confondre ce théorème avec le théorème de récurrence.
  • En quoi est-ce un problème culturel, puisqu'il s'agit bien d'un théorème de récurrence ?
  • Congru
    Modifié (December 2023)
    @GaBuZoMeu, il me semble que le théorème de récurrence dit que toute partie de $\mathbb N$ qui est inductive est égale à $\mathbb N$.
    Donc, on l'applique en montrant qu'une partie de $\mathbb N$ est inductive, ce qui implique par définition qu'on montre que $0$ appartient à cette partie et qu'on montre la stabilité de la partie par la fonction $successeur$.
    Tandisque le théorème d'induction dit que dans un bienfondé-setlike, si une proprité est héréditaire alors elle est vérifiée sur toute la classe de base du bienfondé-setlike. Ainsi, pour bien appliquer le théorème d'induction, il faudrait normalement commencer par dire "soit $\gamma $ tel que la propriété est vraie pour tout élément inférieur à $\gamma$". Ensuite, le but est de montrer que $\gamma $ vérifie la propriété.
  • GaBuZoMeu
    Modifié (December 2023)
    Soit $A$ un prédicat sur $\mathbb N$. Définissons $B(n)$ par $\forall p \leq n\ A(p)$.

    Si on a $A(0)$ et $\forall n\ (A(n)\implies A(n+1))$, alors on a $\forall n\ ((\forall p<n\ B(p)) \implies B(n))$ (raisonner suivant que $n=0$ ou $n$ est un successeur).
    Si on a $\forall n\ ((\forall p<n\ A(p)) \implies A(n))$, alors on a $B(0)$ et $\forall n \ (B(n)\implies B(n+1))$.

    Je ne vois donc pas pourquoi tu tiens tant à distinguer deux types de récurrence

  • Foys
    Modifié (December 2023)
    I) Soit $E$ un ensemble et $R\subseteq E^2$ une relation binaire (on écrira $R(x,y)$ à la place de $(x,y)\in R$). On dit que $R$ est bien fondée si pour toute partie non vide $A$ de $E$, il existe $m\in A$ tel qu'il n'existe aucun $x\in A$ tel que $R(x,m)$. Lorsqu'on est dans cette circonstance, on a le résultat d'induction suivant: soit $B$ une partie de $E$ telle que pour tout $x\in E$, si pour tout $y\in E$ tel que $R(y,x)$ on a $y\in B$ alors $x\in B$.
    Alors $B=E$ (car si le complémentaire $E\setminus B$ est non vide, il contient un $m$ comme dans la définition de "bien fondée" plus haut et on a une contradiction).
    Lorsqu'il est non vide, $E$ possède des éléments minimaux (appliquer la définition à $A:=E$), i.. des $x$ tels que $\{y \in E \mid R(y,x)\} = \emptyset$.
    Pour montrer l'hypothèse de récurrence (appliquée à $B\subseteq E$ dont on veut montrer qu'il est égal à $E$), on remarque que pour tout $t$ tel que $R(t,x)$, on a $t \in B$ (quantification universelle sur l'ensemble vide), autrement dit pour $x$ minimal, $\left (\forall y \in E, R(y,x) \Rightarrow y \in B \right ) \Rightarrow x \in B$ équivaut à $x\in B$ (on parle de "phase d'initialisation" d'une récurrence). 
    Le théorème d'induction précédent devient "si $H_1$ et $H_2$ alors $E = B$" avec $H_1:=$ "pour tout $x\in E$ minimal, $x\in B$" et $H_2:=$"pour tout $x\in E$ non minimal, si pour tout $y\in E$, $R(y,x) \Rightarrow y \in B$ alors $x\in B$".
    Exemple: lorsque $E:=\N$, la relation $R(x,y):= x+1 = y$ est bien fondée.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Congru
    Modifié (1 Jan)
    Vos remarques sont pertinentes.
    Mon unique problème dans la confusion des deux théorèmes c'est lorsqu'on "applique" le théorème d'induction en vérifiant la propriété d’abord sur les éléments minimaux avant de passer à l'hérédité:
    "soit $\gamma $ un élément minimal ....on a $P(\gamma )$, soit $\gamma$ non minimal tel que $\forall x(x<\gamma \implies P(x))$ ...on a $P(\gamma )$, donc par le théorème d'induction on a ..."
    Le théorème utilisé n'est pas le théorème d'induction, c'est son équivalent dont parle @Foys qui est utilisé.
  • Je ne comprends pas bien ce que tu écris. Ce que tu mets entre guillemets est un raisonnement foireux où on croit à tort qu'il faut faire une initialisation.
    Je prends l'exemple d'un résultat à démontrer : 
    Soit $(u_i)_{i\in I}$ une famille (qui peut être infinie) d'endomorphismes diagonalisables d'un espace vectoriel $E$ de dimension finie qui commutent deux à deux. Alors il existe une base de diagonalisation commune à tous les $u_i$.
    Pour montrer cette propriété, on montre que si c'est vrai pour tout espace de dimension strictement plus petite que $\dim(E)$, alors c'est vrai pour $E$. Je me souviens que pas mal d'agrégatifs avaient du mal à avaler ça et pensaient qu'il fallait faire une initialisation quelque part.
  • @GaBuZoMeu , je suis d'accord avec toi. Et ce que je dis c'est que le plus souvent, les utilisateurs du théorème d'induction font ce que j'ai écrit entre guillemets.
  • Foys
    Modifié (1 Jan)
    Je me souviens que pas mal d'agrégatifs avaient du mal à avaler ça et pensaient qu'il fallait faire une initialisation quelque part.

    Les gens ont souvent du mal à distinguer les propos qui sont (implicitement) niés de ceux qui sont affirmés dans un discours mathématique. 

    "Alice: on va démontrer que s'il existe un x tel que P(x) alors on a Q.
    Bob: Je ne comprends pas pourquoi il existerait un x tel que P(x)."

    C'est quasiment tout le temps de ça dont il s'agit.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
Connectez-vous ou Inscrivez-vous pour répondre.