**Due Monday, March 5**:

- Let A be any set.
- Show that .
- Show that .

- Suppose A and B are subsets of a universal set U. Show that if , then .
- Find , and . Spot a pattern and a formula for . Prove by induction that this formula works for any n.
- Prove by induction that the sum of the numbers from 0 to n is equal to .
- 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**) - 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 (R is
**transitive**)

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 , and then find elements a and b in X such that .

- for all a in X, (a, a) is in R (R is
- 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 (R is
**anti-****symmetric**) - R is
**transitive**(see above) - For all a and b in X, either (a, b) is in R or (b, a) is in R (R is
**total**).

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 the set of positive integers and R is now the relation { (x, y) : x is a factor of y }, then R is not total.

- for all a and b in X, if both (a, b) is in R and (b, a) is in R then a = b (R is