# Set Operations on Relations

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 ...

-
See Intersection of Symmetric Relations is Symmetric at ProofWiki. –  Martin Sleziak Sep 18 '12 at 14:57
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

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.

-

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)$.

-

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.

-
@Austin Mohr: yes, you are right, I didn't notice it. Thanks for pointing out. –  Aang Sep 19 '12 at 8:57