### Archive

Posts Tagged ‘Order Relations’

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

## 1.3 Exercise 7

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.

Categories:

## 1.3 Exercise 6

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.

Categories: