Smallest Symmetric Relation

• Mar 13th 2010, 09:39 PM
TitaniumX
Smallest Symmetric Relation
I have this question for my homework, and I have absolutely no idea how to prove how a "smallest" relation exist. Any help is appreciated. Below is the question:

"Let X be any set. Let R be a relation on X. Prove there is a smallest symmetric relation that contains R."
• Mar 13th 2010, 10:01 PM
Drexel28
Quote:

Originally Posted by TitaniumX
I have this question for my homework, and I have absolutely no idea how to prove how a "smallest" relation exist. Any help is appreciated. Below is the question:

"Let X be any set. Let R be a relation on X. Prove there is a smallest symmetric relation that contains R."

Let $\mathcal{M}=\left\{\mathcal{R}:\mathcal{R}\text{ is a symmetric relation on }X\text{ and }R\subseteq\mathcal{R}\right\}$. The question is $\bigcap_{M\in\mathcal{M}}M$ a symmetric relation on $X$? It is trivially easy to prove that it's a relation, to see that it's symmetric merely note that if $(x,y)\in\bigcap_{M\in\mathcal{M}}M$ then $(x,y)\in N$ for all $N\in\mathcal{M}$ but since each $N$ is symmetric this implies $(y,x)\in N$ for all $N\in\mathcal{M}$ and thus $(y,x)\in\bigcap_{M\in\mathcal{M}}M$. Now it is clear that $\bigcap_{M\in\mathcal{M}}M\supseteq R$ and it is clear that it's the smallest, for if $R\subseteq K$ is a symmetric relation then $K\in\mathcal{M}\implies \bigcap_{M\in\mathcal{M}}M\subseteq K$
• Mar 14th 2010, 10:31 AM
emakarov
Alternatively, you can form a relation $R'$ like this: for every $(x,y)\in R$ put $(x,y)$ and $(y,x)$ in $R'$. Then show that $R\subseteq R'$, $R'$ is symmetric, and if any other symmetric relation contains $R$, it contains $R'$ as well.