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.
3. 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.

4. 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.
5. 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.

      

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

   

7. 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 .
8. 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''.

• About this document ...