The Pasqualian

A Shakesperean Sonnet for Lucinda on her Birthday

January 27th, 2010

No comments

All stars do sparkle silently in the sky
While cinders twinkle quite sonorously
Our hearts beat likewise bum-ba-bum oh my!
And don’t we breathe (tis true!) pulsatingly?
The tide may rise and it may fall again
And night does turn to day as time goes by
The moon herself does wax and then go wane
Things cycle and we don’t know really why.
With spirit we go forth to try succeed
Succumb to failure that we stand once more
We want to be just hugged in time of need
And hug in turn rememb’ring yester yore.
Your beauty and your charm, Lucinda dear
Do not ebb since you’re linda year to year.

Carlos Miscellaneous, Poetry

On Mental Arithmetic

October 29th, 2009

No comments

So the other day one of my students came up to me in semi-awe asking me how its possible for me to do rapid multiplications in my head. He’s seen me do two digit and rarely three digit computations in my head, before I resort to using the calculator (I get lazy too!). ”In fact,” he’s asked me, “why don’t you do all sorts of computations in your head without the use of electronic aids?” He was implying of course that as a mathematician I should have a strange power to multiply numbers instantaneously and with no effort. I chuckled. If he only knew that in my years as a mathematician I seldom even see numbers or do arithmetic at all! The tricks I know I’ve picked up by myself or invented them as I’ve needed them, particularly or especially when I’m teaching high schoolers and university students like himself (and the calculator not being within reach)!

I’ve become convinced that the most efficient way to multiply numbers instantaneously and with little effort is to simply memorize the lists of two, three, and even four digit multiplication tables. Indeed, wouldn’t it be a lot easier to just “know” that 1331 times 11 is 14,641, than to actually grab paper and pencil and physically do it (or use another method for mental calculation that requires considerable thinking)? It is exactly this, after all, which we ask youngsters to do: memorize the multiplication tables of 2 through 9 (rarely up to 20), or the multiplication of two identical numbers (squares). This can however become time-consuming; we don’t want our children to spend their lives learning to immediately recall that 123 times 321 is 39,483. Nevertheless, I bet my bottom dollar that this is exactly what some TV people do, including savants, who indeed may have additional powers of retention (as a photographic memory) and the intention and attention to do so: to “quickly” or instantaneously multiply any two (large) numbers (really, recall their product from memory than do any computation at all).

One is taught of course the usual algorithm to multiply two (any) numbers that involves putting the largest on top and the smallest on the bottom, then taking the units digit of the second number, multiplying through digit by digit and making sure to account for all carry digits, including a zero at the units position in the next row and doing the same with the second digit, etc etc. This algorithm of course requires sparse knowledge, only the multiplication tables of 2 through 9. However the tradeoff is that this method is a bit time consuming, and often requires paper and pencil.

But by the time a student comes to learning special products, one is not told “use these rules to multiply numbers more easily.” One is instead introduced to the (very boring) topic of multinomials (usually binomials) and how we go about obtaining their product. It is up to the student to smart up and think, “hey, this is immensely applicable to mental arithmetic, too,” and few people can synthesize and apply such information solely on their own. Usually one is never “told” that to multiply 17 times 23 one can imagine it as the binomial product of (10 + 7) and (20 + 3) and “FOIL” it in one’s head, which is a lot easier to do than envision what one would do with paper and pencil following the usual algorithm (and having to keep track of the carry digits and the “shifted” rows, for example). I can easily multiply 10 times 20 (two-hundred), 10 times 3 (thirty), 7 times 20 (one-forty), and 7 times 3 (twenty-one), and then add that up if I can retain those numbers to obtain 391 (which, incidentally, is exactly what we do with the usual paper-and-pencil algorithm anyway… except harder, and hence why we need paper and pencil: we split the second number into an addition of tens, hundreds, thousands, etc, then we distribute the first number on the explicit sum, and then sum!). There are some binomial products that are easier to calculate mentally than others, case depending. For example, I could have split 17 times 23 into (20-3) and (20+3), which, one recalls, is 400-9=391 if we use the so-called difference of squares, and more easy to compute than by FOILing as above. To recognize such patterns takes some fine-tuning, but not too long. Some people become really really good at it, and it’s often what I do when I multiply two numbers in my head without a calculator.

There is another little trick that I thought up while working out some arithmetic problems with my students but I never really made conscious nor explicit (until now, that is), and I’m sure we all do the same, for example when counting money. It is this: rather than multiplying two large numbers, sometimes it’s easier to just divide. Say you have 500 peso bills and you’ve got 32 of them. Since 500 is half of 1000, it follows that I should get half of 32000, which is 16000. Like this:

$500 \cdot 32 = \frac{1000}{2} \cdot 32 = 1000 \cdot \frac{32}{2} = 1000 \cdot 16 = 16000$

This nifty trick is immensely powerful! Let me restate it here: multiplying by five (fifty, five-hundred, five-thousand) is in fact very much like dividing by two. The reason is that $5$ and $.5 = \frac{1}{2}$ are related. So now it is really easy to multiply, say, 5 times 132 without much effort. Rather than multiplying times five, simply divide the second number by two and then multiply by ten to obtain 610. The reason is this:

$5 \cdot 132 = (.5 \cdot 10) \cdot 132 = \frac{1}{2} \cdot 10 \cdot 132 = \frac{132}{2} \cdot 10 = 61 \cdot 10 = 610$

Of course, it is very much helpful that the second number is divisible by two. In much the same manner, multiplying by 25 (250, 2500, 25000, etc) is akin to dividing by 4. Say you have 25 times 32. The second number is divisible by 4, so dividing 32 by 4 gives 8. Next multiply by 100, to obtain 800. Here it is explicitly:

$25 \cdot 32 = (.25 \cdot 100) \cdot 32 = \frac{1}{4} \cdot 32 \cdot 100 = \frac{32}{4} \cdot 100 = 8 \cdot 100 = 800$

Of course it helps that the second number given was divisible by 4. It need not be, but one has to deal with the decimal representation of the ensuing fraction.

Next, say we have 75 times 32. Multiplying by 75 (750, 7500, etc) is similar to multiplying by 3 and then dividing by four (or first dividing by four and then multiplying by three). So 75 times 32 is really 8 times 3 times 100, or 2400:

$75 \cdot 32 = .75 \cdot 100 \cdot 32 = \frac{3}{4} \cdot 32 \cdot 100 = 3 \cdot 8 \cdot 100 = 2400$

Seventy five times a number that is divisible by four is especially easy to calculate this way.

In much the same manner:

Multiplying by 125 is similar to dividing by 8. So numbers that are divisible by 8 are especially simple to multiply by 125. For example, 125 times 88 is 11,000. (Why?) Also, if the second number is divisible by four, you can divide by four and then multiply by five. For example, 125 times 44 is 5,500. If the second number is divisible by 2, then you can divide by 2 and multiply by 25 (which in turn is like a division by four). So 125 times 18 is 2,250. Just make sure you keep track of the multiplication by factors of ten.
Multiplying by 375 is similar to dividing by 8 and then multiplying by 3. Numbers divisible by 8 are especially simple to multiply by 375. For example, 375 times 64 is 24,000. (Why?) Like above, there’s more that can be said here.
Multiplying by 625 is like dividing by 8 and then multiplying by 5. Again, numbers divisible by 8 are especially simple to compute. Say 625 times 56 is 35,000. (Make sure you see this.)
Multiplying by 875 is like dividing by 8 and then multiplying by 7. Say 875 times 24 is 21,000. (Yeah?)

As you may notice, multiplying by any multiple of twenty-five is like dividing by four or by eight (and then multiplying by a usually small compensator). Also notice that multiplying by any multiple of five is like dividing by two and then compensating with a multiplication. When I’ve had to multiply three-digit numbers, this is usually the pattern that I follow (for numbers that are multiples of 5 or 25, I’ve been lucky with my students), and that’s how my students are wowed. Neat-o. Can you think of patterns that arise that might involve divisions by three? By six? By seven? By eleven? Fractions involving these numbers in the denominator usually imply a repeating decimal, so. Hmm. Maybe it’s not so clear? Let me know what you think!

Carlos Arithmetic

On Utilities Consumption I: Water

October 27th, 2009

2 comments

So more or less since I came back to Mexico I’ve been saving my water bills, just for fun. ”Eventually,” I thought to myself, “I may be able to do something with them.” Of course by that I meant that sixty years later I would have enough data points to discern some fascinating trends, including those detailing draughts and relative water abundance, and I would absolutely be able to use Viterbi algortithms or some Markovian insight to predict next year’s weather, oh, and the price of potable water. I’m the impatient kind, and have accumulated only about four (sometimes five) year’s worth of data. Here it is; I have plotted my cubic-meter consumption on a month-to-month basis (the bills come in monthly). I’ve assumed that I use the water that I need. Also that the trends represent a fairly typical (there may be some argument here, I predict) three-person household consumption (I don’t live alone). And yes, admittedly, sometimes there are sisterly visits in December and there’s that factor to take into account, but oh well! Let’s just hypothesize my water consumption is fairly typical for a 3 or 4 person household in this geographical region in Mexico, shall we?

I’ve plotted the average consumption, and the two-sigma 95% bounds I calculated using Bessel’s correction of the standard deviation for samples, aka “sample standard deviation”: $\sqrt{\frac{1}{N-1}\sum_{i=1}^{N}\left(x_i - \overline{x} \right)^2 }$ . The correction gives an unbiased variance, even though the standard deviation is slightly underbiased… not that it matters much anyway.

water

An interesting detail is that September seems to me the more precise. My friend Ben objects to my use of the word “precise” in such a way. He’s a physicist. He pointed out to me that what I meant was variance. He kept going on about how precision applies to instrumentation, and how the readings would have a precision estimate that would be reported alongside. I countered that it probably did have an implied precision, because the measure is (surely) to significant figures, and so, a reading of 34, really meant anywhere between 33 and 35, as per the usual rules. Also, I told him his interpretation of precision did not matter in this my particular case. A not so interesting debate ensued, culminating in our agreeing that precision is dependent on context. My argument was that if my monthly data points represent estimates of an “actual” (fictitious) consumption for that month, then indeed my spread indicates precision (where accuracy would indicate how close I came to the “actual” consumption). Anyway. The debate was illuminating in some ways, but banal in many others.

The wide fluctuation in March-April was probably due to a small leak I had in 2008 that I corrected immediately, although I did interpolate some values that were missing for 2007 and 2008 right around that time too. I’m estimating my consumption for October to be about 15 cubic meters, the (unbiased) sample (arithmetic) average for that month.

Carlos General Applied Statistics

1.4 Exercise 5

October 10th, 2009

No comments

I had often wondered how to go about proving closure of addition and multiplication of the integers. After this problem I wondered no more! It’s pretty neat that we can show (by using induction) that by adding any two integers or multiplying them you always get another integer.

“Prove the following properties of $\mathbb{Z}$ and $\mathbb{Z}_+$ :

(a) $a, b \in \mathbb{Z}_+ \Rightarrow a+b \in \mathbb{Z}_+$ . [Hint: Show that given $a \in \mathbb{Z}_+$ , the set $X = \{x \ | \ x \in \mathbb{R}$ and $a+x \in \mathbb{Z}_+\}$ is inductive.]

(b) $a, b \in \mathbb{Z}_+ \Rightarrow a \cdot b \in \mathbb{Z}_+$ .

(c) Show that $a \in \mathbb{Z}_+ \Rightarrow a - 1 \in \mathbb{Z}_+ \cup \{0\}$ . [Hint: Let $X = \{x \ | \ x \in \mathbb{R}$ and $x - 1 \in \mathbb{Z}_+ \cup \{0\}$ ; show that $X$ is inductive.]

(d) $c, d \in \mathbb{Z} \Rightarrow c + d \in \mathbb{Z}$ and $c - d \in \mathbb{Z}$ . [Hint: Prove it first for $d = 1$ .]

(e) $c, d \in \mathbb{Z} \Rightarrow c \cdot d \in \mathbb{Z}$ .”

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

—-

SOLUTION

(a)

Using the hint, we proceed by

Showing $1 \in X$ . Since $a \in \mathbb{Z}_+$ , and $\mathbb{Z}_+$ is inductive, it follows that $a + 1 \in \mathbb{Z}_+$ . Therefore $1 \in X$ .
Supposing $k \in X$ . This of course means $a + k \in \mathbb{Z}_+$ .
Showing $k+1 \in X$ . This would mean $a + (k + 1) \in \mathbb{Z}_+$ . Note that by commutativity and associativity (of the reals, of the integers), we can state $(a + 1) + k$ . But then we know that $(a + 1) \in \mathbb{Z}_+$ by the first point, and that $(a+1) + k \in \mathbb{Z}_+$ by the second point. So we conclude that indeed $a + (k + 1) \in \mathbb{Z}_+$ .

Thus $X$ is inductive. In particular, then, $\mathbb{Z}_+ \subset X$ . It follows that if we pick $b \in \mathbb{Z}_+ \subset X$ , with $a \in \mathbb{Z}_+$ by hypothesis, then we are guaranteed $a+b \in \mathbb{Z}_+$ .

(b)

This is proved the same way as before, with a few minor modifications. Again suppose $a \in \mathbb{Z}_+$ . Let $X' = \{x \ | \ x \in \mathbb{R}$ and $a \cdot x \in \mathbb{Z}_+\}$ . Again we want to show that $X'$ is inductive.

$1 \in X'$ , since $a \cdot 1 = a \in \mathbb{Z}_+$ (by identity axiom of the reals).
Assume $k \in X'$ . This means $a \cdot k \in \mathbb{Z}_+$ .
$k + 1 \in X'$ , since $a ( k + 1) = a \cdot k + a$ (by the distributive property axiom of the reals), with $a \in \mathbb{Z}_+$ by the first point and $a \cdot k \in \mathbb{Z}_+$ by the second point. Finally, $a \cdot k + a \in \mathbb{Z}_+$ by what we proved in part (a).

We conclude $X'$ is inductive, and contains $\mathbb{Z}_+$ . As before, with $a \in \mathbb{Z}_+$ , pick $b \in \mathbb{Z}_+ \subset X'$ , and we are guaranteed the product $a \cdot b \in \mathbb{Z}_+$ .

(c)

Again following the hint, we show:

$1 \in X$ . This is because $1 - 1 = 0 \in \mathbb{Z}_+ \cup \{0\}$ is true.
Suppose $k \in X$ , which means that $k - 1 \in \mathbb{Z}_+ \cup \{0\}$ .
We show that $k + 1 \in X$ . This would mean that $(k + 1) - 1 \in \mathbb{Z}_+ \cup \{0\}$ , or, simplifying, that $k \in \mathbb{Z}_+$ , which is true because $k$ is a positive integer by definition.

Thus, $X$ is inductive and $\mathbb{Z}_+ \subset X$ . Picking $a \in \mathbb{Z}_+ \subset X$ , we see that $a - 1 \in \mathbb{Z}_+ \cup \{0\}$ .

(d)

Taking a hint from previous hints (pun intended), assume $c, d \in \mathbb{Z}$ . Next define $X'' = \{ x \in \mathbb{R}; c + x \in \mathbb{Z}$ and $c - x \in \mathbb{Z}\}$ . We want to show that $X''$ is inductive.

$1 \in X''$ . First of all, we want to show that $c + 1 \in \mathbb{Z}$ . Certainly, $c \in \mathbb{Z}_+ \Rightarrow c+1 \in \mathbb{Z}_+ \subset \mathbb{Z}$ by part (a). If $c = 0$ , then $c + 1 = 1 \in \mathbb{Z}_+ \subset \mathbb{Z}$ . If $c \in \mathbb{Z}_-$ , then $c + 1 \Rightarrow -(-c-1)$ with $-c \in \mathbb{Z}_+$ , so $-c-1 \in \mathbb{Z}_+ \cup \{0\}$ by part (c), and $-(-c-1) \in \mathbb{Z}_- \cup \{0\} \subset \mathbb{Z}$ (!). Secondly, we want to show that $c - 1 \in \mathbb{Z}$ . Then, $c \in \mathbb{Z}_+ \Rightarrow c-1 \in \mathbb{Z}_+ \cup \{0\} \subset \mathbb{Z}$ by part (c). If $c = 0$ , $c-1 = -1 \in \mathbb{Z}_- \subset \mathbb{Z}$ . Finally, if $c \in \mathbb{Z}_-$ , then $c - 1$ can be rewritten as $-(-c + 1)$ with $-c \in \mathbb{Z}_+$ , and $-c + 1 \in \mathbb{Z}_+$ by part (a). Then certainly $-(-c+1) \in \mathbb{Z}_- \subset \mathbb{Z}$ . Thus $1 \in X''$ .
Suppose that $k \in X''$ , which means $c + k \in \mathbb{Z}$ and that $c - k \in \mathbb{Z}$ .
We show that $k + 1 \in X''$ . First, $c + (k + 1)$ means, by rearranging (associativity, commutativity) $(c + 1) + k$ . But we know $(c + 1) \in \mathbb{Z}$ by the first point, and so $(c+1) + k \in \mathbb{Z}$ by the second. We conclude that indeed $c + (k + 1) \in \mathbb{Z}$ . Next we show $c - (k+1) \in \mathbb{Z}$ . By the distributive property, $c - k - 1$ . Then by associativity, $(c - 1) - k$ . We know $c - 1 \in \mathbb{Z}$ by the first point, and $(c-1) - k \in \mathbb{Z}$ by the second point. We conclude that indeed $c - (k + 1) \in \mathbb{Z}$ .

Thus, $X''$ is inductive, and importantly, $\mathbb{Z}_+ \subset X''$ . For any integer $c$ , picking an integer $d \in \mathbb{Z}_+ \subset X''$ guarantees that $c + d \in \mathbb{Z}$ and $c - d \in \mathbb{Z}$ . If $d = 0$ , then simply $c \in \mathbb{Z}$ is true by hypothesis. This shows quite thoroughly the closure of addition of the integers!

(e)

Again taking a hint from previous hints, assume $c, d \in \mathbb{Z}$ . Next define $X''' = \{x \ | \ x \in \mathbb{R}$ and $c \cdot x \in \mathbb{Z}\}$ . We want to show $X'''$ is inductive.

$1 \in X'''$ . It seems clear that $c \cdot 1 \in \mathbb{Z}$ , since simplification means $c \in \mathbb{Z}$ , which is true by hypothesis.
We assume that $k \in X'''$ , which means $c \cdot k \in \mathbb{Z}$ .
We show that $k + 1 \in X'''$ . This means we will show that $c (k + 1) \in \mathbb{Z}$ . By the distributive property, $c \cdot k + c$ . Now, we know $c \in \mathbb{Z}$ by the first point, and $c \cdot k \in \mathbb{Z}$ by the second. Thus $c \cdot k + c \in \mathbb{Z}$ by part (d), and indeed $c (k + 1) \in \mathbb{Z}$ .

Thus $X'''$ is inductive and $\mathbb{Z}_+ \subset X'''$ . Having $c \in \mathbb{Z}$ , pick $d \in \mathbb{Z}_+ \subset X'''$ and we are guaranteed that $c \cdot d \in \mathbb{Z}$ . Next, if $d = 0$ , then $c \cdot d = c \cdot 0 = 0 \in \mathbb{Z}$ . If $d \in \mathbb{Z}_-$ , make the negative sign explicit, so that $c \cdot (-d)$ and by the properties of the reals this becomes $-c \cdot d$ with $-c \in \mathbb{Z}$ and $d \in \mathbb{Z}_+$ , which again guarantees the product to be in $\mathbb{Z}$ . We have just proved closure of multiplication of the integers!

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

1.4 Exercise 4

September 10th, 2009

No comments

“(a) Prove by induction that given $n \in \mathbb{Z}_+$ , every nonempty subset of $\{1, \ldots, n\}$ has a largest element.

(b) Explain why you cannot conclude from (a) that every nonempty subset of $\mathbb{Z}_+$ has a largest element.”

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

(a)

Let $A$ be the set of all positive integers for which this statement is true. Then $A$ contains 1, since when $n=1$ the only nonempty subset of $\{1, \ldots, n\} = \{1\}$ is $\{1\}$ , and the element 1 is the largest element because it’s greater than or equal to itself.

Now suppose $A$ contains $n$ , we want to show it contains $n+1$ as well.

Let $C$ be a nonempty subset of $\{1, \ldots, n+1\}$ . If $C$ consists of $\{n+1\}$ alone, then this is the largest element of $C$ . In fact $n+1$ is the largest element of all sets containing it. Notice that the subsets containing $n+1$ constitute the totality of additional subsets that we can append to the set of subsets of $\{1, \ldots, n\}$ (that have a largest element already from the inductive hypothesis).

Thus $A$ is inductive, $A = \mathbb{Z}_+$ , and the statement is true for all $n \in \mathbb{Z}_+$ .

We can create a little table to show this formally.

1.4.4

(b)

Pick $\mathbb{Z}_+ \subset \mathbb{Z}_+$ . It is nonempty, but has no largest element! For, suppose it did, and pick it. Say it is $x$ . Then $x+1$ is larger, with $x+1 \in \mathbb{Z}_+$ (since $\mathbb{Z}_+$ is inductive, e.g.). We’ve reached a contradiction in our argument, and thus $\mathbb{Z}_+$ has no largest element.

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

1.4 Exercise 3

July 31st, 2009

No comments

To get acquainted with the set of positive integers and how this set is related to “proving things by induction,” this problem is a great primer!

“(a) Show that if $\mathcal{A}$ is a collection of inductive sets, then the intersection of the elements of $\mathcal{A}$ is an inductive set.

(b) Prove the basic properties of $\mathbb{Z}_+$ :

(1) $\mathbb{Z}_+$ is inductive;
(2) (Principle of induction). If $A$ is an inductive set of positive integers, then $A = \mathbb{Z}_+$ .”

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

—–

SOLUTION

(a)

We want to attempt this by contrapositive. Thus we want to show that if the intersection of the sets in the collection is not inductive, then the collection is not a collection of inductive sets. There are two ways in which the intersection of the sets in the collection can fail to be inductive: if $1$ is not in the intersection of the collection, or if for some element $x$ in the intersection of the collection, $x + 1$ is not in there too.

First, if $1$ is not in the intersection of the collection $\mathcal{A}$ , this means at least one set of such collection does not contain $1$ as an element… such a set or several are therefore not inductive, differing from the definition of “inductive.” But then $\mathcal{A}$ is not a collection of (all) inductive sets.

Second, if for some element $x$ in the intersection the collection, $x+1$ is not in the intersection of the collection, then this of course means that at least one of the sets of the collection does not contain $x+1$ as an element. Since each individual set of the collection did contain $x$ in the first place (this element being in the intersection of the collection), such a set or several fail the definition of “inductive.” Naturally, then the collection is not a collection of inductive sets.

(b)

To prove (1), we resort to the definition of $\mathbb{Z}_+$ : $\mathbb{Z}_+ = \cap_{A \in \mathcal{A}} A$ , with $\mathcal{A}$ is a collection of (all) inductive subsets of $\mathbb{R}$ . Next, apply the result of Part (a), and $\mathbb{Z}_+$ is inductive.

Recall that $A$ is an inductive set of positive integers. To show (2), we do so in the usual way we show mutual containment, first by proving $A \subset \mathbb{Z}_+$ and then $A \supset \mathbb{Z}_+$ . Thus:

$A \subset \mathbb{Z}_+$ . $1 \in A$ since $A$ is inductive, and $1 \in \mathbb{Z}_+$ since $\mathbb{Z}_+$ is inductive (by (1)). Next, $x$ is an element of $A$ , and since it is an (positive) integer, we know it is generated by successive additions of 1. Such an $x$ is common to all inductive sets, and so it belongs to the intersection of the collection of all inductive sets: $x \in \cap_{A \in \mathcal{A}} A$ . Well, $x + 1$ is an element of $A$ being a positive integer too, and such element is common to all inductive sets as well; it lies in the collection of all inductive sets. (Notice we are using actual induction to show this inclusion). Thus all elements of $A$ lie in the intersection of all inductive sets of $\mathbb{R}$ .

$A \supset \mathbb{Z}_+$ . Pick an element $x \in \mathbb{Z}_+$ . Since $x \in \cap_{A \in \mathcal{A}} A$ , and $A$ is a member of such collection, then such an $x \in A$ .

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

1.4 Exercise 2

July 25th, 2009

No comments

Another one of those really really long problems, but oh well… after this one the exercises seem more interesting. As before, I’m doing five by five until the end.

“Prove the following laws of inequalities for $\mathbb{R}$ , using axioms (I)-(VI) along with the results of Exercise 1:

A Mixed Algebraic and Order Property

VI. If $x>y$ , then $x + z > y + z$ . If $x>y$ and $z > 0$ , then $x \cdot z > y \cdot z$ .

(a) $x > y$ and $w > z \Rightarrow x + w > y + z$ .

(b) $x > 0$ and $y > 0 \Rightarrow x + y > 0$ and $x \cdot y > 0$ .

(d) $x > y \iff -x < -y$ .

(e) $x>y$ and $z<0 \Rightarrow xz < yz$ .

(f) $x \neq 0 \Rightarrow x^2 > 0$ , where $x^2 = x \cdot x$ .

(g) $-1 < 0 < 1$ .

(h) $xy > 0 \iff x$ and $y$ are both positive or both negative.

(i) $x > 0 \Rightarrow \frac{1}{x} > 0$ .

(j) $x > y > 0 \Rightarrow \frac{1}{x} < \frac{1}{y}$ .

(k) $x < y \Rightarrow x < \frac{x + y}{2} < y$ .”

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

—-

SOLUTION

(a)

1.4.2.a

(b)

First we prove the implication $x > 0$ and $y > 0 \Rightarrow x+y > 0$ .

1.4.2.b.I

Next, we show the implication $x > 0$ and $y > 0 \Rightarrow x \cdot y > 0$ .

1.4.2.b.II

(c)

First, we show the forward implication by direct proof.

1.4.2.c.I

Then, the backward implication, also by direct proof.

1.4.2.c.II

(d)

First, the forward implication by direct proof.

1.4.2.d.I

The backward implication is the reverse argument.

1.4.2.d.II

(e)

1.4.2.e

(f)

We separate this by cases. Case $x > 0$ .

Next, case $x<0$ .

1.4.2.f.II

(g)

We will prove that $0<1$ by indirect proof/contradiction. Suppose $1 \leq 0$ . In fact suppose $1 = 0$ , but this contradicts Axiom III. Thus $1 < 0$ . Now pick any $z > 0$ , as per the hypothesis of Axiom VI. Then $1 \cdot z < 0 \cdot z$ by direct application of Axiom VI, which results in $z < 0$ . But this contradicts our picking $z$ is positive, and thus 1 is not less than zero.

Now, since we’ve shown that $0 < 1$ , direct application of part (2c) suggests that $+0 > -1$ , or, by rearranging, $-1 < 0$ . This completes our work, and $-1 < 0 < 1$ .

(h)

We prove the forward implication by indirect proof. Thus suppose either $x$ or $y$ is negative (not both positive or both negative), say $x$ . Then by the hypothesis of the implication, $xy > 0$ . Following through, $x \cdot y \cdot y^{-1} > 0 \cdot y^{-1}$ by Axiom IV. Notice that the existence of the inverse $y^{-1}$ is given by the fact that $y$ cannot be zero, since if it were this would imply $0 > 0$ , a clear contradiction. Next, $x \cdot 1 > 0$ by Axiom IV, Part (1b). Finally this implies that $x > 0$ by Axiom III, a contradiction of our pick of $x$ negative. To be extremely thorough (although the above should suffice), next pick $y$ is negative, and follow the same recipe to obtain $y > 0$ , again a contradiction. This completes the proof of the forward implication.

The backward implication can be proven rather quickly by the direct method. Suppose $x > 0$ and $y > 0$ . Then, by Axiom VI, $x \cdot y > 0 \cdot y$ , which, by Part (1b), means $x y > 0$ , as we wanted to show. Suppose then $x < 0$ and $y < 0$ . By Part (2c), this means $-x > 0$ and $-y > 0$ . By Axiom VI, $(-x) \cdot (-y) > 0 \cdot (-y)$ , and by Part (1e), this means $-(-(xy)) > 0$ which implies $xy > 0$ using Part (1d). As we wanted to show.

(i)

I proceed here again by contradiction or indirect proof. Assume that $\frac{1}{x} \leq 0$ . In fact suppose $\frac{1}{x} = 0$ . By the multiplication property of equality, $x \cdot \frac{1}{x} = x \cdot 0$ . Of course we can multiply thusly because the mere existence of the reciprocal implies $x$ is nonzero. But then we obtain $1 = 0$ , which contradicts Axiom III. Therefore, $\frac{1}{x} < 0$ , or, to align notation, $0 > \frac{1}{x}$ . Then multiply by $x$ on both sides, as per Axiom VI: $0 \cdot x > \frac{1}{x} \cdot x$ . Applying through the notions we know already, we obtain $0 > 1$ , a contradiction of Part (2g). Thus our initial assumption was wrong, and the implication is true as originally stated.

(j)

Again proceed by contradiction, and assume $\frac{1}{x} \geq \frac{1}{y}$ . Suppose first that $\frac{1}{x} = \frac{1}{y}$ . Since $x$ and $y$ are nonzero by hypothesis, we obtain by the Multiplicative Property of Equality that $x = y$ , but this then contradicts the premise that $x$ is larger than $y$ . Next suppose that $\frac{1}{x} > \frac{1}{y}$ . Since $x$ is nonzero and positive, we can easily multiply thusly, without affecting the inequality: $\frac{1}{x} \cdot x > \frac{1}{y} \cdot x$ , and we are justified by Axiom VI. We obtain $1 > \frac{x}{y}$ . Multiply by nonzero and positive $y$ like this: $1 \cdot y > \frac{x}{y} \cdot y$ again justified by Axiom VI and without affecting the inequality, to obtain $y > x$ . This however contradicts our hypothesis, and we’ve shown the implication as originally stated actually holds.

(k)

Again suppose otherwise, that either $x \geq \frac{x+y}{2}$ or $\frac{x+y}{2} \geq y$ . In the first case, multiply by two on both sides to obtain $2x \geq x+y$ , or in effect $(1+1) x \geq x + y$ . Multiplying through implies $x + x \geq x + y$ , or $-x + x + x \geq -x + x + y$ or $x \geq y$ . This last statement contradicts the hypothesis, so our first assumption cannot be true. In the second case, do the same and obtain $x + y \geq 2y$ or $x + y \geq (1 + 1) y$ or $x + y \geq y + y$ or $x + y + -y \geq y + y + -y$ or finally $x \geq y$ , again a contradiction of the hypothesis, which means the second assumption cannot be true either. The statement as originally posited therefore must be true.

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

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

Older Entries

The Pasqualian

A Shakesperean Sonnet for Lucinda on her Birthday

On Mental Arithmetic

On Utilities Consumption I: Water

1.4 Exercise 5

1.4 Exercise 4

1.4 Exercise 3

1.4 Exercise 2

1.4 Exercise 1

1.3 Exercise 15

Busy People

Tags

Categories

Recent Posts

Recent Comments

Business

Math

Categories

Archives

Meta

March 2010
S	M	T	W	T	F	S
« Jan
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31