## Munkres Chapter one Section three: Relations

1.

**Problem:** Define two points and of the pane to be equivalent if . Check that this is an equivalence relation and describe the equivalence classes

**Proof:**

**Reflexivity**: Clearly

**Symmetry:** If then

and thus

**Transitivity: **If then and implies that . But, concatenating these inequalities and cutting out the middle gives and so .

2.

**Problem: **Let be a relation on a set . If , define the restriction of to to be the relation . Show that the restriction of an equivalence relation is an equivalence relation

**Proof:**

**Reflexivity:** Note that for each it’s true that and so (by ‘s reflexivity) and so

**Symmetry:** If then which says that and thus

**Transitivity: **If then we first note that . Furthermore, since we see that ‘s transitivity implies that and so by previous comment

3.

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

“Since is symmetric, . Since is transitive “

What’s the problem?

**Proof:** He assumed there is a such that

4.

**Problem: **Let be surjective function. Let us define a relation on by setting

if

**a) **Show that this is an equivalence relation

**b) **Let (set of all equivalence classes) Show there is a bijective correspondence between and

**Proof:**

**a)**

**Reflexivity:** Clearly, since is a function, so that

**Symmetry:** If then evidently from where symmetry immediately foll0ws.

**Transitivity:** Equally easy, if then

**b) ** Define

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

then

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

and then by the surjectivity of for every there is some such that . Thus, and so is surjective.

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

5.

**Problem:** LEt 4latex S$ and be the following subsets of

and

**a) **Show that is an equivalence relation on and . Describe the equivalence classes of

**b) **Show that given any collection of equivalence relations on a set , their intersection is an equivalence relation

**Proof:**

**a) **

**Reflexivity:** Clearly for every

**Symmetry:** This follows since

**Transitivity:** Clearly, if then and thus is the difference of two integers and so itself and integer.

To see that we merely note that

**b) **Let be a nonempty class of equivalence relations and let

To see that is an equivalence relation on we first note that since that . Next, we note that if then and so and so . Lastly, if then and so and so

6.

**Problem:** Define a relation on by setting if either , or and . Show that this an order relation on the plane.

**Proof:**

**Comparable**:** **Since the definition of the relation took arbitrary points in and compared them, it’s clearly a linear ordering.

**Non-reflexive:** This is clear since

**Transitive: **Suppose that and . 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 be an order relation on and .

**Comparability:** Let then and so or , and so or

**Non-reflexivity:** If then

which is a contradiction.

**Transitivity:** This is identical to the transitivity proof for restrictions of equivalence relations.

8.

**Problem:** Check that the relation given by iff or if then .

**Proof:**

**Comparability:** Let . If then and if then we have by the comparability of the usual ordering on that either or

**Non-reflexivity:** Since and non-reflexivity is immediate.

**Transitivity:** This is just several simple cases again.

9.

**Problem:** Check that if and are two ordered sets, then the dictionary order is an order relation on

**Proof: **This is also relatively menial, but so important that it needs to be done:

**Comparability:** Let be arbitrary. If then the comparability of implies that either or , and so either or . If the comparability of implies that either or and so either or

**Non-reflexivity: **Note that by the non-reflexivity of we see that and so

**Transitivity:** Suppose that and . Now, if then . So, if we see that and so and so . If then and so . Now, if then . If then and so . If then and th same conclusion follows.

10.

**Problem:**

**a) **Show that the map :x\mapsto\frac{x}{1-x^2}$ is order preserving.

**b) **Show that the equation defines an inverse for

**Proof:**

**a) **Suppose that then and so and so and so finally . Next, suppose that then and so the above shows that and so 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 and suppose that and are both immediate predecessor to . Suppose that , then contradicting ‘s status as an immediate predecessor. The proof for immediate successor is similar.

Let both be least elements of a set . Then, since we have that . But, since we have that . Since and is impossible, it follows that . 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 has the l.u.b. property, then it has the g.l.b. property.”

**Proof:** Let have the l.u.b. property and let be bounded below. Consider the set . Then, (since is bounded below) and it’s bounded above (by any element of ). Thus, by assumption exists. We claim that . To see this, first note that , since otherwise there is some such that and so clearly is an upper bound for which is smaller than , contradicting it’s definition as . Now, to see that for every we suppose not, then there is some such that , but this contradicts that is an upper bound for . It follows that and that . Thus, and so .

*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 is a relation on a set , define a new relation on by letting if

**a) **Show that is symmetric iff

**b) **Show that if is an order relation, then is an order relation.

**c) **Prove the converse of the theorem in exercise thirteen.

**Proof:**

**a) **This is absolutely clear. If then .

**b) **

**Comparability:** Let be arbitrary. We may assume WLOG that and so

**Non-reflexivity: **Suppose that then , which is a contradiction.

**Transitivity: **Let be arbitrary, then and so and therefore

**c) **It’s pretty much the same procedure. For a non-empty bounded above set we have that is non-empty and bounded below. Thus, exists and using the same logic as before one can show that .

15.

**Problem:** Assume that the real line has the l.u.b. property.

**a) **Show that the sets and have the l.u.b.

**b) **Does in the dictionary order have the l.u.b? What about ? What about

**Proof:**

**a) **Let be bounded above by . By the l.u.b property of we have that $ exists. Clearly, we have that and , thus

Let be nonempty and bounded above by . We have that and certainly .

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

No comments yet.

## Leave a Reply