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 Pn with n edges and n+1 vertices. Corrected 2008-11-19.
The cycle Cn with n edges and n vertices, where n≥3. Clarification added 2008-11-19.
The complete graph Kn with n vertices.
The n-dimensional cube Qn.