Homework 2

Due Monday, March 5:

Let A be any set.
- Show that $\overline{\overline{A}} = A$ .
- Show that $A \cap \overline{A} = \emptyset$ .
Suppose A and B are subsets of a universal set U. Show that if $A \subseteq B$ , then $\overline{B} \subseteq \overline{A}$ .
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.
Prove by induction that the sum of the numbers from 0 to n is equal to $\frac{n(n+1)}{2}$ .
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$ .
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.