Let $\{\alpha_i \mid i\in \mathbb N\}$ is family of equivalence relations on the set $A$ such that for every $i \in N$ $\alpha_i\subseteq\alpha_{i+1}$. Prove that the union of all $\alpha_i$ is equivalence relation on $A$.

Whenever there are problems involving family of relations I'm clueless. I know that we obviously need to prove reflexivity,symmetry and transitivity but other than that I can't even begin.

  • 1
    $\begingroup$ I guess you forgot to mention that all the $\alpha_i$ are equivalence relations. (Otherwise there are trivial counterexamples.) $\endgroup$ – Stefan Mesken Nov 16 '17 at 17:25
  • $\begingroup$ I also thought that they are supposed to be. But nowhere in the question it is stated that they are also equivalence relations.That's why I was mostly clueless about how to begin(It's an old exam question). $\endgroup$ – DreaDk Nov 16 '17 at 17:30
  • $\begingroup$ Well, that must be a mistake. Before looking at my hint: Can you proof this assuming that all the $\alpha_i$ are equivalence relations? $\endgroup$ – Stefan Mesken Nov 16 '17 at 17:31
  • $\begingroup$ I also fixed the formatting of your post. For the future, here is a MathJax tutorial. $\endgroup$ – Stefan Mesken Nov 16 '17 at 17:33
  • $\begingroup$ I would perhaps be able to prove some of it. But the whole idea of family of sets/relations is a bit confusing to me (mainly cause I haven't encountered it much) $\endgroup$ – DreaDk Nov 16 '17 at 17:33

The proof is really straightforward and one of those 'let use make sure you understand the definition' kind of exercises. I'll get you started and then you'll pick it up from there:

Let's proof that $\alpha := \bigcup \{ \alpha_i \mid i \in \mathbb N \}$ is transitive - reflexivity and symmetry are even easier:

Let $x,y,z \in A$ such that $(x,y) \in \alpha$ and $(y,z) \in \alpha$. Then there are, by the definition of $\alpha$, $i,j \in \mathbb N$ such that $(x,y) \in \alpha_{i}$ and $(y,z) \in \alpha_j$. Let $k = \max\{i,j\}$. Then $\alpha_i, \alpha_j \subseteq \alpha_k \subseteq \alpha$ and thus $(x,y),(y,z) \in \alpha_k$.

Now we use the fact that $\alpha_k$ is an equivalence relation to conclue that $(x,z) \in \alpha_k$. Since $\alpha_k \subseteq \alpha$, it follows that $(x,z) \in \alpha$ and thus that $\alpha$ is transitive.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.