Méthode du 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
modifierOn fixe un langage et on considère deux -structures et de domaines respectivement et . On appelle isomorphisme partiel entre et tout isomorphisme entre deux sous--structures de et de . Ainsi, on dit alors qu'une famille non vide d'isomorphismes partiels entre et est un va-et-vient si les deux propriétés suivantes sont vérifiées :
- (VA)
- (VIENT)
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
modifierLa 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
modifierOn considère deux ensembles ordonnés denses et 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 et :
- et
et on construit une bijection strictement croissante entre et en associant progressivement des éléments de à et de à . Au départ, aucun élément de n'est associé à un élément de .
(1) Soit le plus petit indice tel que n'est pas associé à un élément de , et soit un indice tel que n'est pas associé à un élément de et tel que peut être associé à de sorte que la correspondance est strictement croissante. Alors on associe et .
(2) Soit le plus petit indice tel que n'est pas associé à un élément de , et soit un indice tel que n'est pas associé à un élément de et tel que peut être associé à de sorte que la correspondance est strictement croissante. Alors on associe et .
(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 et de , en correspondance avec des éléments et de respectivement, tels et , on choisit entre et , ce qui est possible par la propriété de densité. Sinon, on choisit un élément quelconque de assez grand ou assez petit, ce qui est possible parce que 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 et sont dénombrables.
Note historique
modifierQuant à 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- « Les méthodes de va-et-vient sont souvent attribuées à Cantor, Bertrand Russell et C. H. Langford (en) [...], mais rien ne permet de soutenir une de ces attributions. »
- Edward Vermilye Huntington, The continuum and other types of serial order, with an introduction to Cantor's transfinite numbers, Harvard University Press, (lire en ligne)
- Felix Hausdorff, Grundzüge der Mengenlehre, Leipzig, Veit & Comp., (lire en ligne)
- Wilfrid Hodges, Model theory, Cambridge University Press, , 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 », , 345 p. (ISBN 978-0-387-98760-6, lire en ligne)