Hiérarchie de Borel
Bonjour,
1) NOTATION Soit $\mathcal{S}$ une collection d'ensembles. On note $\mathcal{S}_\sigma$ la collection de tous les ensembles qui sont l'union dénombrable de membres de $\mathcal{S}$, et on note $\mathcal{S}_\delta$ la collection de tous les ensembles qui sont l'intersection dénombrable de membres de $\mathcal{S}$.
2) DÉFINITION Soit $X$ un espace métrisable. Soit $\omega_1$ le premier ordinal non-dénombrable. Pour $1 \leqslant \xi < \omega_1$, on définit les classes $\Sigma_\xi^0(X)$ et $\Pi_\xi^0(X)$ de sous-ensembles de $X$ par induction transfinie comme suit : $$
\begin{align}
\Sigma_1^0(X) & = \{U \subset X \mid U \text{ est ouvert}\}, \\
\Pi_\xi^0(X) & = \bigl\{X \setminus U \mid U \in \Sigma_\xi^0(X)\bigr\}, \\
\Sigma_\xi^0(X) & = \Bigl\{\bigcup_n A_n \mid A_n \in \Pi_{\xi_n}^0(X),
\xi_n < \xi, n \in \mathbb{N}\Bigr\} \text{ pour } \xi > 1.
\end{align}
$$ On définit en outre $\Delta_\xi^0 = \Sigma_\xi^0 \cap \Pi_\xi^0$.
3) LEMME. Pour tout $1 < \xi < \omega_1$, $$
\Sigma_{\xi}^0(X) =
{\left(\bigcup_{1 \leqslant \alpha < \xi} \Pi_\alpha^0(X) \right)}_\sigma
\quad\text{et}\qquad
\Pi_{\xi}^0(X) =
{\left(\bigcup_{1 \leqslant \alpha < \xi} \Sigma_\alpha^0(X) \right)}_\delta.
$$ 4) LEMME Pour tout $1 \leqslant \xi < \omega_1$, $\Sigma^0_\xi,\Pi^0_\xi \subset \Delta^0_\xi$.
5) QUESTION Comment démontrer ces deux points ? Soit $X$ un espace métrique. Si $\xi > 1$, $$
A \in \Delta^0_{\xi+1}(X) \,\iff\, A = \lim_n A_n
\text{ où $A_n \in \Delta^0_\xi(X)$}.
$$ Si $\xi$ est un ordinal limite, $$
A \in \Delta^0_{\xi+1}(X) \,\iff\, A = \lim_n A_n
\text{ où $A_n \in \bigcup_{\alpha < \xi}\Delta^0_\alpha(X)$}.
$$
1) NOTATION Soit $\mathcal{S}$ une collection d'ensembles. On note $\mathcal{S}_\sigma$ la collection de tous les ensembles qui sont l'union dénombrable de membres de $\mathcal{S}$, et on note $\mathcal{S}_\delta$ la collection de tous les ensembles qui sont l'intersection dénombrable de membres de $\mathcal{S}$.
2) DÉFINITION Soit $X$ un espace métrisable. Soit $\omega_1$ le premier ordinal non-dénombrable. Pour $1 \leqslant \xi < \omega_1$, on définit les classes $\Sigma_\xi^0(X)$ et $\Pi_\xi^0(X)$ de sous-ensembles de $X$ par induction transfinie comme suit : $$
\begin{align}
\Sigma_1^0(X) & = \{U \subset X \mid U \text{ est ouvert}\}, \\
\Pi_\xi^0(X) & = \bigl\{X \setminus U \mid U \in \Sigma_\xi^0(X)\bigr\}, \\
\Sigma_\xi^0(X) & = \Bigl\{\bigcup_n A_n \mid A_n \in \Pi_{\xi_n}^0(X),
\xi_n < \xi, n \in \mathbb{N}\Bigr\} \text{ pour } \xi > 1.
\end{align}
$$ On définit en outre $\Delta_\xi^0 = \Sigma_\xi^0 \cap \Pi_\xi^0$.
3) LEMME. Pour tout $1 < \xi < \omega_1$, $$
\Sigma_{\xi}^0(X) =
{\left(\bigcup_{1 \leqslant \alpha < \xi} \Pi_\alpha^0(X) \right)}_\sigma
\quad\text{et}\qquad
\Pi_{\xi}^0(X) =
{\left(\bigcup_{1 \leqslant \alpha < \xi} \Sigma_\alpha^0(X) \right)}_\delta.
$$ 4) LEMME Pour tout $1 \leqslant \xi < \omega_1$, $\Sigma^0_\xi,\Pi^0_\xi \subset \Delta^0_\xi$.
5) QUESTION Comment démontrer ces deux points ? Soit $X$ un espace métrique. Si $\xi > 1$, $$
A \in \Delta^0_{\xi+1}(X) \,\iff\, A = \lim_n A_n
\text{ où $A_n \in \Delta^0_\xi(X)$}.
$$ Si $\xi$ est un ordinal limite, $$
A \in \Delta^0_{\xi+1}(X) \,\iff\, A = \lim_n A_n
\text{ où $A_n \in \bigcup_{\alpha < \xi}\Delta^0_\alpha(X)$}.
$$
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
A \in \Delta^0_{\xi+1}(X) \,\iff\, A = \lim_n A_n \text{ où $A_n \in \Delta^0_\xi(X)$}.
$$ C'est facile. C'est l'autre sens qui me pose problème.
Ton lemme4 est faux (ça se voit même par un béotien qui n'y connaitrait rien vu tes définitions formelles de $\Delta$ juste avant ton lemme3
Par contre ce que tu demandes est simple, c'est la descente des "non" le long des formules.
Par exemple $non(A_1\cup A_2\dots) = (nonA_1) \cap (nonA_2) \cap \dots$.
Les $\prod$ étant définis comme les "non" des $\sum$, ça correspond à tes désirs.
Ton lemme3 est faux, on ne voit pas trop pourquoi on créerait un niveau $\sum_a$, si chacun de ses éléments étaient dans des $\prod_b$ avec $b<a$
De toute façon, tout ceci est une mise en symbolique de choses très simples:
"il revient au même de cloturer par complémentaire et union, que de cloturer par unions, intersections, mais en partant à la base des atomes et de leur complémentaires, etc en interchangeant union et intersection"
Pour $\Delta$ post suivant, j'ai un peu envie de boire du café :-D
J'ai rédigé une preuve mais je ne sais pas si elle est correcte. Je ne vois pas bien où j'utilise l'hypothèse d'ordinal limite (en fait c'est la 1ère fois que je fais des maths avec des ordinaux).
Pour le lemme 3, as-tu bien vu qu'il y a un $\sigma$ et un $\delta$ ?
Après j'ai lu la réaction de Christophe, qui disait : "purée, mais tout est faux !".
Après j'ai lu ton dernier post, qui a éclairé ma lanterne.
J'ai vraiment la flemme de décortiquer ta preuve (surtout qu'elle n'est pas facile à lire), mais j'imagine que l'idée est la bonne.
Je t'explique le coup des ordinaux limites (il n'y a pas besoin de connaître grand chose sur les ordinaux pour comprendre la hiérarchie borélienne) : tout est dans la définition 2) de Kechris. Comme il écrit un bouquin il essaye de raccourcir les définitions en les donnant de façon synthétique. Dans un cours présentiel pédagogique on t'expliquerait le passage aux ordinaux successeurs et le passage aux ordinaux limites.
Voilà ce que je te conseille : reprends la définition de Kechris et essaye de définir proprement les $\Pi_1^0$, les $\Delta_1^0$, les $\Sigma_2^0$, les $\Pi_2^0$ et les $\Delta_2^0$.
Ensuite essaye de faire de même avec les $\Sigma_{\omega}^0$, les $\Pi_{\omega}^0$ et les $\Delta_{\omega}^0$. Quand tu auras fait tout ça tu verras la différence entre l'étape successeur et l'étape limite.
Le point 3) est juste la définition donc je ne comprends pas que ce soit mis en lemme :-S
Le point 4) (avec effectivement $\xi+1$ à droite) est facile à montrer : il suffit de remarquer que $\Sigma^0$ est croissante (évident par définition) et $\Pi^0_\alpha \subset \Sigma^0_{\alpha+1}$ (aussi évident par définition).
Ce qui est un peu surprenant c'est qu'en général les choses ne sont pas définies comme ça, et c'est quand elles sont définies autrement qu'on a besoin d'une distinction successeur/limite.
Hmm, je dirais que c'est une reformulation de la définition.
Oui le point 4 est facile à démontrer, comme quasiment tous les points de mon pdf, à l'exception du théorème de réduction.
Quelles choses ne sont pas définies comme ça ? J'ai pris la définition de Kechris. Srivastava prend le point 3 comme définition. On a bien besoin de la distinction successeur/limite dans la preuve du théorème qui m'intéresse (Hausdorff-Lebesgue-Banach, section 24 de Kechris 1995).
Tout est là en fait, tu dois avoir le nez sur le guidon je pense (en plus avec les lettres grecques...).
La hiérarchie borélienne est spéciale et utilisée d'une façon très particulière (et pas du tout pour faire de la théorie de la mesure) en théorie descriptive des ensembles.
C'est ce qui explique cette hiérarchie qu'il faut voir comme une hiérarchie de formules et non d'ensembles.
Tu as des boréliens dont on peut décrire ce qu'il sont par une formule très compliquée ordinalement et qui sont .. l'ensemble vide.
Cette hiérarchie de formules te met juste un bon ordre, considéré comme naturel sur les formules:
D'abord les trucs simples, les ouverts
Ensuite leur complémentaire
Ensuite les unions dénombrables
Puis les complémentaires
Puis les unions dénombrables
and so on. On épuise théoriquement le tout à $\omega_1$ pour ce qui est de l'univers, c'est une notion relative à l'univers et à son $\omega_1$.
Les cas limite sont juste l'enregistrement de ce que tu as fait avant.
Si on veut éviter le passage aux complémentaires, et ça, en tant qu'expert en mesures, ça t'est familier, on
Départ (en mettant les complémentaires des atomes, donc les fermés)
Unions des
Intersections des
Unions des
Intersections des
Unions des
Intersections des
and so on.
C'est le truc le plus important de toute la science: l'irréductibilité de l'alternance de quantificateurs. Tu as la même chose, à peu près partout (pour les boréliens, l'indice est IN, mais c'est très conventionnel) :
Les Atomes
Les $\exists$
Les $\forall$
Les $\exists$
Les $\forall$
Les $\exists$
Les $\forall$
and so on
Tu remarqueras le côté arbitraire de mettre les $\forall$ après les $\exists$ de ma part, c'est une impolitesse grave. Du coup, tu rencontreras plutôt un dévot respect de la symétrie avec des trucs du genre:
$\exists $ || $\forall$
$\exists $ || $\forall$
$\exists $ || $\forall$
$\exists $ || $\forall$
and so on
Evidemment, comme toujours aux étapes limites, on prend tout ce qu'on a fait avant.
Je pense que c'est à ça que tu as affaire présentement par exemple.
Il est aussi possible par économie "un peu bizarre", certains auteurs "sautent" les étapes limites. Du coup, que font-ils?
Et bien :
$\exists $ || $\forall$
$\exists $ || $\forall$
$\exists $ || $\forall$
.
.
étape limite: formes = union de trucs avant || forme = 1intersection des trucs avant
$\exists $ || $\forall$
$\exists $ || $\forall$
$\exists $ || $\forall$
.
.
and so on.
Bref, on a l'impression d'être décorateur d'intérieur en faisant ça :-D
Et c'est pas fini :-D Tu vas tomber sur les versions dites "light". C'est la même chose, mais "sans paramètre". Du coups les premiers ordinaux te donnent les complexités des formules arithmétiques. Et les célèbres théorèmes "à la Godel-Tarski-Turing-Church et cie" disent que l'ensemble des énoncés vrais en arithmétique est $\Delat^0_\omega$ par exemple.
Bref, si tu t'attend à "cerner" d'un coup ces hiérarchies de formules, tu risque d'être déçu. Par contre, elles t'indiquent la complexité d'une définition de borélien.. A défaut de cerner, on NOMME ;-)
Pour les lemmes etc, je t'ai répondu, c'est toujours le même principe d'élimination des "non" que l'on fait redescendre sur les atomes. Le dénombrable n'y est pour rien, ça vaut pour toute formule $\infty$-borel (c'est la même chose avec les ordinaux en indices à la place des entiers. Et de ce fait toute formule a ... une probabilité de survenir. C'est comme ça (moyen parmi d'autre) que l'univers tout entier "sent" et "commente" ce qu'il y a ... à l'extérieur de lui.
Par exemple, la probabilité nulle de la formule $$x\mapsto \cup_{a\in \R} \ [x=a]$$
signale aux mégalos que leurs réels sont "que dalle" à côté de tous ceux qui ne sont pas dans l'univers. Il n'en est pas moins vrai qu'elle désigne $\R$ en tant que borélien replatonisé à l'échelle de l'univers.
Peux-tu l'énoncer, ça ira peut-être plus vite si on te le démontre directement du coup, non?
Ah effectivement je n'avais pas repéré que ton document parlait d'autre chose que tes 2 lemmes. Mais du coup je ne comprends pas ta question initiale, tu peux préciser ?
Quant à la question de la définition, c'est très certainement comme ça que fait Kechris, et c'est équivalent à la définition "usuelle", mais comme dit Martial la définition est en général présentée de manière moins synthétique pour être plus compréhensible à des débutant.e.s. Mais je viens de jeter un oeil à wikipedia, et visiblement c'est cette définition qui y est donnée aussi - donc j'ai peut-être rêvé en pensant que la définition usuelle était autre chose ( à vrai dire, à part faire une distinction successeur/limite dans la définition, qui peut être utile, je n'arrive plus trop à voir ce qui pourrait être différent, ce qui participe à l'idée que Martial et moi avons eu une hallucination collective :-D )
Il faut savoir :-D ça va te faire plaisir max, que les théoriciens descriptifs comme Kechris and co sont des microscopeurs: qu'entends-je par là?
Et bien ils essaient de tout comprendre jusqu'aux rouages les plus élémentaires. C'est la raison pour laquelle "la théorie descriptive" est "en partie" née, ayant comme point de départ, disons (je brode, mais ça donne le principe) le théorème de séparation des analytiques par des boréliens, avec une des plus belles preuves de tous les temps, mais très peu constructive, et la volonté de rendre cette preuve "complètement obsolète" par écrasement du mécanisme sous la compréhension ultime.
C'est ainsi qu'ont émergé des théorèmes comme"tout ensemble analytique qui ne contient que des parties bien ordonnées de $\Q$ est "pauvre" au sens qu'il existe un ordinal qui le borne toutes, etc.
Et de là, a émergé des auteurs mettant parfois des heures à rajouter une brindille de menthe, à faire réchauffer un plat 4.8 secondes, pour affiner, etc. D'où des définitions aux apparences parfois un peu "arbitraires". Alors qu'en réalité il s'agit d'une prévision pour faire sauter 2 étapes 514 étapes plus loin.
Ils "n'ont pas compris" (je trolle) que pour faire "vraiment ça", faut passer en logique affine (VOIRE LINEAIRE), et que leurs empilements de RPA infinistes de toute façon ne les amène qu'à des ordinaux qui gardent leur boite noire intacte.
@Steven: le théorème que tu signales se fait facilement avec ton expertise "théorie de la mesure". C'est vraiment le même genre d'arguments, qui ont toujours le même plan: "la plus petite classe machin a les propriétés trucs donc contient la plus petite classe qui a les propriétés trucs"
Ne te laisse pas impressionner par la prise d'espaces métriques "quelconques". La séparabilité ramène tout à $\R$.
Si $f(A)$ et $g(B)$ sont inséparables alors il existe $a_1,b_1$ tel que $f(Aa_1)$ est inséparable de $g(Bb_1)$. Pour les mêmes raisons il existe $a_2,b_2$ tels que $f(Aa_1a_2)$ est inséparable de $g(Bb_1b_2)$, etc.
A la fin les singletons $\{f(a)\}$ et $\{g(b)\}$ sont inséparables, contradiction. Conclusion, $f(A)$ et $g(B)$ étaient bien séparables par un borélien.
On a tout en un: un bon gros coup de RPA + un bon gros coup d'infini renversé, que du bonheur. Ca les a attiré comme le rouge attire les taureaux, fallailt qu'ils explorent chaque mm² de cette montagne merveilleuse.
Précision: $Xx$ est l'ensemble des éléments de $X$ qui commencent par $x$. De plus si on pouvait séprarer $f(Au)$ de $g(Bv)$, pour tout $u,v$, par le borélien $C(u,v)$, ie $Machin \subset C(u,v)$ qui est disjoint de $Truc$, on pourrait séparer $f(A)$ et $g(B)$ par le borélien
$$ \exists u\forall v : ToBeIn(C(u,v))$$
Du coup, est-ce que tu tiens VRAIMENT à connaitre EXACTEMENT l'ordinal qui mesure la Baireitude ou la Borélianité d'une fonction?
Parce que sinon, les Baires sont celles obtenues en itérant le passage à la limite simple à partir des continues et les boréliennes sont celles dont l'image réciproque envoie chaque ouvert sur un borélien.
Baire inclus dans Boral est "routinier" (ce sont des dadas initiaux en théorie de la mesure) et Borel inclus dans Baire assez aussi mais va nécessiter probablement de particulariser l'espace métrique d'arrivée (d'où ton "séparable"). Ca évite d'avoir des "localement Borel" non Borel "tout court".
Tu peux prouver qu'une limite simple de fonctions boréliennes est boréliennes. C'est le côté "facile".
Soit $U$ un ouvert de l'espace d'arrivée, et surtout on considère que $U$ est la réunion d'une suite d'ouverts $U_n$ vérifiant $adh(U_n)\subset U$. Ca fait tout le charme de la théories descriptive ces précautions continuelles.
Chacun des $U_n$ a une image réciproque par les item de la suite borélienne. Maintenant look:
$(f(x) \in U) = $
$(\exists n: f(x)\in U_n) = $
$(\exists n \exists p\forall q>p: f_q(x)\in U_n) = $
$(\exists n \exists p\forall q>p: x\in A(q,n) )$
ce qui montre que l'image réciproque de tout ouvert par $f$ est borélien.
La réciproque est probablement une horreur absolue à cause de nos obsessions pour les fonctions qui apparaissent des objets "isolés".
L'espace d'arrivée étant séparable, on dispose de boule de centre un élément du dense dénombrable et de rayon rationnel. Je les appelle $B_n$.
Tu as une fonction borélienne $f$ de complexité minimum à être contre-exemple (cette notion de minimum, c'est ce que cherche Kechris à formaliser avec ses ordinaux)
Sa borélianité minimum te permet de savoir que pour chaque $x$ et chaque $n$, il y a une famille $p\mapsto A(n,p)$ d'ensembles de l'ensemble de départ, tels que $f^{-1}(B_n) = $ réunion des $A(n,p)$ quand $p$ parcourt $\N$. En outre les $A(n,p)$ sont de complexité suffisamment petite pour que tu puisse exiger la chose suivante:
J'associe à $x$ une suite de boules $C(x,n)$ de rayon $1/n$ qui contiennent $f(x)$, et une famille de $D(x,p,n)$ ensembles de complexité plus petite tels que $f^{-1}(C(x,n) = \cup_p D(x,n,p)$
J'ai une suite de fonctions "Baire" $g_n$ telles que pour tout $x$ et tout $n,p\leq n$, si $x\in D(x,n,p)$ alors $g_n(x)\in C(x,n)$
Cette $g$ existe car elle répond à moins d'exigences que $f$ qui existe.
Bon, c'est très bâclé, je te donne juste l'idée, la construction de $g_n$ requiert un peu plus de soin. Mais in fine, une fois que tu as ta suite de $g_n$, "Baires", elle converge simplement vers $f$ et c'est fini.