Démonstration par récurrence transfinie
Bonjour. Je voudrais être sûr d'avoir bien compris ce théorème (dit de démonstration par récurrence transfinie) :
On compare souvent ce théorème au théorème de récurrence sur $\N$, pourtant il me semble qu'il y a une différence importante : dans ce dernier on demande que l'hypothèse de récurrence $P(n) \Rightarrow P(n+1)$ soit vérifiée, mais aussi que $P(0)$ soit vérifiée. Alors que dans celui de récurrence transfinie on demande juste que l'hypothèse de récurrence soit vérifiée.
C'est bien cela ?
-
Soit $P$ une propriété définie dans un ensemble $(E, \le)$ bien ordonné. Si :
$\forall x \in E \ [\forall y < x , P(y)] \Rightarrow P(x)$
alors $P$ est vérifiée pour tout $x\in E$.
On compare souvent ce théorème au théorème de récurrence sur $\N$, pourtant il me semble qu'il y a une différence importante : dans ce dernier on demande que l'hypothèse de récurrence $P(n) \Rightarrow P(n+1)$ soit vérifiée, mais aussi que $P(0)$ soit vérifiée. Alors que dans celui de récurrence transfinie on demande juste que l'hypothèse de récurrence soit vérifiée.
C'est bien cela ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je me place dans $\N$.
Pour $x=0$, la proposition $ [\forall y < x , P(y)]$ prend la valeur Faux.
Donc l'implication $\forall x \in E \ [\forall y < x , P(y)] \Rightarrow P(x)$ prend la valeur Vrai.
De ce fait, présentée sous la forme de la récurrence transfinie, la récurrence sur \( \N \) ne nécessite pas d'initialisation.
Suis- je clair ?
e.v.
Pourtant j'ai un livre d'algèbre (niveau licence) qui dit, à propos du théorème dans $\N$, qu'il est quelque fois nécessaire de regrouper dans l'hypothèse de récurrence tous les niveaux jusqu'à $n$. C'est l'hypothèse de récurrence forte. Mais il faut quand même montrer que $P(0)$ est vraie. Or le théorème par récurrence transfinie ressemble au théorème de récurrence forte dans $\N$. D'où mon trouble. Cela ne sert donc à rien dans ce cas de prouver $P(0)$ ?
Si $R$ est une relation bien fondée sur $X$ et que $P$ est une propriété des éléments de $X$ telle que $P(x)$ dès que $P(y)$ pour tout $y \in X$ tel que $y R x$, alors $P(x)$ est toujours vérifiée. Quand $R$ est une relation d'ordre totale sur $X$, ça donne le principe énoncé dans le premier post.
On peut prendre $R$ la relation sur $\N$ définie par $n R m \iff n+1=m$. Dans ce cas, il y a deux "types" d'entiers : d'un côté $0$ et de l'autre, ceux qui ont un prédécesseur. Il faut alors montrer deux choses : la propriété pour $0$ et la propriété pour $n+1$ en la supposant pour $n$.
@ev La première proposition dont tu parles prend la valeur Vrai.
e.v.
Bonjour CPL. Je comprends ce que tu dis. Et ev dit d'ailleurs la même chose (je crois que sa première proposition prend bien la valeur Faux). Ce qui m'étonne c'est que l'énoncé sur le théorème de récurrence forte dans mon livre d'algèbre pour la licence est donc incorrect. Voici le texte de mon livre, il apparaît comme commentaire après l'énoncé du théorème de récurrence faible :
Lorsqu'il est nécessaire de regrouper dans l'hypothèse de récurrence tous les niveaux jusqu'à $n$, il faut alors démontrer que : 1) $P(0)$ est vraie 2) $\forall n \in \N \ [\forall p \le n \ \ P(p)] \Rightarrow P(n+1)$
Il ne faut pas croire tout ce qui est écrit dans les livres :-)
Je vous remercie pour vos réponses, toi et ev.
$$ \exists n: [P(n) \ et\ (\forall p<n: nonP(p))]$$
est la négation (logique classique) de :
$$ \forall n: [(\forall p<n: nonP(p))\to (nonP(n))]$$
et quand tu enlèves le "non" (P est quelconque), ça donne :
$$ \forall n: [(\forall p<n: P(p))\to P(n)]$$
Bonjour Martimax. Je crois que cette proposition est fausse, non vraie.
C'est pourquoi l'implication $[\forall y < x , P(y)] \Rightarrow P(x)$ prend la valeur vraie pour $x=0$.
Pour s'en convaincre, il suffit de poser $X = \{x \in E : y < x \text{ et } \lnot P(y) \}$
Et alors le théorème s'écrit :
Soit $P$ une propriété définie dans un ensemble $(E, \le)$ bien ordonné. Si : $\forall x \in E \ \ (X=\emptyset) \ \Rightarrow P(x)$ alors $P$ est vérifiée pour tout $x\in E$.
Mais je ne comprends toujours pas pourquoi l'initialisation $P(0)$ = vraie est déguisée, pour moi c'est une conséquence des équations logiques mais je ne sens pas d'intuition derrière.
Merci beaucoup.
Pierre
mon premier énoncé centré dit que $P$ a un plus petit élément
le deuxième qu'il n'en a pas
le troisième que nonP n'a pas de plus petit élément.
Si il n'y a aucun $y$ qui est $<x$, alors peu importe ce que tu me mets comme $P$, $\forall y< x, P(y)$ est vraie. Preuve : donne moi un $y<x$, je te montrerai que $P(y)$ (indication : tu ne peux pas m'en donner, donc je n'ai rien à faire :-D)
Tu as énoncé la contraposée du théorème je crois. C'est-à-dire si $P(n)$ n'est pas vérifiée pour tout $n \in \N$ alors il existe $n$ tel que $\lnot P(n) \text{ et } (\forall p<n:
P(p))$. C'est ça ?
Dans ce cas si $V$ est un ensemble et $F$ une propriété quelconque, l'énoncé
$$\left [\neg \exists y, y \in V \right ] \Rightarrow \left [ \forall x \in V, F(x)\right ]$$ devient une évidence grammaticale compte tenu de ce que (*) $\neg \neg C$ équivaut à $C$ pour tout énoncé $C$ puisque, une fois les abréviations dépliées et la règle (*) mise a contribution, on voit que cet énoncé dit la même chose que $$
\neg \left [\left ( \neg \exists y \left [ y \in V \right ] \right )\wedge \exists x \left ( x \in V \wedge \neg F(x) \right )\right ]
$$
En effet s'il n'y a aucun élément dans $V$, comment pourrait-il y avoir un élément dans $V$ qui de surcroît ne satisfait pas $F$?
Ensuite tu peux remplacer $V$ par $\emptyset$.
$$\left [\neg \exists y, y \in V \right ] \Rightarrow \left [ \forall x \in V, F(x)\right ]$$
Mais j'ai compris en sortant le symbole $\lnot$ des crochets. Je te remercie.
Ne peut-on pas dire aussi que $\forall x P(x)$ peut s'écrire $\forall x \in X$ en ayant préalablement posé $X=\{y \ | P(y)\}$ ?
Si $P$ est impossible on voit ainsi que $X$ est vide et $\exists x \in X$ est faux donc $\forall x P(x)$ est vrai. Est-ce correct ?
1/ $[(\exists xR(x))\to P]$ veut dire la même chose que $[\forall x(R(x)\to P)]$ et ce dans TOUTES les logiques actuellement connues, y compris les plus faibles (bien plus faibles que l'intuitionniste). Tu peux même considérer que ce n'est pas une équivalence mais une égalité à ce point de rapprochement.
2/ En particulier, avec $P:=faux$, on note généralement $\perp$ pour dire "faux", et on abrège $A\to \perp$ par $(non(A))$, ça te donne:
$$[(\exists xR(x))\to \perp] \iff [\forall x(R(x)\to \perp)]$$
c'est à dire
$$[non(\exists x R(x))] \iff [\forall x(non(R(x)))]$$
que l'on devrait probablement plutôt écrire raisonnablement:
$$[non(\exists x R(x))] = [\forall x(non(R(x)))]$$
A cause de la présence très en amont de cette équivalence.
A mes précédents posts, je n'ai pas eu le temps d'écrire en entier l'axiome de récurrence qui t'intéressait, je me suis contenté d'insister (je varie en te le faisant avec le signe $\in$) sur le fait que pour tout $A$:
c'est la même chose de dire : $non(\exists x:[x\in A\ et\ (\forall y<x: y\notin A)])$
que de dire :$ [ \forall x:[ (\forall y<x: y\notin A) \to (x\notin A) ] $
en notant $\to$ pour l'implication.
Ceci afin de te signaler que c'est un grand mot que de dire que c'est un théorème que l'axiome de récurrence (ou la définition de bon ordre) entraine l'énoncé qui est à l'origine du présent fil. Certes, c'est bien un théorème, mais il est parfaitement évident, ce n'est qu'une réécriture de la définition quasiment telle quelle.
Dire "toute partie non vide a un plus petit élément" c'est dire (et pas seulement "équivalent par théorème à dire"):
$$ \forall A: [(\forall x:[ (\forall y<x: y\notin A) \to (x\notin A) ] )\to (A\ vide) ]$$
edit, j'avais écrit $ \forall A: [(\forall x:[ (\forall y<x: y\notin A) \to (x\notin A) ] ) ]$ qui non seulement est faux, mais même plus, ne veut pas dire grand chose.
Sur le point (1) tu as écrit : $[(\exists xR(x))\to P]$ veut dire la même chose que $[\forall x(R(x)\to P)]$. Cela est vrai à condition que la variable $x$ ne figure pas dans l'énoncé de $P$ ? Ce qui est bien le cas dans l'exemple que tu prends ensuite.
En dernière partie tu écris que la formule :
$$ \forall A: (\forall x:[ (\forall y<x: y\notin A) \to (x\notin A) ] ) $$
revient à dire que toute partie $A$ possède un plus petit élément. J'ai du mal à comprendre pourquoi, ce ne serait pas plutôt sa négation :
$$\exists x:[x\in A\ et\ (\forall y<x: y\notin A)]$$
qui veut dire cela (il existe $x\in A$ tel que tous ses minorants stricts n'appartiennent pas à $A$).
$(A\ et\ := (\forall X :[(A\to (B\to X))\to X])$
$(A\ ou\ :=(\forall X: [(A\to X)\to ((B\to X)\to X)])$
$(\exists x: R(x)) := (\forall Z: [(\forall y:(R(y)\to Z))\to Z])$
Tu as deux "et", je ne t'ai donné que le plus usité.
C'est de là que résulte (entre autre) la "profonde quasi-égalité" entre $[(\exists xR(x))\to P]$ et $\forall x[R(x)\to P]$
Je te rappelle aussi que "l'abréviation" $(non(A)):=(A\to Tout)$ peut en fait "se démontrer" quasiment dans les plus faibles logiques, donc ne peut pas être sujette à doutes importants (j'abrège $\perp :=Tout$).
$$[non(A)] = [(non(\perp)) \to (non(A))] = [A\to \perp]$$
Les logiques classiques et intuitionnistes (et autres logiques) sont définies comme suit:
L'ensemble des phrases, noté $P$ est doté d'un ordre noté $\leq$, complet (tout ensemble a une borne inf) et d'un élément $1$ et vérifie, pour toutes phrases $A,B,C$:
$(1\to A) = A$
$A\leq B$ si et seulement si $1\leq (A\to $
$[A\to (B\to C)]=[B\to (A\to C)]$
$\to$ est croissant à droite et décroissante à gauche
Les théorèmes sont les éléments $\geq 1$
- Si tu ajoutes l'axiome : $\forall X: X\leq 1$, tu obtiens la logique dite AFFINE (ainsi en logique affine il n'y a qu'un théorème: $1$)
- Si tu ajoutes à la logique affine l'axiome : $\forall X, Y: ( [X\to (X\to Y)]\leq [X\to Y])$, tu obtiens la logique dite INTUITIONNISTE
- Si tu ajoutes à la logique intuitionniste l'axiome $\forall X,Y: [((X\to Y)\to Y) = ((Y\to X)\to X)]$, tu obtiens la logique dite CLASSIQUE.
La science se fait en logique classique. Tes études se sont déroulées en logique classique par exemple.
- Posée comme elle est, ta question laisse penser que tu n'as pas cerné la différence fondamentale entre la récurrence "simple" et la récurrence forte. La première n'est valide que dans le cas où chaque élément (sauf 0) a un prédécesseur, donc dans le cas où ton ensemble bien ordonné est isomorphe à $(\mathbb{N}, \leq )$ ou un de ses segments initiaux (lui-même ou un ensemble fini), tandis que la récurrence forte est valide pour tout ensemble bien ordonné (si tu es au-delà de $\mathbb{N}$ il y aura au moins un élément sans prédécesseur, le premier d'entre eux est le plus petit élément plus grand que tout les entiers naturels, il existe car l'ensemble est bien ordonné).
- Ici vous vous êtes surtout concentré sur le fait qu'en utilisant cette formule on peut se passer d'une formule d'initialisation, c'est exact, mais si on est pas habitué, il faut faire super attention à plusieurs raccourcis qui ont été utilisés ici, et dont les gens déjà très à l'aise avec la logique font abstraction (alors que ça peut méchamment bloquer les néophytes).
Tu as écris à peu près cela:
$\forall x\in E \left( \left[\forall y <x \rightarrow P(y) \right] \rightarrow P(x) \right) $
On notera d'une part que quand on écrit $y<x$ c'est que y appartient à E (sinon la relation d'ordre n'a pas été définie) et les trucs du genre $\forall x \in E(F(x))$ (où F est une formule) sont en fait un raccourci pour dire $\forall x (x\in E \rightarrow F(x))$ (et pour la petite histoire, quand tu écris $\exists x\in E (F(x))$ ça signifie $\exists x (x\in E \wedge F(x) )$ ).
Une formule "grammaticalement correcte" pour les règles de logique classique (dit aussi "calcul des séquents") ressemblerait plutôt à cela:
$ \forall x \left( x\in E \rightarrow \left[ \left(\forall y \left[y \in E \rightarrow \left(y<x \rightarrow P(y)\right) \right] \right) \rightarrow P(x) \right] \right)$
C'est à partir de cela que tu dois utiliser cette histoire d'hypothèse vide comme l'ont au début proposé ev et Champ-au-Lion, mais les premières fois, ce n'est pas évident et tu as donc tout intérêt à "transformer" cette formule de manière à avoir un machin qui te rendra plus évidente cette hypothèse vide, d'une part en mettant les implications sous formes disjonctives au niveau de $ y \in E \rightarrow \left(y<x \rightarrow P(y)\right) $ ( tu dois obtenir un truc dans ce goût-là: $\neg y\in E \lor \neg y<x \lor P(x) $, si je ne me trompe pas sur les conventions de priorités entre la négation et les opérateurs binaires ) et ensuite, comme ça a été proposé d'utiliser notamment ces histoires de négation et de quantificateur pour montrer que la formule est en fait équivalente à ce machin-là:
$\forall x\left( x\in E\rightarrow \left[ \left( \neg\exists y[y\in E \wedge y<x\wedge \neg P(y)]\right) \rightarrow P(x)\right]\right)$
Et là, ça pose moins de problème car la formule $\neg\exists y[y\in E \wedge y<x\wedge \neg P(y)]$ est évidemment vrai pour $x=0$.
Pierre
$\exists x\in A: B$ est une abréviation de $\exists x: ([x\in A]\ et\ $
$\forall xRt: B$ est une abréviation (très abusive) de $\forall x: ([xRt]\to $
$\exists xRt: B$ est une abréviation de $\exists x: ([xR t]\ et\ $
C'est tout.
D'autre part, comme le signale à juste titre TitiLC, on t'a écrit en espérant que tu saurais où se trouvent les tacites $\forall x\in A$, en écrivant $\forall x$ à la place, parce que c'est sacrément chronophages sinon. Mais n'hésite pas à demander si tu vois un $\forall x$ et que tu te demandes quel $<<\in A>>$ est sous-entendu.
Tu utilises souvent le symbole " : " peux-tu me dire s'il a une signification particulière, ou si c'est juste un séparateur ? Car je l'ai aussi souvent vu dans les formules décrivant un ensemble comme $E=\{x\in X : P(x)\}$