I don't understand equivalence classes with relations

1.1k Views Asked by At

I am not quite understanding equivalence classes. For example I have this problem:

Let $A$ be the set of integers and $\quad a\;R\;b\quad$ if and only if $\quad |a| = |b|$.

I have proved that this is an equivalence relation, (its reflexive, symmetric and transitive), but how do I show the equivalence classes?

3

There are 3 best solutions below

8
On BEST ANSWER

Equivalence classes (wrt your equivalence relation) are subsets of elements of the original set with the following property: every element of a certain equivalence class must be equivalent (wrt the equivalence relation) to any other in it and inequivalent to any other out of it.
This implies that equivalence classes are disjoint subsets of the original set. (*)

You are asked to construct the maximal subsets of $\mathbb Z$, such that - picked one - every element in it has the same absolute value as any other element of the subset. It should be fairly easy to understand how many elements can belong to every equivalence class in this case (there is an important exception, though: $0$).
Notice that in general the cardinalities of the equivalence classes of a set wrt an equivalence relation are different!

(*) This second part of the definition was added after the useful comments of two users below.

0
On

Its best to begin with the following definition.

The equivalence class associated with $a \in A$ with respect to $\sim$ will be denoted $[a],$ and has defining property: $b \in [a]$ iff $b \sim a$.

We can then define the term 'equivalence class' as follows.

An equivalence class of $A$ with respect to $\sim$ is subset $B \subseteq A$ such that $B=[a]$ for some $a \in A$.

We can now discover the equivalence classes iteratively. Choose $a_0 \in A$ and work out what $[a_0]$ is. Then choose $a_1 \in A$ such that $a_1 \notin [a_0]$ and work out what $[a_1]$ is. Then choose $a_2 \in A$ such that $a_2 \notin [a_1] \cup [a_0]$, and work out what $[a_2]$ is. etc.

For example, in the case of $A =$ the integers, we might proceed as follows.

Choose $a_0 = 0$.

Then $b \in [a_0]$ is equivalent to $b \sim a_0$, which is equivalent to $|b| = |a_0|$, which is equivalent to $|b|=0$, which is equivalent to $b=0$. So $b \in a_0$ iff $b=0$, or in other words $a_0 = \{0\}$.

Next choose $a_1 = 1$. Notice $1 \notin [a_0]$.

Then $b \in [a_1]$ is equivalent to $b \sim a_1$, which is equivalent to $|b| = |a_1|$, which is equivalent to $|b|=1$, which is equivalent to $b=-1$ or $b=1$. So $b \in a_1$ iff $b=-1$ or $b=1$, or in other words $a_1 = \{-1,1\}$.

Next choose $a_2 = 2$. Notice $2 \notin [a_1] \cup [a_0]$.

Wash, rinse and repeat.

At some point, you'll intuit that the equivalence classes of $A$ with respect to $\sim$ are precisely the $B \subseteq A$ such that there exists natural $n$ such that $B = \{-n,n\}$. Note this is only true if we regard zero as a natural number.

3
On

The quotient set of integers modulo your relation $R$ can be identified with the set of natural numbers $\geq 0$, via the following bijection: set $$f:\frac{\mathbb{Z}}{R}\longrightarrow\mathbb{N}$$ sending the class $[a]$ to the natural number $|a|$, hence you get:

$\bullet$ a well-defined map: if $a$ and $a'$ both represent the class $[a]$, then they differ by the signum, hence their absolute value $|a|=|a'|$ is the same.

$\bullet$ suppose $|a|=|a'|$ for a couple $a,a'$ of integers. Then they differ by the signum, hence they represent the same equivalence class in the quotient $\frac{\mathbb{Z}}{R}$, and this shows that $f$ is injective

$\bullet$ given a natural number $a\geq 0$, then $f([a])=a$, meaning that $f$ is also surjective.