2
ELEMENTARY CONCEPTS
CH.
1
is, a followed by jS). The associative law (a/J)y = a(j8y) holds since, for every
x in X,
*((«0)y) = (x(c0)yy = ((*«)j8)y = (aw)(/5y) = *(a(j8y)).
Hence the set ^~x of all transformations of X is a semigroup with respect to
iteration. We call ^x the full transformation semigroup on X.
A mapping a of a set X into a set Y will be said to be a mapping of X onto Y
(or upon Y) if every element of Y is the image under a of at least one element
of X. A mapping a of X into Y is said to be (1, 1) or one-to-one if distinct
elements of X are mapped by a into distinct elements of Y. A one-to-one
mapping of a set X upon itself will be called a permutation of X, even when
X is infinite. The symmetric group @x on X consists of all permutations of
X under the operation of iteration.
If X is a finite set {xi, •, xn}, and if yi, ,yw are elements of X, not
necessarily distinct, then we shall use the classical notation
=
/a?i»2- -xn\
a~
\ym---yn)
to mean that a is the transformation of X defined by
xta = yt (i = 1, 2,- -,?i).
/ / ai, 02, -»*, an °^e elements of a semigroup S, and we set
a±aL -aw = 01(02(03- -(On-iOn)- •))
£Aett every other possible meaningful expression A obtained by inserting paren-
theses in the finite sequence 01, 02, •, an is equal to a±a2- -an.
This is trivial for n = 2. Assume by way of induction that it is true for all
expressions of length less than n. Now A, to be meaningful, must be a
product BC of a meaningful expression B in a±9 02, •, ar and a meaningful
expression C in ar+i, •, an, for some r such that 1 ^ r n. By hypothesis
for induction, B = a\a^- -ar = ai(02- -ar). Hence, by associativity,
A = 5(7 = (ai(a2- -arJJC = 0i((02- -ar)C).
But (a2- -ar)C is a meaningful expression of length n— 1 in 02,- •, an, and
so, by hypothesis for induction again, must equal 0203- -an, yielding the
desired conclusion.
For any positive integer n, the wth power an of an element 0 of a semigroup
S is defined to be 0102 an with = 02 = = an = 0. The first two
'' laws of exponents'',
a
m+n
=
aman, (am)n = 0 m n ,
evidently hold for any 0 in 5 and any positive integers m and n.
A non-empty subset T of a groupoid S is called a subgroupoid of S if aeT
and fee?7 imply abeT. The intersection of any set of subgroupoids of S is
evidently either empty or a subgroupoid of S. If A is any non-empty subset
of S, the intersection of all subgroupoids of S containing A (S itself being one
Previous Page Next Page