Why do I need to know that rng R = A for this proof?

20 Views Asked by At

Let $A$ be a nonempty set. Show that if $R$ is a symmetric and transitive relation on $A$ such that $rngR = A$, then $R$ is reflexive on $A$.

So I proved this by saying: For all $x,y\in A$, $(x,y)\in R$ implies $(y,x)\in R$. (definition of symmetric relation)

And for all $x,y\in A$, $(x,y)\in R$ and $(y,x)\in R$ implies $(x,x)\in R$. (definition of transitive relation)

Therefore, $R$ is reflexive.

My prof made a comment on my proof, asking what rngR=A is for, which I don't know so an answer would be very much appreciated.

2

There are 2 best solutions below

0
On BEST ANSWER

Suppose that $\operatorname{rng}R\ne A$; then there is some $x\in A$ that is not in the range of $R$. But then $R$ cannot be reflexive, because $\langle x,x\rangle\notin R$.

The problem with your argument is that in order to show that $\langle x,x\rangle\in R$, you have to have some $y\in A$ such that $\langle x,y\rangle\in R$ and hence by symmetry $\langle y,x\rangle\in R$. If you don’t have such a $y$ in the first place, you can’t use transitivity to get $\langle x,x\rangle$. And if $x$ is not in the range of $R$, then you don’t have such a $y$.

If $\operatorname{rng}R=A$, then for each $x\in A$ there is some $y\in A$ such that $\langle y,x\rangle\in R$. Symmetry then tells you that $\langle x,y\rangle\in R$, and transitivity that $\langle x,x\rangle\in R$, so in fact we see that $R$ is reflexive if and only if $\operatorname{rng}R=A$.

4
On

In general, transitive + simmetric does not say that the relation is reflexive. For example, $$A=\{x,y,z\},$$ and $$R=\{(x,y),(y,x)\}.$$