En lógica matemática , especialmente teoría de conjuntos y teoría de modelos , el método de ida y vuelta es un método para mostrar isomorfismo entre estructuras infinitas contables que satisfacen condiciones específicas. En particular, se puede utilizar para demostrar que
- cualesquiera dos conjuntos numeradamente infinitos densamente ordenados (es decir, ordenados linealmente de tal manera que entre dos miembros cualesquiera haya otro) sin puntos finales 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 .
- cualesquiera dos álgebras booleanas sin átomo numerables infinitas son isomórficas entre sí.
- cualesquiera dos modelos atómicos contables equivalentes de una teoría son isomorfos.
- el modelo Erdős-Rényi de gráficos aleatorios , cuando se aplica a gráficos infinitos contables, siempre produce un gráfico único, el gráfico de Rado .
- cualesquiera dos conjuntos enumerables recursivamente muchos-completos son recursivamente isomórficos.
Aplicación a conjuntos densamente ordenados
Suponer que
- ( A , ≤ A ) y ( B , ≤ B ) son conjuntos ordenados linealmente;
- Ambos son ilimitados, en otras palabras, 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 contablemente infinitos.
Corrija enumeraciones (sin repetición) de los conjuntos subyacentes:
- A = { a 1 , a 2 , a 3 ,…},
- B = { b 1 , b 2 , b 3 ,…}.
Ahora construimos una correspondencia uno a uno entre A y B que es estrictamente creciente. Inicialmente ningún miembro de A se empareja con cualquier miembro de B .
- (1) Deja i ser el índice más pequeño de tal manera que un i todavía no está enlazado con cualquier miembro de B . Sea j un índice tal que b j aún no esté emparejado con ningún miembro de A y que a i pueda emparejarse con b j de manera consistente con el requisito de que el emparejamiento sea estrictamente creciente. Empareja a i con b j .
- (2) Let j ser el índice más pequeño de tal manera que b j aún no está emparejado con cualquier miembro de A . Sea i un índice tal que a i aún no esté emparejado con ningún miembro de B y b j pueda 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 debe comprobarse que la elección requerida en los pasos (1) y (2) se pueda realizar realmente de acuerdo con los requisitos. Usando el paso (1) como ejemplo:
Si ya hay una p y una q en A correspondientes a b p y b q en B respectivamente, de modo que a p < a i < a q y b p < b q , elegimos b j entre b p y b q usando densidad. De lo contrario, elegimos un elemento grande o pequeño adecuado de B utilizando el hecho de que B no tiene ni un máximo ni un mínimo. Las elecciones realizadas en el paso (2) son doblemente posibles. Finalmente, la construcción termina después de muchos pasos contables porque A y B son infinitos contablemente. Tenga en cuenta que tuvimos que utilizar todos los requisitos previos.
Historia
Según Hodges (1993):
- Los métodos de ida y vuelta a menudo se atribuyen a Cantor , Bertrand Russell y CH Langford […], pero no hay evidencia que respalde ninguna de estas atribuciones.
Mientras que el teorema de los conjuntos contables densamente ordenados se debe a Cantor (1895), el método de ida y vuelta con el que ahora se demuestra fue desarrollado por Huntington (1904) y Hausdorff (1914). Posteriormente se aplicó en otras situaciones, sobre todo por Roland Fraïssé en la teoría de modelos .
Ver también
Referencias
- 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
- Hausdorff, F. (1914), Grundzüge der Mengenlehre
- Hodges, Wilfrid (1993), teoría de modelos , Cambridge University Press , ISBN 978-0-521-30442-9
- Marker, David (2002), Model Theory: An Introduction , Textos de posgrado en matemáticas , Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-98760-6