3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Isn't an equivalence relation only defined between members of the same set ? $\endgroup$
    – Tom Collinge
    Jun 26, 2014 at 14:22
  • 1
    $\begingroup$ @TomCollinge yeah they are, say some set $U$. Then in this setting, we (most likely) have $A,B \subseteq U$ :) Also, John, thanks for the context (ie the text in small font). Found it helpful! $\endgroup$
    – Musa Al-hassy
    Jun 28, 2014 at 3:40

3 Answers 3

Reset to default
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Excellent, I had been hoping I would be able to say something short and sweet like $A/R = B/R$. Thank you. $\endgroup$
    – John Wickerson
    Jun 28, 2014 at 6:23
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thanks for this Moses :-). I wonder: to what extent is your set equivalence by $\approx$-extensionality ($A \approx B$) the same as the $A/{\approx} = B/{\approx}$ suggestion by user126154? $\endgroup$
    – John Wickerson
    Jun 28, 2014 at 6:27
  • $\begingroup$ Some progress has been recorded; see edited solution :) $\endgroup$
    – Musa Al-hassy
    Jun 29, 2014 at 15:39
  • 1
    $\begingroup$ Cool. Thanks Moses! I'll have a read in a mo, but just a quick remark: you get better formatting of your quotients if you type A/{\approx} (gives $A/{\approx}$) instead of A/\approx (gives $A/\approx$). $\endgroup$
    – John Wickerson
    Jun 29, 2014 at 15:41
  • $\begingroup$ Thanks! That was really bothering me and I didn't know what to do. I don't know much about the TeX system of stackexchange, but I was really impressed by the juxtaposition of my calculations above ( in the edit): it just happened, I didn't do anything :) $\endgroup$
    – Musa Al-hassy
    Jun 29, 2014 at 15:45
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .