Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 6 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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