1
$\begingroup$

Given $T\circ S=\emptyset$ and $R$ nonempty, would $(T \circ S) \circ R$ be anything other than the empty set?

I'm also curious the other way around. I think that it would be just empty.

  • 0
    @Algfic: Titles/subject lines are meant to be indexing features and guides, much like the title in the spine of a book tells you something about the book; but you don't tell readers to go read the spine of the book halfway through the book. Please make the body of your post self-contained, without references to the title.2011-04-18

2 Answers 2

6

Recall the definition of composition:

Let $R,S$ be binary relations. $R\circ S = \{\langle x,y\rangle\mid \exists z(\langle x,z\rangle\in S\wedge \langle z,y\rangle\in R)\}$. (Essentially this a generalization of composition of functions.)

Suppose $R=\emptyset$ (which is a relation as all its members are ordered pairs) then clearly $R\circ S=\emptyset$, otherwise $x(R\circ S)y$ implies there is some $z$ such that $\langle x,z\rangle\in S=\emptyset$ which is a contradiction.

2

Asaf already gave a good answer. I prefer the order of composition of relations to be the same as for functions (which, if I am not mistaking, is the opposite of Asaf's order).

So suppose $X,Y,Z$ are sets and we have relations $X\xrightarrow{R}Y\xrightarrow{S}Z$ (by which I mean $R$ is a relation from $X$ to $Y$, and $S$ is a relation from $Y$ to $Z$). Then the composition $S\circ R$ is a relation from $X$ to $Z$ given by

$S\circ R:=\{(x,z)|\exists y\in Y: (x,y)\in R\text{ and }(y,z)\in S\}$.

Now to your question about the converse: this is not true. An easy counter-example might be to take $X=\{1\}=Z$ and $Y=\{1,2\}$, and $R=\{(1,1)\}$ and $S=\{(2,1)\}$. Then $(1,1)\notin S\circ R$. So $S\circ R=\emptyset$ while $R\neq \emptyset$ and $S\neq \emptyset$.

  • 0
    You are absolutely right. And to think that I started by stating that function-like and switched it over :-) I'll go and correct myself now.2011-04-18