I got this little algebra exercise which I am struggling with. My problem is probably that I am a beginner in working with relations and lattices, so I will appreciate any help.
Let $Eq(X)$ be the lattice of equivalence relations on a set $X$.
The question:
Show that for all $α, β \in Eq(X): α \circ β \subseteq α \vee β$, but that equality does not hold in general.
My thoughts:
Suppose $\langle a, b \rangle \in \alpha \circ \beta$. I will show that then it is also in $\alpha \vee \beta$. Then I will show that the opposite direction is not true.
LHS: By definition of the relational product, there is a $c \in X$ such that $\langle a, c \rangle \in \alpha$ and $\langle c, b \rangle \in \beta$. This is just a different notation for saying $a \: \alpha\: c$ and $c\:\beta\: b$.
RHS: If $\langle a, b \rangle \in \alpha \lor \beta$ then there is a $c$ such that $\langle a, c \rangle \in \alpha$ or $\langle c, b \rangle \in \beta$.
This immediately shows that the RHS has a "weaker condition" or "subset of conditions" of the LHS, so if the LHS holds for something, it automatically holds for the RHS as well.
However, reversing the direction, If $\langle a, b \rangle \in \alpha \lor \beta$ then there is a $c$ such that $\langle a, c \rangle \in \alpha$ \textbf{or} $\langle c, b \rangle \in \beta$, but that does not imply that $\langle a, c \rangle \in \alpha$ \textbf{and} $\langle c, b \rangle \in \beta$. Therefore $\alpha \lor \beta \nsubseteq \alpha \circ \beta$.
Is this proof correct? I am not very sure and it seems suspiciously simple.
Any thoughts? Thank you very much.
The problem is with your definition of α ∨ β. The correct definition is:
(x , y) ∈ α ∨ β iff ∃ n ∈ ℕ, ∃ c₀, c₁, …, cₙ such that x α c₀ β c₁ α ⋯ cₙ β y.
(See update below for alternative, equivalent definition.)
With the correct definition, the proof is straightforward.
By definition, (x , y) ∈ α ∘ β iff ∃ c such that x α c β y.
So take n = 0 and c₀ = c to see that (x , y) ∈ α ∨ β.
On the other hand, by concrete counterexample, you can show that α ∨ β ⊈ α ∘ β.
If you can't think of one on your own, play around with these equivalence relations on the set {0, 1, 2, 3}:
α = {(0, 0), (0,1), (1,0) (1,1), (2,2), (2,3), (3,2), (3,3)}
β = {(0, 0), (1,1), (1,2), (2,1), (2,2), (3,3)}
(and look at the pair (0,3))
Update As Adayah points out, an equivalent definition is that α ∨ β is the smallest equivalence relation containing α and β.
To solve the problem with this definition, suppose (x , y) ∈ α ∘ β. Let c be such that x α c β y. Then, (x , c) ∈ α ⊆ α ∨ β and (c , y) ∈ β ⊆ α ∨ β. Therefore, x (α ∨ β) c (α ∨ β) y, so by transitivity, (x , y) ∈ α ∨ β.