Homework 2

Due Wednesday, 9/27:

  1. Suppose A and B are finite sets and |A| = m, |B| = n. Find |A x B| and prove (by induction on n) that this is formula is correct. (Hint: fix |A| = m. Then figure out |A x B| for |B| = 0, 1, 2, 3, and see if you spot a pattern.)
  2. A relation R on a set X is called a linear order (or a total order) if it obeys the following properties:
    • for all a and b in X, if both (a, b) is in R and (b, a) is in R then a = b (this is called anti-symmetry)
    • for all a, b, and c in X, if (a, b) is in R and (b, c) is in R, then (a, c) is in R (this is called transitivity)
    • For all a and b in X, either (a, b) is in R or (b, a) is in R (this is called totality).

    Show that if X is the set of integers \mathbb{Z}, and R is the relation defined by \{ (x, y) : x - y \leq 0 \}, then R is a total order. Next, show that if X is again the set of integers and R is now the relation { (x, y) : x is a factor of y }, then R is not a total order.

  3. Let A = {0, 1, 2, .., n – 1}, so |A| = n. Determine the number of bijections from A to A (that is, find the number of functions with domain A and codomain A that are both one to one and onto), and prove (by induction on n) that this is correct.
  4. A relation R on a set X is called an equivalence relation if:
    • for all a in X, (a, a) is in R (R is reflexive)
    • for all a and b in X, if (a, b) is in R, then (b, a) is in R (R is symmetric)
    • R is transitive (see above)

    Show that if X = {0, 1, 2, 3} and R is the relation { (x, y) : x – y is an even integer}, then R is an equivalence relation. In addition, find elements a and b in X such that (a, b) is in R, and then find elements a and b in X such that (a, b) is not in R.