Elementary set theory - challenging problem from relations and equivalence classes

Question

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

Answer 1

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.

Answer 2

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.