Raisonnement par l'absurde

Rambert

Bonjour

Je voulais connaître l'existence (ou non?) d'un exemple pour lequel le raisonnement par l'absurde est invalide pour démontrer une proposition ou un théorème

Merci

Dom

Invalide ?
C’est-à-dire ?

Poirot

Toute démonstration en logique classique peut être transformée en une démonstration par l'absurde.

Rambert

Dom http://www.les-mathematiques.net/phorum/read.php?16,2205952,2205954#msg-2205954http://serge.mehl.free.fr/chrono/Brouwer.html

"Dans l'ensemble accepté N, la définition d'un nombre premier est valide car on saura ou bout d'un nombre fini d'essais si le nombre est premier ou non. La preuve de l'infinitude des nombres premiers, pourtant très belle, donnée par Euclide, reposant sur un raisonnement par réduction à l'absurde, est rejetée par Brouwer "

Poirot

Sujet abordé 30000 fois ici et ailleurs, la preuve de l'infinitude des nombres premiers n'est pas une preuve par l'absurde. La preuve montre que pour toute famille finie de nombres premiers, il existe un nombre premier ne lui appartenant pas.

Maxtimax

Une démonstration par l'absurde n'est jamais invalide classiquement.

En logique intuitionniste, elle n'est valide que si l'énoncé qu'on cherche à prouver est de la forme $\neg A$ (pour un tel énoncé, on a effectivement $\neg\neg\neg A\implies \neg A$), donc pour une réponse à ta question : presque toutes.

Par contre l'extrait que tu cites est faux. La preuve d'Euclide (attention, pas ses interprétations modernes) est complètement constructive et intuitionniste. Simplement, en mathématiques classiques, on considérera qu'elle démontre "l'ensemble des nombres premiers est infini" (en donnant un sens positif au mot "infini"), alors que ce qu'elle démontre c'est "l'ensemble des nombres premiers n'est pas fini".

D'ailleurs c'est sous cette seconde forme que c'est énoncé par Euclide: "aucune collection finie de nombres premiers n'est complète". La preuve est complètement constructive: elle prend une collection finie de nombres premiers, et fournit un nombre premier qui n'est pas dedans

christophe c

C'est un sujet spécialisé, il faudrait que tu précises ta question, qui formulée comme telle n'a pas de réponse.

Tu as plusieurs logiques, dont deux vieilles et célèbres qui sont :

La LC (logique classique)

La LI (logique intuitionniste)

On obtient la LC en ajoutant l'axiome du RPA à la LI (ie $\forall X: [((X\to Tout) \to Tout)\to X]$)

Toutes les maths se font en LC, même si on étudie la LI en tant qu'objet à part et fait parfois quelques raeensement en disant "tiens ce passage-là est de la pure LI"

Mais c'est assez local (par exemple même $\{0;1\}$ n'est pas bien ordonnable si on ne met pas un peu de logique classique.) La LI pure est très spéciale.

La seule chose qu'on peut te dire c'est que quand M.Dupont te présente une preuve avec un RPA, tu peux lui répondre "tu es en logique classique, mais serait-tu capable de le prouver en LI?". Et là, selon le truc que c'est tu le mettras plus ou moins en difficulté.

Concernant les nombres entiers, c'est un assez mauvais exemple, car tout les énoncés sans quantificateurs a la valeur vrai ou la valeur faux et du coup les EVENTUELS survenues d'impuissance de l'intuitionniste ne se feront que sur les "ou" et des $\exists$ "en dur" qui ne sont pas tellement "intéressants", du moins d'un point de vue non spécialisé.

Mais tout ce qui est écrit avec "et" et quelque soit qui est prouvable classiquement l'est intuitionnistiquement. Cela provient de ce que les théorèmes suivants sont intuitionistes:

[non (non =>B ] => (non (non (A=>B))) => (A=>B)

$\forall R $ si $\forall a: [ (non(non(R(a)))) \Rightarrow R(a) ] $ alors $non (non (\forall xR(x))) =>(\forall xR(x))$