Archive

Archive for February, 2009

1.3 Exercise 12

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:

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:

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):

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.

Categories:

1.3 Exercise 11

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

Categories:

1.3 Exercise 10

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,

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

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,

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:

By transitivity on zero,

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:

Now,

$g(f(x)) = x$

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

Categories:

1.3 Exercise 9

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.

Categories:

1.3 Exercise 8

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.

Categories: