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
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]
Ici la même preuve présenté un poil différemment
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
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Il arrive, plus souvent qu'on ne le pense, qu'en déroulant les axiomes et leurs premières conséquences, alors la conclusion tombe toute seule. Mais il est possible que le problème résiste à ce genre d'attaques et qu'il faille chercher ailleurs.
** dans le premier post
Pourquoi ? Je pense au contraire que c'est typiquement un exemple où la preuve catégorique vient d'abord. C'est d'ailleurs dans le cadre catégorique que le problème se pose assez naturellement.
Ca me fait un peu penser au fait que l'axiome du choix => le tiers exclu (une preuve quasi-évidente du type suffit d'y penser, puis pour publier, une probable traduction en termes "sérieux", ie pour envoi à un journal catégorique).
Mais tout ça c'est l'intimité des matheux, on ne sait jamais qui a trouvé le premier les choses (sauf s'il publie) et comme les preuve intuitionnistes élémentaires ne sont pas publiables, il reste l'envoi sur un forum ou par mail pour diffuser (et si un catégoriste est informé, une publication "sérieuse" avec des flèches dans un journal catégorique)
mise aussi dans le premier post.
La preuve en diagramme est tout à fait constructive. Et pour moi elle est largement aussi parlante que la preuve en formule que tu as écrite. D'ailleurs, tout à fait objectivement, c'est exactement la même preuve. Ce que tu as écrit est la traduction fidèle de ce que racontent les diagrammes.
Tu n'es pas familier avec les diagrammes et tu as du mal à raisonner dessus ; ça ne te parle pas. Soit. Mais tu sembles en déduire, comme une évidence, que c'est le cas pour tout le monde. Tu te trompes.
Et voyons d'où vient cet exercice. Il vient du livre de Johnstone sur les topos. C'est effectivement dans le cadre des topos que le problème se pose naturellement. Où ailleurs parle-t-on de classifiant des sous-objets et de flèche de ce classifiant dans lui-même ? C'est bien dans un topos.
J'ai moi-même eu une pratique assidue et professionnelle des topos il y a une quarantaine d'années. Ce type de preuve catégorique est tout à fait dans l'esprit des travaux sur les topos, et je suis convaincu que c'est la preuve originelle.
Maintenant, je ne peux pas t'empêcher de te raconter l'histoire d'une manière qui te plait mieux ...
Non, pas pour tout le monde, mais pour une proportion des mathématiciens (peut-être 40-50%, je ne sais pas, ceux qui ne font pas de catégories)
Non , non ce n'est pas une question de me plaire, je ne sais pas c'est tout. Je te fais confiance quand tu témoignes de l'autre possibilité.
La seule chose dont je suis assez convaincu, c'est que de toute façon il n'existe pas de journal qui prendrait les curiosités (les preuves de 10-15 lignes faciles une fois trouvées, mais pas forcément faciles à trouver) comme par exemple des preuves intuitionnistes inédites de trivialités classiques. Donc pour moi, c'est simple, les gars qui aiment ça (je ne sais pas s'il y en a beaucoup et même s'il y en a), ou bien ne publient pas et ça peut se perdre, ou bien traduisent ça (automatiquement, algo exposé par Prouté par exemple) en catégories et publient dans un journal catégorique.
Mais évidemment ce n'est pas un argument pour dire que l'exemple précis de ce fil a suivi ce destin, je n'en sais strictement rien. Je ne sais pas plus si le théorème [Choix => Tiers exclu] a suivi ce destin, je n'en sais strictement rien.
Par contre, quand j'ai vu que ce théorème, je le découvre (je parle de la version "preuve intuitionniste de blabla", pas de la version catégorie) à 50ans, ça m'a fait un choc et c'est pourquoi, j'ai envoyé un mail à "tous@Pariscnrsblabla" parce que je suis quasi sûr que quels que soient leur destin, si ces curiosités restent à l'état de simple article dans un journal spécialisé de catégorie, les gens risquent de jamais les connaitre.
Or je trouve que le fait qu'il existe une preuve constructive de l'involutivité de n'importe quelle injection de P(1) dans P(1) doit être connu de tous.
Et en fait j'espère que les curiosités de même nature (en 10ans j'en ai rencontré 2 c'est peu, celles signalées ci-dessus) feront l'objet de publicité (non catégorique j'entends: les versions "preuve intuitionniste de").
Ah bah ça c'est parfaitement clair et j'en sais quelque chose, j'ai passé la journée d'hier à taper une traduction1, puis 2, puis 3, puis 4*** de plus en plus courtes pour arriver à un truc "présentable. Autrement dit, j'ai fait le chemin inverse, ie pris la preuve en diagrammes pour "redescendre" à un niveau élémentaire (ie maths basiques "officiellement" que tout étudiant de L1 est "censé" comprendre). Et j'ai été très poussif, m'a fallu deux traductions pour remplacer $f\circ T\circ <>_U$ par... "constante f(1)" :-D:-D
*** voir lien tout en haut de mon premier post
Je m'insurge encore dans des discussions dont l'écriture formelle de la logique me dépasse parfois. En cela je me considère comme un classique. Mais dans votre démo quand vous dites.
Je vois pas qu'est qui permet de dire: Donc f(f((x))=f(1)
Par ailleurs je suis ce forum depuis un moment et là @christophe, vous reparlez encore de l'axiome du choix et du problème du tiers exclu. A mon niveau (je repense au problème du paradoxe de Russell, dont vous me dites que c'est plus un paradoxe, mais plutôt un théorème) je reviens confirmer ou poser la réflexion dans le sens que ce que vous appelez théorème pour évacuer le paradoxe de Russell est en fait le nouveau axiome et l'axiome du choix n'est qu'un théorème. Le tiers exclu en fait est un ensemble et pas forcément un élément (''singleton).
On a prouvé avant dans le post que tout élément de U est égal à f(1)
lemme1: soit $x,y$ des parties de $1$ tel que $x=1\iff y=1$. Alors $x=y$.
preuve : on va prouver que $\forall t: (t\in x\iff t\in y)$. Supposons $t\in x$. Alors $t=0$ (car $x\subset 1$) et $x=1$. Alors $y=1$, donc $0\in y$ donc $t\in y$.
$t\in y$ implique $t\in x$ se prouve pareil.
Soit $f$ une injection de $P(1)$ dans $P(1)$. Le but de la suite est de prouver $f\circ f =identite$
lemme2: pour tout $x$ inclus dans $1$, si $f(x)=1$ alors $x=f(1)$.
preuve: On suppose $f(x)=1$. On prouve $x=1\iff f(1)=1$ et ça suffit d'après le lemme1.
Supposons $x=1$. Alors $f(1)=1$
Réciproquement, supposons $f(1)=1$. Comme $f(x)=1$ et $f$ injective, donc $x=1$
lemme3: Soit $x$ inclus dans $1$ tel que $f(x)=1$. Alors $f(f(x))=x$
preuve: d'après le lemme2, $x=f(1)$. Donc $f(f(x)) = f(1) =x$
lemme final: on prouve que $f$ est involutive
preuve: comme $f$ injective, il suffit de prouver que pour tout $x$ inclus dans $1$, $f(f(f(x))) = f(x)$. Et pour ça, il suffit de prouver que $f(x)=1\iff f(f(f(x)))=1$.
Supposons $f(x)=1$. D'après le lemme3, $x=f(f(x))$ donc $f(f(f(x))) = f(x)=1$
Supposons $f(f(f(x))) =1$. Alors, d'après le lemme1, $f(f(x)) = f(1)$ et comme $f$ injective, donc $f(x)=1$
CQFD
Alors il existe n entier tel que (fog)(n) égal id. avec n dépendant du cardinal de E (ou G parce que on sait finalement qu'ils ont même cardinal)
On définit (si $i \leq k$) aussi l'image de $i \rightarrow k$ par le foncteur $\Omega$, $\Omega(i) \rightarrow \Omega(k): j \in \Omega(i) \mapsto \max (j,k) \in \Omega(k)$.
On définit $f:\Omega \rightarrow \Omega$ par $f i: \Omega(i) \rightarrow \Omega(i)$ qui à $j \in \Omega(i)$ associe $\max(j-1,i) \in \Omega(i) $. Alors $f$ est surjective mais non injective.
Pardon, et à dispo bien entendu, pour toute question.