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

- 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
- 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. - for all a in X, (a, a) is in R (R is