Let $S=\{a,b\}$. Of all the relations on $S$ which are symmetric? Reflexive? Transitive?

64 Views Asked by At

The relations are as follows:

1.) $\{(a,a)\}$

2.) $\{(a,b)\}$

3.) $\{(b,a)\}$

4.) $\{(b,b)\}$

5.) $\{(a,a),(a,b)\}$

6.) $\{(a,a),(b,a)\}$

7.) $\{(a,a),(b,b)\}$

8.) $\{(a,b),(b,a)\}$

9.) $\{(a,b),(b,b)\}$

10.) $\{(b,a),(b,b)\}$

11.) $\{(a,a),(a,b),(b,a)\}$

12.) $\{(a,a),(a,b),(b,b)\}$

13.) $\{(a,a),(b,a),(b,b)\}$

14.) $\{(a,b),(b,a),(b,b)\}$

15.) $\{(a,a),(a,b),(b,a),(b,b)\}$

I think the I think 1, 4, 8, 14 are both symmetric and reflexive and 12 is transitive. I'm not sure though.

1

There are 1 best solutions below

0
On

I'll do #2 and 15.

#2: $R_2 = \{(a,b)\}$ is not symmetric, because $(a,b)$ is in $R_2$, yet $(b,a)$ is not in $R_2$. Recall that the definition of symmetric says that $(a,b) \in R \Rightarrow (b,a) \in R$.

$R_2$ is not reflexive, because you need, for each element in $S$, something of the form $(x,x) \in R$. In particular (and this will hold for the rest of the relations $R_n$ under consideration), you need $(a,a) \in R_2$ and $(b,b) \in R_2$ since $a,b \in S$.

$R_2$ is actually transitive! Recall that the definition of transitivity is a conditional statement. The hypothesis of this statement is never satisfied, so the statement is always true.


#15: $R_{15} = \{(a,a), (b,b), (a,b), (b,a) \}$

$R_{15}$ is reflexive, as discussed above.

$R_{15}$ is symmetric, as discussed above.

$R_{15}$ is actually transitive as well. We have pairs of the form $(x,y)$ and $(y,z)$ in our relation, where $x = a; y = b; z = a$. So this satisfies the hypothesis of the definition of transitivity. The conclusion of the definition requires $(x,z)$ to (also) be in the relation. But $(x,z) = (a,a) \in R_{15}$, so we're good.