Discussion:Nombre définissable/Mail Delahaye

Une page de Wikipédia, l'encyclopédie libre.
Autres discussions [liste]
  • Suppression
  • Neutralité
  • Droit d'auteur
  • Article de qualité
  • Bon article
  • Lumière sur
  • À faire
  • Archives
Bonjour,
Je tente de répondre à vos questions entre vos lignes.

Bonjour Mr Delahaye.

Je suis un contributeur sur Wikipédia, et j'ai eu l'occasion de réaliser des articles sur des domaines vous concernant, comme par exemple sur les suites aléatoires (http://fr.wikipedia.org/wiki/Suite_aléatoire), largement fondé sur votre livre "Information, complexité et hasard".

Actuellement, l'article "Nombre définissable" sur Wikipédia (http://fr.wikipedia.org/wiki/Nombre_définissable) fait l'objet de nombreux débats en page de discussion (http://fr.wikipedia.org/wiki/Discuter:Nombre_définissable). Le problème est le suivant : il ne semble pas exister ni de définition explicite, ni source détaillée sur ce concept, pourtant important et utilisé par de nombreux auteurs y compris vous-même. Je n'ai pas réussi à trouver de définition précise (formelle ou non) de ce concept dans vos livres (ou dans d'autres !), bien que vous l'utilisiez fréquemment. Le plus précis que j'aie trouvé dans vos livres est p.95 de ""Information, complexité et hasard" sur "nombre définissable dans ZF", qui est malheureusement une définition récursive ( = "Nombre dont on peut donner une définition dans la théorie des ensembles de ZF").

Une définition de nombre définissable est forcément relative à un système formel, d'où la référence par exemple à ZF. Une fois le système formel fixé la définition est assez simple et n'est pas récursive :
- un nombre x réel est définissable s'il existe une formule (de ZF) P(x) dont on puisse démontrer (dans ZF) qu'il existe un seul x tel de P(x) (P(x) est la définition de x). Il faut aussi bien sûr qu'on puisse démontrer P(x) => (x appartient à R).
Comme les formules de ZF sont en quantité dénombrable (le vocabulaire de base est fini, une formule est une suite finie d'éléments de ce vocabulaire), il n'y a forcément qu'une quantité dénombrable de nombres définissables dans ZF (ou dans S, S fixé)

Le débat porte sur deux points principaux :

1) Les nombres définissables sont-il en nombre infini dénombrable ou non-dénombrable, et même le concept d'ensemble des nombres définissables a-t-il un sens ?

La réponse est au-dessus.

Bien que vous, et bien d'autres sources (Chaitin notamment), stipuliez que les nombres définissables sont dénombrables, certains intervenants du débat font valoir que si on admet qu'ils sont dénombrables, alors il est possible d'utiliser l'agument diagonal (le nombre exhibé par diagonalisation étant, dans un certain sens, rigoureusement et univoquement "défini" ainsi) pour démontrer qu'ils ne le sont pas. Bien évidemment, tout dépend de la définition de "définissable" employée et nous retrouvons ici un besoin pressant de définition précise.

L'argument diagonal définit effectivement un nombre réel, mais ne sera pas définissable dans ZF. Il n'y a aucun paradoxe.
L'existence de nombres définissables "de l'extérieur" mais pas de l'intérieur est une forme d'incomplétude.

Dans le même sens, Turing, dans son article fondateur "On computable numbers", parle de "definable numbers" et les nombres non-calculables qu'il exhibe par diagonalisation sont qualifiés par lui de "definables". Il est frappant de voir qu'aucun auteur ne semble traiter de cet argument diagonal sur le problème de la définition des nombres réels.

Ce n'est pas exact. Les logiciens ont parfaitement conscience de l'argument diagonal et en tiennent compte.
Dans l'article de Turing (je travaille de mémoire) il diagonalise sur les nombres calculables, ce qui est une opération qu'on peut faire dans ZF et qui définit donc un nombre définissable de ZF, qui bien sûr n'est pas calculable (c'est ce que voulait Turing). Là encore pas de paradoxe du tout.

2) Chaque auteur semble utiliser des termes voisins pour qualifier ce concept, sans qu'il soit bien clair s'il s'agit bien du même concept ou non (toujours le même problème de définition).

Il se peut qu'il y ait une utilisation imprécise du terme. De toutes les façons le concept de définissable n'est pas absolu (comme le concept de "démontrable"), si on fait attention à ce qu'on dit on doit toujours préciser "definissable dans ZF" ou "définissable dans Peano", etc. Le fait que ZF permette de faire presque toutes les mathématiques, conduit certains à croire que ce qui n'est pas définissable dans ZF ne l'est pas du tout, mais c'est évidement faux à cause du raisonnement diagonal (que l'on n'oublie jamais !).
Un langage rigoureux consisterait à ne jamais utiliser le mot "définissable" sans précision.

Chaitin parle de "nombres nommables" (dans son dernier livre "Hasard et complexité en mathématiques"), et sans en donner de définition ! Borel de "nombre accessibles", vous-même et d'autres de "nombre définissable". Quels sont les rapports entre ces différentes définitions ?

Pour Borel, il ne s'agit certainement pas des nombres définissables dont je parlais au-dessus car la logique mathématique n'était pas assez développée quand il écrivait. Je ne sais pas trop à quoi vous faites allusion dans son cas.
La phrase tirée de wikipedia :
Selon Émile Borel, un nombre réel définissable est un réel qui peut être décrit comme un objet mathématique, de sorte que ceux qui en parlent soient assurés qu'ils parlent d'un même et unique nombre.
se réfère à une définition informelle et qui (via diagonalisation) conduit à des difficultés. S'il s'agit de nombres précis, Pi, e, oméga, elle ne pose pas de problèmes. Les problèmes viennent quand on veut parler de nombres non définissables, ou quand on veut parler de l'ensemble des nombres définissables. Il faut alors faire attention et bien préciser "dan ZF" ou autre choses.
Pour Chaitin, je pense qu'il parle des nombres définissables (en sous-entendant "dans ZF").
Quand j'emploie cette expression il s'agit de nombres définissables de ZF, ou alors comme dans le cas de Borel, c'est que je parle d'un nombre précis dont la définition est bien précise.
L'usage est un peu comparable à celui de "démontrable". Comme il n'y a pas de définition ultime de la notion de démonstration, il faudrait toujours parler de démonstrable dans S (en précisant S). Cependant quand on parle d'une démonstration classique (dont la formalisation dans Peano ou ZF est possible) on ne prend pas la peine de préciser. C'est seulement quand on veut parler de propositions non démontrables qu'il devient indipensable de préciser.
Le cas du nombre oméga de Chaitin est un bon exemple. Si on en comprend bien la nature, il est parfaitement bien défini (et il est inutile de préciser dans Peano ou dans ZF, car dans les deux systèmes sa définition est exprimable et donne la même chose).

Connaissez vous une source qui fasse le point sur ces problèmes de manière claire et précise ? Ou peut-être dans un de vos livres que je ne connais pas ? Ou dans un article de Pour la Science ? (ou sinon, cela peut être une bonne idée pour une future chronique de "Pour la Science" !)

Evidemment, l'idéal serait que vous participiez vous-même à cet article, mais je n'ose l'espérer. Je sais que vous avez un compte Wikipédia, j'ai eu l'occasion de discuter avec vous quand vous étiez (à juste titre) intervenu sur votre propre article pour le clarifier.

Il se peut que j'en parle un jour dans PLS, mais ce n'est pas prévu pour l'instant.
Vous devriez regarder
http://en.wikipedia.org/wiki/Definable_number
http://en.wikipedia.org/wiki/Definable_set
http://en.wikipedia.org/wiki/Tarski's_indefinability_theorem
http://knowledgerush.com/kr/encyclopedia/Definable_number/
La théorie de la definability (et non pas definissability) en logique est extremement riche.
Un exemple : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.4440:
Voir aussi :
http://www.amazon.com/s/ref=nb_ss_gw?url=search-alias%3Daps&field-keywords=definability+logic&x=0&y=0
Bien cordialement,
Jean-Paul Delahaye