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 having difficulties understanding how do I perform set operation like union or intersection on Relations.

In a question, I am asked to prove/disprove:

  • If R & S are symmetric, is $R \cap S$ symmetric?
  • If R & S are transitive, is $R \cup S$ transitive?

How do I do that? 1st, how does $R \cap S$ or $R \cup S$ look like? How can I write a formal prove/disprove for it? I am very bad at these proves ...

share|improve this question
    
See Intersection of Symmetric Relations is Symmetric at ProofWiki. –  Martin Sleziak Sep 18 '12 at 14:57
2  
Remember that (in the usual set-based formalism) a relation $R$ is simply a set of ordered pairs: $R=\{(x,y)\mid x\mathrel{R} y\}$ by definition. So $R\cap S$ is the realation such that $x\mathrel{(R{\cap}S)} y$ iff $x\mathrel{R}y \land x\mathrel{S}y$. –  Henning Makholm Sep 18 '12 at 14:57
add comment

3 Answers

A binary relation is nothing but a set of ordered pairs, where instead of $(x,y) \in R$ we usually write $x\, R\,y$. Now you have to use the definition of 'symmetic' and $\cap$ (resp. transitive and $\cup$) to show these properties hold or give an example where it doesn't hold. I will show you what I mean using another statement:

  • If $R$ and $S$ are symmetric, $R \cup S$ is.

Proof. Let $x \ (R \cup S) \ y$, which means $(x,y ) \in R \cup S$. If $(x,y) \in R$, we have $x \ R \ y$, so $y \ R \ x$ by symmetry, so $(y,x) \in R \subseteq R \cup S$. If on the other side $(x,y) \in S$, it holds $x \ S \ y$, so $y \ S \ x$ by symmetry, so $(y,x) \in S \subseteq R \cup S$.

  • If $R$ and $S$ are transitive, $R \setminus S$ is.

This is false, a counterexample is given by $R = \{0,1\}^2$ and $S = \{(0,0), (1,1)\}$. $R$ and $S$ are (obviously) transitive, but $(0,1), (1,0) \in R \setminus S$ and $(0,0) \not\in R \setminus S$. So $R\setminus S$ isn't transitive.

share|improve this answer
add comment

Other answers have already discussed symmetry.

An example of transitive $R$ and $S$ with non-transitive $R \cup S$ can be obtained by taking $$ R = \{(1,2),(2,1)\} $$ and $$ S = \{(2,3),(3,2)\}. $$ In $R \cup S$, we have $(1,2)$ and $(2,3)$, but not $(1,3)$ (that is, $1$ is related to $2$ and $2$ is related to $3$, but $1$ is not related to $3$).

The trick is set up $R$ and $S$ in such as way that $R \cup S$ requires a new ordered pair (i.e. relationship) that wasn't present in either $R$ or $S$. In this example, that is the ordered pair $(1,3)$.

share|improve this answer
add comment

For $R\cap S$ being symmetric,

Let $(x,y)\in R\cap S\implies (x,y)\in R $ and $(x,y)\in S\implies (y,x)\in R$ and $(y,x)\in S$ (as $R,S$are symmetric) $\implies (y,x)\in R\cap S$.

Thus, $R\cap S$ is symmetric.

For transitive part($R\cup S$),

Let $(x,y)$ and $(y,z)\in R\cup S\implies $

Three cases possible:

Case 1: If both $(x,y)$ and $(y,z)\in R\implies (x,z)\in R\implies (x,z)\in R\cup S\implies $ Transitivity holds for $R\cup S $ in this case.

Case 2: If both $(x,y)$ and $(y,z)\in S\implies (x,z)\in S\implies (x,z)\in R\cup S\implies $ Transitivity holds for $R\cup S $ in this case too.

Case 3: Case 1: If $(x,y)\in R$ and $(y,z)\in S$ does not$ \implies $ $(x,z)\in R$ or $ S$ which does not $\implies (x,z)\in R\cup S\implies $ Transitivity need not hold for $R\cup S $ in this case.

Thus, Considering all the three cases, $R\cup S$ need not be transitive.

share|improve this answer
    
@Austin Mohr: yes, you are right, I didn't notice it. Thanks for pointing out. –  Aang Sep 19 '12 at 8:57
add comment

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.