* 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 *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 *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 .

Note that associativity is stated for 3 elements. You can prove (using induction) that if associativity holds for 3 elements, then it holds for n elements for any .

* Example.* If is an associative
binary operation, show that

Use 3-element associativity step-by-step:

Of course, this is just a particular case, but it should make it plausible that you could do this with any two groupings of n elements.

* Example.* (* Binary operations
on familiar number systems*) Are addition, subtraction,
multiplication, and division binary operations on the integers , the rational numbers , the real
numbers , and the complex numbers ?

For those which are binary operations, are they associative? Commutative?

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:

Find , , , and .

Is the operation commutative? Is the operation associative?

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.

Most of the initial examples will be of abelian groups. I'll give an example of a non-abelian group later.

* 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*) Consider the following sets:

- the set of integers

- the set of rational numbers

- the set of real numbers

- the set of complex numbers

Are these groups with addition as the operation?

All of them are infinite groups under addition.

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*) Consider the set of nonzero rational
numbers:

Is a group under addition? Under multiplication?

is not a group under addition.

is certainly closed under addition, and addition of rational numbers is associative. However, it does not contain an identity for addition.

Suppose was the identity. Then, for instance,

But .

(Note that in giving this proof by contradiction, I can't begin by
*assuming* that 0 is the identity: I had to show it would have
to be, by the definition.)

(Question: Suppose you try to fix this problem by considering the nonnegative rational numbers under addition. Now 0 is an identity for addition in . But something else goes wrong and is not a group. Do you see what it is?)

is a group under multiplication. The product of two rational numbers is rational number:

Since, in addition, the product of two positive numbers is positive, is closed under multiplication.

Multiplication of rationals is associative. The identity for multiplication is 1, which is a positive rational number. Finally, if is a positive rational number, then so is its multiplicative inverse .

* 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 the convention is to use multiplicative notation for an
arbitrary group (unless you know it's abelian, in which case you
*may* use additive notation).

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

* Example.* (a) Write the expression " " in multiplicative notation and in
additive notation. (Assume the operation is commutative, and
" " means the inverse of b.)

(b) Write " " in multiplicative notation. (Assume the operation is commutative.)

(c) Write " " in additive notation. (Assume the operation is commutative.)

(a) In multiplicative notation, this is . In additive notation, this is .

(b) In multiplicative notation, this is .

(c) In additive notation, this is .

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.

Associativity applies to 3 elements:

It's easy to show in particular cases that it applies to products with any number of factors.

* Example.* Suppose S is a set with an
associative binary operation . Suppose . Prove
that

* Proposition.* Suppose S is a set with an
associative binary operation. Then for all , any two ways of
grouping a product of n factors give the same result.

I won't give the proof here, but it isn't too difficult: Use induction. Given this result, from now on, I'll be a little casual about associativity of products with any number of factors.

* 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 of (a) 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 .

I'm assuming in giving this definition that any two ways of associating a product with n factors gives the same result.

* 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.

(b) Solve for x in terms of a and b:

(a) Note that I was not told that G was abelian, so I have to be careful not to commute elements (in general).

(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 .

* 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"!

* Example.* (* Orders of
elements*) This is a group of order 6:

Find the orders of the elements of this group.

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.

1 has order 1 --- and in fact, *in any group, the identity is the
only element of order 1*.

The element a has order 6 since , and no smaller positive power of a equals 1.

has order 3, because

has order 2, because

has order 3, because

has order 6. Note that

You can check that no smaller positive power of gives the identity.

* Example.* What is the order of in , 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 .)

(a) Show that Q is not abelian.

(b) Find the orders of 1, -1, and i.

(a) Since but (for instance), Q is not abelian.

(b) 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.

* Definition.* If G is a group with n elements
and G has an element x of order n, G is said to be *
cyclic* of order n.

x is called a * generator* of the cyclic group,
and the cyclic group consists of all powers of x.

Thus, Q is not cyclic, since it has no elements of order 8.

It turns out the is an infinite cyclic group, since you can get every7 element by taking multiples of 1 (or -1). I'll discuss cyclic groups in more detail later.

Copyright 2016 by Bruce Ikenaga