1. ## Discrete Relations

Relations can be composed just as functions are composed (for instance $g~ o~ f$).. note that the "o" is meant to be the "of" symbol but didn't know how to do it in latex.

For each of the following below, either prove or provide a counterexample:

a.) If $R$ is reflexive and if $S$ is reflexive, then $S~o~R$ is reflexive.

b.) If $R$ is symmetric and $S$ is symmetric, then $S~o~R$ is symmetric.

c.) If $R$ is transitive and $S$ is transitive, then $S~o~R$ is transitive.

2. Originally Posted by fifthrapiers
Relations can be composed just as functions are composed (for instance $g~ o~ f$).. note that the "o" is meant to be the "of" symbol but didn't know how to do it in latex.
For each of the following below, either prove or provide a counterexample:
a.) If $R$ is reflexive and if $S$ is reflexive, then $S~o~R$ is reflexive.
b.) If $R$ is symmetric and $S$ is symmetric, then $S~o~R$ is symmetric.
c.) If $R$ is transitive and $S$ is transitive, then $S~o~R$ is transitive.
We assume that these are all relations on the same set.
Recall that $(x,y) \in g \circ f \Leftrightarrow \quad \left( {\exists z} \right)\left[ {(x,z) \in f \wedge (z,y) \in g} \right]$

For (a) $\left( {\forall z} \right)\left[ {\left( {z,z} \right) \in f \wedge (z,z) \in g} \right] \Rightarrow \left[ {(z,z) \in g \circ f} \right]$

Consider $f = \left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\,\,g = \left\{ {\left( {b,c} \right),\left( {c,b} \right)} \right\}\,\mbox{ but }\,g \circ f = \left\{ {\left( {a,c} \right)} \right\}$.

3. Originally Posted by Plato
We assume that these are all relations on the same set.
Recall that $(x,y) \in g \circ f \Leftrightarrow \quad \left( {\exists z} \right)\left[ {(x,z) \in f \wedge (z,y) \in g} \right]$

For (a) $\left( {\forall z} \right)\left[ {\left( {z,z} \right) \in f \wedge (z,z) \in g} \right] \Rightarrow \left[ {(z,z) \in g \circ f} \right]$

Consider $f = \left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\,\,g = \left\{ {\left( {b,c} \right),\left( {c,b} \right)} \right\}\,\mbox{ but }\,g \circ f = \left\{ {\left( {a,c} \right)} \right\}$.
I forgot to add that we let $R$ and $S$ be binary relations on the set $A$. Not sure if this changes it.

I'm assuming that, based on your results, $S\circ R$ still wouldn't be reflexive.

For b, showing if its symmetric,

Suppose $A = \{1,2,3\}, \mbox{then} R = \{1,2\}, \{2,1\}, \{1,3\}, \{3,1\}, \{2,3\}, \{3,2\}$. Also, $S$ would also equal that if they're both symmetrical. So then the composition of R and S would be symmetrical?

And for c, transitivity is a little harder since we know if A = B, and B = C, then A = C. So I'd have to set up 3 different subsets? Perhaps drawing digraphs would help?

Thanks Plato.

4. No I proved the if each of R & S is reflexive then RoS is reflexive.

The example shows that if each of R & S is symmetric then RoS need not be.

You can use a similar example to disprove part c.

5. Originally Posted by Plato
We assume that these are all relations on the same set.
Recall that $(x,y) \in g \circ f \Leftrightarrow \quad \left( {\exists z} \right)\left[ {(x,z) \in f \wedge (z,y) \in g} \right]$

For (a) $\left( {\forall z} \right)\left[ {\left( {z,z} \right) \in f \wedge (z,z) \in g} \right] \Rightarrow \left[ {(z,z) \in g \circ f} \right]$

Consider $f = \left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\,\,g = \left\{ {\left( {b,c} \right),\left( {c,b} \right)} \right\}\,\mbox{ but }\,g \circ f = \left\{ {\left( {a,c} \right)} \right\}$.
Ahh I see why I was confused.

For (a) $\left( {\forall z} \right)\left[ {\left( {z,z} \right) \in f \wedge (z,z) \in g} \right] \Rightarrow \left[ {(z,z) \in g \circ f} \right]$

That's for a, and then you did b too, which was

Consider $f = \left\{ {\left( {a,b} \right),\left( {b,a} \right)} \right\},\,\,g = \left\{ {\left( {b,c} \right),\left( {c,b} \right)} \right\}\,\mbox{ but }\,g \circ f = \left\{ {\left( {a,c} \right)} \right\}$.

I thought the above was for part a, and I knew that that wasn't symmetrical, not reflexive. Ok, got it.