Thread: Prove the total number of cosets of a particular subgroup in a particular group is m?

I'm having difficulty in understanding a proof given on wikipedia under "Examples" section. The proof can be found at:

Coset - Wikipedia, the free encyclopedia

Math Problem:

If is an additive group of integers and a subgroup such that
where is an integer. Then prove that the cosets of in are the sets.

Proof:

Let be the additive group of integers and the subgroup
where is a positive integer.

Then the cosets of in are the sets , where .

There are no more than cosets, because . <--------------My problem?

The coset is the congruence class of a modulo



My question:

Why is that the ? Specifically why's that ?

I know it's true visually but how do I prove that ?

Is it possible to kindly help me find the reason why's and what it got to do with congruence class of modulo which is stated at the next line of the proof above?

suppose i have the entire set of integers:

Z = {.........-4,-3,-2,-1,0,1,2,3,4,5........}

what set do i get if i add 1 to every integer in this set?

one of the peculiarities of the integers is that there is no "smallest integer" nor no "largest integer" so there is no "bottom" that gets bigger when we add 1 to everything, nor no "top" that keeps everything under a certain amount.

EDIT: here is a "semi-formal" proof that Z = Z+1.

suppose k is in Z. then k-1 is in Z as well, so k = (k-1) + 1 is in Z+1.

on the other hand, suppose m is in Z+1. then m = n+1, for some integer n. hence m = n+1 is also an integer, whence m is in Z.

thus Z+1 = Z, since the two sets contain each other.

EDIT #2:

let's look at a particular m, say m = 5.

now 5Z = {........-25,-20,-15,-10,-5,0,5,10,15,20,25,30.......}.

1+5Z = {.......-24,-19,-14,-9,-4,1,6,11,16,21,26,31......}

2+5Z = {......-23,-18,-13,-8,-3,2,7,12,17,22,27,32.......}

3+5Z = {......-22,-17,-12,-7,-2,3,8,13,18,23,28,33......}

4+5Z = {.....-21,-16,-11,-6,-1,4,9,14,19,24,29,34......}

so far, we haven't had any "overlap" at all, every integer only occurs in ONE of these sets.

what happens when we have:

5+5Z = {.......-20,-15,-10,-5,0,5,10,15,20,25,30,35.....}

all we have done is "shifted 5Z over 5". but 5Z has no "start" and no "end" (it's infinite both ways), so we don't get any "extras" at the "end" or any "new ones" at the "start".

***************************

personally, i don't like this way of looking at Z/5Z. i prefer to think of it as a PARTITION of Z into 5 subsets:

5Z = all integers of the form 5k, for some integer k.
1+5Z = all integers of the form 5k+1
2+5Z = all integers of the form 5k+2
3+5Z = all integers of the form 5k+3
4+5Z = all integers of the form 5k+4

if you like you can think of this partition as being the equivalence classes of the following equivalence relation:

m~n if m-n is divisible by 5.

so now your question becomes: why are the integers of the form 5k+5 of the form 5k?

because 5k+5 = 5(k+1) (we just change k's).

Originally Posted by Deveno

suppose i have the entire set of integers:

Z = {.........-4,-3,-2,-1,0,1,2,3,4,5........}

what set do i get if i add 1 to every integer in this set?

one of the peculiarities of the integers is that there is no "smallest integer" nor no "largest integer" so there is no "bottom" that gets bigger when we add 1 to everything, nor no "top" that keeps everything under a certain amount.

EDIT: here is a "semi-formal" proof that Z = Z+1.

suppose k is in Z. then k-1 is in Z as well, so k = (k-1) + 1 is in Z+1.

on the other hand, suppose m is in Z+1. then m = n+1, for some integer n. hence m = n+1 is also an integer, whence m is in Z.

thus Z+1 = Z, since the two sets contain each other.

EDIT #2:

let's look at a particular m, say m = 5.

now 5Z = {........-25,-20,-15,-10,-5,0,5,10,15,20,25,30.......}.

1+5Z = {.......-24,-19,-14,-9,-4,1,6,11,16,21,26,31......}

2+5Z = {......-23,-18,-13,-8,-3,2,7,12,17,22,27,32.......}

3+5Z = {......-22,-17,-12,-7,-2,3,8,13,18,23,28,33......}

4+5Z = {.....-21,-16,-11,-6,-1,4,9,14,19,24,29,34......}

so far, we haven't had any "overlap" at all, every integer only occurs in ONE of these sets.

what happens when we have:

5+5Z = {.......-20,-15,-10,-5,0,5,10,15,20,25,30,35.....}

all we have done is "shifted 5Z over 5". but 5Z has no "start" and no "end" (it's infinite both ways), so we don't get any "extras" at the "end" or any "new ones" at the "start".

***************************

personally, i don't like this way of looking at Z/5Z. i prefer to think of it as a PARTITION of Z into 5 subsets:

5Z = all integers of the form 5k, for some integer k.
1+5Z = all integers of the form 5k+1
2+5Z = all integers of the form 5k+2
3+5Z = all integers of the form 5k+3
4+5Z = all integers of the form 5k+4

if you like you can think of this partition as being the equivalence classes of the following equivalence relation:

m~n if m-n is divisible by 5.

so now your question becomes: why are the integers of the form 5k+5 of the form 5k?

because 5k+5 = 5(k+1) (we just change k's).

Deveno,...Just brilliant! Thanks for help.

Sorry for prematurely closing this thread.

Deveno, I've a question about the notation you used.

You said(just after the asterisks symbol) that:

Deveno said:
"...personally, i don't like this way of looking at Z/5Z. i prefer to think of it as a PARTITION of Z into 5 subsets:"

I was just wondering:how did you interpret this notation of "Z/5Z"?

I understand on previous sentences you mentioned that "shifted 5Z over 5".

Can you tell me how that equals to "Z/5Z"?

Z/5Z is the set of cosets. the idea is that the "divisor" notation similarity is to remind you of ab/b = a ("factoring out b"), and so Z/5Z is called a "factor group" or more usually, a "quotient group" of Z.

imagine that the integers are like a deck of cards, and you start dealing the cards 1 by 1, into 5 "bowls". every 5th card goes into the same bowl. the bowls are like the cosets: we wind up with 5 subsets of Z, each of which is completely disjoint with all the other 4, and every integer winds up in exactly one coset (no integers get "left out").

for this to work, in general, the subgroup (in this case 5Z) has to have a certain kind of structure, called "normality". for abelian groups (such as Z), every subgroup is normal, so its a non-issue.

Again thanks for help.