# What's a good notation to show elements of relation composition?

Teaching discrete mathematics, we pose (from the textbook) questions on finding compositions of relations, notably, relations on very small finite sets with only 3 or 4 elements (as an introductory and tested exercise).

I'm searching for some way of being very specific and concrete in pointing out the individual "linkages" that are producing elements in the composition relation. I've been frustrated that none of the textbooks I've checked ever shows an explicit example being worked out like this. It's always definition, boom, final composition relation in its entirety.

For example, here's an exercise from the Rosen Discrete Math book:

Let $$R$$ be the relation $$\{(1,2),(1,3),(2,3),(2,4),(3,1)\}$$, and let $$S$$ be the relation $$\{(2,1),(3,1),(3,2),(4,2)\}$$. Find $$S \circ R$$.

(*) Here's where I want some scratch/explanatory work, resulting in the answer:

$$\{(1,1),(1,2),(2,1),(2,2)\}$$

Now, my instinct is to start writing something like: $$(1,2) + (2,1) \implies (1, 1)$$, etc., but that's a multifold abuse of notation -- which my students are already greatly struggling with, so I want to set a good example.

I really want something that can be written briefly in one line of text per element in the composition (e.g., not converting to a digraph and saying "look at this, it's easy", or any other trick to make the problem "easier" -- the point is to document production of each individual element).

What's the best way to show work in finding elements of a relational composition (at point (*) above)?

• You can invent a symbol, like $(1,3)\star(3,2)\to(1,2)$. – Joel Reyes Noche May 10 at 13:35
• Or 2S3R1, which has the advantage of having the following cute mnemonic: $c S\circ R a$ iff $c S b R a$ for some $b$. – Steven Gubkin May 10 at 13:44
• @DanielR.Collins I also see no real problem with $(3,2) \circ (1,3) = (1, 2)$ – Steven Gubkin May 10 at 13:53
• @StevenGubkin: Maybe with a different symbol for the operator. – Daniel R. Collins May 10 at 21:43
• ... and: I think I want them associating left-to-right (unlike the composition operator), so the "internal linkage" per the definition is more obvious. – Daniel R. Collins May 11 at 2:46

To explain why any particular ordered pair is in $$S \circ R$$, you can just show that it satisfies the definition, which says that $$(a,c)$$ is in $$S \circ R$$ if there exists $$b$$ such that $$(a,b) \in R$$ and $$(b,c) \in S$$. To show this is true, you can just give an example of such $$b$$ and observe that $$(a,b) \in R$$ and $$(b,c) \in S$$. The two things here are connected with the word "and"; if you want to use a symbol for that, it should be $$\wedge$$ or $$\And$$, not $$+$$.

For example, you could write:

$$(1,3) \in R \quad \And \quad (3,2) \in S, \quad\text{so} \quad (1,2) \in S \circ R$$.

This is already quite short, and I don't think you should write anything further removed from the definition of $$S \circ R$$ just to shorten it further.

• (+1) I was going to suggest (in a comment, as I don't have time now to discuss issues relating to what to use) "$(1,2) \in R$ and $(2,1) \in S$ gives $(1,1)$", but for teaching purposes "$\ldots (1,1) \in S \circ R$" is probably better, at least in the beginning when students are first learning how to do this. As a personal preference, to reduce the symbol clutter, I would use "and" rather than "&". (Also, I can type "and" quicker than "&", and my hand-writing of "&" is usually not even close to what it's supposed to look like!) – Dave L Renfro May 12 at 7:47
• Incidentally, and now I'm spending more time here than I wanted to (!), these statements only tell us that certain ordered pairs belong to the composition, and thus something else needs to be used when a student includes an incorrect ordered pair. For class presentations/explanations, however, I guess you handle this by picking elements in $R$ one at a time, and for each such choice, check it's compatibility with each of the elements in $S.$ – Dave L Renfro May 12 at 8:22
• I usually handwrite the ampersand as something like $\varepsilon$ with a vertical line through it, which I think looks different enough from $\notin$ to avoid confusion. But the word "and" is always a good choice. – Trevor Wilson May 12 at 8:37
• +1 Clearly legitimate and a good thing to consider. However, while it looks viable for one case, when I need to do around a half-dozen for one exercise, then all the repetitive element-of-set parts get a bit frustrating. And I kind of wish the internal bridging elements ($b$) were visually closer together. So I'm leaning towards wanting a (new) shorter notation. – Daniel R. Collins May 12 at 14:33
• @DanielR.Collins You can't get any closer than just overlapping them: $(1,(3),2)$. Maybe with an $S$ and $R$ written underneath for clarity? I don't think it's very good and I prefer Trevor's answer, but this is certainly new and short. – Thierry May 12 at 19:19

I'd avoid introducing a new notation for such a limited scope: you won't probably use it elsewhere during the class, and it wouldn't be used elsewhere in the literature.

I have three suggestions. The first is a simple variation of Trevor Wilson's answer, which mirrors the first relation sign to keep the bridging elements together:

$$R\ni(1,3) \And (3,2) \in S\Rightarrow (1,2) \in S \circ R$$

The second is to use a table, structured as follows:

$$(a,b) \in R$$ $$(b,c) \in S$$ $$(a,c) \in S \circ R$$
$$(1,3)$$ $$(3,1)$$ $$(1,1)$$
$$(1,3)$$ $$(3,2)$$ $$(1,2)$$
... ... ...

The third is another table, where the first column lists the pairs from $$R$$, and the first row lists the pairs from $$S$$. Then, you mark the intersections which have an element in common (this might possibly reduce mistakes from the students):

$$(2,1)$$ $$(3,1)$$ $$(3,2)$$ $$(4,2)$$
$$(1,2)$$ $$(1,1)$$
$$(1,3)$$ $$(1,1)$$ $$(1,2)$$
$$(2,3)$$ $$(2,1)$$ $$(2,2)$$
... ... ... ... ...
• +1, thanks for writing these options, this is thoughtful. That said, I may not use any of them. (a) Uses $\ni$ which is not at any point used/defined in the class or book (which itself breaks the "won't probably use it elsewhere during the class" idea). (b) Is something I've actually tried to commit to previously, but in practice wind up not having space for/seems unclear without some connecting operators. (c) Again seems very large, esp. trying to fit online onscreen as part of a larger exercise? But maybe I should give that one more thought. It does demonstrate all the checks we do mentally. – Daniel R. Collins May 13 at 12:46
• This is a good answer-especially the second table. So much depends on how the order pairs in $R$ and $S$ are presented. The worst case scenario is long text strings separated by commas, and every element is related to every other element, and the entries of the ordered pairs are categorical and so not easily sortable as is the case with numeric and alpha. If the data is not even presented in a structure similar to the second table, then the first thing to do, before determining $S\circ R$, is to organize it! – user52817 May 13 at 14:25

Thanks for your feedback on my previous answer, which contained a misunderstanding. Here's a new try. I believe the following is the way to express the thought that you were trying to express as $$(1,2) + (2,1) \implies (1, 1)$$, using only the notation your book seems to be using:

$$\{(1,2)\}\circ\{(2,1)\}=\{(1,1)\}.$$

That is, your book defines a relation as a set of ordered pairs. We restrict our attention to one element of S and one element of R, forming singleton sets which represent relations that connect only two things (i.e., each of their graphs would be a single dot). We compose these two singleton relations and get one element of the composition of S with R. The complete composition of S and R would be the union of all such compositions of singletons with singletons.

• +1 Thanks for thinking about this. This at least seems like we're on a legitimate track... – Daniel R. Collins May 11 at 0:54
• ... But note that I think we've fallen afoul of the composition associating right-to-left issue. Actually, $\{(1,2)\} \circ \{(2,1)\} = \{(2,2)\}$. And in that respect doing it this way slightly obscures the "internal linkage" which is described in the definition of a relation. Also e.g., $\{(3,4)\} \circ \{(2,3)\} = \{(2,4)\}$. – Daniel R. Collins May 11 at 0:57