# Homework 2

Due Monday, March 5:

1. Let A be any set.
• Show that $\overline{\overline{A}} = A$.
• Show that $A \cap \overline{A} = \emptyset$.
2. Suppose A and B are subsets of a universal set U. Show that if $A \subseteq B$, then $\overline{B} \subseteq \overline{A}$.
3. Find $2^0, 2^0 + 2^1, 2^0 + 2^1 + 2^2$, and $2^0 + 2^1 + 2^2 + 2^3$. Spot a pattern and a formula for $2^0 + 2^1 + \ldots + 2^n$. Prove by induction that this formula works for any n.
4. Prove by induction that the sum of the numbers from 0 to n is equal to $\frac{n(n+1)}{2}$.
5. 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 $(a, b) \in R$, and then find elements a and b in X such that $(a, b) \not \in R$.

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