Confusing composition of relations

Question

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

Answer 1

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\}\;.$$

Answer 2

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