Ideal Analytic sets

Cet article fournit des exemples naturels d'ensembles analytiques complets en démontrant que l'idéal de Hindman et l'idéal $\mathcal{D}$ sont $\mathbf{\Pi}_1^1$-complets, tout en explorant les liens entre ces idéaux et certaines familles d'arbres classiques comme ceux de Sacks et Miller.

L'essentiel

Imaginez que vous êtes un architecte qui conçoit des bâtiments infinis. Dans le monde des mathématiques, ces bâtiments sont appelés des espaces polonais (comme la ligne réelle ou des espaces de suites infinies). L'article que nous allons explorer, écrit par Łukasz Mazurkiewicz et Szymon Żeberski, est une enquête sur la complexité de certains de ces bâtiments.

Plus précisément, les auteurs cherchent à identifier des structures si complexes qu'elles servent de "référence ultime" pour mesurer la difficulté de tout autre problème mathématique de ce type. Ils appellent ces structures des ensembles analytiques complets.

Voici une explication simplifiée de leur travail, divisée en deux grandes aventures.

Partie 1 : Les Jardins Interdits (Les Idéaux sur les nombres)

Imaginons que vous ayez une boîte infinie remplie de nombres naturels (1, 2, 3, 4...). Un idéal est comme une règle de jardinage qui dit : "Voici les plantes que vous avez le droit de garder dans votre panier."

• Si vous gardez une plante, vous devez aussi garder toutes ses petites feuilles (sous-ensembles).
• Si vous gardez deux plantes, vous pouvez les mettre ensemble dans le panier (union finie).

Le but des auteurs est de trouver des règles de jardinage si bizarres et complexes qu'il est impossible de les décrire simplement (elles ne sont pas "Boreliennes"). Pour prouver cela, ils utilisent une astuce géniale : la réduction.

L'analogie de l'arbre de décision :
Imaginez un arbre de décision infini (comme un jeu de "choisissez votre propre aventure" qui ne finit jamais).

• Si l'arbre a une branche qui continue à l'infini, on dit qu'il est "mal fondé" (il ne s'arrête jamais).
• Si l'arbre s'arrête toujours, il est "bien fondé".

Les mathématiciens savent déjà que trouver si un arbre a une branche infinie est un problème très difficile (c'est l'exemple de référence de la complexité).

La méthode unifiée :
Les auteurs disent : "Et si on transformait n'importe quel arbre de décision en un panier de nombres ?"
Ils créent une machine (une fonction) qui prend un arbre et le transforme en un ensemble de nombres.

• Si l'arbre a une branche infinie, le panier de nombres résultant est "trop gros" pour être dans notre règle de jardinage (il n'est pas dans l'idéal).
• Si l'arbre s'arrête, le panier est "petit" et rentre dans la règle.

En faisant cela, ils prouvent que leur règle de jardinage est aussi complexe que le problème de l'arbre infini. Ils appliquent cette machine à plusieurs types de règles :

1. L'idéal de Ramsey : Une règle basée sur les paires de nombres.
2. L'idéal de Hindman : Une règle basée sur les sommes de nombres (si vous prenez un ensemble infini, toutes les sommes possibles de ses éléments doivent être dans le panier).
3. L'idéal des différences : Basé sur les soustractions.

Leur découverte ? Ces règles sont toutes des "monstres" de complexité. Elles sont $\Pi^1_1$-complètes. En langage simple : c'est le niveau de difficulté maximal pour ce type de problème. Si vous pouvez résoudre le problème de l'arbre infini, vous pouvez résoudre le problème de ces règles de jardinage, et vice-versa.

Partie 2 : Les Codes Secrets des Arbres (Les Arbres et les Espaces)

Dans la deuxième partie, les auteurs changent de décor. Au lieu de jouer avec des nombres, ils jouent avec des arbres eux-mêmes.

Imaginez que chaque arbre est un code secret qui décrit un bâtiment (un ensemble fermé) dans un espace infini.

• Certains arbres sont très "paresseux" : ils s'arrêtent vite.
• D'autres sont très "généreux" : ils ont des branches infinies partout.

Les auteurs s'intéressent à des types d'arbres très spécifiques, comme les arbres de Miller ou Laver.

• Un arbre de Miller est comme un arbre qui, à chaque nœud, a une infinité de branches qui partent. C'est un arbre très "branchu".
• Un arbre de Sacks est un arbre parfait qui se divise toujours en deux.

La grande question :
Si je vous donne un code (un arbre), pouvez-vous dire rapidement si cet arbre contient un sous-arbre "spécial" (comme un arbre de Miller) ?

Les auteurs montrent que la réponse est non, pas facilement.
Ils prouvent que l'ensemble de tous les codes qui contiennent un arbre de Miller (ou de Laver) est un ensemble $\Sigma^1_1$-complet.

Pourquoi est-ce important ?
Cela a des conséquences sur la géométrie de ces espaces infinis :

• Un ensemble fermé qui contient un arbre de Miller est "trop gros" pour être un simple tas de points isolés (il n'est pas $\sigma$-compact).
• Un ensemble qui contient un arbre de Laver a une propriété de domination très forte.

En résumé, ils disent : "Si vous voulez savoir si un ensemble fermé est 'petit' (comme un tas de poussière) ou 'grand' (comme une forêt infinie), vous devez résoudre un problème mathématique d'une complexité extrême."

Conclusion : Ce qui est simple et ce qui ne l'est pas

Pour finir, les auteurs font une petite remarque intéressante. Ils montrent que certaines règles, comme "être un ensemble de mesure nulle" (très petit en taille) ou "être un ensemble maigre" (très petit en densité), sont en fait simples (Boreliennes). On peut les vérifier sans avoir à résoudre le problème de l'arbre infini.

En résumé, l'article nous dit :

1. Il existe des règles mathématiques (idéaux) et des types d'arbres si complexes qu'ils sont les "champions du monde" de la difficulté.
2. Les auteurs ont trouvé une méthode universelle (une machine) pour transformer n'importe quel problème d'arbre infini en ces règles, prouvant ainsi leur complexité.
3. Cela nous aide à classer les problèmes mathématiques : certains sont "faciles" (Boreliens), d'autres sont "très durs" (Analytiques complets), et ceux-ci sont les plus durs de tous.

C'est comme si les auteurs avaient créé un test de QI mathématique ultime : si vous pouvez passer ce test, vous pouvez résoudre presque n'importe quel problème de ce type dans le monde des ensembles infinis.

Résumé technique

Voici un résumé technique détaillé de l'article « IDEAL ANALYTIC SETS » de Łukasz Mazurkiewicz et Szymon Żeberski, rédigé en français.

Titre : Ensembles Analytiques Idéaux

Auteurs : Łukasz Mazurkiewicz et Szymon Żeberski
Domaine : Théorie descriptive des ensembles, Topologie polonaise, Idéal sur $\omega$.

---

1. Problématique et Contexte

L'objectif principal de cet article est de fournir des exemples « naturels » d'ensembles $\Sigma^1_1$-complets (analytiques complets) et $\Pi^1_1$-complets (coanalytiques complets) dans le cadre de la théorie descriptive des ensembles.

Bien que l'existence d'ensembles analytiques non boréliens soit connue (notamment l'ensemble des arbres mal fondés, $IF_\omega$), identifier des ensembles naturels dans des contextes spécifiques (comme les idéaux sur les entiers naturels ou les codes d'ensembles fermés dans les espaces polonais) comme étant complets pour ces classes de complexité est un défi.

Le papier se divise en deux parties :

1. L'étude des idéaux sur $\omega$ (l'ensemble des entiers naturels).
2. L'application de ces résultats à la complexité descriptive de familles d'arbres et au codage d'idéaux $\sigma$-additifs dans les espaces polonais (comme l'espace de Baire $\omega^\omega$ ou l'espace de Cantor $2^\omega$).

2. Méthodologie : L'Approche Unifiée

Les auteurs s'appuient sur une méthode unifiée introduite dans une référence antérieure [3] pour construire des réductions boréliennes.

• Concept de réduction : Un ensemble $B$ est réductible à $A$ s'il existe une fonction borélienne $f$ telle que $f^{-1}[A] = B$. Si $B$ est $\Sigma^1_1$-complet et réductible à $A$, alors $A$ l'est aussi.
• L'objet de référence : L'ensemble $IF_\omega$ (l'ensemble des arbres sur $\omega$ qui sont mal fondés, c'est-à-dire ayant une branche infinie) est le standard $\Sigma^1_1$-complet.
• Construction de la réduction :
  Soit $\Lambda$ un ensemble dénombrable infini et $\rho : P(\omega) \to P(\Lambda)$ une fonction monotone. On définit une famille $I_\rho = \{A \subseteq \Lambda : (\forall F \in [\omega]^\omega)(\rho(F) \not\subseteq A)\}$.
  Les auteurs construisent une fonction borélienne $\varphi : Tree_\omega \to P(\Lambda)$ telle que :
  $$\varphi^{-1}[I_\rho^+] = IF_\omega$$
  où $I_\rho^+$ est le dual de l'idéal (les ensembles qui ne sont pas dans l'idéal).
  La preuve repose sur l'existence d'une injection $\alpha : \omega^{<\omega} \to \omega$ préservant l'ordre d'inclusion des séquences, permettant de transformer une branche infinie dans un arbre en un ensemble appartenant à $I_\rho^+$, et inversement.

3. Résultats Principaux

Partie I : Idéaux sur $\omega$

Les auteurs démontrent que plusieurs idéaux classiques sont $\Pi^1_1$-complets (ce qui signifie que leur complémentaire est $\Sigma^1_1$-complet).

1. L'Idéal de Ramsey ($R$) :

   • Défini par $R = \{A \subseteq \omega : [A]^2 \notin R\}$ (les ensembles qui ne contiennent pas de sous-ensemble infini dont toutes les paires sont dans l'ensemble).
   • Résultat : $R$ est $\Pi^1_1$-complet. La preuve utilise la réduction unifiée pour montrer que si un ensemble est dans le dual de $R$, il contient une structure d'arbre infini.

2. L'Idéal de Hindman ($H$) :

   • Défini par les ensembles qui ne sont pas des IP-sets (ensembles contenant les sommes finies non vides d'un sous-ensemble infini).
   • Résultat : $H$ est $\Pi^1_1$-complet. La preuve est plus technique, exploitant la représentation binaire des nombres pour garantir que les sommes finies préservent la structure de l'arbre.

3. Modifications de l'Idéal de Hindman ($H_k$) :

   • Généralisation aux sommes de exactement $k$ éléments ($FS_k$).
   • Résultat : $H_2$ est démontré comme étant $\Pi^1_1$-complet. Les auteurs formulent la Conjecture 1 selon laquelle $H_k$ est $\Pi^1_1$-complet pour tout $k \ge 2$.
   • Ils établissent également la hiérarchie d'inclusion : $n | m \iff H_n \subseteq H_m$.

4. L'Idéal des Différences ($D$) :

   • Défini par les ensembles qui ne contiennent pas de différences infinies ($\Delta(B) = \{a-b : a,b \in B, a>b\}$).
   • Résultat : $D$ est $\Pi^1_1$-complet. La preuve utilise une injection vers les puissances de 2 pour simplifier l'analyse des différences.

Partie II : Arbres et Codes d'Ensembles Fermés

La seconde partie relie les idéaux précédents à la complexité descriptive des familles d'arbres et des ensembles fermés dans les espaces polonais.

1. Arbres de Mathias, Miller et Laver :

   • Les auteurs montrent que la famille des arbres contenant un arbre de Mathias (lié au forcing de Mathias) est $\Sigma^1_1$-complet.
   • Par extension, les familles d'arbres contenant un arbre de Miller ou un arbre de Laver sont également $\Sigma^1_1$-complets.

2. Arbres de Sacks et Silver (sur $2^{<\omega}$) :

   • Théorème 3.7 : La famille des arbres contenant un arbre de Sacks (arbre parfait) est $\Sigma^1_1$-complet.
   • Théorème 3.9 : La famille des arbres contenant un arbre de Silver est $\Sigma^1_1$-complet.
   • Ces résultats sont obtenus via des réductions boréliennes sophistiquées depuis $IF_\omega$.

3. Complexité des Codes d'Ensembles Fermés (Corollaires) :
   En utilisant la correspondance entre les arbres et les ensembles fermés (via le corps de l'arbre $[T]$), les auteurs déduisent la complexité des ensembles de codes pour certains idéaux $\sigma$ :

   • Les codes d'ensembles fermés Ramsey-nuls sont $\Pi^1_1$-complets.
   • Les codes d'ensembles fermés $\sigma$-compacts sont $\Pi^1_1$-complets.
   • Les codes d'ensembles fermés non fortement dominants sont $\Pi^1_1$-complets.
   • Les codes d'ensembles fermés $G$-indépendants (liés aux arbres de Silver) sont $\Pi^1_1$-complets.

4. Contre-exemples Boréliens :
   Pour nuancer, les auteurs montrent que certains ensembles de codes classiques sont boréliens (et donc pas $\Pi^1_1$-complets) :

   • Les codes d'ensembles fermés maigres (meager).
   • Les codes d'ensembles fermés de mesure nulle.

4. Signification et Contribution

• Unification : Le papier offre un cadre unifié pour prouver la complétude $\Sigma^1_1$ et $\Pi^1_1$ de divers objets combinatoires et topologiques, évitant des preuves ad hoc pour chaque cas.
• Nouveaux Exemples : Il fournit une liste systématique d'exemples naturels d'ensembles complets, enrichissant la littérature sur la classification des ensembles analytiques et coanalytiques.
• Lien Combinatoire-Topologique : Il établit des ponts clairs entre les propriétés combinatoires des idéaux sur $\omega$ (sommes, différences, paires) et la structure topologique des ensembles fermés dans les espaces de Baire et de Cantor (compacité, domination, nullité de Ramsey).
• Résolution de Conjectures : Bien que la conjecture sur $H_k$ pour tout $k$ reste ouverte dans le texte (avec une note indiquant une preuve ultérieure par Jacek Tryba), la démonstration pour $k=2$ et la structure de l'approche ouvrent la voie à des généralisations.

En résumé, cet article consolide la compréhension de la complexité descriptive des structures fondamentales en théorie des ensembles, en démontrant que de nombreuses propriétés « naturelles » (comme être un IP-set, être Ramsey, ou contenir un arbre de Sacks) correspondent exactement aux niveaux les plus élevés de la hiérarchie analytique/coanalytique.