Smallest and biggest symmetric relations

Question

Can anyone give me some hints about this homework? I`m really stuck. Thank you.

Let R is a binary relation in A. Define T and S using R, such that S is the smallest symmetric relation which $R \subseteq S$ and T is the biggest symmetric relation which $T \subseteq R$. (In other words, S and T are binary relations, defined using the sets R,$\varnothing, Id_{A}, A \times$ A and the operations $\cup,\cap , \ ^{-1}, \circ $)

Answer 1

For $T$, first ask yourself what ordered pairs in $R$ absolutely need to be removed to make a symmetric relation; for $S$, what ordered pairs in absolutely have to be added to $R$ to make a symmetric relation. The problem then is to use the allowable tools to remove them.

1. What kind of relation $P$ on $A$ has the property that $P=P^{-1}$?

2. If $P$ is a relation on $A$, what does $P\cap P^{-1}$ look like? Answering this should help you with $T$.

3. Ask and answer a question similar to (2) that helps with $S$.

There is an alternative way to get at $S$. It’s often the case that the smallest whatsit containing a given object is the intersection of all of the whatsits containing it; this works whenever the intersection of whatsits is again a whatsit. Can you see why it works? (Note that this is a pretty common construction, so it’s well worth understanding.)

In this case you want $S$ to be the smallest symmetric relation on $A$ containing $R$, so in your problem a whatsit is a symmetric relation on $A$. Answering the following questions should help you with $S$.

1. Is it true that the intersection of symmetric relations on $A$ is symmetric?

2. Is there at least one symmetric relation on $A$ that contains $R$?

Answer 2

General Hint. Can you describe the property "$U$ is a symmetric relation" using $\cap$, $\cup$, ${}^{-1}$, and/or $\circ$? Note that "$U$ is symmetric" if and only if $(a,b)\in U\Longleftrightarrow (b,a)\in U$ and that $(x,y)\in U\Longleftrightarrow (y,x)\in U^{-1}$.

Hints for $S$. If $S_1$ and $S_2$ are symmetric relations, and both contain $R$, is $S_1\cap S_2$ a symmetric relation that contains $R$? Is there at least one symmetric relation that contains $R$ (not necessarily the smallest one...)

Hints for $T$. What should you remove from $R$ to get something symmetric? What should you keep?