Lifting an equivalence relation on elements to a relation on sets

Question

If every element of $A$ is equivalent (by an equivalence relation $R$) to some element of $B$

$\forall x\in A\ldotp \exists y \in B\ldotp x\,R\,y$

and vice versa

$\forall y\in B\ldotp \exists x \in A\ldotp x\,R\,y$

then what can I deduce about the relationship between $A$ and $B$? I certainly can't say that they're equal, but they would seem to be equivalent in some sense. Perhaps one could say something to do with bijections here? Or perhaps equivalence classes?

---

^{My motivation for asking is that I have a theorem of the form outlined above, and I would like to find a simpler way to state it. Originally my $R$ was just straightforward equality ($=$), and then I could just deduce $A = B$. Now my $R$ is no longer $=$, but I'd still like to keep the statement of my theorem nice and succinct if I can.}

Answer 1

From your question it seems that the relation $R$ is defined in $A\cup B$.

You can therefore say that from your assumptions, as sets, we have $A/R=B/R=(A\cup B)/R$

Indeed, any equivalence class in $(A\cup B)/R$ contains both an element of $A$ and an element of $B$.

So the natural inclusions

$A/R\hookrightarrow (A\cup B)/R$ and $B/R\hookrightarrow (A\cup B)/R$ are onto.

Answer 2

If $R$ is an equivalence relation on $X$ and $A,B\subseteq X$, then your statement is equivalent to: The partition of $X$ into equivalence classes is such that each equivalence class intersecting $A\cup B$ intersects both $A$ and $B$. I do not think much more can be said.

Answer 3

This' neat :)

From the observation,

$ \;\;\; A \subseteq B \\\equiv \forall a \in A. a \in B \\\equiv \forall a \in A. \exists b \in B. b = a $

We can generalize this preorder from any equivalence relation $\sim$ by defining $$A \subseteq_\sim B :\equiv (\forall a \in A. \exists b \in B. a \sim b)$$

(Now this is indeed a preorder ---ie reflexive and transitive ... I couldn't prove antisymmetry.)

Anyhow, from this we can extend $\sim$ to sets by $$A \approx B :\equiv A \subseteq_\sim B \land B \subseteq_\sim A$$

Now this is indeed an equivalence relation and it is induced by the given $\sim$. We may call this set equivalence by $\sim$-extensionality, for example.

I had fun doing this; hope it helps!

---

Edit: it'd be nice to relate $\approx$ with $\sim$; we can show $$A \approx B \implies A/\sim \,= B/\sim$$ Indeed, $\;\;\;X \subseteq_\sim Y \\\equiv \forall x \in X. \exists y \in Y. x \sim y \\\equiv \forall x \in X. \exists y \in Y. x/\sim \,=\, y /\sim \\\equiv \forall x \in X. \exists y \in Y. x/\sim \,=\, y /\sim \,\in Y/\sim \\\Rightarrow \forall x \in X. x/\sim \,\in Y/\sim \\\equiv X/\sim \;\subseteq\, Y/\sim $ and thus $\;\;\; A \approx B \\\equiv A \subseteq_\sim B \subseteq_\sim A \\\Rightarrow A/\sim \subseteq B/\sim \subseteq A/\sim \\\equiv A/\sim \,=\, B/\sim $

It'd be nice if the converse also held; we'll leave that as an exercise to the diligent reader/poster ;)