Accueil🇫🇷Chercher

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.

Utilisations

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

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. 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

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

  1. « 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. »
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Back-and-forth method » (voir la liste des auteurs).

Article lié

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.