0
$\begingroup$

I am struggling with the following question from basics of set theory(equivalence relation, equivalence classes). The question is as follows

In the set $2^{\mathbb{R} \times \mathbb{R} }$ we define the relation R in the following way: for $A,B\subseteq \mathbb{R} \times \mathbb{R} $ we have: $A R B \Leftrightarrow \forall(x,y)\in A \exists (a,p),(q,b)\in B:(x=a \wedge y = b) \wedge \forall(x,y)\in B \exists (a,p),(q,b)\in A:(x=a \wedge y = b)$

  • a) Prove that such defined relation R is equivalence relation.
  • b) Determine equivalence class for the set $\mathbb{R} \times \{ 0, 1\}$ in terms of given relation R.
  • c) Is equivalence class for every finite set in the case of given relation R is a finite set?

    In point (a), verification of reflexivity and symmetry is straightforward. However, I can't do a check for transitivity. Regarding points (b), (c) I stuck completely as I do not see how to modify structure of relation R given in this problem.

Any help/solutions/advices are very, very appreciated(spent by far 3 hours and still can't solve this problem).

$\endgroup$
0
$\begingroup$

I'll answer the transitivity part.

Let's assume that $ARB, BRC$. Let $(x,y) \in A$. Therefore, exists $(a,p), (q,b) \in B$, such that $x=a, y=b$. Since $BRC$, then exists $(r,s), (t,u)\in C$, such that $a=r, p=u$, and also exists $(c, d), (e,f)\in C$, such that $q=c, b=f$. Therefore, for the pair $(r,s), (e,f)$ we have that $x=a=r, y=b=f$, and therefore this is transitive.

Let me know if you need any help from here with the other two questions.

$\endgroup$
  • $\begingroup$ Thanks! (turned out to be easier than I thought). If you would be able to provide me help for point (b), this will be sufficient for me as I see direct consequence to answer (c) from (b). $\endgroup$ – MIT May 21 '16 at 20:24
  • $\begingroup$ If you would be able to solve point (b) and post your solution, I would be very thankful to you. $\endgroup$ – MIT May 21 '16 at 20:24
0
$\begingroup$

Suppose that $A\mathrel{R}B$ and $B\mathrel{R}C$; we want to show that $A\mathrel{R}C$. To do this, we must show two things:

  • if $\langle x,y\rangle\in A$, then there are $\langle a,p\rangle,\langle q,b\rangle\in C$ such that $x=a$ and $y=b$, and
  • if $\langle x,y\rangle\in C$, then there are $\langle a,p\rangle,\langle q,b\rangle\in A$ such that $x=a$ and $y=b$.

It’s a little easier to work with the following equivalent statements:

  • if $\langle x,y\rangle\in A$, then there are $p,q\in\Bbb R$ such that $\langle x,p\rangle,\langle q,y\rangle\in C$, and
  • if $\langle x,y\rangle\in C$, then there are $p,q\in\Bbb R$ such that $\langle x,p\rangle,\langle q,y\rangle\in A$.

(Be sure to verify that these versions really are equivalent to the definition.)

Suppose, then, that $\langle x,y\rangle\in A$. Since $A\mathrel{R}B$, we know that there are $p_1,q_1\in\Bbb R$ such that $\langle x,p_1\rangle,\langle q_1,y\rangle\in B$. Since $\langle x,p_1\rangle\in B$, and $B\mathrel{R}C$, we know that there are $p_2,q_2\in\Bbb R$ such that $\langle x,p_2\rangle,\langle q_2,p_1\rangle\in C$. And since $\langle q_1,y\rangle\in B$, we know similarly that there are $p_3,q_3\in\Bbb R$ such that $\langle q_1,p_3\rangle,\langle q_3,y\rangle\in C$. In particular, there are $p_2,q_3\in\Bbb R$ such that $\langle x,p_2\rangle,\langle q_3,y\rangle\in C$, which is exactly what we wanted. (I.e., we take $p=p_2$ and $q=q_3$.)

This verifies the first point, and the verification of the second is very similar; once you’ve finished that off, you’ll have shown that $R$ is transitive.

For the next part of the question let $A=\Bbb R\times\{0,1\}$, the set of all ordered pairs of real numbers whose second components are $0$ or $1$. We need to find the subsets $B$ of $\Bbb R\times\Bbb R$ such that $A\mathrel{R}B$.

Suppose that $A\mathrel{R}B$; what must $B$ look like? For each $\langle x,i\rangle\in A$ there must be $p,q\in\Bbb R$ such that $\langle x,p\rangle,\langle q,i\rangle\in B$. This means that $B$ must contain at least one ordered pair whose first component is $x$, and at least one ordered pair whose second component is $i$. We also know that for each $\langle x,y\rangle\in B$ there must be $p,q\in\Bbb R$ such that $\langle x,p\rangle,\langle q,y\rangle\in A$; this means that $x$ can be any real number, as we can then take $p=0$ or $p=1$ and have $\langle x,p\rangle\in A$, but $y$ has to be $0$ or $1$. Putting the pieces together, for each $x\in\Bbb R$ there must be a $y\in\Bbb R$ such that $\langle x,y\rangle\in B$, but in fact that $y$ has to be $0$ or $1$, so for each $x\in\Bbb R$ at least one of $\langle x,0\rangle$ and $\langle x,1\rangle$ must belong to $B$. We also know that there has to be at least one $x\in\Bbb R$ such that $\langle x,0\rangle\in B$, and at least one $x\in\Bbb R$ such that $\langle x,1\rangle\in B$. In short, $B$ can be any subset of $\Bbb R\times\{0,1\}$ that has at least one pair with second component $0$, at least one pair with second component $1$, and every real number as first component of at least one pair. (All of these sets are actually subsets of $A$, though of course not every subset of $A$ qualifies.)

For the last part, let $A$ be a finite subset of $\Bbb R\times\Bbb R$, say $A=\{\langle x_k,y_k\rangle:k=1,\ldots,n\}$ for some $n$. Suppose that $A\mathrel{R}B$, and apply the same sort of reasoning to see what conditions $B$ must satisfy; you should find that the reasoning is very similar, but feel free to leave a question if you get stuck.

$\endgroup$
  • $\begingroup$ Thank you for help. However, In the definition of equivalence class, we are for fidning A such that A R B, not opposite as it was stated in your post... $\endgroup$ – MIT May 21 '16 at 20:35
  • $\begingroup$ @MIT: In (b) you’re finding the equivalence class of the set that I chose to call $A$; that’s the set of $B\subseteq\Bbb R\times\Bbb R$ such that $A\mathrel{R}B$. It’s also the set of $B\subseteq\Bbb R\times\Bbb R$ such that $B\mathrel{R}A$, since $R$ is symmetric. $\endgroup$ – Brian M. Scott May 21 '16 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.