Archive

Archive for February, 2009

1.3 Exercise 12

February 27th, 2009 No comments

This problem, although cool because it exposes us to out-of-the-ordinary order relations on the Cartesian plane, was a little long, I felt.  Nevertheless, it shows that we can create order relations with smallest elements, with elements with no immediate predecessors, and with no smallest elements, and any happy combination as well.

"Let  \mathbb Z_+ denote the set of positive integers.  Consider the following order relations on  \mathbb Z_+ \times \mathbb Z_+ :

(i) The dictionary order.

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

(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

In these order relations, which elements have immediate predecessors?  Does the set have a smallest element?  Show that all three order types are different." 

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

------

SOLUTION  

In this problem, I found it very helpful to write out the order sequence for the three cases, or even try to picture each on the Cartesian plane  \mathbb{Z}_+ \times \mathbb{Z}_+ .  Thus, for the dictionary order: 

13121

Having done so, it is a lot easier to see that the elements that do not have immediate predecessors are of the form  (j, 1) . For, choose any element in column  j-1 as a candidate,  (j-1, k) .  The problem is that the set  \{(x, y) \verb| | \vert \verb| | (j-1, k) < (x, y) < (j, 1)\} is nonempty because the element  (j-1, k+1) is in it.  The tricky part may be the element   (1, 1) .  This element has no immediate predecessor because it is the smallest element (since it is less than any other element and equal to itself).

For the order of (ii), the order sequence looks like:

13122

where  C = j-1 and  D = 1-k are constants determined by the choice of  j or  k .  Elements with no immediate predecessors are  (j, 1) and  (1, k) .  In the first case, candidates to be the immediate predecessor of  (j, 1) are  ((j+1)+m, (j+1)+m-C) , but then set  \{(x, y) \verb| | \vert \verb| | ((j+1)+m, (j+1)+m-C) < (x, y) < (j, 1)\} is never empty, because the element  ((j+1) + (m + 1), (j+1)+(m+1)-C) is in it.   Next for  (k, 1) , candidates to be the immediate predecessor are of form  ((k-1) + n + D, (k-1) + n) , but then again the set  \{(x, y) \verb| | \vert \verb| | ((k-1)+n+D, (k-1)+n) < (x, y) < (1, k)\} is never empty, because the element  ((k-1) + (n+1)+D, (k-1)+(n+1)) is in it.  

It is quite clear that there is no smallest element: for every element of form  (j, 1) and  (1, k) we can find a smaller element, as we've seen, and any other element  (j+m, j+m - C) a smaller element is  (j+(m-1), j+(m-1)-C) .  Similarly, for any element  (k+n+D, k+n) , a smaller element is  (k+(n-1)+D, k+(n-1)) .

Finally, for (iii):

13123

with  C = j+1 .  Here,  (1, 1) is clearly the smallest element (it is less than every other element and equal to itself).  Furthermore, every element except the smallest has an immediate predecessor.

All of these order relations are of different order type.  First we show that there is no order preserving bijection from  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_{ii} to  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_i or  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_{iii} .  For, suppose there is.  Then there exists an element  (j, 1) ,  (k, 1) ,  (j+m, j+m-C) , or  (k+n+D, k+n) ordered by  <_{ii} that maps to the smallest element of  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_i or  <_{iii} .  The problem is that, as we've seen, for each of these we can find a smaller element, where we cannot find a smaller element for the smallest element of  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_i or  <_{iii} .  Next we show that there cannot exist a bijection from  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_i to  \mathbb{Z_+} \times \mathbb{Z_+} ordered by  <_{iii} . Suppose there is.  An element  (j, 1) , having no immediate predecessors under  <_{i} , would have to map to the only element that does not have immediate predecessors under  <_{iii} , the smallest element.  But then there are elements  (j-1, k) that are less than  (j, k) that would be undefined under such a map, so the map is not bijective.

Thus, the three order relations are different order type.

1.3 Exercise 11

February 20th, 2009 No comments

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

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

-------

SOLUTION 

The element  a \in A ordered can have no more than one immediate successor, for, suppose there were. This means that  (a, b) and  (a, b') are both empty. Also,  a < b and  a < b' by definition and because the set is ordered.  In particular, however, either  b < b' xor  b' < b because the set is ordered. Suppose  b < b' .  Taking into account all the conditions,  a < b < b' and  (a, b') is nonempty, a contradiction.  Next suppose  b' < b .  Again, the conditions suggest  a < b' < b , and  (a, b) is nonempty, another contradiction.

We argue that an ordered set can have at most one immediate predecessor analogously.

To show that a subset of an ordered set has at most one smallest element, we argue again by contradiction.  Suppose otherwise, so that  a \in A_0 \subset A , an ordered set, and also  a' \in A_0 are smallest elements.  In particular, this means  a \leq x \verb| | \forall x \in A_0 , but also  a' \leq x \verb| | \forall x \in A_0 .  Since the set is ordered, however, either  a < a' xor  a' < a .  Suppose it is the first case, but then  a' is not less than all elements in  A_0 , because  a belongs to it.  It cannot be a smallest element too.  Suppose it is the second case, but then again  a is not less than all elements in  A_0 , because  a' belongs to it.  It cannot be a smallest element too.

We argue the fact that an ordered set has at most one largest element analogously.

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.