Composite Relations - Give Examples of relations $R_1$ and $R_2$ such that $R_2 \circ R_1 = R_1 \circ R_2$ and $R_2 \circ R_1 \neq R_1 \circ R_2$

Question

Let $S =[a,b,c]$. Give examples of

a. relations $R_1$ and $R_2$ on $S$ such that $R_2 \circ R_1 = R_1 \circ R_2$

b. relations $R_1$ and $R_2$ on $S$ such that $R_2 \circ R_1 \neq R_1 \circ R_2$

My attempt:

Definition 6.3.9 states that we let $R_1$ and $R_2$ be relations on a set $S$. The composition of $R_2$ with $R_1$ is the relation $R_2 \circ R_1 = [(x,y) \in S \times S :( \exists y \in S)[(x,v) \in R_1 \land (v,y) \in R_2]$

for a. let $ R_1 = [a,a]$ and $R_2 = [a,a]$

If we take the composition of $ R_2 \circ R_1$,

$R_2 \circ R_1 = [(a,a) \in S \times S :( \exists a \in S)[(a,a) \in R_1 \land (a,a) \in R_2]$

then the result is $[a,a]$

If we take the composition of $R_1 \circ R_2$,

$R_1 \circ R_2 = [(a,a) \in S \times S :( \exists a \in S)[(a,a) \in R_2 \land (a,a) \in R_1]$

then the result is $[a,a]$

For b

Let $R_1 = [a,b]$ and $R_2 = [b,c]$. Then by definition 6.3.9, we have $R_2 \circ R_1 = (a,b) \in S \times S : (\exists y \in S)[(a,v) \in R_1 \land (v,b) \in R_2]$

Similarly, $R_1 \circ R_2 = (a,c) \in S \times S : (\exists y \in S)[(a,v) \in R_2 \land (v,c) \in R_1]$

I'm not sure if I'm doing this correctly because I don't know how to expand the definition. The question states to give examples, so for a I had $R_1$ and $R_2$ be the same value and for b I had $R_1$ and $R_2$ be different values so that when I take the composite of $R_1 \circ R_2$ and $R_2 \circ R_1$ the result won't be the same.

If it was a composite function then I know that if I put my $R_1$ into my $R_2$ I would have something like $[a,c]$. I'm not sure if it applies to composite relations.

Is there any way to make my proof clearer or easier to understand?

Answer 1

You seem a little confused about set builder notation. When we write $$T=\{x\in S: x \text{ satisfies some condition}\}$$ The symbol $x$ is a free variable. This, unpacked, roughly gives you instructions for how to build $T$:

1. Take an $x$ in $S$.
2. Check to see if $x$ satisfies the condition.
3. If it does, put $x$ in $T$.
4. If it doesn't, throw it out.
5. Repeat until you run out of $x$'s.

So "$x$" is kind of a dummy variable. If you've ever done any computer programming, you can think of $x$ a little bit like the i in a for loop. If not, ignore that last part.

So when you write $$R_2 \circ R_1 = [(a,a) \in S \times S :( \exists a \in S)[(a,a) \in R_1 \land (a,a) \in R_2]$$this is not quite right. First of all, $a$ is already taken as a name, so we don't want to use $(a,a)$ in the left hand side of the set builder notation.

Now, your examples are good so that's good. For a, let's unpack this $$R_2 \circ R_1 = \{(x,y) \in S \times S :( \exists v \in S)[(x,v) \in R_1 \land (v,y) \in R_2]\}.$$ That means $R_2 \circ R_1$ is the set of all pairs $(x,y)$ in $S\times S$ such that $(v,y)\in R_2$ and $(x,v)\in R_1$. If we want to be real meticulous here, we can actually list out the elements of $S\times S$:

1. $(a,a)$
2. $(a,b)$
3. $(a,c)$
4. $(b,a)$
5. $(b,b)$
6. $(b,c)$
7. $(c,a)$
8. $(c,b)$
9. $(c,c)$

Now we want to figure out exactly what $R_2 \circ R_1$ is—we have a description of it in set builder notation but we would like to translate that into an extensional list of its elements. Here, $(a,a)$ is the only pair $(x,y)$ element in $S\times S$ such that there exists a $v\in S$ (namely $v=a$) such that $(v,y)\in R_2$ (for $y=a$) and $(x,v)\in R_1$ (take $x=a$). And thankfully since $R_1=R_2$ here, that takes care of $R_2$ as well.

For part b, you've put $R_1=\{(a,b)\}$ and $R_2=\{(b,c)\}$. We now want to find $R_1\circ R_2$. Again this is the set of all pairs $(x,y)$ in $S\times S$ such that $(v,y)\in R_2$ and $(x,y)\in R_1$. Well, if $(v,y)\in R_2$ then $v$ must be $b$ and $y$ must be $c$, since your $R_2$ only has that one element. Now, is there an $x$ such that $(x,v)\in R_1$ with $v=b$? Well, yeah, the only element in $R_1$: $(a,b)$.

For $R_2 \circ R_1$, the analysis goes similarly. If $(v,y)\in R_1$ at all then $v=a$ and $y=b$. Is there an $(x,v)\in R_2$ where $v=a$? No there is not: the only element in $R_2$ is $(b,c)$. So there is no element in $S\times S$ which satisfies the definition, and hence $R_2\circ R_1=\emptyset$.