# Relations: is the composition of an empty set with a nonempty set empty? And the other way around

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.

• What do you mean by the composition of sets? – Thomas Rot Apr 18 '11 at 16:40
• @Thomas: as the tag (relations) is being used, it is likely to assume that the OP means $T,S,R$ are binary relations. – Asaf Karagila Apr 18 '11 at 16:44
• I think that the question needs to be edited to clarify the meaning, i.e. explain that $R,T,S$ are relations, and better yet - since you assume $T\circ S$ is empty, just say you're composing the empty relation with $R$. It is more direct and clearer to the reader. – Asaf Karagila Apr 18 '11 at 16:46
• @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. – Arturo Magidin Apr 18 '11 at 20:45

## 2 Answers

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.

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$.

• Actually, the composition as I gave it is the same as the composition of functions if you treat $f=\{\langle x,f(x)\rangle\mid x\in dom(f)\}$. – Asaf Karagila Apr 18 '11 at 19:06
• @Asaf: Hmm, you didn't specify it, but it seems that your $R$ is a relation from $Y$ to $Z$, that your $S$ is a relation from $Z$ to $X$, and that your $R\circ S$ is a relation from $X$ to $Y$. (Which I'd call $S\circ R$ as for functions, unless you also use the reversed (obsolete?) convention for function composition?) Or am I confusing your notation $zSx$ and $yRz$? I assumed you meant $(z,x)\in S$ and $(y,z)\in R$, respectively. – wildildildlife Apr 18 '11 at 19:18
• 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. – Asaf Karagila Apr 18 '11 at 19:32