Breaking an equivalence relation into equivalence classes

257 Views Asked by At

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\} $$

1

There are 1 best solutions below

0
On

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.