Skip to main content
2 of 2
typos

Cyclic relation algebra

A relation algebra $\mathbf{R}$ is a structure $\langle |\mathbf{R}|, \vee, \neg, \circ, I, (-)^{op} \rangle$ such that:

  • $\langle |\mathbf{R}|, \vee, \neg \rangle$ is a Boolean algebra,
  • $\langle |\mathbf{R}|, \circ, I, (-)^{op} \rangle$ is a monoid with involution satisfying: $(p \circ q)^{op} = q^{op} \circ p^{op}$
  • involution $(-)^{op}$ preserves $\vee$, that is: $(p \vee q)^{op} = p^{op} \vee q^{op}$
  • $\circ$ preserves $\vee$, that is: $(p \vee q) \circ r = p \circ r \vee q \circ r$
  • Tarski axiom holds: $(p^{op} \circ \neg (p \circ q)) \vee \neg q = \neg q$

An example of a relation algebra is the algebra of all binary sub-relations of a given equivalence relation.

Let us say that an element $p$ of a relation algebra is cyclic if the set $\{p^k \colon k \in \mathcal{N} \}$ is finite (where $p^k$ is the $k$-fold composition $\circ$ of $p$). Let us call a relation algebra cyclic if each of its elements is cyclic.

An example of a cyclic relation algebra is a finite relation algebra.

Does there exist an infinite cyclic relation algebra generated by a finite number of elements?