Archive

Archive for February, 2009

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:

1.3 Exercise 5

This problem was fun but a bit long.  In it we see how we can construct a couple uncommon equivalence relations on the real line.  Having done this, one should have the grasp to create monsters of any kind.

"Let $S$ and $S'$ be the following subsets of the plane:

$S = \{(x, y)\verb| | \vert \verb| | y = x+1$ and $0

$S' = \{(x, y)\verb| | \vert \verb| | y - x$ is an integer$\}$

(a) Show that $S'$ is an equivalence relation on the real line and $S' \supset S$.  Describe the equivalence classes of $S'$.

(b) Show that given any collection of equivalence relations on a set $A$, their intersection is an equivalence relation on $A$.

(c) Describe the equivalence relation $T$ on the real line that is the intersection of all equivalence relations on the real line that contain $S$.  Describe the equivalence classes of $T$."

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

-----------

SOLUTION

(a)

First, notice that the equivalence relation is on $\mathbb{R}$, this is the set we've been calling $A$ in previous problems.  And so an equivalence relation lives in $\mathbb{R} \times \mathbb{R}$, as can be seen from the definition of $S'$.

Reflexivity is established by the fact that $S' \supset \{(x, y) \verb| | \vert \verb| | y - x = 0 \}$, and so $\forall x \verb| | (x, x) \in C$ simply means $x - x = 0$ is true for all $x$.  Recognizing this as a real number axiom, we take for granted its veracity.

Symmetry: by definition, $S' \supset \{(x, y) \verb| | \vert \verb| | y - x = K \}$ with $K \in \mathbb{Z}$.  We wish to show that $(y, x) \in S'$, and this would mean $x - y = K$.  Rearranging this in turn suggests that $-(y - x) = K$, or $y - x = -K$.  Now $-K$ is also an integer by closure of the ring operation "addition" ($-K + K = 0 \verb| | \vert \verb| | K, 0 \in \mathbb{Z} \Rightarrow -K \in \mathbb{Z}$), and so $S' \supset \{(x, y) \verb| | \vert \verb| | y - x = -K \}$.  Thus, $(x, y)$ and $(y, x)$ are in $S'$.

Transitivity.  Picking elements $(x, y), (y, z) \in S'$, we want to show $(x, z) \in S'$.  Again we will resort  to the definitions.  That the first point is in $S'$ suggests $y - x = K_1$ with $K_1 \in \mathbb{Z}$, and the second that $z - y = K_2 \Rightarrow y = z - K_2$ with $K_2 \in \mathbb{Z}$. Substituting we get $z - K_2 - x = K_1 \Rightarrow z - x = K_1 + K_2 = K_3$, with $K_3 \in \mathbb{Z}$ by closure of the ring structure of integers.  Thus, $(x, z) \in S'$.

To show the inclusion $S' \supset S$, recast $S$ as $\{(x, y) \verb| | \vert \verb| | y - x = 1$ and $0 < x < 2\}$.  Obviously $S' \supset \{(x, y) \verb| | \vert \verb| | y - x = 1\}$, and $S'$ also includes any subset of $\{(x, y) \verb| | \vert \verb| | y - x = 1\}$, too.

Having picked an $i \in [0, 1)$, the equivalence classes can be described by $E_i = \{e \verb| | \vert \verb| | e = i + z, z \in \mathbb{Z}\}$.  The set of integers is an equivalence class, e.g.

(b)

Reflexivity is established by the fact that the reflexive elements belong to all equivalence relations on $A$, or, in other words, $\forall x \in A, (x, x) \in C_i$ if we index by $i$.  Thus, $\forall x \in A, (x, x) \in \cap C_i$.

Symmetry.  First, notice that any particular equivalence relation of $A$ is symmetric. So now pick any element in the intersection of equivalence relations, $(x, y) \in \cap C_i$.  Such a point belongs to all equivalence relations because it is in the intersection.  Its symmetric point $(y, x)$ is also in all equivalence relations, and therefore it is in the intersection. We can conclude $(y, x) \in \cap C_i$, or $\cap C_i$ is symmetric.

Transitivity. First notice that each and all equivalence relations are transitive.  So now pick points $(x, y), (y, z) \in \cap C_i$.  These points are in all equivalence relations because they are in the intersection.  But then the point $(x, z)$ is in all equivalence relations as well.  Therefore it will find its way in the intersection $(x, z) \in \cap C_i$, and $\cap C_i$ is transitive.

(c)

The set $T$ is an equivalence relation, by (b) above.  $T$ contains $S$ because the elements of $S$ are in all equivalence relations  by the definition of intersection.  Also, $T$ contains the set $\{(x, y) \verb| | \vert \verb| | y-x = 0\}$ by reflexivity.  Then by symmetry, $T$ contains $\{(x, y) \verb| | \vert \verb| | y = x -1, 1 < x < 3\}$.  There are additional elements that are included by transitivity: pick two points $(x, x+1), (x+1, x+2) \in S$ with $0 < x+1 < 2$.  This last statement suggests $-1 < x < 1$, but $x$ must be greater than zero because of the restriction of $S$, so $0 < x < 1$.  These elements obtained by transitivity indicate that points of the set $S^* = \{(x, y) \verb| | \vert \verb| | y = x+2, 0 are in $T$.  By symmetry again, $\{(x, y) \verb| | \vert \verb| | y = x-2, 2.  We should try applying transitivity on $S^*$, to make sure we're not missing any elements of $T$.  Pick another two points $(x, x+2), (x+2, x+4) \in S^*$, with $0.  These elements cannot be in $T$ because they lie outside $0 < x < 1$.  One checks this covers all transitivity possibilities.

Summarizing: $T = \{(x, y) \verb| | \vert \verb| | y - x = 0\} \cup \{(x, y) \verb| | \vert \verb| | y = x + 1, 0 < x < 2\} \cup \{(x, y) \verb| | \vert \verb| | y = x - 1, 1 < x < 3\} \cup \{(x, y) \verb| | \vert \verb| | y = x + 2, 0 < x < 1\} \cup \{(x, y) \verb| | \vert \verb| | y = x - 2, 2 < x < 3\}$.

The equivalence classes: for $-\infty < x \leq 0$ and $3 \leq x < \infty$, each equivalence class has $x$ as its single element. $\{1, 2\}$ belong to an equivalence class. Elements $0 < x < 1$ belong to a 3-member equivalence class, $\{x, x+1, x+2\}$.

Categories: