To quote Halmos:

If $R$ is an equivalence relation in $X$, and if $x$ is in $X$, the equivalence class of $x$ with respect to $R$ is the set of all elements $y$ in $X$ for which $x R y$. Examples: if $R$ is equality in $X$, then each equivalence class is a singleton; if $R = X \times X$, then the set $X$ itself is the only equivalence class.

~P. R. Halmos, Naive Set Theory (p. 28)

The first one, I think I understand. Each equivalence class is a singleton because each element $x$ in $X$ is only equal to itself.

The second is confusing me further the more I think about it, perhaps because of the wording. If $R = X \times X$, do I still consider it to be 'in' $X$ or is it 'in' the result of $X \times X$? If it's the former, how is that any different than equality in $X$? When comparing across sets rather than within one set, the equality results should still be the same, yielding a number of singletons. If it's the latter, then surely we're now dealing with a series of ordered pairs that did not exist in the set $X$ beforehand, precluding it from being the equivalence class.

Or, is it that it's neither of these, and the set $X$ used here is being treated like the $x$ we are seeking equivalence classes for in his initial definition? This latter definition seems to be the only way I can get my head around how $X$ itself ends up being the equivalence class, but also seems like I'm missing something vital in making that assumption.

  • $\begingroup$ If $R$ is the $X \times X$ that means that any two elements $x, y \in X$ are related to each other: $x R y$ because obviously the pair $(x, y)$ is always in $X \times X = R$. So the equivalence class of any $x \in X$ is the whole set: $[x] = X$. $\endgroup$ – 0XLR May 24 '19 at 20:37

I think the key idea here is that you can regard an equivalence relation (well... any relation really) $R$ in $X$ as a subset of $X\times X$.

How? Well, by saying that $$xRy\iff (x,y)\in R\subset X\times X$$

Does this make sense? If it does, then consider the first case, the equality one. Here the subset corresponding to this equivalence relation would be

$$R=\{(x,x)\mid x\in X\}\subset X\times X$$

i.e. the elements where both entries are the same. This is because an element is only identified with itself, and thus each equivalence class contains only one element.

If, on the other hand, the subset of $X\times X$ corresponding to the equivalence relation is the whole set $R=X\times X$, then every pair of elements is identified. Therefore the equivalence class of any element in $X$ is the whole set $X$, because all elements are identified with it.

I hope this helps.


Recall that we can define a relation $R$ on a set $X$ as a set of ordered pairs from $X \times X$. That is to say, a relation on a set is a subset of the set's Cartesian product with itself, i.e.

$$R = \{(x,y) \mid x,y \in X, \text{x is related to y by ... whatever rule defines the relation} \} \subseteq X \times X$$

To say that $R = X \times X$ thus implies that for any $x$ and $y$ in $X$, the ordered pair $(x,y)$ is in $R$, or equivalently $xRy$ for all $x,y\in X$.

Thus, every element is simultaneously related to every other element in $X$. Thus, this defines a single equivalence class (since an equivalence class "bundles" together all elements which are related to each other). We can conveniently simply call this class $X$ since all of these related elements are, in fact, in $X$.


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.