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

Question

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)?

Answer 1

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.

Answer 2

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

Answer 3

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.