Abstract Nonsense

Crushing one theorem at a time

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<x<2\right\}

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<y_1-x_1^2, or y_0-x_0^2=y_1-x_1^2 and x_0<x_1. 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<x_0

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<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<y^2 or if x^2=y^2 then x<y.

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<x^2 or x^2<y^2

Non-reflexivity: Since x\not< x and x^2\not <x^2 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<x<y 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<x<0 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<b, 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<x 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<x_0, 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.

Advertisements

September 25, 2010 - Posted by | Fun Problems, Munkres, Topology | , , , , , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: