Annuler
connectez vous
logique en post-bac
- Description de mathématique formelle-termes et relations
- Théorèmes
- Théories logiques
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Espaces vectoriels et Applications linéaires - supérieur
- Un best-of d'exos de probabilités (après le bac)
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup LogiqueTopics traitant de logique [tout]Lister tous les topics de mathématiques
Niveau Maths sup
Axiome de récurrence
Posté par 
Ramanujan
RamanujanBonjour,
Mon livre dit que : une application important des propriétés de que nous avons listées est le principe de récurrence qui affirme que :
Si est une partie de
contenant
et telle que :
alors
Sauf que je n'ai pas compris comment on déduit le principe de récurrence des propriétés ci-dessous en verte...
Une construction rigoureuse de l'ensemble des entiers sort du cadre de ce cours. Il est toutefois indispensable dans cet ouvrage de donner une liste exhaustive des propriétés admises qui nous permettrons de construire la suite.
1/ Toute partie non vide de possède un plus petit élément.
2/ Toute partie non vide majorée de possède un plus grand élément.
3/ n'est pas majoré.
Conséquences immédiates :
possède un plus petit élément noté 0.
Soit . Alors l'ensemble des entiers strictement plus grands que
est non vide (sinon
est un majorant de
) : son plus petit élément est appelé successeur de
:
Soit . Alors l'ensemble des entiers strictement plus petits que
est non vide (il contient 0) et majoré par
: son plus grand élément est appelé prédécesseur de
et est égal à
:
Le but de la démonstration par récurrence, c'est de démontrer que le prédicat P d'une variable entier naturel, est vrai.
Autrement dit que pour tout n entier naturel, P(n) (est vrai).
Dans ton théorème rappelé, A est une partie de quelconque.
Eh bien oui j'en prends une particulière.
Le principe de récurrence est démontré dans mon livre. C'est le suivant :
Soit un prédicat défini sur
. Si
est vrai et si
alors
est vraie pour tout entier naturel.
Sauf que ce n'est pas ça qui m'intéresse, j'aimerais comprendre comment prouver le résultat suivant qui est donné sans preuve dans mon livre :
Si est une partie de
contenant
et telle que :
alors
salut
peux-tu exhiber un entier qui ne soit pas dans A ?
peux-tu prouver que 10 000 appartient à A ?
Bonjour,
Soit le complémentaire de
dans
. Si
, alors la propriété est démontrée. Supposons
non vide. L'on sait alors que
posséderait un plus petit élément, noté
. D'autre part, vu que
,
serait distinct de
et posséderait donc un prédécesseur
strictement inférieur à tout élément de
. Ainsi aurait-on
, ce qui avec
donnerait finalement ; d'où une contradiction avec notre hypothèse. Ainsi a-t-on
nécessairement.
Ah pardon, je pensais que tu disais vouloir en déduire le principe de raisonnement par récurrence (ce qui n'est pas tout à fait la propriété énoncée par ailleurs).
On va donc démontrer cela sans le raisonnement par récurrence.
Supposons non vide ; c'est une partie de
et nous notons donc
(
car
). Par contraposition
, ce qui contredit la définition de
.
on peut même "utiliser la récurrence" pour montrer la récurrence sans même avoir à parler de minimum ou de maximum ou quoi que ce soit
si N/A n'est pas vide alors soit n un élément de N/A
considérons alors l'entier n - 1 :
alors il y a deux cas :
soit n - 1 appartient à N/A et on recommence avec n - 1
soit n - 1 appartient à A ... mézalor n - 1 +1 appartient à A
de toute façon ne pas utiliser la récurrence c'est en fait utiliser la récurrence parce qu'on ne monte pas mais on descend et que N a le bon gout d'être minoré donc on est obligé de s'arrêter à 0 (utilisation d'un minimum à un instant du raisonnement <=> descendre (= récurrence) jusqu'à ... l'absurde : la contradiction)
en espérant que Ramanujan saura ronger l'os et en tirer la substantifique moelle ...
ThierryPoma @ 07-07-2019 à 17:19
Bonjour,
Soit
le complémentaire de 
dans 
. Si 
, alors la propriété est démontrée. Supposons non vide. L'on sait alors que posséderait un plus petit élément, noté 
. D'autre part, vu que 
, serait distinct de 
et posséderait donc un prédécesseur 
strictement inférieur à tout élément de . Ainsi aurait-on 
, ce qui avec
donnerait finalement
; d'où une contradiction avec notre hypothèse. Ainsi a-t-on 
nécessairement.
Bonjour,
Soit
donnerait finalement
Merci beaucoup. Super démonstration, j'ai suivi pas à pas en réécrivant tout, j'ai réussi à tout comprendre !
Mathématiques MPSI - 5e édition
Tout-en-un
Collection : J'intègre, Dunod
Parution : février 2018
Claude Deschamps, François Moulin, André Warusfel, Nathalie Cleirec, Jack Michel Cornil et al.
J'ai une petite question dans la démonstration du théorème suivant :
Soit un prédicat défini sur
. Si
est vraie et si :
alors la propriété
est vraie pour tout entier naturel
.
Démonstration :
Supposons que n'est pas vérifiée sur
. Alors
est une partie non vide de
, elle admet donc un plus petit élément noté
.
Comme est vraie,
donc
. Comme
donc
.
est vraie donc
est vraie soit
d'où une contradiction.
Je n'ai pas compris l'intérêt de démontrer que .
Bonjour,
Si alpha = 0 , alpha - 1 n'appartient pas à N.
Or, P est défini sur N, donc on n'aurait pas pu écrire P (alpha - 1)
Ne vois-tu pas que c'est exactement la même démonstration que ce qu'on t'a proposé sur ta question précédente ?...
Confer mon premier message : une fois ta proposition démontrée, le principe de raisonnement par récurrence s'en déduit immédiatement.
Jezebeth @ 07-07-2019 à 16:39
Il te suffit de noter \right\})
.
Il te suffit de noter
Donc de deux choses l'une :
- ou bien ton livre fait d'abord cette démonstration du raisonnement par récurrence avant de caractériser l'ensemble des entiers naturels en disant que toute partie contenant 0 et étant inductive est cet ensemble entier.
Dans ce cas ton résultat originel est trivial, puisque si A contient 0 et est inductive, par récurrence A contient ... ;
- ou bien ton livre commence par la démonstration de la caractérisation, et pas besoin de se casser la tête, le principe de raisonnement par récurrence en découle tout seul.
Cela rejoint la remarque de carpediem ; de grâce, un peu de bon sens : ne faisons pas les mêmes raisonnements plusieurs fois et soyons logiques dans l'enchaînement des résultats établis.
lefou666 @ 07-07-2019 à 21:19
Bonjour,
Si alpha = 0 , alpha - 1 n'appartient pas à N.
Or, P est défini sur N, donc on n'aurait pas pu écrire P (alpha - 1)
Bonjour,
Si alpha = 0 , alpha - 1 n'appartient pas à N.
Or, P est défini sur N, donc on n'aurait pas pu écrire P (alpha - 1)
Merci !
@Jezebeth
Oui les démonstrations se ressemblent.
Le livre fait d'abord la caractérisation des entiers en listant les propriétés admises, puis il donne le principe de récurrence (sans le démontrer) qu'a démontré Thierry Poma et enfin il donne le théorème de la récurrence avec le prédicat (celui-ci est démontré).
Elles ne se ressemblent pas juste, elles sont identiques, j'insiste !
Et c'est un peu idiot comme présentation des choses, je trouve. (Mais bon, les Dunod ne sont pas réputés pour leur finesse mathématique !)
Jezebeth @ 07-07-2019 à 22:32
Elles ne se ressemblent pas juste, elles sont identiques, j'insiste !
Et c'est un peu idiot comme présentation des choses, je trouve. (Mais bon, les Dunod ne sont pas réputés pour leur finesse mathématique !)
Elles ne se ressemblent pas juste, elles sont identiques, j'insiste !
Et c'est un peu idiot comme présentation des choses, je trouve. (Mais bon, les Dunod ne sont pas réputés pour leur finesse mathématique !)
Ce livre me correspond très bien concernant ce point : "lorsque plusieurs preuves étaient possibles, nous avons choisi de ne pas privilégier systématiquement la plus courte, souvent au profit de constructions explicites."
Rebonjour,
Je rappelle le théorème 12 :
Soit un prédicat défini sur
. Si
est vrai et si
alors
est vraie pour tout entier naturel.
J'ai une nouvelle question concernant la récurrence à partir d'un entier . Je n'ai pas compris comment on applique le théorème 12. Déjà le théorème 12 commence par "si
est vraie" or ici le prédicat n'est pas défini pour
Si est défini sur
avec :
vraie et
Alors le théorème 12 appliqué à nous donne :
tu devrais aller voir des exemples concrets (= des exercices) pour mieux comprendre les choses ...
ainsi par exemple je te propose les deux exercices classiques qui permettent de bien distinguer ce qui se passe entre l'initialisation et l'hérédité :
EX 1 : Soit n un entier naturel et P(n) la proposition
1) vérifier P(n) pour n 
{0, 1, ..., 10}
2) Montrer que la proposition P(n) est héréditaire à partir d'un certain rang à déterminer.
4) Pour quels entiers la proposition est-elle vraie ? Justifier.
EX 2 : Soit n un entier naturel et P(n) la proposition
1) vérifier P(n) pour n {0, 1, ..., 10}
2) Résoudre dans IR l'inéquation
3) en déduire que la proposition est héréditaire à partir d'un certain rang à déterminer.
4) Pour quels entiers la proposition est-elle vraie ? Justifier.
@Carpediem
Avant de m'attaquer à vos exos, je vais essayer de démontrer le résultat général de la récurrence à partir d'un entier en utilisant la remarque de Lionel.
Posons :
Là je m'emmêle les pinceaux avec le
J'ai résolu les exos de mon livre facilement, j'ai des difficultés dans les démonstrations générales...
Exemple :
Montrer qu'à partir d'un certain rang on a :
J'ai réussi à appliquer le principe de récurrence à partir d'un
SI je veux appliquer le théorème à . On suppose
vraie.
Mais comment savoir sur quoi est définie ?
Puis on suppose que si
Alors est vraie pour tout
Tkt pas je comprends même avec mon indication c'est assez compliqué comme exercice il faut voir que
est vraie pour tout n, alors
est vraie pour tout n, donc
vraie pour tout
. C'est assez compliqué à voir, ça demande beaucoup de reflexion d'arriver à un tel résultat, même le major de Polytechnique galère avec ça.
Et puis toujours la même remarque sur la propriété en rouge, mais visiblement tu n'as vraiment pas envie de t'en servir...
Sur le même modèle, on montre que si A est une partie de contenant
et étant inductive, alors A est
!
lionel52 @ 08-07-2019 à 14:16
Tkt pas je comprends même avec mon indication c'est assez compliqué comme exercice il faut voir que
)
est vraie pour tout n, alors )
est vraie pour tout n, donc )
vraie pour tout 
. C'est assez compliqué à voir, ça demande beaucoup de reflexion d'arriver à un tel résultat, même le major de Polytechnique galère avec ça.
Tkt pas je comprends même avec mon indication c'est assez compliqué comme exercice il faut voir que
Ok merci.
Encore une question sur la récurrence d'ordre 2 :
Soit une propriété définie sur
avec
et
vraies ainsi que :
Alors la propriété est vraie pour tout .
Je n'ai pas compris la remarque du livre : il suffit d'appliquer le théorème 12 à la propriété.
Je ne vois pas comment appliquer le théorème 12 à
donc tu n'as pas compris le raisonnement par récurrence ...
le raisonnement par récurrence est constitué de deux arguments concernant une propriété dépendant d'un entier P(n) :
a/ une initialisation ... pour un certain entier ...(une trivialité sans intérêt mais nécessaire)
b/ l'hérédité de la propriété : P(n) => P(n + 1) ... (l'exercice ou activité mathématique par excellence)
b/ ne consiste pas à montrer que P(n) est vraie mais que : si P(n) est vraie alors P(n + 1) est vraie (on démontre donc la véracité de l'implication)
je te propose ces deux classiques :
1/ montrer que les propriétés :
a/ est multiple de 9
b/ est multiple de 9
sont héréditaires
2/ quelle propriété est vraie ?
Salut Ramanujan.
Tu poses et tu appliques ton théorème 12 avec
.
C'est quoi ? Et c'est quoi l'hérédité dans ce cas ?
Ramanujan @ 08-07-2019 à 18:15
@Jezebeth
En pratique, on n'utilise jamais la propriété en rouge non ?
@Jezebeth
En pratique, on n'utilise jamais la propriété en rouge non ?
sauf ici et maintenant, pour démontrer le principe de raisonnement par récurrence
Bonjour
Ramanujan @ 08-07-2019 à 18:14
Ok merci.
lionel52 @ 08-07-2019 à 14:16
Tkt pas je comprends même avec mon indication c'est assez compliqué comme exercice il faut voir que
est vraie pour tout n, alors est vraie pour tout n, donc vraie pour tout . C'est assez compliqué à voir, ça demande beaucoup de reflexion d'arriver à un tel résultat, même le major de Polytechnique galère avec ça.
Tkt pas je comprends même avec mon indication c'est assez compliqué comme exercice il faut voir que
Ok merci.
tu auras fait ma soirée !
jsvdb @ 08-07-2019 à 20:22
Salut Ramanujan.
Tu poses := P(n) \text{ et } P(n+1))
et tu appliques ton théorème 12 avec .
C'est quoi)
? Et c'est quoi l'hérédité dans ce cas ?
Salut Ramanujan.
Tu poses
C'est quoi
Cela veut dire quoi := ?
Mais après je n'ai pas trop compris.
On suppose que
Alors à fortiori :
Alors
@Carpediem
Pour la a :
Supposons que est vraie à un rang
.
Posons : : il existe un entier relatif
tel que :
D'après l'hypothèse de récurrence :
La propriété est héréditaire.
Or est un multiple de 9, la propriété
est vraie donc
est vraie.
Pour la b :
Supposons que est vraie à un rang
.
Posons : : il existe un entier relatif
tel que :
D'après l'hypothèse de récurrence :
La propriété est héréditaire.
Or n'est pas un multiple de 9, la propriété
est fausse donc
n'est pas vraie pour tout entier
Bonsoir,
P(n) n'est pas vraie pour tout entier n: Exact
Mais, elle pourrait être vraie à partir d'un rang autre que 0.
A toi de le dire dans la démonstration
Ramanujan @ 08-07-2019 à 23:05
= P(0) \ \text{et} \ P(1))
On suppose que \ \text{et} \ P(n+1)) \implies (P(n+1) \ \text{et} \ P(n+2)) )
Alors à fortiori : \ \text{et} \ P(n+1)) \implies P(n+2)) )
Alors \ \text{et} \ P(n+1)))
est vraie pour tout entier 
donc à fortiori )
est vraie pour tout entier
On suppose que
Alors à fortiori :
Alors
Ce raisonnement concernant la démo de la récurrence d'ordre 2 est-il correct ?
Ramanujan @ 08-07-2019 à 23:05
même plus que ""a fortiori""... ces deux lignes sont absolument équivalentes
jsvdb @ 08-07-2019 à 20:22
On suppose que
Alors à fortiori :
On suppose que
Alors à fortiori :
même plus que ""a fortiori""... ces deux lignes sont absolument équivalentes
Ah merci du coup j'ai compris la méthode, ça marche aussi pour la récurrence forte.
Soit une propriété définie sur
avec
vraie ainsi que :
Alors est vraie pour tout
.
Il suffit d'appliquer le théorème 12 avec
Donc
des démonstrations bien maladroites ...
et l'hypothèse de récurrence permet de conclure que la propriété P est héréditaire ... par combinaison linéaire
et l'hypothèse de récurrence permet de conclure que la propriété Q est héréditaire ... par combinaison linéaire
d'autre part P(0) est vraie donc par (le théorème de récurrence) P est vraie pour tout n
de plus on sait que ce qui montre trivialement que
est multiple de 9 (cours de première et sans utiliser le principe de récurrence)
enfin Q(0) est fausse, Q(1) est fausse, ..., Q(n) est fausse ... pour tout n en fait ...
on ne peut pas initialiser mais on ne sait pas si Q(n) est vraie pour un certain entier n
or
et (on sait que) 9 divise donc si 9 divise
alors par combinaison linéaire 9 diviserait 2 ... contradiction
donc cette fois ci on est certain que Q(n) est fausse pour tout n