équivalence en théorie de la démonstration

[ilelogique]

Bonjour,
Savez-vous, lorsque deux propositions sont équivalentes (au sein d'une certaine théorie), si il existe nécessairement une preuve qui procède par équivalence ?
J'essaie d'être plus clair :
dans certains cas on prouve une équivalence en procédant par équivalences successives (comme 2x=6 <=> x=3),
Mais dans d'autres cas la preuve directe et celle de sa réciproque ne sont pas les mêmes, on prouve une implication puis l'autre.
Je me demande alors si il existe toujours ou pas, une démonstration qui procèderait par équivalence ?
merci.
-----

[ilelogique]

Pourquoi personne ne s'interres-t-il à ma question s'il vous plait ?
merci

[invite57a1e779]

Pourquoi personne ne s'interres-t-il à ma question s'il vous plait ?
merci

Peut-être parce qu'elle n'est pas facile.

Il existe des cas classiques où l'on prouve que .
Puis on prouve que en utilisant .
Ainsi une démonstration directe de paraît difficile, mais de là à prouver que c'est impossible, il y a un gouffre.

[ilelogique]

Le fait qu'il advienne de démontrer B=>A en utilisant A=>B (je veux bien en voir un exemple simple) n'implique en rien, selon moi, sur ce que je dis : il existe des preuves qui procèdent par équivalence : la règle qui permet de passer de x=3 à 2x=6 est la même dans un sens et dans l'autre (multiplier par le réel qu'on veut, de part et d'autre de l'égalité, dans la théorie de l'arithmétique classique), c'est réversible ; et d'autres fois la preuve d'un sens n'a rien à voir avec celle de l'autre sens (comme ce que tu soulèves et qu'on voit souvent en géométrie). La question est de savoir si, quand on connait la preuve d'une implication et celle, tout autre, de sa réciproque, il est ou non possible de trouver une preuve directe de l'équivalence des deux propositions présentes ; et surtout si cela est toujours possible ?
merci

[A voir en vidéo sur Futura]

[invite57a1e779]

il existe des preuves qui procèdent par équivalence : la règle qui permet de passer de x=3 à 2x=6 est la même dans un sens et dans l'autre (multiplier par le réel qu'on veut, de part et d'autre de l'égalité, dans la théorie de l'arithmétique classique), c'est réversible ; et d'autres fois la preuve d'un sens n'a rien à voir avec celle de l'autre sens (comme ce que tu soulèves et qu'on voit souvent en géométrie). La question est de savoir si, quand on connait la preuve d'une implication et celle, tout autre, de sa réciproque, il est ou non possible de trouver une preuve directe de l'équivalence des deux propositions présentes ; et surtout si cela est toujours possible ?
merci

Si ta question est :
lorsque, d'une part, on sait déduire B de A à l'aide d'un modus ponens utilisant le théorème C, et que, d'autre part, on sait déduire A de B à l'aide d'un modus ponens utilisant le théorème D, est-il possible d'utiliser le même théorème dans les deux cas, la réponse est "presque" oui : il suffit d'utiliser le théorème (C et D).
C'est pourquoi j'envisageais le cas de démonstration par méthode "de falsa positione", le théorème D nécessitant , il n'est plus possible d'utiliser du théorème (C et D) pour déduire B de A, et je pense que le problème de savoir si aucun autre théorème E ne conviendrait n'est vraiment pas des plus faciles. Comme je le disais, il y a un gouffre...

[Médiat]

Pourquoi personne ne s'interres-t-il à ma question s'il vous plait ?

1) Pas simple : cf. l'intervention de God's Breath
2) Mal cadrée : Logique classique, Logique intuitioniste, Logique linéaire (moins répandue, mais très présente en théorie de la preuve), système de Hilbert, système de Gentzen (j'imagine que c'est à ce dernier que tu penses)...
3) Je ne perçois pas l'intérêt de la question (ce qui ne veut pas dire qu'elle n'en a pas), par exemple en arithmétique classique le système de preuve de Hilbert permet de démontrer que (1 = 2) <==> non (Théorème de Fermat) ; je veux bien m'occuper du sens ==>, pour le sens <== il va falloir demander de l'aide, car personnellement je n'ai pas le bagage nécessaire pour comprendre la démonstration de Wiles et je ne vois pas pourquoi je dérangerais ce brave homme pour démontrer le sens ==> accessible à tous les élèves de lycée.

[ilelogique]

Au départ la question que je me suis posée venait de considérations mathématiques simples du programme de terminale S. Vous conviendrez sans doute (God's Breath et Mediat notamment) que les élèves à ce niveau ont déjà du mal avec les principes simples de la logique classique (réciproque, contraposée, équivalence, etc.). Aussi (je fais dans le spectacle scientifique, voir l'île logique) la logique à laquelle je me référais était certes classique et dans un esprit, en effet, tourné vers le style Gentzen.
Je conviens que, dans ce cas, s'il existe une preuve de A=>B et une autre de B=>A, on aura une preuve de A<=>B (ne serait-ce qu'en "collant" les deux preuves).
Finalement mon problème revient à cela : Parfois, en Terminale par exemple, on fait des démonstrations qui "procèdent par équivalence" (en ce sens que les deux sens de l'implication sont montrés simultanément, conjointement) et d'autres fois on est ammené à faire chaque sens de la preuve séparément.
Ma question étant : "existe-t-il nécéssairement une preuve qui procède par équivalence ?"...je conviens tout à fait qu'il nous faut définir ce qu'on appelle "une preuve qui procède par équivalence" dans un systême formel (calcul des séquents de base, mettons Gentzen)...Je ne sais pas si une telle définition existe ni quelle allure elle aurait...
Ne pourrait-on pas, par exemple, définir cela avec des sortes de preuves réversibles ?
(si depuis une théorie T, avec l'hypothèse de la proposition P on parvenait à construire une preuve formelle de Q alors, en gros, en supposant T et Q et en "retournant" la preuve précédente on obtiendrait directement une preuve de P. La preuve par équivalence deviendrait une espèce de preuve non orientée qu'on peut lire dans les deux sens...).
Mais bon sans doute m'égarre-je...
Merci pour vos éclaircissements...

ps : je serais curieux de voir un exemple de démonstration où la preuve de B=>A utilise de façon indispensable celle de A=>B...

[invite6b73e3e6]

sans doute m'égarre-je...
...

sans doute m'égaré-je....

Cordialement,

CD

[invite57a1e779]

Bonjour ilelogique,

Il faudrait effectivement définir ce qu'on appelle "une preuve qui procède par équivalence" dans un systême formel (calcul des séquents de base, mettons Gentzen).

Je reprends ton exemple :

la règle qui permet de passer de x=3 à 2x=6 est la même dans un sens et dans l'autre (multiplier par le réel qu'on veut, de part et d'autre de l'égalité, dans la théorie de l'arithmétique classique), c'est réversible

.

Ce n'est pas tout à fait exact.

Je note et .

Tu dispose d'un théorème T qui dit exactement :

Tu utilises deux particularisations (instantiations) de ce théorème :
– en substituant x à a, 3 à b, et 2 à c ;
– en substituant 2x à a, 6 à b, et 1/2 à c.

Les raisonnements effectifs sont :
– on déduit B de A par modus ponens sur A et ;
– on déduit A de B par modus ponens sur B et .

Formellement, on est obligé d'écrire les formules et : la preuve n'est pas vraiment la même dans les deux sens.

je serais curieux de voir un exemple de démonstration où la preuve de B=>A utilise de façon indispensable celle de A=>B

Premier exemple : un sous-ensemble H de Z en est un sous-groupe additif si, et seulement, si H=nZ, avec n dans N.

On commence par montrer l'implication : H=nZ, avec n dans N => H sous-groupe additif de Z.

Ensuite, si H est un sous-groupe additif de Z, soit H={0}=0.Z, soit H!={0}, on définit [...] le plus petit entier naturel non nul, n, appartenant à H, on pose H'=nZ. On utilise alors la première implication pour dire que H' est un-sous-groupe additif de Z, et obtenir l'inclusion de H' dans H, puis on montre l'inclusion de H dans H' et, pour ce faire, on utilise l'inclusion de H' dans H obtenue par la première implication. On conclut finalement que H=H' ...

Autre exemple : démonstration géométrique du théorème de Ménélaüs.

Si les points P, Q, R pris sur les côtés du triangle ABC sont alignés alors on a la célèbre relation ...

Si l'on a la célèbre relation..., soit R' l'intersection de la droite PQ avec le troisième côté du triangle, alors P, Q et R' sont alignés, donc satisfont la même relation que P, Q et R, ce qui permet de conclure à R=R' et à l'alignement souhaité.

Mais le fait que ces démonstrations classiques de B=>A utilisent celles de A=>B, je ne vois pas comment atteindre, pour une preuve donnée, le caractère indispensable de cette méthode.
En particulier, il suffit de raisonner analytiquement pour obtenir directement l'équivalence dans le cas du théorème de Ménélaüs (sous les réserves mentionnées à propos de x=3 <=> 2x=6).

[Médiat]

Je note et .

Tu dispose d'un théorème T qui dit exactement :

Tu utilises deux particularisations (instantiations) de ce théorème :
– en substituant x à a, 3 à b, et 2 à c ;
– en substituant 2x à a, 6 à b, et 1/2 à c.

Les raisonnements effectifs sont :
– on déduit B de A par modus ponens sur A et ;
– on déduit A de B par modus ponens sur B et .

Formellement, on est obligé d'écrire les formules et : la preuve n'est pas vraiment la même dans les deux sens.

Je voulais justement utiliser cet exemple .. pour montrer le contraire (mais avec la même remarque finale que toi sur le fait que cela ne montre pas le caractère indispensable de la différence).

Car dans IN, A ==> B utilise la fonctionnalité de la multiplication, alors que B ==> A utilise la régularité de la multiplication (on ne peut pas multiplier par 1/2).

En allant plus loin, dans l'arithmétique de Robinson, on peut démontrer que
, alors que l'autre sens ne peut être démontré, contrairement à l'arithmétique de Peano où il y a équivalence, donc la démonstration dans un sens nécessite le schéma d'induction, ce qui n'est pas le cas de l'autre sens (la-dessus, on peut toujours ajouter des hypothèses inutiles à une démonstration).

Il faudrait que je me replonge dedans mais il me semble que dans la logique linéaire, la réponse serait non à ta question initiale.

[invite57a1e779]

mais avec la même remarque finale que toi sur le fait que cela ne montre pas le caractère indispensable de la différence.

C'est bien ce "caractère indispensable" qui est le noeud du problème... et qui en fait la difficulté.

Car dans IN, A ==> B utilise la fonctionnalité de la multiplication, alors que B ==> A utilise la régularité de la multiplication (on ne peut pas multiplier par 1/2).

Je n'ai volontairement pas précisé dans quel ensemble on travaillait ; ma rédaction envisage bien évidemment un corps, ou "plus grand", pour mettre en évidence les "non-dits" de la preuve au niveau de l'instantiation du théorème utilisé, différence plus subtile, mais incontournable, que le cas de où l'on n'utilise pas le même théorème pour les deux implications.

[ilelogique]

merci pour vos réponses, je comprends bien que les preuves de x=3 =>2x=6 et de 2x=6 =>x=3 ne sont pas les mêmes finalement (car instances différentes du théorême).
L'idée que je proposais (Ne pourrait-on pas, par exemple, définir cela avec des sortes de preuves réversibles ?
(si depuis une théorie T, avec l'hypothèse de la proposition P on parvenait à construire une preuve formelle de Q alors, en gros, en supposant T et Q et en "retournant" la preuve précédente on obtiendrait directement une preuve de P. La preuve par équivalence deviendrait une espèce de preuve non orientée qu'on peut lire dans les deux sens...)) n'existe-t-elle pourtant pas dans la littérature ? est-elle idiote ?
merci