Relations (Binary) - Composition

Question

Let $R = \{(a,b), (b,c), (c,d)\}$

How can I figure out why $R^{2} = \{(a,c), (b,d)\}$? This there a mathematical proof (or formula) to determine this for larger set of relations? Is it always first member of first ordered pair with the second member of the second ordered pair, followed by the first member of the second ordered pair with the second member of the third ordered pair, and so on?

And as for $R^{3} = \{(a,d)\}$ is is always the first member of the first ordered pair to the second member of the third ordered pair and so on?

Answer 1

Your undersanding of the process is accurate. The pair $(x,y)$ is in $R^2$ if there is a $z$ such that $(x,z)$ and $(z,y)$ are both in $R$. So you search for all cases where the second "coordinate" of one ordered pair is equal to the first coordinate of another. So for example if $(a,d)$ is in the relation $R$, and $(d,w)$ is in the relation $R$, then $(a,w)$ is in $R^2$.

There is another way to do it which looks more "mathematical" but amounts to the same thing. However, doing it the way I will describe is not pleasant for humans. (Computers love it.)

In our situation, we have $4$ objects, namely $a$, $b$, $c$ and $d$. Instead, let's call them $a_1$, $a_2$, $a_3$, and $a_4$. Make a $4\times 4$ matrix as follows.

In the position where the $i$-th row and $j$-th column meet, put a $1$ if $R(a_i,a_j)$ and a $0$ otherwise. This is called the adjacency matrix of the relation $R$ (the language comes from the theory of directed graphs).

Square the adjacency matrix. If in the squared matrix, there is a $0$ where the $i$-th row and the $j$-th column meet, then the relation $R^2$ does not hold for $(a_i,a_j)$. If where the $i$-th row and $j$-th column meet, there is a number $\ne 0$, then the relation $R^2$ holds for $(a_i,a_j)$. The number measures the number of $w$ such that $(a_i,w)$ and $(w,a_j)$ are both in $R$, or more geometrically the number of $2$-step "paths" from $a_i$ to $a_j$.

Remark: The same idea works for relations on any finite set, and for $R^n$ (just take the $n$-th power of the adjacency matrix, easier said than done).

More generally, suppose that you have two relations $R$ and $S$ on a set. We can define $RS$ in a way analogous to the definition of $R^2$. And we find $RS$ by multiplying the adjacency matrices of $R$ and $S$, and going through the same process as we did for $R^2$.

The adjacency matrix can be a powerful tool. For we can use matrix theoretic ideas, such as eigenvalues, to obtain useful information about $R$.

Answer 2

I would like to add my two cents to André Nicolas's answer.

There are two definitions of the composition of binary relations in use. The choice of one of them is merely a matter of personal taste, and since you haven't given yours, I will choose for this post the definition I prefer.

Let $\rho$ and $\sigma$ be binary relations on a set $X$ and let $n$ denote $\operatorname{card}(X)$ (possibly infinite). We define $\rho\circ \sigma$ as follows.

$$\rho\circ \sigma=\{(i,j)\in X\times X\,|\,(\exists x\in X)((i,x)\in \rho\wedge (x,j)\in \sigma)\}$$

Let's use the less common symbol for the existential quantifier, that is $\bigvee$ instead of $\exists.$

$$\rho\circ \sigma=\left\{(i,j)\in X\times X\,|\,\bigvee_{x\in X}((i,x)\in \rho\wedge (x,j)\in \sigma)\right\}$$

Let now $\mathbb{B}=(\{0,1\},\vee,\wedge\}$ be the two-element Boolean algebra without the unary operation. We denote the set of all square matrices of size $n\times n$ (still possibly infinite) with entries in $\mathbb B$ by $\mathcal M_n.$ Let's suppose for a moment that $n<\infty.$ $\mathbb B$ is a semiring and there is a natural multiplication in the set of finite square matrices over a semiring. The definition is exactly the same as for rings or fields. For $\mathbb B$ we obtain the following definition.

Let $R=[r_{ij}],S=[s_{ij}]$ be matrices in $\mathcal M_n.$ We define $[t_{ij}]=R\cdot S\in\mathcal M_n$ by setting

$$t_{ij} = \bigvee_{x=1}^n (r_{ix}\wedge s_{xj}),$$

for $(i,j)\in\{1,...,n\}\times\{1,...,n\},$ where $\bigvee$ stands for summation in $\mathbb{B}.$ (That is, its meaning is formally different from the meaning of $\bigvee$ in the formula for $\rho\circ\sigma.$)

We see however that in this case there is no apparent reason to confine ourselves to finite matrices. Indeed, summation over infinite sets of indices is well-behaved in $\mathbb B$ and for infinite $n$ we can take the set $X$ as the set of indices instead of $\{1,...,n\}$. This time we define

$$t_{ij} = \bigvee_{x\in X} (r_{ix}\wedge s_{xj}),$$

for $(i,j)\in X\times X.$

The similarity between the formula for $\rho\circ\sigma$ and that for $R\cdot S$ is striking. It should be now an easy exercise to find an isomorphism between the set of all binary relations on $X$ with composition as an operation and the set $\mathcal M_n$ with the matrix multiplication defined above.

Answer 3

No, you can't do things exactly in that way. It's not "always first member of first ordered pair with the second member of the second ordered pair, followed by the first member of the second ordered pair with the second member of the third ordered pair, and so on", and no to the other questions. In truth, sets in general have no such "order" or "sequencing", so you can't even legitimately say the "first ordered pair" or the "nth ordered pair". That said, you can have a first member of an ordered pair.

As correctly implied by Andre Nicolas you want to look for all common "middle" terms. You can "compose" two ordered pairs if and only if the second term of one pair A is the same term as the first term of the other pair B. The resulting "composition" consists of the first member of A, and the second member of B. E. G. Say you have A={(a, a)}. Well, a=a, so A$^{2}$={(a, a)}, since the second member of (a, a) equals the first member of (a, a). If you have B={(a, b), (b, a)}, then we have B$^{2}$={(a, a), (b, b)}, since the second member of (a, b) equals the first member (b, a) giving us (a, a), and the second member of (b, a) equals the first member of (a, b).

As another way to think about it, say you take all ordered pairs like (x, y), and rewrite them with the first member first, followed by an arrow, and then the second member. So for (x, y), we'll write x->y. If we can "compose" two ordered pairs (a, b), (c, d) in this notation, then we have a->b and c->d. Well, if b=c, instead of writing a->b and c->d, since c will "take us to" d anyways, we can just go there directly and write a->d. If c does not equal d, then we can't "compose" anything here, as there exists no common point of contact, so to speak.

As others have pointed out, there does exist another way to do this, but I doubt that's what you're looking for.