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