1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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.)

$\endgroup$

You must log in to answer this question.

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