Definition. A binary operation on a set S is a function which takes a pair of elements and produces another element . That is, a binary operation is a function .
Binary operations are usually denoted by infix operators:
(The last notation --- suppressing the operation symbol entirely --- is what you do when you write " " to mean "3 times x". In this case, the operation is multiplication.)
When you are trying to show that you have a binary operation on a set S, the issue is usually whether S is closed under the operation. This means that for all , you have .
As with any universal statement ("for all "), to prove that is a binary operation on S you must show that it holds for arbitrary s and t. You are not allowed to pick {\it specific} elements s and t in the set.
On the other hand, if you think that S is not closed under , you need to give a specific counterexample. You can {\it disprove} a universal statement with a single counterexample.
Most binary operations satisfy additional properties. Here are two that are particularly important.
Definition. Let be a binary operation on a set S.
(a) is associative if for all .
(b) is commutative if for all .
Example. ( Binary operations on familiar number systems) Addition, subtraction, and multiplication are binary operations on the integers , the rational numbers , the real numbers , and the complex numbers .
For example, consider the operation of addition on the set of integers. If you add two integers, you get a well-defined integer as the result. Addition is therefore a binary operation on .
Addition and multiplication are both associative and commutative operations on , , , and .
Subtraction is not associative:
Subtraction is also not commutative:
Since the counterexamples I gave used only integers, which are elements of , , , and , the last two statements are true for all of these sets.
Division is not a binary operation on any of these sets. For one thing, you cannot divide by 0. For example, and but .
Example. ( A binary operation defined by a table) Consider the following operation table:
The first row says that
The second row says that
(The first element is the row element and the second element is the column element.)
is commutative --- in fact, this follows from the fact that the table is symmetric about the main diagonal (the diagonal running from northwest to southeast).
However, is not associative:
It's possible to define a binary operation using a table if the set is small. If the set is too large or the set is infinite, this isn't useful or possible.
Example. ( Function composition as a binary operation) If X is a set and is the set of functions from X to X, then function composition is a binary operation on .
As the diagram shows, if and are functions, then the composite is another function from X to X.
Example. ( An "operation" which isn't well-defined) If , can I define to be "an integer bigger than "? That is, does this define a binary operation on ?
In this case, the supposed operation apparently produces an integer, so the issue is not whether the set is closed under the operation. The problem is that "an integer bigger than " does not define a unique integer. For example, if and , then . The definition would allow to be 7 (since , but would also work (since ).
The input does not produce a unique output : that is, does not define a function from pairs of integers to integers. Thus, is not a binary operation.
Definition. A group is a set G with a binary operation such that:
(a) ( Associativity) for all .
(b) ( Identity) There is an element such that for all .
(c) ( Inverses) For each , there is an element (the inverse of a) such that .
The notations " " for the operation, "e" for the identity, and " " for the inverse of a are temporary, for the sake of making the definition. In particular examples, you'll see that other notations are used. And I'll say something about the general issue of notation in groups later on.
Notice that the operation in a group does not need to be commutative. That is, need not equal .
Definition. A group is abelian if the group operation is commutative --- that is, for all a and b.
The term "abelian" honors Niels Henrik Abel (1802--1829). Abel and Paolo Ruffini were the first to demonstrate the unsolvability of the general quintic equation.
Definition. The order of a group is the number of elements in the group, if it is finite. Otherwise, the group has infinite order. denotes the order of the group G.
A finite group is a group whose order is finite; an infinite group is a group whose order is infinite.
Example. ( Group structures on familiar number systems) , , , and are groups with addition as the operation. All of them are infinite.
Consider, for example, the case of . The sum of two integers is an integer. Addition of integers is associative. 0 is an identity for addition. And if , the additive inverse of x is , another integer.
Example. ( The nonnegative rationals under addition) is not a group under addition.
is certainly closed under addition, and addition of rational numbers is associative. Also, 0 is an identity element for addition. But does not have an additive inverse in .
Example. ( The integers mod n) If a and b are integers and n is a positive integer (in most cases, ), then a and b are congruent mod n if n divides . In this case, you write .
For example, -6 and 36 are congruent mod 14, since 14 divides .
Equality mod n is an equivalence relation on , and therefore is partitioned into equivalence classes. For example, the equivalence classes of integers mod 4 are
To say that this is a partition of means that every integer is in exactly one of these sets.
Let (read "Z mod n") denote the set of equivalence classes of integers under equality mod n. There are n equivalence classes: The class containing 0, the class containing 1, ..., the class containing . As usual, I'll abuse notation and denote the equivalence classes by 0, 1, ..., .
Thus, . Add elements of by adding and reducing mod n. Thus, in ,
With these definitions, is a group. It is called the cyclic group of order n.
It would be very tedious to check the axioms by hand. I'll take them for granted right now; later, this issue will be dealt with by constructing as a quotient group of .
Example. ( The rationals under multiplication) is not a group under multiplication. Multiplication is a binary operation on the rationals. I will take for granted the fact that multiplication of rational numbers is associative. 1 is an identity for multiplication. But does not have a multiplicative inverse.
On the other hand, , the nonzero rationals, is a group under multiplication. Multiplication is a binary operation on the nonzero rationals: If and are nonzero rationals, then
is a nonzero rational, so is closed under multiplication.
Again, I will take for granted the fact that multiplication of rational numbers is associative.
If is a nonzero rational, then
Thus, 1 is an identity for multiplication.
Finally, if is a nonzero rational, its multiplicative inverse is , another nonzero rational:
Example. ( Guessing an identity and inverses) Define an operation on the real numbers by
Does this give a group structure on ?
takes two real numbers and produces a real number, so is a binary operation on .
Next, I'll check associativity. Let . Then
Thus, , so is associative.
Next, I have to determine whether there is an identity for . First, I'll work backwards to guess what the identity should be. This is not a proof! Once I have my guess, I'll confirm my guess (if possible).
Suppose e is the identity. Then in particular, (I picked 3 at random). This means that , or .
My guess is that the identity is -2. To see if it works, let . Then
This proves that -2 is the identity for .
Finally, I want to show that every element has an inverse. Since -2 is the identity, this means that for every element a, I must find an element such that and .
As I did in the identity step, I'll guess by working backwards, then confirm my guess. Since I want a formula for in terms of a, I'll work with an arbitrary --- in contrast to picking a random element of , as I did to find the identity.
Start with . This means that , so .
(Be sure you understand why I'm not finished yet! Finding does not prove that inverses exist. Think about the reasoning: I started with , which assumes that is defined. I need to confirm that is the inverse of a under , which I do by direct computation.)
I have
Therefore, is the inverse of a.
I've verified all the axioms, so is a group under the operation .
Example. ( A left identity and right inverses) Let denote the nonzero reals. Define a binary operation on by
(The operation is , and I multiply as usual on the right side.)
If a and b are nonzero real numbers, so is . Therefore, the set is closed under the operation.
This is a case where I should prove that the operation is associative. Let . Then
1 is a left identity, in the sense that for all . But (for example)
In other words, 1 is not a two-sided identity, as required by the group definition.
There are also right inverses: for all . But (for instance) there is no such that , since
with is not a group. This example shows why you have to be careful to check the identity and inverse properties on "both sides" (unless you know the operation is commutative).
Note: It is true that if an associative operation has a left identity and every element has a left inverse, then the set is a group.
Example. ( A group which is a subset of the integers) Let
Is G a group under integer addition? (Assume that integer addition is associative.)
First, I'll check whether integer addition actually gives a binary operation on G. To do this, I need to check whether the set is closed under the operation. I'll take two arbitrary elements of G, add them, and see if the sum is an element of G.
Let . Then
Note that:
Now I know that addition gives a binary operation on G.
I'm assuming that addition is associative.
Next, I must show that G has an identity element. 0 is an identity element for addition of integers, so it will work for elements of G:
However, I also have to show that 0 is in G! To do this, write it as :
Therefore, 0 is the identity element of G.
Finally, let . I must show that it has an inverse under addition. The ordinary additive inverse works:
However, as with the identity 0, I have to show that is in G. To do this, just rewrite it so it has the correct form:
This shows that every element of G has an inverse.
Therefore, G is a group.
The groups I've discussed so far are all abelian. For example, , , , and are abelian groups under addition. (As I'll note below, by convention you use the word "addition" to refer to the group operation only if the group is abelian.) Here's an example of a nonabelian group.
Example. ( Symmetry groups) A regular n-gon is a closed, convex polygon in the plane with n equal sides. For example, a regular 3-gon is an equilateral triangle, and a regular 4-gon is a square.
A rigid motion of the plane is a map which preserve distances. , the dihedral group of order , is the group of rigid motions of the plane which carry a given regular n-gon onto itself. (Such a rigid motion is said to preserve the figure. It is also called a symmetry of the figure.)
If you wish, you may think of as the set of rigid motions of the plane which carry the set n complex n-th roots of 1 onto itself. For example, the 4-th roots of 1 are , and is the set of rigid motions of the plane which map the set of 4-th roots to itself.
I will look at , the dihedral group of order 8. First, I will show that the square has 8 symmetries.
A map which carries the square onto itself must map vertices to vertices. Here is a picture of a square with the vertices labelled.
Consider vertex 1. A rigid motion can map it to any of the 4 vertices. Once I know where 1 goes, 3 must go to the vertex opposite it, since distance are preserved. Now there are only two possibilities for vertices 2 and 4. All together, I have choices, so there at most 8 symmetries. I'll show there are exactly 8 by displaying 8 different symmetries.
(Before I do, note that the same argument shows that .)
I will take my square to be as pictured above. The 8 symmetries are as follows:
1. id, the identity symmetry.
2. , counterclockwise rotation through .
3. , counterclockwise rotation through .
4. , counterclockwise rotation through .
5. , reflection across the horizontal line which bisects the square.
6. , reflection across the vertical line which bisects the square.
7. , reflection across the "southwest to northeast" line which bisects the square.
8. , reflection across the "northwest to southeast" line which bisects the square.
For example, here is :
The operation on is function composition --- do one rigid motion after another. It's clear that this is a binary operation, but I need to establish a convention concerning how I will write the operation. I will write
In other words, I'll apply the motions from right to left. This is consistent with the usual notation for composing functions: means g first, then f.
The next picture shows the composite . You can see that .
With a little bit of patience (and perhaps a little cardboard square), you can generate the multiplication table for . Here it is:
This table illustrates a number of ideas.
From the table, it is apparent that is not abelian. For example, , but .
Next, if you examine the table, you will see that each row contains each element of the group exactly once. The same is true for each column. This is true for an arbitrary group G. Here's why.
Consider the row for the element . If x occurs in the b and c columns, this means that . Multiply this equation on the left by :
That is, the b and c columns are actually the same columns. Hence, each row contains a given element at most once.
On the other hand, consider again the row for . Take ; does x occur in this row? Well, , so x occurs in the column for . That is, every element of G occurs in the row for a.
All together, every element of G occurs exactly once in the row for a. A similar argument works for columns. \boxedtext{2}{In the operation table for a group, each element occurs exactly once in each row and each column.}
Note that it doesn't work the other way: There are lots of tables which satisfy this condition but are not tables for groups.
This fact is of some use if you are constructing group multiplication tables by hand. In fact, why not find all groups of a given order by simply writing down multiplication tables?
This is surely a finite process for groups of order (say) 1024, but it isn't very practical. For one thing, the number of possibilities quickly becomes astronomical. (There is no formula known which gives the number of "different" groups of order n in terms of n.) For another thing, there are situations in which two tables represent the "same" group, but this isn't always easy to tell from the group table.
Notation. It's tedious to have to write " " for the operation in a group. It's common to use either multiplicative or additive notation instead. Here is how the various notations compare.
Note that in multiplicative notation, "1" refers to the identity, which may or may not be the number 1. Likewise, in additive notation, "0" refers to the identity, which may or may not be the number 0.
Of course, if there is a standard way to refer to the operation or the identity element in a group, you use it instead of the general notation. For instance, in the group of integers under addition, you use "+" for the operation --- it would be silly and confusing to use " "!
And in the group of matrices with real entries under matrix addition, the identity is
Notice that you should only use additive notation if the operation is commutative (i.e. the group is abelian). You're still permitted to use multiplicative notation in this case. If you don't know whether the operation is commutative, use multiplicative notation.
Example. (a) Write the expression " " in multiplicative notation and in additive notation. (Assume the operation is commutative.)
In multiplicative notation, this is . In additive notation, this is .
(b) Write " " in multiplicative notation. (Assume the operation is commutative.)
In multiplicative notation, this is .
(b) Write " " in additive notation. (Assume the operation is commutative.)
In additive notation, this is .
From now on, I'll use multiplicative notation for an arbitrary group (unless I know it's abelian, in which case I might use additive notation).
I've been referring to the identity of a group and the inverse of an element, but the axioms don't say that there is only one identity, or that an element has only one inverse. The next proposition asserts that the identity and inverses are unique.
Proposition. Let G be a group.
(a) The identity element of G is unique.
(b) The inverse of an element is unique.
Proof. To show a thing is unique, you assume that you have two things of that kind, then show that the two things must in fact be the same.
Suppose 1, are identity elements for G. Then because 1 is an identity, but because is an identity. Therefore, . The identity element of G is unique.
Suppose and that I have elements which behave like the inverse of g. This means that
Now
By associativity, , but . So , and . The inverse of an element is unique.
Proposition. Let G be a group and let .
(a) If , then . If , then .
(b) .
(c) .
Proof. For the first part of (a), I have
You can prove the second part in similar fashion.
For the proof of (b), I'm going to be a little casual about associativity. I have
Lkewise, . So must be the inverse of , i.e. . (The rule may be familiar to you if you know about matrices, since this is the way you take the inverse of a product of matrices.)
For (c), note that
This shows that a is the inverse of --- that is, .
Notation. If a is an element of a group G with identity 1, then . If n is a positive integer,
If n is a negative integer, means . For example, is defined to be , the inverse of .
Proposition. Let G be a group and let .
(a) If , then .
(b) for all .
(c) for all .
I'll omit the proof: It involves induction and is not that enlightening.
Example. ( Computations with group elements) Suppose G is a group and .
(a) Simplify as much as possible.
Note that I was not told that G was abelian, so I have to be careful not to commute elements (in general).
(b) Solve for x in terms of a and b:
I can multiply both sides of the equation by the same thing, but I have to be careful to multiply on the same side of both sides. For example, in the second line below, I multiplied both sides on the left by .
Example. ( Groups of order 2) Suppose G is a group of order 2: . Then , where 1 is the identity and is another element. a must have an inverse; since , the inverse of a is not 1. Therefore, the inverse of a is a, and . The multiplication table for G looks like this:
This group is called , the cyclic group of order 2. Here is another table for the same group:
In this case, I think of as the set , with addition mod 2.
What do I mean when I say that they're "the same group"?
I mean that I can get the second table from the first this way:
This is an example of an isomorphism --- a function which "matches up" elements of one group with another, so the group table is preserved. (I'll make this more precise later.) Isomorphic groups are the same as groups. In this sense, is the only group of order 2.
Example. ( Groups of order 3) Suppose that G is a group and . Let , where 1, a, and b are different elements.
If , then , or , contradicting the fact that a and 1 were distinct elements. If , then (because gives , or , contradicting the fact that b and 1 were distinct elements). But then , so , the same contradiction as before. Hence, . Using the principle that each row or column of a multiplication table contains each element exactly once, I can fill in the rest of the table:
This is , the cyclic group of order 3. Here is another table for the same group:
These two tables give groups which are isomorphic. Up to isomorphism, there is only one group of order 3, namely .
There are two groups of order 4, one group of order 5, two groups of order 6, and one group of order 7. As I mentioned earlier, no one knows a formula for determining how many groups of order n there are. And the method of the preceding examples --- essentially, trial and error --- is untenable once n gets large.
Definition. If G is a group and , the order of g is the smallest positive integer n such that . If for any postive integer n, then g has infinite order.
In this definition, "1" denotes the identity element of G, and I'm using multiplicative notation. Using additive notation, the definition would read: If G is a group and , the order of g is the smallest positive integer n such that . If for any postive integer n, then g has infinite order.
Recall that the order of a group is the number of elements in the group; the preceding definition pertains to the order of an element, which is the smallest positive power of the element which equals the identity. Don't confuse the two uses of the word "order"! When I discuss cyclic groups in more detail, I'll show how the two definitions are related.
Example. ( Orders of elements) This is a group of order 6:
The operation is multiplication and the identity is 1. To find the order of an element, I find the first positive power which equals 1.
The element a has order 6: , and no smaller positive power of a equals 1.
has order 3, because
1 has order 1 --- and in fact, in any group, the identity is the only element of order 1.
Consider the cyclic group of order 10:
Here the operation is addition and the identity is 0. To find the order of an element, I find the first positive multiple which equals 0.
Thus, 6 has order 5, because
Finally, consider the group of real numbers under addition. The element has infinite order: If I take positive multiples of , I'll never get 0:
Example. ( The group of quaternions) This is the group table for Q, the group of quaternions. (Notice that the way i, j, and k multiply is similar to the way the unit vectors , , multiply under the cross product in .)
The identity 1 has order 1, -1 has order 2, and i has order 4:
It's no coincidence that 1, 2, and 4 are divisors of 8, the order of the group. The order of an element always divides the order of the group.
However, it doesn't work the other way: 8 is obviously a divisor of 8, but there's no element of order 8 in Q.
In the special case where and G has an element x of order n, G is said to be cyclic of order n. Since n is the smallest power of x which gives 1, it's easy to show that
must be distinct. Since there are n of these powers, and since there are only n elements in G, this must be all of G:
x is called a generator of the cyclic group, and the cyclic group consists of all powers of x.
The quaternion group Q is not cyclic, because there is no element whose powers give all of Q. and , which I described in earlier examples, are cyclic groups of order 2 and 3, respectively.
Example. ( Isomorphic groups) If the group is abelian, I usually use additive notation. Then the definition of the order of an element reads: The order of g is the smallest positive integer n such that .
For example, consider under addition mod 6:
Here 1 and 5 have order 6, and 2 has order 3:
4 also has order 3:
Since 1 (and 5) have order 6, is cyclic of order 6. In this case, every element is a multiple of 1 (or 5). (I say "multiple" rather than "power", because the group is abelian and I'm using additive notation.)
Remember that it's perfectly correct to write the cyclic group of order 6 this way, using multiplicative notation:
a generates this group, because every element in the group is a power of a. (I say "power" rather than "multiple" this time because the operation is multiplication.)
The powers of are
Since I get the whole group, is a generator, too.
You can get this group table from the first table by the following replacements:
These replacements could be represented by the function for .
This function is another example of an isomorphism.
There is another (really different) group of order 6 --- namely, the group of symmetries of an equilateral triangle. Its table looks like this:
Compare the table for this group with the tables for . See if you can figure out ways in which these groups are not the same as groups.
Copyright 2009 by Bruce Ikenaga