Les théorèmes de Gödel et leurs implications

il y a 3 minutes, Spontzy a dit :

Bonjour.

Ah bon ? Il n'est donc pas possible pour un constructiviste de faire de l'arithmétique ? faudrait peut-être le signaler à tous ceux qui perdent leur temps...

 

Puis-je vous demander quel est votre problème avec moi ? Il n'a jamais été question de moi, sauf pour vous qui n'arrêtez pas de me mettre au centre du sujet. Pourriez-vous vous limiter à m'attaquer personnellement en messages privés, c'est dommage de polluer les files.

A+

Lisez plutôt mon exposé ci dessus sur la récurrence, ce sera plus intéressant de connaître votre avis (si vous en avez un ) plutôt que de se disputer sur des imbécillités et de se gargariser de mots prétendument savants. 

Bof. Pas envie de vous lire. Peut-être plus tard.

Mais, je vous félicite et remercie d'avoir pris le temps d'écrire un exposé.

 

Citation

 

Citation

Mais en l'occurrence nous parlons d'arithmétique, domaine dans lequel opère le tiers exclus.

Ah bon ? Il n'est donc pas possible pour un constructiviste de faire de l'arithmétique ? faudrait peut-être le signaler à tous ceux qui perdent leur temps...

Mais sur le fond, confirmez-vous que le tiers exclus opère en arithmétique et que donc on ne peut pas faire d'arithmétique si on est constructiviste ?

A+

Citation

 

Après vérification il y a bien une erreur dans les programmes de terminales S.

Dans le manuel terminales S mathsrepères, chez Hachette, page 10, la récurrence est bien présentée ainsi :

-P(0) vraie (initialisation)

-Pour tout n, P(n) vraie implique P(n+1) vraie, alors P(n) est vraie.

Donc on fait bien la supposition que P(n) est vraie. Ce qui est absurde.

Ce n'est pas du tout l'axiome de Peano qui lui stipule :

-P(0) vraie (initialisation)

-Pour tout n, si P(n) implique P(n+1) est vraie alors P(n) est vraie.

Dans le manuel il est supposé que P(n) est vraie : raisonnement circulaire. Erreur de présentation.

L'axiome de Peano tient lui, la route. Reste à lever ce problème : sachant que P faux implique P (n+1) vraie est une implication vraie, suis-je sûr de toujours trouver que P (n) faux implique P (n+1) faux ? là il y a un doute.

Modifié le 21 décembre 2017 par aliochaverkiev

Citation

Reste à lever ce problème : sachant que P faux implique P (n+1) vraie est une implication vraie, suis-je sûr de toujours trouver que P (n) faux implique P (n+1) faux ? là il y a un doute.

Je ne comprends toujours pas le problème.

Le principe de la récurrence est de montrer l'hérédité de la proposition P. On cherche uniquement à démontrer qu'il y a implication entre P(n) et P(n+1). C'est l'hérédité qui importe, pas le statut de vérité de P(n). Le statut de vérité est apporté par la vérification au rang initial. Puis on fait hériter cette valeur de vérité aux termes suivant.

Ainsi, dans le cas ou P(n) est fausse, vous pouvez trouver une hérédité. C'est même fréquent. Mas vous ne pouvez pas trouver d'initialisation vérifiant votre hypothèse fausse (par définition du fait qu'elle est fausse).

A+

 

il y a 13 minutes, Spontzy a dit :

Je ne comprends toujours pas le problème.

Le principe de la récurrence est de montrer l'hérédité de la proposition P. On cherche uniquement à démontrer qu'il y a implication entre P(n) et P(n+1). C'est l'hérédité qui importe, pas le statut de vérité de P(n). Le statut de vérité est apporté par la vérification au rang initial. Puis on fait hériter cette valeur de vérité aux termes suivant.

Ainsi, dans le cas ou P(n) est fausse, vous pouvez trouver une hérédité. C'est même fréquent. Mas vous ne pouvez pas trouver d'initialisation vérifiant votre hypothèse fausse (par définition du fait qu'elle est fausse).

A+

 

Si quand même, il est important que P(n) soit vraie ! puisque c'est la base de l'utilisation de la récurrence dans les programmes de terminales S. L'hérédité peut être vraie avec une proposition P(n) fausse. C'est là le problème.

Je vous recopie ici l'hérédité telle qu'elle est apprise en terminales S :

 

-P(0) vraie (initialisation)

-Pour tout n, P(n) vraie implique P(n+1) vraie, alors P(n) est vraie.

Vous lisez bien : P(n) vraie.

 

Vous pensez que, parce que l'initialisation à 0 est vraie alors cela suffit à démontrer que P(n) est vraie quelque soit n.

Or vous avez des propositions qui  sont vraies pour n = 0 et fausses pour d'autres valeurs. Du coup les prof disent "bon il faut initialiser à 2, ou 3 ou 4 ou 5 !" d'accord mais nous ne sommes plus dans l'axiome de Peano. C'est ainsi qu'une proposition vraie pour n = 0 peut ne pas l'être pour n = 2, ou 3 par exemple. Dans ce cas, si vous vous fondez sur le seul fait que la proposition est vraie pour n= 0 et que du coup, pour vous, la proposition est vraie pour tout n (avec une hérédité qui est fondée sur P(n) faux) vous vous plantez. 

Quand vous établissez l'hérédité P(n) implique P(n+1) vraie vous l'établissez pour tout n.  Mais l'hérédité, ici la valeur de vérité de l'implication, ne dit rien sur la vérité ou la fausseté de P(n). L'hérédité peut être vraie mais la proposition P(n) peut être fausse pour certaines valeurs de n. P(n) peut être vraie pour n = 0 et pas pour n = 1 (et cela arrive). C'est pourquoi, dans l'enseignement actuel on part du principe que P(n) est vraie (c'est à dire que P(n) est vraie pour tout n).

 

 

 

L'erreur de raisonnement que vous faites est intéressante. Elle m'oblige à approfondir la logique même de la relation implication et je commence à comprendre pourquoi elle est aujourd'hui exclue de l'enseignement secondaire.

En effet vous pensez que, si l'implication :  P implique Q est vraie alors soit P est toujours vraie, soit P est toujours fausse. Si donc l'initialisation est vraie pour n = 0, alors P est vraie et comme pour vous P ne peut être que toujours vraie ou toujours fausse, il suffit qu'elle soit vraie pour n= 0 pour qu'elle soit toujours vraie  quel que soit n. De même, si P est fausse elle est toujours fausse, donc elle ne peut pas être vraie pour n = 0. Or justement ça ne marche pas comme ça, si P implique Q est vraie alors soit P(n) est fausse, soit P(n) est vraie, mais ce n'est pas exclusif. C'est l'implication qui est vraie, mais nous ne savons rien sur la vérité de P et de Q. Elle peut être vraie pour certaines valeurs de n et fausse pour d'autres valeurs de n. Cela ressort des tables de vérité. Quand l'implication (ici l'hérédité) est vraie et que Q est vraie (ici P(n+1)) alors P (ici P(n)) peut être soit vraie soit fausse, sans exclusion de l'une ou l'autre possibilité. Autrement dit elle peut être vraie pour tout n, fausse pour tout n, ou parfois vraie, parfois fausse.

 

Modifié le 21 décembre 2017 par aliochaverkiev

@aliochaverkiev: en parlant d'erreur de raisonnement, j'aimerais que vous surligniez dans ce que j'ai écrit où est mon erreur (je souhaite apprendre).

 

Citation

En effet vous pensez que, si l'implication :  P implique Q est vraie alors soit P est toujours vraie, soit P est toujours fausse

Non je n'ai pas dit cela.

Citation

comme pour vous P ne peut être que toujours vraie ou toujours fausse

Non, et la récurrence ne démontre que la vérité de P au dessus d'un n initial. Pas vrai en dessous.

Mais très simplement,

SI

il existe un entier n0 tel que P(n0) est vraie (initialisation)

ET

pour tout n ≥ n0, P(n) ⇒ P(n+1) est vraie, (hérédité)

ALORS

pour tout n ≥ n0, P(n) est vraie.

 

Votre vérification de l'hypothèse, elle est bien faite pour tout n (≥n0), non ?

A+

Modifié le 21 décembre 2017 par Spontzy

Bien sûr qu'il y a des propositions qui sont vraies quelles que soient les valeurs de n.

Mais il y a aussi des propositions qui ne sont pas vraies quelles que soient les valeurs de n.

Votre erreur est de croire qu'une proposition si elle est vraie pour une valeur de n doit être vraie pour toutes les valeurs de n.

Prenons la proposition : 

2^n plus grand ou égal à n². Elle est vraie pour n = 0, pour n = 1, pour n = 2, mais fausse pour n =3.

Votre erreur est de croire que, dans une table de vérité le vrai ou le faux concerne  les propositions quelles que soient les valeurs de n. A ce compte là la récurrence est inutile. Il suffit de démontrer qu'une proposition est vraie pour n = 0 pour que la proposition soit vraie pour tout n ! Absurde.

Par ailleurs dans le théorème de Fermat la valeur de vérité ne porte pas sur l'égalité mais sur le discours sur cette vérité (il n'existe pas etc.) c'est à dire la valeur de vérité porte sur le métalangage. En plus nous ne sommes même pas dans le cadre de la récurrence où il ne s'agit que de propositions dépendant exclusivement de n. Là vous introduisez des variables x, y et z !!!

La récurrence porte sur la proposition elle-même (sur le calcul propositionnel) pas sur le discours sur la proposition, et sur des propositions ne dépendant que de n.

Vous êtes en train de m'embarquer dans des sophismes. C'est amusant mais nous risquons de perdre notre temps. 

(Il est bien évident que si je dis que l'équation n + 1 = 3 n'est vraie que pour n = 2, et si vous appelez proposition le discours sur l'équation, alors ce discours est ou vrai ou faux ! Mais là franchement amusez-vous avec quelqu'un d'autre que moi. Je voudrais que vous soyez honnête avec moi, sinon vous n'allez pas encore comprendre que je devienne agressif ! )

 

Modifié le 21 décembre 2017 par aliochaverkiev

(J'avais écrit des bêtises, relisez mon message que j'ai du modifier avant votre réponse).

Dans votre pratique de la récurrence, montrez vous que : pour tout n ≥ n0, P(n) ⇒ P(n+1) est vraie ? Si oui, où est le problème ? La valeur de vérité de la proposition n'a aucun intérêt à cette étape.

A+

 

il y a 26 minutes, Spontzy a dit :

(J'avais écrit des bêtises, relisez mon message que j'ai du modifier avant votre réponse).

Dans votre pratique de la récurrence, montrez vous que : pour tout n ≥ n0, P(n) ⇒ P(n+1) est vraie ? Si oui, où est le problème ? La valeur de vérité de la proposition n'a aucun intérêt à cette étape.

A+

 

Mais parce que la proposition " P(n) implique P(n+1)" peut être une proposition vraie avec P(n) vraie ou fausse, !!! oh oh reprenez vos livres de math, étudiez l'implication bon sang. Ce peut même être une proposition vraie avec P(n) faux et P(n+1) faux ! vous ne connaissez pas l'implication ! 

C'est bien parce que la proposition "P(n) implique P(n+1) " peut être vraie avec P(n) fausse pour certaines valeurs de n que nous avons un problème ! et c'est pour cela que, dans les manuels nous partons de l'hypothèse que P(n) est vraie ! (et c'est un abus), parce que, quand P(n) est vraie et que la proposition P(n) implique P(n+1) est vraie nous sommes sûrs que P(n+1) est vraie quelle que soit n ! c'est l'implication ! Prenez le temps de bien aller étudier l'implication, ouvrez vos livres de maths. 

 

 

Modifié le 21 décembre 2017 par aliochaverkiev

Vous avez un problème avec moi, vous devriez essayer de dépersonnaliser.

Citation

Mais parce que la proposition " P(n) implique P(n+1)" peut être une proposition vraie avec P(n) vraie ou fausse, !!!

C'est vrai !

Citation

 vous ne connaissez pas l'implication ! 

C'est faux. Mais vous pouvez croire le contraire si vous le voulez.

 

Citation

C'est bien parce que la proposition "P(n) implique P(n+1) " peut être vraie avec P(n) fausse pour certaines valeurs de n que nous avons un problème !

C'est faux. Il n'y a pas de problème.

La récurrence c'est ça :

SI

il existe un entier n0 tel que P(n0) est vraie (initialisation)

ET

pour tout n ≥ n0, P(n) ⇒ P(n+1) est vraie, (hérédité)

ALORS

pour tout n ≥ n0, P(n) est vraie. (conclusion)

 

Disons que vous êtes ok sur l'initialisation et la conclusion.

L'hérédité se moque de la valeur de vérité de P. Ce qui est indispensable pour que la récurrence soit valable, c'est que P(n) ⇒ P(n+1) est vraie quel que soit n ≥ n0. Si l'implication est démontrée quel que soit ce n (≥ n0), alors la démonstration est accomplie. La preuve :

Hypothèse à démontrer : vous dites que la proposition P peut être fausse, je le réécris de cette manière :

Il existe un plus petit entier i tel que P(i) est faux. i est forcément > n0, car P(n0) est vrai (initialisation).

Ce qui signifie que P(i-1) est faux. Car nous avons démontré que P(n)=>P(n+1) si n≥n0 (ce qui est identique à P(n-1)=>P(n) si n>n0). Dans notre cas, P(i) est faux. D'après la table de vérité que vous avez écrite, P(i-1) est forcément faux.

( je redonne la table, nous sommes dans le cas de la dernière colonne

a	1	1	0	0
b	1	0	1	0
a ⇒ b	1	0	1	1

car ici a=>b est vrai (nous l'avons démontré a étant P(n-1) et b étant P(n)) et b est faux (votre hypothèse). Donc a est faux).

Donc P(i-1) est faux.

Or P(i-1) est vrai par hypothèse, car P(i) est le premier élément de P étant faux. Donc notre hypothèse initiale (en bleu) est fausse. Donc il n'existe pas de plus petit i tel que P(i) est faux.

 

Donc en bref, si vous pouvez initialiser une proposition P et démontrer que P(n)=>P(n+1) est vraie quel que soit n, alors P(n) est vraie quel que soit n.

A+

 

 

 

 

 

 

Modifié le 21 décembre 2017 par Spontzy

Votre démonstration prouve que la proposition P implique Q n'est pas vraie pour tout n.  Quand j'étudie la proposition " P implique Q " je peux détecter qu'elle n'est pas vraie pour tout n. Mais je peux détecter qu'elle est vraie pour tout n supérieur par exemple à un nombre donné. Ce qui me permet d'initialiser à ce nombre. Je n'ai donc plus de problème.

Mais il y a deux questions qui se posent : est-ce que les valeurs de n pour lesquelles je ne peux pas démontrer la véracité de l'implication sont les mêmes que celles pour lesquelles elle est fausse ?

Prenons un contre exemple, un cas précis. Je reviens sur la proposition

2^n plus grand ou égal à n². 

Je remarque que n'avez pas répondu au fait qu'elle est vraie pour n = 0, puis n=1, puis n= 2 mais elle est fausse pour n= 3. Ce qui pour vous est impossible, puisqu'une proposition est soit vraie soit fausse, indépendamment de n. A moins que vous ayez changé d'avis depuis  car je vois que brusquement votre raisonnement se fortifie ! J'imagine que vous reçu l'aide d'un sachant, tant mieux, car du coup je vais pouvoir exposer mon problème à quelqu'un qui pourra (peut être) me répondre. Transmettez lui mes salutations.

Je reprends. Essayons de prouver que la proposition est vraie pour (n+1) sans me soucier de savoir si la proposition est vraie ou fausse pour n. Je vais trouver que la proposition est vraie pour n plus grand ou égal à trois (je laisse la démonstration à votre soutien). Alors je lui demande : comment se fait il que je trouve n égal à 3 alors que, pour 3 la proposition est fausse ? Il va me répondre qu'il suffit que j'initialise à 3 pour voir que c'est faux. D'accord mais là je tombe dans le bricolage, pas dans la démonstration. Ensuite je vais aussi trouver que je dois écarter les valeurs n = 0, n = 1 et n = 2, alors que , pour ces valeurs la proposition est vraie.

Donc ma question est celle-ci ( si je ne vois pas que je dois initialiser la proposition à 4 et non à 0) 

1  : y a t il un raisonnement qui me donne immédiatement cette directive, ou est-ce je dois bricoler ?

2  existe-t-il un raisonnement qui me permette de constater que la proposition est vraie pour n = 0, n = 1, n = 2 ?

Ce qui est inquiétant dans ces difficultés c'est qu'en définitive il est légitime de se poser cette question :  est ce qu'il y aurait des démonstrations qui ne permettraient pas de voir que l'implication est fausse dans certains cas ? Une démonstration qui s'appuie sur des prémisses fausses peut arriver à n'importe quoi, notamment à démontrer qu'une proposition est vraie pour tout n. Dans ce cas je ne peux pas détecter qu'il y a des cas où la proposition est fausse pour certaines valeurs de n.

En effet votre raisonnement conduit à cette alternative :

- soit la récurrence est vraie pour tout n

- soit la proposition n'est pas vraie pour tout n.

Dans une démonstration nous partons toujours d'hypothèses qui sont soient vraies soit fausses. Et nous le savons. C'est à dire que nous étudions les deux cas de figure en le disant. Nous disons :

1/supposons que l'hypothèse est vraie [(P(n) vraie]

ou

2/ supposons que l'hypothèse est fausse [(P(n) fausse]

puis nous déroulons notre démonstration.

Nous ne partons pas d'hypothèses dont ne savons rien quant à la fausseté ou à la vérité. Autrement dit : prouvez moi qu'une démonstration ne conduit pas à des catastrophes quand je ne fais aucune hypothèse sur la vérité ou la fausseté de mes hypothèses. Sans cette preuve je peux toujours émettre cette objection : je peux bien trouver une démonstration qui me conduise à une erreur que je ne détecterai pas, notamment l'erreur de croire que P(n) implique P(n+1) est vraie quelque que soit n, sans voir qu'elle est fausse pour certaines valeurs de n. Ne détectant pas cela je ne peux pas même faire l'hypothèse que la proposition pourrait être fausse !!!

Autrement dit existe-t- il une théorie de la démonstration qui pose comme principe que la vérité ou la fausseté des hypothèses n'a aucune importance ? je n'en ai jamais entendu parler.

Enfin je suis allé voir les exercices des classes prépa que j'ai chez moi, tous partent de l'hypothèse que P(n) est vraie pour démontrer P(n+1)

 

 

 

 

Ne pas se soucier de la vérité ou pas de P(n) est très dangereux.

Prenons la proposition suivante :

1/(n² -2) < 0.

Pour n = 0, la proposition est vérifiée.

Je pars donc de la proposition 1/(n²-2) < 0 sans me soucier de sa vérité.

(n+1) > n  quelque soit n

(n+1)² > n² quelque soit n

(n+1)² -2 > n² -2 quelque soit n

donc 1/((n+1)²-2) < 1/(n²-2) quelque soit n

Mais 1/ (n²-2) < 0 donc 1 /((n+1)² -2) < 0

donc 1/(n²-2) <0 implique 1/((n+1)²-2) < 0 quelque soit n.

Que s'est il passé ? pour ne pas m'être soucié de la vérité de P(n) je me suis planté car mon raisonnement ne me permet pas de détecter que l'implication n'est pas vraie pour tout n.

Votre raisonnement est juste concernant l'implication mais faux concernant la démonstration qui permet de passer de n à (n+1).

Je suis donc bien obligé de considérer la vérité de la proposition P(n). C'est d'ailleurs ce qui est fait dans tous les exo que j'ai pu voir dans les classes préparatoires.

 

Bonjour.

Citation

Votre démonstration prouve que la proposition P implique Q n'est pas vraie pour tout n.

Ridicule. C’est une des hypothèses de ma démonstration : je la surligne en bleu.

« L'hérédité se moque de la valeur de vérité de P. Ce qui est indispensable pour que la récurrence soit valable, c'est que P(n) ⇒ P(n+1) est vraie quel que soit n ≥ n0. Si l'implication est démontrée quel que soit ce n (≥ n0), alors la démonstration est accomplie ».

NB : Ce qui se passe avant n0 n'intéresse pas la récurrence.

 

Citation

Quand j'étudie la proposition " P implique Q " je peux détecter qu'elle n'est pas vraie pour tout n. Mais je peux détecter qu'elle est vraie pour tout n supérieur par exemple à un nombre donné. Ce qui me permet d'initialiser à ce nombre. Je n'ai donc plus de problème.

Ma démonstration prouve que SI il existe un entier n0 tel que P(n0) est vraie (initialisation) ET pour tout n ≥ n0, P(n) ⇒ P(n+1) est vraie, (hérédité) ALORS pour tout n ≥ n0, P(n) est vraie. (conclusion). Cela répond aux questions que vous posiez le 14 et le 21 décembre.

 

Citation

Mais il y a deux questions qui se posent : est-ce que les valeurs de n pour lesquelles je ne peux pas démontrer la véracité de l'implication sont les mêmes que celles pour lesquelles elle est fausse ?

Prenons un contre exemple, un cas précis. Je reviens sur la proposition

2^n plus grand ou égal à n². 

Je remarque que n'avez pas répondu au fait qu'elle est vraie pour n = 0, puis n=1, puis n= 2 mais elle est fausse pour n= 3. Ce qui pour vous est impossible, puisqu'une proposition est soit vraie soit fausse, indépendamment de n

 

Merci de me citer.

 

 

Citation

Je reprends. Essayons de prouver que la proposition est vraie pour (n+1) sans me soucier de savoir si la proposition est vraie ou fausse pour n. Je vais trouver que la proposition est vraie pour n plus grand ou égal à trois (je laisse la démonstration à votre soutien). Alors je lui demande : comment se fait il que je trouve n égal à 3 alors que, pour 3 la proposition est fausse ? Il va me répondre qu'il suffit que j'initialise à 3 pour voir que c'est faux. D'accord mais là je tombe dans le bricolage, pas dans la démonstration. Ensuite je vais aussi trouver que je dois écarter les valeurs n = 0, n = 1 et n = 2, alors que , pour ces valeurs la proposition est vraie.

Donc ma question est celle-ci ( si je ne vois pas que je dois initialiser la proposition à 4 et non à 0) 

1  : y a t il un raisonnement qui me donne immédiatement cette directive, ou est-ce je dois bricoler ?

Non. Il faut chercher. La plupart des démonstrations mathématiques sont des « bricolages ». Elles sont des œuvres humaines. Et cela les rend parfois belles.

Citation

2  existe-t-il un raisonnement qui me permette de constater que la proposition est vraie pour n = 0, n = 1, n = 2 ?

Pas un raisonnement. Il s’agit d’une vérification calculatoire. Remplacer n par sa valeur dans l’expression de P(n).

Citation

Ce qui est inquiétant dans ces difficultés c'est qu'en définitive il est légitime de se poser cette question :  est ce qu'il y aurait des démonstrations qui ne permettraient pas de voir que l'implication est fausse dans certains cas ?

Non. C’est ce que j’ai démontré. Voir plus loin.

Citation

Une démonstration qui s'appuie sur des prémisses fausses peut arriver à n'importe quoi, notamment à démontrer qu'une proposition est vraie pour tout n. Dans ce cas je ne peux pas détecter qu'il y a des cas où la proposition est fausse pour certaines valeurs de n.

En effet votre raisonnement conduit à cette alternative :

- soit la récurrence est vraie pour tout n

- soit la proposition n'est pas vraie pour tout n.

Dans une démonstration nous partons toujours d'hypothèses qui sont soient vraies soit fausses. Et nous le savons. C'est à dire que nous étudions les deux cas de figure en le disant. Nous disons :

1/supposons que l'hypothèse est vraie [(P(n) vraie]

ou

2/ supposons que l'hypothèse est fausse [(P(n) fausse]

puis nous déroulons notre démonstration.

Nous ne partons pas d'hypothèses dont ne savons rien quant à la fausseté ou à la vérité. Autrement dit : prouvez moi qu'une démonstration ne conduit pas à des catastrophes quand je ne fais aucune hypothèse sur la vérité ou la fausseté de mes hypothèses. Sans cette preuve je peux toujours émettre cette objection : je peux bien trouver une démonstration qui me conduise à une erreur que je ne détecterai pas, notamment l'erreur de croire que P(n) implique P(n+1) est vraie quelque que soit n, sans voir qu'elle est fausse pour certaines valeurs de n. Ne détectant pas cela je ne peux pas même faire l'hypothèse que la proposition pourrait être fausse !!!

 

C’est exactement ce que j’ai démontré. Je vais essayer de reformuler, sans le soutien de mon prof de terminale, je m’excuse si ce n’est pas assez pédagogique :

Nous parlons d’une démonstration par récurrence. On émet une hypothèse (qui peut être vraie ou fausse par définition d’une hypothèse). C’est la proposition P.

 

La récurrence c'est ça :

SI

il existe un entier n0 tel que P(n0) est vraie (initialisation)

ET

pour tout n ≥ n0, P(n) ⇒ P(n+1) est vraie, (hérédité)

ALORS

pour tout n ≥ n0, P(n) est vraie. (conclusion)

 

D’abord on vérifie, par un calcul que P(n0) est vraie. C’est purement calculatoire. On remplace numériquement la variable « n » par sa valeur numérique et on vérifie l’égalité.

Puis on démontre que l’implication (pour tout n ≥ n0) P(n) ⇒ P(n+1) est vraie. C’est le gros du travail. On se moque du fait que P soit vraie ou fausse. Vous verrez pourquoi plus loin. Ici, on montre que l’implication du rang n au rang n+1 est vraie. Pour la suite, nous supposons que cette implication est démontrée (si elle ne l’est pas, c’est qu’on ne peut pas conclure à notre démonstration, évidemment).

Votre question est : peut on prouver que P(n) est vraie pour tout n ? En effet, à ce stade, nous ne savons pas si P(n) est vraie ou fausse. Nous savons uniquement qu’elle est vraie pour n0 et que l’hérédité est établie (pour tout n ≥ n0, P(n) ⇒ P(n+1) est vraie).

Alors allons-y pour la démonstration :

 

Hypothèses :

-          Nous avons P(n0) vraie. C’est l'initialisation.

-          Nous avons démontré que l’implication de n à n+1 est vraie. (pour tout n ≥ n0, P(n) ⇒ P(n+1) est vraie). C’est l’hérédité.

Nous voulons montrer que P(n) ne peut pas être fausse pour au moins un rang donné. Procédons par l’absurde en faisant donc l’hypothèse contraire à ce que l’on veut démontrer :

Supposons qu’il existe au moins un rang j tel que P(j) est fausse.

Notons i (nombre entier, comme n) le plus petit rang pour lequel la proposition P est fausse. Soit P(i) est faux.

Comme P(n0) est vraie (initialisation), alors i>n0. Il est donc possible de regarder ce qui se passe au rang i-1.

L’hérédité nous permet d’écrire : P(i-1)=>P(i) est vraie (car i>n0).

Or P(i) est fausse par hypothèse (bleue).

Donc P(i-1) est fausse. (je passe le détail de la table de vérité que vous maitrisez).

Nous aboutissons immédiatement à une contradiction : nous avons défini i comme étant le plus petit rang pour lequel la proposition P est fausse et nous arrivons à la conclusion que P est également fausse au rang inférieur. Notre hypothèse bleue est donc erronée (démonstration par l’absurde).

 

On démontre donc bien que si initialisation il y a, si hérédité il y a, alors la récurrence fonctionne. On se moque que la proposition P soit vraie ou pas. Je n’utilise nulle part cela dans la démonstration, au contraire, j’envisage tous les cas dans ma table de vérité.

 

Citation

Enfin je suis allé voir les exercices des classes prépa que j'ai chez moi, tous partent de l'hypothèse que P(n) est vraie pour démontrer P(n+1)

Évidemment. Et pourquoi donc font-ils cela ? Par principe d’efficacité. Si on choisit des propositions fausses, on ne pourra pas initialiser ou pas démontrer l’hérédité pour tout n supérieur ou égal à n0. Pour réussir la démonstration, il faut trouver la bonne proposition. En essayer des mauvaises est une perte de temps.

A+

Il y a 19 heures, aliochaverkiev a dit :

(n+1)² -2 > n² -2 quelque soit n

donc 1/((n+1)²-2) < 1/(n²-2) quelque soit n

Attention, l'implication ici utiliser est fausse, en effet on a 1>-0.5 et pourtant on n'a pas 1<-2...

Donc il faut prendre en considération le signe de la quantité à inverser, ce qui fait capoter ton raisonnement.

Le 14/12/2017 à 09:14, Spontzy a dit :

Bonjour.

Il y a un bug dans le raisonnement : vous définissez E' et E en utilisant n (entier naturel fini). E' contient bien plus d'élément que E tant que la définition est respectée, pour tout n entier naturel. Si vous dites après que n tend vers l'infini, vous ne pouvez plus définir E'.

A+

 

Je ne comprends pas la nature de l'objection !? Si " n " est un entier naturel, ne puis-je pas prendre celui que je veux, aussi grand que je veux ? Si non, dans ce cas, toute l'Analyse est à revoir, car il est plus que fréquent de faire tendre vers l'infini le " n " qui est toujours pris dans N, c'est-à-dire dans les entiers naturels. Y aurait-il en mathématique deux poids et deux mesures ? Un légitime en Analyse et un autre en Algèbre ?

 

Néanmoins, si l'usage des infinis dans mon exemple pose problème, alors cela confirme mes réticences sur leur usage inconsidéré, si l'exemple est valide en usant des infinis, alors on voit poindre une contradiction par l'emploi justement des infinis, retour à la case départ, il faut être vigilant quand on use des infinis indéfiniment si j'ose dire.

Bonjour.

Citation

Je ne comprends pas la nature de l'objection !? Si " n " est un entier naturel, ne puis-je pas prendre celui que je veux, aussi grand que je veux ? Si non, dans ce cas, toute l'Analyse est à revoir, car il est plus que fréquent de faire tendre vers l'infini le " n " qui est toujours pris dans N

On peut faire tendre n vers l'infini. n étant un entier. Mais l'infini n'est pas un entier (regardez les différentes définitions des entiers, les plus courantes étant celles qui définissent les entiers comme successeur d'un autre entier. "infin-1" n'a pas de sens et l'infini ne succède à personne). On ne peut donc pas remplacer "n" par l'infini dans votre raisonnement.

Citation

il faut être vigilant quand on use des infinis indéfiniment si j'ose dire.

Je vous rejoins à 100% la dessus !

A+

Le 14/12/2017 à 14:19, aliochaverkiev a dit :

Hum...ne passez pas le bac S, vous auriez zéro ! vous n'y êtes pas du tout, il faut que je vous explique votre erreur de raisonnement, mais c'est assez long, vous avez beaucoup de lacunes en math, vous ne comprenez pas l'implication* par exemple (pourtant cette relation est étudiée depuis Aristote !).

Merci de t'en soucier, mais j'ai vu qu'au fil de tes propres réflexions, tu as fini par te rendre compte de quoi je parlais: on ne peut pas démontrer le principe de raisonnement par récurrence, but premier de mon intervention !

En réalité il y a 3 positions: celle de Hilbert ( position formelle, c'est une règle ), celle de Frege ( c'est une définition, car elle est incluse dans la construction des entiers naturels ) et celle de Poincaré ( elle est intuitive, on ne peut la démontrer, elle n'est pas réductible, ni à la logique, ni au principe de non-contradiction, au mieux on a un système circulaire de part l'axiomatique -> Frege ):

Citation

Bon j'essaye quand même de devenir votre enseignant !

Quand vous écrivez n'importe quelle égalité de type :

Vn = f(n), vous pouvez l'écrire par définition, comme une donnée par vous décidée. V(n) = 2 n par exemple, vous écrivez cela par décision. Donc V(n+1) = 2(n+1) bien sûr !

Mais ici quand nous écrivons Vn = 1/2^n (on emploie le signe ^ plutôt que le signe exp, car exp est le symbole de la fonction exponentielle, c'est pourquoi je ne comprenais rien au début à ce que vous écriviez) nous ne le décidons pas ! nous l'observons. Nous observons que, pour un indice donné, mettons n, nous voyons, après observation, que Vn semble être égal à 1/2^n. Mais V(n) n'est pas du tout défini comme étant égal à 1/2^n ! V(n) est définie comme étant égal à (n+1) U(n) !

[ Je ne pensais pas qu'une écriture littérale tronquée par facilité à cause de l'éditeur de textes - avant la refonte du site il y a peu l'éditeur proposait les indices et les exposants ce qui facilitait l'écriture matheuse, mais ça c'était avant - aurait causé un tel embarras, j'aurais cru que c'était suffisamment évident pour ne pas confondre exp entre exposant et exponentielle, oui je suis de la " vieille école " ça ne me gêne pas le moins du monde de dire 5 exposant 2 ]

Définition de la puissance réelle.
x est un réel strictement positif et a est un réel quelconque.

x^a (appelez-le "x puissance a" ou "x exposant a") est le réel défini par :

x^a = exp(a . ln(x)) = e^{a . ln(x)}

http://tanopah.jo.free.fr/ADS/bloc5/puissanceA.html

 

 

Citation

Et, bien sûr dans le cadre de cette définition nous avons bien V(n+1) = (n+2) U(n+1), là c'est évident puisque nous appliquons une définition. Mais quand constatons que V(n) = 1/2^n nous ne savons pas si cette constatation est vraie pour toutes les valeurs de n. Pour vous c'est évident ! mais pour un mathématicien absolument pas ! d'autant que les mathématiciens vont trouver des suites de ce type qui vont être vraies pour l'indice n et pas pour l'indice (n+1) !

Le problème des mathématiciens c'est celui-là : est ce qu'une proposition vraie pour l'indice n= 0, n = 1, n = 2, n = n est vraie pour l'indice n+1 ? Pour vous c'est évident mais pour un mathématicien pas du tout ! D'autant que vous avez des suites qui sont vraies pour n = 1, n= 2, etc. et qui ne sont pas vraies soudain pour certaines valeurs de l'indice. Avec votre sens de l'évidence en maths c'est pour le coup que nous ne serions pas sûrs que l'avion qui part de Paris à 12 heures  arrivera bien à Marseille à 13 heures !

 

Votre erreur est la suivante :

Vous tenez pour vraie l'égalité V(n) = 1/2^n.

Or nous ne savons pas si elle est vraie !

Si vous partez de l'idée qu'elle est vraie en soi, bien sûr V(n+1) = 1/2^(n+1).

Il faut que nous prouvions qu'elle est vraie. Vous passez allègrement par dessus l'exigence de démonstration !

 

Mais mon souci n'était pas de résoudre l'exercice, qui était parfaitement secondaire.

Je reformule ma requête, peut-on être certain, et je crois que quelque part tu te l'aies posée également, que si j'ai une hypothèse fausse, je puisse avoir quand même l'hérédité mais fausse également !? ( avec l'étape d'initialisation validée )  [ Ce qui ne peut aucunement être le cas avec l'exo de mon fils puisque j'ai donné l'écriture formelle de la suite et qui correspond à l'hypothèse ]

Fausse dans le sens où je retrouve, après intégration, développements et simplifications, à " n+1 " mon hypothèse de départ en " n ", c'est-à-dire en changeant n par n+1 dans la formulation directement - ce que tu m'as reproché, comme étant un court-circuit dans le raisonnement - mais en réalité c'est ça que j'avais en tête, dit autrement, que cela marche sur le papier, avec la formule ou sur la forme, mais que ce soit faux dans la partie numérique/calculée avec les valeurs effectives.

 

Je donne un " exemple " connexe pour fixer les idées, si j'ai 3x + 1 = 0, on voit bien que si on prend l'hypothèse x = 5 ça ne marche pas, par contre si je prends x = f ( t ) alors je n'ai rien de faux en remplaçant, mais je n'ai aucune garantie que ce soit juste pour autant tant que je ne donne pas une valeur à f ( t ). Il faut se concentrer sur l'idée derrière et non pas sur l'exemple qui est trivial et ne pose strictement aucun problème: de remplacer une expression par une autre n'apporte de prime abord aucune garantie, même si il n'y a aucune contradiction pendant le processus; et c'est ce que je demande, quand on introduit une hypothèse formelle dans le principe de raisonnement par récurrence, comment être certain que celle-ci ne peut pas ne pas être juste ( la double négation est primordiale: je ne suis pas malheureux *n'implique pas d'être heureux, je ne suis pas pauvre *n'implique pas d'être riche )

 

 

Citation

Cela dit la récurrence pose problème à beaucoup de lycéens de terminales S je vous rassure, c'est une notion complexe.

Pas uniquement, à tous les niveaux y compris bien plus élevés:

 

Modifié le 23 décembre 2017 par deja-utilise

Le 14/12/2017 à 14:49, aliochaverkiev a dit :

Par ailleurs les mathématiques travaillent sur des objets précis, des nombres en arithmétique, des points en géométrie. Les mathématiciens ne prétendent pas du tout travailler sur des lois, sur des notions comme la vie, ou je ne sais quoi. Ils n'ont pas cette prétention.

Derrière le symbolisme mathématique se dévoile un sens, il ne faut pas rester cloitrer derrière le jargon matheux, il faut tenter de comprendre la signification profonde de ce que l'on manipule, de ce que l'on lit ou écrit. Le symbolisme en math est une forme abrégée de langage, qui peut sans perte être retranscrit dans le langage ordinaire: De la sorte, on voit de multiple connexions entre la mathématique, la physique, la vie quotidienne, la philosophie, d'autres sciences, la psychologie, etc...

( La sommation de 1 + 1/2 + 1/4 + 1/8 +... a une signification, une situation potentiellement réelle qui y correspond, dû à Zénon. )

 

Par exemple le signe = signifie équivalence ou égalité si ce sont des nombres. D'autre part il n'y a jamais de vérité en mathématique, juste des équivalences/similarités, dans l'algèbre booléenne l'emploi des termes vrai et faux est impropre, car cette logique est employée couramment en électronique ou informatique, le fait que le courant passe n'est pas une vérité en soi, ni qu'il ne passe plus une fausseté, il vaudrait mieux le retraduire par oui - non par exemple. 

 

Peut-on soutenir que 0.99999... égal 1 en toute rigueur ?

Quelle est la somme de 1 - 1 +1 - 1 + 1 - 1 + ... = ?

Le 14/12/2017 à 19:39, Spontzy a dit :

Oui nous en sommes sûrs, sauf à refuser le tiers exclus.

Mais comme on le sait bien, ce tiers exclus n'est maintenant plus discutable dans ZFC.

A+

Le tiers-exclu, ce qui implique aussi le principe de non-contradiction par conséquent, mais on peut aussi douter de l'emploi des infinis comme je m'échine à le montrer, et pour moi c'est amplement suffisant pour recourir à une approche plus constructive, par exemple rechercher la valeur de Pi par le procédé d'Archimède est, pour ma part, une " bonne " méthode, en revanche le principe de raisonnement par récurrence est douteux, car si on l'applique au monde physique, il ne tient jamais la route, car les approximations de départ rejaillissent toujours à un moment ou à un autre, de plus rien ne peut être totalement infini par faute de moyens, de ressources ou de temps. Et il y a une passerelle entre les mathématiques et le monde réel, même si on se refuse à la voir !

Bref les math " classique " c'est bien joli, mais dans ma conception, c'est une Physique qui a dégénéré... Mais il est vrai qu'il n'est pas interdit de jouer, que ce soit aux échecs ou avec les maths ou des briques de Lego, chacun son trip. 

 

Le 14/12/2017 à 20:01, aliochaverkiev a dit :

Au demeurant je ne vois absolument pas le rapport entre la théorie des ensembles de Zermelo-Fraenkel avec le principe de récurrence. Expliquez moi. 

 

Parce que les entiers eux-mêmes sont construits de manière récurrente, non ?