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