Forcing with random variables in bounded arithmetics and set theory

Cet article analyse le forçage booléen à valeurs aléatoires dans l'arithmétique bornée sous l'angle de la théorie des ensembles, démontrant que ce forçage est isomorphe à une algèbre de probabilité non séparable et étudiant les propriétés des extensions génériques de modèles non standards ainsi que les avantages de cette interprétation par rapport aux approches axiomatiques.

L'essentiel

Le Grand Jeu du Hasard : Comment "Inventer" des Nombres avec la Théorie des Ensembles

Imaginez que vous êtes un architecte qui construit des maisons (des modèles mathématiques). Habituellement, vous travaillez avec des règles strictes et des matériaux connus. Mais parfois, vous voulez construire une maison avec une pièce secrète, un nouvel étage que personne n'avait jamais vu auparavant. C'est ce que fait cet article : il explique comment ajouter de nouveaux "nombres" à un monde mathématique existant en utilisant le hasard.

1. Le Contexte : Deux Mondes qui se Rencontrent

L'auteur relie deux mondes qui semblent très différents :

• L'Arithmétique Bornée (le monde des petits nombres) : C'est comme un atelier de menuiserie très strict où l'on ne peut utiliser que des outils simples et des règles limitées. On y étudie la complexité des preuves mathématiques (est-ce qu'on peut prouver une chose rapidement ?).
• La Théorie des Ensembles (le monde infini) : C'est comme un univers cosmique infini où l'on peut manipuler des dimensions et des probabilités gigantesques.

L'article dit : "Et si on utilisait les outils puissants de l'univers infini pour réparer ou modifier l'atelier de menuiserie ?"

2. L'Analogie du "Hasard" (Forcing)

En mathématiques, le "forcing" (forçage) est une technique pour ajouter de nouveaux éléments à un système sans casser ses règles.

• L'analogie du dé : Imaginez que vous avez un dé à 6 faces (un nombre standard). Vous voulez ajouter un nouveau nombre à votre jeu, mais vous ne savez pas lequel. Vous lancez le dé des milliards de fois. Le résultat de ce lancer infini crée un "nouveau nombre" qui n'existait pas avant.
• L'article de Krajíček (l'ancien travail) : Un mathématicien nommé Krajíček avait déjà inventé une méthode pour ajouter de tels "nombres aléatoires" dans l'atelier de menuiserie (l'arithmétique). Mais sa méthode était très technique, comme une recette de cuisine écrite dans une langue obscure.
• La découverte de Honzik : L'auteur de cet article dit : "Attendez, cette recette obscure est en fait exactement la même chose que de lancer un dé dans l'univers infini !". Il montre que la méthode de Krajíček est isomorphe (identique dans sa structure) à une technique célèbre en théorie des ensembles appelée l'algèbre de probabilité.

3. L'Idée Maîtresse : Le "Nombre Aléatoire"

L'article explique comment, en utilisant un modèle mathématique "saturé" (un modèle qui contient déjà une infinité de nombres, même des nombres "étranges" ou non standards), on peut utiliser le hasard pour insérer un nouveau nombre entier entre deux nombres existants.

• L'analogie du couloir : Imaginez un couloir infini rempli de portes (les nombres). Entre chaque porte, il y a un espace.
  • Dans la vie normale, vous ne pouvez pas mettre de nouvelle porte entre deux portes existantes sans tout casser.
  • Avec la méthode de l'article, on utilise une "poussière de hasard" (une mesure de probabilité) pour créer une nouvelle porte flottante, un nombre aléatoire, qui se glisse parfaitement entre deux portes existantes.
  • Ce nouveau nombre n'est ni trop grand, ni trop petit, il est juste "au milieu" de l'inconnu.

4. Pourquoi est-ce important ?

Pourquoi s'embêter à inventer des nombres avec du hasard ?

• Le test de résistance : En informatique et en logique, on veut savoir si certaines affirmations sont "vraies" ou "fausses" de manière absolue, ou si cela dépend de la façon dont on regarde les choses.
• L'analogie du test de stress : En ajoutant ce "nombre aléatoire", on teste la solidité des règles de l'arithmétique. Si l'on peut construire un monde où une règle est vraie et un autre où elle est fausse (grâce à ce nombre), alors cette règle n'est pas une vérité absolue.
• Le lien avec la complexité : Cela aide à comprendre pourquoi certains problèmes informatiques sont si difficiles à résoudre. Si l'on peut prouver qu'un problème nécessite une "longueur de preuve" énorme, cela signifie qu'il est intrinsèquement difficile.

5. La Conclusion : Une Nouvelle Perspective

L'auteur conclut en disant que cette approche change la façon de voir les mathématiques :

• Au lieu de construire des outils de force spécifiques pour chaque petit problème (l'arithmétique), on peut utiliser les "super-outils" de l'univers infini (la théorie des ensembles).
• C'est comme si, pour réparer une montre, on utilisait les principes de l'ingénierie spatiale. Cela semble exagéré, mais cela révèle des structures cachées que l'on ne voyait pas en regardant seulement la montre.

En résumé :
Cet article est un pont entre deux mondes. Il montre que la méthode complexe pour ajouter des "nombres génériques" dans les mathématiques limitées est en fait une version miniature d'un jeu de hasard géant joué dans l'univers infini. Cela nous aide à mieux comprendre la structure des nombres, la difficulté des problèmes informatiques et la nature même de la vérité mathématique.

Résumé technique

Voici un résumé technique détaillé de l'article "Forcing with Random Variables in Bounded Arithmetics and Set Theory" de Radek Honzik.

1. Problématique et Contexte

L'article s'attaque à la compréhension structurelle du forçage de Krajíček (développé dans [19]), une méthode utilisée en arithmétique bornée (théories faibles de l'arithmétique) pour prouver l'indépendance de certaines affirmations et établir des bornes inférieures sur la complexité des preuves de tautologies propositionnelles.

• Le problème : Le forçage de Krajíček est le seul exemple connu de forçage en arithmétique bornée qui ajoute des entiers "génériques" (non standards) à un modèle. Cependant, sa construction repose sur des mesures de Loeb et des variables aléatoires dans un cadre non standard, ce qui le rend difficile à comparer directement avec les techniques de forçage classiques de la théorie des ensembles.
• L'objectif : L'auteur vise à réinterpréter le forçage de Krajíček sous l'angle du forçage en théorie des ensembles. L'objectif est de montrer que cette construction n'est pas isolée, mais qu'elle est isomorphe à un forçage probabiliste standard (l'algèbre de probabilité $B_{\omega_1}$), permettant ainsi d'utiliser les outils puissants de la théorie des ensembles pour analyser la structure des modèles génériques d'arithmétique bornée.

2. Méthodologie

L'auteur adopte une approche hybride combinant l'analyse non standard, la théorie des mesures et la théorie du forçage :

1. Cadre de travail : L'étude se déroule dans un modèle transitif dénombrable de la théorie des ensembles $V$. On considère un modèle $M$ d'arithmétique vraie (vrai modèle de l'arithmétique de Peano) qui est $\omega_1$-saturé et de cardinalité $\omega_1$. On suppose également l'Hypothèse du Continu (CH) pour simplifier les cardinalités.
2. Identification de l'algèbre de forçage :
   • L'auteur examine l'algèbre de probabilité $B_{M,\Omega}$ utilisée par Krajíček, construite à partir d'un nombre non standard $\Omega \in M$ et de la mesure de Loeb (ou une mesure de comptage standardisée sur les sous-ensembles finis de $M$ de $\Omega$).
   • En utilisant le théorème de Maharam (qui classe les algèbres de probabilité homogènes), l'auteur démontre que $B_{M,\Omega}$ est isomorphe à l'algèbre de probabilité standard $B_{\omega_1}$, générée par l'espace produit $2^{\omega_1}$ muni de la mesure produit.
3. Construction des extensions génériques :
   • Au lieu de travailler uniquement avec des modèles à valeurs booléennes (comme dans [19]), l'auteur définit des extensions génériques à deux valeurs $M[G]_R$ dans l'univers forcé $V[G]$.
   • Ces modèles sont déterminés par un filtre générique $G$ et un ensemble $R$ de variables aléatoires (fonctions $\alpha : \Omega \to M$ appartenant à $M$).
   • L'ensemble $R$ agit comme une contrainte de complexité computationnelle : selon le choix de $R$, on obtient différents sous-modèles de l'extension maximale.

3. Contributions Clés et Résultats Principaux

A. Isomorphisme avec le Forçage Standard (Théorème 5.13)

Le résultat central est que, sous l'hypothèse que $M$ est un modèle $\omega_1$-saturé de taille $\omega_1$, l'algèbre de forçage de Krajíček $B_{M,\Omega}$ est isomorphe en tant qu'algèbre de mesure à $B_{\omega_1}$.

• Implication : Le forçage de Krajíček est équivalent au forçage standard qui ajoute $\omega_1$ réels aléatoires. Cela place le forçage en arithmétique bornée dans le cadre bien étudié du forçage probabiliste en théorie des ensembles.
• Différence avec Scott : Alors que Scott [28] utilisait $B_{\omega_2}$ pour ajouter $\omega_2$ réels (pour réfuter l'Hypothèse du Continu), Krajíček utilise une structure isomorphe à $B_{\omega_1}$ pour ajouter un "entier aléatoire" non standard.

B. Structure des Modèles Génériques $M[G]_R$

L'article analyse la relation entre l'ordre linéaire du modèle de base $(M, <)$ et son extension $(M[G]_R, <)$.

• L'entier aléatoire ($id_G$) : Si l'ensemble $R$ contient la fonction identité $id : \Omega \to \Omega$, alors l'élément générique $id_G$ génère toute l'extension. $id_G$ est un "entier aléatoire" inséré dans le modèle.
• Densité mutuelle (Théorèmes 5.24 et 5.27) :
  • Nouveaux entiers denses : Si $R$ contient des variables appropriées, de nouveaux entiers sont ajoutés de manière dense entre n'importe quels deux entiers de $M$ dont la distance externe est infinie.
  • Densité de $M$ : La densité de $M$ dans $M[G]_R$ dépend de la nature des variables aléatoires. Si une variable est "bornée" par un ensemble de mesure nulle, elle peut créer des intervalles vides d'entiers de $M$. Si elle est "non bornée", elle crée des intervalles autour d'elle contenant aucun entier de $M$.
• Modèle Maximal : Il existe un modèle maximal $M[G]_{R_{max}}$ correspondant à l'ensemble de toutes les variables aléatoires possibles. Tous les autres modèles $M[G]_R$ sont des sous-structures de ce modèle maximal et satisfont les mêmes formules quantifier-free.

C. Approche Alternative au Forçage Axiomatique

L'article propose une alternative à l'approche axiomatique de Atserias et Müller [2].

• Au lieu de définir un cadre de forçage spécifique pour les théories faibles, l'auteur propose d'immerger le modèle d'arithmétique $M$ dans un modèle de théorie des ensembles $V$, d'appliquer le forçage standard, et d'étudier les propriétés de l'extension $M[G]$.
• Cette méthode permet de transférer des résultats profonds de la théorie des ensembles (comme les propriétés de l'algèbre $B_{\omega_1}$) vers l'arithmétique bornée.

4. Signification et Impact

• Unification conceptuelle : L'article brise la barrière entre le forçage en arithmétique bornée et le forçage en théorie des ensembles. Il montre que les constructions complexes de Krajíček sont, au niveau de l'algèbre de forçage, des objets standards.
• Nouvelles perspectives structurelles : En analysant la densité mutuelle entre $M$ et $M[G]_R$, l'article fournit des insights sur la géométrie des modèles non standards générés par le forçage, ce qui est crucial pour comprendre la complexité des preuves dans ces théories.
• Limites et Avenir : L'auteur note que cette approche ne produit pas directement de nouveaux théorèmes d'indépendance (les résultats de Krajíček restent valables), mais elle offre un cadre plus robuste pour les analyser. Elle suggère que d'autres notions de forçage en théorie des ensembles pourraient être adaptées à l'arithmétique bornée si l'on parvient à trouver les lemmes combinatoires appropriés (comme les "switching lemmas").

En résumé, Radek Honzik démontre que le forçage de Krajíček n'est pas un artefact isolé de l'arithmétique bornée, mais une manifestation spécifique du forçage probabiliste sur $2^{\omega_1}$, offrant ainsi une nouvelle grille de lecture puissante pour l'étude des modèles génériques et de la complexité computationnelle.