Given $R$, a symmetrical relation over $A$, if $(R \circ R)$ is a function, then $R$ is a function

45 Views Asked by At

Given a non-empty set $A$ and the symmetrical relation $R \subset A\times A$ such that $(R\circ R)$ is a function. The exercise asks if $R$ is a function.

I'm not sure if my reasoning is correct here. Here's what I came up with so far.

If $R$ is symmetrical, then $\forall x,y \in (R\circ R)$, $x=y$.

So every element of $R$ is of the form $(x,x)$, which is the identity function. Is that right?

1

There are 1 best solutions below

0
On BEST ANSWER

$\newcommand{\dom}{\operatorname{dom}}$It’s true that $R\circ R$ is the identity function on $\dom R$, but $R$ itself need not be. For instance, let $A=\{0,1\}$ and $R=\{\langle 0,1\rangle,\langle 1,0\rangle\}$; then $R$ is symmetric, $R\circ R$ is the identity function on $A$, and $R$ is a function, but not the identity function on $A$.

Suppose that $x,y,z\in A$ and $\langle x,y\rangle,\langle x,z\rangle\in R$; we want to show that $y=z$. By symmetry we must have $\langle y,x\rangle\in R$, so $\langle y,y\rangle,\langle y,z\rangle\in R\circ R$. And $R\circ R$ is a function, so $y=z$, as desired, and $R$ is indeed a function.