Question de vocabulaire sur les univers

Cyrano

Bonjour
Lorsqu'on parle de l'univers (de Von Neumann) des ensembles $V$, je comprends les choses de la façon suivante. On se donne une théorie formelle syntaxique pure, à savoir ZFC. Puis on fait un acte de foi : il existe au moins un modèle de cette théorie. Ensuite, on se fixe un tel modèle, disons $M$ et au sein de $M$ on construit la hiérarchie menant à $V$. Pareillement après on peut construire celle menant à $L$. On peut ensuite refaire pareil dans n'importe quel modèle $M$ de ZFC. Ainsi chaque $M$ aura son $V$ et son $L$. Dans certains $M$, le $V$ est égal au $L$ et dans certains autres $M$, le $V$ n'est pas égal au $L$. Right ?

Cependant en lisant des interventions de théoriciens des ensembles, sur mathoverflow notamment, je constate que certains raisonnent différemment. Ils considèrent un $V$ "absolu" a priori et considèrent que tous les modèles $M$ de ZFC sont des ensembles de cet univers $V$. Autrement dit, pour eux le $V$ vient en premier et les modèles ensuite. 
Et c'est vrai que je peux comprendre la tentation d'envisager les choses de cette façon. Dans mon premier paragraphe, je considère les modèles $M$ en premier. Ces modèles sont des ensembles au sens de la méta-théorie, que je laisse volontairement floue. À aucun moment je ne considère de méta-univers contenant tous les méta-ensembles. Est-ce que cela pose réellement un problème ? Peut-on faire toute la théorie des ensembles (jusqu'aux résultats les plus poussés) sans considérer de $V$ "absolu" mais simplement en affirmant que chaque modèle $M$ a son $V$ interne ? 

Foys

Cyrano a dit :

Bonjour
Lorsqu'on parle de l'univers (de Von Neumann) des ensembles $V$, je comprends les choses de la façon suivante. On se donne une théorie formelle syntaxique pure, à savoir ZFC. Puis on fait un acte de foi : il existe au moins un modèle de cette théorie.

 C'est le contraire : il est déclaré dans les hypothèses (si on s'exprime ainsi en l'invoquant) et donc on montre des propriétés valables dans tous les univers de ce type (même s'il en existe aucun). Il ne faut pas oublier que l'écriture de toute théorie mathématique consiste en fait en un procès à charge contre ses axiomes (un théorème de ZF, disons "$A$" et la même chose qu'un théorème de logique de la forme $\neg X_1 \vee \neg X_2 \vee \dots \neg X_n \vee A$ où les $X_i$ sont pris parmi les axiomes de ZF autrement dit on exhibe la possibilité de la fausseté de l'un des $X_i$ si celle de $A$ est constatée).

L'invocation de modèles est un artifice langagier commode. L'intuition est donnée par ce qui se passe en forcing (en fait juste avant la construction du forcing). On a les méta résultats suivants (qui ne font référence à aucune notion de modèle) :

Définition : soit $C$ une formule dont (mettons) $t$ est la seule variable libre. Soit $F$ une formule dont les variables libres sont distinctes de $C$. On définit $\{t \mid C\}\vDash F$ par induction en posant :

$\{t \mid C\} \vDash x \Box y := x \Box y$ (avec $\Box$ qui est $\in$ ou $=$)

$\{t \mid C\} \vDash  (F,G):= nand ((\{t \mid C\} \vDash F), (\{t \mid C\} \vDash G)) $

 $\{t \mid C\} \vDash \exists y H :=  \exists y (y \in \{t \mid C\} \wedge \{t \mid C\} \vDash H)$ ($y$ étant non libre dans $C$; la graphie "$y \in \{ t \mid C\}$ abrégeant $C[t:=y]$")

Soit $u$ un ensemble et $F$ une formule (ne contenant pas la lettre $u$ ni la lettre $w\neq u$ comme variable libre): on note $u\vDash F:= \{w \mid w \in u\} \vDash F$.

On a les (méta) résultats suivants dans ZFC.

1°) ("princlpe" de réflexion de Montague). Soit $\Phi$ un énoncé sans variables libres. On a le théorème suivant: Pour tout ordinal $\alpha$, il existe un ordinal limite $\beta>\alpha$ tel que $\Phi \Leftrightarrow (V_{\beta} \vDash \Phi) $ (on dit que $V_{\beta}$ "reflète" $\Phi$).

Voir un livre de théorie des ensembles (ex : Krivine, Jech etc).

Ceci va permettre d'assimiler des $V_{\alpha}$ à des "modèles" de ZFC (je mets des guillemets à modèle pour une raison technique subtile à détailler plus tard) grâce à l'artifice suivant :

soit $M$ une lettre et $\mathcal T$ la théorie constituée de tous les axiomes de ZFC et aussi de tous les énoncés de la forme $M\vDash F$ où $F$ est un axiome de ZFC. Soit $G$ une formule où $M$ n'est pas libre. Si $G$ est un théorème de $\mathcal T$ alors $G$ est un théorème de ZFC; en effet $G$ étant un théorème de $\mathcal T$ il existe (syntaxiquement) des axiomes $X_1,\dots ,X_d, Y_1,\dots ,Y_e$ de ZFC tels que $(X_1 \wedge \dots \wedge X_d \wedge (M \vDash Y_1) \wedge \dots \wedge(M \vDash Y_e)) \Rightarrow G$ est un théorème de logique. Soit $\alpha>0$ un ordinal tel que $V_{\alpha}$ reflète $Y_1 \wedge \dots \wedge Y_e$. Alors en remplaçant $M$ par $V_{\alpha}$ dans la formule précédente on obtient que $(X_1 \wedge \dots \wedge X_d \wedge (V_{\alpha} \vDash Y_1) \wedge \dots\wedge (V_{\alpha} \vDash Y_e)) \Rightarrow G$ est encore un théorème de logique cependant par le principe de réflexion, chacun des $V_{\alpha} \vdash Y_i$ est un théorème de ZFC et donc $G$ aussi.

Ceci entraîne l'équiconsistance de $\mathcal T$ et de ZFC (prendre $G:= \perp$)

On peut également rajouter parmi les axiomes de $\mathcal T$:

-$M$ est transitif ($V_{\alpha}$ l'est)

-$M$ est dénombrable (!!! mais voir le théorème de Lowenheim-Skolem).

Bref on peut se permettre de rajouter à la volée des ensembles qui satisfont tous les axiomes de ZFC et les voir comme des "univers".
Mais tout est syntaxique; ça reste une vue de l'esprit.

Cyrano

Je comprends l'idée que la théorie des modèles peut se ramener à un jeu syntaxique. Ma question concerne l'ordre dans lequel on fait les choses.

- Commence-t-on par postuler l'existence d'un univers $V$ dans la métalangue auquel "tout" appartient ? Ainsi n'importe quel ensemble $M$ servant de modèle pour n'importe quelle théorie est tel que $M \in V.$ (Avec l'appartenance au sens méta également.)

- Ou bien commence-t-on par des ensembles "naïfs" dont on ne précisera pas "où ils vivent". Via ces ensembles naïfs, on définit les $M$ (et plein d'autres choses) et au sein de chaque $M$ on a un $V^M$ tel que $V^M \subset M.$

J'ai toujours cru que c'était la seconde vision qui était la plus classique.

Georges Abitbol

@Cyrano : Je ne comprends pas ta question sur le fait de "postuler un univers $V$". Quand on écrit "soit $G$ un groupe, blablabla", on ne veut pas dire "il existe $G$ tel que $G$ groupe et blablabla" mais "pour tout groupe $G$, blablabla". N'est-ce pas pareil ici ? Ou alors j'ai rien compris du tout ?

Cyrano

Sauf que dans l'option numéro $1$, on ne peut pas dire "quelque soit l'univers $V$" puisque cette notion d'univers n'est même pas réellement définie. Tu pourrais dire que c'est un truc qui vérifie ZFC, mais alors dans le fond tu parles d'un modèle de ZFC et autant considérer l'option numéro $2$. 

Georges Abitbol

Ben moi je dirais qu'on dit simplement "soit $(V,\epsilon)$ un modèle de ZFC" en se disant qu'on parle peut-être de rien.

Foys

Rien n'oblige les gens à parler d'univers a priori. C'est juste langagièrement plus commode que de traîner des considérations syntaxiques (les livres "introduction to axiomatic set theory" de Takeuti et Zaring ou "basic set theory" d'Azriel Levy le font et règlent ce problème  aux prix d'une lecture pénible).

Le point de vue 1 avec l'univers absolu est au fond celui de NBG (la théorie démontre l'existence de $V$ et a un nombre fini d'axiomes ce qui permet de faire passer pas mal de méta dans la théorie elle-même ce qui est quand même plus propre).

Comme il est gratuit (en termes de risques supplémentaires d'inconsistance) d'ajouter des ensembles qui satisfont tout ce qu'on veut (cf mon post) y compris la validation de tout ZFC, le point de vue 1 valide un peu le point de vue 2.

Cyrano

D'accord je comprends mieux. Le truc qui me dérange aussi avec l'univers absolu, c'est que je vois difficilement comment construire une extension $V[G]$ pour le forcing. En effet, par définition, il n'y a "rien en dehors" de ce $V$. Par contre il est possible de construire $M[G]$ à partir d'un modèle $M$ de ZFC.

Foys

Je dirais qu'on a tort de voir de véritables engagements philosophiques dans ces points de vue. Les théorèmes de complétude et d'incomplétude apportent des réponses techniques à cette problématique.

Digression : le théorème de complétude ne requiert pas toute la force de la théorie des ensembles. Ce que suppose le théorème de complétude de la logique du premier ordre est mieux connu avec les mathématiques à rebours ("reverse mathematics"): sous "RCA0" (un ensemble d'axiomes d'arithmétique du second ordre minimal pour décrire toutes les opérations informatiques en ignorant les problèmes de complexité algorithmique et de finitude des limites concrètes des ordinateurs physiques), le théorème de complétude est équivalent au lemme de König faible (qui est intuitif quoiqu'on dise même s'il exhibe des objets non informatiquement calculables quoique parfaitement déterminés).

RCA0 est un sous-système de l'arithmétique du second ordre (dans un tel système le mot ensemble ne signifie rien d'autre qu'une "partie de $\N$" - et pour RCA0 une telle partie est a priori de fonction caractéristique calculable- et les outils fournis pour manipuler cette notion sont réduits à presque rien et sont beaucoup moins engageants que ce qui est proposé en théorie des ensembles proprement dite). La liste exhaustive des axiomes d'arithmetique du second ordre permet de donner une démonstration intuitionniste du théorème de complétude (ce théorème est trouvable sur le site internet de Jean-Louis Krivine).

Le premier théorème de Gödel est simplement (pour la théorie des ensembles) un énoncé $X$ (concret) du langage de la théorie des ensembles tel que si $ZFC \vdash X$ alors $ZFC \vdash \{0,1\}$ et si $ZFC \vdash \neg X$ alors $ZFC \vdash \{0,1\}$.

Avec ces ingrédients on se retrouve dans l'une des situations suivantes:

I) RCA0 est contradictoire (et toutes les intuitions basiques de 99.999% des mathématiciens sur les nombres et les opérations arithmétiques élémentaires sont fausses)

II) le lemme de König est faux

III) ZF est contradictoire et il n'existe aucun modèle de cette théorie

IV) il existe plusieurs (beaucoup) de modèles de ZF et de ZFC.

Et dans la situation de IV) il y a forcément:

-des modèles de ZFC inclus les uns dans les autres

-des modèles de ZFC qui appartiennent à d'autres en tant qu'ensembles dénombrables (les bijections d'objets de ces modèles qui sont prouvablements non équipotents dans la théorie sont simplement en dehors dudit modèle mais existent dans le grand modèle ambiant).

-des modèles non standards variés.

Bref toute une jungle d'objets exotiques et non isomorphes entre eux.

Les modèles de ZFC ne doivent pas créer plus de malaise que disons les modèles de la théorie de groupes. Un modèle de théorie des groupes n'est rien d'autre qu'un groupe. Bah il y a plusieurs groupes différents, des groupes qui sont sous-groupes d'autre etc, et certainement pas un gros groupe absolu unique, cadre de toute la pensée sur les groupes. La "théorie des groupes" a pour vocation d'étudier tous les groupes, et non pas un groupe absolu, qui serait le récit-cadre fixé une fois pour toutes de ce qu'on voudrait comprendre d'une hypothétique loi de groupe universelle.

Maintenant il n'y a plus qu'à remplacer "groupe" par "univers ensembliste" dans ce qui précède.

L'incantation "soit $V$ un univers" démarrant un exposé de théorie des ensembles est du même niveau d'engagement philosophique que "soit $G$ un groupe" des livres d'algèbre.

Cyrano

Désolé pour cette non-réponse.
Ton post m'a été utile Foys et je continue d'explorer ces questions semi-philosophiques de mon côté. 

Plutôt que de créer un nouveau topic, je pose tout de suite une question reliée à la précédente. Soit $M$ un modèle de ZFC. Au sein de ce $M$ je construis $V_0, V_1, etc.$ puis tous les $V_{\alpha}$ où $\alpha$ est un ordinal. Quel est le statut exact de ce $\alpha$ apparaissant dans $V_{\alpha}$ ? Est-ce le $\alpha$ de $M$, qu'on pourrait noter $\alpha_M$ ou est-ce le $\alpha$ "ambiant" celui qui vient de la méta-théorie englobant $M$ ?

Foys

je construis 𝑉0,𝑉1,𝑒𝑡𝑐. puis tous les 𝑉𝛼 où 𝛼 est un ordinal. Quel est le statut exact de ce 𝛼 apparaissant dans 𝑉𝛼?

@Cyrano: réponse paragraphe 4°, l'argumentaire est dans les paragraphes précédents. Ce sont des résultats (un peu) techniques de théorie de la démonstsration.

Les notations sont celles de https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2409593/#Comment_2409593

 Un couple $\{t \mid F\}$ où $t$ est une variable et $F$ une formule s'appellera ci-dessous une classe.

Etant données deux classes $C:=\{t\mid F\}$ et $D:= \{t \mid D\}$, on dit que "$C$ est incluse dans $D$" (et on note "$C \subseteq D$") l'énoncé $\forall t C \Rightarrow D$. On appelle "variables libres" d'une classe $\{t\mid F\}$ les variables libres de $F$ différentes de $t$.

L'écriture étant données des lettres $A,u_1,...,u_n$, l'écriture "$A(u_1,...,u_n)$" veut dire que $A$ est une formule dont toutes les variables libres sont parmi les $u_1,....,u_n$.

Soient $C,D$ deux classes sans variables libres telles que $C\subseteq D$ et $F(y_1,...,y_d)$ une formule. Généralement, $y_1 \in C \wedge y_2 \in C \wedge ... \wedge y_d \in C $ n'entraîne pas que $C\vDash F$ et $D \vDash F$ sont équivalentes: $F$ définit des propriétés différentes des objets $y_1,...,y_d$ de $C$, selon qu'on interprète $F$ dans $C$ ou dans $D$. Mais ci-dessous, on va voir une condition suffisante commode qui entraîne cette équivalence pour des ensembles particuliers de formules.

1°) Soient à nouveau $C,D$ des classes dont les variables libres sont dans $p_1,...p_r$. On suppose $C\subseteq D$ dans tout le paragraphe.

Soit $\Phi$ un ensemble de formules (au sens intuitif) stable par sous-formules (pour toute $F\in\Phi$ et toute formule $G$, si $G$ est une sous-formule de $F$ alors $G\in \Phi$). On suppose en outre que pour toute $F(x_1,...,x_n,y)$ telle que $\exists y F \in\Phi$ (et donc $F\in \Phi$ aussi...), on peut prouver que $\forall x_1 \forall x_2...\forall x_n, (x_1 \in C \wedge ... \wedge x_n \in C) \Rightarrow (\exists y\in D, C\vDash F  \Rightarrow \exists y \in C, C\vDash F)$. Alors pour tout $G(y_1,...,y_m) \in \Phi$, on peut prouver: $\forall y_1 \forall y_2 ... \forall y_m, (y_1 \in C \wedge ... y_m \in C) \Rightarrow (C \vDash G \Leftrightarrow D \vDash G)$ ("test de Tarski-Vaught").

La preuve est plus courte que l'énoncé: il s'agit d'une simple récurrence sur la taille des formules, le seul cas délicat (du quantificateur existentiel) étant pris en charge par l'hypothèse.

Ce résultat se généralise en théorie des modèles. Lorsque $\Phi$ est l'ensemble de toutes les formules, on dit que $C$ est une sous-structure élémentaire de $D$.

2°) -On dit qu'une formule est à quantificateurs bornés si elle est obtenue par application successive des opérations suivantes: (i)$x\in y$, $x=y$ sont à quantificateurs bornés.(ii) Pour toutes formules $F,G$ à quantificateurs bornés, $nand(F,G)$ est à quantificateurs bornés. (iii) pour toute formule $H$ à quantificateurs bornés et toutes lettres $a,b$, $\exists a(a \in b \wedge H)$ est à quantificateurs bornés.

-On dit qu'une formule $F$ est $\Delta_0$ (ou parfois $\Sigma_0$ suivant les livres) s'il existe une formule $F'$ à quantificateurs bornés logiquement équivalente (équivalente sans hypothèses) à $F$. Par exemple, si $K$ est $\Delta_0$ et si $a,b$ sont des lettres, $\forall a, a\in b \Rightarrow K$ est $\Delta_0$ (équivalente à $\neg \exists a (a \in b \wedge \neg K)$).

Il est clair que l'ensemble des formules à quantifications bornées est stable par sous formules. On a alors le résultat suivant avec $C,D$ classes telles que $C \subseteq D$.

-On suppose que pour tous $x,y\in D$, si $x\in y$ et $y\in C$ alors $x\in C$. Alors pour toute formule à quantifications bornées $F$ (et donc par équivalence, toute formule $\Delta_0$), on a $C \vDash F$ si et seulement si $D \vDash F$.

La preuve est immédiate par le théorème du paragraphe précédent.

3°) L'univers est lui-même une classe (si on note $V:= \{x \mid x=x\}$, on voit que $F \Leftrightarrow V\vDash F$ pour tout $F$).

Une classe $C$ telle que pour tous $x,y$, si $y\in C$ et $x\in y$ alors $x\in C$ s'appelle une "classe transitive". Pour de telles classes, le résultat de 2°) s'applique et on a donc pour toute propriété $F(x)$ qui est $\Delta_0$ et pour tout $t \in C$, $t$ vérifie $F$ si et seulement si il vérifie $F$ interprétée dans $C$, autrement dit $C\vDash F$.

On dit qu'un ensemble $M$ est transitif si la classe $\{u\mid u \in M\}$ est transitive.

4°) Dans ZF (avec axiome de fondation), le fait d'être un ordinal est équivalent à un énoncé $\Delta_0$ 

En effet un ensemble $x$ est un ordinal si et seulement si il est transitif et si la relation $a,b \mapsto a\in b$ est un ordre total strict sur $x$.

Cette propriété est facilement $\Delta_0$.

Par conséquent, pour toute classe transitive $C$ qui satisfait tous les axiome de $ZF$, les ordinaux de $C$ sont exactement les ordinaux de l'univers entier qui appartiennent à $C$.

5°) (ajout non indispensable) le test de Tarski-Vaught entraîne le théorème de Lowenheim-Skolem et (plus dur) le schéma de réflexion.

Cyrano

Si je comprends bien, tous les modèles de $ZF$ contiennent tous les ordinaux et ce sont les ordinaux de l'univers ambiant. 
Donc si on faisait "l'intersection" de tous les modèles de $ZF$, celle-ci contiendrait en particuliers tous les ordinaux. 

Foys

Cyrano a dit :

Si je comprends bien, tous les modèles de $ZF$ contiennent tous les ordinaux et ce sont les ordinaux de l'univers ambiant.

Non car par exemple $M \subseteq V$ peut être un modèle transitif dénombrable et alors les ordinaux de $M$ sont un ordinal dénombrable dans $V$. Mais un $x$ quelconque de $V$ est un ordinal de $M$ si et seulement si c'est un ordinal de $V$ et si $x\in M$.

De plus on ne peut pas oublier l'hypothèse de transitivité dans ce que j'ai dit plus haut.

Cyrano

Hum je vois bien la difficulté, c'est là que la cervelle commence à chauffer.
Soit donc $M$ un modèle dénombrable de ZF. Je peux donc y faire toutes les constructions classiques qui résultent des axiomes de ZF. Donc $M$ possède son $\omega_1$ disons $\omega_1^M$. Mais du coup tu sembles dire que depuis $V$ ce $\omega_1^M$ est vu comme un ordinal dénombrable. Donc il existerait au sein de $M$ une bijection entre $\omega_1^M$ et un ordinal dénombrable qui, lui pour le coup, est vu comme dénombrable par $M$ et par $V$. Est-ce à peu près ça ? 

Foys

Justement cette bijection entre $\omega_1^M$ et $\omega$ n'est pas dans $M$ mais en dehors. Il existe un certain nombre de propriétés $\Delta_0$ qui se comportent bien du coup, quand on manie des modèles transitifs. Mais il en existe deux remarquables qui ne le sont pas et qui ont un comportement pathologique:

-$y = \mathcal P(x)$ et plus généralement $c = a^b$

-"$x$ et $y$ sont en bijection".

$\N$ est le même dans $M$ et dans $V$ ($\N$ est défini par une propriété $\Delta_0$);

-tous les ensembles infinis de $M$ sont dénombrables (et donc en bijection, avec des bijections appartenant à $V \backslash M$) 

-$\mathcal P(\N)^M$ est dénombrable.

Cyrano

Oui ok, c'est compris, merci.

J'ai toujours voulu éviter de m'attaquer aux $\Delta_0, \Sigma_0, \Pi_0$ ainsi qu'à leurs généralisations car les histoires de complexité de formules et de combinatoire sur les quantificateurs me semblent atrocement lourdes. Mais je vois bien que ça devient vite inévitable.