136.330 Test 1.
(October 2, 2002)
Justify all your answers unless otherwise stated.
1. Suppose 
, 
are two sets and
suppose that 
, 
and 
are mapping
defined as follows:
(a) Which of the mappings 
are one-to-one,
which are onto? (Just give answers; no need of any justification).
(b) Find 
(this means,
find what 
does to every
element in its domain).
Solution.
(a) 
are bijections
(so one-to-one and onto); 
is onto but not
one-to-one.
(b) Notice that 
is the following
map (see 
above, and
follow the mapping arrow in the opposite direction): 
. So it happens that 
. Now we compute: 
, 
, 
and 
.
2. In a set of 12
people (denoted by 
) any two are of different heights, with Michael being the
tallest of all. Define an operation (denoted by 
) by: if 
and 
are different
people then 
= that taller of
and 
; otherwise 
).
(a)
Is 
commutative ?
(justify in no more than 2 sentences)
(b)
Is 
associative ?
(justify in no more than 2 sentences)
(c) Is there the identity element ? If yes, describe it.
(d) Which elements (people) are invertible?
Solution. (a) The
operation 
is obviously
commutative.
(b) The operation 
is associative:
the result of multiplying any three elements (people) in any order whatsoever
is the tallest person.
(c) The shortest person is the identity.
(d) The shortest person is the only invertible element.
3. Suppose 
and suppose that
we know that 
is group (that
is, the set 
, together with the operation 
is a group).
Suppose in addition that the following is a partially completed Cayley table of
.
Complete the Cayley table of 
. No need to justify your answer here.
Solution. 
4. Suppose 
is an Abelian
group with identity 
, and suppose 
is the subset of
consisting of
those elements 
for which 
. Define 
over 
as follows: for
any 
, 
.
(a) Show that 
is an operation
over 
.
(b) Show that 
with 
is an Abelian
group.
Solution.
(a) We need to show that given 
, 
is also in 
. Since 
, and because of the definition of 
, we need to show that 
. We have 
, where in the first step we have used the commutativity and
associativity of 
.
(b) 
(associativity);
(so 
is in 
);
and 
(so 
is the identity);
for 
, 
so each element
is the inverse of itself; finally 
(commutativity).
5. (a) Write 
(
) in cycle notation (without the symbol for inverse).
(b) For which values of 
, 
, will every 
-cycle 
be its own
inverse?
Solution. (a) Using
the usual notation for permutations, the cycle 
is the
permutation 
(with the other
elements fixed). From there we see that 
. Now we find that 
(or, which is the
same, 
).
(b) With the above notation, we see that 
, while 
. So, these two are not equal if 
. On the other hand, it is obvious that for 
we have 
. So, only for 
, every 
-cycle 
is its own
inverse.