2
$\begingroup$

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

  • 1
    @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.2012-02-01

2 Answers 2

3

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

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?