A solutions manual for Topology by James Munkres
3. Relations
Equivalence Relations
1. Define two points \((x_0, y_0)\) and \((x_1, y_1)\) of the plane to be equivalent if \(y_0 - x_0^2 = y_1 - x_1^2\). Check that this is an equivalence relation and describe the equivalence classes.
Proof. \(\quad\) It is easily seen that the relation is reflexive, symmetric, and transitive. Each equivalence class is a parabola given by \(x\mapsto x^2+ c\).\(\quad\square\)
2. Let \(C\) be a relation on a set \(A\). If \(A_0\subset A\), define the restriction of \(C\) to \(A_0\) to be the relation \(C\cap (A_0\times A_0)\). Show that the restriction of an equivalence relation is an equivalence relation.
Proof. \(\quad\)It is clear that: \[ \forall x\in A_0\forall y\in A_0((x,y)\in C \Leftrightarrow (x,y)\in C\cap (A_0\times A_0)). \] Thus all the properties for an equivalence relation hold in \(C\cap (A_0\times A_0)\).\(\quad\square\)
3. Here is a “proof” that every relation \(C\) that is both symmetric and transitive is also reflexive: “Since \(C\) is symmetric, \(aCb\) implies \(bCa\). Since \(C\) is transitive, \(aCb\) and \(bCa\) together imply \(aCa\), as desired.” Find the flaw in this argument.
Proof. \(\quad\) Let \(C\subset A\times A\) be a relation. If \(C\) is symmetric and transitive, then: \[ \forall a\forall b(aCb\Rightarrow aCa). \] If \(C\) is reflexive, then: \[ \forall a\in A(aCa). \] \(\quad\square\)
4. Let \(f : A\to B\) be a surjective function. Let us define a relation on \(A\) by setting \(a_0\sim a_1\) if \(f(a_0)= f(a_1)\).
\(\quad\)(a) Show that this is an equivalence relation.
\(\quad\)(b) Let \(A^\ast\) be the set of equivalence classes. Show there is a bijective correspondence of \(A^\ast\) with \(B\).
Proof. \(\quad\)(a) \(f(a)=f(a)\). \(f(a)=f(b)\) and \(f(b)=f(c)\) \(\Rightarrow f(a)=f(c)\). \(f(a)=f(b)\) \(\Rightarrow f(b)=f(a)\).
\(\quad\)(b) Let \(g:A^\ast\to B\) be a function given by \({x}\mapsto f(a)\) where \(a\in{x}\), and let \({x}, {y}\in A^\ast\) and \(a,b\in{x}\). Since \(a\sim b\), \(f({x})=f({y})\), thus \(g\) is well-defined. If \(x\neq y\) and \(c\in x\) and \(d\in y\), then \(f(c)\neq f(d)\), thus \(g(x)\neq g(y)\), so \(g\) is injective. Since \(f\) is surjective, for every \(d\in B\) there is \(c\in A\) such that \(f(c)=d\), and since \(\sim\) is an equivalence relation, there is \(z\in A^\ast\) such that \(c\in z\); \(g(z)= f(c)=d\), so \(g\) is surjective. Thefefore, \(g\) is bijective.\(\quad\) \(\quad\square\)
5. Let \(S\) and \(S'\) be the following subsets of the plane: \[
\begin{array}{rl}
S &=\{(x, y)\mid y = x + 1\text{ and }0 < x < 2\},\\
S' &=\{(x, y)\mid y - x\text{ is an integer}\}.
\end{array}
\] \(\quad\)(a) Show that \(S'\) is an equivalence relation on the real line and \(S'\supset S\). Describe the equivalence classes of \(S'\).
\(\quad\)(b) Show that given any collection of equivalence relations on a set \(A\), their intersection is an equivalence relation on \(A\).
\(\quad\)(c) Describe the equivalence relation \(T\) on the real line that is the intersection of all equivalence relations on the real line that contain \(S\). Describe the equivalence classes of \(T\).
Proof. \(\quad\)(a) \(x-x=0\). \(a-b=n\in\mathbb{z}\Rightarrow b-a=-n\). \(a-b=n,b-c=m\) for \(n,m\in\mathbb{z}\Rightarrow\) \(a-c=n+m\).
\(\quad\)(b) Let \(R=\{R_i\mid i\in I\}\) be the collection of equivalence relations on \(A\) indexed by a nonempty set \(I\). For all \(a\in A\), since \(a\in R_i\) for each \(i\in I\), \((a,a)\in \bigcap_{i\in I}R\). If \((a,b)\in\bigcap_{i\in I}R\), then \((a,b)\in R_i\) for each \(i\in I\), thus \((a,a), (b,b), (b,a)\in R_i\) for each \(i\in I\), so \((a,a), (b,b), (b,a)\in\bigcap_{i\in I}R\). Similarly, if \((a, b), (b,c)\in \bigcap_{i\in I}R\), then \((a,c)\in\bigcap_{i\in I}R\).
\(\quad\)(c) A equivalence relation on the real line that contain \(S\) need more equations. \(y=x\) for the reflexivity, \(x=y+1\) for the symmetry. Thus \(0<x<3\) and \(0<y<3\). \(x=y+1+1\) for the transitivity, thus in general, \(y-x\) is an integer, \(0<x<3\) and \(0<y<3\). \(T\) is the restriction of \(S'\) to \((0,3)\). This definition is minimal with respect to the previous equations. \(T\) can be seen as the intersection of two equivalence relations, \(S'\cap \{(x,y)\mid\text{either }0<x<3\) and \(0<y<3\), or \((x\le 0\) or \(x\ge 3)\) and \((y\le 0\) or \(y\ge 3)\}\). \(\quad\square\)
Order Relations
6. Define a relation on the plane by setting \[ (x_0, y_0) < (x_1, y_1) \] if either \(y_0 - x_0^2 < y_1 - x_1^2\), or \(y_0 - x_0^2 = y_1 - x_1^2\) and \(x_0 < x_1\). Show that this is an order relation on the plane, and describe it geometrically.
Proof. \(\quad\)It is easily seen that comparability, nonreflexivity and transitivity hold for the given relation. Geometrically, if \((x_0,y_0)<(x_1,y_1)\), then \((x_0,y_0)\) lies in \(y=x^2+c\) for some \(c\in\mathbb{R}\) and \((x_1,y_1)\) lies in \(y=x^2+d\) for some \(d\in\mathbb{R}\) and either \(c<d\), or \(c=d\) and \(x_0<x_1\).\(\quad\square\)
7. Show that the restriction of an order relation is an order relation.
Proof. \(\quad\)Let \(A\) and \(A_0\) be sets such that \(A_0\subset A\) and let \(C\) be an order relation on \(A\). It is clear that: \[ \forall x\in A_0\forall y\in A_0((x,y)\in C \Leftrightarrow (x,y)\in C\cap (A_0\times A_0)). \] Thus all the properties for an order relation hold in \(C\cap (A_0\times A_0)\).\(\quad\square\)
8. Check that the relation defined in Example 7 is an order relation.
Proof. \(\quad\)From Example 7, “Define \(xCy\) if \(x^2 < y^2\), or if \(x^2 = y^2\) and \(x < y\).”
\(\quad\)Clear.\(\quad\square\)
9. Check that the dictionary order is an order relation.
Proof. \(\quad\)Clear.\(\quad\square\)
10. \(\quad\)(a) Show that the map \(f : (-1, 1)\to\mathbb{R}\) of Example 9 is order preserving.
\(\quad\)(b) Show that the equation \(g(y) = 2y/[1 + (1 + 4y^2)^{1/2}]\) defines a function \(g:\mathbb{R}\to (-1,1)\) that is both a left and a right inverse for \(f\).
Proof. \(\quad\)(a) From Example 9, \(f\) is given by \(x\mapsto x/(1-x^2)\). Suppose that \(y>x\). \(f(y)-f(x)=\) \(y/(1-y^2)-x/(1-x^2)\) \(=(y-yx^2 - x+xy^2)/((1-y^2)(1-x^2))\) \(=(y-x+yx(y-x))/((1-y^2)(1-x^2))\). Since \(y-x>0\) and \(|y-x|>|xy(y-x)|\), \(f(x)<f(y)\). Thus \(f\) is order preserving; thus injective, and also neither upper-bounded nor lower-bounded; thus surjective. Therefore, \((-1, 1)\) and \(\mathbb{R}\) have the same order type.
\(\quad\)(b) Brute-force is enough. ;-)\(\quad\square\)
11. Show that an element in an ordered set has at most one immediate successor and at most one immediate predecessor. Show that a subset of an ordered set has at most one smallest element and at most one largest element.
Proof. \(\quad\)Let \(S\) be an ordered set, and let \(a,b,c\in S\). If \(a\) has immediate successors, \(b\) and \(c\), then by comparability, \(b=c\); otherwise \(b<c\) or \(b>c\), a contradiction. Similarly to immediate predecessor, smallest element, and largest element.\(\quad\square\)
12. Let \(\mathbb{Z}_+\) denote the set of positive integers. Consider the following order relations on \(\mathbb{Z}_+\times\mathbb{Z}_+\):
\(\quad\)(i) The dictionary order.
\(\quad\)(ii) \((x_0, y_0) < (x_1, y_1)\) if either \(x_0 - y_0 < x_1 - y_1\), or \(x_0 - y_0 = x_1 - y_1\) and \(y_0 < y_1\).
\(\quad\)(iii) \((x_0, y_0) < (x_1, y_1)\) if either \(x_0+y_0<x_1+y_1\), or \(x_0 + y_0 = x_1 + y_1\) and \(y_0 < y_1\).
\(\quad\)In these order relations, which elements have immediate predecessors? Does the set have a smallest element? Show that all three order types are different.
Proof. \(\quad\)(i) \((x,1)\) for every \(x\in\mathbb{Z}_+\) has no immediate predecessor. \((1,1)\) is the smallest.
\(\quad\)(ii) \((x,1)\) and \((1,y)\) for every \(x,y\in\mathbb{Z}_+\) have no immediate predecessor. No smallest element.
\(\quad\)(iii) \((1,1)\) has no immediate predecessor. \((1,1)\) is the smallest.
\(\quad\) Suppose \(f(b)=c\), where \(f\) is bijective order preserving function, and \(b\) has immediate predecessor \(a\), and \(c\) has no immediate predecessor, then there is no \(f(a)\). They all have different order types.\(\quad\square\)
13. Prove the following:
Theorem. If an ordered set A has the least upper bound property, then it has the greatest lower bound property.
Proof. \(\quad\)Let \(S\subset A\) be bounded below, and let \(T=\{x\in A\mid x\) is a lower bound of \(S\}\) be nonempty. \(T\) has a least upper bound \(t\), and clearly \(t\) is a greatest lower bound of \(S\).\(\quad\square\)
14. If \(C\) is a relation on a set \(A\), define a new relation \(D\) on \(A\) by letting \((b,a)\in D\) if \((a,b)\in C\).
\(\quad\)(a) Show that \(C\) is symmetric if and only if \(C=D\).
\(\quad\)(b) Show that if \(C\) is an order relation, \(D\) is also an order relation.
\(\quad\)(c) Prove the converse of the theorem in Exercise 13.
Proof. \(\quad\)(a) Clear.
\(\quad\)(b) “If \(yDx\) and \(zDy\), then \(zDx\).” implies “If \(zDyDx\), then \(zDx\)”. \(D\) is transitive; the other properties are obvious.
\(\quad\)(c) Let \(S\subset A\) be bounded above and let \(T=\{x\in A\mid x\) is a upper bound of \(S\}\) be nonempty. \(T\) has a greatest lower bound \(t\), and clearly \(t\) is a least upper bound of \(S\).\(\quad\square\)
15. Assume that the real line has the least upper bound property.
\(\quad\)(a) Show that the sets \[
\begin{array}{ll}
\left[0,1\right] &=\{x\mid 0\le x\le 1\},\\
\left[0,1\right) &=\{x\mid 0\le x <1\}
\end{array}
\] have the least upper bound property.
\(\quad\)(b) Does \([0,1]\times [0,1]\) in the dictionary order have the least upper bound property? What about \([0, 1]\times [0, 1)\)? What about \([0, 1)\times [0, 1]\)?
Proof. \(\quad\)(a) Let \(S\subset [0,1]\). Since \(S\) of \(\mathbb{R}\) is bound above, \(S\) has a least upper bound \(m\). Clearly \(m\in[0,1]\), thus \([0,1]\) also has the least upper bound property. Let \(T\subset [0,1)\). Since \(T\) of \(\mathbb{R}\) is bounded above, \(T\) has a least upper bound \(n\) such that \(n\in[0,1]\). If \(n=1\), then \(T\) of \([0,1)\) is not bounded above. Thus if \(T\) of \([0,1)\) is bounded, then \(n\in [0,1)\). Therefore, \([0,1)\) has the least upper bound property.
\(\quad\)(b) \([0,1]\times [0,1]\) and \([0, 1)\times [0, 1]\) have the least upper bound property. \(\{0\}\times[0, 1)\subset [0, 1]\times [0, 1)\) has no least upper bound.\(\quad\square\)