Consider the relation $S$ defined on the set $X = \{1, 2, \cdots, 99\}$ as$$ x\mathrel{S}y \Longleftrightarrow x − y \text{ is a multiple of } 11. $$ Into how many classes does it partition the set $X$?

According to what was explained, equivalence classes are subsets all having elements $y$ that could go with one value of $x$.

The above question, according to the solution, has the answer as $11$ classes from $\{1,12,23,\cdots,89\}$ to $\{11,22,33,\cdots,99\}$ with each class starting from $n = 1, \cdots, 11$. But why is there not the set $\{12,23,34,\cdots,89\}$? Is it because those numbers have already appeared in the previous sets?

And for this relation, how many equivalence classes are there?

$$S = \{0,1, 2, \cdots,9\}\\ R = \{(A, B) ∈ P(S) × P(S) : A = S \setminus B \text{ or } A = B\} $$


In general, if $S$ is an equivalence relation on a set $X$, then, the equivalence class of $x\in X$ is defined as: $$[x]=\{y\in X\mid xSy\}.$$

So, $[x]$ must contain, by its definition, all $y\in X$ such that $ySx$, which means that no subset of $[x]$ can be a class on its own, apart from $[x]$ itself.

Let in our case $A=\{1,12,23,\dots,89\}$ and $B=\{23,23,\dots,89\}$. It is obvious that $A=[1]$ and that $B\underset{\neq}{\subset}A$, so $B$ cannot be an equivalence class.

In general, if $x,y\in X$, then it is true that either: $$[x]=[y]$$ or $$[x]\cap[y]=\varnothing.$$

from which we can also imply that $B$ is not an equivalance class.

To prove the former, we think as follows:

For every $x,y$ exactly one of the following is true: $$xSy\text{ or }x\not Sy$$ where, by $\not S$ we mean that $(x,y)\not\in S$.

If $xSy$ then, for every $z\in[y]$ we have that: $$zSy\overset{xSy}{\Rightarrow}xSz\Rightarrow z\in[x]$$ so $[y]\subseteq[x]$. Also, for every $z\in[x]$ we have that: $$xSz\overset{xSy}{\Rightarrow}zSy\Rightarrow z\in[y]$$ so $[x]\subseteq[x]$. So, from the above $[x]=[y]$.

If $x\not Sy$, then, if there exists $z\in X$ such that $x\in[x]\cap[y]$ we get that $z\in[x]$ and $z\in[y]$ so $zSx$ and $zSy$ which implies that $xSy$, which is a contradiction. So, $[x]\cap[y]=\varnothing$.

Using this result, we can see that, if $B$ was an equivalence class, then we should have $B\cap A=\varnothing$ or $B=A$ which is not true, so $B$ cannot be an equivalence class.

Last note! When we write: $$A=\{x\in X\mid \text{some property for }x\}$$ where $X$ is some set, we mean that $A$ includes all the elements $x$ of $X$ that do have the named property. So, the equivalence class of $x$ contains all the elements that are equivalent with $x$!

Edit: For more information on the specific equivalance relation we are using here and in similar constructions, see this article.


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.