My relation sets are as follows:

R = {(0,0), (0,2), (0,3), (2,0) (3,0)}

R^op = {(0,0), (0,2), (0,3), (2,0) (3,0)}

R^c = {(0,1),(0,4),(1,0),(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,0),(4,1),(4,2),(4,3),(4,4)}

Question is R o R^op o R^c

I ended up with the set of {(0,1), (0,2), (0,3), (0,4)} but I don't think this is correct.

Can someone help me go about this problem? It's confusing because my R^op set is the same as my R set

  • $\begingroup$ How is the composition defined? $\endgroup$ – Rajkumar Oct 3 '16 at 17:22
  • $\begingroup$ Q := R o R^op o R^c $\endgroup$ – Hobbes Oct 3 '16 at 17:42
  • $\begingroup$ My question was how the compositions of two relations are defined ? $\endgroup$ – Rajkumar Oct 3 '16 at 19:08
  • $\begingroup$ I'm not sure how to answer that, sorry. the question is asking R ∘ R^op ∘ R^c R is a subset of {0,1,2,3,4} x {0,1,2,3,4} $\endgroup$ – Hobbes Oct 3 '16 at 19:14
  • $\begingroup$ Take a look at Compositions of relations $\endgroup$ – Namaste Oct 3 '16 at 21:03

Since $R$ is symmetric, $R^{-1}$ (which you call $R^{\text{op}}$) is just $R$, and you’re interested in $R\circ R\circ R^c$. Because $R$ is so small, it’s not hard to check that

$$R\circ R=R\cup\{\langle 2,2\rangle,\langle 3,3\rangle,\langle 2,3\rangle,\langle 3,2\rangle\}\;.$$

In other words, $R\circ R=\{0,2,3\}\times\{0,2,3\}$: it contains every ordered pair that can be formed using just $0,2$, and $3$. For convenience let $S=R\circ R$; we want $S\circ R^c$.

Suppose that $\langle a,b\rangle\in S\circ R^c$; then there must be a $c\in\{0,1,2,3,4\}$ such that $\langle a,c\rangle\in R^c$ and $\langle c,b\rangle\in S$. We’ve just seen that $\langle c,b\rangle\in S$ if and only if $b,c\in\{0,2,3\}$, so $c$ has to be $0,2$, or $3$. What members of $R^c$ have $0,2$, or $3$ as second element? Those elements are:

$$\langle 1,0\rangle,\langle 4,0\rangle,\langle 1,2\rangle,\langle 2,2\rangle,\langle 3,2\rangle,\langle 4,2\rangle,\langle 1,3\rangle,\langle 2,3\rangle,\langle 3,3\rangle,\langle 4,3\rangle$$

This means that if $a$ is anything except $0$, there is a $c\in\{0,2,3\}$ such that $\langle a,c\rangle\in R^c$, and therefore $\langle a,0\rangle,\langle a,2\rangle$, and $\langle a,3\rangle$ are all in $S\circ R^c$. If $a=0$, on the other hand, there is no $c\in\{0,2,3\}$ such that $\langle a,c\rangle\in R^c$, and therefore none of $\langle a,0\rangle,\langle a,2\rangle$, and $\langle a,3\rangle$ is in $S\circ R^c$. It follows that

$$S\circ R^c=\{1,2,3,4\}\times\{0,2,3\}\;,$$

and I’ll leave it to you to write out the full set of $12$ ordered pairs if you wish.

Note: I have assumed that your concatenation is from right to left. In the less likely event that it is from left to right, then $\langle a,b\rangle\in S\circ R^c$ if and only if there is a $c\in\{0,1,2,3,4\}$ such that $\langle a,c\rangle\in S$ and $\langle c,b\rangle\in R^c$, and similar reasoning leads to the conclusion that $$S\circ R^c=\{0,2,3\}\times\{1,2,3,4\}\;.$$

  • $\begingroup$ Thanks for the response, Brian. Really appreciate it. I will have to get back to you with an appropriate response once I wrap my head around it. $\endgroup$ – Hobbes Oct 3 '16 at 20:52
  • $\begingroup$ @Hobbes: You’re welcome. By all means take whatever time you need. $\endgroup$ – Brian M. Scott Oct 3 '16 at 20:53
  • $\begingroup$ Can you explain why R∘R=R∪{⟨2,2⟩,⟨3,3⟩,⟨2,3⟩,⟨3,2⟩} ? I got R∘R = {(0,0), (0,2), (0,3)} $\endgroup$ – Hobbes Oct 3 '16 at 21:39
  • $\begingroup$ @Hobbes: As examples, you get $\langle 2,0\rangle$ from $\langle 2,0\rangle$ followed by $\langle 0,0\rangle$, and you get $\langle 2,2\rangle$ from $\langle 2,0\rangle$ followed by $\langle 0,2\rangle$. Can you see how to fill in the rest now? $\endgroup$ – Brian M. Scott Oct 3 '16 at 21:43
  • $\begingroup$ Thanks! I'm not sure why I wasn't following. Re-did it on paper and now I have the set you gave me. I think the 0 relating to multiple points tripped me up. Also, composition of relations is read from right to left? My teacher always makes a point about reading from left to right. He may have mentioned the reverse is true when doing composition, but I don't remember. $\endgroup$ – Hobbes Oct 3 '16 at 21:54

I will follow the definition of composition given here.

We can think a relation $R \subseteq X \times Y$ as a multivalued function $f:X \rightarrow Y$. For example, in your problem, the relation $R$ can be considered as a function $f: X \rightarrow Y$, where $X$ and $Y$ are the sets of first and second co-ordinates, respectively. That is, $X = \{0,2, 3\}$ and $Y = \{0, 2, 3\}$. For $x \in X$, we define its image $f(x)$ as $$f(x):= \{y: (x, y)\in R\},$$ which is a set of $y$-co-ordinates which are related to $x$ under the relation $R$. For the given relation $R$, we have $f(0) = \{0, 2, 3\},$ $f(2) = \{0\}$ and $f(3) = \{0\}$. Viewing relations as multivalued functions, we can easily compute the composition of relations by applying the compositions of multivalued functions. We proceed like this. For convenience, I will denote the relation $R^{op}$ by $S$ and the relation $R^c$ by $T$. Let $g$ and $h$ be the multivalued functions with appropriate domains and codomains corresponding to the relations $S$ and $T$, respectively. Then the relation $R \circ R^{op}\circ R^{c} = R\circ S \circ T$ will be given by the composition of multivalued functions: $f\circ g \circ h$. This composition can be computed by first computing $g \circ h$, which will be a multivalued function. Then we can compose it with $f$. Here I will compute $g \circ h$ only. Note that $g: \{0, 2, 3\} \rightarrow \{0,2, 3\}$ is defined by $g(0) = \{0,2,3\}, ~g(2) = \{0\}$ and $g(3) = \{0\}$. Similarly, $h: \{0,1,2,3,4\} \rightarrow \{0, 1, 2, 3, 4\}$ is defined by $h(0) = \{1,4\},~ h(1) = \{0,1,2,3,4\}= h(4),$ $h(2) = \{1,2,3,4\} = h(3)$. Now $g\circ h: \{0,1,2,3,4\} \rightarrow \{0,2,3\}$ can be computed as follows: Let $S \circ T(x)$ denote the subset of the relation $S \circ T$ whose elements has first cordinate $x$. With these notation, we can write, $$g \circ h(0) = g(h(0)) = g(\{1,4\}) = g(1)\cup g(4) = \phi\cup \phi = \phi$$, where we have used the fact that for a multivalued function $f: X \rightarrow Y$, $f(\{x_1, x_2, \ldots x_k\}) = f(x_1) \cup f(x_2) \cup \cdots \cup f(x_k)$. Therefore, $$S \circ T(0) = \phi$$ Similarly, $$g \circ h(1) = g(h(1)) = g(\{0,1,2,3,4\}) = \{0,1,2,3,4\}.$$ Hence $S \circ T(1) = \{(1, 0), (1,1), (1,2),(1,3), (1,4)\}$. $$g \circ h(2) = g(h(2)) = g(\{1,2,3,4\}) = \{0,1,2,3,4\},$$ and so $S \circ T(2) = \{(2, 0), (2,1), (2,2),(2,3), (2,4)\}$. Similarly, we have $$S \circ T(3) = \{(3, 0), (3,1), (3,2),(3,3), (3,4)\},$$ and $$S \circ T(4) = \{(4, 0), (4,1), (4,2),(4,3), (4,4)\}.$$ Therefore, $$S \circ T = S \circ T(0) \cup S \circ T(1) \cup S \circ T(2) \cup S \circ T(3) \cup S \circ T(4) = \{(1, 0), (1,1), (1,2),(1,3), (1,4), (2, 0), (2,1), (2,2),(2,3), (2,4), (3, 0), (3,1), (3,2),(3,3), (3,4), (4, 0), (4,1), (4,2),(4,3), (4,4)\} = \{(x, y): x = 1,2,3,4 ~\text{and}~ y = 0,1,2,3,4\}.$$ Now by the same procedure, we can compute $R \circ (S \circ T)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.