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.

| cite | improve this answer | |

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.