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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s