Méthode du va-et-vient

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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[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 :

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

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[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]

  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é[modifier | modifier le code]