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.

  • 1
    $\begingroup$ What do you mean by the composition of sets? $\endgroup$ – Thomas Rot Apr 18 '11 at 16:40
  • $\begingroup$ @Thomas: as the tag (relations) is being used, it is likely to assume that the OP means $T,S,R$ are binary relations. $\endgroup$ – Asaf Karagila Apr 18 '11 at 16:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Apr 18 '11 at 16:46
  • $\begingroup$ @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. $\endgroup$ – Arturo Magidin Apr 18 '11 at 20:45

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

  • $\begingroup$ 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)\}$. $\endgroup$ – Asaf Karagila Apr 18 '11 at 19:06
  • $\begingroup$ @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. $\endgroup$ – wildildildlife Apr 18 '11 at 19:18
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Apr 18 '11 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.