Which graphs are elementarily equivalent to their own disjoint sums?

Question

In Stefan Geschke's recent question, one of the solutions observed that the graph consisting of a single infinite beaded chain, a $\mathbb{Z}$-chain where each integer is connected to its nearest neighbors, is elementarily equivalent to the disjoint sum of any number of such chains. That is, a single chain has all the same first order properties in the language of graph theory as two chains, or as any number of such chains.

(The reason was that all these graphs are cycle-free and have every element with degree $2$, but the theory asserting this is already complete. This can be seen by observing that every model of this theory having uncountable size $\kappa$ consists of $\kappa$ many $\mathbb{Z}$-chains, and all such models are isomorphic---in other words, the theory is $\kappa$-categorical---and so the theory is complete, since otherwise it would have non-isomorphic models of size $\kappa$.)

My question here is about the extent to which this phenomenon generalizes to other graphs.

Question. Which graphs $G$ are elementarily equivalent to $G\sqcup G$? And how about $\delta$ many copies of $G$ with itself $\bigsqcup_\delta G$?

Let's introduce some terminology and say that a graph $G$ is 2-self-similar if $G$ is elementarily equivalent to $G\sqcup G$, and more generally $G$ is $\delta$-self-similar if $G$ is elementarily equivalent to $\delta$ many copies of $G$.

Further questions: If $G$ is 2-self-similar, does this imply that it is $\delta$-self-similar for every $\delta$? For which $\delta,\gamma\geq 2$ does $\delta$-self-similarity imply $\gamma$-self-similarity? If $G$ is 2-self-similar, does this imply that each copy of $G$ is an elementary substructure of $G\sqcup G$? And similarly for $\bigsqcup_\delta G$?

On the one hand, the argument about $\mathbb{Z}$-chains easily generalizes to many other graphs, such as the connected graph tree $T$ in which every vertex has degree $3$. That is, the theory of cycle-free graphs with every vertex of degree $3$ is $\kappa$-categorical for uncountable cardinals $\kappa$ and hence complete, and so $T$ is elementarily equivalent to any number of disjoint copies of $T$. And we can clearly use trees of any finite uniform degree in this argument. Also, there are non-uniform graphs with self-similarity, such as the graph tree where vertices alternate degree 2, degree 3, etc., and any other definable pattern. And cycle-freeness is not required, since one could add loops of any length to every vertex in a $\mathbb{Z}$-chain, for example, and the original argument would still work fine.

In addition, trivial instances of self similarity arise when $G$ is outright isomorphic to $G\sqcup G$, such as with the infinite edgeless graph, or when $G$ is any infinite sum of a fixed graph (and this is equivalent to $G\cong G\sqcup G$). But the example of $\mathbb{Z}$-chains shows that this isomorphism version of self similarity is not a necessary property for 2-self-similarity, since one $\mathbb{Z}$-chain is obviously not isomorphic to two, even though they are elementarily equivalent.

Meanwhile, there are some easily observed obstacles to $\delta$-self-similarity:

• If $G$ has definable elements, then 2-self-similarity will fail, since every point has automorphic images in $G\sqcup G$.

• Similarly, if $G$ has nonempty finite definable subsets, then it will not be $n$-self-similar for large enough $n$, since again there will be too many automorphic images. (Perhaps this argument can be improved to show $G$ is not 2-self-similar; for example, this is easy to see when the copies of $G$ are elementary substructures of $G\sqcup G$.)

• If $G$ has finite diameter, then again self-similarity will fail, since multiple copies of $G$ will not be connected and hence not have that diameter. (Thus, for example, the countable random graph is not 2-self-similar.)

Finally, it seems that many similar questions can be asked about other mathematical structures.

• Which partial orders $P$ are elementarily equivalent to $P\oplus P$? Or to $\oplus_\delta P$?
• Which groups $G$ are elementarily equivalent to $G\oplus G$? Or to $\oplus_\delta G$?
• Same for rings or whatever structure for which direct sum makes sense.

I am wondering whether there might be a general model-theoretic characterization of self similarity.

Answer 1

EDIT: This is now a two-part answer to respond to two of Joel's sub-questions. (I still don't know about his main question, which seems quite difficult to me.)

Part I: I claim that for any two cardinals $\gamma, \delta \geq 2$, a graph $G$ is $\gamma$-self-similar if and only if $G$ is $\delta$-self-similar.

The idea is to use Ehrenfeucht-Fraisse games to show that $m$-self-similarity for a finite $m \geq 2$ is equivalent to $\gamma$-self-similarity for every cardinal $\gamma$.

First, suppose $G$ is elementarily equivalent to $m$ disjoint copies of itself for some finite $m$. Then for any finite $k$, $G$ is elementarily equivalent to the disjoint union of $m^k$ copies of itself. (Why? You can do an induction on k; if $G$ is equivalent to $G^{m^k}$, then you can show that $G^m$ is equivalent to $G^{m^{k+1}}$ by thinking of the latter as a sum of $m$ copies of $G^{m^k}$, and then get a winning strategy for the verifier for an EF game on $(G^m,G^{m^{k+1}})$ by thinking of the game as a sum of $m$ simultaneous games between each copy of $G$ in $G^m$ and each copy of $G^{m^k}$ in $G^{m^{k+1}}$, using the verifier's winning strategy for $(G, G^{m^k})$ on each subgame.) It follows that for any infinite $\gamma$, $G$ is elementarily equivalent to a disjoint sum of $\gamma$ copies of itself: to show that the length-$n$ EF game against $G$ and $G^\gamma$ has a winning strategy for the verifier, we simply pick $k$ with $m^k \geq n$ and use the winning strategy for the verifier for $G$ and $G^{m^k}$.

Second, suppose $G$ is elementarily equivalent to $G^\gamma$ for some infinite $\gamma$. Then for any finite $k$, $G^k$ is also elementarily equivalent to $G^\gamma$: this is because we can write $G^\gamma$ as a disjoint sum of $k$ copies of $G^\gamma$ (since $\gamma$ is infinite), and to get a winning strategy for the verifier for the $n$-step EF game, simply imagine that you are playing $k$ separate games between each copy of $G$ in $G^k$ and each of the $k$ copies of $G^\gamma$.

So if $k$ and $\ell$ are finite and $G^k$ is elementarily equivalent to $G^\omega$, then $G^\ell$ is also elementarily equivalent to $G^\omega$, so by transitivity, $G^k$ is equivalent to $G^\ell$. Putting all of this together, my claim follows.

---

Part II: It is possible to give a nice characterization of self-similarity for abelian groups.

Szmielew showed that two abelian groups G and H are elementarily equivalent if and only if they have all the same "Szmielew invariants," where the Szmielew invariants of G are the following (which are defined to be either natural numbers 0, 1, ... or $\infty$):

1. The exponent of G, the least positive n (if it exists) such that nG = 0, or else $\infty$;

2. For each prime p and $n \geq 0$, $\dim {p^n G[p]}/{p^{n+1} G[p]}$, where $G[p]$ is the subgroup of all $p$-torsion elements of $G$ and the dimension is as an $\mathbb{F}_p$ vector space;

3. For each prime p, $\lim_{n \rightarrow \infty} \dim {p^n G}/{p^{n+1} G}$;

4. For each prime p, $\lim_{n \rightarrow \infty} \dim p^n G[p]$.

Since $G \oplus G$ has the same exponent as $G$ and invariants 2 through 4 commute with direct sums (the invariant of $G \oplus H$ is the sum of the invariants of $G$ and of $H$), it follows that an abelian group $G$ is self-similar if each of its invariants of type 2 through 4 is either $0$ or $\infty$.

(See Hodges' Model Theory or Prest's Model Theory and Modules for nice explanations of Szmielew invariants.)

I don't know how far this generalizes -- i.e. are there many other natural categories with coproducts such that elementary equivalence is determined by such a list of cardinal invariants which commute with taking coproducts? For graphs, this seems like too much to hope for, but at least maybe for theories of modules over nice rings (like Dedekind domains) you could do something similar.

Answer 2

It's a fairly old question, but I think I have the answer for graphs. Let's define some notations, based on John Goodrick's answer. Everything below can be formalized by Ehrenfeucht–Fraïssé games, but we'll use the notion of logical type to shorten arguments.

A type denotes any $n$-type for $n<\omega$. The realization of a type $t$ in a graph $G$ is a subset of vertices which is of type $t$.

Definition 1: A theory is abundant if every type is either not realized or realized infinitely often.

Lemma: The theory of a self-similar structure is abundant.

This follows directly from John Goodrick's answer, that self-similar is the same as $\delta$-similar for any $\delta$. Take some realization of a type $t$ in $G$. Since $G$ is self-similar, it is equivalent to $\oplus_\omega G$, thus we can find $\omega$ realizations from the copies of $G$.

Let $d(u,v)$ be the graph distance (or hop distance), which is considered infinite if the two vertices belong to different connected components. Let the distance $d(U,V)$ over sets of vertices be the minimum over every possible pair of vertices.

Definition 2: A theory is scattered if for every pair of types $t_1$, $t_2$ and every $k$, there exists a realization of $t_1$ and a realization of $t_2$ at distance at least $k$.

(In particular, they can be at infinite distance.) Note that if a theory is abundant and scattered, then it is possible to find at least $m$ pairs of realizations at distance at least $k$ for any $m$, since the pair form an instance of a $f(n,k)\leqslant$-type.

Now the result: A structure is self-similar if and only if it is abundant and scattered.

Since we already have the implication 'self-similar $\rightarrow$ abundant', we can focus on the 'scattered' part. In the forward direction, take two realizations of any pair of realized types $t_1$ and $t_2$. Since $G$ is elementarily equivalent to $G \oplus G$, we have found a realization of $t_1$ and $t_2$ at distance more than $k$. In the other direction, suppose the theory is not scattered, i.e. there is a pair of types $t_1$ and $t_2$ for which there are no realizations at distance more than $k_\star$ for some natural number. Then take in $G \oplus G$ one realization of $t_1$ and one of $t_2$ in each copy of $G$. They are at distance more than $k_\star$, thus $G \oplus G$ and $G$ cannot be elementary equivalent, a contradiction.