1
$\begingroup$

I was puzzling over another question: Let $R$ be an equivalence relation on a set $A$, $a,b \in A$. Prove $[a] = [b]$ iff $aRb$. And this made me discover that $$(0) \; \langle \forall a,b :: aRb \equiv \langle \forall x :: aRx \equiv bRx \rangle \rangle$$ is an alternative characterization of $R$ being an equivalence relation, and one which only uses logical equivalence. (Note that throughout this question, $a$, $b$, $c$, and $x$ implicitly range over a fixed set $A$.)

Update 3: To put it more explicitly and longwindedly, I discovered that $$R \textrm{ is an equivalence relation on } A \;\equiv\; \langle \forall a,b \in A :: aRb \:\equiv\: \langle \forall x \in A :: aRx \equiv bRx\rangle \rangle$$

(I've updated this question to ask for the correctness of this definition, and have posted my original question as a separate one: Is this alternative definition of 'equivalence relation' well-known? useful? used?)

The nice thing about this definition is that it says, "equivalence of $a$ and $b$ means that it doesn't matter which of the two you substitute", which seems to be the essence of equivalence (cf. Leibniz' law).

Is this alternative definition well-known? useful? used? correct?


Update: Two comments and one answer suggest that my $(0)$ is not equivalent to the combination of \begin{align} (1) & \langle \forall a :: aRa \rangle \\ (2) & \langle \forall a,b :: aRb \;\Rightarrow\; bRa \rangle \\ (3) & \langle \forall a,b,c :: aRb \land bRc \;\Rightarrow\; aRc \rangle \\ \end{align} However, as far as I can see these are equivalent. One direction is proven in the answers to the question referenced above. For the other direction, we have for all $a$ \begin{align} & aRa \\ \equiv & \;\;\;\;\;\text{"using $(0)$ with $b:=a$"} \\ & \langle \forall x :: aRx \equiv aRx \rangle \\ \equiv & \;\;\;\;\;\text{"logic"} \\ & \textrm{true} \\ \end{align} and for all $a$ and $b$ \begin{align} & aRb \\ \equiv & \;\;\;\;\;\text{"by $(0)$"} \\ & \langle \forall x :: aRx \equiv bRx \rangle \\ \Rightarrow & \;\;\;\;\;\text{"choose $x:=a$"} \\ & aRa \equiv bRa \\ \equiv & \;\;\;\;\;\text{"by $(1)$"} \\ & bRa \\ \end{align} and for all $a$, $b$, and $c$ \begin{align} & aRb \land bRc \\ \equiv & \;\;\;\;\;\text{"by $(0)$, twice"} \\ & \langle \forall x :: aRx \equiv bRx \rangle \land \langle \forall x :: bRx \equiv cRx \rangle \\ \Rightarrow & \;\;\;\;\;\text{"logic"} \\ & \langle \forall x :: aRx \equiv cRx \rangle \\ \equiv & \;\;\;\;\;\text{"by $(0)$ with $b:=c$"} \\ & aRc \\ \end{align}

Or am I missing something?


Update 2: In the above I have now made all quantifications explicit, to prevent any confusion.

$\endgroup$
  • $\begingroup$ This does not characterize equivalence relations. For instance, the empty relation satisfies this. Or for a nonempty example, the relation on $\mathbb Z$ where $1$ and $2$ are related to themselves and to each other and nothing else is related to anything else. $\endgroup$ – Santiago Canez Jun 19 '13 at 16:35
  • $\begingroup$ You would need to assume beforehand that $R$ is reflexive in order for this to work. $\endgroup$ – Santiago Canez Jun 19 '13 at 16:47
2
$\begingroup$

What you have almost works. The only problem with it is that it makes $R$ a proper class, since it implies that $xRx$ for all sets $x$. You really ought to quantify over the domain of $R$; if that’s $D$, you want

$$\forall x,y\Big(xRy\leftrightarrow x,y\in D\land\forall z\in D(xRz\leftrightarrow yRz)\Big)\;.$$

Now you get $xRx$ precisely for those sets $x$ that are elements of $D$, which is what you want.

$\endgroup$
  • $\begingroup$ And that is what I assumed was clear from the context, and that is why I added the following in an update: "$a$, $b$, $c$, and $x$ implicitly range over a fixed set $A$", and why I made my definition more explicit in another comment: $$R \textrm{ is an equivalence relation on } A \;\equiv\; \langle \forall a,b \in A :: aRb \:\equiv\: \langle \forall x \in A :: aRx \equiv bRx\rangle \rangle$$ Now that the correctness of $(0)$ is out of the way, what about my original question: is it well-known/useful/used? $\endgroup$ – Marnix Klooster Jun 19 '13 at 20:43
  • 2
    $\begingroup$ @Marnix: I don’t think that I’ve ever seen it singled out explicitly, though I expect that someone has done so somewhere. I just think of it as yet another part of the constellation of ideas that includes equivalence relations, partitions, and quotients as ways of looking at one and the same thing. $\endgroup$ – Brian M. Scott Jun 19 '13 at 20:50
3
$\begingroup$

Your characterization of $R$ may "beg the question": the characterization of an equivalence relation:$$aRb \equiv \langle \forall x :: aRx \equiv bRx \rangle$$

works fine, provided we know that $R$ is reflexive. So if you're trying to define an equivalence relation, we run into problems.

However, if you have the added premise: "given $R$ is an equivalence relation," then indeed, $R$ is reflexive. So if you are offering an alternative characterization of what it means for two elements to be related under $R$, given that $\,R\,$ is an equivalence relation, then I think your characterization is fine, and is appealing at an intuitive level. However, you'll want to restrict $x$ to the domain (set $S$) on which the equivalence relations $R$ is defined, and also add the qualification that $a, b \in S$. $$a, b \in S \land aRb \equiv (\forall x \in S :: aRx \equiv bRx)$$

$\endgroup$
  • $\begingroup$ @amWhy: You seem to say that my $(0)$ does not imply reflexivity, i.e., it does not imply $(1)$, while it clearly does. Is the confusion perhaps over quantifications? I've made these now explicit in my question, just in case. For complete completeness, my fully formal definition would be $$R \textrm{ is an equivalence relation on } A \;\equiv\; \langle \forall a,b \in A :: aRb \:\equiv\: \langle \forall x \in A :: aRx \equiv bRx\rangle \rangle$$ How is that not equivalent to the standard definition of an equivalence relation? $\endgroup$ – Marnix Klooster Jun 19 '13 at 20:06
  • $\begingroup$ What about the set S of all letters of the English Alphabet, and the Relation R defined on S given simply by $R = \{(a, b)\mid aRb\} = \{(a, a), (b, b), (a, b), (b, a)\}.$. Then since $xRz \equiv F \land yRz\equiv F$, by definition (0), we have that "$xRz \equiv yRz$" evaluates to true $(F\equiv F)$ is true. Which by definition (0), means $x R y$ must also be true. Since you have that $xRy \equiv (xRz \equiv yRz)$. But $(x, y)\notin R$. This gives us ultimately, that you are claiming $F\equiv T$ in this case $\endgroup$ – Namaste Jun 19 '13 at 20:13
  • $\begingroup$ Of course, we won't run into such a problem if it happens to be true that $R$ is an equivalence relation. But then, why the need to say that an equivalence relation is an equivalence relation? $\endgroup$ – Namaste Jun 19 '13 at 20:17
  • $\begingroup$ @Marnix and user1411 are correct: $(0)$ implies that $R$ is reflexive. In fact, it implies too much reflexivity: it implies that $xRx$ for all sets $x$. $\endgroup$ – Brian M. Scott Jun 19 '13 at 20:26
  • 1
    $\begingroup$ Well now after all the qualifications you've added (not explicitly to your definition (0), most of which were suggested, you have omitted the problem. What you originally wrote and posted was not a complete or accurate definition of an equivalence relation. Why don't you re-post what you've now corrected, leaving a trace of your thought pattern and the modifications, given my answer and comments of others? What you have now qualified with ifs and or buts is nothing more than using different notations to try and say what is better said elsewhere. $\endgroup$ – Namaste Jun 19 '13 at 22:02

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.