0
$\begingroup$

Here's the question:

Prove or give a counterexample to the statement: If $R$ is a reflexive relation on $A$, then $R \circ R$ is also a reflexive relation on $A$.

I completely understand how it works from an intuitive point of view because this means $a\in A \Rightarrow (a,a)\in R$ so plugging the result of $aRa$ (which is $a$) back into $R$ will give you $a$ again. I'm just having a hard time explaining this in the form of a formal proof since $R(R(a,a))$ seems like it would only be proper notation if $R$ was a function and not just a relation and I can't find good examples of proofs involving composition of relations.

1 Answers 1

2

By the definition of composition, $\langle a,a\rangle\in R\circ R$ if and only if there is an $x\in A$ such that $\langle a,x\rangle\in R$ and $\langle x,a\rangle\in R$. If $R$ is reflexive, we may take $x=a$: $\langle a,a\rangle\in R$ and $\langle a,a\rangle\in R$, so $\langle a,a\rangle\in R\circ R$.

That’s really all you have to say.

Informally, $a$ itself provides the ‘stepping-stone’ that’s needed to show that $\langle a,a\rangle\in R\circ R$.

  • 0
    @kamikazekent: You’re welcome!2012-10-22