Démontrable par l'absurde...démonstrable par voie directe

[invitea0ece8ff]

Désolé de remonté un topic un peut vieu, mais le sujet m'interresse.

J'précise que j'ai lut tout les posts, mais que quelque concept et subtilité m'on échapé.

Donc voila j'aurai plusieur questions:
1) Peut t'on transformer toutes démonstrations de la forme:
(A=>B=>...=>faux) => non(A)
en une démonstration de la forme:
vrai=>...=>non(A)

2) Mon raisonnement est t'il valide (bien que pas tres formel):
Admettre la validité de toutes les démonstrations par l'absurde de la forme:
(non(A)=>faux)=>A
est équivalent a admettre la validité du tiers exclu.

Admettre que toute les démonstrations utilisant le tiers exclu peuvent etre mit sous la forme:
vrai=>...=>A
de tel manière qu'aucune fois le tiers exclut n'est néccessaire pour passer d'une proposition a l'autre, revient a admettre que le tiers exclu est déductible des autres axiomes de la logique intuitionniste.

Comme le tier exclu n'est pas déductible de la logique intuitionniste, alors la réponse a la question de dépare est non.

3) Est s'que j'ai bien compris:
Dire que A est indéductible, veut dire qu'il n'existe pas de "chemins" fini, qui permettent en "commençant" par vrai, de "rejoindre" A (a l'aide d'une succession d'implications).
Ni de chemin qui permettent en commençant par A, de rejoindre faux.

non(A) signifie qu'il existe un chemin, permettant d'aller de A à faux.
Donc si A est indéductible, non(A) est faux (car un tel chemin n'existe pas).
-----

[invité576543]

Donc voila j'aurai plusieur questions:
1) Peut t'on transformer toutes démonstrations de la forme:
(A=>B=>...=>faux) => non(A)
en une démonstration de la forme:
vrai=>...=>non(A)

Il y a un problème de notation. Le signe "=>" est, usuellement, un signe apparaissant dans les expressions logiques, ce n'est pas un signe décrivant une étape de démonstration. Dans cette discussion la différence est essentielle, du coup ta question est difficile à comprendre.

Admettre la validité de toutes les démonstrations par l'absurde de la forme:
(non(A)=>faux)=>A
est équivalent a admettre la validité du tiers exclu.

Oui, avec la même remarque sur le vocabulaire. En pratique, à partir de

non(A)=>faux

on peut déduire par application de la contraposition

non(faux) => non(non(A))

d'où

non(non(A))

et on peut passer de là à A uniquement avec le tiers exclus.

3) Est s'que j'ai bien compris:
Dire que A est indéductible, veut dire qu'il n'existe pas de "chemins" fini, qui permettent en "commençant" par vrai, de "rejoindre" A (a l'aide d'une succession d'implications).

A l'aide d'une succession d'étapes de démonstration, chaque passage devant être conforme à une règle de démonstration parmi celles valides dans la théorie de la démonstration considérée.

Il me semble que cette définition revient à indéductible = non démontrable.

non(A) signifie qu'il existe un chemin, permettant d'aller de A à faux.

oui

Donc si A est indéductible, non(A) est faux (car un tel chemin n'existe pas).

Non, on peut avoir à la fois A non démontrable et non(A) non démontrable.

Cordialement,

[leon1789]

Désolé de remonté un topic un peut vieu, mais le sujet m'interresse.

y a pas lieu d'être désolé de s'intéresser

J'précise que j'ai lut tout les posts, mais que quelque concept et subtilité m'on échapé.

courageux !

3) Est s'que j'ai bien compris:
Dire que A est indéductible, veut dire qu'il n'existe pas de "chemins" fini, qui permettent en "commençant" par vrai, de "rejoindre" A (a l'aide d'une succession d'implications).
Ni de chemin qui permettent en commençant par A, de rejoindre faux.

non(A) signifie qu'il existe un chemin, permettant d'aller de A à faux.

Donc si A est indéductible, non(A) est faux (car un tel chemin n'existe pas).

Comme le dit Michel, non(A) n'est pas forcément faux, mais peut être aussi indécidable.

En tout cas, si A est indécidable alors non(A) ne peut pas être démontré vrai (simplement par définition).

A mon avis, je crois que, des exemples (en logique ad hoc, pas ZFC ) peuvent être :
A = l'axiome du choix --> non(A) indécidable
A = [P ou non(P)] --> non(A) faux

[sadben2004]

Je vois pas de différence entre le raisonnement par absurde et la contraposé :

On veut montrer que A est vrai (sous aucune hypothèse, ou par exemple sous l'hypothèse que 1#0 ou une autre assertion V VRAIE)
On montre alors que nonA => non V

une dem par contraposé est tjs <=> à un raisonnement directe. mais un mode est souvent plus intuitif que l'autre.
(non a=>non b=>non c=>non d) <=> ( d=>c=>b=>a)

sqrt(2) IN Q => .... => (Il existe p q paires et premiers entre eux )
(Il n'existe pas p et q paires et premiers entre eux) => .... => sqrt(2) est irrationnelle

Je me trompe ?

[invité576543]

Je vois pas de différence entre le raisonnement par absurde et la contraposé :

Il y a deux "raisonnements par contraposée"

Passer de A => B à non(A) => non(B), qui n'est pas comparable à un raisonnement par l'absurde,

et

passer de non(A) => B à non(B) => A, que l'on peut comparer à un raisonnement par l'absurde (en mettant "faux" à la place de B par exemple).

Cordialement,

[leon1789]

Il y a deux "raisonnements par contraposée"

Passer de A => B à non(B) => non(A), qui n'est pas comparable à un raisonnement par l'absurde,

et

passer de non(A) => B à non(B) => A, que l'on peut comparer à un raisonnement par l'absurde (en mettant "faux" à la place de B par exemple).

Cordialement,

Il y a aussi deux raisonnements par l'absurde : la réduction et le détour.

Je pense que passer de A => B à non B => non A, c'est comparable à une réduction à l'absurde : sachant (A => B)
non B => (B => faux) => (A = > B => faux) => non A

Passer de non(A) => non(B) à B => A, c'est effectivement comparable à un détour par l'absurde.

[invité576543]

Il y a aussi deux raisonnements par l'absurde : la réduction et le détour.

Je pense que passer de A => B à non B => non A, c'est comparable à une réduction à l'absurde : sachant (A => B)
non B => (B => faux) => (A = > B => faux) => non A

Passer de non(A) => non(B) à B => A, c'est effectivement comparable à un détour par l'absurde.

D'accord.

J'ai juste pris le pli de réserver "raisonnement par l'absurde" au détour (le seul cas qui commence par "je suppose le contraire de ce que je veux démontrer, alors ...").

Cordialement,

[invite6754323456711]

D'accord.

J'ai juste pris le pli de réserver "raisonnement par l'absurde" au détour (le seul cas qui commence par "je suppose le contraire de ce que je veux démontrer, alors ...").

Cordialement,

Quelle différence faite vous (mmy et leon) en logique classique entre réduction à l’absurde et détour par l’absurde ?



Patrick

[invité576543]

Quelle différence faite vous (mmy et leon) en logique classique entre réduction à l’absurde et détour par l’absurde ?

Si tu regardes en détail, tu détecteras des remplacement de non(non(P)) par P dans un cas et pas dans l'autre.

Cordialement,

[invite6754323456711]

Si tu regardes en détail, tu détecteras des remplacement de non(non(P)) par P dans un cas et pas dans l'autre.

Cordialement,

Oui mais n'est-il pas non(non(P)) <--> P en logique classique. Qu'est que cela apporterait de faire la distinction ?

Patrick

[leon1789]

Oui mais n'est-il pas non(non(P)) <--> P en logique classique. Qu'est que cela apporterait de faire la distinction ?

La distinction se fait justement en logique intuitionniste, où non(non(P)) <-- P, mais pas l'autre sens.

[invitea0ece8ff]

OK, donc j'ai compris de travers.
on a donc enfaite si j'ai bien compris se coup si:
avec A -> B qui signifie, qu'il est possible de passer de A a B a l'aide d'une succession d'etape de démonstrations.

A, signifie:
1 -> A

non(A) signifie:
A -> 0
(et non pas:
non(1 -> A)
mais:
(A -> 0) => non(1 -> A) si jamais la théorie est cohérente
ou de maniere plus condenser:
non(1->0)

Il est important de noté que la réciproque est fausse:
non(1 -> A) => (A -> 0)
c'est d'ailleur se fait qui permet d'avoir des énoncés indémontrables.)

A indemontrable signifie:
non(1 -> A) et non(A->0)

donc on a, a partir de ces définitions:

non(non(A)) signifie:
non(A) -> 0

Si jamais la transformation suivante est possible:
non(A) -> 0 remplacer par:
(A->0) -> 0

Ceci signifie que la théorie peut "parler" d'elle même, qui l'y a un mélange entre le signifiant et le signifié, ceci néccessite aussi une sorte de processus recursif entre ces deux notions.


La règle du tier exclu dit alors (si l'on l'ajoute):
(A->0)->0 => A->1
Si jamais l'on s'interresse a la sémantique, ceci veut dire que quand la théorie utilisé nous dit: il est impossible de trouver 0 a partir de A,
alors il est obligatoirement possible de trouver 1, a partir de A dans cette théorie.

Ici il faut faire attention, cela ne signifie pas, comme l'on pourrai le croire a premiere vu, que tout est démontrable dans cette théorie, car la théorie n'est pas obligé de nous dire: "il est impossible de trouver 0 a partir de A".

maintenant si A est indémontrable, qu'en est t'il de non(A):
non(1 -> A) et non(A->0) et A->0 = faux
donc non(A) est faux

Et la mon erreur a été de confondre la théorie et la "meta-théorie"
non(A) faux, ne signifie pas:
non(non(A))

Par contre l'on peut remarquer que, si l'on considere que la signification de la théorie sur laquel on se penche est valide, on a:
non(non(A)) => non(A) faux

Mais pas l'inverse !

Voila, j'espere que cette fois j'ai bien compris!

[leon1789]

J'ai juste pris le pli de réserver "raisonnement par l'absurde" au détour (le seul cas qui commence par "je suppose le contraire de ce que je veux démontrer, alors ...").

Une réduction à l'absurde peut aussi commencer par l'écriture "je suppose le contraire de ce que je veux démontrer, alors ..."

Formellement, imaginons une suite d'implications : non B => ... => faux.
C'est une réduction à l'absurde de non non B (dont non B est la négation, car non non non B = non B)
C'est aussi un détour par l'absurde pour démontrer B (car non non B = B via tiers exclu)

Je me trompe ? C'est un peu tiré par les cheveux : démontre-t-on souvent non non B ?

Mais quand même ! pour démontrer , on commence bien par écrire pour faire une réduction à l'absurde...

[invitea0ece8ff]

J'vien de me rendre compte que mon message est difficilement comprehensible, parce que j'n'est pas bien fait la distinction entre le non de la "théorie analyser", et le non de la théorie qu'on analyse.

Mais je retrouve plus comment éditer.

[leon1789]

Mais je retrouve plus comment éditer.

Passer 5 minutes, je crois qu'on ne peut plus modifier ses messages.

[invité576543]

Une réduction à l'absurde peut aussi commencer par l'écriture "je suppose le contraire de ce que je veux démontrer, alors ..."

Pourrais-tu reprendre ton exemple en écrivant A pour ce que l'on veut démontrer?

Cordialement,

[leon1789]

Pourrais-tu reprendre ton exemple en écrivant A pour ce que l'on veut démontrer?

On veut démontrer A où (penser à et )

Plusieurs stratégies :

-1- par un détour par l'absurde, on écrit [non A], et on trouve une contradiction... Ainsi [non non A] est vrai donc [A] est vrai (par tiers exclu)

-2- par une réduction par l'absurde, on écrit [ B], et on trouve une contradiction. Ainsi [non B] est prouvé.

Cela étant, en écrivant [ B], on a aussi [non A] car [non A] = [non non B]. Ici la réduction à l'absurde commence donc par une supposition plus forte que la négation [non A] que l'on fait par un détour.

-3- par une réduction par l'absurde différente : on écrit [non non B], et on trouve une contradiction. Ainsi on prouve [non non non B], et donc A=[non B] est vrai (car triple négation <=> négation)


Ce qui est amusant, c'est que les stratégies -1- et -3- ne différente finalement en rien puisque [non A] = [non non B] !
Cela dit, en réalité, on utilise plutôt la stratégie 2.

Je me trompe ? J'espère que je suis clair.

[invité576543]

On veut démontrer A où (...)

-2- par une réduction par l'absurde, on écrit [ B], et on trouve une contradiction. Ainsi [non B] est prouvé.

Ce n'est donc pas "je suppose la négation de ce que je veux prouver, alors...". C'est "je suppose B tel que ce que je veux prouver est la négation de B, alors...".

Cordialement,

[leon1789]

Ce n'est donc pas "je suppose le contraire de ce que je veux prouver, alors...". C'est "je suppose B tel que ce que je veux prouver est non(B), alors...".

Cordialement,

Oui, dans le cas -2-, tu as raison.

Mais dans le cas -3- qui est aussi une réduction à l'absurde, on écrit bien la négation de ce qu'on veut démontrer.

Es-tu d'accord ?
Si oui, peut-on conclure que pour démontrer une négation [non B], un détour par l'absurde est un cas particulier d'une réduction par l'absurde à cause du cas -3- ?

[invitea0ece8ff]

Oui, dans le cas -2-, tu as raison.

Mais dans le cas -3- qui est aussi une réduction à l'absurde, on écrit bien la négation de ce qu'on veut démontrer.

Es-tu d'accord ?
Si oui, peut-on conclure que pour démontrer une négation [non B], un détour par l'absurde est un cas particulier d'une réduction par l'absurde à cause du cas -3- ?

Effectivement, j'avait pas remarquer sa.

Donc la demonstration par l'absurde n'implique pas dutout d'utiliser le tiers exclu, le detour par l'absurde etant juste une demonstration par l'absurde ou l'on utilise le tiers exclu a la fin.

Mais donc j'définirai la question du premier post ainci:
si:
A->0
est ce que:
1->(A->0)

En gardan la notation que j'ai utiliser dans mon dernier post.
Et donc, il me semble asser clair que sa a pas de raison d'etre le cas pour une théorie quelconque.

[invité576543]

Mais dans le cas -3- qui est aussi une réduction à l'absurde, on écrit bien la négation de ce qu'on veut démontrer.

J'y réfléchis!

Cdlt,

[invité576543]

-3- par une réduction par l'absurde différente : on écrit [non non B], et on trouve une contradiction. Ainsi on prouve [non non non B], et donc A=[non B] est vrai (car triple négation <=> négation)

Comme A=non(B), je peux réécrire (en rouge les différences)

-3- par une réduction par l'absurde différente : on écrit [non A], et on trouve une contradiction. Ainsi on prouve [non non A], et comme A = non(B), on a prouvé [non non non B], donc [non B] (car triple négation <=> négation), donc A.

En d'autres termes, tu dis qu'une démonstration par détour par l'absurde de A est acceptable en intuitionniste à la condition que A soit de la forme non(B), la raison en serait que (triple négation <=> négation) est une régle de démonstration acceptable en intuitionniste, c'est cela?

On doit pouvoir reformuler comme suit:

Si A est de la forme non(B), alors non(non(A)) => A, en utilisant ta règle sur la triple négation. Or il clair que si non(non(A)) => A , alors une démonstration par l'absurde de A est acceptable.

Tout tourne autour de ta règle sur la triple négation, je ne me rappelle plus (et ai la flemme de chercher) si tu as fourni une référence indépendante sur cette règle...

Cordialement,

[leon1789]

En d'autres termes, tu dis qu'une démonstration par détour par l'absurde de A est acceptable en intuitionniste à la condition que A soit de la forme non(B), la raison en serait que (triple négation <=> négation) est une régle de démonstration acceptable en intuitionniste, c'est cela?

oui.

Tout tourne autour de ta règle sur la triple négation, je ne me rappelle plus (et ai la flemme de chercher) si tu as fourni une référence indépendante sur cette règle...

exactement.

On a clairement [non non (non E) <= (non E)] (triple négation <= négation)

Si on faire agir la version faible du principe de contraposition [C => D] => [non D => non C]
sur l'implication [E => non non E] ,
on obtient [non non non E => non E] (triple négation => négation)

[leon1789]

Mais donc j'définirai la question du premier post ainci:
si:
A->0
est ce que:
1->(A->0)

En gardan la notation que j'ai utiliser dans mon dernier post.
Et donc, il me semble asser clair que sa a pas de raison d'etre le cas pour une théorie quelconque.

Sans tiers exclu, ça parait effectivement difficile.

[leon1789]

hello hello,

Non rationnel est intrinsèquement négatif, puisqu'on peut travailler dans Q sans s'occuper de R. On dit simplement que x²-2 n'a pas de racine, ou n'est pas réductible, etc. Et je ne vois pas comment on peut écrire cela positivement.

-- Une preuve par l'absurde commence par , etc.


-- Mais une preuve "directe" peut être comme cela ? Soit , alors
Comme , on a impair ( est la valuation en 2) et par ailleurs pair. Ainsi , donc
Donc le polynôme X²-2 n'a pas de racine dans Q.

Est-ce une preuve "positive" ?


-- Pour moi, cette preuve "directe" est nettement plus intéressante que toute preuve par l'absurde (et cela montre qu'elles ne sont absolument pas de même nature !) car toutes les assertions de cette preuve sont vraies, y compris , plus fort que le résultat que l'on en retient.
Cela arrive de temps en temps qu'une preuve "directe" démontre davantage que ce que l'on en retient (on le voit bien quand, ultérieurement, on a besoin d'une assertion "juste survolée" dans la preuve directe). Et ceci ne peut évidemment pas faire une preuve par l'absurde...

[invite7863222222222]

Comme , on a impair ( est la valuation en 2) et par ailleurs pair. Ainsi

Bonjour,

Ce passage est sensé être évident ?

[invite7863222222222]

Bonjour,

Ce passage est sensé être évident ?

Je n'ai rien dit, effectivement c'est bon.

[invité576543]

on a impair ( est la valuation en 2) et par ailleurs pair. Ainsi

Comment démontres-tu le "ainsi"?

(Je ne cherche pas la petite bête, a priori c'est convaincant, je demande juste de développer le point le moins bien développé, le moins "évident" comme dit jreeman.)

Cordialement,

[leon1789]

Bonjour,

Ce passage est sensé être évident ?

p² et 2q² n'ayant pas la même valuation, leur différence n'est pas nulle (de valuation égale au minimum de celle de p² ou de 2q²) donc elle vaut au moins 1.

On pourrait dire que c'est un peu "tiré par les cheveux" car le fait que la différence n'est pas nulle suffit pour faire conclure... sans aller chercher une minoration par 1. ok

[leon1789]

Je ne cherche pas la petite bête

Pas de problème ! Effectivement, c'est peut-être un point sensible dans le raisonnement : j'aurais dû argumenter un peu.