Método de ida y vuelta

En lógica matemática , especialmente en teoría de conjuntos y teoría de modelos , el método de ida y vuelta es un método para demostrar el isomorfismo entre estructuras infinitamente numerables que satisfacen condiciones específicas. En particular, se puede utilizar para demostrar que:

• Dos conjuntos infinitamente numerables y densamente ordenados (es decir, ordenados linealmente de tal manera que entre dos elementos cualesquiera existe otro) sin extremos son isomorfos. Un isomorfismo entre órdenes lineales es simplemente una biyección estrictamente creciente . Este resultado implica, por ejemplo, que existe una biyección estrictamente creciente entre el conjunto de todos los números racionales y el conjunto de todos los números algebraicos reales .
• Dos álgebras booleanas sin átomos cualesquiera, con un número infinito numerable de elementos, son isomorfas entre sí.
• Dos modelos atómicos numerables equivalentes cualesquiera de una teoría son isomorfos.
• El modelo de Erdős-Rényi de grafos aleatorios , cuando se aplica a grafos infinitos numerables, produce casi con seguridad un grafo único, el grafo de Rado .
• Dos conjuntos cualesquiera multi-completos recursivamente enumerables son recursivamente isomorfos.

Establecemos un idioma${\displaystyle {\mathcal {L}}}$y consideramos dos${\displaystyle {\mathcal {L}}}$- estructuras${\displaystyle {\mathcal {M}}}$y${\displaystyle {\mathcal {N}}}$de dominios respectivamente${\displaystyle M}$y${\displaystyle N}$.

Llamamos isomorfismo parcial entre${\displaystyle {\mathcal {M}}}$y${\displaystyle {\mathcal {N}}}$cualquier isomorfismo entre dos${\displaystyle {\mathcal {L}}}$- subestructuras de${\displaystyle {\mathcal {M}}}$y${\displaystyle {\mathcal {N}}}$.

Una familia no vacía${\displaystyle {\mathcal {I}}}$de isomorfismos parciales entre${\displaystyle {\mathcal {M}}}$y${\displaystyle {\mathcal {N}}}$Se denomina vaivén si se cumplen las dos propiedades siguientes:

• (ADELANTE)${\displaystyle \forall \sigma \in {\mathcal {I}}\;\;\forall c\in M\;\;\exists \sigma '\in {\mathcal {I}}\;{\bigl (}\sigma \subseteq \sigma '\;\land \;c\in \mathrm {dom} (\sigma '){\bigr )}}$

• (ATRÁS)${\displaystyle \forall \sigma \in {\mathcal {I}}\;\;\forall d\in N\;\;\exists \sigma '\in {\mathcal {I}}\;{\bigl (}\sigma \subseteq \sigma '\;\land \;d\in \mathrm {im} (\sigma '){\bigr )}}$

En otras palabras, cada isomorfismo parcial de la familia admite una extensión que pertenece a la misma familia. Además, se puede encontrar dicha extensión con mayor precisión para cada isomorfismo parcial, imponiendo qué nuevo elemento debe pertenecer al dominio de la extensión o a su imagen (codominio).

Como ejemplo, el método de ida y vuelta puede utilizarse para demostrar el teorema de isomorfismo de Cantor , aunque esta no fue la demostración original de Georg Cantor . Este teorema establece que dos órdenes lineales densos, numerables e ilimitados son isomorfos. ^{[ 1 ]}

Supongamos que

• ( A , ≤ _A ) y ( B , ≤ _B ) son conjuntos ordenados linealmente;
• Ambos son ilimitados, es decir, ni A ni B tienen un máximo ni un mínimo;
• Están densamente ordenados, es decir, entre dos miembros cualesquiera hay otro;
• Son infinitos numerables.

Corrija las enumeraciones (sin repetición) de los conjuntos subyacentes:

A = { a ₁ , a ₂ , a ₃ , ... },

B = { b ₁ , b ₂ , b ₃ , ... }.

Ahora construimos una correspondencia uno a uno entre A y B que es estrictamente creciente. Inicialmente, ningún miembro de A está emparejado con ningún miembro de B.

(1) Sea i el índice más pequeño tal que a _i aún no está emparejado con ningún miembro de B. Sea j algún índice tal que b _j aún no está emparejado con ningún miembro de A y a _i puede emparejarse con b _j de manera consistente con el requisito de que el emparejamiento sea estrictamente creciente. Empareja a _i con b _j .

(2) Sea j el índice más pequeño tal que b _j aún no está emparejado con ningún miembro de A. Sea i algún índice tal que a _i aún no está emparejado con ningún miembro de B y b _j puede emparejarse con a _i de manera consistente con el requisito de que el emparejamiento sea estrictamente creciente. Empareja b _j con a _i .

(3) Vuelva al paso (1) .

Aún es necesario comprobar que la elección requerida en los pasos (1) y (2) se pueda realizar de acuerdo con los requisitos. Tomando el paso (1) como ejemplo:

Si ya existen en A un elemento _p y un elemento _q que corresponden respectivamente a b _p y b _q en B, tales que a _p < a _i < a _q y b _p < b _q , elegimos b _j entre b _p y b _q usando la densidad. De lo contrario, elegimos un elemento grande o pequeño adecuado de B usando el hecho de que B no tiene ni máximo ni mínimo. Las elecciones hechas en el paso (2) son dualmente posibles. Finalmente, la construcción termina después de un número numerable de pasos porque A y B son numerablemente infinitos. Nótese que tuvimos que usar todos los prerrequisitos.

Según Hodges (1993):

Los métodos de ida y vuelta suelen atribuirse a Cantor , Bertrand Russell y CH Langford [...], pero no hay pruebas que respalden ninguna de estas atribuciones.

Si bien el teorema sobre conjuntos numerables densamente ordenados se debe a Cantor (1895), el método de ida y vuelta con el que se demuestra actualmente fue desarrollado por Edward Vermilye Huntington (1904) y Felix Hausdorff (1914). Posteriormente, se aplicó en otras situaciones, sobre todo por Roland Fraïssé en la teoría de modelos .

• Juego de Ehrenfeucht-Fraïssé

• Hausdorff, F. (1914), Grundzüge der Mengenlehre
• Hodges, Wilfrid (1993), Teoría de modelos , Cambridge University Press , ISBN 978-0-521-30442-9
• Huntington, EV (1904), El continuo y otros tipos de orden serial, con una introducción a los números transfinitos de Cantor , Harvard University Press
• Marker, David (2002), Teoría de modelos: Una introducción , Textos de posgrado en matemáticas , Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-98760-6