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.

1. Let L be any lattice and consider the monoid . Let be some fixed element of L.

A relation R on L is defined by

1. Give the definition of a congruence relation.
2. 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.
3. Consider the particular case where ordered by | (the divisibility relation) and . Recall that is the set of positive integer divisors of 12.
1. Write out the partition of L into congruence classes.
2. Give the multiplication table of the quotient monoid L/R.
3. Find a homomorphism from onto .
2. Let . Find:
1. The number of everywhere defined functions from A to B.
2. The number of everywhere defined one-to-one functions from A to B.
3. The number of relations from A to B.
4. The number of symmetric relations from B to itself.
1. There are five pairwise non-isomorphic posets on the set . Draw five Hasse diagrams of posets on so that no two of them are isomorphic.
2. Indicate which of the posets in part (a) are lattices.

3. Define an operation * on the non-negative real numbers, , by

1. Show that * is associative.
2. Find an identity element of .
3. Decide if is a semigroup, monoid 6 and/or a group. Give reasons.
1. State precisely the definition of2 a transitive relation.
2. 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.

1. Find 4 . Show or explain your work.
2. Find . 4 Give reasons.

4. Let be functions from the set to itself which are indicated below:

1. 6 -2pc

2. Find an 4 isomorphism from M to
where and + is addition mod 4.
3. Give the definition 6 of a submonoid and then find all the submonoids of .
5. One of the following two sentences is true.

or

Decide which sentence is true and prove it by induction.
Hint: think about the so-called ``inductive step''.