What is left composition of two binary relations?

173 Views Asked by At

What is left composition of two binary relations?

Consider sets $X$, $Y$, $Z$:

$$X = \{a,b,c\}$$ $$Y = \{1,2,3\}$$ $$Z = \{x,y,z\}$$

Then $R$, $S$ are relations:

$$R = \{(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c, 2), (c, 3)\}$$

$$S = \{(1, x), (1, y), (1, z), (2, x), (2, y), (2, z), (3, x), (3, y), (3, z)\}$$

Then composition $R$ and $S$ will be:

$$R \circ S = \{(a, x), (a, y), (a, z), (b, x), (b, y), (b, z), (c, x), (c, y), (c, z)\}$$

What is left composition $R;S$ in this exapmle?

1

There are 1 best solutions below

0
On BEST ANSWER

Left composition as the words says, is just like traditional right composition, but in the inverse order.

From wikipedia we can see that

$$R;S = \{(x,z) \in X \times Z \mid \exists y \in Y : (x,y) \in R \land (y,z) \in S \}$$

This means that to get $R;S$ we first go through $R$, and then from the output of $R$ to $S$. In traditional right composition, to get $R \circ S$ we first go through $S$ and then through $R$, getting the usual definition:

$$R \circ S = \{ (x,z) \in X \times Z \mid \exists y \in Y : (x,y) \in S \land (y,z) \in R \}$$

I'm almost certain your confusion comes from the fact that sometimes relation composition is defined with the $\circ$ symbol but the left composition definition. To add even more to the confusion, function composition is also defined with the same $\circ$ symbol but always with the right composition definition.

Basically, it's the same thing but in reverse order.

Note that in your example, the right composition of $R$ and $S$ is the empty set, since there are no elements of $Z$ in $X$.