Raisonnement par l'absurde

@Homo Topi : Christophe a détaillé les aspects logiques de la question (il y a une erreur dans son latex, il doit manquer un dollar quelque part, mais je pense qu'il s'en apercevra bientôt).
Dans ta démonstration de l'infinitude des nombres premiers tu n'as nul besoin du RPA. Il suffit de la formuler ainsi :
Soit p un nombre premier. Il est le $n^{ième}$ de la liste, donc les $n$ premiers nombres premiers s'écrivent : $p_1=2, p_2=3, ..., p_n=p$.

Il en est de même de l'irrationalité de $\sqrt{2}$.
Notons $P$ la propriété $\exists x \in \mathbb{\Q}, x^2=2$.
Tu supposes $P$, blablabla, et tu arrives à une contradiction en exhibant une fraction qui est à la fois irréductible et simplifiable.
Moralité : tu as prouvé ce que Christophe appelle "P implique Tout", donc tu as prouvé $\neg P$, CQFD.
Et toujours pas de RPA là-dedans.

Martial a écrit:

Soit p un nombre premier.

Ok, $p=13$.

Martial a écrit:

Il est le $n^{ième}$ de la liste, donc les $n$ premiers nombres premiers s'écrivent : $p_1=2, p_2=3, ..., p_n=p$.

Ok, $n=6$, $p_1=2, p_2=3, p_3=5, p_4=7, p_5=11, p_6=13$

Martial a écrit:

Tu poses $q=p_1.p_2...p_n+1$, et tu montres que $q$ est premier.

Ok, $q=2\times3\times5\times7\times11\times13+1=30031=59\times509$.

Montrons que $q$ est premier...

(:D @NM, je crois que Martial est comme moi ce matin, pas encore très réveillé, moi, je viens seulement de corriger mon dollar.

Je rappelle que la question de savoir si un énoncé "se prouve avec le RPA" n'a pas de sens clair.

1/ Tous les énoncés ont une preuve utilisant le RPA,

2/ Tous les énoncés ont au moins une preuve n'utilisant pas le RPA

3/ Quasiment tous les énoncés sont non prouvables (avec ou sans RPA), tant qu'on ne fait pas assez d'hypothèses (qu'on appelle pudiquement des axiomes)

4/ Que, du fait que les gens raisonnent en logique classique, les axiomes ne sont pas très très regardés dans le détail et il suffit de les changer pour faire disparaitre un RPA

5/ Que donc, la question de HT n'est pas assez précise. Mais que la réponse est sérieusement non, sinon le RPA lui-même pourrait se prouver sans RPA, ce qui me donne l'occasion de rappeler que le RPA est l'axiome:

$$\forall A: ([A\to Tout] \to [(A\to Tout)\to Tout]) \to A$$

et non pas l'axiome, contrairement à un préjugé populaire:

$$\forall A: [(A\to Tout)\to Tout] \to A$$

qui lui est "trivial" sans ajout extérieur de richesse logique.

6/ Concernant l'arithmétique, ces questions sont un peu floues aussi, puisque si on considère que les seules primitives sont $\forall ; \to$ (et éventuellement "et" qui ne pose pas de problème), alors l'arithmétique intuitioniste est égale à l'arithmétique classique et donc la preuve qu'il y a une infinité de nombres premiers est de ce fait intuitionniste.

7/ Quand ce genre de phénomène se produit, même en ajoutant $\exists$, et pour des énoncés "bêtes", la seule chose qui change c'st la longueur de la preuve, puisque dès lors que vous disposez d'une borne, le tiers exclus ne donne qu'un seul avantage, c'est de dire "il existe une preuve intuitionniste de moins de tant de caractères" (à vous de la ptrouver). Exemple: une preuve classique aux "échecs10000" que l'un des deux bords a une stratégie infaillible fait 3 lignes, alors qu'une preuve intuitionniste fera 10^je ne pas combien de lignes.

8/ Je signale une preuve partielle de pourquoi si on prouve $(X\to Tout)\to Tout$ en n'utilisant qu'une seule fois $X$, alors on a une preuve "évidente à partir de la précédente" de $X$.

8.1/ Soient les combinateurs $K,D,B$ tels que :
8.1.1/ $\forall x,y,z: Dxyz > x(yz)$
8.1.2/ $\forall x,y,: Bxy> yx$
8.1.3/ $\forall x,y,: Kxy> x$

8.2/ Une preuve qui n'utilise qu'une seule fois $X\to Tout$ (je mets le reste des axiomes dans une conjonction-contextuée avec $X$), se traduit par une expression écrite avec les 3 machins $D,B,K$ qui décrivent une fonction allant de $(X\to Tout)$ au paradis.

8.3/ J'ajoute une lettre $h$ qui signale que l'hypothèse $X\to Tout$ est faite. J'exécute le mot, de sorte que j'ai un mot $m$ qui désigne un élément du paradis.

8.4/ Ce mot ne peut pas commencer par $D$ et être de la forme $Dpq$, puisque $Dpq$ ne peut garantir que des phrases de la forme $U\to V$, ce qui n'est pas le cas de $Tout$.

8.5/ Ce mot ne peut pas commencer par $K$ et être de la forme $Kp$, puisque $Kp$ ne peut garantir que des phrases de la forme $U\to V$, ce qui n'est pas le cas de $Tout$.

8.6/ Ce mot ne peut pas commencer par $B$ et être de la forme $Bp$, puisque $KB$ ne peut garantir que des phrases de la forme $U\to V$, ce qui n'est pas le cas de $Tout$.

8.7/ Il commence donc par $h$ et est de la forme $hn$. Le mot $n$ NE CONTIENT PAS $h$, puisque $h$ n'a été utilisé qu'une fois. Or $n$ désigne un élément de $X$. On a donc une preuve de $X$ aisée à récupérer.

8.8/ A noter que l'exécution termine toujours puisque chaque pas élimine une lettre, donc il va raccourcir jusqu'à ne plus contenir de sous-mots à exécuter. L'exécution se fait suivant les règles décrites en 8.1 et ce genre de démarche est "généralement" qualifié "d'éliminatrice de coupures", mais ici on est dans un cas simplissime.

8.9/ Donc Homo Topi, oui quand tu n'utilises ton hypothèse $nonX$ qu'une seule fois pour arriver à une absurdité, tu es tranquille, ton RPA s'éliminera facilement.

8.10/ Sauf que attention: quasiment aucun matheux faisant un RPA n'aura "instinctivement" la bêtise de faire un RPA de cette manière. Le besoin qu'ils ressentent du RPA vient "bien évidemment" de la multi-utilisation de l'hypothèse ajoutée pour obtenir l'absurde.

8.11/ De la même manière que si tu files une fonction bluffe $f$ vendue comme allant de $A\to Paradis$ dans Paradis et qu'une personne te rétorque qu'avec elle, elle va au paradis, si elle la duplique 51746 fois pour ce faire, tu auras plein de $f(u(f))$ imbriqués (et de manière éventuellement bouclante) et ça ne te servira à rien de récupérer $u(f)$ en disant "ah ah il appartient à $A$, car il aura été construit avec un $f$ dedans qui était ton bluffe.

8.12/ De la même manière (c'est isomorphe) tu peux espérer (sauf infinis avec axChoix) récupérer un élément de l'espace vectoriel $E$ à partir d'une application affine de $L(L(E,\R), \R)$, même si ca canonicité comporte une partie "transcendantale", alors qu'à l'aide, je ne sais moi, d'une simple application continue, ou même polynomiale allant de $(E\to Tout)$ dans $Tout$; tu n'as strictement aucune chance dans bien des cas de trouver quel élément de $E$ lui serait canoniquement rattaché.

@Christophe : "je crois que Martial est comme moi ce matin, pas encore très réveillé, moi, je viens seulement de corriger mon dollar."

En fait c'est plus compliqué ça : j'ai la tête farcie de forcing, et en plus il faut que j'aille faire des courses à Auchan, et je cherche toutes les combines possibles et imaginables pour retarder... parmi lesquelles expliquer (mal) le RPA à Homo Topi.
Au fait tu as encore un dollar à corriger au paragraphe 8.9 de ton dernier post, lol..

Ah merci, j'y vais sur le champ

@Poirot : soit $P$ l'ensemble des nombres premiers.
Le raisonnement fait ci-dessus montre que, si $p \in P$, alors $\exists q>p, q \in P$.
L'application qui à tout $p \in P$ associe son successeur immédiat est donc une injection de $P$ dans $P$ qui n'est pas surjective, puisque $2$ n'est pas atteint.
Donc $P$ est Dedekind-infini et, par la contraposée de a) il est infini, même dans ZF.

Conclusion : on n'a pas utilisé $AC_{\omega}$.

Il reste 2 questions :
1) La preuve du a) utilise-t-elle RPA ?
2) Ai-je le droit d'utiliser la contraposée dans ce sens-là si je ne suppose pas RPA ?

@Christophe, tu en penses quoi ?

à un mathématicien ou à un logicien ... à un biologiste ou à un cuisinier

Faut il comprendre qu'un logicien n'est pas un mathématicien ou qu'un cuisinier est un bilologiste ?

GBZM a écrit:

Faut il comprendre qu'un logicien n'est pas un mathématicien ou qu'un cuisinier est un bilologiste ?

Non, mais je pense qu'on s'est compris. Si tu penses que le cuisinier dirait que la courgette est un fruit on peut trouver d'autres exemples, la fraise est un fruit en cuisine mais pas en botanique. Ou alors il y a une blague sur "bilologiste" qui m'est passée au dessus de la tête :-S

http://www.les-mathematiques.net/phorum/read.php?16,1998754,1998868#msg-1998868

christophe c a écrit:

et non pas l'axiome, contrairement à un préjugé populaire:

Concernant le point 5/ de ton message, une définition n'a rien à voir avec un "préjugé" populaire. Les gens n'appellent pas certains objets volants "avions" par préjugé populaire mais par convention collective. Ce qui est appelé "raisonnement par l'absurde" par la quasi-totalité des gens qui s'occupent de ce genre de questions est ton deuxième énoncé.

J'adore, en trois lignes Maxtimax répond à la question du début... après 20 pavés :)o

@homo topi, ok, je viens de lire ton commentaire, bon bin j'espère que "cette prose" te sera utile. L'idée c'est que tu peux la garder dans un fichier ou en favoris.

Homo Topi écrivait : http://www.les-mathematiques.net/phorum/read.php?16,1998754,1999142#msg-1999142

---

> Quand je fais un raisonnement par l'absurde, ce que je fais, c'est : je suppose $A$, je fais un
> raisonnement, j'aboutis à $\neg A$. Donc j'ai prouvé $(A \Longrightarrow (A \wedge \neg A))$,
> c'est-à-dire $A \Longrightarrow faux$.

Autrement dit tu as démontré non A. Ben justement, ce n'est pas un vrai raisonnement par l'absurde : un intuitionniste ne trouvera rien à redire à cette démonstration de non A.

Un intuitionniste ralera si tu fais la chose suivante : tu veux démontrer A. Tu supposes non A, et tu en déduis faux ; et là tu dis "Ça y est, j'ai démontré A". L'intuitionniste te dira : "Non, tu as seulement démontré non non A, tu n'as pas démontré A".

1/ Il y a plusieurs choses dans ce que je t'ai dit, c'est pour ça que je les numérote, afin que tu puisses sélectionner les numéros.

2/ La chose à comprendre que vient de te rappeler GBZM, c'est qu'il y a une ENOOOORRRMEEEEE différence entre

2.1/ prouver que A => Tout et en supposant A et en déduisant Tout. Ca n'a rien d'un RPA, c'est une étourderie fréquente parce que les gens OUBLIENT que nonA C'est A=>Tout

2.2/ Prouver (A=>Tout)=>Tout et PRETENDRE qu'ainsi on a prouvé A.

3/ Ceci étant dit, tu peux ne pas lire la suite.

4/ La suite était que, quand j'ai lu ta demande de bon matin, "tu semblais espérer" que quand on a prouvé
(A=>Tout)=>Tout, "on voudrait bien DANS CERTAINS CAS, passer du temps récréatif ou sérieux à vérifier si on ne pourrait pas prouver directement A d'une AUTRE MANIERE.

5/ Et là, je t'ai juste informé d'un cas où c'est TOUJOURS POSSIBLE, qui est quand dans ta preuve de (A=>Tout)=>Tout, c'est à dire quand tu as supposé A=>Tout et finalement déduit A, tu n'as utilisé QU UNE SEULE FOIS l'hypothèse A=>Tout.

N'hésite pas si tu as des questions, mais je vais sortir donc ne t'inquiète pas.

J'augmente un peu la liste:

7/ [(nonA)=>(nonA)] => (je l'avais oublié, quelle honte :-D )

8/ ((A et => C) => ((A=>C) ou (B=>C))

9/ [ (nonA) =>B ] => (A ou

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

Si tu veux un repère très simple: un théorème est intuitionniste quand il te donne un élément canonique d'un ensemble, comme suit (ce que je te dis là est officiel et prouvé):

D1/ (A et := (A×B)

D2/ (A=>B) := (ensemble des applications de A dans

D3/ (A ou := A union B

D4/ $\forall x\in J: R(x):=$ l'intersection des $R(x)$ quand $x$ parcourt $J$

D5/ $\exists x\in J: R(x) := $ la réunion des $R(x)$ quand $x$ parcourt $J$

Si tu ne parviens pas à SANS Y TOUCHER repenser juste ta preuve en ces termes, c'est qu'elle n'est pas intuitionniste.

Par exemple, si tu essaies de trouver un élément dans $[A$ union $(A\to ]$, tu seras le roi du monde, mais ce n'est pas possible (sans l'axiome du choix, car il faut voir les lettres comme dépendant d'un petit indice $i$ jamais écrit).

Ce repère est vraiment simple à appliquer pour un matheux lambda indépendamment de sa spécialité.

Par exemple, $A\to (A\to $ peut être envoyé dans $A\to B$, via $f\mapsto [x\mapsto f(x)(x)]$, mais tu vois la DUPLICATION évoquée ce matin.


Tu peux "te débarraser" d'un RPA n'ayant pas fait usage de duplication en (sans rien changer) REPENSANT à tes arguments comme s'ils étaient des applications affines (ou linéaires).

Et là, tu vois bien qu'avoir construit un élément du bidual, c'est avoir construit un élément de l'espace lui-même, SAUF si tu as dupliqué car alors ta preuve va par exemple te donner une forme BILINEAIRE de $E^*\times E^*$ dans $\R$ (j'identifie $\R$ au paradis, c'est une autre affaire), et là, tu n'as plus strictement aucune prise pour en tirer un élément de $E$. Ce phénomène intervient en magie quantique ( tu ne peux pas aller de $E$ dans $E\otimes E$, texto nommé non clonage quantique).

Pardon pour l’évidence mais « $Paradis$ », c’est quoi ? C’est « $Tout$ » ?

Ce que je peux faire, si quelqu'un poste une preuve formelle de 5 à 6 lignes d'un truc qui lui tient à coeur, c'est montrer comment tout parser en détail, ainsi que traduire dans les sémantiques diverses et dans la CCH.

On a deux preuves par l'absurde célèbres des énoncés (avec les hypothèses adéquates) suivants:

1/ $a^2=0\to a=0$

2/ $(\forall x>0: a\leq x)\to (a\leq 0)$

Mais peut-être quelqu'un aura-t-il envie d'un truc "un peu plus cossu"?