# Abstract Nonsense

## Munkres Chapter one Section three: Relations

1.

Problem: Define two points $(x_0,y_0)$ and $(x_1,y_1)$ of the pane 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:

Reflexivity: Clearly $y_0-x_0^2=y_0-x_0^2$

Symmetry: If $(x_0,y_0)\sim (x_1,y_1)$ then

$y_0-x_0^2=y_1-x_1^2\implies y_1-x_1^2=y_0-x_0^2$

and thus $(x_1,y_1)\sim(x_0,y_0)$

Transitivity: If $(x_0,y_0)\sim(x_1,y_1)$ then $y_0-x_0^2=y_1-x_1^2$ and $(x_1,y_1)\sim(x_2,y_2)$ implies that $y_1-x_1^2=y_2-x_2^2$. But, concatenating these inequalities and cutting out the middle gives $y_0-x_0^2=y_2-x_2^2$ and so $(x_0,y_0)\sim(x_2,y_2)$.

2.

Problem: Let $C$ be a relation on a set $A$. If $A_0\subseteq A$, define the restriction of $C$ to $A_0$ to be the relation $C\cap\left(A_0\times A_0\right)$. Show that the restriction of an equivalence relation is an equivalence relation

Proof:

Reflexivity: Note that for each $x\in A_0$ it’s true that $x\in A$ and so $(x,x)\in C$ (by $C$‘s reflexivity) and so $(x,x)\in C\cap\left(A_0\times A_0\right)$

Symmetry: If $(x,y)\in C\cap\left(A_0\times A_0\right)$ then $(x,y)\in C\text{ and }(x,y)\in A_0\times A_0$ which says that $(y,x)\in C\text{ and }(y,x)\in A_0\times A_0$ and thus $(y,x)\in C\cap\left(A_0\times A_0\right)$

Transitivity: If $(x,y),(y,z)\in C\cap\left(A_0\times A_0\right)$ then we first note that $x,y,z\in A_0$. Furthermore, since $(x,y),(y,z)\in C$ we see that $C$‘s transitivity implies that $(x,z)\in C$ and so by previous comment $(x,z)\in C\cap\left(A_0\times A_0\right)$

3.

Problem: Here is a proof that every relation $C$ that is both symmetric and transitive is also relfexive

“Since $C$ is symmetric, $x\sim y\implies y\sim x$. Since $C$ is transitive $x\sim y\text{ and }y\sim x\implies x\sim x$

What’s the problem?

Proof: He assumed there is a $y$ such that $x\sim y$

4.

Problem: Let $f:A\to B$ be surjective function. Let us define a relation on $A$ by setting

$a_0\sim a_1$ if $f(a_0)=f(a_1)$

a) Show that this is an equivalence relation

b) Let $A^*=\left\{E(x):x\in A\right\}$ (set of all equivalence classes) Show there is a bijective correspondence between $A^*$ and $B$

Proof:

a)

Reflexivity: Clearly, since $f$ is a function, $a_0=a_1\implies f(a_0)=f(a_1)$ so that $a_0\sim a_1$

Symmetry: If $f(a_0)=f(a_1)$ then evidently $f(a_1)=f(a_0)$ from where symmetry immediately foll0ws.

Transitivity: Equally easy, if $f(a_0)=f(a_1),f(a_1)=f(a_2)$ then $f(a_0)=f(a_2)$

b) Define

$\eta:A^*\to B:E(x)\mapsto f(x)$

First, it is not clear that this is actually a function (the rule of assignment implicitly stated above). To see this suppose that

$E(x)=E(y)$

then

$\eta\left(E(x)\right)=f(x)=f(y)=\eta\left(E(y)\right)$

thus $\eta$ is a well-defined function. To see that this function is bijective we first note that if

$f(x)\ne f(y)\implies x\not\sim y\implies E(x)\ne E(y)$

and then by the surjectivity of $f$ for every $y\in B$ there is some $x\in A$ such that $f(x)=y$. Thus, $\eta\left(E(x)\right)=y$ and so $\eta$ is surjective.

Remark: All we’ve done is identified the fibers together

5.

Problem: LEt 4latex S$and $S'$ be the following subsets of $\mathbb{R}^2$ $S=\left\{(x,y)\in\mathbb{R}^2:y=x+1\text{ and }0 and $S'=\left\{(x,y)\in\mathbb{R}^2:y-x\in\mathbb{R}\right\}$ a) Show that $S'$ is an equivalence relation on $\mathbb{R}$ and $S'\supseteq S$. Describe the equivalence classes of $S'$ b) Show that given any collection of equivalence relations on a set $A$, their intersection is an equivalence relation Proof: a) Reflexivity: Clearly $x-x=0$ for every $x\in\mathbb{R}$ Symmetry: This follows since $z\in\mathbb{Z}\implies -z\in\mathbb{Z}$ Transitivity: Clearly, if $x\sim y,y\sim z$ then $z-y=(z-x)-(x-y)$ and thus $z-y$ is the difference of two integers and so itself and integer. To see that $S\subseteq S'$ we merely note that $y=x+1\implies y-x=1\in\mathbb{Z}$ b) Let $\left\{R_\alpha\right\}_{\alpha\in\mathcal{A}}$ be a nonempty class of equivalence relations and let $\displaystyle \Omega=\bigcap_{\alpha\in\mathcal{A}}R_{\alpha}$ To see that $\Omega$ is an equivalence relation on $\mathbb{R}$ we first note that since $(x,x)\in R_\alpha,\text{ }\forall \alpha\in\mathcal{A}$ that $(x,x)\in\Omega$. Next, we note that if $(x,y)\in\Omega$ then $(x,y)\in R_\alpha,\text{ }\forall \alpha\in\mathcal{A}$ and so $(y,x)\in R_\alpha,\text{ }\forall\alpha\in\mathcal{A}$ and so $(y,x)\in\Omega$. Lastly, if $(x,y),(y,z)\in\Omega$ then $(x,y)(y,z)\in R_{\alpha},\text{ }\forall\alpha\in\mathcal{A}$ and so $(x,z)\in R_{\alpha},\text{ }\forall \alpha\in\mathcal{A}$ and so $(x,z)\in\Omega$ 6. Problem: Define a relation on $\mathbb{R}^2$ by setting $(x_0,y_0)<(x_1,y_1)$ if either $y_0-x_0^2, or $y_0-x_0^2=y_1-x_1^2$ and $x_0. Show that this an order relation on the plane. Proof: Comparable: Since the definition of the relation took arbitrary points in $\mathbb{R}^2$ and compared them, it’s clearly a linear ordering. Non-reflexive: This is clear since $x_0\not Transitive: Suppose that $(x_0,y_0)<(x_1,y_1)$ and $(x_1,y_1)<(x_2,y_2)$. There are several cases all of which are trivial. 7. Problem: Show that the restriction of an order relation is an order relation. Proof: Let $R$ be an order relation on $A$ and $A_0\subseteq A$. Comparability: Let $x,y\in A_0$ then $x,y\in A$ and so $(x,y)\in C$ or $(y,x)\in C$, and so $(x,y)\in C\cap\left(A_0\times A_0\right)$ or $(y,x)\in C\cap\left(A_0\times A_0\right)$ Non-reflexivity: If $x then $(x,x)\in C\cap\left(A_0\times A_0\right)\subseteq C$ which is a contradiction. Transitivity: This is identical to the transitivity proof for restrictions of equivalence relations. 8. Problem: Check that the relation $R\subseteq\mathbb{R}^2$ given by $x<_R y$ iff $x^2 or if $x^2=y^2$ then $x. Proof: Comparability: Let $x,y\in\mathbb{R}$. If $y=-x,\text{ }x\geqslant 0$ then $y<_R x$ and if $y\ne -x$ then we have by the comparability of the usual ordering on $\mathbb{R}$ that either $y^2 or $x^2 Non-reflexivity: Since $x\not< x$ and $x^2\not non-reflexivity is immediate. Transitivity: This is just several simple cases again. 9. Problem: Check that if $\left(A,<_A\right)$ and $\left(B,<_B\right)$ are two ordered sets, then the dictionary order $<_D$ is an order relation on $A\times B$ Proof: This is also relatively menial, but so important that it needs to be done: Comparability: Let $(a,b),(c,d)\in A\times B$ be arbitrary. If $a\ne c$ then the comparability of $<_A$ implies that either $a<_A c$ or $c<_A a$, and so either $(a,b)<_D (c,d)$ or $(c,d)<_D (a,b)$. If $x=y$ the comparability of $<_B$ implies that either $b<_B d$ or $d<_B b$ and so either $(a,b)<_D (c,d)$ or $(c,d)<_D (a,b)$ Non-reflexivity: Note that by the non-reflexivity of $<_B$ we see that $b\not <_B b$ and so $(a,b)\not<_D(c,d)$ Transitivity: Suppose that $(a,b)<_D (c,d)$ and $(c,d)<_D (e,f)$. Now, if $a=c$ then $(a,b)<_D (c,d)\implies b<_B c$. So, if $c=e$ we see that $(c,d)<_D (e,f)\implies d<_B f$ and so $b<_B f$ and so $(a,b)<_D (e,f)$. If $c\ne e$ then $(c,d)<_D (e,f)\implies a=c<_A e$ and so $(a,b)<_D (e,f)$. Now, if $a\ne c$ then $(a,b)<_D (c,d)\implies a<_A c$. If $c=e$ then $a<_A c=e$ and so $(a,b)<_D (e,f)$. If $c\ne e$ then $(c,d)<_D (e,f)\implies c<_A e$ and th same conclusion follows. 10. Problem: a) Show that the map $f:(-1,1)\to\mathbb{R}$:x\mapsto\frac{x}{1-x^2}$  is order preserving.

b) Show that the equation $g(y)=\frac{2y}{1+\sqrt{1+4y^2}}$ defines an inverse for $f$

Proof:

a) Suppose that $0 then $-x^2>-y^2$ and so $1-x^2>1-y^2$ and so $\frac{1}{1-x^2}<\frac{1}{1-y^2}$ and so finally $\frac{x}{1-x^2}<\frac{y}{1-y^2}$. Next, suppose that $y then $-y>-x>0$ and so the above shows that $\frac{-x}{1-x^2}<\frac{-y}{1-y^2}$ and so $\frac{x}{1-x^2}>\frac{y}{1-y^2}. If$latex x>0,y<0$this obvious. b) This is just function composition and is simple. 11. Problem: Show that an element of 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: Let $a,b\in A$ and suppose that $a$ and $b$ are both immediate predecessor to $c$. Suppose that $a, then $b\in(a,c)$ contradicting $a$‘s status as an immediate predecessor. The proof for immediate successor is similar. Let $\alpha,\beta$ both be least elements of a set $A$. Then, since $\alpha\in A$ we have that $\beta\leqslant\alpha$. But, since $\beta\in A$ we have that $\alpha\leqslant \beta$. Since $\alpha<\beta$ and $\beta<\alpha$ is impossible, it follows that $\alpha=\beta$. The proof for largest elements is similar. 12. I’ve done this, but I don’t feel like writing it up. I will at request though. 13. Problem: Prove the following theorem: ” If an ordered set $A$ has the l.u.b. property, then it has the g.l.b. property.” Proof: Let $A$ have the l.u.b. property and let $\varnothing\subsetneq E\subseteq A$ be bounded below. Consider the set $L=\left\{x\in A:x\leqslant e,\text{ }\forall e\in E\right\}$. Then, $L\ne\varnothing$ (since $E$ is bounded below) and it’s bounded above (by any element of $E$). Thus, by assumption $\sup L=\alpha$ exists. We claim that $\alpha=\inf E$. To see this, first note that $\sup L\in L$, since otherwise there is some $e\in E$ such that $e and so clearly $e$ is an upper bound for $L$ which is smaller than $\alpha$, contradicting it’s definition as $\sup L$. Now, to see that $x\leqslant \alpha$ for every $x\in L$ we suppose not, then there is some $x_0\in L$ such that $\alpha, but this contradicts that $\alpha$ is an upper bound for $L$. It follows that $\alpha\geqslant x,\text{ }\forall x\in L$ and that $\alpha\in L$. Thus, $\alpha=\min L$ and so $\alpha=\inf E$. Remark: That may have been poorly written (I’m in a rush to finish these), if you have any questions just ask. 14. Problem: If $C$ is a relation on a set $A$, define a new relation on $A$ by letting $(b,a)\in D$ if $(a,b)\in C$ a) Show that $C$ is symmetric iff $C=D$ b) Show that if $C$ is an order relation, then $D$ is an order relation. c) Prove the converse of the theorem in exercise thirteen. Proof: a) This is absolutely clear. If $(a,b)\in C$ then $(b,a)\in D=C$. b) Comparability: Let $x,y\in A$ be arbitrary. We may assume WLOG that $(x,y)\in C$ and so $(y,x)\in D$ Non-reflexivity: Suppose that $(x,x)\in D$ then $(x,x)\in C$, which is a contradiction. Transitivity: Let $(x,y),(y,z)\in D$ be arbitrary, then $(z,y),(y,x)\in C$ and so $(z,x)\in C$ and therefore $(x,z)\in D$ c) It’s pretty much the same procedure. For a non-empty bounded above set $E$ we have that $U=\left\{x\in A:x\geqslant e,\text{ }\forall e\in E\right\}$ is non-empty and bounded below. Thus, $\inf U$ exists and using the same logic as before one can show that $\inf U=\sup E$. 15. Problem: Assume that the real line has the l.u.b. property. a) Show that the sets $[0,1]$ and $[0,1)$ have the l.u.b. b) Does $[0,1]^2$ in the dictionary order have the l.u.b? What about $[0,1]\times[0,1]$? What about $[0,1)\times[0,1]$ Proof: a) Let $E\subseteq[0,1]$ be bounded above by $x\leqslant 1$. By the l.u.b property of $\mathbb{R}$ we have that$$\sup_{\mathbb{R}}[0,1]=\alpha$ exists. Clearly, we have that $0\alpha$ and $\alpha\leqslant 1$, thus $\alpha\in [0,1]$

Let $E\subseteq [0,1)$ be nonempty and bounded above by $x$. We have that $\frac{x+1}{2}<1$ and certainly $\sup_{\mathbb{R}}(E)=\alpha<\frac{x+1}{2}$.

b) Ask me for these answers if there’s a strong desire too.