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. 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 dénombrables équivalents d'une théorie logique sont isomorphes. Elle permet de démontrer que le 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 récursivement énumérables sont récursivement isomorphes. On 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.