next up previous
Next: About this document

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 tex2html_wrap_inline189 . Let tex2html_wrap_inline191 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 tex2html_wrap_inline205 operation you are using.
    3. Consider the particular case where tex2html_wrap_inline207 ordered by | (the divisibility relation) and tex2html_wrap_inline211 . Recall that tex2html_wrap_inline213 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 tex2html_wrap_inline213 onto tex2html_wrap_inline223 .
  2. Let tex2html_wrap_inline227 . 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 tex2html_wrap_inline243 . Draw five Hasse diagrams of posets on tex2html_wrap_inline243 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, tex2html_wrap_inline249 , by


    1. Show that * is associative.
    2. Find an identity element of tex2html_wrap_inline253 .
    3. Decide if tex2html_wrap_inline253 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 tex2html_wrap_inline261 ,
      R(a) denotes the set tex2html_wrap_inline265 . Suppose that a,b are in A and that aRb holds.


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


  5. Let tex2html_wrap_inline279 be functions from the set tex2html_wrap_inline281 to itself which are indicated below:





    1. 6 tex2html_wrap303 -2pc


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




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

next up previous
Next: About this document

Eli Brettler
Tue Sep 17 10:40:15 EDT 1996