Que los gráficos son elementarily equivalente a su propia discontinuo sumas?

Question

En Stefan Geschke reciente pregunta, una de las soluciones observa que la gráfica que consta de un único infinito de cuentas de la cadena, un $\mathbb{Z}$-cadena donde cada entero está conectado a su vecino más cercano, es elementarily equivalente a la inconexión suma de cualquier número de estas cadenas. Es decir, una sola cadena tiene la misma primer fin de propiedades en el lenguaje de la teoría de grafos como dos cadenas, o cualquier número de tales cadenas.

(La razón era que todos estos gráficos son de ciclo libre y tiene todos los elementos con grado de $2$, pero la teoría de la afirmar esto ya es completa. Esto puede ser visto por la observación de que cada modelo de esta teoría, tener innumerables tamaño de $\kappa$ se compone de $\kappa$ muchos $\mathbb{Z}$de las cadenas, y todos los modelos están isomorfo---en otras palabras, la teoría es $\kappa$-categórica---y de modo que la teoría es completa, ya que de lo contrario hubiera no isomorfos modelos de tamaño $\kappa$.)

Mi pregunta es acerca de la medida en que esta el fenómeno se generaliza a otros gráficos.

Pregunta. Que los gráficos de $G$ son elementarily equivalente a $G\sqcup G$? Y ¿qué hay de $\delta$ muchos copias de $G$ con el mismo $\bigsqcup_\delta G$?

Vamos a introducir algo de la terminología y decir que un gráfico de $G$ es 2-auto-similar si $G$ es elementarily equivalente a $G\sqcup G$, y, más generalmente, $G$ es $\delta$-auto-similar si $G$ es equivalente elementarily a $\delta$ muchas copias de $G$.

Más preguntas: Si $G$ es de 2-auto-similar, no esta implica que la misma es $\delta$-auto-similar para cada $\delta$? Para que $\delta,\gamma\geq 2$ hace $\delta$-auto-similitud implican $\gamma$-auto-similitud? Si $G$ es de 2-auto-similar, ¿esto implica que cada copia de $G$ es una primaria de la subestructura de $G\sqcup G$? Y asimismo, para $\bigsqcup_\delta G$?

Por un lado, el argumento acerca de la $\mathbb{Z}$-cadenas fácilmente se generaliza a otros muchos gráficos, tales como la gráfica conectada árbol de $T$ en el que cada vértice tiene grado $3$. Es decir, la teoría de la ciclo-gráficos gratuitos con cada vértice de grado $3$ es $\kappa$categoría para innumerables cardenales $\kappa$ y, por tanto, completa, y por lo $T$ es elementarily equivalente a cualquier número de desunido copias de $T$. Y vemos claramente el uso de árboles de cualquier finito uniforme de grado en este argumento. También, hay no uniforme de los gráficos con la auto-similitud, tales como el gráfico árbol donde los vértices alternos de grado 2, grado 3, etc., y cualquier otro definibles por el patrón. Y el ciclo libertad no es se requiere, ya que se podría añadir bucles de cualquier longitud para cada vértice en un $\mathbb{Z}$-de la cadena, por ejemplo, y la argumento original todavía funciona bien.

Además, triviales de la auto similitud surgir al $G$ es francamente isomorfo a $G\sqcup G$, como con el infinito edgeless gráfico, o al $G$ es cualquier infinita suma de un fijo gráfico (y esto es equivalente a $G\cong G\sqcup G$). Pero el ejemplo de la $\mathbb{Z}$-cadenas muestra que este isomorfismo versión de auto similitud es no es una propiedad necesaria para el 2-auto-similitud, ya que uno de los $\mathbb{Z}$-cadena obviamente no es isomorfo a dos, incluso a pesar de que son elementarity equivalente.

Mientras tanto, hay algunas observar fácilmente los obstáculos a la $\delta$-auto-similitud:

• Si $G$ ha definibles elementos, a continuación, 2-auto-similitud fallará, ya que cada punto tiene automorphic imágenes en $G\sqcup G$.

• Del mismo modo, si $G$ ha finito no vacío definibles subconjuntos, entonces no va a ser $n$-auto-similar de lo suficientemente grande como $n$, ya que de nuevo habrá demasiados automorphic imágenes. (Tal vez este argumento puede ser mejorado para mostrar $G$ es no 2-auto-similar; por ejemplo, esto es fácil de ver cuando las copias de $G$ son primarias subestructuras de $G\sqcup G$.)

• Si $G$ ha finito de diámetro, de nuevo auto-similitud fallará, ya que varias copias de $G$ no va a estar conectado y por lo tanto no tiene ese diámetro. (Así, por ejemplo, los contables al azar gráfico no es 2-auto-similar.)

Finalmente, parece que muchas preguntas similares se puede pedir acerca de otras estructuras matemáticas.

• Cual parcial de las órdenes $P$ son elementarily equivalente a $P\oplus P$? O $\oplus_\delta P$?
• Que los grupos de $G$ son elementarily equivalente a $G\oplus G$? Or to $\oplus_\delta G$?
• Mismo para los anillos o lo que sea, la estructura para la cual directa suma tiene sentido.

Me pregunto si podría haber un general modelo de la teoría de la caracterización de la auto similitud.

Answer 1

EDIT: Esto es ahora una de dos partes de respuesta para responder a dos de Joel sub-preguntas. (Todavía no sé acerca de su pregunta principal, que parece bastante difícil para mí.)

Parte I: yo creo que para cualquiera de los dos cardenales $\gamma, \delta \geq 2$, un gráfico de $G$ es $\gamma$-auto-semejantes si y sólo si $G$ es $\delta$-auto-similar.

La idea es el uso de Ehrenfeucht-Fraisse juegos para mostrar que $m$-auto-similitud para un finito $m \geq 2$ es equivalente a $\gamma$-auto-similitud para cada cardenal $\gamma$.

En primer lugar, supongamos $G$ es elementarily equivalente a $m$ discontinuo copias de sí mismo para algunos finito $m$. Entonces para un finito $k$, $G$ es elementarily equivalente a la inconexión de la unión de $m^k$ copias de sí mismo. (¿Por qué? Usted puede hacer una inducción sobre k; si $G$ es equivalente a $G^{m^k}$, entonces se puede demostrar que los $G^m$ es equivalente a $G^{m^{k+1}}$ por el pensamiento de este último como una suma de $m$ copias de $G^{m^k}$, y a continuación, obtener una estrategia ganadora para el verificador para una EF juego en $(G^m,G^{m^{k+1}})$ pensando en el juego como una suma de $m$ partidas simultáneas entre cada copia de $G$ en $G^m$ y de cada copia de $G^{m^k}$ en $G^{m^{k+1}}$, utilizando el comprobador de la estrategia ganadora para $(G, G^{m^k})$ en cada subgame.) De ello se deduce que para cualquier infinita $\gamma$, $G$ es elementarily equivalente a un discontinuo suma de $\gamma$ copias de sí mismo: para demostrar que la longitud-$n$ EF juego contra $G$ e $G^\gamma$ tiene una estrategia ganadora para el verificador, nosotros simplemente la selección de $k$ con $m^k \geq n$ y el uso de la estrategia ganadora para el verificador de $G$ e $G^{m^k}$.

En la segunda, supongamos $G$ es elementarily equivalente a $G^\gamma$ para algunos infinito $\gamma$. Entonces para un finito $k$, $G^k$ también es elementarily equivalente a $G^\gamma$: esto es porque se puede escribir $G^\gamma$ como distinto de la suma de $k$ copias de $G^\gamma$ (desde $\gamma$ es infinita), y para obtener una estrategia ganadora para el verificador de la $n$-paso EF juego, simplemente imagina que estás jugando $k$ juegos separados entre cada copia de $G$ en $G^k$ y cada una de las $k$ copias de $G^\gamma$.

Así que si $k$ e $\ell$ son finitos y $G^k$ es elementarily equivalente a $G^\omega$,, a continuación, $G^\ell$ es también elementarily equivalente a $G^\omega$, por transitividad, $G^k$ es equivalente a $G^\ell$. Poniendo todo esto junto, mi reclamo de la siguiente manera.

---

Parte II: es posible dar una buena caracterización de la auto-similitud de abelian grupos.

Szmielew mostró que dos abelian grupos G y H son elementarily equivalentes si y sólo si tienen todos el mismo "Szmielew invariantes," donde el Szmielew invariantes de G son las siguientes (las cuales se definen a cualquiera de los números naturales 0, 1, ... o $\infty$):

1. El exponente de G, la menos positiva de n (si existe) de tal manera que nG = 0, o bien $\infty$;

2. Para cada uno de los primos p y $n \geq 0$, $\dim {p^n G[p]}/{p^{n+1} G[p]}$, donde $G[p]$ es el subgrupo de todas las $p$-torsión de los elementos de $G$ y la dimensión es como un $\mathbb{F}_p$ espacio vectorial;

3. Para cada uno de los primos p, $\lim_{n \rightarrow \infty} \dim {p^n G}/{p^{n+1} G}$;

4. Para cada uno de los primos p, $\lim_{n \rightarrow \infty} \dim p^n G[p]$.

Desde $G \oplus G$ tiene el mismo exponente como $G$ e invariantes de la 2 a la 4 conmuta con directa sumas (el invariante de $G \oplus H$ es la suma de los invariantes de $G$ e de $H$), se deduce que un grupo abelian $G$ es auto-similar si cada uno de sus invariantes de tipo 2 a través de 4 es $0$ o $\infty$.

(Ver Hodges' Modelo de la Teoría o Prest del Modelo de la Teoría y de los Módulos de niza explicaciones de Szmielew invariantes.)

Yo no sé hasta qué punto esto se generaliza, es decir, hay muchas otras categorías de co-productos, tales que la primaria equivalencia es determinado por una lista de cardenal invariantes que conmutan con la toma de co-productos? Para los gráficos, esto parece demasiado a la esperanza, pero al menos tal vez para las teorías de los módulos a través de agradable anillos (como los dominios de Dedekind), se podría hacer algo similar.

Answer 2

Es bastante vieja pregunta, pero creo que tengo la respuesta para los gráficos. Vamos a definir algunas notaciones, basado en Juan Goodrick la respuesta. Todo lo de abajo puede ser formalizada a través de Ehrenfeucht–Fraïssé juegos, pero vamos a usar la noción de tipo lógico para acortar los argumentos.

Un tipo denota cualquier $n$-tipo de $n<\omega$. La realización de un tipo de $t$ en un gráfico de $G$ es un subconjunto de vértices que es de tipo $t$.

Definición 1: Una teoría es abundante si cada tipo es que no se dio cuenta o se dio cuenta infinitamente a menudo.

Lema: la teoría de La auto-similar estructura es abundante.

De esta manera se sigue directamente de Juan Goodrick la respuesta, que la auto-similar es el mismo que $\delta$-similar para cualquier $\delta$. Tomar algunas realización de un tipo de $t$ en $G$. Desde $G$ es auto-similar, es equivalente a $\oplus_\omega G$, con lo que podemos encontrar $\omega$ realizaciones a partir de las copias de $G$.

Deje $d(u,v)$ ser la gráfica de la distancia (o salto de distancia), que se considera infinito si los dos vértices que pertenecen a diferentes componentes conectados. Vamos a la distancia $d(U,V)$ sobre los conjuntos de vértices que ser el mínimo a través de cada posible par de vértices.

Definición 2: Una teoría es dispersada si para cada par de tipos $t_1$, $t_2$ y cada una de las $k$, existe una realización de $t_1$ y de la realización de la $t_2$ a una distancia de al menos $k$.

(En particular, pueden ser a distancia infinita.) Tenga en cuenta que si una teoría es abundante y dispersa, a continuación, es posible encontrar, al menos, $m$ pares de realizaciones en distancia de al menos $k$ cualquier $m$, dado que el par forma una instancia de una $f(n,k)\leqslant$-tipo.

Ahora el resultado: Una estructura es auto-similar, si y sólo si es abundante y dispersa.

Desde ya contamos con la implicación de 'auto-similar $\rightarrow$ abundante', podemos centrarnos en la dispersos parte. En la dirección de avance, tomar dos realizaciones de cualquier par de dio cuenta de los tipos de $t_1$ e $t_2$. Desde $G$ es elementarily equivalente a $G \oplus G$, hemos encontrado una realización de $t_1$ e $t_2$ a una distancia de más de $k$. En la otra dirección, supongamos que la teoría no es dispersa, es decir, hay un par de tipos de $t_1$ e $t_2$ para los que no existen realizaciones en la distancia de más de $k_\star$ para algún número natural. A continuación, tomar en $G \oplus G$ una realización de $t_1$ y uno de $t_2$ en cada copia de $G$. Ellos están a una distancia de más de $k_\star$, lo $G \oplus G$ e $G$ no puede ser primaria equivalente, una contradicción.