Varieties of semiassociative relation algebras and tense algebras

Let $p,q\in\mathbb{Z}$ and let $m,n\in\mathbb{N}$. As $m\geqslant m$, we have $(a_{p,m},a_{p,m})\in R_{S}$, so $R_{S}$ is reflexive. Assume that $a_{p,m}\neq a_{q,n}$. If $p=q$, we must have $m\neq n$, hence $m>n$ or $m<n$, so $(a_{p,m},a_{q,n})\in R_{S}$ or $(a_{q,n},a_{p,m})\in R_{S}$. Similarly, when $p\neq q$, we have $p>q$ or $p<q$, so $(a_{p,m},a_{q,n})\in R_{S}$ or $(a_{q,n},a_{p,m})\in R_{S}$. Combining these results, we find that $R$ is total, which is what we wanted. ∎

If $X\subseteq V$, then $f_{S}(X)$ is the set of vertices that are pointed at by $X$, while $g_{S}(X)$ is the set of vertices that point at $X$. From this and Figure 1, the required results follow immediately. ∎

It is clear that $\mathscr{S}_{S}\subseteq\mathscr{B}_{S}$ and that any subuniverse of $\mathbf{F}_{S}$ that extends $\mathscr{S}_{S}$ also extends $\mathscr{B}_{S}$, so it remains to show that $\mathscr{B}_{S}$ is a subuniverse of $\mathbf{F}_{S}$.

By definition, $\mathscr{B}_{S}$ is the set of all finite unions of elements of $\mathscr{S}_{S}$. Thus, $\mathscr{B}_{S}$ is closed under (binary) union and $\varnothing\in\mathscr{B}_{S}$.

By distributivity, to show that $\mathscr{B}_{S}$ is closed under (binary) intersection, we only need to show that $X\cap Y\in\mathscr{B}_{S}$ if $X,Y\in\mathscr{S}_{S}$. Let $p\in\mathbb{Z}$ and let $m\in\mathbb{N}$. If $X\in\mathscr{S}_{S}$, then $A_{p,m}\cap X=\varnothing$ or $A_{p,m}\cap X=A_{p,m}$, hence $A_{p,m}\cap X\in\mathscr{B}_{S}$. Clearly, $U_{p}\cap U_{q}=U_{\max(p,m)}$ and $U_{p}\cap D_{q}=\bigcup\{V_{r}\mid p\leqslant r\leqslant q\}$, for all $q\in\mathbb{Z}$. If $q\in\mathbb{Z}$, $n\in\mathbb{N}$ and $X\in\{S_{q,n},\bar{S}_{q,n}\}$, then we have $U_{p}\cap X=X$ when $q\geqslant p$ and $U_{p}\cap X=\varnothing$ when $q<p$. Thus, $U_{p}\cap X\in\mathscr{B}_{S}$ when $X\in\mathscr{S}_{S}$. If $q\in\mathbb{Z}$, then it is clear that $D_{p}\cap D_{q}=D_{\min(p,q)}$. If $X\in\{S_{q,n},\bar{S}_{q,n}\}$, for some $q\in\mathbb{Z}$ and $n\in\mathbb{N}$, then $D_{p}\cap X=X$ if $q\leqslant p$ and $D_{p}\cap X=\varnothing$ if $q>p$. From this, it follows that $D_{p}\cap X\in\mathscr{B}_{S}$, for all $X\in\mathscr{S}_{S}$. If $q\in\mathbb{Z}$ and $n\in\mathbb{N}$, then we have $S_{p,m}\cap S_{q,n}=S_{p,\max(m,n)}$ when $q=p$ and $S_{p,m}\cap S_{q,n}=\varnothing$ when $q\neq p$. Clearly, $S_{p,m}\cap\bar{S}_{q,n}=\varnothing$, for all $p\in\mathbb{Z}$ and $n\in\mathbb{N}$, so $S_{p,m}\cap X\in\mathscr{B}_{S}$ if $X\in\mathscr{S}_{S}$. If $q\in\mathbb{Z}$ and $n\in\mathbb{N}$, then we have $\bar{S}_{p,m}\cap\bar{S}_{q,n}=S_{p,\max(m,n)}$ when $q=p$ and $\bar{S}_{p,m}\cap\bar{S}_{q,n}=\varnothing$ otherwise, so $\bar{S}_{p,m}\cap X\in\mathscr{B}_{S}$, for all $X\in\mathscr{S}_{S}$. Combining these results, we find that $\mathscr{B}_{S}$ is closed under intersection.

From De Morgan’s laws and the observations above, to show the closure of $\mathscr{B}_{S}$ under forming complements, it will be enough to show that $X^{c}\in\mathscr{B}_{S}$ if $X\in\mathscr{S}_{S}$. As $A_{p,m}^{c}=\bigcup\{A_{p,n}\mid n<m\}\cup U_{p+1}\cup D_{p-1}\cup S_{p,m+1}\cup\bar{S}_{p,m+1}$, $U_{p}^{c}=D_{p-1}$, $D_{p}^{c}=U_{p+1}$, $S_{p,m}^{c}=\bigcup\{A_{p,n}\mid n<m\}\cup\bar{S}_{p,m}\cup U_{p+1}\cup D_{p-1}$ and $\bar{S}_{p,m}^{c}=\bigcup\{A_{p,n}\mid n<m\}\cup S_{p,m}\cup U_{p+1}\cup D_{p-1}$, it follows that $\mathscr{B}_{S}$ is closed under forming complements. As $\varnothing\in\mathscr{B}_{S}$, this result tells us that $V\in\mathscr{B}_{S}$.

By additivity, to show that $\mathscr{B}_{S}$ is closed under $f_{S}$ and $g_{S}$, we only need to check that $f_{S}(X),g_{S}(X)\in\mathscr{B}_{S}$ if $X\in\mathscr{S}_{S}$. This follows from Lemma 3.6, so $\mathscr{B}_{S}$ is indeed a subuniverse of $\mathbf{F}_{S}$, which is what we wanted. ∎

Firstly, assume that $a_{q,1}\in X$. Based on Figure 1, $f_{S}^{2}(X)=D_{q+1}$ and $f_{S}^{4}(X)=D_{q+2}$, which implies that $f_{S}^{4}(X)\cap f_{S}^{2}(X)^{c}=V_{q+2}$. Thus, (1) holds.

Now, assume that we have $a_{q,1}\notin X$. Similarly to the previous case, $f_{S}^{3}(X)=D_{q+1}$ and $f_{S}^{5}(X)=D_{q+2}$, hence $f_{S}^{5}(X)\cap f_{S}^{3}(X)^{c}=V_{q+2}$. Thus, (2) also holds. ∎

By Lemma 3.9(1), we have $\beta(A_{p,1})=V_{p+2}$. So, based on Figure 1, $g_{S}^{2}(\beta(A_{p,1}))=U_{p+1}$. Similarly, $g_{S}^{8}(V_{p+2})=U_{p-2}$ and $g_{S}^{10}(V_{p+2})=U_{p-3}$, hence $f_{S}^{4}(g_{S}^{10}(\beta(A_{p,1})\cap g_{S}^{8}(\beta(A_{p,1}))^{c})=f_{S}^{4}(V_{p-3})=D_{p-1}$. By Lemma 3.6(1), we have $\sigma(A_{p,1})=A_{p,2}$, as claimed.

Next, we will use a (strong) inductive argument for the second claim. By Lemma 3.6(1) and Lemma 3.6(2), $\nu_{3}(A_{p,1})=f_{S}(A_{p,2})\cap f_{S}(A_{p,1})^{c}=A_{p,3}$ and $\nu_{4}(A_{p,1})=f_{S}(A_{p,3})\cap f_{S}(A_{p,2})^{c}=A_{p,3}$ as $\sigma(A_{p,1})=A_{p,2}$. Let $n\geqslant 5$ and assume that $\nu_{m}(A_{p,1})=A_{p,m}$, for all $4\leqslant m\leqslant n$. From this assumption and Lemma 3.6(2), it follows that $\nu_{n+1}(A_{p,1})=f_{S}(A_{p,n})\cap f_{S}(A_{p,n-1})^{c}=A_{p,n+1}$. Thus, $\nu_{m}(A_{p,1})=A_{p,m}$, for all $m\geqslant 3$, as claimed. ∎

Let $\mathscr{V}_{p}$ denote the subuniverse of $\mathbf{B}$ generated by $V_{p}$. By Lemma 3.7, it will be enough to show that $\mathscr{S}_{S}\subseteq\mathscr{V}_{p}$.

Firstly, we claim that $V_{q}\in\mathscr{V}_{p}$, for every $q\in\mathbb{Z}$. Based on Figure 1, Lemma 3.6(3) and Lemma 3.6(5), we have $f_{S}^{2m}(V_{p})=D_{p+m}$, for each $m\in\mathbb{N}$. This implies that $V_{p+m+1}=f_{S}^{2m+2}(V_{p})\cap f_{S}^{2m}(V_{p})^{c}\in\mathscr{V}_{p}$, for every $m\in\mathbb{N}$, hence we have $V_{q}\in\mathscr{V}_{p}$, for every $q\geqslant m+2$. Similarly, if $q\in\mathbb{Z}$ and $m\in\mathbb{N}$, then $g_{S}^{2m}(V_{q})=U_{q-m}$, hence $V_{q-m-1}=g_{S}^{2m+2}(V_{q})^{c}\cap g_{S}^{2m}(V_{q})\in\mathscr{V}_{p}$. Thus, we must have $V_{q}\in\mathscr{V}_{p}$, for all $q\in\mathbb{Z}$, as claimed.

Based on Figure 1, Lemma 3.6(3) and Lemma 3.6(5), $f_{S}^{2}(V_{q-1})=D_{q}$, for each $q\in\mathbb{Z}$. Similarly, we also have $g_{S}^{2}(V_{q+1})=U_{q}$, for every $q\in\mathbb{Z}$. Hence, by the previous result, we have $D_{q},U_{q}\in\mathscr{V}_{p}$, for all $q\in\mathbb{Z}$.

By Lemma 3.6(13) and the previous result, $A_{p,1}=g(U_{q+1})\cap U_{q+1}^{c}\in\mathscr{V}_{p}$, for all $q\in\mathbb{Z}$. So, by Lemma 3.11, we have $A_{p,n}\in\mathscr{V}_{p}$, for all $p\in\mathbb{Z}$ and $n\in\mathbb{N}$.

Based on Lemma 3.6(3), $S_{q,m}=f_{S}(D_{q-1})\cap(\bigcup\{A_{q,n}\mid n<m\}\cup D_{q-1})^{c}$. Hence, by the above results, we must have $S_{q,m}\in\mathscr{V}_{p}$, for all $q\in\mathbb{Z}$ and $m\in\mathbb{N}$.

Clearly, we must have $\bar{S}_{q,m}=(\bigcup\{A_{q,n}\mid n<m\}\cup D_{q-1}\cup U_{q+1}\cup S_{q,m})^{c}$, for all $q\in\mathbb{Z}$ and $m\in\mathbb{N}$. So, based the above results, we must have $\bar{S}_{q,m}\in\mathscr{V}_{p}$, for all $q\in\mathbb{Z}$ and $m\in\mathbb{N}$.

Based on these results, $\mathscr{V}_{p}=\mathscr{B}_{S}$, which is what we wanted to show. ∎

By Lemma 3.7, $X$ and $X^{c}$ can be represented as unions of finite subsets of $\mathscr{S}_{S}$. Clearly, only one of the unions will involve an element of $\{U_{p}\mid p\in\mathbb{Z}\}$. So, based on Figure 1, we have $f_{S}(X)\neq V$ or $f_{S}(X^{c})\neq V$, as required.∎

By Lemma 3.7, $X$ can be represented as the union of a finite subset of $\mathscr{S}$. By assumption, $f_{S}(X)\neq V$, so Lemma 3.6(iii) tells us that such a representation cannot involve an element of $\{U_{p}\mid p\in\mathbb{Z}\}$. Since $X\neq\varnothing$, there is maximal $p\in\mathbb{Z}$ with $V_{p}\cap X\neq\varnothing$, as claimed. ∎

The first statement is an immediate consequence of Lemma 3.7, while (2) is evident from the self similarity of $\langle V;R_{S}\rangle$.

From (1) and (2), it follows that we can define a map $\mu\colon\mathscr{B}_{S}\to\mathscr{B}_{S}$ by setting $\mu(t^{\mathbf{B}}(V_{p}))=t^{\mathbf{B}}(V_{q})$, for every unary term $t$. Combining (1) and (2), we find that $\mu$ is a bijection. Based on (2), $\mu$ is an endomorphism of $\mathbf{B}_{S}$. Thus, $\mu$ is an automorphism of $\mathbf{B}_{S}$, so (3) holds. ∎

By Lemma 3.13 and Łoś’s Theorem, $f(X/\mathscr{U})\neq 1$ or $f(X/\mathscr{U}^{\prime})\neq 1$. Without loss of generality, we can assume that $f(X/\mathscr{U})\neq 1$. By Lemma 3.9 and Lemma 3.14, either $\{i\in I\mid f_{S}^{4}(X(i))\cap f_{S}^{2}(X(i))^{c}=V_{p},\textrm{ for some }p\in\mathbb{Z}\}$ or $\{i\in I\mid f_{S}^{5}(X(i))\cap f_{S}^{3}(X(i))^{c}=V_{p},\textrm{ for some }p\in\mathbb{Z}\}$ is an element of $\mathscr{U}$. Based on Lemma 3.15(3), $\mathbf{B}_{S}$ embeds into the subalgebra of $\mathbf{B}_{S}^{I}/\mathscr{U}$ generated by $X/\mathscr{U}$, as claimed. ∎

It is clear that $\{\varnothing,V\}$ is a subuniverse of $\mathbf{B}_{S}$, and that the corresponding subalgebra of $\mathbf{B}_{S}$ is isomorphic to $\mathbf{T}_{0}$. By Jónsson’s Theorem, $\operatorname{Si}(\operatorname{Var}(\mathbf{T}_{0}))=\operatorname{\mathbb{I}}(\mathbf{T}_{0})$, so by Lemma 3.4, we must have $\operatorname{Var}(\mathbf{T}_{0})\subsetneq\operatorname{Var}(\mathbf{B}_{S})$. Let $\mathcal{V}\in\Lambda_{\textrm{TTA}}$ with $\operatorname{Var}(\mathbf{T}_{0})\subsetneq\mathcal{V}\subseteq\operatorname{Var}(\mathbf{B}_{S})$. Clearly, $\operatorname{Si}(\mathcal{V})\subseteq\operatorname{Si}(\operatorname{Var}(\mathbf{B}_{S}))$. By Proposition 2.7(3), $\operatorname{Si}(\operatorname{Var}(\mathbf{B}_{S}))=\operatorname{\mathbb{ISU}}(\mathbf{B}_{S})$, hence $\operatorname{Si}(\mathcal{V})\subseteq\operatorname{\mathbb{ISU}}(\mathbf{B}_{S})$. Since $\operatorname{Var}(\mathbf{T}_{0})\subsetneq\mathcal{V}$, there is some $\mathbf{A}\in\operatorname{Si}(\mathcal{V})$ with more than 2 elements. By Lemma 3.16, $\mathbf{B}_{S}$ embeds into $\mathbf{A}$, so $\mathbf{B}_{S}\in\mathcal{V}$, hence $\mathcal{V}=\operatorname{Var}(\mathbf{B}_{S})$. Thus, $\operatorname{Var}(\mathbf{B}_{S})$ is a cover of $\operatorname{Var}(\mathbf{T}_{0})$ in $\boldsymbol{\Lambda}_{\textrm{TTA}}$, as required. Based on these arguments, it is evident that $\operatorname{Var}(\mathbf{B}_{S})$ is also join-irreducible. ∎