Binary Operations
“ * ” is called a binary operation on S
Definition: A binary operation on a set S is a
function * : S S → S
Example:
The function f: → defined by
f(x,y) = xy + y
is a binary operation on
Associativity
A binary operation * on a set S is
associative if:
for all a,b,cS, (a*b)*c = a*(b*c)
Examples:
Is f: → defined by f(x,y) = xy + y
associative?
(ab + b)c + c = a(bc + c) + (bc + c)? NO!
Commutativity
A binary operation * on a set S is
commutative if
For all a,bS, a*b=b*a
Identities
R0 is like a null motion
Is this true: a YSQ, a R0 = R0 a = a? YES!
R0 is called the identity of on YSQ
In general, for any binary operation on a set
S, an element e S such that for all a S,
ea=ae=a
is called an identity of on S
Inverses
Definition: The inverse of an element a YSQ
is an element b such that:
a b = b a = R0
Examples:
R90 inverse: R270
R180 inverse: R180
F| inverse: F|
Every element in YSQ
has a unique inverse
R0 R90 R180 R270 F| F— F F
R0 R0 R90 R180 R270 F| F— F F
R90 R90 R180 R270 R0 F F F| F—
R180 R180 R270 R0 R90 F— F| F F
R270 R270 R0 R90 R180 F F F— F|
F| F| F F— F R0 R180 R90 R270
F— F— F F| F R180 R0 R270 R90
F F F— F F| R270 R90 R0 R180
F F F| F F— R90 R270 R180 R0
Groups
A group G is a pair (S,), where S is a set
and is a binary operation on S such that:
1. is associative
2. (Identity) There exists an element
e S such that:
e a = a e = a, for all a S
3. (Inverses) For every a S there is
b S such that: a b = b a = e
If is commutative, then G is called a
commutative group
Examples
Is (,+) a group?
Is + associative on ? YES!
Is there an identity? YES: 0
Does every element have an inverse? NO!
(,+) is NOT a group
Examples
Is (Z,+) a group?
Is + associative on Z? YES!
Is there an identity? YES: 0
Does every element have an inverse? YES!
(Z,+) is a group
Examples
Is (YSQ, ) a group?
Is associative on YSQ? YES!
Is there an identity? YES: R0
Does every element have an inverse? YES!
(YSQ, ) is a group
Examples
Is (Zn,+) a group?
(Zn is the set of integers modulo n)
Is + associative on Zn? YES!
Is there an identity? YES: 0
Does every element have an inverse? YES!
(Zn, +) is a group
Identity Is Unique
Theorem: A group has at most one identity
element
Proof:
Suppose e and f are both identities
of G=(S,)
Then f = e f = e
Inverses Are Unique
Theorem: Every element in a group has a
unique inverse
Proof:
Suppose b and c are both inverses of a
Then b = b e = b (a c) = (b a) c = c
A group G=(S,) is finite if S is a finite set
Define |G| = |S| to be the order of the group
(i.e. the number of elements in the group)
What is the group with the least number of
elements? G = ({e},) where e e = e
How many groups of order 2 are there?
e f
e e f
f f e
Generators
A set T S is said to generate the group
G = (S,) if every element of S can be
expressed as a finite product of elements in T
Question: Does {R90} generate YSQ? NO!
Question: Does {S|, R90} generate YSQ? YES!
An element g S is called a generator of
G=(S,) if {g} generates G
Does YSQ have a generator? NO!
Generators For Zn
Any a Zn such that GCD(a,n) = 1 generates Zn
Claim: If GCD(a,n) =1, then the numbers
a, 2a, …, (n-1)a, na are all distinct modulo n
Proof (by contradiction):
Suppose xa = ya (mod n) for x,y {1,…,n}
and x ≠ y
Then n | a(x-y)
Since GCD(a,n) = 1, then n | (x-y), which
cannot happen
If G = (S,), we use an denote (a a … a)
n times
Definition: The order of an element a of G is
the smallest positive integer n such that an = e
The order of an element can be infinite!
Example: The order of 1 in the group (Z,+)
is infinite
What is the order of F| in YSQ? 2
What is the order of R90 in YSQ? 4
Orders
Theorem: Let x be an element of G. The
order of x divides the order of G
Corollary: If p is prime, ap-1 = 1 (mod p)
(This is called Fermat’s Little Theorem)
{1,…,p-1} is a group under multiplication
modulo p
Lord Of The Rings
We can define more than one operation on a set
For example, in Zn we can do addition and
multiplication modulo n
A ring is a set together with two operations
Definition:
A ring R is a set together with two binary
operations + and x, satisfying the following
properties:
1. (R,+) is a commutative group
2. x is associative
3. The distributive laws hold in R:
(a + b) x c = (a x c) + (b x c)
a x (b + c) = (a x b) + (a x c)
Fields
Definition:
A field F is a set together with two binary
operations + and x, satisfying the following
properties:
1. (F,+) is a commutative group
2. (F-{0},x) is a commutative group
3. The distributive law holds in F:
(a + b) x c = (a x c) + (b x c)
