Refining Equivalence Relations with Finite Branching

We define a new theory $\textrm{REF}_\alpha$ to be, approximately, a “binary tree” of equivalence relations, of depth $\alpha$ . That is, each equivalence class at level $\gamma$ splits into exactly two classes at level $\gamma+1$ , assuming that’s well-defined.

More precisely, for any ordinal $\alpha$ , we define the language $L_\alpha = \{ E_\beta : \beta<\alpha \}$ , where each $E_\beta$ is a binary relation. The theory $\textrm{REF}_\alpha$ states that each $E_\beta$ is an equivalence relation, and if $\beta+1<\alpha$ , then every $E_\beta$ splits into precisely two $E_{\beta+1}$ classes. More axiomatically, for any $x$ in the structure, there is a $y$ in the structure where $E_\beta xy$ and $\lnot E_{\beta+1}xy$ , but for any $z$ in the structure, if $E_\beta xz$ , then either $E_{\beta+1}xz$ or $E_{\beta+1}yz$ .

The tree motivation yields an “intended model,” (which is not necessarily a prime model) denoted $2^\alpha$ , where the underlying set is the space of functions from $\alpha$ to $2$ , and the equivalence relation $E_\beta$ is agreement on the subset $\beta\subset \alpha$ . It is clear that this is an equivalence relation, and that each $E_\beta$ -class (represented by a “partial function” from $\beta$ to $2$ ) indeed refines into exactly two $E_{\beta+1}$ -classes (extensions of that partial function, which send $\beta$ itself to either $0$ or $1$).

If $\alpha$ is a nonzero limit ordinal, then every equivalence class, at every height, is subdivided at the next height, so must have at least 2 elements. But it’s then subdivided again, and so on, so in fact, every equivalence class at every level must be infinite. This is not actually true if $\alpha$ is a successor ordinal, so for this (and a few other) reasons, we will always assume $\alpha$ is a nonzero limit ordinal. In fact the next theorem is not true if $\alpha$ is a successor ordinal!

$\textrm{REF}_\alpha$ has quantifier elimination.

Suppose that $\mathfrak{A},\mathfrak{B}\vDash \textrm{REF}_\alpha$ , that $\overline{c}$ is a tuple from the intersection, and that $\phi(x, \overline c)$ is an open formula with $x$ free. Suppose also that for some $a\in\mathfrak{A}$ , we have $\mathfrak{A}\models \phi(a, \overline c)$ . It is then sufficient to show that $\mathfrak{B}\vDash \exists x \phi(x, \overline c)$ .

So let $\beta$ be the largest ordinal (less than $\alpha$ ) where $E_\beta xc$ appears positively in $\phi(x,\overline c)$ , for some $c\in\overline c$ . If there are none, we just let $\beta=-1$ , where $E_{-1}xy$ is just always true. We will now produce a solution to $\phi(x,\overline c)$ in $\mathfrak{B}$ .

We may assume (by using the disjunctive normal form, then passing to a positive disjunct) that $\phi$ is a conjunction of atoms, some positive and some negative. Let $\beta$ be the highest ordinal such that some $E_\beta xc$ appears in $\phi$, and start with the $E_\beta$ -class of $c$ in $\mathfrak{B}$ . We will go term-by-term in $\phi$ and generate an infinite number of solutions.

First, all positive terms are already satisfied, since they must be of the form $E_\gamma xc'$ , and since $a$ models $\phi$ , we must have $c, a, c'$ all $E_\gamma$ -equivalent, since $\gamma\leq\beta$ by construction, and the equivalence relations refine their predecessors.

So for negative terms, note that if $\gamma\leq\beta$ and $\lnot E_\gamma xc'$ appears, then it’s already satisfied, since as before, $c$ and $a$ are $E_\gamma$ -equivalent. So if $\lnot E_\gamma ac'$ , then $\lnot E_\gamma cc'$ , so if $E_\beta xc$ , then $\lnot E_\gamma xc'$ .

So we now pass to the case where $\beta<\gamma$ , and are concerned with the case where $\lnot E_\gamma xc'$ appears in $\phi$ , but $E_\gamma xc'$ actually holds. But since $\beta<\gamma$ , there are multiple $E_\gamma$ -classes within our working set, and clearly only one class can violate our constraint. Thus we can simply pass to any of the other $E_\gamma$ -classes and stay in infinite set of solutions.

Constructively, we work within the set of solutions to our largest positive constraint. Then, in ascending order in $\gamma$ , we move to $E_\gamma$ -classes which satisfy our negative constraints. This terminates in finite time (since formulas are finite) and we have our solution in $\mathfrak{B}$ . This completes the proof.

$\textrm{REF}_\alpha$ is complete.
$\textrm{REF}_\alpha$ has a prime model.

The “intended model,” $2^\alpha$ , is quite obviously larger than the language at hand, but a slight modification of our construction will yield a substructure of $2^\alpha$ we will call $M$ . In fact the substructure will just be those functions which are zero on a cofinite subset of $\alpha$ . This is still a model of $\textrm{REF}_\alpha$ , by the same proof as before- we just don’t have so many classes actually represented. Note that in this model (and in the intended model, though not all models), if $\beta<\alpha$ is a limit ordinal, then $E_\beta = \bigcap_{\gamma<\beta}E_\gamma$ . That is, if two functions disagree at a limit stage, then they disagree on a previous stage.

Claim: The lexicographic ordering on $M$ is a well-order.

In all cases, if $a<b$ in $M$ , then there is a $\beta$ such that $a$ and $b$ agree up to $\beta$ , but then $a(\beta)=0<1=b(\beta)$ . Then $c<a$ , then the relevant point $\gamma$ of last agreement must have $\gamma<\beta$ . Thus, any infinite downward chain in $M$ yields an infinite downward chain of ordinals, which is impossible.

Now, from the claim, we can use strong induction to build an injection from $M$ into any arbitrary model $\mathfrak{A}\models\textrm{REF}_\alpha$ . Pick the target of the first element (the zero function) arbitrarily. For any other function $f\in M$ , pick the last $\beta$ where $f(\beta)=1$ , and let $g$ be the function which agrees everywhere with $f$ except at $\beta$ , and where $g(\beta)=0$ . Then $g<f$ , so $g$ already has an image in $\mathfrak{A}$ - call it $a_g$ .

We want an $a_f$ which is $E_\gamma$ -equivalent with $a_g$ if and only if $\gamma \leq\beta$ . But the $E_\beta$ -class is infinite and refines into two $E_{\beta+1}$ -classes, so choose $a_g$ arbitrarily from the class which doesn't contain $a_f$ .

This gives an injection which preserves every $E_\beta$ and its negation. By quantifier elimination, this is then an elementary map, yielding primality. Completeness follows immediately- $\mathfrak{A}\models \sigma$ if and only if $M\models \sigma$ , so $\textrm{REF}_\alpha=\textrm{Th}(M)$ , and is complete.

$\textrm{REF}_\alpha$ is stable.

We use the local form of stability. By quantifier elimination, it is sufficient to show that open formulas are stable. The class of stable formulas is also closed under negation and conjunction, so it sufficient to show that positive atoms are stable.

Now we show that for any atom $\phi$ and any set $A$ , every type in $S_\phi(A)$ is definable. But this is pretty clear: any atom is either of the form $x=y$ or $E_\beta xy$ . In either case, if the atom never appears positively, then it admits a definition of $y\not=y$ . If it does appear positively, say as $x=a$ or $E_\beta xa$ , then it can be defined by $y=a$ or $E_\beta ya$ respectively, since both equality and $E_\beta$ are equivalence relations.

$\textrm{REF}_\alpha$ is superstable.

Superstability is equivalent to the property that there is no infinite forking chain. By quantifier elimination and the usual reductions, this would be an element $b$ and a sequence $\{ a_n:n\in\omega\}$ such that, if $A_n=\{a_0, \ldots, a_{n-1}\}$ , then $b$ forks with $a_n$ over $A_n$ for every $n$ .

Claim: $a$ forks with $B$ over $C$ if and only if, for some $\beta$ and some $b\in B$ , we have $E_\beta ab$ , but for every $m<n$ and every $c\in C$ , we have $\lnot E_\beta bc$ .

This shows that an infinite forking chain of types yields an infinite decreasing chain of ordinals, which is impossible. So $\textrm{REF}_\alpha$ must be superstable.