Méthode du va-et-vient — Wikipédia

Pour les articles homonymes, voir Va et vient.

En logique mathématique, et particulièrement en théorie des ensembles et en théorie des modèles, la méthode du va-et-vient est une méthode pour démontrer l'isomorphisme entre des structures dénombrables vérifiant certaines conditions additionnelles.

Définition[modifier | modifier le code]

On fixe un langage ${\displaystyle {\mathcal {L}}}$ et on considère deux ${\displaystyle {\mathcal {L}}}$-structures ${\displaystyle {\mathcal {M}}}$ et ${\displaystyle {\mathcal {N}}}$ de domaines respectivement ${\displaystyle M}$ et ${\displaystyle N}$. On appelle isomorphisme partiel entre ${\displaystyle {\mathcal {M}}}$ et ${\displaystyle {\mathcal {N}}}$ tout isomorphisme entre deux sous-${\displaystyle {\mathcal {L}}}$-structures de ${\displaystyle {\mathcal {M}}}$ et de ${\displaystyle {\mathcal {N}}}$. Ainsi, on dit alors qu'une famille ${\displaystyle {\mathcal {I}}}$ non vide d'isomorphismes partiels entre ${\displaystyle {\mathcal {M}}}$ et ${\displaystyle {\mathcal {N}}}$ est un va-et-vient si les deux propriétés suivantes sont vérifiées :

• (VA) ${\displaystyle \forall \sigma \in {\mathcal {I}}\ \ \forall c\in M\ \ \exists \sigma '\in {\mathcal {I}}}$ ${\displaystyle \left(\ \sigma \subseteq \sigma '\ \land \ c\in \mathrm {dom} (\sigma ')\ \right)}$
• (VIENT) ${\displaystyle \forall \sigma \in {\mathcal {I}}\ \ \forall d\in N\ \ \exists \sigma '\in {\mathcal {I}}}$ ${\displaystyle \left(\ \sigma \subseteq \sigma '\ \land \ d\in \mathrm {im} (\sigma ')\ \right)}$

En d'autres termes, chaque isomorphisme partiel de la famille admet un prolongement, que l'on peut exhiber au sein même de la famille. Mais en plus, on peut également trouver de manière plus précise un tel prolongement pour chaque isomorphisme partiel, en imposant quel nouvel élément on souhaite qu'il appartienne au domaine du prolongement, ou à son image (codomaine).

Utilisations[modifier | modifier le code]

La méthode du va-et-vient s'applique à des ensembles dénombrables infinis ayant une certaine structure (au sens logique du terme). Elle permet de construire une bijection entre ces ensembles, bijection qui possède des propriétés de préservation de la structure, donc qui est un isomorphisme. Voici des exemples :

• La méthode peut être utilisée pour démontrer que deux ensembles ordonnés denses (c'est-à-dire totalement ordonnés et tels qu'entre deux éléments distincts, il existe toujours un troisième) dénombrables et sans éléments extrémaux sont isomorphes (un isomorphisme entre ensembles totalement ordonnés est une bijection strictement croissante). Ce résultat implique par exemple qu'il existe des bijections strictement croissantes entre l'ensemble des nombres rationnels et l'ensemble des nombres algébriques.
• Elle permet de démontrer que deux algèbres de Boole infinies dénombrables sans atomes sont isomorphes.
• Elle permet aussi de démontrer que deux modèles atomiques (en) dénombrables équivalents d'une théorie logique sont isomorphes.
• Elle permet de démontrer que le modèle d'Erdős-Rényi (en) des graphes aléatoires, appliqué à des graphes infinis dénombrables, produit toujours un graphe unique, le graphe de Rado.
• Elle permet de démontrer que deux ensembles m-complets (en) récursivement énumérables sont récursivement isomorphes.

Application aux ensembles ordonnés denses[modifier | modifier le code]

On considère deux ensembles ordonnés denses ${\displaystyle (A,\leq _{A})}$ et ${\displaystyle (B,\leq _{B})}$ dénombrables, et sans éléments extrémaux, c'est-à-dire sans éléments maximum ou minimum. On fixe une énumération des éléments de ${\displaystyle A}$ et ${\displaystyle B}$ :

${\displaystyle A=\{a_{1},a_{2},a_{3},\ldots \}}$ et ${\displaystyle B=\{b_{1},b_{2},b_{3},\ldots \}}$

et on construit une bijection strictement croissante entre ${\displaystyle A}$ et ${\displaystyle B}$ en associant progressivement des éléments de ${\displaystyle A}$ à ${\displaystyle B}$ et de ${\displaystyle B}$ à ${\displaystyle A}$. Au départ, aucun élément de ${\displaystyle A}$ n'est associé à un élément de ${\displaystyle B}$.

(1) Soit ${\displaystyle i}$ le plus petit indice tel que ${\displaystyle a_{i}}$ n'est pas associé à un élément de ${\displaystyle B}$, et soit ${\displaystyle j}$ un indice tel que ${\displaystyle b_{j}}$ n'est pas associé à un élément de ${\displaystyle A}$ et tel que ${\displaystyle a_{i}}$ peut être associé à ${\displaystyle b_{j}}$ de sorte que la correspondance est strictement croissante. Alors on associe ${\displaystyle a_{i}}$ et ${\displaystyle b_{j}}$.

(2) Soit ${\displaystyle j}$ le plus petit indice tel que ${\displaystyle b_{j}}$ n'est pas associé à un élément de ${\displaystyle A}$, et soit ${\displaystyle i}$ un indice tel que ${\displaystyle a_{i}}$ n'est pas associé à un élément de ${\displaystyle B}$ et tel que ${\displaystyle b_{j}}$ peut être associé à ${\displaystyle a_{i}}$ de sorte que la correspondance est strictement croissante. Alors on associe ${\displaystyle b_{j}}$ et ${\displaystyle a_{i}}$.

(3) On recommence en (1).

Il faut vérifier que les choix dans les étapes (1) et (2) peuvent être réalisés en respectant les conditions. Considérons une étape (1) : S'il existe des éléments ${\displaystyle a_{p}}$ et ${\displaystyle a_{q}}$ de ${\displaystyle A}$, en correspondance avec des éléments ${\displaystyle b_{p}}$ et ${\displaystyle b_{q}}$ de ${\displaystyle B}$ respectivement, tels ${\displaystyle a_{p}<a_{i}<a_{q}}$ et ${\displaystyle b_{p}<b_{q}}$, on choisit ${\displaystyle b_{j}}$ entre ${\displaystyle b_{p}}$ et ${\displaystyle b_{q}}$, ce qui est possible par la propriété de densité. Sinon, on choisit un élément quelconque de ${\displaystyle B}$ assez grand ou assez petit, ce qui est possible parce que ${\displaystyle B}$ n'a ni élément maximum ni élément minimum. Les choix faits dans l'étape (2) sont duaux des précédents. Enfin, la construction se termine après un nombre dénombrable d'étapes parce que les ensembles ${\displaystyle A}$ et ${\displaystyle B}$ sont dénombrables.

Note historique[modifier | modifier le code]

Quant à l'origine de la méthode, Hodges 1993:

« Back-and-forth methods are often ascribed to Cantor, Bertrand Russell and C. H. Langford (en) [...], but there is no evidence to support any of these attributions. »^[1]

Le théorème sur les ensembles ordonnés denses dénombrables appelé le « théorème de Cantor en théorie des ordres » est dû à Cantor (1895), la méthode de va-et-vient avec laquelle il est maintenant démontré a été développée par Huntington 1904 et Hausdorff 1914. Ultérieurement, elle a été appliquée par Roland Fraïssé en théorie des modèles.

Notes et références[modifier | modifier le code]

• Edward Vermilye Huntington, The continuum and other types of serial order, with an introduction to Cantor's transfinite numbers, Harvard University Press, 1904 (lire en ligne)
• Felix Hausdorff, Grundzüge der Mengenlehre, Leipzig, Veit & Comp., 1914 (lire en ligne)
• Wilfrid Hodges, Model theory, Cambridge University Press, 1993, 772 p. (ISBN 978-0-521-30442-9, lire en ligne)
• David Marker, Model Theory : An Introduction, Berlin, New York, Springer-Verlag, coll. « Graduate Texts in Mathematics », 2002, 345 p. (ISBN 978-0-387-98760-6, lire en ligne)

Article lié[modifier | modifier le code]

• Jeu d'Ehrenfeucht-Fraïssé

• Portail des mathématiques
• Portail de l'informatique théorique