# uppersemilattice end extensions

I'm trying to modify an argument in Jockush and Slaman's paper On the $\Sigma_2$ theory of the upper semilattice of the Turing degrees. One of the major hurdles is that I don't actually see why a claim they make is true. In particular, they claim an equivalence relation is a congruence relation, but I don't see why.

Let $\mathcal{M},\mathcal{N}$ be finite uppersemilattices, so that $\mathcal{N}$ is an end-extension of $\mathcal{M}$. The goal is to show that $\mathcal{N}$ is a subUSL of a simple end extension (simple means generated by a single new element) of a free extension of $\mathcal{M}$.

Firstly enumerate $\mathcal{N}\setminus\mathcal{M}= \{b_1,\ldots,b_n\}$, let $x_1,\ldots,x_n$ be new elements, and let $g$ take $b_i$ to $x_i$. Let $\mathcal{M}_1$ denote the free extension of $\mathcal{M}$ by $\{x_1,\ldots,x_n\}$ (I'll give a formal definition at the end). Define a map $h:\mathcal{M}_1\rightarrow \mathcal{N}$ by $$h(a \vee \bigvee X) = a \vee_{\mathcal{N}}\bigvee_{\mathcal{N}}\{b_i:g(b_i)=x_i\in X\}.$$ One can check this is a USL homomorphism.

Now, let $c$ be new and let $\mathcal{M}_2$ be the free extension of $\mathcal{M}_1$ by $c$. We define $\sim$ on $\mathcal{M_2}$ by $e_1 \sim e_2$ iff $e_1 = e_2$ or $$(\exists d_1,d_2\in\mathcal{M}_1)[e_1 = d_1 \vee_{\mathcal{M}_2} c, e_2 = d_2 \vee_{\mathcal{M}_2}c\text{ and }h(d_1)=h(d_2)].$$ One can check this is an equivalence relation. The authors claim this is a congruence relation (they want to define $\mathcal{N}_2$ be the quotient of $\mathcal{M}_2$ by $\sim$ and then $\mathcal{N}_2$ will be the simple extension they are after).

Suppose $e_1\sim e_1'$ and $e_2\sim e_2'$, we want to show $e_1\leq e_2$ iff $e_1'\leq e_2'$. We can write each element, uniquely, as the join of some $d\in \mathcal{M}$ and a subset of $\{c\}$, we do this as $e_1 = d_1 \vee Y_1$ with the obvious changes to subscripts and primes.

Its easy to see that if $e\in\mathcal{M}_2$ is in $\mathcal{M}_1$ (or more precisely, it is of the form $d \vee \emptyset$) then its $\sim$ equivalence class is just itself. So if $e_2\in\mathcal{M_1}$, then, as free extensions are also end extensions, $e_1\in\mathcal{M_1}$ and so $e_2=e_2',e_1=e_1'$. But, as soon as $e_2\neq e_2'$ I get stuck. Working through the definition of $\sim$ one derives that $h(d_2)=h(d_2')$ and as $e_1\leq e_2$ we know $d_1\leq d_2$, so that $h(d_1)\leq h(d_2)=h(d_2')$ as $h$ is a homomorphism. But, of course, I can't pull back $h(d_1)\leq h(d_2')$ to $d_1\leq d_2'$, because homomorphisms don't work backwards with relations.

Anyone see what I'm missing?

Given a USL $\mathcal{M}$ and a set $X$ the free extension of $\mathcal{M}$ by $X$ can be realised as the structure with elements of the form $a \vee Y$ where $Y$ is a finite subset of $X$. You say $a\vee Y\leq a'\vee Y'$ iff $a\leq_\mathcal{M} a'$ and $Y\subseteq Y'$, and define $(a\vee Y) \vee (a'\vee Y')$ to be $(a\vee_{\mathcal{M}} a')\vee (Y\cup Y')$. One can naturally identify $\mathcal{M}$ with $\mathcal{M}\times\{\emptyset\}$ in the new structure.

So, with further reflection, I have come to the conclusion that $\sim$ is not a congruence with respect to the $\leq$ structure. I even have a counter-example. $\newcommand{\M}{\mathcal{M}}\newcommand{\N}{\mathcal{N}}$ Let $\M = \{0\}$ and let $\N$ be the diamond $\{0,a,b,a\lor b\}$, clearly an end-extension of $\M$. $\M_1$ will be the free extension of $\M$ generated by $x_1,x_2$ and $x_3$ corresponding to $a,b$ and $a\lor b$ respectively.
Now let $c$ be new, and consider elements $e_1 = (0 \lor \bigvee \{x_1\})\lor c, e_2 = (0\lor\bigvee\{x_1,x_2\})\lor c$, and $e_2' = (0\lor \bigvee\{x_3\})$. Note that $e_1\leq e_2$ yet $e_1\nleq e_2'$. However, $e_2 \sim e_2'$, as their corresponding $d$s are $0\lor \bigvee\{x_1,x_2\}$ and $0\lor \bigvee\{x_3\}$, which map, via $h$ to $0 \lor_\N \bigvee_\N \{a,b\} = a\bigvee_\N b$ and $0 \lor_\N \bigvee_\N \{a\lor b\}= a\lor b$. Consequently, $\sim$ is not congruent for $\leq$.
However, $\sim$ is congruent for $\lor_{\M_2}$, and so this descends, and you can use this to define a binary relation $\leq$ on the quotient given by $[a] \leq [b]$ iff $[a]\lor [b] ( = [a\lor b]) = [b]$, one can show this is a partial order and $\lor$ is the join operator. Hopefully we can still embed $\N$ in the quotient.