3
$\begingroup$

On a practice exam, our teacher gave us this answer as the third point in proving:

Let $n$ be a positive integer and let $P = \{$equivalence classes for is-congruent-to-mod-$n\}$. Show that $P$ is a partition of the set of integers.

$\bigcup_{a\in\mathbb{Z}_n} [a] = \mathbb{Z}$: Clearly $\bigcup_{a\in\mathbb{Z}_n} [a] \subseteq \mathbb{Z}$ as each element in each set is an integer. Now let $z \in\mathbb{Z}$. By the division algorithm there is a unique pair $(q,r)$ with $0 \leq r < n$ such that $z=qn+r$. Thus $z\equiv r\pmod{n}$. That is $z\in[r]$, so $z\in\bigcup_{a\in\mathbb{Z}_n}[a]$.

My question is, I do not understand what this is saying. I do not understand the notation, nor do I understand what this is proving.

  • 1
    I think some clarification is needed on what's supposed to be proved here. The equivalence classes of any equivalence relation form a partition. One might prove this fact, or one might prove that "is-congruent-to-mod-$n$" is an equivalence relation, but it seems strange to call something "equivalence classes", which already implies that the relation is an equivalence relation, and then prove specifically for this relation that these classes form a partition.2012-05-23

1 Answers 1

1

We have this little theorem that can be pretty helpful in this situations:

Theorem: Let $\,X\,$ be a non-empty set, and let $\,S:=\{A_i\;\;;\;\;i\in I\}\,$ be a collection of non-empty subsets of $\,X\,$ . Then $\,S\,$ is a partition of $\,X\,$ iff the sets in $\,S\,$ are the equivalence classes of some equivalence relation on $\,X\,$.

Proof: This is a rather easy but interesting exercise.

Well, now just prove that $\,P\,$ fulfills the requirements of the above theorem, for example: define a relation $\,R_n\,$ on $\,\mathbb Z\,$ by $aR_nb\,\Longleftrightarrow a=b+kn\,\,,\,\text{for some integer}\,\,k$ It is pretty straightforward to check reflexivity, symmetry and transitivity, and the equivalence classes are the modulo n ones.

  • 0
    That is part of the above theorem and of the definition [1] of partition, as far as I am aware.[1]:http://en.wikipedia.org/wiki/Partition_of_a_set2012-06-23