Is this relation reflexive?

Question

Suppose $R$ is a relation on $N_4=\{1,2,3,4\}$ such that $R\circ R = R$. How would I prove that $R$ is reflexive? Could you give me some tips about how to start off?

Answer 1

If we add to the opening definition a little (using definitions from Wikipedia):

Suppose $R$ is a relation over its field $N_4=\{1,2,3,4\}$ such that $R\circ R = R$.

...then we have specified that every element of $N_4$ is involved in some way in $R$. This makes the question more interesting, but we can still exhibit an $R$ that is not reflexive:

$$\{(1,1),(1,2),(3,3),(3,4)\}$$

Some values of the range are not defined when we attempt the composition, so they are "lost": $4$, for example cannot be further related to anything by $R$. This does not affect the composition; it is still valid.

We can specify $R$ a little more precisely still, to find a situation where the claim might be true:

Suppose $R$ is a relation on $N_4=\{1,2,3,4\}$ that is left-total and right-total such that $R\circ R = R$.

Now every element in $R$ is involved in both domain and range, and we can make a little progress.

We know that $R$ is transitive. If $aRb$ and $bRc$ then, since $R\circ R = R$, $aRc$.

However, although there must be some reflexive elements (at the ends of transitive chains), it is still not the case that $R$ is necessarily reflexive. As a counterexample, $$ \{(1,1),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4),(4,4)\} $$ in which 1 and 4 are reflexive but 2 and 3 are not.

Answer 2

This cannot be proven, because it is false. For example, $R$ could be the empty relation, which is not reflexive but which satisfies $R \circ R = R$. Do you have any further assumptions about $R$?