I am going through C. Ashe and J. Knight Computable structures and the Hyperarithmetic Hierarchy and am stuck at proving one of their Lemmas on back and forth relations and linear orderings (Chapter 15.3.3.).

Ashe and Knight define the standard back and forth relation as follows. I will only state the (slightly simpler) definition for finite languages here.

For two structure $\mathcal{A},\mathcal{B}$ in a finite language $L$ and tuples $\overline a\in \mathcal{A}$ and $\overline b \in \mathcal{B}$ of the same size we define the relation $\leq_\beta$ by induction.

  • $(\mathcal{A},\overline a) \leq_0 (\mathcal{B},\overline b)$ if and only if all quantifier free formulas $\phi(\overline x)$ true of $\overline{a}$ in $\mathcal{A}$ are true of $\overline{b}$ in $\mathcal{B}$,
  • for $\beta\geq 1$, $(\mathcal{A},\overline a)\leq_\beta (\mathcal B,\overline b)$ if and only if, for each $\overline{d}\in \mathcal{B}$ and each $0\leq \alpha<\beta$, there exists $\overline{c}\in \mathcal{A}$ of the same length such that $(\mathcal{B},\overline b \overline d)\leq_\alpha (\mathcal{A},\overline a \overline c)$.

The Lemma I am struggling with is the following.

Lemma 15.7. Suppose $\mathcal{A}$ and $\mathcal{B}$ are linear orderings. Let $\overline{a}=(a_0,\cdots, a_{n-1})$, $\overline{b}=(a_0,\cdots,a_{n-1})$ be increasing tuples from $\mathcal A$, $\mathcal B$, respectively, and let $\mathcal {A}_i, \mathcal{B}_i$ be intervals such that $$ \mathcal{A}=\mathcal{A}_0 + \{a_0\}+\mathcal{A}_1+\cdots+ \{a_{n-1}\} + \mathcal{A}_n,$$ $$ \mathcal{B}=\mathcal{B}_0 + \{b_0\}+\mathcal{B}_1+\cdots+ \{b_{n-1}\} + \mathcal{B}_n.$$ Then $(\mathcal{A},\overline a)\leq_\beta (\mathcal{B},\overline b)$ if and only if for all $0\leq i\leq n$, $\mathcal{A}_i\leq_\beta \mathcal{B}_i$.

They claim that this is easily proved by induction on $\beta$. For $\beta=0$ it is easy, but I am stuck at the induction step. I was trying using the fact that $(\mathcal A,\overline a)\leq_\beta (\mathcal B,\overline b)$ iff $\Sigma_\beta^{\mathrm{in}}\mbox{-}tp(\overline b)\subseteq \Sigma_\beta^{\mathrm{in}}\mbox{-}tp(\overline a)$ (Proposition 15.1 in their book) but could not come up with anything substantial. (Here $\Sigma_\beta^{\mathrm{in}}\mbox{-}tp^{\mathcal{B}}(\overline b)$ is the set of infinitary $\Sigma_\beta$ formulas true of $\overline b$ in $\mathcal{B}$.)

  • $\begingroup$ Please define some of your notation. What is the meaning of $\leq_{\beta}$. Is it just embedding ? $\endgroup$ – Rene Schipperus Dec 20 '16 at 16:38
  • $\begingroup$ Sorry, I added the definitions to my question. I hope that it is clearer now. $\endgroup$ – Dino Rossegger Dec 20 '16 at 18:21
  • $\begingroup$ In the def'n of $\leq_{\beta}$ there is no def'n of $(B,\bar b,\bar d)\leq_{0} (A,\bar a,\bar c)$ so how do we know whether $(A,\bar a)\leq_1 (B,\bar b) $ ? $\endgroup$ – DanielWainfleet Dec 20 '16 at 19:30
  • $\begingroup$ If $\overline b$ and $\overline d$ are tuples of size $m$ and $n$, respectively, then $\overline b, \overline d$ is the canonical tuple of size $m+n$ obtained by concatenation of $\overline b$ and $\overline d$. This is the notation used in Computable structures and the hyperarithmetic hierarchy. If I recall correctly this is often written without comma and I agree that this notation might be confusing. I will edit my question accordingly. $\endgroup$ – Dino Rossegger Dec 20 '16 at 20:30

Here's the argument for the inductive step $\beta\geq 1$.

Suppose $(\mathcal{A},\overline{a})\leq_\beta (\mathcal{B},\overline{b})$. We want to show that $\mathcal{A}_i\leq_\beta \mathcal{B}_i$ for all $i$. By definition, we need to show that for any $\overline{d}\in \mathcal{B}_i$ (which we might as well assume is in ascending order - if you don't believe this, you should check it) and $\alpha<\beta$, there is $\overline{c}$ such that $(\mathcal{B}_i,\overline{d})\leq_\alpha(\mathcal{A}_i,\overline{c})$. Well, since $(\mathcal{A},\overline{a})\leq_\beta (\mathcal{B},\overline{b})$, there is some tuple $\overline{c}$ such that $(\mathcal{B},\overline{b}\overline{d})\leq_\alpha (\mathcal{A},\overline{a}\overline{c})$. In particular, the quantifier-free types of $\overline{b}\overline{d}$ and $\overline{a}\overline{c}$ agree, so the elements of $\overline{c}$ are in increasing order and are all in $\mathcal{A}_i$. So we have \begin{align*} \mathcal{A} &= \mathcal{A}_0 + \{a_0\} + \dots + \{a_{i-1}\} + (\mathcal{A}_i^0 + \{c_0\} + \mathcal{A}_i^1 + \{c_1\} + \dots \{c_{k-1}\} + \mathcal{A}_i^k) + \{a_i\} + \dots + \mathcal{A}_n\\ \mathcal{B} &= \mathcal{B}_0 + \{b_0\} + \dots + \{b_{i-1}\} + (\mathcal{B}_i^0 + \{d_0\} + \mathcal{B}_i^1 + \{d_1\} + \dots \{d_{k-1}\} + \mathcal{B}_i^k) + \{b_i\} + \dots + \mathcal{B}_n \end{align*} where the suborders in parentheses are subdivisions of $\mathcal{A}_i$ and $\mathcal{B}_i$. Now by the inductive hypothesis, since $(\mathcal{B},\overline{b}\overline{d})\leq_\alpha (\mathcal{A},\overline{a}\overline{c})$, we have $\mathcal{B}_i^j\leq_\alpha \mathcal{A}_i^j$ for all $1\leq j\leq k$, and by the inductive hypothesis again, this implies that $(\mathcal{B}_i,\overline{d})\leq_\alpha (\mathcal{A}_i,\overline{c})$.

The converse direction is similar: We assume that $\mathcal{A}_i\leq_\beta\mathcal{B}_i$ for all $i$. To show that $(\mathcal{A},\overline{a})\leq_\beta (\mathcal{B},\overline{b})$, we pick $\overline{d}$ from $\mathcal{B}$ and $\alpha<\beta$, and we want to find $\overline{c}$ such that that $(\mathcal{B},\overline{b}\overline{d})\leq_\alpha (\mathcal{A},\overline{a}\overline{c})$. This time, we break up the tuple $\overline{d}$ into the subtuples which land in each interval $\mathcal{B}_i$, find corresponding tuples in the $\mathcal{A}_i$, and apply the inductive hypothesis twice as above.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.