What do $R$, $R^2$ and $R^{-1}$ represent?

Question

Question

What do $R$, $R^2$ and $R^{-1}$ represent when $R$ is a relation on the set of natural numbers?

I'm doing some homework, but the $R^2$ and $R^{-1}$ notation confuses me.

Does $R^2 = R*R$?

Does $R^{-1} = \frac{1}{R}$?

Answer 1

$R^{-1}$ is the inverse relation: $R^{-1}=\{\langle \ell,k\rangle:\langle k,\ell\rangle\in R\}$. In other words, you get $R^{-1}$ from $R$ by turning each ordered pair in $R$ around. If $R=\{\langle n,n+1\rangle:n\in\Bbb N\}$, so that $R$ contains such pairs as $\langle 1,2\rangle$ and $\langle 7,8\rangle$, then $R^{-1}=\{\langle n+1,n\rangle:n\in\Bbb N\}$ and contains such pairs as $\langle 2,1\rangle$ and $\langle 8,7\rangle$.

$R^2$ is the composition of $R$ with itself. An ordered pair $\langle k,\ell\rangle$ is in $R^2$ if and only if there is an $n\in\Bbb N$ such that $\langle k,n\rangle$ and $\langle n,\ell\rangle$ are in $R$. In terms of the steppingstone analogy, if $R$ lets you get from $k$ to $\ell$ in two steps, then $R^2$ lets you do it in one. If $R$ is the relation that I used as an example in the first paragraph, $R$ lets you go from $k$ to $\ell$ in one step exactly when $\ell=k+1$, so it lets you get from $k$ to $\ell$ in two steps exactly when $\ell=k+2$. In this case, then, it turns out that

$$R^2=\{\langle n,n+2\rangle:n\in\Bbb N\}\;.$$

Note that if $R$ is transitive, and it lets you get from $k$ to $\ell$ in two steps, then by the definition of transitivity it already lets you get from $k$ to $\ell$ in one step. Thus, if $R$ is transitive you’ll always find that $R^2\subseteq R$: every pair in $R^2$ is already in $R$.

Answer 2

Usually, $R^{-1}$ is defined as follows: $R^{-1}:=\{(b,a): (a,b) \in R\}$.

$R^2$ is more ambiguous, but most of the times it means this: $R^2:=\{(a,c): (a,b),(b,c)\in R$ for some $b \in \mathbb{N} \}$

Answer 3

A relation is a set of ordered pairs. You can imagine each ordered pair as an arrow: An arrow goes from $x$ to $y$ if $(x,y)\in R$.

With this visualization the inverse relation $R^{-1}$ just means reversing all arrows.

Composition of relations $S\circ R$ simply means that you start from one point and look where you can get if you follow an $R$-arrow first and then then an $S$-arrow.

For example have a look at this picture:

The pair $(0,2)$ belongs to the relation $S\circ R$, because there is a path from 0 to 2 (since you $(0,1)\in R$, and $(1,2)\in S$). Would you be able to find all ordered pairs belonging to $S\circ R$? (You may also notice that this is example of two equivalence relations such that their composition is not an equivalence relation.)

You have asked about $R\circ R$; it is a special case of this (when $S=R$).

See also: directed graph representing the inverse relation