Indécidabilité et négligeabilité

Pablo_de_retour
Pablo_de_retour
dans Fondements et Logique
Bonsoir à tous

Si nous regardons les mathématiques dans leur ensemble, comme étant une seule théorie unifiée, comment peut-on formaliser de manière rigoureuse la notion d'indécidabilité, et établir que l'ensemble des résultats indécidables en mathématiques est négligeable, ou non ? Est-ce que c'est démontrable ?

Merci d'avance.

Réponses

  • Poirot
    Poirot
    Tu te fais une bien fausse idée de l'unification des maths. :-D

    Tu peux regarder la proportion des formules de longueur au plus $N$, disons en théorie des ensembles, qui sont indécidables dans $\mathsf{ZFC}$ et regarder la limite quand $N$ tend vers l'infini. Il me semble qu'il est connu que cette limite vaut $1$.
  • Pablo_de_retour
    Pablo_de_retour
    Poirot a écrit:
    Tu peux regarder la proportion des formules de longueur au plus $N$, disons en théorie des ensembles, qui sont indécidables dans $\mathsf{ZFC}$

    Comment calculer cette proportion Poirot ?

    Edit,
    Je précise que je suis un ignare en théorie de complexité en Logique, c'est juste par curiosité que je cherche à connaitre la réponse.
  • Martial
    Martial
    @Poirot : aurais-tu par hasard une référence expliquant, même heuristiquement, pourquoi la limite vaut $1$ ?
    Ça m'intéresserait, même si j'en suis totalement convaincu.

    Mon explication perso, ras des pâquerettes : plus le problème est long à raconter, et plus il est difficile à résoudre, pour nous certes, mais aussi et surtout pour ZFC.
    Bon, ça passerait mieux au Café du Commerce, mais comme il est méfer en ce moment je vais m'en contenter, lol.
  • Poirot
    Poirot
    @Martial : je n'ai pas de référence précise. Je pense avoir déjà vu Christophe l'affirmer, et j'ai lu quelque chose de proche dans un article de Delahaye sur des travaux récents de chercheurs (je crois) français.
  • Poirot
    Poirot
    J'ai retrouvé le papier de Delahaye : http://cristal.univ-lille.fr/~jdelahay/pls/249.pdf
  • Pablo_de_retour
    Pablo_de_retour
    Et moi, Poirot, tu ne réponds pas à ma question ? :-(

    Edit,
    Croisement avec le message de Poirot.
  • Poirot
    Poirot
    Je n'ai pas la réponse à cette question.
  • Pablo_de_retour
    Pablo_de_retour
    Alors, on attend CC pour voir si lui, il a la réponse ou non, et où je peux trouver d'informations ou de cours sur ça !?. :-)
  • Martial
    Martial
    @Poirot : merci pour le lien.

    "Je n'ai pas la réponse à cette question. "
    Mais en quelque sorte, le lien que tu me donnes répond (de façon empirique certes) à la question de Pablo.

    Bonne soirée à tous
  • christophe c
    christophe c
    Je n'ai pas de référence. Mais je confirme le résultat, vrai d'ailleurs pour toute théorie récursivement enumerable. On peut même dire encore plus: l'ensemble des énoncés décidables est "presque fini" en un certain sens. C'est d'ailleurs une traduction de la fameuse phrase de Kant que nous ne connaissons a priori des choses que ce que nous y mettons nous mêmes. Quand une théorie est structurellement souple pour faire toutes les maths, elle "voit mieux" le "nombre fini" de familles d'axiomes" qu'elle a adoptées.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 15

DeGeerDomJFSJLTchanig +10 Invités