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