Preuve : définition par récurrence
Bonjour ! :-)
J'essaie de construire dans $ZFC$ les ensembles de nombres habituels ainsi que leur structure, mais après avoir défini et montré les propriétés de base de plusieurs types d'objets (couple, produit cartésien, graphe, relation, fonction $-$ pour moi synonyme du mot "application", $\mathbb{N}$, application successeur $s$) et après avoir prouvé le schéma de théorèmes de récurrence, je bloque pour démontrer que l'on peut définir une suite par récurrence (eh oui, sans ça, pas d'addition (:P)).
On considère un ensemble $E$, un élément $a$ de $E$ et une application $h$ de $\mathbb{N} \times E$ dans $E$.
On veut montrer qu'il existe une unique application $f$ de $\mathbb{N}$ dans $E$ vérifiant $f(0)=a \wedge \forall n \in \mathbb{N},\ f(s(n)) = h(n,f(n))$.
Pour l'unicité, une récurrence suffit.
Pour l'existence, j'ai d'abord défini $\mathscr{G}$ (par compréhension) comme $\{\ G \in \mathcal{P} (\mathbb{N} \times E)\ |\ (0,a) \in G \wedge [\forall n,\ \forall e,\ (n,e) \in G \Rightarrow (s(n),h(n,e)) \in G]\ \}$.
Ensuite, comme $\mathscr{G}$ est habité (il comprend $\mathbb{N} \times E$) je note $f$ le triplet $(\mathbb{N},E,\cap \mathscr{G})$.
Il reste à montrer que $f$ est bien une application, et qu'elle convient alors (cela découlerait de la définition de $\mathscr{G}$).
Par récurrence, on démontre facilement $\forall n \in \mathbb{N},\ \exists e \in E,\ (n,e) \in \cap \mathscr{G}$.
Là où je bloque, c'est pour démontrer $\forall n \in \mathbb{N},\ \forall e \in E,\ \forall e' \in E,\ [(n,e) \in \cap \mathscr{G} \wedge (n,e') \in \cap \mathscr{G}] \Longrightarrow e=e'$.
Peut-être n'ai-je pas pris la bonne définition du graphe de $f$ ?
Merci d'avance pour vos réponses ! :-D
J'essaie de construire dans $ZFC$ les ensembles de nombres habituels ainsi que leur structure, mais après avoir défini et montré les propriétés de base de plusieurs types d'objets (couple, produit cartésien, graphe, relation, fonction $-$ pour moi synonyme du mot "application", $\mathbb{N}$, application successeur $s$) et après avoir prouvé le schéma de théorèmes de récurrence, je bloque pour démontrer que l'on peut définir une suite par récurrence (eh oui, sans ça, pas d'addition (:P)).
On considère un ensemble $E$, un élément $a$ de $E$ et une application $h$ de $\mathbb{N} \times E$ dans $E$.
On veut montrer qu'il existe une unique application $f$ de $\mathbb{N}$ dans $E$ vérifiant $f(0)=a \wedge \forall n \in \mathbb{N},\ f(s(n)) = h(n,f(n))$.
Pour l'unicité, une récurrence suffit.
Pour l'existence, j'ai d'abord défini $\mathscr{G}$ (par compréhension) comme $\{\ G \in \mathcal{P} (\mathbb{N} \times E)\ |\ (0,a) \in G \wedge [\forall n,\ \forall e,\ (n,e) \in G \Rightarrow (s(n),h(n,e)) \in G]\ \}$.
Ensuite, comme $\mathscr{G}$ est habité (il comprend $\mathbb{N} \times E$) je note $f$ le triplet $(\mathbb{N},E,\cap \mathscr{G})$.
Il reste à montrer que $f$ est bien une application, et qu'elle convient alors (cela découlerait de la définition de $\mathscr{G}$).
Par récurrence, on démontre facilement $\forall n \in \mathbb{N},\ \exists e \in E,\ (n,e) \in \cap \mathscr{G}$.
Là où je bloque, c'est pour démontrer $\forall n \in \mathbb{N},\ \forall e \in E,\ \forall e' \in E,\ [(n,e) \in \cap \mathscr{G} \wedge (n,e') \in \cap \mathscr{G}] \Longrightarrow e=e'$.
Peut-être n'ai-je pas pris la bonne définition du graphe de $f$ ?
Merci d'avance pour vos réponses ! :-D
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Juste une remarque en passant :
On montre par récurrence : "pour tout entier n, il existe une unique application f : N $\rightarrow $ N telle que f(0) = n et f(x+) = f(x)+ pour tout entier x"
On peut noter fn cette unique application et définir n+m par fm(n).
Ce qui, entre parenthèses, permet d'introduire la relation d'ordre sur N et de démontrer directement la construction plus générale par induction (qui justifie par exemple la construction de suites définies par une relation de récurrence sur plusieurs valeurs antérieures).
Mais j'aimerais quand même, éventuellement pour construire d'autres objets, prouver ce que j'ai écrit dans mon premier message.
En fait, je viens juste de penser à une autre preuve : on démontre par récurrence $\forall n \in \mathbb{N},\ \exists ! G \in \mathcal{P} (s(n) \times E),\ (0,a) \in G \wedge [\forall k \in s(n),\ \forall e,\ (k,e) \in G \Rightarrow (s(k),h(k,e)) \in G]$ $\wedge \forall k,\ \forall e,\ \forall e',\ [(k,e) \in G \wedge (k,e') \in G] \Longrightarrow e=e'$.
Par remplacement, on définit l'ensemble de ces "$G$", puis on montre par récurrence que son union convient comme graphe de $f$ (il faudra que je l'écrive pour être sûr).
Edit : Merci Maxtimax pour le $k<s(n)$.
J'ai aussi oublié un $\mathcal{P}$.
En réalité tu n'as pas besoin d'invoquer le remplacement (ce serait terrible ! Invoquer le remplacement pour de l'induction ?), une fois que tu as ta formule (à $\epsilon$ près) tu peux définir explicitement la fonction $\mathbb N\to E$ obtenue.
Une fonction $f$ d'une partie de $\N$ dans $E$ va être dite dans la suite de ce message, $h$-inductive si
1°) Pour tous $x,y\in \N$, si $x$ est dans l'ensemble de définition de $f$ (noté $dom(f)$ dans la suite) et si $y\leq x$, alors $y\in dom(f)$.
2°) si $0\in dom(f)$ alors $f(0)=a$ et pour tout $n\in dom(f)$, si $s(n)\in dom(f)$ alors $f\left( s(n) \right )=h \left(n, f(n)\right)$.
On a les résultats:
I) si $f,g$ sont deux fonctions $h$-inductives, alors pour tout $n\in \N$, $n\in dom(f) \cap dom(g) \Rightarrow f(n)=g(n)$.
La preuve est immédiate par récurrence sur $n\in \N$ (penser à rester strict et formel).
II) La réunion de l'ensemble de toutes les fonctions $h$-inductives est une fonction $h$-inductive.
Soient $u$ cette union, et $x,y,z$ tels que $(x,y)\in u$ et $(x,z)\in u$. Alors il existe $f,g$ $h$-inductives telles que $(x,y)\in f$ et $(x,z) \in g$. Mais alors, comme $x\in dom(f)\cap dom(g)$, $y=f(x)=g(x)=z$ par I) ci-dessus. On en déduit que $u$ est une fonction.
Montrons que $u$ satisfait les conditions 1°) et 2°) du haut du post.
Il est clair que $dom(u)$ est la réunion des $dom(f)$ où $f$ parcourt l'ensemble de toutes les fonctions $h$-inductives, et 1°) en découle.
Pour 2°): si $0\in dom(u)$ alors $0\in dom(f)$ où $f$ est $h$-inductive. donc $(0,a)\in f \subseteq u$ et comme $u$ est une fonction, $u(0)=a$.
Soit $n\in dom(u)$ tel que $s(n)\in dom(u)$; soit $g$ $h$-inductive telle que $s(n)\in dom(g)$ (et donc $n\in dom(g)$ par 1°).
Alors $\left ( n,g(n) \right ) \in u$ et donc $g(n)=u(n)$ ($u$ étant une fonction) et de même $\left (s(n), g\left (s(n)\right ) \right )\in u$ et donc $g\left ( s(n) \right )=u\left ( s(n)\right )$. Finalement on a $u\left ( s(n)\right ) = g\left ( s(n)\right )=h\left (n,g(n) \right )=h\left (n,u(n) \right )$ ce qui conclut la preuve de ce que $u$ est $h$-inductive.
III) $dom(u)=\N$.
(i) $0\in dom(u)$, en effet le singleton $\{(0,a)\}$ est une fonction $h$-inductive (appliquer les définitions).
(ii) Soit $n\in dom(u)$. Soit $f$ $h$-inductive telle que $n\in dom(f)$. Soit $\varphi$ l'ensemble des couples $(p,q)$ tels que $p\leq n$ et $(p,q)\in f$, ou bien $p=s(n)$ et $q=h\left (n,f(n) \right )$. On vérifie immédiatement que $\varphi$ est une fonction $h$-inductive. Par suite $\left (s(n),\varphi \left ( s(n)\right ) \right )\in u$ et donc $s(n)\in dom(u)$.
En résumé, (i) et (ii) disent que $0\in dom(u)$ et pour tout entier $n\in \N$, $n\in dom(u) \Rightarrow s(n)\in dom(u)$, donc par récurrence, tout entier est dans $dom(u)$.
On dit que $u$ est la "suite définie par récurrence à l'aide de $h$ (et de la condition initiale $u(0)=a$)" ou expressions en prose équivalentes. L'unicité d'une telle $u$ est la conséquence du résultat I) plus haut.
[size=x-small]Remarque culturelle: toute ressemblance avec les résultats d'équations différentielles ordinaires et notamment l'existence de solutions maximales n'est ni fortuite ni involontaire. Les suites récurrentes sont en quelque sorte des solutions "d'EDO discrètes" (à moins que le second concept soit le pendant continu du premier). Et puis vous avez les résultats de discrétisation à la Euler. Noter qu'on peut aussi exprimer et prouver les résultats dans les deux cas avec des points fixes! Un parallèle intéressant à explorer à mon avis.[/size]
Certes, mais une remarque éthique et non pas culturelle s'impose.
La preuve que
$$\exists u\forall n: u(n+1)=f(u(n))$$
a tendance dans le marasme du pédagogisme à avoir été considérée comme "inutile à diffuser" sous le prétexte que l'énoncé serait évident.
Ce qui n'est pas vraiment le cas pour les solutions max d'équa diff.
Avec une conséquence c'est que sur 1000 profs du secondaire interrogés du secondaire, en charge de classes de premières; terminales, probablement pas plus de 5 te fournirait une preuve. (Et j'insiste que malgré les airs cabalistiques, vu de loin, des posts complets de foys, il s'agit d'un exercice quasi-évident à la condition de respecter la science qu'on doit prouver ce qu'on dit et ne pas surcharger au doigt mouillé en axiome ses exposés).
Je rappelle que l'unique suite $u$ telle que $u(0)=a$ et $u\circ s = f\circ u$ est l'ensemble des couples $(n,x)$ tels qu'il existe une suite finie $v$ définie sur un segment initial de $\N$, vérifiant $v(0)=a$ et $\forall p: v(p+1)=f(v(p))$ ou $n+1\notin dom(v)$ telle que $v(n)=x$.
Maxtimax, effectivement c'est beaucoup mieux avec $k<s(n)$, mais je n'ai pas encore défini l'ordre (la transitivité me posant problème avec $\in$, je voulais passer par l'addition).
J'essaierai en remplaçant par $k \in s(n)$, mais je ne suis pas sûr d'y arriver.
Sinon, je peux toujours faire comme l'a dit GG, puis définir l'ordre, et enfin revenir à la définition par récurrence.
Ah effectivement, par compréhension ça marche bien puisque le graphe est une partie de $\mathbb{N} \times E$, mais quand on a goûté au remplacement, difficile de s'en défaire ! À vrai dire, j'ai même défini le produit cartésien par double remplacement plutôt que par le double ensemble des parties de l'union !
Foys, merci pour cette autre preuve, je l'étudierai si je bloque !
Christophe C, merci pour cette définition, mais je n'aime pas trop réduire une fonction à son graphe, même si on pourrait alors définir son domaine et son image. Je préfère le point de vue mathématique habituel ^^
pour répondre précisément à la question de ton premier message, c'est oui, tu as choisi la bonne définition du graphe de f !
Je note x+ s(x), et K l'intersection de tes parties G de N x E.
Une seule récurrence suffit pour montrer que K est un graphe fonctionnel de domaine N et d'image dans E, à savoir que pour tout n dans N, il existe un unique v dans E tel que (n, v) soit dans K :
vrai pour n = 0 : (0, a) est dans tous les G, donc dans K. S'il existait (0, b) dans K avec b $\neq $ a, tu vérifies que K \ { (0, b) } est l'un des G, donc K $\subset $ K \ { (0, b) }, absurde.
On suppose vrai pour n. Soit v l'unique élément de E tel que (n, v) soit dans K.
(n+, h(n, v)) est dans tous les G, donc dans K. S'il existait (n+, w) dans K avec w $\neq $ h(n, w), tu vérifies également que K \ { (n+, w) } est l'un des G, absurde.
Je suis tout à fait d'accord que « c'est normal de prouver en maths ». Et une fois la suite de Fibonacci définie comme je viens de le faire, et comme on le fait depuis toujours, il reste pas mal de choses à « prouver », sans se farcir au préalable trente lignes de logique indigeste pour prouver ce que tout le monde voit, que cette suite est bien définie comme j'ai dit et comme tout le monde dit.
Maintenant, sans doute cette démonstration d'existence de cette suite a-t-elle son intérêt pour les amateurs de logique, et loin de moi le désir de les en détourner ni de leur interdire quoi que ce soit. Mais pour ceux qui pratiquent l'une des autres dizaines de spécialités mathématiques, eh bien, on définit la suite et ensuite on se pose les vrais problèmes mathématiques qu'elle soulève, et ils sont légion.
Bien sûr le problème de l'existence d'une suite se pose lorsque la fonction « de transfert », d'un terme en fonction des précédents, n'est pas partout définie, comme une suite homographique par exemple, et se pose alors légitimement le problème des valeurs initiales pour lesquelles la suite existe comme suite infinie. Ce n'est pas un problème de logique mais de tel ou tel des autres multiples secteurs des mathématiques proprement dites, algèbre, analyse, et tout ça.
Bonne soirée.
Fr. Ch.
Du coup on fait la preuve une fois pour toute que le genre de définition que tu proposes a un sens, et après comme tu dis on peut passer à autre chose - mais il faut bien le faire une fois, sinon on est bien embêté pour expliquer pourquoi on a pris $\mathbb N$ et pas autre chose.
C'est moi, pas toi pour le rouge et les numéros. (Au passage, je n'ai pas eu l'occasion de te le dire et suis peu dispo, mais très heureux de ta victoire -- santé!!)
(1) je ne dirais pas "normal" mais tautologique ou "par définition". Cependant, quand tu ne prouves pas, tu peux toujours admettre avec le statut d'hypothèse ce que tu as admis, donc pas de souci. Par contre, il s'agit, et je crois que tu es attaché à ça, de l'utilisation de la langue franco-mathématique. Il est incorrect de dire "soit la suite définie par", car cette tournure n'a pas une structure honnête d'hypothèse, puisqu'elle tente de vendre comme un "allant de soi au statut hybride" une hypothèse dogmatique (tant qu'elle n'est pas prouvée) assez sulfureuse et inutile.
Tu peux parfaitement devenir correcte en disant "je suppose que $u$ est une suite telle que" en attendant. Je ne t'attaque pas sur l'idée que ça doit forcément s'accompagner d'une preuve d'existence. Il n'y a strictement aucun besoin qu'elle existe pour tes déductions. Par contre, ton message (je sais bien que tu ne dis pas ça) peut faire croire à des néophytes que tu as besoin de l'unicité, et tout ça à cause de l'ambiguité de la tournure idiote et pédagogiste "soit la suite définie par"
(2) Non, pas tout le monde, hélas. Les monde des matheux est très fermé, très autiste, même si très respectable. Dans la filigrane de ton post, tu es presque trop (et excessivement) "gentil" dans un sens acide avec la logique, puisque tu vends ou veux y mettre les entiers naturels. Or les entiers naturels méritent "mieux" que (et comme chacun sait je n'ai rien contre les logiciens :-D ) d'être sous-entendus monopole du logicien.
(3) Là je pense que tu te trompes sur les gens. Ce sont plutôt des professionnels qui vont t'emmerder avec une preuve d'existence et d'unicité d'une telle suite. Ou en tout cas, des gens "sérieux" et en voie de professionnalisation JUSTEMENT. Et de toute façon, c'est un problème de maths, de niveau "correcte", comme TOUS LES PROBLEMES DE MATHS si on définit le niveau par la capacité des gens à réussir cet exercice. J'insiste bien que TOUTES LES MATHS consiste à "psychanalyser pourquoi on est sûr de telle ou telle chose", pas juste la logique. Et plein sont ouverts actuellement. Et ILS SONT TOUJOURS résolus de la même façon: un gugus a réussi à "tellement psychanalysé pourquoi il en était sûr' qu'il a réussi à l'encoder dans une preuve irréfutable (appelée "démonstration mathématique"). Le reste, c'est de la physique. Alors il est vrai qu'à l'époque des ordis qui cherchent tout seuls, ça change un peu la donne mais c'est une autre affaire.
Aussi je n'approuve pas un propos comme le tien (je ne dis pas que tu ne peux pas faire cet exercice, mais des amateurs passionnés d'autre chose pourraient eux ne pas y arriver) qui PEUT SEMBLER malgré tes précautions légitimer une déclaration comme "ce n'est pas que je n'y arrive pas, c'est que c'est sûr sans que je le prouve". Un tel propos donne l'impression qu'on peut ajouter des axiomes à coups de menton.
(4) Je pense que tu es dans le camp ultramajoritaire, mais je désapprouve ce camp consistant à rappeler que les labods de logique mathématique sont intégrés aux labos de maths au même titre que ceux de théorie des groupes ou d'analyse. Si bureaucratiquement, la logique est une spécialité des maths, elle n'en est pas une comme une autre, puisqu'elle la légifère. Et ces "agressions" intellectualo-statutaire contre la logique ont hélas eu comme effet collatéral le crash du secondaire français. Parfois les slogans politiques ont des conséquences lointaines.
(5) c'est quasiment un lapsus révélateur, on ne devrait pas trouver dans un examen la consigne qui demande une suite de phrases séparées par des donc dont la dernière serait
$$\exists ! u\in \N^\N : blabla $$
alors que c'est un exercice difficile pour 99% des étudiants, même s'il est évident certes pour les logiciens. En quoi la classification d'un problème de maths dans une spécialité le transformerait-il en faux problème de maths. Là encore, je ne dis pas que c'est ton propos, mais les pédagogistes se sont TOTALEMENT reposés sur des propos comme les tiens pour intrduire leurs délirés dans les écoles (expérimentation, etc).
En conclusion: je ne sais pas si tu en fais (tu m'as un peu parlé de ta vie, mais ne m'as pas renseigné sur ce point), je pense que la physique pourrait bien te passionner, car au fond on sent chez toi que le mot vrai veut dire "inspiré par une problématique issue de la physique" (enfin je peux me tromper, mais j'espère que tu fais de la physique!!)