Démonstration par récurrence
Bonjour, j'ai rencontré lors de ma terminale des démonstrations par récurrence.
Existe-il des théorèmes où il n'y qu'une démonstration: celle par récurrence ?
Aussi, peut-on montrer qu'il existe des théorème mathématique qui ne peuvent être montrés que par récurrence?
Sinon, peut-on prouver que si on montre par récurrence un théorème alors il existe un autre moyen de démontrer un théorème?
Merci d'avance.
Existe-il des théorèmes où il n'y qu'une démonstration: celle par récurrence ?
Aussi, peut-on montrer qu'il existe des théorème mathématique qui ne peuvent être montrés que par récurrence?
Sinon, peut-on prouver que si on montre par récurrence un théorème alors il existe un autre moyen de démontrer un théorème?
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si tu travailles uniquement en arithmétique, alors la théorie de Peano sans l'axiome de récurrence est strictement moins forte que la théorie de Peano avec axiome de récurrence et donc il y a des théorèmes que l'on peut démontrer par récurrence que l'on ne peut pas démontrer sans. Il me semble (là je ne suis plus persuadé) que la commutativité de l'addition est un tel exemple.
Si tu es dans une théorie plus forte, comme la théorie des ensembles par exemple, la réponse peut différer. En theorie des ensembles le principe de récurrence est un théorème, pas un axiome, et du coup on peut toujours éviter la récurrence, ne serait-ce qu'en la redémontrant dans le cas particulier en question, ou en effectuant un raisonnement par l'absurde
> principe de récurrence est un théorème, pas un
> axiome, et du coup on peut toujours éviter la
> récurrence, ne serait-ce qu'en la redémontrant
> dans le cas particulier en question, ou en
> effectuant un raisonnement par l'absurde
Donc, en pratique, il n'existe aucun théorème mathématique, qui n'ait de démonstration que par récurrence?
Ou alors on sait qu'une autre démonstration, mais on l'a pas encore trouvé?
Ottman, du coup il existe des théorèmes démontrés uniquement par récurrence? Et où on a montré qu'ils ne peuvent l'être que comme tel?
Merci pour vos réponses.
Soient les axiomes:
1) tout objet $x$ a un unique successeur $s(x)$.
2) l'objet $A$ n'est le successeur de personne.
2') si un objet $x$ n'est le successeur de personne alors $x=A$.
3) pour tout $x$ et tout $y$ on a:
3.1) $x*y=y*x$.
3.2) $x*A=x$.
3.3) $s(x*y)=s(x)*y$.
4) pour tout $x$, tout $y$ et tout $z$ on a $(x*y)*z=x*(y*z)$
Alors la proposition "pour tout $x$ il existe $y$ tel que $x=y+y$ ou $x=s(y+y)$" n'est pas une conséquence de ces axiomes.
En effet, considérons $M$ l'ensemble des couples $(z,k)$ où $k$ est un entier naturel et $z$ est un entier relatif, qui de plus est positif si $k=0$.
Dans $M$ on définit:
-$A=(0,0)$.
-$s(z,k)=(z+1,k)$.
-$(z,k)*(y,j)=(z+y,k+j)$.
Il est facile de voir que $M$ muni de cette structure vérifie tous les axiomes mais pas la proposition (en effet, si $k$ est impair alors pour n'importe quel $z$ le couple $(z,k)$ est un contre-exemple).
En revanche si on ajoute à notre axiomatique le schéma de récurrence:
5) pour toute proposition $P$ si pour tout $x$ on a $P(x)$ implique $P(s(x))$ et si de plus $P(A)$, alors pour tout $y$ on a $P(y)$.
alors la proposition devient un théorème (exercice: le faire) (en particulier $M$ ne vérifie plus cette nouvelle axiomatique). Pour prouver ce théorème on est obligé d'utiliser 5), sinon il serait encore vrai dans $M$.
Bref par contre un théorème prouvable uniquement par récurrence bof ^^ (après en prenant en compte uniquement la théorie des entiers de Peano c'est possible mais je ne vois pas,)
Soit $R$ une relation de $E$, on écrira parfois dans la suite "$xRy$" à la place de $(x,y) \in R$ pour dire $(x,y)$ appartient à $R$.
$R$ est dite bien fondée si pour toute partie non vide $F$ de $E$, il existe $m\in F$ tel que pour tout $x\in E$, si $(x,m)\in R$ alors $x\notin F$ (en termes plus imagés, toute partie non vide "possède un élément minimal" au sens de $R$).
-Par exemple l'ensemble des $(n,n+1)$ dans $\N^2$ est une relation bien fondée (découle du fait que si $F\subseteq \N$ est non vide, il y a un plus petit élément dans $F$).
-l'ordre lexicographique strict sur $\N^d$
-L'appartenance est une relation bien fondée dans les ordinaux.
-Dans l'ensemble des fermés de Zariski de $K^n$ ($K$ est par exemple un corps commutatif), l'inclusion stricte est bien fondée.
(ces deux derniers exemples ne sont pas du niveau terminale certes...)
-Soit $(E,R)$ un couple avec $R$ une relation sur $E$. Si $x\in E$, soit $S_x:=\{y\in E\mid (y,x)\in R\}$.
Propriété de récurrence: On suppose que $R$ est bien fondée. Soit $P$ un sous-ensemble de $E$ tel que pour tout $x\in E$, si $S_x\subseteq P$ alors $x\in P$.
Alors $P=E$.
Preuve: Par l'absurde: sinon $P\backslash E$ n'est pas vide et il existe donc $m\in E\backslash P$ tel que pour tout $x\in E$, $(x,m)\in R\implies x \notin E\backslash P$ c'est-à-dire $x\in P$. Autrement dit $S_m\subseteq P$ et donc $m\in P$. Contradiction.
Soit maintenant $H$ un ensemble quelconque(*).
Soit $\mathcal F:=\coprod_{x \in E} H^{S_x} (= \bigcup_{x \in E} \{x\} \times H^{S_x})$.
On a la propriété suivante: soit $\varphi: \mathcal F\to H$ une fonction. Alors si $R$ est bien fondée, il existe une unique fonction $g: E\to H$ telle que pour tout $x\in E, \varphi \left ((x,g|_{S_x}) \right)=g(x)$
En l'espèce, $g$ est dite définie par induction (ou par récurrence) à partir de $\varphi$ et de $R$.
Dans la suite, on notera $\varphi (g|{S_y})$ au lieu de $\varphi \left((y,g|{S_y} )\right)$ par abus de langage (ce qui ne posera jamais problème).
On donne la preuve plus loin après quelques préliminaires.
On appelle segment initial toute partie $A$ de $E$ telle que pour tous $x,y\in E$, si $(x,y)\in R$ et si $y\in A$ alors $x\in A$. $E$ est par exemple lui-même un segment initial de $E$. Toute réunion et toute intersection d'une famille de segments est un segment (trivial). Par définition, il est immédiat qu'une partie $B$ est un segment initial de $E$ si et seulement si pour tout $x\in B$, $S_x\subseteq B$. Notons, lorsque $A$ est un segment initial de $E$, $\mathcal F(A):=\coprod_{x\in A} H^{S_x }$ (de sorte que $\mathcal F=\mathcal F(E)$ avec la notation plus haut).
Si $A$ est un segment initial de $E$ (désormais on dira simplement "segment"), une fonction $f:A\to H$ sera dite inductive sur $A$ si pour tout $u\in A$, $\varphi(f|_{S_u})=f(u)$. Par exemple, une fonction $g: E\to H$ est inductive sur $E$ si et seulement si elle satisfait la propriété qu'on cherche présentement à montrer.
Lemme 1: pour tout segment $A$, si $f,g:A \to H$ sont inductives alors $f=g$.
En effet soit $K:=\{x \in A\mid g(x)\neq f(x)\}$. On veut prouver que $K=\emptyset$. Si ce n'est pas le cas, soit ($R$ étant bien fondée) $m\in K$ tel que pour tout $x\in E$, $(x,m)\in R\implies x\notin K$. Alors on en déduit immédiatement que $S_m\cap K=\emptyset$. En particulier, pour tout $y\in S_m$, $g(x)=f(x)$ donc $g(m)=\varphi(g|_{S_m})=\varphi(f|_{S_m})=f(m)$. Contradiction (NB: on pourrait aussi appliquer la propriété de récurrence en remarquant que les segments de $(A,R\cap A^2)$ sont tous des segments de $R$ et que $R\cap A^2$ est également bien fondée).
Corollaire: il y a au plus une seule fonction définie par récurrence sur $E$ à partir de $\varphi$ et de $R$.
Maintenant qu'on a l'unicité, montrons l'existence d'une telle fonction.
Remarque 2: Soient $A,B$ deux segments avec $A\subseteq B$ et $f:B\to H$ une fonction inductive. Alors $f|_A$ est inductive (évident).
Par suite, soient $C,D$ deux segments, $f:C\to H$ et $g:D\to H$ des fonctions inductives. Alors $f|_{C\cap D}=g|_{C\cap D}$. En effet, $C\cap D$ est un segment, et $f|_{C\cap D}$, $g|_{C\cap D}$ des fonctions inductives sur $C\cap D$ donc elles sont égales par le lemme 1.
Cela étant, soit $\mathcal I$ l'ensemble de toutes les segments de $E$ sur lesquel il existe une fonction inductive. Si $A\in \mathcal I$, notons $f_A$ l'unique (cf lemme 1) fonction inductive définie sur $A$. Soit $G:=\bigcup_{A\in \mathcal I} A$ (qui est un segment comme on l'a dit plus haut). Si $x\in G$ et si $A,B\in \mathcal I$ sont tels que $x\in A\cap B$, alors $f_A(x)=f_B(x)$ par la remarque 2 et donc on définit une fonction $f:G\to H$ en posant $f(x)=f_C(x)$ où $C$ est un élément de $\mathcal I$ contenant $x$.
On va conclure en montrant que $f$ est inductive et que $G=E$.
En effet soit $x\in G, A\in \mathcal I$ tel que $x\in A$. Alors pour tout $y\in S_x$, $y\in A$ et donc $f(y)=f_A(y)$, finalement $f(x)=f_A(x)=\varphi(f_A |_{S_x})=\varphi(f|_{S_x})$ et donc $f$ est inductive.
Si $G\neq E$, soit $p\in E\backslash G$ tel que pour tout $x\in E$, $(x,p)\in R \Rightarrow x\in G$ (ou ce qui revient au même, tel que $S_p\subseteq G$.) On pose $f'(x)=f(x)$ si $x\in G$ et $f'(p)=\varphi(f|_{S_p})$. Alors $G\cup\{p\}$ est un segment (et donc $f'$ est de facto inductive): en effet soit $z\in G\cup\{p\}$: si $z\in G$ on sait déjà que $S_z\subseteq G \subseteq G\cup\{p\}$ et si $z=p$ on a déjà dit que $S_p\subseteq G$.
Donc $G\cup \{p\}\in \mathcal I$ et donc $p\in \bigcup_{A\in \mathcal I} A=G$ (contradiction).
[size=x-small](*) à l'attention des fans perplexes de l'ensemble vide: il existe toujours un élément $a$ de $E$ tel que $S_a=\emptyset$ (ça va être un élément minimal de $E$); donc $H^{S_a}$ et en particulier $\mathcal F$ sont non vides. Ainsi si $H$ est vide, $\varphi:\mathcal F\to H$ ne peut pas exister.[/size]
Si on suppose l'axiome du choix on a l'équivalence, pour un couple $(E,R)$ avec $R\subseteq E^2$, entre:
1° $R$ est bien fondée.
2° Il n'existe aucune suite $(x_n)_{n\in \N}$ d'éléments de $E$ telle que pour tout $n\in \N$, $(x_{n+1},x_n)\in R$.
(bref on ne peut pas "descendre indéfiniment dans $E$")
http://www.les-mathematiques.net/phorum/read.php?16,1265877,1265915#msg-1265915
ce fil est très intéressant, il (surtout la piste de SdOA) me permet de comprendre genre 8,9,10 ans après un exercice de cc s'agissant de la récurrence pur jus sur une des dualités pythagoriciennes : le pair et l'impair.
Ce qui me gêne dans ta piste sieur Shah d'Ock Anonyme : tu énonces des axiomes mais pas de règles de déduction.
Ce serait marrant de trouver un modèle où $s(s(s(A)))$ s'écrit aussi bien $x*x$ que $s(x*x)$.
De ce que j'ai pu lire dans un "que sais-je ?" (-> rien) nouvelle génération (ben rien de nouveau, je sais toujours rien) Pythagore et les Pythagoriciens, $1$ n'était ni pair ni impair, ni mâle ni femelle (ni limité ni illimité ?) et on ne parle pas de $A$ mais de $s(A)$.
S
Je réponds tardivement, je n'avais pas vu le fil, pardon: en maths (et en sciences) on déduit les théorèmes d'axiomes. L'axiome de récurrence en fait partie dans certaines théories. Les axiomes qu'on choisit de légitimer peuvent être considérés comme formant ce qu'on appelle "une théorie". Dans certaines théories l'énoncé de récurrence est pris comme axiome (et s'appelle alors l'axiome de récurrence) et dans d'autres non.
Parmi les théories qui ne le prennent pas comme axiome, il y a deux catégories:
1) celles où ce n'est pas utile car il est déjà un théorème de la théorie (car d'autres axiomes, plus forts, entrainent l'énoncé de récurrence).
2) Les autres.
La théorie en vigueur qui commande les maths (ZF(C)) n'a pas besoin de prendre comme axiome l'énoncé de récurrence car elle le démontre.