Archive

Archive for the ‘Relations’ Category

1.3 Exercise 10

February 13th, 2009 No comments

This problem acquaints us with the notion that two sets can be the same order type.  The requirement is that a function between the sets preserve order and that it be bijective.

"(a) Show that the map  f : (-1,1) \rightarrow \mathbb R of Example 9 is order preserving.

 f(x) = \frac{x}{1-x^2}

(b) Show that the equation  g(y) = \frac{2y}{[1+(1+4y^2)^{\frac{1}{2}}]}  defines a function  g : \mathbb R \rightarrow (-1,1) that is both a left and right inverse for  f ."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 29.)

---------

SOLUTION

(a)

If the map is order preserving, then  x_1 < x_2 \Rightarrow f(x_1) < f (x_2) .  Now, we've got to be careful or we will not be thorough.  We have to assume that the set  (-1, 1) inherits the standard order of the reals.

Pick  x_1 = 0, x_2 but in  (0, 1) , and thus  0 < x_2 by the standard order of the reals.  We've got to proceed by contradiction.  Suppose  f(0) \geq f(x_2) .  This means  0 \geq \frac{x_2}{1-x_2^2} .  Since the denominator is positive, we can multiply both sides of the inequality without affecting the ordering (we take this as an axiomatic property of inequality), to obtain  0 \geq x_2 , a clear contradiction.  

Next pick  x_1 but in  (-1, 0) and  x_2 = 0 , so that  x_1 < 0 by the standard order of the reals.  Again proceeding by indirect proof, assume  f(x_1) \geq f(0) , which means  \frac{x_1}{1-x_1^2} \geq 0 .  Again the denominator is positive for any choice of  x_1 in the domain, so we can multiply without affecting the ordering.  In this case,  x_1 \geq 0 , contrary to our assumption.  

Now, by transitivity on zero, any  x_1 < x_2 with  x_1 < 0 and  0 < x_2 (but within the domain  (-1, 1) ) implies  f(x_1) < f(0), f(0) < f(x_2) \Rightarrow f(x_1) < f(x_2) . We have yet to check that any two positive choices  x_1, x_2 and two negative choices  x_1, x_2 (within the domain) are ordered under the image.

Pick two  x_1, x_2 > 0, x_1 < x_2 within  (0, 1) .  By indirect proof,

1310a1

We know from hypothesis that  x_1 < x_2 \Rightarrow x_1 - x_2 < 0 .  Thus, by transitivity of the reals:

1310a2

This last step is justified because, since both  x_1, x_2 are positive quantities, we can divide both sides by either one without affecting the ordering.  Now, the conclusion is contrary to our assumption that   x_1 < x_2 .  Thus  x_1 < x_2 \Rightarrow f(x_1) < f (x_2) must be true for two positive choices of  x_1, x_2 in the domain. 

Lastly, pick two   x_1, x_2 < 0, x_1 < x_2 within  (-1, 0) .  By indirect proof,

1310a3

Let's make the negative sign explicit so that the elements  x_1, x_2 are positive and within  (0, 1) . But this in particular now means that  x_2 < x_1 \Rightarrow x_2 - x_1 < 0 .

 \frac{x_1}{x_1^2 - 1} \geq \frac{x_2}{x_2^2 - 1}

The denominators are both negative quantities.  In particular, when we multiply by one there will be an inequality reversal, but multiplying then by the other preserves the inequality.  Thus:

1310a4

By transitivity on zero, 

1310a5

This last bit is contrary to our assumption, and we are done.

Therefore  f is order preserving. 

(b)

First we observe in particular that any  y works (negative or otherwise) because the squaring of  y makes  g(y) 's denominator positive  \forall y .  So there are no discontinuities and the domain of  g is all of  \mathbb R .  Secondly, we observe that if we pick  y a very large number,  1+4y^2 \approx 4y^2 and the denominator becomes approximately  1+2y \approx 2y .  Thus  g(y) < 1 for  y a very large number.  Arguing similarly,  g(y) > -1 for  y a very large negative number.  The image of  g(y) is therefore  (-1,1) .

We now show that  g(y) is a right inverse by calculating  f(g(y)) = y .  Then we show  g(y) is a left inverse by calculating   g(f(x)) = x .

 f(g(y)) = y

Just for fun, rearrange  g(y) as:

1310b

Now, 

1310c

 

 g(f(x)) = x

1310d

The fact that  f is both order preserving and bijective means that  (-1, 1) and  \mathbb{R} are the same order type.

1.3 Exercise 9

February 12th, 2009 No comments

The dictionary order relation is very important, because it describes in probably the most sensible way  how we can order points on the Cartesian plane (or on any Cartesian product).  

"Check that the dictionary order is an order relation." 

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 29.)

-----

SOLUTION  

First, notice that the dictionary order is defined on  A \times B (and thus the dictionary order relation lives in  (A \times B) \times (A \times B) ).

Comparability.   Pick  a_1 \times b_1 \neq a_2 \times b_2 .  Then either  a_1 <_A a_2 , or  a_1 >_A a_2 (or both). If  a_1 = a_2 , then either  b_1 <_B b_2 or  b_1 >_B b_2 (or both).  Notice that if  b_1 = b_2 , then  a_1 \times b_1 = a_2 \times b_2 , contrary to our pick or assumption.  Thus, comparability is true for all elements of  A \times B .

Non-reflexivity.  We want to show that for no  a \times b \in A \times B the statement  (a \times b, a \times b) \in C holds.  Suppose it does for some element.  Then this means  a <_A a , but this contradicts the identity or reflexive property of equality.  It follows  a = a , but then  b <_B b , again a contradiction.  Non-reflexivity holds therefore for all elements  a \times b .

Transitivity.  Picking  a_1 \times b_1 ,  a_2 \times b_2 , and  a_3 \times b_3 \in A \times B , we have to show that  a_1 \times b_1 < a_2 \times b_2 and  a_2 \times b_2 < a_3 \times b_3 implies  a_1 \times b_1 < a_3 \times b_3 .  As in previous problems, we can check this by proceeding in cases.  In the first case,  a_1 <_A a_2 and  a_2 <_A a_3 .  This means  a_1 <_A a_2 <_A a_3 .  Here may be a sticky part: we have to know that the set  A is ordered (and transitivity holds in that set), as we do because we know  <_A is an ordering relation.  Thus, by transitivity of the set  A ,  a_1 <_A a_3 .  In the second case,   a_1 <_A a_2 and  a_2 = a_3 .  In this case we use substitution and arrive at  a_1 <_A a_3 .  In the third case,   a_1 = a_2 and  a_2 <_A a_3 .  Again by substitution  a_1 <_A a_3 .  In the fourth case,   a_1 = a_2 and  a_2 = a_3 .  This implies  b_1 <_B b_2 and  b_2 <_B b_3 .  In turn, this means  b_1 <_B b_2 <_B b_3 .  Again, we have to know that  B is ordered (as we do, by  <_B ), and thus transitivity holds for the elements of  B :  b_1 <_B b_3 .  It follows that the order relation on  A \times B inherits transitivity.

1.3 Exercise 8

February 11th, 2009 No comments

Other than just teaching us to check that order relations satisfy the properties of comparability, non-reflexivity, and transitivity, these problems also give us insight into how we can order different elements of a set, in this particular case a very familiar one: the reals.  For example, the order relation defined on the reals of this problem shows the uncanny notion that we can order them as follows: 

 0 < \ldots < -0.5 < 0.5 < \ldots < -1 < 1 <\ldots < -2.1234 < 2.1234 < \ldots

"Check that the relation defined in Example 7 is an order relation: Define  xCy if  x^2 < y^2 , or if  x^2 = y^2 and  x < y ."  

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 29.)

-------

SOLUTION  

First we notice that the order relation is defined on  \mathbb{R} .

Comparability:  Choosing  x, y \in \mathbb{R} , so that  x \neq y , either  x^2 < y^2 or  y^2 < x^2 (or both), and the elements are comparable.  Supposing  x^2 = y^2 , then either  x < y or  x > y (or both).  The elements are comparable.  If  x = y , then we picked the elements contrary to our assumption.  Thus comparability holds.

Non-reflexivity:  we want to show that for no  x \in \mathbb{R} the statement  (x, x) \in C holds.  Suppose it holds for some element  x .  This means  x^2 < x^2 which will contradict the identity property of equality. So  x^2 = x^2 .  Then, checking the second criterion,  x < x , we conclude that this is also a contradiction.  Non-reflexivity must hold.

Transitivity.  If  x, y, z \in \mathbb{R} , we want to show that if  xCy and  yCz , this implies  xCz .  There are four cases.  In the first case,  x^2 < y^2 and  y^2 < z^2 implies  x^2 < y^2 < z^2 .  Since the reals are transitive axiomatically,  x^2 < z^2 .  In the second case  x^2 < y^2 and  y^2 = z^2 .  We can substitute and ascertain that  x^2 < z^2 .  In the third case,  x^2 = y^2 and  y^2 < z^2 .  Substituting again we obtain  x^2 < z^2 .  Finally,  x^2 = y^2 \Rightarrow x < y and  y^2 = z^2 \Rightarrow y < z .  This implies  x < y < z , but by transitivity of the reals,  x < z .  Transitivity must hold.  

1.3 Exercise 7

February 10th, 2009 No comments

After doing the same procedure for an exercise on equivalence relations, this question should pose no problem.  Important is starting to visualize relations on the Cartesian product of a set.  What does an order relation look like?  It is upper or lower triangular (by comparability and transitivity), with the identity line deleted (because of non-reflexivity).  Contrast this with what an equivalence relation looks like: a square (because of symmetry and transitivity) with an extended diagonal (the identity line by reflexivity).

"Show that the restriction of an order relation is an order relation."   

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 29.)

--------

SOLUTION  

Suppose there is an order relation defined on the elements of  A .

Comparability:  Pick  x, y \in A with  x \neq y  (x, y) \in A \times A and  (y, x) \in A \times A , but importantly, either  (x, y) \in C or  (y, x) \in C (or both).  Now suppose these same elements  x, y \in A_0 .  Then  (x, y) \in A_0 \times A_0 , and  (y, x) \in A_0 \times A_0 .  We already know that either one or the other (or both) of such elements belong to  C .  Thus either  (x, y) \in C \cap A_0 \times A_0 or  (y, x) \in C \cap A_0 \times A_0 (or both).  The restriction inherits comparability.

Non-reflexivity.  Picking  x \in A , it is clear that  (x, x) \in A \times A .  We know, however, that  (x, x) \notin C .  If such  x is picked so that it also belongs to  A_0 , then  (x, x) \in A_0 .  But such an element of the cross product is not in  C , we've established, so it cannot possibly be in the intersection of  C with  A_0 \times A_0 .  Thus,  C \cap A_0 \times A_0 inherits non-reflexivity.

Transitivity.  Picking different elements  x, y, z \in A , it is clear that in particular the elements  (x, y), (y, z) , and  (x, z) \in A \times A .  Suppose these elements  x, y, z \in A_0 , and thus   (x, y), (y, z) , and  (x, z) \in A_0 \times A_0 .  Now further suppose  (x, y), (y, z) \in C .  By transitivity of the order relation in  A ,  (x, z) \in C .  This last element is in both  C and  A_0 \times A_0 , and thus it is in the intersection.  Transitivity of the order relation is inherited by the restriction.

We conclude that the restriction of an order relation is an order relation.

1.3 Exercise 6

February 9th, 2009 No comments

I've been a little remiss about writing problems and their solutions out this last week because I'm taking the civil service exam and have been studying for it.  There is lots of history that I don't know!  There is lots of math that I don't know either, but I think I want to aggrandize my knowledge set so that it is diverse, than so specialized.  I favor Encyclopedism. 

Without further ado, however, here's exercise 1.3.6.  This is interesting like the first problem on Equivalence Relations was interesting; ordering based on parabolas.

"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."  

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 29.)

-----------

SOLUTION 

Comparability: Choosing two points  (x_0, y_0) \neq (x_1, y_1) , either  y_0 - x_0^2 < y_1 - x_1^2 or   y_0 - x_0^2 < y_1 - x_1^2 (or both, by the definition of "or": non-reflexivity and transitivity will exclude one or the other possibility).  If they are equal, then  x_0 < x_1 or  x_0 > x_1 (or both).  If  x_0 = x_1 ,  y_0 = y_1 , and then  (x_0, y_0) = (x_1, y_1) , contrary to our assumption.

Non-reflexivity: we want to show that for no  (x, y) in the plane the relation  (x, y) < (x, y) holds.  So suppose it holds for some point.  This means  y^2 - x < y^2 - x , which is not true because of the identity (reflexive) property of equality (an element equals itself).  So then we conclude that  y^2 - x = y^2 - x . At this point we have to check the second criterion,  x < x .  Again this contradicts the identity (reflexive) property of equality.  Our assumption must have been wrong, so there is no  (x, y) that is lesser than itself.

Transitivity.  We want to show that  (x_0, y_0) < (x_1, y_1) and  (x_1, y_1) < (x_2, y_2) \Rightarrow (x_0, y_0) < (x_2, y_2) . There are four cases.  In the first case,  y_0^2 - x_0 < y_1^2 - x_1 and  y_1^2 - x_1 < y_2^2 - x_2 .  This implies  y_0^2 - x_0 < y_1^2 - x_1 < y_2^2 - x_2 , and  y_0^2 - x_0 < y_2^2 - x_2 . This last step is justifiable because the order relation of the reals is axiomatic (hence, transitivity of the reals is axiomatic). In the second case,  y_0^2 - x_0 < y_1^2 - x_1 , and   y_1^2 - x_1 = y_2^2 - x_2 and  x_1 < x_2 .  Substitution shows the implication:  y_0^2 - x_0 < y_2^2 - x_2 .  In the third case,  y_0^2 - x_0 = y_1^2 - x_1 and  x_0 < x_1 , and   y_1^2 - x_1 < y_2^2 - x_2 .  Again substitution shows the implication:  y_0^2 - x_0 < y_2^2 - x_2 .  Finally, in the fourth case,  y_0^2 - x_0 = y_1^2 - x_1 and  x_0 < x_1 , and  y_1^2 - x_1 = y_2^2 - x_2 and  x_1 < x_2 .  This in turn suggests  x_0 < x_1 < x_2 , and  x_0 < x_2 .  Again, this last step is justifiable because we inherit transitivity of the reals from the axiomatic fact that the reals are ordered.

For two points in different standard parabolas  y - x^2 = K , the point that is "lesser" is in the bottomest parabola.  For two points on the same parabola, the one on the left is lesser.  Put a different way, for a single point, such a point is lesser than all the points in parabolas above its own, and lesser than points on the same parabola to the right of itself.