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 every element by taking multiples of 1 (or -1). I'll discuss
cyclic groups in more detail later.
Copyright 2022 by Bruce Ikenaga