Problem: Suppose $R$ is a relation on $A$. Prove that if $R$ is reflexive then $R \subseteq R \circ R$. Counterexample: Let $A = \{1,2\}$ and $R = \{(1,1),(2,2),(1,2)\}$. Then $R \circ R = \{(1,2)\}$. Obviously $R\nsubseteq R \circ R$. This is an exercise I saw in a book, so I assume this is not a valid counterexample. Either I don't understand the problem or the author made some kind of a mistake. Which one is it?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Probably you have to check if $R◦R = \{ (1,2) \}$ is right ... See Composition of relations. $\endgroup$– Mauro ALLEGRANZAMar 23, 2015 at 13:41
-
$\begingroup$ If the containment had gone the other way, i.e., if it had said $R \circ R \subseteq R$, then this would be equivalent to $R$ being transitive. But the way it is worded, saying $R \subseteq R \circ R$, it actually is a correct statement, given that $R$ is reflexive. In my answer, initially I was too hasty and wrote something wrong; I have edited it now, to avoid further confusion. $\endgroup$– Brent KerbyMar 23, 2015 at 14:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
It looks like your calculation of $R \circ R$ in this case is incorrect and that your example is not actually a counterexample to the statement that if $R$ is reflexive then $R \subseteq R \circ R$.
$\begingroup$
$\endgroup$
There are more pairs in the R ◦ R of your example. Think of what you can compose from (1,1) and then (2,2). This will show you why your example is not a counterexample.
In addition, there is a pretty straightforward proof for the initial claim : just take an element of R , make use of the reflexive property and you will show that the element belongs to R ◦ R as well.
