0

Hi I have the follow questions that I'm not quite able to solve.

Let X be a set, and let $\mathcal R$ be a relation on $X$ which is reflexive and transitive. We define a new relation $\mathcal Q$ on $X$ by declaring that $x$$\mathcal Q$$y$ ⇔ ($x$$\mathcal R$$y$ and $y$$\mathcal R$$x$) $\forall$ $x, y ∈ X.$

(1) Show that $\mathcal Q$ is an equivalence relation.

(2) Let $\mathcal O$,$\mathcal O'$ ∈ X/$\mathcal Q$ be two equivalence classes for the relation $\mathcal Q$. Show that the following conditions are equivalent:

(a) there exist $x$ ∈ $\mathcal O$ and $x'$∈ $\mathcal O'$ such that $x\mathcal Rx'$;

(b) for all $x$ ∈ $\mathcal O$ and all $x'$ ∈ $\mathcal O'$, we have $x\mathcal Rx'$

(3) We define a relation $\overline R$ on $X/\mathcal Q$ by declaring that $\mathcal O \overline R \mathcal O'$ ⇔ (∀$x$ ∈ $\mathcal O$, ∀$x$ ∈ $\mathcal O'$, $x\mathcal Rx'$).

For all $\mathcal O$, $\mathcal O'$ ∈ $X$/$\mathcal Q$. Show that $\overline R$ is an order relation on $X$/$\mathcal Q$.

So I'm pretty sure (1) follows directly from the definition since an equivalence class is defined as a relation that is reflexive, symmetric and transitive. Now since it states that $\mathcal R$ is reflexive and transitive, and the right side just defines symmetry, the conclusion can only be that the relation is also symmetric. This means that $\mathcal Q$ is an equivalence relation. But how do I prove this correctly?

for (2) and (3), they also seem very similar, since they are all equivalence classes meaning that all these definitions must follow from that. However I'm struggling to get anywhere with the correct proof.

23408924
  • 505
  • 3
  • 14

1 Answers1

1

To prove that $Q$ is reflexive, take $x \in X$;
since $R$ is reflexive, $x R x$, whence $xRx$ and $xRx$, that is, $xQx$.

Now suppose that $xQy$. This means that $xRy$ and $yRx$.
Hence $yRx$ and $xRy$, and therefore, $yQx$.
Thus $Q$ is symmetric.

Suppose now that $xQy$ and $yQz$.
It follows that $xRy$, $yRx$, $yRz$ and $zRy$;
from the first and the third, since $R$ is transitive, $xRz$;
from the fourth and the second, $zRz$.
So $xQz$, and we conclude that $Q$ is transitive.

For the second part, (b) implies (a) follows from the fact that equivalence classes are non-empty.
For the converse, suppose $x \in O$ and $x' \in O'$ are such that $xRx'$.
Now take $y \in O$ and $y \in O'$; we want to prove that $yRy'$.
Notice that since $x,y \in O$, we have that $xQy$, that is, $xRy$ and $yRx$.
Analogously $x'Ry'$ and $y'Rx'$.
Now, $yRxRx'Ry'$ and by transitivity of $R$, we get the desired result.

Perhaps you can now prove the last part.
If you get stuck again, let me know, and I'll try to give a hint.

amrsa
  • 12,917