A group G,
sometimes denoted by {G,Ÿ}, is
a set of elements with a binary operation denoted by Ÿ that associates to each ordered pair (a, b) of
elements in G an element (aŸb) in G,
such that the following axioms are obeyed:
•Closure with
respect to the operation. Closure means that if a and b are in the set, then
the element aŸb = c
is also in the set.
•Associativity with
respect to the operation. Associativity means that (aŸb)Ÿc = aŸ(bŸc).
•Guaranteed
existence of a unique identity element with regard to the operation. An element i
would be called an identity element if for every a in the set, we have aŸi = a.
•The
existence of an inverse element for
each element with regard to the operation. That is, for every a in the set, the
set must also
contain an element b such that aŸb = i
assuming that i is
the identity element.
Groups - Example
•Let sn = <1, 2, ...., n> denote a
sequence of integers 1 through n.
•Let’s
now consider the set of all permutations of the sequence sn. Denote this set by Pn. Each element of the set Pn stands for a permutation <p1,p2,p3,.....,pn>
of the sequence sn.
–What is
the size of the set Pn?
Answer: n!
•Consider the case
when s3= <1, 2, 3>. In this case, the set of
permutations of the sequence s3 is
given by P3 = {<1,2,3>,
<1,3,2>,
<2,1,3>,
<2,3,1>,
<3,1,2>,
<3,2,1>}.
–The set P3 is of size 6.
•Now
let the binary operation on the elements of Pn be
that of composition of permutations.
•We will
denote a composition of two permutations by the symbol Ÿ.
•For
any two elements ρ and
π of the set Pn, the composition π Ÿ ρ
means that we want to re-permute the elements of ρ according to the elements of π.
•Let’s
go back to the example in which the starting sequence is given
by s3 =<1,2,3>.
•As
already shown, each element of P3 is a distinct permutation of the three
integers in s3.
That is,
P3 = {
<p1, p2, p3>
| p1, p2, p3∈s3 with p1≠p2≠p3}
•Consider
the following two elements π and ρ in the set P3 of permutations:
–π
= < 3, 2, 1 >
–ρ
= < 1, 3, 2 >
•Let’s
now consider the following composition of the two permutations
π and
ρ:
π Ÿ ρ =
<3,2,1> Ÿ <1,3,2>
What that means is to permute ρ according to the elements of π.
What that means is to permute ρ according to the elements of π.
•
•For our
example, that is accomplished by first choosing the third element of ρ,
followed by the second element of ρ, followed finally by the first element
of ρ.
•The result
is the permutation <2, 3, 1>.
•So we
say
–π Ÿ ρ =
<3,2,1> Ÿ <1,3,2> = <2,3,1>
–Therefore, the
composition of the two permutations <3,2,1> and <1,
3, 2> is the permutation <2, 3, 1>.
•Clearly,πŸρ ∈ P3.
•
•This shows
that P3 closed with respect to the operation of com- position of two
permutations.
•
•What
About the Other Three Conditions that P3 Must Satisfy If It is a Group?
•P3 obeys the associativity property with respect
to the composition-of-permutations operator. This we can do by showing
that
for any three elements ρ1, ρ2, and ρ3 of the set P3, the following will always be true
ρ1
Ÿ(ρ2 Ÿρ3) =
(ρ1 Ÿρ2)Ÿρ3
•
•The
set P3 obviously contains a special element
<1, 2, 3> that can serve as the identity element with
respect to the composition- of-permutations operator.
•It is
definitely the case that for any ρ∈P3 we
have
<1,2,3>Ÿρ = ρŸ<1,2,3>
= ρ
•Again, because P3 is a small sized set, we can easily demonstrate that for every ρ ∈ P3 there exists another unique element π ∈ P3 such that
ρŸπ = πŸρ = the
identity element
•For
each ρ, we
may refer to such a π as ρ’s
inverse.
–For the
sake of convenience, we may use the notation −ρ for such a π.
•Obviously,
then, P3 along with the composition-of-permutations
operator is a group.
•Note
that the set Pn of all permutations of the starting
sequence sn can only be finite. As a result, Pn along with the operation of composition
as denoted by ’•’
forms
a finite group.
•The set Pn of permutations along with the
composition-of-permutations operator is referred to as a permutation
group.
No comments:
Post a Comment