# When can composition be applied to two relations/functions? Exercise 4.2.15 - How to prove it

There are things that I don't understand about composition. For example, if I have to explain when and why composition cannot be applied to two functions, how can I argue or show that it cannot be done?

For example suppose $$f:A\rightarrow B$$, $$g:C\rightarrow D$$ and $$B\neq C$$.

According to the following definition, composition cannot be applied to these functions because $$B\neq C$$.

But Velleman says that is not necessary for $$B$$ and $$C$$ to be the same set.

And gives the following exercise to solve:

I proved the first implication by contradiction but I don't know what the set E is. And I don't know how to prove the second implication.

If $$B⊂C$$, then $$g◦f$$ can be applied? And if $$C⊂B$$? What is the difference between composing functions and composing relations? Are there fewer restrictions on composition of relations?

When can I apply the composition? What are the restrictions and how can I prove that a composition cannot be applied?

I would like to go deeper into these concepts, if you want to recommend bibliography I will read it with pleasure.

• If I understand the intent correctly, I think they just mean to take any set $E$ that contains both $B$ and $C$ (for example, $E=B\cup C$). Apr 10 at 7:59
• @Greg And can E be a subset of $B\cup C$? In that case E would not give the same result Apr 10 at 8:07
• @Voxywave: $E$ can be a subset of $B \cup C$ as long as $R$ is a relation from $A$ to $E$ and $S$ is a relation from $E$ to $D$, as required in the statement of the problem; that is, as long as $R \subseteq A \times E$ and $S \subseteq E \times D$. As long as that requirement is met, all choices of $E$ will give the same result. Apr 10 at 15:08

You can take $$E$$ to be the union of $$B$$ and $$C$$, or actually any set that contains $$B\cup C$$. Now, your concerns about composition are a bit subtle and their solution depends on the "tiny" details in the definition of "relation" and "function". For my definition, both a function and a relation $$f\colon A \to B$$ are defined as a triple $$(A,B,f)$$ where $$f$$ is a suitable subset of the product set $$A\times B$$. So, it is imprecise to say that $$f$$ is a also a function $$f\colon A\to E$$ if $$E$$ contains $$B$$. What is true (or more precise) is that, in your situation, if $$R_1=(A,B,R_1)$$ and $$R_2=(C,D,R_2)$$ are two relations with $$B\neq C$$, for any set $$E$$ containing $$B\cup C$$, there are two uniquely induced relations (so, uniquely determined but different, in principle, from $$R_1$$ and $$R_2$$ if $$B\neq E$$ and/or $$C\neq E$$), $$(A,E,R^E_1)$$ and $$(E,D,R^E_2)$$. Then, for any such $$E$$, the composition $$R_2^E\circ R_1^E$$ is well-defined and it does not depend on the specific choice of $$E$$, but only on the original relations $$R_1$$ and $$R_2$$. Using this invariance, you can extend the definition of composition and define $$R_2\circ R_1:=R^E_2\circ R^E_1$$ for any $$E\supseteq B\cup C$$. Again, this will be well-defined because the composition $$R^E_2\circ R^E_1$$ does not depend on the choice of $$E$$. But still, with the standard definition of composition you cannot make sense of an expression like "$$R_2\circ R_1$$" if the target of $$R_1$$ is not contained in the source of $$R_2$$.
EDIT: As professor Velleman made clear in the comments, it seems that there is no complete agreement on the definition of basic concepts like a "relation" or a "function". My research in the last 10 years has been mostly in category theory, so the above definition of a function is certainly the most natural to me, and to other people with my same background. On the other hand, it seems that people with other backgrounds prefer to give slightly different definitions (a relation between $$A$$ and $$B$$ is not a triple, but it is really just a subset of $$A\times B$$, so the notion of source and target become not well-defined, but otherwise everything still works just fine). These two approaches are both present in the literature and in textbooks, so they are both to be considered correct. The important thing is to make sure that we adopt one of the two conventions and maintain it consistently throughout our work. This is exactly where my answer above becomes wrong: I have given an answer that uses the definition of a relation as a triple to a questions that assumes that a relation is, by definition, just a subset of the product space.
• Yes, the standard definition just makes sense under that condition. The exercise you mentioned suggests that, even if that is not the case, then there is still a uniquely determined relation/function $A\to D$ that would probably deserve to be called the "composition". But, strictly speaking, that is not a composition of the two original maps/relations. Apr 10 at 9:16
• The definition of function proposed in this answer is not the definition used in How To Prove It, and it is not the definition used in most set theory books. In How To Prove It, a function from $A$ to $B$ is simply a subset of $A \times B$ with the property that for all $a \in A$ there is a unique $b \in B$ such that $(a, b)\in f$. With that definition, if $f:A \to B$ and $B \subseteq E$ then $f:A \to E$. Apr 10 at 14:47
• Similarly, in How To Prove It, a relation from $A$ to $B$ is simply a subset of $A \times B$, and therefore if $R$ is a relation from $A$ to $B$, $A \subseteq A'$, and $B \subseteq B'$, then $R$ is a relation from $A'$ to $B'$. Since that is the definition used in How To Prove It, that is the definition that should be used in doing the exercise quoted in the question. Apr 10 at 15:05
• Dear prof. Velleman, of course you are the authority here and what you say is indeed correct: to solve an exercise in a given book, one should use the definitions as stated in that book (that I do not know). As for the definition of a function $f\colon A\to B$, I have always been thought that the subset $\{(a,f(a)):a\in A\}$ is the graph of the function, while the function itself includes the specification of its source and target. In fact, this is the definition you have to take if you want the category of sets to be a well-defined category. Apr 10 at 15:16
• @Simone: There is not complete agreement in the literature about this. For example, see en.wikipedia.org/wiki/Binary_relation. That article defines a relation from $A$ to $B$ to be a subset of $A \times B$, but then it says that some authors use the ordered triple definition that you proposed. No need to delete your answer--it's probably good for readers to see that there are two slightly different definitions in use. Apr 10 at 15:35