le corps de réels calculables est-il complet ?

[acx01b]

Bonsoir,

Le corps des réels calculables est-il complet ?
(Un réel est calculable si il existe un algorithme au sens de Turing qui sait énumérer ses décimales. L'algorithme (qui énumère une décimale de ce nombre) doit pouvoir être défini par une suite finie de 0/1 et s'exécuter en un temps fini)

On dit qu'un corps qui contient les rationnels est complet si toute suite de Cauchy d'éléments du corps converge vers un élément du corps.

Si l'on considère uniquement les suites de Cauchy calculables, on trouve que le corps des réels calculables est complet ?
Et si l'on considère également les suites de Cauchy non calculables, on trouve que le corps des réels est le plus petit corps complet qui contient Q ?
Donc si l'on considère la "calculabilité" des objets mathématiques et en particulier des nombres comme axiome, on trouve que R n'existe pas et que le plus petit corps complet qui contient Q est l'ensemble des réels calculables qui est par définition en bijection avec N ?
Au contraire si on utilise l'axiome qu'il existe des nombres "non-calculables" on tombe sur la définition habituelle des réels ?
-----

[acx01b]

( L'algorithme pour un réel calculable en particulier, qui prend en entrée n et qui retourne sa n ème décimale, doit s'exécuter en un temps fini et tenir sur une mémoire finie, idem pour une suite de Cauchy calculable en particulier)

[Médiat]

Bonjour,

Le corps des réels calculables ne possède pas la propriété de la borne sup.
Vous pouvez jeter un œil au document "final.pdf" : http://forums.futura-sciences.com/ma...ml#post3958180

Le chapitre VI.4, et en particulier la page 191, où vous trouverez un contre-exemple.

[acx01b]

Je suis encore plus perdu. En y réfléchissant je pense avoir entendu parler du nombre de Chaitin (définissable mais non calculable) en cours à Paris 6.

Il existe un corps entre les réels calculables et les réels définissables ? Et entre les réels définissables et les réels ?

[A voir en vidéo sur Futura]

[Médiat]

Calculable() est compris entre Calculable et Définissable.
Définissable(), pour non définissable est compris entre Définissable et

[acx01b]

Ces deux corps sont définis (un peu comme le nombre de Chaitin) mais ne sont pas construits (par induction?) à partir d'objets de base (dans les deux cas on fait appel à un objet, pour le moment, hypothétique ?).

Qu'il n'existe pas d'algorithme général calculable pour prouver que deux réels calculables a,b égaux sont bien égaux, ça me parait difficile à prouver. Ça voudrait dire qu'il existe des vérités mathématiques (ici en particulier qu'en énumérant les décimales de a et b on n'en trouvera jamais de différentes) qui sont impossibles à prouver ?

[acx01b]

En fait si j'ai bien compris, pour le nombre de Chaitin il existe une suite croissante (et majorée par 1, donc de Cauchy) calculable qui converge vers ce nombre donc il n'est pas hypothétique, et il est naturel de vouloir l'ajouter à l'ensemble des réels calculables. Donc j'ai dit une bêtise.

[invite8133ced9]

Bonsoir,

Si je peux me permettre, l'existence d'un ensemble des réels définissables est équivalente à l'existence d'une formule définissant un réel définissable.
En tout cas, on ne peut pas donner sens à des assertions comme "l'ensemble des réels définissables est dénombrable" sans démontrer son existence; sinon, les paradoxes ne seraient pas loin.

[acx01b]

Oui mais je reste persuadé qu'il y a définir et définir.

Dans ce cas particulier des corps compris entre Q et R, on doit, entre autre détailler :
- comment on définit les éléments du corps
- notamment comment on définit l'opérateur " appartient_au_corps (x : nombre) -> booléen "
- pour définir cet opérateur on doit d'abord définir quelle est la représentation de x, et quelle est la formule qui garantit que l'appartenance d'un nombre au corps n'est pas indécidable
- si certain éléments sont des limites de suites, il faut définir le type de suite en question et comment on les construit
- comment on ordonne le corps (donc en définissant des opérateurs de comparaison)
- etc..

j'ai l'impression que tous ces points sont non triviaux quand on parle du corps des réels calculables ou des réels définissables.

J'en déduis donc (naïvement) que si on considère enfin le corps des réels, ces questions deviennent tellement compliquées (pour le commun des mortels) qu'on ne se pose même plus la question de la nature de ces opérateurs, de leurs représentations et même de leur existence : on prend pour axiome qu'ils existent et que si un jour, pour un problème particulier, on a besoin de les manipuler, on y arrivera.

Si on prend les réels calculables, et qu'on considère suivant la même construction les suites calculables, on tombe sur le nombre de Chaitin qui n'est pas calculable. Ça remet en question la manière dont on a construit ce corps des réels calculables puisque cette notion de calculabilité est on ne peut plus naturelle et intuitive, et je pense ne pas être le seul à ne pas avoir trop envie de manipuler des nombres non calculables, ou pire non définissables, car on craint que ça nous amène à ensuite considérer des objets de plus en plus tordus et c'est la voie royale vers l'indécidabilité généralisée.

[invite8133ced9]

Pour ce qui est des réels calculables, leur définition est donnée dans le document proposé par Mediat.
La définition par les fonctions récursives permet de les étudier dans ZF et de considérer leur ensemble.
La structure de corps ordonné sur cet ensemble est simplement la "restriction" à l'ensemble des réels calculables de la structure de corps ordonné usuelle sur .
La liste de contraintes que tu donnes est donc respectée, dans ce qui s'applique aux réels calculables, pour les réels calculables.


C'est une autre histoire pour les réels définissables, puisqu'aucun des points n'est rempli à leur sujet.

En fait les problèmes de définissabilité ne se réduisent pas à des questions d'existence: l'existence est codée dans le langage de la théorie (), contrairement à la définissabilité qui se situe au dessus. Il ne s'agit donc pas de rajouter un axiome introduisant un ensemble non défini; on ne pourrait même pas l'écrire.

La présence éventuelle d'objets tordus mais absolument invisibles n'est pas gênante en mathématique, ou du moins elle ne l'est que parce qu'elle montre que notre portée est limitée. Mais tant qu'il est impossible d'interagir avec des réels non définissables, ben il ne risque pas d'y avoir de problèmes. Encore une fois c'est une question de langage, on pourrait croire que ces réels définissables vont interdire des théorèmes qui seraient vrais pour les autres réels. Mais en fait, plus ils se distinguent par les théorèmes qu'ils invalident, plus ils se définissent, ce qui limite leur capacité à nuire. (Ce n'est pas une preuve hein, juste une idée).