# Smallest and biggest symmetric relations

Can anyone give me some hints about this homework? Im 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$)

• @DidierPiau: First line: "Can anyone give me some hints about this homework?" – Arturo Magidin Jan 31 '12 at 20:17
• @DidierPiau: The second paragraph: describing/defining the smallest symmetric relation on $A$ that contains $R$ using $R$, $\varnothing$, $\mathrm{Id}_A$, $A\times A$, $\cap$, $\cup$, ${}^{-1}$, and $\circ$; and describing the largest symmetric relation on $A$ that is contained in $R$ using the same ingredients... – Arturo Magidin Jan 31 '12 at 20:30
• @Arturo: ...and asking no question at all, in the end. Sure, reading your post, I see that you assume the question is: Show that such an $S$ and such a $T$ exist. This interpretation makes sense, of course, but it is NOT in the original post. (To raise the quality of the formulation of the questions on the site seems a worthy goal, I would say. Don't you think?) – Did Jan 31 '12 at 21:16
• @DidierPiau: I don't follow your comment. The "imperative" in the second paragraph is "Define $T$ and $S$... using blah". So I'm not assuming that the question is "Show that such an $S$ and $T$ exist", but rather that the question is "Can you help me do this problem?" And the problem is "Use blah` to define/construct S and T such that..." This is clearer than many a post we have received, though certainly not the best possible. But my point is that the post does contain an explicit question about an explicit problem. – Arturo Magidin Jan 31 '12 at 21:35
• @Didier: Yes, I think better questions are a worthy goal. But I honestly don't understand your particular objection to this one (as opposed to others). The way I read this question, the OP quoted a problem from his assignment/book (the second paragraph), and asked for help with that problem (the first paragraph). A common occurrence here. You seem to be reading it as if the second paragraph is not a well-defined problem, I'm reading it as something I would see in a textbook, not as an attempt by the OP at framing a task. – Arturo Magidin Feb 1 '12 at 1:56

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$?

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?