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.

  • 0
    Do you know what a partition is?2012-05-14
  • 0
    Yes. I know that each subset in a partition is not empty, and that all of the subsets together form the original set, and that the subsets are disjoint2012-05-14
  • 0
    I am confused by the U. What does U mean?2012-05-14
  • 1
    for non-emptiness show that for each number in $\{0,\dots,n-1\}$ there is an integer number congruent to it.2012-05-14
  • 1
    for the second part show that each integer is congruent to some number in $\{0,\dots,n-1\}$. (somehow converse of the above!)2012-05-14
  • 2
    And finally for the most important part, show that if $a,b$ are two different integers, they are either congruent mod $n$ or not!2012-05-14
  • 0
    @Ali: $\bigcup$ is set union. You should have seen $X \bigcup Y$ in set theory long before getting to partitions. Maybe you aren't familiar with the summation-like notation? The one here simply means set union over all "a" that are elements of the equivalence class mod n.2012-05-14
  • 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
    And that theorem that says that if $xRa$ and $xRb$ then $\hat a =\hat b$ (i.e. two equivalence classes are either equal or disjoint)2012-06-23
  • 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