Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am a bit stuck on this one question from my homework and for some reason it isn't making any sense to me. I would really appreciate it if somebody could explain it to me how I can go about to solving it.

Suppose that $\sim_1$ and $\sim_2$ are equivalence relations on the set $S$. Define a new relation $\sim_v$ so that $$a \sim_v b \Leftrightarrow a\sim_1 b \vee a\sim_2 b.$$

Is $\sim_v$ always an equivalence relation? (Specifically, it is true that for every pair of equivalence relations $\sim_1$ and $\sim_2$ the relation $\sim_v$ is an equivalence relation?) If so, prove it. If not, give an example where it fails and explain why it fails for your example.

share|improve this question
1  
My approach here would be attempt to prove that $\sim_v$ is an equivalence relation, and see if this goes badly wrong at any point. Either your proof succeeds, or you should see where the problem is, helping you to construct a counterexample. –  Matt Pressland Jan 28 '13 at 14:43
1  
You can have $a\sim_1b$ and $b\sim_2 c$ but neither $a\sim_1c$ nor $a\sim_2c$ so you might not have the transitive property. –  Sigur Jan 28 '13 at 14:43
1  
To show that it's an equivalence relation, you need to show 3 properties, do you know what they are? –  Guest 86 Jan 28 '13 at 14:46

2 Answers 2

up vote 2 down vote accepted

Jason Bourne has given a concrete example, but I think that it might be helpful to see the approach that Matt Pressland suggested in the comments. Suppose that $S,\sim_1,\sim_2$, and $\sim_v$ are as given; we’ll try to prove that $\sim_v$ is an equivalence relation on $S$ and see what happens.

  • Reflexivity: If $x\in S$, then $x\sim_1 x$, so $x\sim_v x$. Thus, $\sim_v$ is reflexive.

  • Symmetry: If $x,y\in S$ and $x\sim_v y$, then $x\sim_1 y$ or $x\sim_2 y$. Without loss of generality $x\sim_1 y$; but then $y\sim_1 x$, so $y\sim_v x$, and $\sim_v$ is symmetric.

  • Transitivity: Suppose that $x,y,z\in S$ and $x\sim_v y\sim_v z$. Then $x\sim_i y$ for at least one $i\in\{1,2\}$, and $y\sim_j z$ for at least one $j\in\{1,2\}$. If we can choose $i$ and $j$ to be equal, we’re in business: if $x\sim_1 y\sim_1 z$, for instance, then $x\sim_1 z$ by transitivity of $\sim_1$, and therefore $x\sim_v z$. But what if we can’t choose $i$ and $j$ to be equal? What if $x\sim_1 y\sim_2 z$, $x\not\sim_2 y$, and $y\not\sim_1 z$? Then there’s no obvious guarantee that either $x\sim_1 z$ or $x\sim_2 z$. It’s conceivable, of course, that there’s some guarantee that isn’t obvious, but there’s so little here to work with that it doesn’t really seem likely. At this point a better bet is to try to find a specific counterexample: a set $S$ and equivalence relations $\sim_1$ and $\sim_2$ on $S$ such that $\sim_v$ is not transitive.

This can be done in a very visual way if you understand the connection between equivalence relations on $S$ and partitions of $S$. Consider a four-element set:

$$\begin{array}{|cc|} \hline a&b\\ c&d\\ \hline \end{array}\tag{1}$$

I can partition it into rows to get

$$\begin{array}{|cc|} \hline a&b\\ \hline c&d\\ \hline \end{array}\;;$$

the associated equivalence relation $\sim_1$ has $x\sim_1 y$ if and only if $x$ and $y$ are in the same row of $(1)$.

I can also partition it into columns to get

$$\begin{array}{|c|c|} \hline a&b\\ c&d\\ \hline \end{array}\;;$$

the associated equivalence relation $\sim_2$ has $x\sim_2 y$ if and only if $x$ and $y$ are in the same column of $(1)$.

Now $x\sim_v y$ if and only if $x$ and $y$ are in the same row or the same column of $(1)$. Thus, $a\sim_v a$, $a\sim_v b$, and $a\sim_v c$, but $a\not\sim_v d$. In fact, $x\sim_v y$ if and only if $x$ and $y$ are not the two ends of a diagonal in $(1)$. Thus, $a\sim_v b\sim_v d$, but as we already saw, $a\not\sim_v d$.


Recall that $\sim_1,\sim_2$, and $\sim_v$ are actually subsets of $S\times S$. In fact, $\sim_v=\sim_1\cup\sim_2$. This is a bit hard to read, so let me replace the names $\sim_1,\sim_2$, and $\sim_v$ by $E_1,E_2$, and $E_v$, respectively, and write $E_v=E_1\cup E_2$. This exercise shows that the union of two equivalence relations is not necessarily an equivalence relation. (The intersection of two equivalence relations, on the other hand, always is an equivalence relation; if you’ve not done so, you might find it a useful exercise to prove this.) For any equivalence relations $E_1$ and $E_2$ on a set $S$ there is a smallest equivalence relation $E$ on $S$ such that $E_1\cup E_2\subseteq E$, but it usually isn’t simply $E_1\cup E_2$. It turns out that $xEy$ if and only if for some $n$ there are $x_0,\dots,x_n\in S$ such that $x_0=x$, $x_n=y$, and $x_{k-1}(E_1\cup E_2)x_k$ for $k=1,\dots,n$. In other words, $xEy$ if and only if you can get from $x$ to $y$ be a finite chain of steps, each of which takes you from an element $x_{k-1}$ of $S$ to an element $x_k$ that is related to $x_{k-1}$ by at least one of the two equivalence relations $E_1$ and $E_2$.

In the little example above, for instance, there is such a path from $a$ to any of the four elements of the set, so $a$ is related to $a,b,c$, and $d$. In fact, in this simple example $E$ turns out to be the trivial equivalence relation $S\times S$: everything in $S$ is $E$-related to everything in $S$. Equality is the equivalence relation on $S$ that makes the most distinctions: each element of $S$ gets its own equivalence class. The trivial equivalence relation $S\times S$ is the one that makes the fewest: it lumps all of $S$ into a single equivalence class.

share|improve this answer
    
Thank you so much for explaining it!!! :) –  Somebody Jan 28 '13 at 22:18
    
@Mohamed: You’re very welcome. –  Brian M. Scott Jan 28 '13 at 22:18
    
I'm also wondering, would this be also similar for the relation if suppose instead of it being ~v, it was ~/\. (Sorry for the strange symbols, not really sure how to do the fancy version, but that upside down V is the "and" symbol. Or would it hold, because for it to be a relation, it would have to hold for when it is a ~1 b ~2 c and a ~2 b ~1 c? –  Somebody Jan 28 '13 at 22:41
1  
@Mohamed: You mean defining $x\sim_{\land}y$ if and only if $x\sim_1 y$ and $x\sim_2 y$? Yes, that’s an equivalence relation. In fact, it’s the one that I suggested you might want to try to prove: it’s the intersection of $\sim_1$ and $\sim_2$. –  Brian M. Scott Jan 28 '13 at 22:53

Define $\sim_1$ on the set of integers such that $a\sim_1 b$ if and only if $b-a$ is divisible by $2$.

Define $\sim_2$ on the set of integers such that $a\sim_2 b$ if and only if $b-a$ is divisible by $3$.

Define $\sim_v$ on the set of integers such that $a\sim_v b$ if and only if $a\sim_1 b$ or $a\sim_2 b$.

Verify that the first two are equivalence relations but the last is not as it is not transitive.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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