Due Wednesday, 9/27:
- 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.)
- 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
, and R is the relation defined by
, 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.
- 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.
- 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.
