Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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.

share|cite|improve this answer

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|cite|improve this answer

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

Your Answer


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.