# 1. ℝ/ℚ

Recall that ℝ is the set of real numbers and ℚ is the set of rational numbers, those elements of ℝ that can be expressed as p/q where p is an integer and q is a nonzero natural number.

Define the relation ~ on ℝ by the rule x~y if and only if x-y ∈ ℚ.

- Show that ~ is an equivalence relation.
Show that ~ is preserved by addition: that is, if x ~ x' and y ~ y', then x+y ~ x'+y'.

*Corrected 2008-11-17.*- Describe the equivalence class of 0 under ~.

# 2. Lattices

Let (L,≤) be a lattice, that is, a partially ordered set such that every pair of elements x and y have a greatest lower bound x∧y and a least upper bound x∨y.^{1}

- Prove or disprove: Any minimal element of L is a minimum element.
- Prove or disprove: For all x, y, and z, (x∨y)∨z = x∨(y∨z).

# 3. Bipartite graphs

For which values of n are each of the following graphs bipartite?

The path P

_{n}with n edges and n+1 vertices.*Corrected 2008-11-19.*The cycle C

_{n}with n edges and n vertices, where n≥3.*Clarification added 2008-11-19.*The complete graph K

_{n}with n vertices.The n-dimensional cube Q

_{n}.