temps "=" axiome du choix

Pour fêter ça, j'ai décidé de vous raconter une découverte récente (moins de 20ans) de Jean-Louis Krivine (un logicien renommé qui s'occupe de la correspondance de Curry Howard)

La correspondance de Curry Howard est une branche de la logique et de l'informatique fondée sur une idée-théroème: {\it tous les théorèmes de maths correspondent canoniquement à des programmes informatiques}.

Du coup, Jean-Louis et beaucoup d'autres sont partis à la chasse aux programmes qui correspondent aux preuves habituelles qu'on rencontre en maths. Actuellement, c'est un domaine où chacun a "sa" vision, mais en gros, JLK est à peu près le seul qui ait réellement attaqué les axiomes non logiques: c'est à dire tout ce qui est sans justification et pourtant "cru" par les "experts" quand ils décident ou non d'accepter une argumentation.

La cerise sur le gateau est {\it l'axiome du choix} (beaucoup discuté dans le passé).

L'axiome du choix est une conséquence de l'axiome (H) suivant: pour n'importe quel ensemble $E$ il existe une application $f$ de domaine $E\times \N$ telle que pour tout $y$ et tout $x\in E$ si $y\in x$ alors il existe un entier $p$ tel que $f(x,p)\in x$

L'axiome (H) correspond à un objet très primitif sur les processeurs: il correspond à {\bf l'horloge}

Dans un prochain post, je vous expliquerai pourquoi...
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi

Réponses

  • Je vais vous prouver "en douceur" (et dans un premier temps, sans même introduire le sujet) que (H) correspond à "l'horloge". Bien sûr ça aura un petit goût informel, mais je préciserai ensuite...

    Je rappelle juste (quand-même!) que les preuves sont {\it telles quelles} des programmes. Il reste à dire de quoi. Je pense que vous n'aurez pas beaucoup d'efforts à faire pour comprendre, qu'en tant qu'objets formels, elles sont des garanties de quelque chose, quelque chose qui peut se dire, chaque fois, de la manière suivante: face à une "hostilité" (j'appellerai ça, plagiant les spécialistes, un environnement) à ce que la preuve prouve, la preuve apporte une réponse "gagante" sans demander à son utilisateur (qui répond à l'hostilité) des qualités d'inspiration. Autrement dit, "la preuve fait tout le travail".
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Une "autorisation" bien connue en mathématique, qui appartient au groupe dont le nom officiel est {\it inférence} est celle qui consiste à faire l'enchainement suivant dans une preuve:

    ...A
    ...$A\to B$

    {\bf donc B}

    Cette inférence s'appelle un {\it modus ponens}

    La construction correspondante, en terme de programmes ou en termes "d'idées opératoires" est la suivante:

    Vous disposez par hypothèse d'une garantie $v$ de $A$, et d'une garantie $u$ de $A\to B$. But: fabriquer une garantie de $B$

    Le "robot" $r$ qui va garantir $B$ se comportera de la manière suivante: il passera la main au robot $u$, mais il aura pris soin avant de placer $v$ en "bouclier".

    En effet, ce faisant, soit $E$ un {\it environnement} hostile à $B$. Voyons si, dans cet environnement le robot $r$ s'en tire: il place en "bouclier" le robot $v$ (qui je le rappelle garantit $A$) puis passe la main à $u$.

    Au moment où le robot $u$ est sollicité, il se trouve face à un environnement $F$ qui "agresse" $A\to B$. {\bf Et notre hypothèse} était que $u$ s'en tire face à n'importe quel environnement qui agresse $A\to B$...

    La seule chose que j'ai vraiment supposé ici, et ce sera une définition: après avoir placé $v$ comme "bouclier" le robot $v$ a {\bf transformé} légèrement l'environnement dans lequel il se trouvait. Et précisément, il l'a fait passé de $E$ à $F$.

    $E$ agressait $B$ alors que $F$ n'agresse plus que $A\to B$.

    Un cosmonaute à poil dans le vide n'est pas du tout comme un cosmonaute à poil dans sa combinaison dans le vide. Ici c'était $v$ la combinaison et $u$ le cosmonaute.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • J'écris maintenant une phrase formellement pour exprimer H:

    $\forall x\forall y: [(\forall p\in \N: f(x,p)\notin x)\to y \notin x]$

    Comme vous pouvez le constater, il y a le signe "implique" (représenté par la petite flêche $\to$), dont je viens de vous parler au post précédent, mais il y a aussi le signe $\forall$ dont je vous parle maintenant en terme "d'actions" ou de "programmes informatiques"

    {\bf Par définition} je dirai qu'un environnement est hostile à $\forall t R(t)$ quand cette environnement {\bf tape sur la touche $t$}, puis, {\bf ensuite} agresse $R(t)$.

    Ainsi vous voyez les objets (ou plutôt les noms d'objets) jouer le rôle de "touches" de clavier.

    D'une manière abstraite, vous pouvez le concevoir comme un "couple" $(\alpha; E)$ avec $\alpha=$"je tape $t$" (imaginons que les environnements parlent) et $E$ un environnement hostile à $R(t)$.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Sans rien justifier pour l'instant, voici des définitions-hypothèses:

    1) Un environnement qui agresse $A\to B$ fournit une "promesse" de $A$ et nous supposerons qu'en fait, il fournit {\bf une garantie de $A$} (ce qui illustre une certaine imbrication entre les robots et les environnements.

    2) Un robot $r$ qui garantit $\forall w\in Clavier\ numerique$ blabla, a forcément une façon "robotique" (et même uniforme) de réagir à l'appui sur n'importe quelle touche $w$. Nous noterons le robot induit $r(w)$ (comportement du robot $r$ {\bf après} qu'on lui a envoyé le signal qu'on a tapé sur la touche $w$)




    Voilà l'argument Krivinien:

    je construis un robot $r$ "réaliste" et je vous raconte pourquoi il n'échoue dans aucun environnement qui agresse H.

    Un environnement $E$ qui agresse H va, avant toute chose, d'abord taper sur une certaine touche $x_0$ puis sur une touche $y_0$, puis ensuite, il va agresser:

    $(\forall p\in \N f(x_0,p)\notin x_0)\to y_0\notin x_0$.

    Il va donc fournir une promesse (et j'ai dit juste au début de ce post que cette promesse est une garantie de..), donc une garantie $u$ de:

    $\forall p\in \N f(x_0,p)\notin x_0$

    Et ensuite, il agresse $y_0\notin x_0$. (Au moment où il démarre cette agression, il est devenu l'environnement disons $G$). Un agresseur de $y_0\in x_0\to tout$ fournit forcément une garantie (sous forme d'un robot $v$) de $y_0\in x_0$ avant, ensuite d'agresser "tout".

    Le robot $r$ va {\bf se servir de l'horloge} pour fournir l'heure à $u$ (sous forme d'un entier dont il n'a jamais encore été question dans l'histoire de leur chamailleries (robots contre environnements). Autrement dit, il va passer la main à "$u(time)$" puis placer en bouclier le robot $v$. $time$ ne sera ici rien d'autre qu'un entier dont il n'a encore jamais été question (un tout nouvel entier).

    Par hypothèse, $u(time)$ sort vainqueur dans toute agression de $f(x_0,time)\in x_0\to tout$.

    Cela implique en particulier que $y_0\neq f(x_0,time)$, {\bf or, on voit mal comment, dans une "bagarre" entre un robot et un environnement, comment sans jamais préciser ce que veut dire $f$, bref, on voit mal comment le robot $u(time)$ pourrait garantir que $f(x_0;time)\notin x_0$, sans en fait avoir une méthode uniforme de comportement, qui finalement garantit AUSSI $y_0\notin x_0$}.

    Mais si cette partie non justifiée de mon argumentation est vrai, c'est à dire si, selon toute vraisemblance, $u(time)$ garantit $y_0\in x_0\to tout$, alors, comme $v$ garantit $y_0\in x_0$... Je vous laisse terminer!
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • bonjour

    je n'avais pas vu ce joli post dont je vous remercie grandement. Une question me vient, en pensant à la non-limitation du théorème de Curry-Howard à la logique intuitionniste(bien sur je pense à la correspondance entre le tiers-exclu et les instructions d'échappement par Griffin et Felleisen), je me demandais si il était possible d'étendre la correspondance entre axiome du choix dénombrable et cycle d'horloge pour le choix indénombrable voire se servir d'une sorte d' "inverse" de la correspondance de Curry-Howard sur un programme informatique particulier(je n'ai aucune idée de celui-ci mais bon, j'ose quand même un programme qui ferait exactement la même chose que celui que vous proposez mais à un temps "aléatoire" ferait un reset et recommencerais avec une autre fonction que f) dans le but de démontrer qu'un produit indénombrable d'ensembles non vides et non vide par exemple. Je pense avoir dit assez de bétises pour cette fois.

    Merci de vos futures réponses.
  • Attention, Chalons va nous démontrer qu'en tant qu'êtres soumis à la temporalité, nous sommes doués de libre arbitre ! C'est à un grand moment de philosophie que nous sommes conviés mesdames et messieurs ! ;)
    Trêve de plaisanterie, la question de hjkl sur "l'inverse" de la correspondance de Curry-Howard est intéressante : qui sait s'il n'existe pas déjà un programme correspondant à une preuve de RH ?
  • Pour Frege, les mathématiques sont intemporelles, hors du temps.
    Bon d'accord, on sait ce qu'il est advenu de sa construction.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Bonjour

    Comme je n'avais pas eu de réponses à mon étrange car j'avais répondu à votre post bien trop tard, j'ai décidé de le reposter. Donc voilà ma question, en pensant à la non-limitation du théorème de Curry-Howard à la logique intuitionniste(bien sur je pense à la correspondance entre le tiers-exclu et les instructions d'échappement par Griffin et Felleisen), je me demandais si il était possible d'étendre la correspondance entre axiome du choix dénombrable et cycle d'horloge pour le choix indénombrable voire se servir d'une sorte d' "inverse" de la correspondance de Curry-Howard sur un programme informatique particulier(je n'ai aucune idée de celui-ci mais bon, j'ose quand même un programme qui ferait exactement la même chose que celui que vous proposez mais à un temps "aléatoire" ferait un reset et recommencerais avec une autre fonction que f) dans le but de démontrer qu'un produit indénombrable d'ensembles non vides et non vide par exemple.

    Je pense avoir dit assez de bêtises pour cette fois.
    Merci de vos futures réponses.

    [Autant continuer sur la discussion initiale. :) AD]
Connectez-vous ou Inscrivez-vous pour répondre.