1

Suppose $R_1, R_2$ are both equivalence relations defined on nonempty set $A$. Prove or disprove: $R_1 \cap R_2$ is an equivalence relation.

What method (if any) would you take to prove this in as few sentences as possible?

Martin Sleziak
  • 53,687
NaN
  • 1,417
  • 4
    Do you have a way to prove it with a large number of sentences? If so, please tell us. – Trevor Wilson Nov 01 '13 at 02:40
  • I'm not sure I understand what $R_1 \bigcap R_2$ would mean. Suppose I take $R_1$ on the integers as congruence mod 5; and $R_2$ as congruence mod 6. What would their intersection be? – Betty Mock Nov 01 '13 at 02:47
  • 1
    @BettyMock Congruence mod 30. – Did Nov 01 '13 at 02:49
  • @BettyMock A (binary) relation is usually formalized as a set of ordered pairs: $x \mathbin{R} y$ means $(x,y) \in R$. In this case we literally take the intersection of the two sets. – Trevor Wilson Nov 01 '13 at 03:04
  • @TrevorWilson No, sorry. – NaN Nov 01 '13 at 04:05
  • @Did: I believe Betty Mock wanted Necron to answer her question. – bof Nov 01 '13 at 04:06
  • The method is sometimes called "following your nose". – bof Nov 01 '13 at 04:08
  • @BettyMock, if $R_1, R_2$ are defined on $\mathbb{Z}$. Then for distinct $a, b \in \mathbb{Z}$, then $a\ R_1\ b \Leftrightarrow a \equiv b (\mod{5})$, and for all distinct $a, b \in \mathbb{Z}$, $a\ R_2\ b \Leftrightarrow a \equiv b (\mod{6})$. Considering both cases $5 \mid (a-b)$ and $6 \mid (a-b)$. This is only possible (without proof) if $5\cdot 6 \mid (a - b)$. Is this correct? – NaN Nov 01 '13 at 04:09
  • @BettyMock: See my answer for a way to interpret $R_1\cap R_2$ that may be more compatible with what you're used to. – Cameron Buie Nov 01 '13 at 04:13
  • @bof Maybe, maybe not. – Did Nov 01 '13 at 08:59

1 Answers1

5

Let $R=R_1\cap R_2.$ You must show the following:

  • For any $a\in A,$ $\langle a,a\rangle\in R.$ ($R$ is reflexive on $A$.)
  • For any $a,b\in A$, if $\langle a,b\rangle \in R,$ then $\langle b,a\rangle\in R.$ ($R$ is symmetric on $A$.)
  • For any $a,b,c\in A$, if $\langle a,b\rangle,\langle b,c\rangle\in R,$ then $\langle a,c\rangle\in R$. ($R$ is transitive on $A$.)

Each step can be proved very directly and straightforwardly, since $R_1,R_2$ are equivalence relations on $A$. Let me prove symmetry to give you a taste of it.

Suppose that $a,b\in A$ such that $\langle a,b\rangle\in R.$ Then $\langle a,b\rangle\in R_1,$ so since $R_1$ is symmetric on $A$, then $\langle b,a\rangle\in R_1.$ Likewise, $\langle b,a\rangle\in R_2,$ so $\langle b,a\rangle\in R_1\cap R_2=R.$

Alternately, if you're not used to thinking of binary relations as sets of ordered pairs, we can proceed as follows.

We still let $R=R_1\cap R_2.$ By this, we mean that $a\:R\:b$ if and only if $a\:R_1\:b$ and $a\:R_2\:b.$ Then we need to show the following:

  • For any $a\in A,$ $a\:R\:a.$
  • For any $a,b\in A$, if $a\:R\:b,$ then $b\: R\: a.$
  • For any $a,b,c\in A$, if $a\: R\: b$ and $b\:R\:c,$ then $a\:R\:c$.

Each step is again straightforward, and very similar to the approach that would be taken above. Once again, I'll prove symmetry.

Suppose that $a,b\in A$ such that $a\:R\:b.$ Then $a\:R_1\:b,$ so since $R_1$ is symmetric, then $b\:R_1\:a.$ Likewise, $b\:R_2\:a,$ so $b\:R\:a$ by definition of $R=R_1\cap R_2.$

Cameron Buie
  • 102,994
  • Thinking of binary relations as sets of ordered pairs is how I intuitively think of relations. – NaN Nov 01 '13 at 04:11