Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $r \in \mathbb{N}$. Observe the equivalence relation $\sim \subseteq \mathbb{Z} \times \mathbb{Z}$ defined as $x \sim y :\Leftrightarrow (\exists k \in \mathbb{Z})(y=x+kr)$. Show that an operation $'+'$ on $\mathbb{Z}/\sim$ given by $[x]_\sim + [y]_\sim := [x+y]_\sim$ is well-defined.

My attempt at a proof:

Let $x\sim x', y\sim y'$, then we know that $(\exists k_1 \in \mathbb{Z})(x=x'+k_1r)$ and $(\exists k_2 \in \mathbb{Z})(y=y'+k_2r)$. Adding $x$ and $y$, we see that $x+y=x'+y'+(k_1+k_2)r$. Because $\mathbb{Z}$ is closed under addition, $k_1+k_2 \in \mathbb{Z}$, and eventually $x+y\sim x'+y'$.

Unfortunately, I'm not even sure whether I'm on the right track here. As far as I can see, I've shown that adding two elements of (different) equivalence classes yields an element, whose equivalence class is in $\mathbb{Z}/\sim$. Is that sufficient to show that $'+'$ is well-defined?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Yes, you're on the right track. "Well-defined" just means that it should be an actual operation that takes 2 equivalence classes and sends them to a (uniquely determined) equivalence class. The way the operation is written makes use of specific representatives of the equivalence classes. $[x+y]$ makes sense as an element of $\mathbb{Z}/\sim$, but you need to know that it is determined by the classes of $x$ and $y$, rather than depending on the choices of representatives. To do so, you suppose that another arbitrary choice of representatives is made (your $x'$ and $y'$), and show that the sum $[x'+y']$ is the same. That is what your work shows.

The language in your second to last sentence isn't entirely accurate. What you've shown is that adding 2 equivalence classes determines an equivalence class. The key word is "an" (singular); you've shown that you couldn't get different equivalence classes by "adding" in different ways.

To contrast, suppose $r=3$ and we want to "define" an operation by $[x]^{[y]}=[x^y]$. If we try to combine $[2]$ and $[1]$ using this "operation", we get $[2]^{[1]}=[2^1]=[2]$. But $[1]=[4]$, so we also get $[2]^{[1]}=[2]^{[4]}=[2^4]=[16]=[1]$. Thus this "operation" is not well-defined. (Of course, there are other problems, like defining powers of $0$ or negative powers, but the point here is the non-uniqueness, even if it did make sense.) Better examples of non-well-defined "operations" arise when you study groups. There you study equivalence classes called cosets of subgroups and try to combine them analogously to how equivalence classes mod $r$ are added in your problem. You find that unless the subgroup satisfies a certain property called being "normal", the "operation" is not well-defined.

share|improve this answer
    
thank you very much, your answer was very helpful. –  Greg S Nov 21 '10 at 10:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.