Un scoop que je partage — Les-mathematiques.net The most powerful custom community solution in the world

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]


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

Réponses

  • Dans les topos, en écrivant les définitions, j'ai l'impression que c'est une trivialité :-(
  • zephir a écrit:
    Dans les topos, en écrivant les définitions, j'ai l'impression que c'est une trivialité sad smiley
    Comment l'aurais-tu fait? (des fois qu'un truc simple m'ait échappé mais j'ai quand même passé du temps dessus).
  • @Zephir: c'est peu probable. Normalement, si "X" est la difficulté de prouver un truc intuitionnistiquement alors "2^X" est la difficulté de le prouver avec des flèches dans tous les sens. Or intuitionnistiquement, c'est pas très dur, mais c'est pas une évidence.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Il y a une différence notoire entre "j'ai l'impression que ...", "je pense que ...", "j'ai la conviction que ..." et "j'ai démontré que ...". Comme Christophe l'a dit dans l'un de ses messages, un théorème est une liste de trivialité.
    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.
  • Merci pour ce charmant résultat, et pour le partage de ces choses nouvelles pour moi en tout cas, c'est la première fois que je lis une démonstration intuitionniste (du moins en m'en rendant compte que s'en est une)^^!
  • Est-ce un scoop ?C'est en fait juste la traduction en langage interne de la démonstration catégorique du livre de Johnstone. Si ta réflexion t'a permis de comprendre ainsi cette démonstration, parfait.
  • Non ce que j'appelle "scoop", c'est le théorème, évidemment, pas la façon dont la démonstration a été trouvée (probablement il y a longtemps d'ailleurs, car une preuve comme ça ne se trouve pas d'abord catégoriquement je pense)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • J'ai encore raccourci un peu la démo. Je vais faire un doc d'accompagnement où je vais renseigner sur la logique intuitionniste et sur les références connues de ce résultat** (j'ai envoyé un mail avec lien vers ce fil à tous les chercheurs de Paris6,7,cnrs, d'où cette politesse). Mais il me faudra un peu de temps, j'ai cours aujourd'hui

    ** dans le premier post
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • car une preuve comme ça ne se trouve pas d'abord catégoriquement je pense

    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.
  • J'avoue que je ne sais pas. Certes la preuve catégorique ne prend qu'une page, mais j'aurais eu tendance à soupçonner que personne ne se serait donné la peine de chercher longtemps une preuve après s'être posé la question, se disant, "bon bin, c'est vrai classiquement dans les ensembles, mais on fait clairement un raisonnement par tiers exclus pour l'avoir, donc pas la peine de chercher plus loin". Mais quitte à chercher plus loin, il parait naturel de chercher à le prouver constructivement (ce qui ne demande que des bases très élémentaires) plutôt que chercher à l'obtenir à coup de flèches dans des catégories. Je soupçonne (mais j'en sais rien), que le premier qui l'a trouvé avait une preuve constructive très simple (comme celle en haut du fil) et l'a traduit ensuite en catégories.

    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)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • La version catégorique de ce théorème

    mise aussi dans le premier post.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Mais quitte à chercher plus loin, il parait naturel de chercher à le prouver constructivement (ce qui ne demande que des bases très élémentaires) plutôt que chercher à l'obtenir à coup de flèches dans des catégories. Je soupçonne (mais j'en sais rien), que le premier qui l'a trouvé avait une preuve constructive très simple (comme celle en haut du fil) et l'a traduit ensuite en catégories.

    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 ...
  • Mais tu sembles en déduire, comme une évidence, que c'est le cas pour tout le monde. Tu te trompes.

    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)
    Maintenant, je ne peux pas t'empêcher de te raconter l'histoire d'une manière qui te plait mieux ...

    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").
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GBMZ a écrit:
    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

    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
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Bonjour.
    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).
  • Je vois pas qu'est qui permet de dire: Donc f(f((x))=f(1)

    On a prouvé avant dans le post que tout élément de U est égal à f(1)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Je vous répercute le mail qu'Alain Prouté a envoyé, en réponse à mon mail, à la liste de diffusion new@pariscnrsblabla
    [size=large]Le théorème dont il est question est de Higgs. Il est cité dans le livre de Lambek et Scott ``Introduction to higher order categorical logic''. Il dit précisément la chose suivante:

    Dans tout topos T, tout monomorphisme du classifiant du foncteur des sous-objets vers lui-même est une involution.

    Comme l'a remarqué Bruno, le théorème est trivial dans le topos des ensembles, mais il est moins trivial dans un topos quelconque (où il est valide car ``purement intuitionniste'').

    La démonstration n'est pas très compliquée, mais elle utilise le langage interne et (si je me souviens bien) la sémantique de Kripke-Joyal. J'ai donné cet énoncé en exercice en examen de M2 il y a quelques années (voir sur ma page le recueil de problèmes sur les topos).

    Le théorème reste trivial dans tout topos de préfaisceaux dont le classifiant du foncteur des sous-objets est ``fini au dessus de chaque objet de la catégorie de départ''. Par contre, si on prend par exemple le topos des systèmes dynamiques discrets, le classifiant du foncteur des sous-objets a une infinité d'éléments (de l'unique sorte dans le cas de ce topos). C'est la structure de la dynamique de ce système (dynamique) qui est telle que tout monomorphisme vers lui-même est une involution. C'est d'ailleurs assez facile à voir dans ce cas. Toutefois, il doit exister des exemples plus difficiles.

    Ce théorème a une conséquence amusante, qui est que dans tout topos, le classifiant du foncteur des sous-objets est ``Dedekind-fini'' même s'il est notoirement infini du point de vue ensembliste (quand cela a un sens).[/size]
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Pour les rares personnes qui ont eu la flemme de lire la preuve du premier post, j'en rédige une (la même, mais je change la rédaction), qui se lit paresseusement et sans peiner (j'évite l'usage d'un ensemble intermédiaire). Rappel: $0=\emptyset$ et $1=\{0\}$

    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
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • En tout cas avec les méthodes classiques on peut montrer que si E et F sont finis et qu'il existe une injection f: E vers F et une injection g:F vers E
    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)
  • Petit exercice : exhiber un topos $E$ dont l'objet classifiant les sous-objets $\Omega$ est tel qu'il existe une flèche épi ("surjective") $f:\Omega\to \Omega$ qui n'est pas mono ("injective").
  • @GaBuZoMeu: Je réponds à l'exercice. On considère la catégorie $C= \N$. Il y a un morphisme (qui de plus est unique) entre $i\in \N$ et $j \in \N$ si et seulement si $i \leq j$. On considère le topos $\bf{Ens}^C$. Le classifiant $\Omega$ est défini comme suit: $\Omega (i)=\{ j \in \N | j \geq i\}$.
    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.
  • Oui, bravo, c'est l'exemple que j'avais aussi en tête. ;-)
  • Je fais juste remonter le fil car d'une part j'ai cherché longtemps sans retrouver la preuve e td'autre part, j'ai cherché longtemps le fil.

    Pardon, et à dispo bien entendu, pour toute question.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!