Can a parent and child node have the same type in a well-founded digraph tree?

Question

$\newcommand\toward{\rightharpoonup}$It would help me to understand something in a current research project if someone could provide an example of directed graph $\langle G,\toward\rangle$ with the following properties

• The graph is connected.
• Every node $x$ points at exactly one parent node $y$, via $x\toward y$. Thus, the underlying relation is a tree.
• The relation $\toward$ is well-founded, so that every nonempty subset $X\subset G$ has an $\toward$-minimal element $x\in X$, meaning that $y \not\!\toward x$ for all $y\in X$. In the presence of DC, this is equivalent to saying that there is no infinitely receding sequence $\cdots\toward x_3\toward x_2\toward x_1\toward x_0$.
• Finally, the key part, there are two elements $a$ and $b$ with $a\toward b$, such that $a$ and $b$ realize exactly the same type in $\langle G,\toward\rangle$. That is, $G\models\varphi(a)\leftrightarrow\varphi(b)$ for any assertion $\varphi$ in the digraph language.

Can this happen?

Note that there can be no automorphism mapping $b$ to $a$, for in this case, we could iterate it to produce a receding chain, contrary to the well-founded hypothesis.

Also, since $b$ is not minimal, neither can $a$ be minimal, and if there is a path from a minimal element to $a$ of length $k$, then there is one to $b$ of length $k+1$, and so if the types are the same, there is a path to $a$ of length $k+1$, and so on. So both $a$ and $b$ will have infinite rank with respect to the well-founded relation. And I think one can carry that reasoning much further.

In my actual application, there is a lot more structure, and I consider $a$ and $b$ to realize the same assertions in a much stronger language, one that includes second-order logic and more. But I realized I don't have a complete grasp even on this "easy" case. What are types like in these well-founded digraph trees?

Answer 1

For an ordinal $\alpha$, let $D(\alpha)$ denote the tree of finite sequences $\langle\xi_i,n_i\rangle_{i\lt\ell}$ of pairs from $\alpha\times\omega$ such that $\xi_0 \gt \xi_1 \gt \cdots \gt \xi_{\ell-1}$. The next lemma allows us to determine when two such trees are elementarily equivalent.

Lemma. If $\alpha,\beta \geq \omega n$ then Duplicator has a winning strategy in the EF game of length $n$ between $D(\alpha)$ and $D(\beta)$.

The proof is by induction on $n \geq 1$. Without loss of generality $\beta = \omega n$. If Spoiler's initial play is in $D(\omega n)$, Duplicator can simply copy that move over in $D(\alpha)$ verbatim.

Suppose Spoiler plays $\langle\xi_i,n_i\rangle_{i\lt\ell}$ in $D(\alpha)$. Duplicator's response is the sequence $\langle\xi'_i,n_i\rangle_{i\lt\ell}$ where $\xi'_i = \xi_i$ when $\xi_i \lt \omega(n-1)$ and $\omega(n-1) \leq \xi'_i \lt \omega n$ when $\xi_i \geq \omega(n-1)$ (the precise choice of $\xi'_i$ in the latter case doesn't matter so long as the $\xi'_i$ are decreasing).

Note that the tree below the initial segment $\langle\xi_i,n_i\rangle_{i\lt k}$, excluding the tree below $\langle\xi_i,n_i\rangle_{i\leq k}$ if $k \lt \ell$, is a copy of $D(\xi_{k-1})$ or $D(\alpha)$ when $k = 0$. By the induction hypothesis, Duplicator has a winning strategy in the EF game of length $n-1$ playing each such tree with its counterpart in $D(\omega n)$. Duplicator can then use these strategies for subsequent moves. $\square$

The example tree $T$ is obtained as follows.

• First construct the tree $U$ whose nodes are pairs $(m,n) \in \omega^2$ with edges $(2^k(2m+1)-1,n) \to (m,n+1)$ and no others. So $U$ consists of infinitely many levels $\omega\times\{n\}$, where each node has a parent at the next level and, except for nodes on the bottom level, infinitely many children at the previous level.
• Next, for each node $(m,n)$ of $U$ attach a copy of the tree $D(\omega^2)$ where $(m,n)$ is the root. Note that the tree below $(m,n)$ ends up being isomorphic to $D(\omega^2+n)$.

All the nodes $(m,n)$ of $U$ realize the same type since the tree below $(m,n)$ are all elementarily equivalent by the Lemma and the remaining nodes form an isomorphic copy of $T$ itself.

Answer 2

What about this? Consider a graph $G$ of size $\omega_1$ such that

• $G$ is connected,

• For every node $a$ of rank $\alpha$, and every $\beta<\alpha$, $a$ has $\omega_1$-many children of rank $\beta$.

• Every node has a parent, and there are nodes of all ranks below $\omega_1$.

Now I think an Ehrenfeucht-Fraisse game should show that - if I pick nodes $a$ and $b$ in $G$ with $a$ the parent of $b$ and $rk(b)>\omega^\omega$ (I'm not sure that's optimal) - the structures $(G, a)$ and $(G, b)$ are elementarily equivalent, so $a$ and $b$ have the same type in $G$. I'm pressed for time, so I can't write out the details - of course, if there's a mistake, here it is! - but this seems to work.

We can then replace $G$ with a countable subgraph $G_0$, by taking a countable elementary substructure of $G$ containing $a$ and $b$.