Fix a set X and consider the collection of all symetric relations on it. I also assume that the empty relation is by definiyion symmetric. Well, it is true that the above collection forms a complete atomic boolean algebra?

It forms a complete lattice. Moreover the atoms are of the form $\{(x,x)\}$ and $\{(x,y),(y,x)\}$. So, I expect that the collection is clearly atomic. I'm able to find a complement for any symmetric relation, and moreover unions of symmetric relations are also symmetric. Is my argument correct?

Does the same hold for preorders?


1 Answer 1


The intersection and the union of two symmetric relations is a symmetric relation. In addition, the complement of a symmetric relation $R$, i.e. the relation $\mathcal{P}(X \times X) \setminus R$ is symmetric. Therefore the set of all symmetric relations on $X$ is a Boolean subalgebra of the Boolean algebra $\mathcal{P}(X \times X)$ of all binary relations on $X$.

Because arbitrary intersections and unions of families of symmetric relations are symmetric, it is a complete Boolean subalgebra. It is atomic because each non-empty symmetric relation $R$ contains some pair $\langle a, b \rangle$ and therefore $\{ \langle a, b \rangle, \langle b, a \rangle \} \subseteq R$. As you observe, every symmetric relation of the form $\{ \langle a, b \rangle, \langle b, a \rangle \}$ is an atom of the lattice of all symmetric relations on $X$.

This is not true for preorders. The intersection of an arbitrary family of preorders is a preorder, but the union $R \cup S$ of two preorders $R$ and $S$ is typically not a preorder. Nonetheless, for each relation $T$ there is a smallest preorder which contains $T$, namely the reflexive transitive closure of $T$. Therefore, preorders on $X$ form a complete lattice where arbitrary meets are computed as intersections and arbitrary joins are computed as the reflexive transitive closure of the union. (For joins of non-empty families of preorders, it suffices to take the transitive closure rather than the reflexive transitive closure, since the union is already a reflexive relation.)

This lattice is not distributive, i.e. it does not satisfy $x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)$. In particular, it is not a Boolean algebra. One way to see that it is not distributive is to observe that it contains the lattice of equivalence relations on $X$ as a sublattice and to observe that the lattice of equivalence relations on $X$ fails to be distributive even if $X$ is a three-element set. (The lattice of equivalence relations is also called the partition lattice.)


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .