Un scoop que je partage

Je partage un résultat dont l'histoire sur le forum, grâce à foys a été possible et qui a été peu banal (un mail, une recherche d'extraits, un raisonnement catégorique réservé aux initiés des diagrammes cartésiens, bref).


Vous connaissez tous l'ensemble vide $\emptyset$. Vous savez qu'il n'a qu'un seul sous-ensemble, l'ensemble vide lui-même. Vous connaissez aussi probablement tous $1$, mais vous êtes peut-être un moins nombreux à sa voir qu'il s'agit de $\{0\}$. A noter que $\emptyset$ est noté $0$.

$1$ ne contient qu'un seul élément, l'ensemble vide. Si vous raisonnez en logique classique, il a deux sous-ensembles, l'ensemble vide $0$ et lui-même $1$.

Il est maintenant bien connu que la logique intuitionniste (c'est à dire la logique classique dont on retire le droit de raisonner par l'absurde, le droit de dire que non(non(A)) implique A, le droit d'admettre A ou nonA) ne permet pas de prouver qu'il n'y a que deux sous-ensembles de $1$.

En fait, ça peut même aller très loin. Pour n'importe quel espace topologique $E$, il y a un modèle de la théorie des ensembles intuitionniste où $(P(1),\subseteq)$ est très exactement structuré comme l'ensemble des ouverts de $E$ muni de l'inclusion.

Un grand classique (en logique classique) qui apparait comme une trivialité pour tout le monde est de dire que si $f$ est une injection de $P(1)$ dans $P(1)$ alors $f\circ f=identite$. Bin voui, si on raisonne classiquement, ou bien $f(0)=0$ et dans ce cas $f(1)=1$, donc $f=identite$, ou bien $f(0)=1$, mais dans ce cas $f(1)=0$ et encore une fois $f\circ f=identite$.

Très bien, mais ça, c'est un raisonnement on ne peut plus classique. Il n'a rien d'intuitionniste!! En effet, en intuitionnisme, ce n'est pas parce qu'un élément $x$ est différent de $0$ qu'il est égal à $1$. On n'a pas le tiers exclus, ni en fait "rien du tout" de ce genre.

Il apparait donc très étonnant, et "peu probable" que l'on puisse fournir une preuve purement intuitionniste qu'une injection $f:P(1)\to P(1)$ soit forcément une involution (ie $f\circ f=identite$).

Et bien après une petite journée de réflexion (lien plus haut), je tiens à vous faire partager un truc de dingue: si si on peut prouver de manière purement intuitionniste que $f\circ f= identite$.

Je vais soigner la chose, afin qu'un maximum de visiteurs qui tomberont dessus comprennent et soient marqués par cet évènement (dont je regrette qu'il ait eu si peu d'audience quand il a été découvert, probablement il y a assez longtemps).

Avant de lire la suite, essayez donc d'y arriver seuls, vous verrez que ce n'est pas facile.

[large]En accompagnement de ce post, je fais un post où j'informe les matheux non logiciens de ce qu'est la logique intuitionniste[/large]




L'hypothèse est donc que $f$ est une injection de $P(1)$ dans $P(1)$. Cela signifie, je le rappelle que $\forall x,y$ dans $P(1)$, si $f(x)=f(y)$ alors $x=y$. On va prouver DE MANIERE INTUITIONNISTE que $f\circ f=identite$

Etant donnés $u,v$ deux parties de $1$, il y a évidemment équivalence entre $u\subseteq v$ et $0\in u\Rightarrow 0\in v$. En effet, je rappelle que $X$ est une partie de $1$ si et seulement si $\forall t: (t\in X\Rightarrow t=0)$. De plus pour toute partie $X$ de $1$, $[0\in X\iff X=1]$

Ainsi, pour prouver que $X=Y$, il nous suffira de prouver que $X\subseteq Y$ et $Y\subseteq X$, donc de prouver que $X=1\iff Y=1$.

Soit $U$ l'ensemble des parties $x$ de $1$ telles que $f(x)=1$.

Nous montrons que $\forall x\in U: x=f(1)$. Comme dit avant, pour chaque $x\in U$, il suffit de prouver $x=1\iff f(1)=1$. Or c'est presque évident: si $x=1$, alors comme $f(x)=1$ puisque $x\in U$, on a $f(1)=1$. Réciproquement, si $f(1)=1$, alors comme $f(x)=1$ et $f$ injective, il suit $x=1$.

Nous montrons maintenant que $\forall x\in U: f(f(x)) =x$. Là encore, c'est presque évident: si $x\in U$ alors $f(x)=1$ et d'après ce qui précède, $f(1)=x$. N'importe quel lecteur voit alors que $f(f(x))=x$.

C'est presque terminé.

Soit $x$ une partie de $1$. Il nous reste à prouver que $f(f(x))=x$.
L'injectivité de $f$ fait qu'il nous suffit de prouver que $f(f(f(x))) = f(x)$.
Et là encore nous nous contentons de prouver que $f(f(f(x)))=1\iff f(x)=1$.

Supposons $f(x)=1$. Alors $x\in U$ donc $f(f(x)) =x$ donc $f(f(f(x))) = f(x)=1$

Supposons $f(f(f(x))) = 1$. Alors $f(f(x))\in U$ puisque son image par $f$ est $1$.
Donc $f(f(x)) = f(1)$ (puisque $f(f(x))\in U$) donc $f(x)=1$

On vient bien de justifier $f(f(f(x))) =1\iff f(x)=1$.

CQFD

Franchement, qui eut pensé qu'il existât une preuve intuitionniste aussi subtile d'un truc qui semble à donf "classique"?

La version catégorique de ce théorème