Composite Relations

Question

I'm new to functions and relations, and I've only just figured out that there are 16 relations on a set with 2 elements. I can't figure out what is meant by R ; R ⊆ R other than the fact it is a composite relation! Any help / guidance would be appreciated!

Answer 1

A relation $R$ from set $A$ to set $B$ is (by definition) a subset of the Cartesian product $A\times B$. Thus a relation is a set. For instance here is a relation, $R_1$ on $\{0,1\}$ (i.e. a relation from $\{0,1\}$ to $\{0,1\}$): $R_1=\{(0,1), (1,0)\}$.

Since relations from $A$ to $B$ are subsets of $A\times B$, it makes sense to ask if one relation from $A$ to $B$ is a subset of another. Extending the above example: Here is another relation on $\{0,1\}$: $R_2=\{(0,0), (0,1), (1,0)\}$. Then $R_1\subseteq R_2$.

I hope these ideas help!

Answer 2

According to Wikipedia article Composition of relations some people use $R;R$ for left composition of relations. In this example, there is no difference between left and right composition, since $R$ is being composed with itself.

So, the question asks whether for every $R$ on a two-element set, the relation $R;R$ is a subset of $R$. In plain words, it's asking whether every relation is transitive.

Answer 3

For relations $R\subseteq A\times B$ and $S\subseteq B\times C$ one define $R;S=\{(a,c)\in A\times C|\exists b\in B: (a,b)\in R\wedge (b,c)\in S\}$.

If $A=B=C=\{0,1\}$ and $R=S$, then $R\subseteq \{(0,0),(0,1),(1,0),(1,1)\}$. Suppose $R=\{(0,1),(1,0)\}$, then $R;R=\{(0,0),(1,1)\}\nsubseteq\{(0,1),(1,0)\}=R$. Counter example thus.