Sous ensembles définissables

[Médiat]

Critique : les explications sur la complexité sont claires, pertinentes et très intéressantes, néanmoins il y a un aspect qui me gêne : certes « le monde des vérités mathématiques est inaccessible », mais il n’est pas utile d’invoquer Gödel ou ses successeurs pour cela, par exemple avec un ensemble très « simple » (pas tant que cela) et en tout état de cause très « naturel », à savoir les entiers naturels, il n’est pas possible de définir tous ses sous-ensembles, et même plus, un tirage aléatoire (infini, donc il n’est pas question de le réaliser) a plus de chance de donner un ensemble non définissable plutôt qu’un ensemble définissable.

Le passage de ton texte que j'ai cité me remplis de perplexité. Qu'entend tu par ensemble non-définissable: un ensemble qui ne puisse pas être énuméré par un algorithme ?

Non, ensemble non définissable dans ce contexte est un ensemble pour lequel il n'existe pas de formule du premier ordre qui soit capable de l'identifier (et donc de créer un ensemble grâce au schéma de compréhension), par exemple les nombre pairs sont définissables ; il est clair que si il existe une formule du premier ordre, il va exister un algorithme (dans un sens qui n'inclut pas la nécessité de se terminer, mmy a eu raison de le préciser) qui va "énumérer" cet ensemble (mais c'est un algorithme qui ne se terminera jamais, pour tous les ensembles infinis) ; l'algorithme est même très facile à écrire :
on initialise une variale à 0,
on teste si la valeur courante de la variable vérifie la formule du premier ordre, on décide si cette valeur est dans l'ensemble ou non,
on incrémente la variable
on boucle.

Mais le noeud de la question n'est pas là, en effet dans l'exemple de la citation initiale il est question de IN, mais la définition aurait été la même dans IR et là, pas question d'énumérer, même l'intervalle [0, 1] qui se définit pourtant très facilement.

N'hésite pas à poser des questions si je ne suis pas clair.
-----

[invite0fb72cf8]

Non, ensemble non définissable dans ce contexte est un ensemble pour lequel il n'existe pas de formule du premier ordre qui soit capable de l'identifier

Donc, par exemple, l'ensemble des nombres premiers est définissable dans ce contexte ? Qu'entend tu par formule de premier ordre (une recherche google ne m'a pas donné beaucoup de résultats, tu peux m'envoyer un site web si tu n'a pas envie de coucher un pavé ).

Mais le noeud de la question n'est pas là, en effet dans l'exemple de la citation initiale il est question de IN, mais la définition aurait été la même dans IR et là, pas question d'énumérer, même l'intervalle [0, 1] qui se définit pourtant très facilement.

Qu'il y aie des sous-ensembles bizarres dans IR ne m'étonne pas tellement, c'était surtout le fait que ton assertion se rapporte à IN qui m'a fait réagir.

Merci pour tes réponses,

Ising

[Médiat]

Qu'entend tu par formule de premier ordre

Le langage qui permet de parler de IN est (0, s, +, .) où s est la fonction successeur, une formule du premier ordre de l'arithmétique est une formule n'utilisant que ce langage (en plus du langage de la logique avec égalité) et des quantifications sur des variables et pas sur des sous-ensembles.
Par exemple dans IR, la propriété dîte de la borne supérieure n'est pas du premier ordre pour le langage des corps, car elle nécessite une quantification sur des sous-ensembles.
Dans le langage des corps, la propriété d'être archimédien n'est pas du premier ordre (elle nécessite autre chose que le langage des corps).

Donc, par exemple, l'ensemble des nombres premiers est définissable dans ce contexte ?

Le contexte est l'arithmétique de Peano : soit p(x) la formule .
L'ensembles des nombres premiers est bien l'ensemble des éléments x qui vérifient p(x).

[Urgon]

Le passage de ton texte que j'ai cité me remplis de perplexité. Qu'entend tu par ensemble non-définissable: un ensemble qui ne puisse pas être énuméré par un algorithme ?

Non, ensemble non définissable dans ce contexte est un ensemble pour lequel il n'existe pas de formule du premier ordre qui soit capable de l'identifier.

Je prends cette discussion - sur un sujet qui m'intéresse - en cours. Est-ce que je peux traduire le dialogue ci-dessus par :

Ising : Qu'entend tu par ensemble non-définissable: un ensemble qui n'est pas récursivement énumérable ?

Médiat : Non, ensemble non définissable dans ce contexte est un ensemble qui n'est pas récursif.

Ce qui n'est effectivement pas la même chose. Ou alors le point que tu voulais souligner, Médiat, est ailleurs ?

D'autre part, le concept de "nombre définissable" a été défini (!) par Emile Borel d'une manière plus souple que "il n'existe pas de formule de premier ordre..". Selon Borel, est définissable ce "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".

Cela a une importance, car le nombre Oméga de Chaitin, bien que "définissable" sans conteste (au sens de Borel), ne peut être défini par aucune formule de premier ordre.

Le nombre Oméga est il "définissable" selon toi, Médiat ?

[A voir en vidéo sur Futura]

[Médiat]

Médiat : Non, ensemble non définissable dans ce contexte est un ensemble qui n'est pas récursif.

Le lien que tu donnes précise bien que les ensembles récursifs sont des ensembles d'entiers (ou de n-uplets d'entiers), la notion de définissabilité que j'utilise ici est celle du premier ordre et concerne tous les ensembles de quelque cardinalité qu'ils soient (la différence est donc encore pire) ; par exemple dans le langage des corps (0, 1, +, .), IN n'est pas définissable dans IR ; mais dans un ensemble de cardinal muni d'une relation d'ordre et d'un symbôle de constante, définir l'ensemble des éléments plus petits (resp. plus grands) que la constante est très simple.

Le nombre Oméga est il "définissable" selon toi, Médiat ?

Aucune idée, pour que je puisse répondre il faudrait plonger la définition de Omega dans une théorie du premier ordre (et encore cela risque de ne pas être simple), mais quand je vois la définition probabiliste sur wikipedia, j'ai des doutes.

[Urgon]

Aucune idée, pour que je puisse répondre il faudrait plonger la définition de Omega dans une théorie du premier ordre (et encore cela risque de ne pas être simple), mais quand je vois la définition probabiliste sur wikipedia, j'ai des doutes.

Au sens "formule du premier ordre"; moi aussi.

Mais c'est un peu là où je voulais en venir : une définition d'un nombre définissable qui "manque" le nombre Oméga peut-elle être une définition pertinente ?

Car, au sens borélien, le nombre Oméga est bel et bien définissable : plusieurs mathématiciens peuvent étudier les propriétés du nombre Oméga (et il en a), et aboutissent aux mêmes conclusions. Ils étudient bien le "même" objet mathématique.

[Médiat]

Mais c'est un peu là où je voulais en venir : une définition d'un nombre définissable qui "manque" le nombre Oméga peut-elle être une définition pertinente ?

Oui. C'est juste pas la même problématique que la calculabilité.