Homework #1

1.  Prove the following:
    A - (B ^ C) = (A - B) v (A - C)

    Solution:  let
       L = A - (B ^ C) and
       R = (A - B) v (A - C)

       To show that L = R we will show that 1) L is a subset of R and
       2) R is a subset of L.

       1) Let x be any element of L; then x is in A, but
       x is not in both B and C (which also means that either x is not
       in B or x is not in C).  If x is in A but not in B, then x is an
       element of (A - B).  If x is in A but not in C, then x is an element
       of (A - C).  Because x is in A but either not in B or not in C,
       then x is an element of either (A - B) or (A - C), and is thus an
       element of R.  Therefore L is a subset of R.

       2) Let x be any element of R; then x is either an element of A but not
       an element of B, or x is an element of A but not an element of C.
       In either case we know that x is an element of A.  We also know that
       x is either not an element of B or not an element of C, which means that
       x cannot be an element of both B and C (x is not an element of B^C).
       As a result, x is an element of L.  Therefore R is a subset of L.

       Q.E.D.

2.  Give functions f: N->N that satisfy
    a) f is one-to-one but not onto
    b) f is onto but not one-to-one
    c) f is a bijection

    Solution:

    a)  f(x) = x * 2
      Every distinct element of x has a different value of (x*2), thus
      the function is one-to-one.  On the other hand, some values in the
      range of the function (namely the odd numbers) are not under the image
      under f of any element in N.  Thus the function is not onto.

    b)  f(x) = floor(x / 2)
      Every distinct element y of x is an image under f of some element in N
      (in particular, the element y*2 and y*2 + 1), thus the function is onto.
      However, two distinct elements of x can map to the same value under the
      function f.  In particular, x=2 and x=3 both map to the natural number
      1.  Thus the function is not one-to-one.

    c)  f(x) = x
      This is a simple example.  Because every distinct element x will be
      mapped onto a distinct natural number, the function is onto.  Every
      element of N is an image under f of some element in N (namely itself),
      so the function is onto.  Because the function is one-to-one and onto,
      by definition the function is a bijection.

3.  Prove that the union of two countable sets is countable.

    Solution:    To show a bijection f:N->(AvB), where A and B are
    countable sets, we can use the dovetailing technique described in the
    textbook.  In particular, we will visit the first element of set A followed
    by the first element of set B, then the second element of set A then set B,
    and so on.  The union can be listed as AvB = {a0, b0, a1, b2, ...}.
    For each element we have to consider the case that the same element may
    exist in the other set (the union does not include duplicates).  Thus
    for each element, before we visit the element we first check each element
    already visited (because a finite number of elements have been visited,
    this requires finite time).  If no equivalent element has been visited,
    we visit the element.  If a duplicate is found, we do not visit (add to
    the list) the element.

    Similarly, it is sufficient to show that AvB is a subset of a countably
    infinite set.  We know that AvB is a subset of the set created by
    concatenating the two sets A and B.  The only difference between the
    concatenation of A and B and their union is that duplicate elements are
    not included in the union.  We can use the "dovetailing" described on
    page 22 of the textbook to show that the concatenation of the sets is
    countably infinite.  Because AvB is a subset of this concatenation,
    AvB is countably infinite.

4.  Let R1 and R2 be any two partial orders on the same set A.  Show that
    R1 ^ R2 is a partial order.

    Solution:  To show that R=R1^R2 is a partial order we need to show that
    R is reflexive, transitive, and has no nontrivial cycles.
    Note that (x,y) is in R if it is in R1 and in R2.

    Reflexive ((x,x) in R).
    For any element x, (x,x) is in R1 and (x,x) is in R2
    (since R1 and R2 are partial orders they are reflexive), thus
    (x,x) is in R.

    Transitive (if (x,y) and (y,z) are in R, then (x,z) is in R).
    If (x,y) and (y,z) are in R then they are both in R1 and R2.
    Because R1 and R2 are partial orders they are transitive, so (x,z) is
    in both R1 and R2.  Thus (x,z) is in R.

    No nontrivial cycles (prove by contradiction).
    Let (a1, ..., an) be a nontrivial cycle in R, n > 1.
    We know that each for sequence pair (ai, ai+1) to be in R, it is in both
    R1 and R2.  If each such pair exists in both R1 and R2, then the entire
    chain exists in both R1 and R2.  This is a contradiction, because R1 and R2
    are partial orders and cannot contain nontrivial cycles.  Thus R does not
    contain nontrivial cycles.

5.  Let R be b binary relation on the set A = the set of all English words;
    (a,b) in R if and only if a is longer than b.
    Is R a partial order?  Is R a total order?  Justify your answer.
    What are the minimal element(s)?

    Solution:  R is not a partial order because R is not reflexive (a word
    cannot be longer than itself).  I will also construct a solution for
    relation R that is {(a,b}:  word a is longer than or equal in length to b}.
    In this case, R is a partial order but not a total order (words of equal
    length are not elements of R).  The minimal elements are words consisting of
    one character such as "a" and "I".

6.  Consider the set of elements S = {1,2,3} and a relation R defined on
    these elements

    R = {(1,2), (2,1), (2,2), (2,3), (3,2)}.

    Show R2 (R2 is R.R, or R composed with itself)
    and the transition closure of R (R*).

    Solution:  R2 = R.R = {(1,2), (2,1), (2,2), (2,3), (3,2)} v
                        {(1,1), (1,3), (3,1), (3,3)}
    We cannot add any new relations in the transitive closure, so R* = R2.

7.  Are the following sets closed under the following operations?  If not,
    name a set of which the property is a closure property.

    a) The even integers under division
    b) The positive integers under multiplication.

    Solution:
    a) No.  18 divided by 6 is not an even integer.
       Real numbers are closed under division.
    b) Yes.