/Solutions

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 ∈ ℚ.

1. Show that ~ is an equivalence relation.

2. Show that ~ is preserved by addition: that is, if x ~ x' and y ~ y', then x+y ~ x'+y'. Corrected 2008-11-17.

3. 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.
2. 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?

1. The path P_n with n edges and n+1 vertices. Corrected 2008-11-19.

2. The cycle C_n with n edges and n vertices, where n≥3. Clarification added 2008-11-19.

3. The complete graph K_n with n vertices.

4. The n-dimensional cube Q_n.