Proving properties of binary relations

Question

Attempting to find answers to solve these questions. I've been looking all over the web for references since my textbooks aren't being helpful. Now, I'm still at the starting point.

Prove the following properties of binary relations.

1). 1◦R=R

2). R◦(S ∪ T) = R ◦ S ∪ R ◦T

3). R ⊆ S ⇒ T ◦ R ⊆ T ◦S

I would greatly appreciate it if you could help me out. Seriously, I honestly don't even know how to prove each of them, let alone writing out the answers.

Answer 1

The composition operation $R\circ S$ of two relations $R$ and $S$ is a relation such that that $x (R\circ S) y$ exactly when there exists a $z$ such that $xRz$ and $zSy$ (e.g., if $A$ is a relation between vertices of a graph representing adjacency, then $v(A\circ A)w$ represents the relation of there existing a trail of length two between $v$ and $w$).

The union $R\cup S$ of two relations represents the relation of at least one of $R$ or $S$ holding. And $R\subset S$ represents "if $xRy$ then $xSy$."

The identity relation $1$ is the minimal relation satisfying reflexivity. That is, $x1y$ implies $x=y$, and vice versa.

In each of these, we make heavy use of proving two sets are equal by showing that they are subsets of one another. We also make heavy use of showing a set is a subset of another by showing that whenever one has an element of the first that it is also an element of the second.

1. Whenever $xRy$ then $x(1\circ R)y$ since $x1x$ and $xRy$, so $R\subset 1\circ R$. Conversely, if $x(1\circ R)y$, then there is a $z$ such that $x1z$ and $zRy$, but $x1z$ implies $x=z$, and so $xRy$, which implies $1\circ R\subset R$. Hence, $1\circ R=R$.

2. If $x(R\circ(S\cup T))y$, then there is a $z$ such that $xRz$ and $z(S\cup T)y$. Either $zSy$ or $zTy$. In the first case, then $x(R\circ S)y$, and in the second $x(R\circ T)y$, so in either case, $x(R\circ S\cup R\circ T)y$. This shows $R\circ (S\cup T)\subset R\circ S\cup R\circ T$. Going the other way is similar.

3. Suppose $R\subset S$. If $x(T\circ R)y$, then there is a $z$ such that $xTz$ and $zRy$, but since $R\subset S$, we also have $zSy$, and so $x(T\circ S)y$. Hence $T\circ R\subset T\circ S$.

I'm not sure if this is helpful, but this is something I wrote at some point about binary relations (as a warning, it does not use standard notation and terminology): http://kylem.net/math/relations.html