As promised, I'm going to give a lot of examples of groups (and of non-groups). They're all going to be relatively simple examples, but they're all important. In each I'm going to give the set and the operation and then show how each of the four properties is satisfied (except, sometimes, I will say something is 'clear' which means that it is either a part of the definition of the operation, or it is very simple). I'm not planning on doing formal proofs, but if you'd like one, I would be happy to write one for you.
Example: The integers under addition form a group.
Let G be the set of all integers (whole numbers), both positive and negative and including zero. Let the operation on this set be addition and denote it by '+'. Then G is a group.
Let G be the set of all integers (whole numbers), both positive and negative and including zero. Let the operation on this set be addition and denote it by '+'. Then G is a group.
- Closure
- If I take two integers and add them together, I get an integer, making G closed.
- Associativity
- Integers are naturally associative under addition.
- Identity
- The integer, 0, is the identity. Any integer plus 0 is still the same integer.
- Inverses
- The inverse of an integer is just its negative. If k is an integer, then k+(-k) = k-k = 0.
Example: The rational numbers under multiplication form a group.
Let G be all rational numbers (any fraction of integers) except for 0 and let the operation on G be multiplication, denoted by '∙'. Then G forms a group.
Let G be all rational numbers (any fraction of integers) except for 0 and let the operation on G be multiplication, denoted by '∙'. Then G forms a group.
- Closure
- Closure holds because the product of two rational numbers is still rational (which is clear from the definition of a rational number). However, 0 is not in G, so it is important to ensure that multiplying two non-zero rational numbers together cannot yield zero. This comes from the fact that if a∙b = 0 then either a or b must be zero, so G is closed.
- Associativity
- Again, associativity is clear from the definition.
- Identity
- The rational number, 1 (or 1/1), is the identity. Any rational number times 1 is itself.
- Inverses
- If r is a rational number, then r∙(1/r) = 1, so every non-zero rational number has an inverse. This condition is why we must remove 0 from G, that is 0 has no inverse.
Example: The integers under multiplication do not form a group.
Let G be the set of integers except for zero and let the operation on zero be multiplication, denoted by '∙'. Closure, associativity, and identity all hold (1 is the identity). However, integers do not have multiplicative inverses. Since every element of a group must have a multiplicative inverse, all I need to do is find one element that does not have an inverse to prove that G is not a group. Any number besides 1 and -1 will do just fine. 2 is an integer, and if 2∙k = 1 then k has to be 1/2 which is not an integer, so although 2 has a multiplicative inverse, it does not have one in G, so G is not a group.
Let G be the set of integers except for zero and let the operation on zero be multiplication, denoted by '∙'. Closure, associativity, and identity all hold (1 is the identity). However, integers do not have multiplicative inverses. Since every element of a group must have a multiplicative inverse, all I need to do is find one element that does not have an inverse to prove that G is not a group. Any number besides 1 and -1 will do just fine. 2 is an integer, and if 2∙k = 1 then k has to be 1/2 which is not an integer, so although 2 has a multiplicative inverse, it does not have one in G, so G is not a group.
Example: The dihedral group of order 8
We finally get to learn the math behind the joke. The dihedral group is a rather abstract thing to think about at first, so try to bear with me. Think about a square piece of paper (the same on both sides) sitting on a table with a black outline of the square on the table. Now suppose I tell you that you can pick it up and turn it however you want and flip it over, but when you put it back down it has to fit right back in the black square on the table. There are really only so many unique ways you can do this, and we talk about those ways in terms of how the square changes from before the shift to after the shift. These changes are as follows: rotating 90 degrees clockwise, rotating 180 degrees clockwise, rotating 270 degrees clockwise, flipping along any of the four lines of symmetry, and doing nothing. These eight things (I can prove that they are the only 8, but you should just trust me) are the elements of our group, D (called the dihedral group of order 8). Now we need an operation. If each element can be thought of as a shift in the square and a and b are two of these elements, then a∙b is simply the shift of a then the shift of b. After this complicated explination, D is a group.
We finally get to learn the math behind the joke. The dihedral group is a rather abstract thing to think about at first, so try to bear with me. Think about a square piece of paper (the same on both sides) sitting on a table with a black outline of the square on the table. Now suppose I tell you that you can pick it up and turn it however you want and flip it over, but when you put it back down it has to fit right back in the black square on the table. There are really only so many unique ways you can do this, and we talk about those ways in terms of how the square changes from before the shift to after the shift. These changes are as follows: rotating 90 degrees clockwise, rotating 180 degrees clockwise, rotating 270 degrees clockwise, flipping along any of the four lines of symmetry, and doing nothing. These eight things (I can prove that they are the only 8, but you should just trust me) are the elements of our group, D (called the dihedral group of order 8). Now we need an operation. If each element can be thought of as a shift in the square and a and b are two of these elements, then a∙b is simply the shift of a then the shift of b. After this complicated explination, D is a group.
- Closure
- Closure might be the hardest one to understand. But as I said before, a∙b is the shift of a and then the shift of b. So then if we pick up the square and perform the a shift and, without putting it down, perform the b shift, then the square will land back in its original position, thus a∙b is equivalent to one of the eight elements of the group.
- Associativity
- This is sort of a result of the definition, but might not be obvious. a∙(b∙c) means construct what b∙c is, and then do it after a, which is just doing a, b, and then c. But (a∙b)∙c means perform (a∙b) and then perform c, which is also just doing a, b, and then c so a∙(b∙c) = (a∙b)∙c.
- Identity
- The element that is "doing nothing" is the identity element. It should be clear that this is the identity because if a is some element of D, then "doing nothing and then doing a" is identical to "doing a and then doing nothing."
- Inverses
- The fact that each element has an inverse should also be pretty clear. Suppose the square is sitting on the table and we call this position (1) and then we perform an element of D and that puts the square in position (2). Then it is pretty obvious you can pick up the square again from position (2) and get it back to position (1). But going from (2) to (1) certainly satisfied the definition of being in D, and performing these two operations in either order is equivalent to "doing nothing."
Next, I'm going over one of the most important groups in the field of group theory, the finite cyclic groups (that name won't make sense yet - its okay). First, though, we need to discuss modular division. In general, when you try to divide two integers, you don't get an integer back. In 3rd grade you learned that 13/5 = 2.6 but, before that, you learned that 13/5 = 2 remainder 3. That remainder is what we're concerned with in modular division. The definition of modular division is as follows:
Definition: Modular Division
Let a and b be integers with b>0. There exists unique integers q and r such that a = bq+r where 0≤r<b. We then say that a = r mod b or that a mod b = r.
Let a and b be integers with b>0. There exists unique integers q and r such that a = bq+r where 0≤r<b. We then say that a = r mod b or that a mod b = r.
Understanding this definition is rather simple if you can see past the math language. To determine a mod b, you just divide a by b and keep only the remainder, r. "a = r mod b" and "a mod b = r" are two ways of saying the exact same thing. A couple examples are 12 = 3 mod 5, 8 mod 3 = 2, and 6 mod 2 = 0. Modular division with negative numbers (only a can be negative) is a little more difficult, but is not something that we need to be concerned with. One thing to notice is that part of the definition is that r<b, so a mod b is always going to be less than b.
Example: The Cyclic Group of Order n
Pick an integer, n>0 and let Z(n) be all the integers from 0 to n-1, that is Z(n) = {0, 1, ..., n-1}. The operation on Z(n) is called modular addition and is denoted by '+'. However, it is not quite the same as standard addition. By "a+b" what we really mean is "a+b mod n." So then the moral is, when we're working in Z(n), to add two numbers, we add them up, divide by n, and keep the remainder. A concrete example is if n = 7 then 4 and 6 are in Z(7). Then 4+6 = (4+6) mod 7 = 10 mod 7 = 3.
Pick an integer, n>0 and let Z(n) be all the integers from 0 to n-1, that is Z(n) = {0, 1, ..., n-1}. The operation on Z(n) is called modular addition and is denoted by '+'. However, it is not quite the same as standard addition. By "a+b" what we really mean is "a+b mod n." So then the moral is, when we're working in Z(n), to add two numbers, we add them up, divide by n, and keep the remainder. A concrete example is if n = 7 then 4 and 6 are in Z(7). Then 4+6 = (4+6) mod 7 = 10 mod 7 = 3.
- Closure
- If a and b are in Z(n), then a+b is some number mod n, and from the definition of modular division, any number mod n must be less than n, so a+b is in Z(n).
- Associativity
- It isn't obvious that modular division is associative. The proof isn't hard, but its tedious and difficult to follow so I'm going to leave it out. However, it is something that you can probably do yourself if you sit down and work it out. You're welcome to just trust me, though. I'm going to give one example to show you that I'm not making it up, but please keep in mind that one example is not a proof. Consider Z(7) again and lets see if 5+(4+6) = (5+4)+6. 5+(4+6) = 5+3 = 1 and (5+4)+6 = 2+6 = 1.
- Identity
- The identity element is 0. Just like in standard addition, adding zero to anything doesn't change it.
- Inverses
- Choose some a in Z(n). My claim is that n-a is the inverse of a, so I need to show that a+(n-a) = 0 = (n-a)+a. Notice that on the left side, a+(n-a) = n mod n = 0 and on the right, (n-a)+a = n mod n = 0. Since the choice of a was arbitrary, each element of Z(n) has an inverse.
There are lots of groups in the world, these are just a few examples. As the very first such examples, its natural to be confused - especially about the dihedral group and the cyclic group. I would love to explain better and more in-depth, but for the the sake of not writing a book, I'm going to stop here. As always, feel free to ask questions and leave comments. In the next entry I'll discuss some of the properties that differentiate different kinds of groups.
No comments:
Post a Comment