1 Introduction

In a recent paper [9, 1.10], Maddux defined the variety \(V=\mathbf{H}\mathbf{S}\mathbf{P}\,\mathsf{RRA}^c\), where \(\mathsf{RRA}\) is the variety of representable relation algebras and \(\mathsf{RRA}^c=\{\mathfrak {A}^c:\mathfrak {A}\in \mathsf{RRA}\}\). Here, \(\mathfrak {A}^c\) denotes the completion of the relation algebra \(\mathfrak {A}\). For details of these notions and further ones used below, see the very attractive introduction to [9].

In [9, problem 1.1(3)], Maddux asked whether V is closed under canonical extensions.

Theorem 1.1

V and \(\mathbf{S}\,\mathsf{RRA}^c\) are closed under canonical extensions.

Proof

By [4, theorem 3.8], if \(\mathsf K\) is a class of relation algebras that is closed under ultraproducts, and \(\mathsf{K}^c=\{\mathfrak {A}^c:\mathfrak {A}\in \mathsf{K}\}\), then \(\mathbf{S}\,\mathsf{K}^c\) and \(\mathbf{H}\mathbf{S}\mathbf{P}\,\mathsf{K}^c\) are both closed under canonical extensions. Theorem 1.1 follows by taking \(\mathsf{K}=\mathsf{RRA}\), which is a variety and so closed under ultraproducts. \(\square \)

RA denotes the class of all relation algebras. Using the known facts that RA is closed under completions [10] but RRA is not [7], Maddux noted that

$$\begin{aligned} \mathsf{RRA}\subsetneq V\subseteq \mathsf{RA}, \end{aligned}$$

and he showed that V contains a number of non-representable ‘Monk algebras’, so that the gap between \(\mathsf{RRA}\) and V is substantial. In [9, problem 1.1(1)], he asked whether \(V=\mathsf{RA}\). This was answered negatively by Andréka and Németi [1], where it is shown that in fact there are continuum-many varieties lying between V and \(\mathsf{RA}\). That might suggest that V is ‘nearer’ to \(\mathsf{RRA}\) than to \(\mathsf{RA}\), but as ‘evidence’ in the other direction, we show below that \(\mathsf{RRA}\) is not finitely axiomatisable over V.

2 \(\mathsf{RRA}\) is not finitely axiomatisable over V

It suffices to show that RRA contains an ultraproduct of algebras in \(V{\setminus }\mathsf{RRA}\). To this end, we use a construction from [6] of relation algebras from graphs.

2.1 Graphs

Graphs here are undirected and loop-free. Let G be a graph whose set of nodes is N, say. Recall that a cycle of length\(l\ge 3\)inG is a subset \(\{v_0,\dots {},v_{l-1}\}\subseteq N\) of size l such that \((v_i,v_{(i+1)\bmod l})\) is an edge of G for each \(i<l\). A subset \(X\subseteq N\) is said to be independent if no pair of nodes in X is an edge of G. The chromatic number\(\chi (G)\) of G is the least natural number n such that N is the union of n (possibly empty) independent sets, and \(\infty \) if there is no such n. It is well known (see, e.g., [2, 1.6.1]) that \(\chi (G)\le 2\) iff G has no cycles of odd length. We let \(+\) and \(\sum \) denote disjoint union of graphs. Then if \(G_i\)\((i\in I)\) are graphs, \(\chi (\sum _{i\in I}G_i)\) is the least upper bound (possibly \(\infty \)) of \(\{\chi (G_i):i\in I\}\).

Let n be a positive integer. Let \(K_n\) be a complete graph with precisely n nodes. Clearly, \(\chi (K_n)=n\). Let \(E_n\) be a graph with \(\chi (E_n)\ge n\) and with no cycles of length at most n—finite examples were constructed by Erdős [3].

We use these graphs to construct some infinite graphs (\(G^k_n\), \(G^k\), \(G^\omega \)), and compute their chromatic numbers. First define

$$\begin{aligned} G^0_n&= \sum _{m\ge n}E_m, \end{aligned}$$
(2.1)
$$\begin{aligned} G^k_n&= G^0_n+K_k \quad \text{ if } 0<k<\omega . \end{aligned}$$
(2.2)

Since \(\{\chi (E_m):m\ge n\}\) is unbounded, each \(G^k_n\) has chromatic number \(\infty \).

Next, fix a non-principal ultrafilter D over \(\omega {\setminus }1\). Define the ultraproduct

$$\begin{aligned} G^k=\prod _D \{G^k_n:0<n<\omega \}, \quad \text{ for } \text{ each } k<\omega . \end{aligned}$$
(2.3)

First consider the case when \(k=0\). Observe that \(G^0_n\) in (2.1) has no cycles of length\({}\le n\). Now for each \(l\ge 3\), the property of having no cycles of length l can be expressed by a first-order sentence, and is true for all but finitely many \(G^0_n\). So by Łoś’s theorem, \(G^0\) in (2.3) has no cycles of length l. This holds for each l, so in fact \(G^0\) has no cycles at all, and hence \(\chi (G^0)\le 2\).

What about \(\chi (G^k)\) for \(k>0\)? By standard ultraproduct considerations,

$$\begin{aligned} G^k\cong G^0+K_k, \end{aligned}$$

so we further obtain \(\chi (G^k)=\max (\chi (G^0),\chi (K_k))\le \max (2,k)<\infty \).

Finally let

$$\begin{aligned} G^\omega =\prod _D\{G^k:0<k<\omega \}. \end{aligned}$$
(2.4)

For each \(m>0\), \(K_m\) embeds into \(G^k\) for every \(k\ge m\). It follows by Łoś’s theorem that \(K_m\) embeds into \(G^\omega \), so plainly, \(\chi (G^\omega )\ge m\). This holds for every m, so \(\chi (G^\omega )=\infty \).

2.2 Relation algebras from graphs

Let G be an infinite graph with set of nodes N. We write \(N\times 3\) for the set \(N\times \{0,1,2\}\), and \(G\times 3\) for the graph whose set of nodes is \(N\times 3\) and where ((v, i), (w, j)) is an edge of \(G\times 3\) iff \(i\ne j\) or (v, w) is an edge of G. In simple words, \(G\times 3\) consists of three disjoint copies of G, with all possible edges added between the copies.

We now define a relation algebra atom structure isomorphic to one in [6, section 4] and [5, chapter 14]. We stipulate that \(A=(N\times 3)\cup \{1^{\mathrm{'}}\}\), \(I=\{1^{\mathrm{'}}\}\), \({\breve{x}}=x\) for every \(x\in A\), and for each \(x,y,z\in A\), C(x, y, z) holds iff

  1. (1)

    one of x, y, z is \(1^{\mathrm{'}}\) and the other two are equal, or

  2. (2)

    \(\{x,y,z\}\subseteq N\times 3\) and \(\{x,y,z\}\) is not independent (in the graph \(G\times 3\)).

One can check that for any graphs \(G_n\)\((0<n<\omega )\),

$$\begin{aligned} \alpha \left( \prod _DG_n \right) \cong \prod _D\alpha (G_n). \end{aligned}$$
(2.5)

We write \(\mathfrak {A}(G)\) for the complex algebra of \(\alpha (G)\) (see [9, 1.13]). By [8, lemma 6.2], \(\mathfrak {A}(G)\) is a relation algebra; of course it is atomic and its atom structure is \(\alpha (G)\). We will need the following fact about it, from [6, theorems 10–11] or [5, theorems 14.12–13] or (for \(\Leftarrow \)) [5, exercise 14.2(7)]. It uses our assumption that G is infinite.

Fact 2.1

\(\mathfrak {A}(G)\in \mathsf{RRA}\) if and only if \(\chi (G)=\infty \).

2.3 Why \(\mathsf{RRA}\) is not finitely axiomatisable over V

Let \(k<\omega \). For \(0<n<\omega \), we saw that \(\chi (G^k_n)=\infty \), so \(\mathfrak {A}(G^k_n)\in \mathsf{RRA}\) by fact 2.1. Define the ultraproduct

$$\begin{aligned} \mathfrak {A}^k=\prod _D\{\mathfrak {A}(G^k_n):0<n<\omega \}. \end{aligned}$$
(2.6)

Then \(\mathfrak {A}^k\in \mathsf{RRA}\), since \(\mathsf{RRA}\) is a variety and closed under ultraproducts. So by definition of V,

$$\begin{aligned} \mathfrak {C}^k\,=(\mathfrak {A}^k)^c\in V. \end{aligned}$$

By Łoś’s theorem, \(\mathfrak {A}^k\) is atomic. So (e.g., [5, remark 2.67]) its completion \(\mathfrak {C}^k\) is isomorphic to the complex algebra of the atom structure of \(\mathfrak {A}^k\). This atom structure is \(\prod _D\alpha (G^k_n)\cong \alpha (\prod _DG^k_n)=\alpha (G^k)\) by (2.6, 2.5, 2.3). Hence, \(\mathfrak {C}^k\cong \mathfrak {A}(G^k)\). We saw that \(\chi (G^k)<\infty \), so by fact 2.1, \(\mathfrak {C}^k\notin \mathsf{RRA}\).

Finally let \(\mathfrak {C}\) be the ultraproduct \(\prod _D\{\mathfrak {C}^k:0<k<\omega \}\). As before, this is an atomic relation algebra with atom structure isomorphic to \(\prod _D\alpha (G^k)\cong \alpha (\prod _DG^k)=\alpha (G^\omega )\), so its completion \(\mathfrak {C}^c\) is isomorphic to \(\mathfrak {A}(G^\omega )\). But \(\chi (G^\omega )=\infty \), so \(\mathfrak {A}(G^\omega )\in \mathsf{RRA}\) by fact 2.1. Then \(\mathfrak {C}\subseteq \mathfrak {C}^c\in \mathsf{RRA}\), and as RRA is closed under subalgebras, we obtain \(\mathfrak {C}\in \mathsf{RRA}\).

We can now prove our main theorem.

Theorem 2.2

\(\mathsf{RRA}\) is not finitely axiomatisable over V.

Proof

We have shown that \(\mathfrak {C}^k\in V{\setminus }\mathsf{RRA}\) for \(k>0\), and \(\mathfrak {C}=\prod _D\mathfrak {C}^k\in \mathsf{RRA}\). It follows by Łoś’s theorem that \(\mathsf{RRA}\) is not finitely axiomatisable over V. \(\square \)