Un peu de théorie effective

Martial
Martial
dans Fondements et Logique
Bonjour à tous,

J'en suis à la théorie descriptive EFFECTIVE des ensembles (qui est loin d'être ma spécialité). Les classes de complexité évoquées ci-dessous sont donc à comprendre au sens "lightface".
Pour simplifier je note $\mathcal{N} = \omega^{\omega}$ et $X_{p,q} = \omega^p \times \mathcal{N}^q$.

Vers le bas de la page 346, Patrick Dehornoy écrit :
Corollaire (non dégénérescence) : Pour tous $p$ et $q$, les relations d'inclusion $\Delta^0_1 \subseteq \Sigma^0_1$ et $\Delta^0_1 \subseteq \Pi^0_1$ sont strictes pour $X_{p,q}$.

Ma question : ne faut-il pas préciser "dès l'instant que $q \geq 1$" ?

Merci d'avance

Martial

Réponses

  • Maxtimax
    Maxtimax
    Peux-tu rappeler ce que veut dire lightface, j'oublie toujours ?

    Pour boldface (les boréliens du coup ? Ou je me trompe sur bold/lightface) oui, vu que $\omega^p$ est discret donc tout est déjà ouvert-fermé
  • Martial
    Martial
    Boldface c'est les boréliens et les projectifs, lightface c'est les hiérarchies arithmétiques et analytique.

    Je suis d'accord avec toi pour boldface tout est trivial.

    Pour lightface, il y a 2 cas mais je ne suis pas sûr de mon coup.
    J'aurais tendance à dire la chose suivante : pour la hiérarchie arithmétique ça revient en gros à se demander si le complémentaire d'un $\Sigma^0_1$ est encore $\Sigma^0_1$, et ça on sait bien que c'est faux. Donc la hiérarchie arithmétique est encore stricte.

    Par contre pour la hiérarchie analytique (toujours dans le cas de $\omega^p$), j'ai l'impression qu'elle est triviale à partir de $\Sigma^1_1$, $\Pi^1_1$, puisqu'il n'y a pas de $\omega^{\omega}$- projection.

    Tu en penses quoi ?
  • Martial
    Martial
    En fait je me rends compte que j'ai mal formulé ma question de base.
    Ce que je veux savoir c'est dans le cas où l'espace ambiant est $\omega^p$, quelles sont, dans la double hiérarchie arithmético-analytique, les inclusions qui sont strictes et quelles sont celles qui sont des égalités ?
  • Maxtimax
    Maxtimax
    Mhm je ne connais pas grand chose à la hiérarchie analytique donc je ne saurais pas te dire, mais je suis d'accord que pour arithmétique ça reste strict.
  • Martial
    Martial
    Merci Max.
  • christophe c
    christophe c
    Salut Martial,

    je n'y connais rien en théorie effective, mais par contre j'ai l'impression qu'il y a peut-être une petite confusion (c'est peut-être moi qui me trompe) :

    "light" je crois que ça veut juste dire "définition sans paramètre" et non pas qu'on change d'ensemble (on ne passe pas aux entiers).

    Par exemple l'ensemble des réels constructibles est un projectif light, mais l'ensemble des réels constructibles à partir de l'oracle $a$ est a priori pas light puisque $a$ a le droit d'être n'importe quel réel.

    SAUF ERREUR DE MA PART, ces souvenirs étant très lointains.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Martial
    Martial
    @Christophe : non ce n'est pas ça.
    J'appelle réel tout élément de $\omega^{\omega}$. Pour définir les sous-ensembles récursifs de $\mathbb{R}$ tu fais comme avec les sous-ensembles récursifs de $\omega^p$ mais en rajoutant la fonction $eval$ aux fonctions de base. Un ensemble récursif est dit $\Sigma^0_1$.
    Roughly speaking, un ensemble est $\Sigma^0_1(a)$ s'il existe une machine qui peut savoir, pour un $x$ donné, si $x$ est dans cet ensemble à condition de disposer d'un oracle qui lui permette de "deviner" des valeurs de $a(n)$ quand il en a besoin.

    Je crois que si $0^{\#}$ existe l'ensemble des réels constructibles est $\Sigma^1_3$ (à confirmer). Mais si $V=L$ il est $\Delta^0_1$ puisque c'est $\mathbb{R}$ tout entier, lol.
  • christophe c
    christophe c
    Merci pour ces précisions. Mais quand tu commences par "non non", es-tu sûr qu'on ne dit pas en fait la même chose?
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    Autrement dit que tu aurais pu dire "oui oui, on peut le dire autrement ..."
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Martial
    Martial
    @Christophe : tu remarqueras que je te réponds avec 2 jours de retard, ce qui m'arrive rarement. C'est juste que j'ai fait un truc inédit : j'ai passé 2 jours à Rouen, pour l'anniversaire d'un pote. Du coup je n'étais pas connecté. J'avais amené mon pc portable mais je ne l'ai même pas ouvert, trop occupé que j'étais à respirer l'air pur, à kiffer les terrasses et à savourer les mets préparés à cette occasion par mon pote.

    Bref, pour répondre à ta question je ne suis pas sûr que l'on ne dise pas la même chose. Le truc c'est que je ne sais pas exactement ce que tu entends par "définition sans paramètre". Peux-tu préciser un peu ?
  • Chaurien
    Chaurien
    kiffer ?
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 23

ChaurienDeGeerJLTJLapinKarnajM.Oueslati.M.Vassilliabiguine_equationchanigtroisqua +13 Invités