Discuter:Nombre définissable

Un article de Wikipédia, l'encyclopédie libre.

	Nombre définissable fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
À évaluer	Cet article a été classé comme d'Avancement ? selon le Tableau d'évaluation du projet. (Voir les statistiques)
À évaluer	Cet article a été classé comme d'Importance ? selon le Tableau d'évaluation du projet.

c'est quoi le omega? (T(omega))

Guigolum 5 juin 2007 à 11:16 (CEST)

Oméga de Chaitin Ekto - Plastor 5 juin 2007 à 13:05 (CEST)

[modifier] Doutes

On flirte dangereusement avec le paradoxe de Richard dans cet article. Déjà avec le titre : si on est capable de définir l'ensemble des nombres définissables, c'est forcément définissable dans un langage donné (celui de la théorie des ensembles, c'est + ou - dans l'article) relativement à un modèle donné : disons celui de la théorie des ensembles où "vit" les réels de l'article. Donc cette notion est tout à fait relative au langage. On a bien défini le réel du pardoxe de Richard par exemple, et il ne peut être définissable en ce sens. Quelles sont les sources ? Proz (d) 7 février 2008 à 20:11 (CET)

Je précise : a priori l'article suppose que l'on sait parfaitement ce que sont les réels, et que parmi ceux-ci on distingue ceux qui sont définissables en théorie des ensembles (on a une propriété qui les caractérise). Mais on définit alors par diagonalisation un réel qui n'est pas définissable dans la théorie des ensembles, cf. paradoxe de Richard, donc l'assertion "Il inclut tout réel qu'on est capable d'exprimer" est forcément fausse. Une façon de faire serait de dire que c'est une notion informelle, d'après en:definable number, Turing l'utilise dans son article (parce qu'il y a plus simple que la constante de Chaitin pour trouver des nombres non calculables, le problème de l'arrêt suffit !). Il faudrait aussi laisser tomber les histoires de corps, (il faudrait déjà que ce soit un ensemble). Ce serait bien quand même d'avoir une référence fiable (Delahaye d'après le schéma?, Borel d'après l'article cité ?) et de savoir ce qu'ils disent. Proz (d) 21 avril 2008 à 19:53 (CEST)

OK, voilà comment on s'en sort avec Richard. Si tu dis "x est un nombre non définissable compris entre 0 et 1", il n'y a aucun moyen de s'entendre pour savoir duquel on parle. Quand à la définition par diagonalisation d'un réel non définissable, elle nécessite d'avoir une définition explicite et de longueur finie d'une bijection entre N et l'ensemble des réels définissables. _{BOCTAOE. Ou pas.} Barraki Retiens ton souffle! 21 avril 2008 à 23:02 (CEST)

Je suis d'accord qu'il faut sortir de la théorie étudiée pour définir la bijection entre N et l'ensemble des réels définissables, mais c'est déjà le cas pour la notion même, et une fois une bijection avec N donnée (c'est quand même ça que veut dire dénombrable) le procédé diagonal définit un réel sans ambiguïté, la définition est bien explicite et finie. Il faut distinguer deux niveaux (la théorie que l'on étudie, la metathéorie où on l'étudie), et c'est quand on mélange les deux, ce qui me semble le cas, que l'on tombe sur des paradoxes. Je crois que le paradoxe de Richard montre qu'il ne peut y avoir de notion "absolue" de nombre définissable. c'est toujours dans un langage et relativement à un modèle (et la définition de l'article ne me parait pas claire du tout). Est-ce que tu as d'autres sources que l'article anglais ? Proz (d) 21 avril 2008 à 23:58 (CEST)

J'ignore effectivement quelles sont les sources de l'article anglais, je me suis contenté de reprendre les points les plus importants. J'ai des exemples d'utilisation de la notion, mais effectivement pas de source définissant. Hum, une question un peu personnelle : j'ai trouvé sur un forum un message d'un prof de maths de l'ENS qui semble connaître des détails importants sur la notion. Son e-mail est public, mais il ne m'a pas répondu. Est-ce que tu as un statut tel que tu as de bonnes chances qu'il te réponde à toi ? _{BOCTAOE. Ou pas.} Barraki Retiens ton souffle! 22 avril 2008 à 18:42 (CEST)

Tu peux demander à Pierre de Lyon il est de l'ENS, féru d'informatique et il ne refusera pas de te répondre. La distinction entre théorie et métathéorie, la représentation d'une théorie dans une autre, c' est dans tous les bouquins de logique un peu approfondis. Ce qui est bizarre c'est que dans cet article la formule définissante est supposée être construite à partir de la théorie des ensembles. On aurait pu penser que c'était à partir d'une axiomatisation différente des +,x,< etc.. --Michel421 (d) 22 avril 2008 à 20:38 (CEST)

En attendant voici le message de celui qui refuse de me répondre (vous trouvez son e-mail dans le post) : http://www.math.niu.edu/~rusin/known-math/98/definable

J'y tire la définition que j'ai utilisé, et il introduit un autre concept, celui de construtibilité au sens de l'univers de Gödel. _{BOCTAOE. Ou pas.} Barraki Retiens ton souffle! 22 avril 2008 à 21:20 (CEST)

Intéressant - il dit que ce qui est définissable serait ce qui est constructible. Si c'est ça que l'article veut dire ça éclaircit déjà. Mais dans ce cas il devrait parler de l'hypothèse du continu ce qu'il ne fait pas.

La constructibilité au sens de Gödel, je la possède sous deux formes : Gödel The consistency of the continuum hypothesis et Krivine un chapitre de Théorie axiomatique des ensembles Gödel travaille en NBG et Krivine en ZFC mais c'est pareil à la terminologie près.--Michel421 (d) 22 avril 2008 à 22:03 (CEST)

Oops......Bzzt wrong. L'article dit que l'ensemble des nombres définissables est dénombrable. Cela ne peut donc pas coller avec ce que dit Madore, que l'on aie L=V ou non.--Michel421 (d) 22 avril 2008 à 22:22 (CEST)

Il dit « Obviously only countably many real numbers are definable ». Il ne contredit pas l'article. Il dit que c'est un concept lié. _{BOCTAOE. Ou pas.} Barraki Retiens ton souffle! 22 avril 2008 à 22:38 (CEST)

J'avais pensé aussi demander son avis à Pierre. Pour ton message : il s'agit d'un ancien élève de l'ens, qui y a été je crois préparateur, mais qui a dû la quitter (et on trouve sur le web des papiers mathématiques assez généralistes de lui très intéressants). Son post ne dit rien d'aussi précis qu'ici. Les définissables en termes d'ordinaux et les constructibles, se sont des notions bien connues de théorie des ensembles dues à Gödel, mais déjà assez avancées. Elles sont traitées dans Jean-Louis Krivine, théorie des ensembles [détail des éditions] (il faut connaître un minimum de logique pour comprendre amha). Cela sert pour les preuves d'indépendance, comme il l'explique. Je ne vois pas trop comment y relier ce qui est dit ici. La notion d'élément définissable d'un modèle dans un langage donné, ou peut-être plutôt de sous-ensemble définissable (des réels, et des sous-ensembles des entiers ce n'est pas très loin) est fondamentale en logique (versant th. des ensembles, th. des modèles), mais c'est relatif à un modèle et à un langage (et il n'y a pas moyen d'"internaliser" cette notion, de tout traiter au même niveau théorème de Tarski).

Le fait que la seule source soit en: confirme mon impression reste que c'est employé informellement (comme le fait Turing), ou alors, en un sens précis, et pour un langage plus restreint que celui de la th. des ensembles (par ex. le problème de l'arrêt, et donc le réel non calculable qui va avec, est définissable au premier ordre dans le langage de l'arithmétique, et par une formule logiquement "assez simple"). Je peux me renseigner auprès de théoriciens des ensembles (mais pas ces jours-ci) pour en savoir plus (mais celui qui a repris l'article sur en:, qui est rédigé plus soigneusement, a l'air d'avoir de gros doutes, et il semble être un théoricien des ensembles sérieux).

Le dessin (qui n'est pas sur en:) fait référence à un livre de Delahaye : c'est vraiment ce dessin ? Quelqu'un l'a lu ? Proz (d) 22 avril 2008 à 22:36 (CEST)

Le dessin est de Utilisateur:Grumpfou. Je peux aussi essayer de contacter Delahaye, j'ai correspondu avec lui à une époque.

En fait, l'article d'Élise Janvresse et Thierry de la Rue done une définition pas très loin de la mienne, sauf pour un point : j'avais supposé que par langage usuel des maths, on entendait ZFC, alors que le passage d'un langage à l'autre semble très important, si je te comprend bien. _{BOCTAOE. Ou pas.} Barraki Retiens ton souffle! 22 avril 2008 à 23:07 (CEST)

Ce dessin a été placé sur Commons par Grumpfou ; il est sous licence GNU ce qui signifie que l'auteur renonce explicitement à ses droits et qu'il y a une trace écrite. Donc normalement le dessin n'est pas de Delahaye.--Michel421 (d) 22 avril 2008 à 23:17 (CEST)

J'ai fait une recherche dans l'article Janvresse - De la Rue, ils ne parlent pas de "corps" des nombres définissables. Incidemment, cela m'a fait me poser quelques questions à 100 balles, comme par exemple : si c'est un sous-corps dénombrable de R, comme R est le corps minimal contenant Q tel que toute partie majorée admette une borne supérieure, il s'ensuit qu'il existe des ensembles de réels définissables dont la borne supérieure dans R n'est pas définissable.--Michel421 (d) 22 avril 2008 à 23:37 (CEST)

euh ... peut-être faut-il lire ce que dit Delahaye (s'il en dit bien quelque chose) avant de l'interroger. En résumé : c'est apparemment une notion que les gens utilisent de façon plutôt informelle (c'est comme ça que je comprends le langage usuel des maths). On peut donner une définition formelle pour un langage donné relativement à un modèle de la théorie des ensembles (ou d'une théorie qui permet de définir les réels), mais alors on ne dit pas nombre définissable tout court, mais par ex. dans le langage de l'arithmétique du 1er ou du 2nd ordre. Quand on commence à parler du langage de la théorie des ensembles, il faut être particulièrement clair sur ce qu'on veut dire pour ne pas tomber dans les paradoxes. Ce qu'il y a à vérifier, c'est si la notion informelle est "sourçable" (autrement qu'en la constatant), et si quelqu'un a étudié une notion plus ou moins générale de "réel définissable". Je propose qu'en attendant d'en savoir plus, on laisse le bandeau, ce qui n'empêche pas de corriger (et pour la question à 100 balles la réponse est, dans le cas de "complet", dans l'article en: ). Proz (d) 23 avril 2008 à 01:20 (CEST)

Euh, pour le corps : une phrase de l'article d':en : « Assuming they form a set, the definable numbers form a field ». Ce n'est pas sourcé mais ça me semble évident : si a et b sont définissable, "a+b", "a-b", "a*b" et "a/b" si b<>0 sont des définitions simples. _{BOCTAOE. Ou pas.} Barraki Retiens ton souffle! 23 avril 2008 à 11:45 (CEST)

Comme aussi est simple la définition "le premier nombre entier non définissable en moins de vingt mots", laquelle définition fait 11 mots. OK pour +,-,x,:,<, log et quelques autres, et là on a les nombres calculables - ce que Turing appelle aussi V-définissables si j'ai bien compris son papier. --Michel421 (d) 23 avril 2008 à 12:31 (CEST)

Hmm non, autant pour moi, ce sont les suites qui sont V-definissables ; bref il faut savoir ce qui est admis dans cette formule φ(t) à une variable libre. Si on se limite à +,-,x,/,<, log, π, e, la constante d'Euler etc.. on a les nombres calculables. Ce sont ni + ni - que les nombres qui sont définissables à partir de ces opérations et constantes. Quant à savoir ce que sont les nombres "définissables" tout court ça semble être de la métaphysique. Il semble que ce soit antérieur à Turing, peut-être Poincaré, Richard...... au moment de leur controverse des fondements, et ça a été repris sans trop de réflexion.--Michel421 (d) 23 avril 2008 à 12:49 (CEST)

Dans son papier "On computable numbers, with an application to the entscheidungsproblem" 1936 Turing dit ceci:

It must be remembered that we have attached rather a special meaning to the phrase “U defines I”. The computable numbers do not include all (in the ordinary sense) definable numbers. Let P be a sequence whose n-th figure is 1 or 0 according as n is or is not satisfactory. It is an immediate consequence of the theorem of §8 that P is not computable. It is (so far as we know at present) possible that any assigned number of figures of P can be calculated, but not by a uniform process. When sufficiently many figures of P have been calculated, an essentially new method is necessary in order to obtain more figures.

Il donne donc un exemple d'une suite "définissable au sens ordinaire" mais ne donne pas une définition générale.--Michel421 (d) 23 avril 2008 à 15:51 (CEST)

Je n'arrive pas à trouver de source. Une chose est sûre : la définition telle qu'elle est dans l'article comporte la mention "un réel a pour lequel il existe une formule φ". Or en premier ordre les φ ne peuvent entrer dans le champ d'un quantificateur. Or les procédés de construction des ensembles sont des formules du premier ordre fournies par les axiomes de ZFC. N'étant pas du premier ordre cette définition ne peut aboutir à définir un objet de ZFC.--Michel421 (d) 24 avril 2008 à 19:44 (CEST)

Pas de souci pour la stabilité par opérations usuelles pour des notions "raisonnables" de nombre définissable. L'article sur en: est correct (on peut discuter la définition avec l'univers de von Neumann) , pourtant ils s'interrogent sur l'intérêt de la notion elle-même (travail inédit etc., tout ce qui est correct n'est pas à écrire).

Je contribue assez peu ces jours-ci (pas d'accès commode), mais avant de partir sur une notion de théorie des modèles d'élément définissable (avec paramètres ce qui est habituel, mais n'était pas ce que visait l'article, de plus ni le langage ni les paramètres ne sont supposés dénombrables), dès la première ligne (qui va comprendre ?), je m'interroge. D'ailleurs ce ne sont pas plus des nombres qu'autre chose. On pourrait tout aussi bien développer l'aspect informel (en trouvant un peu plus de ref. que seulement Turing). Proz (d) 26 avril 2008 à 00:34 (CEST)

S'il y a stabilité pour les opérations usuelles c'est qu'il y a bien un corps des nombres définissables. Il y avait des problèmes et tout d'un coup il n'y en a plus? Du côté anglais Trovatore n'a pas renoncé à son argument de la diagonalisation. Quant à l'intérêt de la notion, il existe, ça a l'air notoire et ça a une valeur encyclopédique ne serait-ce que parce qu'elle a joué un rôle dans la crise des fondements. La définition de la définissabilité par rapport à la théorie des modèles c'est la seule à peu près explicite que j'aie pu trouver, évidemment que tel que c'est c'est peu pédagogique et je pensais étoffer et mettre en forme tout ça mais si tu me dis que c'est pas ça alors il n'y a d'autre choix que de revenir à la forme précédente, mais avec un bandeau "à sourcer" au lieu d'un bandeau de pertinence. Qu'en disent Barraki et Epsilon ? --Michel421 (d) 26 avril 2008 à 09:53 (CEST)

Non, en fait c'est pas notoire, "nombre réel définissable" ça fait 3 occurrences Google. Mais j'ai authentifié que la définition est correcte (mais mal tournée au début). S'appliquant aux réels elle fait bizarre mais en fait c'est un cas d'une formule générale que j'avais depuis longtemps dans mes bouquins ; quant au théorème de Carnap il est numéroté 60 d.1....mais dans quel ouvrage? Manque de bol, sur l'aperçu de Google books la page qui donnait la référence n'était pas consultable en ligne là je me suis donc contenté de la référence Verley. Reste à trouver l'origine de l'affirmation que les nombres définissables forment un corps - --Michel421 (d) 27 avril 2008 à 18:53 (CEST)

Pour parler de corps le problème éventuel est que le support soit un ensemble (voir le théorème de Tarski). La définition n'est toujours pas claire et n'a rien d'authentifiée : soit on parle de "vérité" soit de démontrabilité (dans l'article sur en:, c'est clairement de vérité, là on basculerait vers la démontrabilité, pourquoi ?). Il me semble que l'introduction de constante, c'est pour parler d'extension d'une théorie par définition. Le problème reste entier : une définition précise de réel définissable conduit à ce que l'on peut forcément définir par diagonalisation un réel non définissable (le contraire, entre autres est toujours dit dans l'article), et il n'y a aucune source pour une telle définition précise de "réel définissable". Par ailleurs quelle est justement la définition de Carnap ? En quelle année d'ailleurs, avant la définition de la sémantique de Tarski ? Est-ce qu'il y a vraiment un "théorème de Carnap" (au sens usuel en math) ? Proz (d) 28 avril 2008 à 23:54 (CEST)

[modifier] Définition du définissable

Suite à la discussion précédente j'ai reverté la totalité de l'article sauf le lien Janvresse - De la Rue qui avait le mérite de donner une référence et on repart sur de nouvelles bases.

J'ai commandé le bouquin de Borel. Introuvable sur Hachette, Dunod, Amazon, etc.. Il m'a fallu aller chercher une librairie d'antiquaire à Lyon et payer €100 + €5 de port. Il n'y a que moi pour balancer 105 euros dans une définition qui a le mérite de n'être pas précise, sous prétexte que les définitions précises ne marchent pas .--Michel421 (d) 10 mai 2008 à 19:31 (CEST)

[modifier] Hypothèse de thm expliquant les difficultés ici rencontrées

Bonjour, je n'ai pour ma part aucune source, mais ne serait-on pas là en train de tourner autour d'un (méta) thm (qui a p.e. été démontré) du genre :

L'ensemble des réels définissables dans ZF, n'est pas définissable dans ZF ?

• Ce qui 1. nous rapprocherait du thm de Tarski et 2. nous éviterait de tomber dans le paradoxe de Richard.

• Avec pour la notion de "c est un réel définisable dans ZF" qqch comme :
  • " c est un réel, et
  • Il existe une formule F (à une unique variable libre) n'ayant comme symboles non logiques que = et l'appartenance telle que : ZF|- all x (F(x) <--> x=c) "

Rem : si un tel ensemble existait, il serait dénombrable. J'ai une question : est-ce que toute sous classe d'un ensemble (ici R) est forcément un ensemble (il ne me semble pas clair du tout que par ex le thm de remplacement le prouve) ??

Maintenant a t-on des sources sur un éventuel tel thm?

--Epsilon0 ε₀ 10 mai 2008 à 22:40 (CEST)

Bonjour. Ton definiens n'est pas du premier ordre il ne peut donc pas servir dans le schéma de séparation ou le schéma de remplacement pour déterminer un ensemble.

En ce qui concerne la 2ème question, toute sous-classe d'un ensemble est un ensemble. Mais là il ne s'agit pas d'une sous-classe au sens formel, il s'agit d'une partie (au sens intuitif) de l'univers, qui ne correspond à aucun ensemble [comme j'ai compris][ici voir Krivine] ce qui ne signifie pas forcément que le concept en question n'est pas formalisable, il l'est peut-être, par un procédé que nous ignorons.--Michel421 (d) 11 mai 2008 à 01:09 (CEST)

Pour des choses très analogues, allez voir l'analyse non standard, et l'"ensemble" des entiers standards, par exemple. Dfeldmann (d) 28 mai 2008 à 19:49 (CEST)