Do Jónsson-Tarski algebras form a Schreier variety?

Question

That is: is a subalgebra of a free Jónsson-Tarski algebra (aka Cantor algebra) again free?

I’ve almost convinced myself that it is, but (as with groups) a rigorous proof would be somewhat involved.

Perhaps there are general considerations implying this is true?

Answer 1

This is true, and it's pretty simple once you have a good normal form for elements of free Jónsson-Tarski algebras.

Let's first fix some notation. We will write $w(\cdot,\cdot)$ for the pairing operation on a Jónsson-Tarski algebra and $p_0,p_1$ for the two projections (so $p_0(w(x,y))=x$, $p_1(w(x,y))=y$, and $w(p_0(x),p_1(x))=x$). If $s=a_1\dots a_n$ is a finite string of $0$s and $1$s, we also write $p_s$ as an abbreviation for $p_{a_1}\circ p_{a_2}\circ\dots\circ p_{a_n}$.

Now fix a set $X$ and let $F$ be the free Jónsson-Tarski algebra on $X$. Let $T$ be the set of expressions of the form $p_s(x)$ for any string $s$ and $x\in X$. Define a reduced word on $X$ to be an expression obtained by repeatedly applying $w$ to elements of $T$, such that we never do an operation of the form $w(p_{0s}(x),p_{1s}(x))$.

Claim: Every element of $F$ is represented by a unique reduced word.

Proof: First, any element of $F$ can be represented by a word where we first apply $p_0$ and $p_1$ and only afterwards apply $w$, since if we ever have $p_0\circ w$ or $p_1\circ w$ we can reduce it. This means every element of $F$ is obtained by repeatedly applying $w$ to elements of $T$. Moreover, if we ever have $w(p_{0s}(x),p_{1s}(x))$, we can reduce that to just $p_s(s)$, and thus get a reduced word.

For uniqueness, we can simply define operations $w,p_0,p_1$ on the set of reduced words in the obvious way and check that they give a Jónsson-Tarski algebra. This is completely straightforward, and proves that any two distinct reduced words must represent distinct elements in the free algebra on $X$.

Now we use this characterization to prove that certain subalgebras of $F$ are free. First, define a partial order $\leq$ on $T$ by saying $p_s(x)\leq p_t(y)$ iff $x=y$ and $t$ is a terminal segment of $s$. This makes $T$ a disjoint union of binary trees, one for each element of $X$. Say a subset $Y\subseteq T$ is independent if its elements are pairwise incomparable with respect to $\leq$ and there do not exist two elements of the form $p_{0s}(x)$ and $p_{1s}(x)$ in $Y$.

Claim: If $Y\subseteq T$ is independent, then the subalgebra $A\subseteq F$ generated by $Y$ is free on $Y$.

Proof: It suffices to show that all reduced words on $Y$ give distinct elements of $A$. First, all elements of the form $p_s(y)$ for $y\in Y$ are distinct because the elements of $Y$ are incomparable with respect to $\leq$. Then if we repeatedly apply $w$ to such elements without ever doing an expression of the form $w(p_{0s}(y),p_{1s}(y))$, we can replace each $y\in Y$ with its expression in the form $p_s(x)$ for $x\in X$ to get a word on elements of $X$. This word will be reduced since the elements of $Y$ are incomparable and $Y$ does not contain any two elements of the form $p_{0s}(x)$ and $p_{1s}(x)$. Moreover, distinct reduced words over $Y$ turn into distinct reduced words over $X$ via this process (again, because the elements of $Y$ are incomparable). So, every distinct reduced word over $Y$ gives a distinct element of $A$.

Finally, let $A\subseteq F$ be any subalgebra. Every element of $A$ can be obtained by repeatedly applying $w$ to certain elements of $T$, and those elements of $T$ must also be in $A$ since we can reverse $w$ using $p_0$ and $p_1$. Thus $A$ is generated by $A\cap T$. Let $Y$ be the set of maximal elements of $A\cap T$ with respect to $\leq$.

Claim: $Y$ generates $A$ and is independent, and thus $A$ is freely generated by $Y$.

Proof: Since each element of $Y$ is maximal in $A\cap T$, any two are incomparable. Also, if we had $p_{0s}(x), p_{1s}(x)\in Y$, then $p_s(x)$ would be in $A$ and thus in $A\cap T$, contradicting maximality of $p_{0s}(x)$ and $p_{1s}(x)$. Thus $Y$ is independent.

To see that $Y$ generates $A$, it suffices to show it generates $A\cap T$. So, let $p_s(x)\in A\cap T$. There is then a shortest terminal segment $t$ of $s$ such that $p_t(x)\in A\cap T$, and this $p_t(x)$ is a maximal element of $A\cap T$ and thus in $Y$. But $p_s(x)$ is obtained by repeatedly applying $p_0$ and $p_1$ to $p_t(x)$, so it is in the subalgebra generated by $Y$.

(In fact, it is easy to see that the constructions $Y\mapsto A$ and $A\mapsto Y$ above are inverse to each other, so that every subalgebra of $F$ is generated by a unique independent subset of $T$.)