Next: About this document
YORK UNIVERSITY
Faculty of Arts
Final Examination,
December 21, 1989
Mathematics 2320.03F
Discrete Mathematics
INSTRUCTIONS:  Answer all questions in the booklets
provided.
 Calculators and other aids are not permitted.
 You 3pc
are encouraged to give relevent definitions in your answers and
to show your work. Credit will not necessarily be given for a correct
answer if it is not accompanied by an explanation of the reasoning
involved.
 Let L be any lattice and consider the
monoid .
Let be some fixed element of L.
A relation R on L is defined by
 Give the definition of a
congruence relation.
 You may take it
as given that R is an equivalence relation.
Show that R is a congruence relation. Indicate clearly which of the
properties of the operation you are using.
 Consider the particular case where ordered by 
(the divisibility relation) and . Recall that is
the set of positive integer divisors of 12.
 Write out the partition of L into congruence classes.
 Give the multiplication table of the quotient monoid L/R.
 Find a homomorphism from onto .
 Let
. Find:
 The number of everywhere defined functions from A to B.
 The number of everywhere defined onetoone functions from A to
B.
 The number of relations from A to B.
 The number of symmetric relations from B to itself.

 There are five
pairwise nonisomorphic posets
on the set .
Draw five Hasse diagrams of posets on so that no
two of them are isomorphic.
 Indicate which of the posets in part (a) are lattices.
 Define an operation * on the nonnegative
real numbers, , by
 Show that * is associative.
 Find an identity element of .
 Decide if is a semigroup, monoid
6 and/or a group. Give
reasons.
 State precisely the definition of2
a transitive relation.
 Let R be a
transitive relation on a set A. Recall that
for any ,
R(a) denotes the set . Suppose that a,b are in A and that aRb holds.

 Find 4 . Show or explain your work.
 Find . 4 Give reasons.
 Let be functions from the set
to itself which are indicated
below:
 6
2pc
 Find an 4 isomorphism from M to
where
and + is addition mod 4.  Give the definition 6 of a submonoid
and then find all the submonoids of .
 One of the following two sentences is true.
or
Decide which sentence is true and prove it by induction.
Hint: think about the socalled ``inductive step''.
Next: About this document
Eli Brettler
Tue Sep 17 10:40:15 EDT 1996