1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ Probably you have to check if $R◦R = \{ (1,2) \}$ is right ... See Composition of relations. $\endgroup$ Mar 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$ Mar 23, 2015 at 14:20

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .