What is the smallest equivalence relation containing two equivalence relations

Question

I'm struggling with the following problem: Given two equivalence relations $q,s$ on set $X$. Prove that there exists the smallest (in a sense of inclusion) equivalence relation $r$ such that $g \cup s \subset r$. I was thinking about $r= q \circ s \cup s \circ q \cup q \cup s$ but I'm not sure how to prove that it's the smallest such relation. Any help will be greatly apprecieted.

Answer 1

The relation you propose need not be an equivalence relation. To see that, let $q$ be the equivalence relation on $\mathbb{N}$ given by the partition $$\Bigl\{ \{1,2\}, \{3,4\}, \{5,6\},\ldots\Bigr\}$$ and let $s$ be the equivalence relation given by the partition $$\Bigl\{ \{1\}, \{2,3\}, \{4,5\},\ldots\Bigr\}.$$ The relation $$(q\circ s)\cup (s\circ q)\cup q\cup s$$ does not contain $(1,4)$: this pair is not in $q$, is not in $S$, is not in $q\circ s$ (which only contains pairs of the form $(a,b)$ when there exists $c$ such that $(a,c)\in q$ and $(c,b)\in s$; no such element exists for $1$ and $4$), nor in $s\circ q$. Yet clearly any equivalence relation that contains both $q$ and $s$ must make $1$ and $4$ equivalent, since $1$ is $q$-equivalent to $2$, which is $s$-equivalent to $3$, which is $q$-equivalent to $4$. In fact, your set contains $(1,2)$, $(2,3)$, and $(3,4)$, but not $(1,4)$, so it is not transitive. In this case, the smallest equivalence relation that contains both $q$ and $s$ is the total relation.

There is a very easy top-down solution:

1. Show that the intersection of an arbitrary nonempty family of equivalence relations on $X$ is an equivalence relation on $X$.
2. Show that there is at least one equivalence relation on $X$ that contains both $q$ and $s$.
3. Take $r$ to be the intersection of all equivalence relations on $X$ that contain $q$ and $s$.

Then by 1 and 2 you have that $r$ is an equivalence relation; it is easy to use 3 to show it contains $q$ and $s$; and then 3 also shows that $r$ is the smallest equivalence relation on $X$ that contains $q$ and $s$.

The bottoms-up description is harder. Basically, you want to show that $r$ consists of all pairs $(a,b)\in X\times X$ for which there exists a finite sequence $a_1,a_2,\ldots,a_n$ of elements of $X$ such that $$(a,a_1)\in q,\ (a_1,a_2)\in s,\ (a_2,a_3)\in q,\ldots, (a_n,b)\in t$$ where $t=q$ if $n$ even, and $t=s$ if $n$ is odd.