The Pasqualian

1.4 Exercise 1

June 19th, 2009

No comments

Omigod, this was a kilometric problem, and kind of boring too. I guess once in a lifetime every mathematician (or schoolboy) should go ahead and get his hands dirty proving identities only using axioms. Here goes, although I’ll complete this problem five letters at a time (until I reach the end), over the span of a few days.

“Prove the following laws of algebra for $\mathbb{R}$ , using only the following axioms (I)-(V):

Algebraic Properties of the Reals

I. $(x + y) + z = x + (y+z)$ , $(x \cdot y) \cdot z = x \cdot (y \cdot z)$ for all $x, y, z$ in $\mathbb{R}$ .

II. $x + y = y + x$ $x \cdot y = y \cdot x$ for all $x, y$ in $\mathbb{R}$ .

III. There exists a unique element of $\mathbb{R}$ called zero, denoted by 0, such that $x+0=x$ for all $x \in \mathbb{R}$ . There exists a unique element of $\mathbb{R}$ called one, different from 0 and denoted by 1, such that $x \cdot 1 = x$ for all $x \in \mathbb{R}$ .

IV. For each $x$ in $\mathbb{R}$ , there exists a unique $y$ in $\mathbb{R}$ such that $x+y=0$ . For each $x$ in $\mathbb{R}$ different from 0, there exists a unique $y$ in $\mathbb{R}$ such that $x \cdot y = 1$ .

V. $x \cdot (y+z) = (x \cdot y) + (x \cdot z)$ for all $x, y, z \in \mathbb{R}$ .

—–

(a) If $x+y = x$ , then $y = 0$

(b) $0 \cdot x = 0$ [Hint: Compute $(x+0)\cdot x$ ]

(d) $-(-x) = x$

(e) $x(-y) = -(xy) = (-x)y$

(f) $(-1)x = -x$

(g) $x(y-z) = xy - xz$

(h) $-(x+y) = -x -y; -(x-y) = -x + y$

(i) If $x \neq 0$ and $x \cdot y = x$ , then $y = 1$

(j) $x/x = 1$ if $x \neq 0$

(k) $x/1 = x$

(l) $x \neq 0$ and $y \neq 0$ , then $xy \neq 0$

(m) $(1/y)(1/z) = 1/(yz)$ if $y, z \neq 0$

(n) $(x/y)(w/z) = (xw)/(yz)$ if $y, z \neq 0$

(o) $(x/y) +(w/z) = (xz + wy)/(yz)$ if $y, z \neq 0$

(p) $x \neq 0 \Rightarrow 1/x \neq 0$

(q) $1/(w/z) = z/w$ if $w, z \neq 0$

(r) $(x/y)/(w/z) = (xz)/(yw)$ if $y, w, z \neq 0$

(s) $(ax)/y = a(x/y)$ if $y \neq 0$

(t) $(-x)/y = x/(-y) = -(x/y)$ if $y \neq 0$ “

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

——-

SOLUTION

(a)

1.4.1.a

(b)

1.4.1.b

(c)

1.4.1.c

(d)

1.4.1.d

(e)

First we show the first equality.

1.4.1.e.I

Now the second equality.

1.4.1.e.II

Finally, by transitivity of equality, since $x(-y) = -(xy)$ and $-(xy) = (-x)y$ , it follows that $x(-y) = (-x)y$ .

(f)

1.4.1.f

(g)

1.4.1.g

(h)

First we show the first equation.

1.4.1.h.I

Now the second.

1.4.1.h.II

(i)

1.4.1.i

(j)

1.4.1.j

(k)

1.4.1.k

(l)

Suppose otherwise, that $x y = 0$ . Then:

1.4.1.l

contradicts the fact that $y$ is nonzero. Thus, $x y \neq 0$ holds.

(m)

1.4.1.m

(n)

With $z \neq 0, y \neq 0$ ,

1.4.1.n

(o)

With $y \neq 0, z \neq 0$ ,

1.4.1.o

(p)

Suppose otherwise, and $\frac{1}{x} = 0$ . But then:

1.4.1.p

and this contradicts Axiom III.

(q)

1.4.1.q

(r)

1.4.1.r

(s)

1.4.1.s

(t)

This is true by Part (e), using compact notation.

\subsubsection[Exercise 1]{Prove the following “laws of algebra” for $\mathbb{R}$, using only the following axioms (I)-(V): \newline

\emph{Algebraic Properties of the Reals} \newline

I. $(x + y) + z = x + (y+z)$, \newline

$ (x \cdot y) \cdot z = x \cdot (y \cdot z) $ for all $x, y, z$ in $\mathbb{R}$. \newline

II. $ x+y = y+x $ \newline

$x \cdot y = y \cdot x$ for all $x, y$ in $\mathbb{R}$. \newline

III. There exists a unique element of $\mathbb{R}$ called \emph{zero}, denoted by 0, such that $x+0=x$ for all $x \in \mathbb{R}$. \newline

There exists a unique element of $\mathbb{R}$ called \emph{one}, different from 0 and denoted by 1, such that $x \cdot 1 = x$ for all $x \in \mathbb{R}$. \newline

IV. For each $x$ in $\mathbb{R}$, there exists a unique $y$ in $\mathbb{R}$ such that $x+y=0$. \newline For each $x$ in $\mathbb{R}$ different from 0, there exists a unique $y$ in $\mathbb{R}$ such that $x \cdot y = 1$. \newline

V. $x \cdot (y+z) = (x \cdot y) + (x \cdot z)$ for all $x, y, z \in \mathbb{R}$. \newline \newline

(a) If $x+y = x$, then $y = 0$ \newline

(b) $0 \cdot x = 0$ [Hint: Compute $(x+0)\cdot x$] \newline

(d) $-(-x) = x$ \newline

(e) $x(-y) = -(xy) = (-x)y$ \newline

(f) $(-1)x = -x$ \newline

(g) $x(y-z) = xy – xz$ \newline

(h) $-(x+y) = -x -y; -(x-y) = -x + y$ \newline

(i) If $x \neq 0$ and $x \cdot y = x$, then $y = 1$ \newline

(j) $x/x = 1$ if $x \neq 0$ \newline

(k) $x/1 = x$ \newline

(l) $x \neq 0$ and $x \cdot y = x$, then $y = 1$ \newline

(m) $(1/y)(1/z) = 1/(yz)$ if $y, z \neq 0$ \newline

(n) $(x/y)(w/z) = (xw)/(yz)$ if $y, z \neq 0$ \newline

(o) $(x/y) +(w/z) = (xz + wy)/(yz)$ if $y, z \neq 0$ \newline

(p) $x \neq 0 \Rightarrow 1/x \neq 0$ \newline

(q) $1/(w/z) = z/w$ if $w, z \neq 0$ \newline

(r) $(x/y)/(w/z) = (xz)/(yw)$ if $y, w, z \neq 0$ \newline

(s) $(ax)/y = a(x/y)$ if $y \neq 0$ \newline

(t) $(-x)/y = x/(-y) = -(x/y)$ if $y \neq 0$}

(a)

\newline \newline

\begin{eqnarray*}

-x + x + y & = & -x + x \verb| |\textrm{Additive Prop. of Eq.} \\

0 + y & = & 0 \verb| |\textrm{Axiom IV} \\

y & = & 0 \verb| |\textrm{III}

\end{eqnarray*} \newline \newline

(b)

\newline \newline

\begin{eqnarray*}

(x+0)x & = & x \cdot x + x \cdot 0 \verb| |\textrm{Hint, V} \\

x \cdot x & = & x \cdot x + x \cdot 0 \verb| |\textrm{III} \\

(-x \cdot x) + x \cdot x & = & (-x \cdot x) + x \cdot x + x \cdot 0 \verb| |\textrm{Additive Prop. of Eq.} \\

0 & = & 0 + x \cdot 0 \verb| |\textrm{IV} \\

0 & = & x \cdot 0 \verb| |\textrm{III} \\

x \cdot 0 & = & 0 \verb| | \textrm{Symmetric Prop. of Eq.}

\end{eqnarray*} \newline \newline

(c)

\newline \newline

\begin{eqnarray*}

0 + (-0) & = & 0 \verb| |\textrm{IV} \\

(-0) + 0 & = & 0 \verb| |\textrm{II} \\

-0 & = & 0 \verb| |\textrm{III}

\end{eqnarray*} \newline \newline

(d)

\newline \newline

\begin{eqnarray*}

x + (-x) & = & 0 \verb| |\textrm{IV} \\

x + (-x) + -(-x) & = & 0 + -(-x) \verb| |\textrm{Additive Prop. of Eq.} \\

x + 0 & = & -(-x) \verb| |\textrm{IV, III} \\

x & = & -(-x) \verb| |\textrm{III} \\

-(-x) & = & x \verb| |\textrm{Symmetric Prop. of Eq.}

\end{eqnarray*} \newline \newline

(e)

\newline \newline

First we show the first equality.

\begin{eqnarray*}

x \cdot 0 & = & 0 \verb| |\textrm{Part (b)} \\

x (y + -y) & = & 0 \verb| |\textrm{IV} \\

xy + x(-y) & = & 0 \verb| |\textrm{V} \\

-(xy) + xy + x(-y) & = & -(xy) + 0 \verb| |\textrm{Additive Prop. of Eq.} \\

0 + x(-y) & = & -(xy) \verb| |\textrm{IV, III} \\

x(-y) & = & -(xy) \verb| |\textrm{II, III}

\end{eqnarray*}

Now the second equality.

\begin{eqnarray*}

y \cdot 0 & = & 0 \verb| |\textrm{Part (b)} \\

y (x + -x) & = & 0 \verb| |\textrm{IV} \\

yx + y(-x) & = & 0 \verb| |\textrm{V} \\

xy + (-x)y & = & 0 \verb| |\textrm{II} \\

-(xy) + xy + (-x)y & = & -(xy) + 0 \verb| |\textrm{Additive Prop. of Eq.} \\

0 + (-x)y & = & -(xy) \verb| |\textrm{IV, III} \\

(-x)y & = & -(xy) \verb| |\textrm{II, III} \\

-(xy) & = & (-x)y \verb| |\textrm{Symmetric Prop. of Eq.}

\end{eqnarray*}

Finally, by transitivity of equality, since $x(-y) = -(xy)$ and $-(xy) = (-x)y$, it follows that $x(-y) = (-x)y$

Carlos Munkres's Topology, Set Theory and Logic, The Integers and the Real Numbers

1.3 Exercise 15

June 18th, 2009

No comments

Yes, after months, I’m back ;-). This was an interesting problem to me because it explores a bit more deeply the concept of the LUBP.

“Assume that the real line has the least upper bound property.

(a) Show that the sets $[0,1] = \{x \ \vert \ 0 \leq x \leq 1\}$ and $[0,1) = \{x \ \vert \ 0 \leq x < 1\}$ have the least upper bound property.

(b) Does $[0, 1] \times [0, 1]$ in the dictionary order have the least upper bound property? What about $[0,1] \times [0, 1)$ ? What about $[0,1) \times [0,1]$ ?”

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

——-

SOLUTION

(a)

Pick any nonempty $A_0 \subset [0,1]$ , bounded above in $[0,1]$ . Note that $A_0 \subset [0,1] \subset \mathbb{R}$ , and so $A_0 \subset \mathbb{R}$ , by transitivity of inclusion (a partial order axiom). Since $\mathbb{R}$ has the LUBP (by assumption), the set of upper bounds of $A_0$ (in $\mathbb{R}$ ), say $[b, \infty)$ , has a least upper bound, namely $b$ . Restricted to $A = [0,1]$ , the upper bounds are $[b, \infty) \cap [0, 1] = [b, 1]$ , and $b$ is still the LUB in $A$ . It follows that all nonempty subsets that are bounded above in $A$ have a least upper bound in $A$ , and $A$ has the LUBP. Following the exact same recipe works with all nonempty subsets of $A' = [0,1)$ that are bounded above. As a point of clarification, notice that the set $A_0' = A' = [0, 1)$ is not bounded above in $A'$ , and so it is not an impediment to the base set $A'$ having the LUBP.

(b)

Yes, $[0, 1] \times [0, 1]$ in the dictionary order have the least upper bound property. Pick any nonempty subset of $A = [0, 1] \times [0, 1]$ that is bounded above, as the interval $(x_1 \times y_1, x_2 \times y_2)$ , $[x_1 \times y_1, x_2 \times y_2)$ , $(x_1 \times y_1, x_2 \times y_2]$ , xor $[x_1 \times y_1, x_2 \times y_2]$ with $x, y \in [0,1]$ of course. For all these, the set of upper bounds are $[x_2 \times y_2, 1 \times 1]$ , and the LUB is $x_2 \times y_2$ .

No, $[0,1] \times [0, 1)$ does not have the LUBP (in the dictionary order). We need only show a counterexample: take the interval $(x_1\times y_1, x_1 \times 1)$ (nonempty, bounded above) with $x \in [0, 1]$ and $y \in [0, 1)$ . The set of upper bounds is $(x_1 \times 0, 1 \times 1)$ , and this clearly has no smallest element. In other words, by picking the smallest upper bound one could think of, say $x_2 \times 0$ , the idea is that one can always come up with a (strictly) smaller one, say $\frac{x_2}{2} \times 0$ .

Yes, $[0,1) \times [0,1]$ has the LUBP (in the dictionary order). Pick any nonempty subset of $A = [0, 1) \times [0, 1]$ that is bounded above, as the interval $(x_1 \times y_1, x_2 \times y_2)$ , $[x_1 \times y_1, x_2 \times y_2)$ , $(x_1 \times y_1, x_2 \times y_2]$ , xor $[x_1 \times y_1, x_2 \times y_2]$ with $x \in [0, 1)$ and $y \in [0, 1]$ . For all these, $x_2 \times y_2$ is the LUB, since it’s included in the upper bound set and it is its least element.

Carlos Munkres's Topology, Order Relations, Relations, Set Theory and Logic

Busy People

June 17th, 2009

No comments

People…. mYsTiFy. Some I don’t get.

They act like we’ve never met.

They’ve plans, their afternoons are set.

They work, in their sleep they fidget.

Heart disease? They’ll go ahead and fret.

It’s about their office and their mile-high docket.

“Hello! Sorry, I’ve got to jet!”

Or, they’ll stare through their socket,

Eyes angry, eyes wet,

their pens on their desk going tet-tet-tet.

Get out, like a rocket!

They’ve a gun in their pocket!

It doesn’t seem they will let,

nor go fishing, cast a net,

chillax, get a pet

and take it to the vet.

Shet.

Carlos Miscellaneous, Poetry

On the Swine Flu

April 27th, 2009

5 comments

So I’ve been MIA for the last month-and-a-half because of several exciting things that have happened to me, and I apologize for the hiatus… but it may be prolonged for a while still. However, in the meantime, since a lot of my Mexican colleagues and students have been asking me about the swine flu, in somewhat of a panic, I thought I would try to put some numbers into some well-known SIR equations and see what insights can be obtained regarding the dynamics and proportions of the purported epidemic. I believe this kind of analysis is routine in CDC in the US and in Secretaria de Salud in Mexico, although I’m not too sure how mathematically equipped the latter institution is in my home country. In much of what follows, I have to do some hand-waving because of the unavailability of accurate information in the web-o-sphere, or my inability to access true statistics. Much of what I know I got from CNN and NYTIMES reports of today. I find such fuzzy math unacceptable, personally, except to derive a notion of the magnitude of a problem, and so it would be a mistake to take the calculations as set fact or hard evidence. Caveat in mind, I don’t derive the model (it’s up to the reader to find several excellent sites that might explain it), but instead delve to account for my assumptions and my results.

The SIR model (Susceptibles-Infecteds-Recovereds) uses coupled differential equations to analyze the progress of a disease in a closed population. I focus on the population of Mexico City, assuming that the count of infected individuals nationally can be mostly found there. Thus, out of Mexico City’s 20 million people, most of the suspected 1600 currently-infecteds are in that city (all for simplicity). Recovered individuals are the sum of those dead (149) plus those that did not die. The coupled time-differential equations are:

$\frac{dS}{dt} = -a S I$

$\frac{dR}{dt} = b I$

$\frac{dI}{dt} = a S I - b I$

which basically says that the change in susceptible individuals is proportional to the amount infected and the amount currently susceptible, that the change in recovereds (removed from infection) is proportional to those who are already infected, and that the change in infecteds depends is the rate at which susceptibles get sick minus the rate at which infecteds get removed from the population. The proportionality constants can be calculated with some cleverness (though not necessarily accuracy), like this:

$a = \frac{-\frac{dS}{dt}}{S I}$

and so we must guesstimate $\frac{dS}{dt}$ as well as $S$ and $I$ . If there are currently 1600 individuals that are infected, linearly, 400 have been infected per day since this became news four days ago. So my guesstimate is that the current rate $\frac{dS}{dt} = -400$ individuals per day. The number of susceptibles is the population of Mexico City, so all 20 million, minus infecteds, about (I’m thinking naturally immune individuals are so few that the population number doesn’t change much). Finally, the number of current infecteds (Mexico-wide? focused in Mexico City) is 1600 according to the NYTIMES article I’ve been linking to. This gives a value of $a = 1.25 \times 10^{-8}$ . Calculating $b$ is a bit trickier. The datum says that 149 people have died from the swine flu, but I don’t think all people infected with the swine flu die. I’m going to guesstimate that approximately 20% of the infecteds either die or recover (since apparently 10% of them die) in a day. There’s no reason for this except my hunch. So $b \approx .2$ .

By the chain rule, $\frac{dI}{dt} = \frac{dI}{dS} \cdot \frac{dS}{dt}$ , and so $\frac{dI}{dS} = \frac{\frac{dI}{dt}}{\frac{dS}{dt}}$ . With $I$ not zero, this means

$\frac{dI}{dS} = \frac{1.25 \times 10^{-8} S I - 0.2 I}{-1.25 \times 10^{-8} S I} = -1 + \frac{16,000,000}{S}$ . The partial is zero at $S_* = 16,000,000$ , and has initial conditions $S_0 = 19,998,400$ and $I_0 = 1600$ (twenty million total).

The value $S_*$ is called the threshold value, and it is less than the initial condition $S_0 \approx 20,000,000$ . This suggests an epidemic in fact occurs.

Luckily, $\frac{dI}{dS}$ can be solved in closed form, as

$I = -S + 1.6 \times 10^{7} ln(S) + C$ .

The value of $C$ is of course determined by the initial conditions, as $C = I_0 + S_0 - 1.6 \times 10^7 ln(S_0) \approx -2.489 \times 10^8$ . Then

$I = -S + 1.6 \times 10^7 ln (S) - 2.489 \times 10^8$ .

With this in mind, the maximum number of infecteds at a time occurs at $S_* = 16,000,000$ and is

$I_* \approx 500,000$ ,

or about half a million people, equivalent to about 2.5% of Mexico City’s population.

If there is enough interest, I may calculate the time dynamics (how long the epidemic lasts, etc.) with numerical methods (as by Euler’s method), unfortunately by hand since access to fast computers and cool software is limited to me at present.

——

UPDATE May 5, 2009.

So it appears that the foundational numbers above were vastly overstated (since Mexico hadn’t confirmed the particular strains of the alleged infecteds due to under-equipment): from the number of actual infecteds to the actual number of deaths related to the illness. It now appears that the progression of the swine flu is a lot slower, and also that our derived coefficients are vastly different than originally thought. Still, a happy exercise using the SIR equations. I may yet post a new derivation that reflects reality more truly.

Carlos Differential Equations, Mathematics

1.3 Exercise 14

March 11th, 2009

No comments

Rather than merely repeating the proof of 1.3.13 to show the converse, we can impose the “opposite” or symmetric order relation on the set $A$ to show that if it has the GLBP then it has the LUBP too.

“If $C$ is a relation on a set $A$ , define a new relation $D$ on $A$ by letting $(b, a) \in D$ if $(a,b) \in C$ .

(a) Show that $C$ is symmetric if and only if $C = D$ .

(b) Show that if $C$ is an order relation, $D$ is also an order relation.

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

——

SOLUTION

(a)

$C = D \Rightarrow C \textrm{ is symmetric}$ .

Pick any $a, b \in A$ . Suppose $(a, b) \in C$ : this implies $(b, a) \in D$ . Since $C = D$ , all elements of $D$ are also in $C$ . Thus $(b, a) \in C$ , and $C$ is symmetric.

$C \textrm{ is symmteric} \Rightarrow C = D$ .

Pick $a, b \in A$ so that $(a, b) \in C$ . Also $(b, a) \in C$ by symmetry of $C$ . Now, $(a, b) \in C \Rightarrow (b, a) \in D$ , and also $(b, a) \in C \Rightarrow (a, b) \in D$ , and $D$ is symmetric. Thus, we have the implication that $(a, b) \in C \Rightarrow (a, b) \in D$ via its symmetric partner, and $C = D$ : $C \subset D$ because all elements of $C$ are in $D$ , and $D \setminus C$ is empty because we’re carbon-copying the elements of $C$ into $D$ and $D$ was otherwise empty.

(b)

$C \textrm{ an order relation} \Rightarrow D \textrm{ an order relation}$ .

Comparability. For $a, b \in A$ , either $(a, b) \in C$ or $(b, a) \in C$ $\Rightarrow (b, a) \in D$ or $(a, b) \in D$ . Thus, $D$ inherits comparability.

Nonreflexivity. For all $a \in A$ , $(a, a) \notin C$ . Since such is not in $C$ , it could not have been generated in $D$ . Thus, $(a, a) \notin D$ , and $D$ inherits nonreflexivity.

Transitivity. For $a, b, c \in A$ such that $(a, b), (b, c), (a, c) \in C$ , where the presence of the first two implies the presence of the third. Next, we follow the implication for generating elements in set $D$ : $(b, a), (c, b), (c, a) \in D$ . Rearranging, $(c, b), (b, a), (c, a) \in D$ , and $D$ is transitive because the presence of the first two implied the presence of the third (via $C$ ).

(c)

First of all, if part (b) holds and $C \textrm{ order relation } \Rightarrow D \textrm{ order relation}$ , then $C$ is not symmetric (since if both $(x, y), (y, x) \in C$ , then $(x, x) \in C$ by transitivity, contradicting nonreflexivity). Then, $C$ not symmetric implies $C \neq D$ by contrapositive of part (a). We’ve shown that we’re talking about two different order relations.

Say $A$ has the LUBP $\Rightarrow$ GLBP, ordered as $C$ . This means that for any nonempty $A_0 \subset A$ bounded above, the set of upper bounds, $B \subset A$ , has a least element, say $b$ , so that $b \leq x \in B$ and $b \geq y \in A_0$ . In particular, this means $(b, x) \in C$ xor $b = x$ for all $x \in B$ and $(y, b) \in C$ xor $y = b$ for all $y \in A_0$ . Additionally, since the LUBP implies the GLBP, for any nonempty set $A_1 \subset A$ bounded below, the set of lower bounds, $B' \subset A$ , has a greatest element, $b' \geq x' \in B'$ , and $b' \leq y' \in A_1$ . This means $(x', b') \in C$ xor $x' = b'$ for all $x' \in B'$ and $(b', y') \in C$ xor $y' = b'$ for all $y' \in A_1$ .

Now impose on $A$ , instead of $C$ , the order relation $D$ which is different. Following the implication for generating elements in this new order relation, $(x, b) \in D$ xor $x = b$ , for all $x \in B$ and $(b, y) \in D$ xor $b = y$ for all $y \in A_0$ . Thus, $b$ is a greatest lower bound. Also, $(b', x') \in D$ xor $b' = x'$ for all $x' \in B'$ , and $(y', b') \in D$ xor $b' = y'$ for all $y' \in A_1$ . Thus $b'$ is a least upper bound. Hence, if the set $A$ has the GLBP, it has the LUBP, as we wanted to show.

Carlos Munkres's Topology, Order Relations, Relations, Set Theory and Logic

1.3 Exercise 13

March 2nd, 2009

No comments

This theorem (and its converse) is needed everywhere in analysis and topology, and it is very important.

“Prove the following:

Theorem. If an ordered set $A$ has the least upper bound property, then it has the greatest lower bound property.”

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

—–

SOLUTION

Suppose that $A$ does not have the GLBP. This means that there exists a nonempty $A_0 \in A$ that is bounded below but does not have a greatest lower bound, so that the set of lower bounds $B_l \in A$ (nonempty) does not have a largest element. Additionally, $A_0$ does not have a smallest element, for, if it did, this would in fact be its infimum (such an element would be in the set of lower bounds because it is lesser or equal to all elements of $A_0$ ). Next let’s focus on $B_l$ , which is a set in $A$ as well. It cannot possibly have the LUBP, because it has no greatest element and because $A_0$ , which now bounds it above, has no smallest element. We found a nonempty subset of $A$ with no supremum, and we’ve proved the theorem by contrapositive.

Carlos Munkres's Topology, Order Relations, Relations, Set Theory and Logic

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:

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.

Carlos Munkres's Topology, Order Relations, Relations, Set Theory and Logic

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.

Carlos Order Relations, Relations, Set Theory and Logic, Textbooks

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:

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.

Carlos Munkres's Topology, Order Relations, Relations, Set Theory and Logic

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.