Two Views of the Monotone Sequence Theorem

Posted on by

If a sequence of real numbers (an) is bounded and monotone (and I'm actually going to say nondecreasing, without loss of generality), then it converges. I'm going to tell you why and I'm going to tell you twice.

If our sequence is bounded, the completeness of the reals ensures that it has a least upper bound, which we'll call, I don't know, B, but there have to be sequence elements arbitrarily close to (but not greater than) B, because if there weren't, then B couldn't be a least upper bound. So for whatever arbitrarily small ε, there's an N such that aN > B – ε, which implies that |aN – B| < ε, but if the sequence is nondecreasing, we also have |an – B| < ε for n ≥ N, which is what I've been trying to tell you—

—twice; suppose by way of contraposition that our sequence is not convergent. Then there exists an ε such that for all N, there exist m and n greater or equal to N, such that |am – an| is greater or equal to ε. Suppose it's monotone, without loss of generality nondecreasing; that implies that for all N, we can find n > m ≥ N such that an – am ≥ ε. Now suppose our sequence is bounded above by some bound B. However, we can actually describe an algorithm to find sequence points greater than B, thus showing that this alleged bound is really not a bound at all. Start at a1. We can find points later in the sequence that are separated from each other by at least ε, but if we do this ⌈(B – a1)/ε⌉ times, then we'll have found a sequence point greater than the alleged bound.

Library Fines

Posted on by

Overdue book fines are a terrible sin, not because of the harm done to other library stakeholders, but because of what they say about you as a person: not only did you not get around to finishing the books you (apparently erroneously) thought you wanted to read, but you weren't even responsible enough to bring them back on time.

Subscripting as Function Composition

Posted on by

Dear reader, don't laugh: I had thought I already understood subsequences, but then it turned out that I was mistaken. I should have noticed the vague, unverbalized discomfort I felt about the subscripted-subscript notation, (ank). But really it shouldn't be confusing at all: as Bernd S. W. Schröder points out in his Mathematical Analysis: A Concise Introduction, it's just a function composition. If it helps (it helped me), say that (an) is mere syntactic sugar for a(n): ℕ → ℝ, a function from the naturals to the reals. And (ank) is just the composition a(n(k)), with n(k): ℕ → ℕ being a strictly increasing function from the naturals to the naturals.

"It's Not That"

Posted on by

Oftentimes I initially want to write "It's not that X, but rather Y" to mean "You might think I'm implying that X is true, so I want to emphasize that X is false; Y is true, and that's what explains my position," but I worry that this idiom is ambiguous; someone is likely to interpret it as meaning, "X might be true, but it's not the relevant consideration; my position is actually explained by Y (which does not necessarily contradict X)", which doesn't mean the same thing.

Computing the Arithmetic Derivative

Posted on by

Jurij Kovič's paper "The Arithmetic Derivative and Antiderivative" contains a curious remark in Section 1.2. Having just stated the definition of the logarithmic arithmetic derivative (L(n) = n′/n = Σj aj/pj where the prime mark indicates the arithmetic derivative, and Πipiai is the prime factorization of n), Kovič writes:

The logarithmic derivative is an additive function L(xy) = L(x) + L(y) for any x, y ∈ ℚ. Consequently, using a table of values L(p) = 1/p (computed to sufficient decimal places!) and the formula D(x) = L(x)·x, it is easy to find D(n) for n ∈ ℕ having all its prime factors in the table.

... a table of values? Did I read that correctly? Surely there must be some mistake; surely a paper published in 2012 can't expect us to rely on a printed table, for all the world as if we were John Napier in the seventeenth century! But never fear, dear reader, for the situation is easily rectified—with just a few lines of Python, you can take all the arithmetic derivatives you like on your own personal computing device.

Continue reading →

Blood From a Stone

Posted on by

Decision-theoretically speaking, there's no difference between punishment and lack-of-reward. (Von Neumann–Morgenstern utility functions are really only defined up to an affine transformation: if your behavior is described by u(x), then v(x) := au(x) + b does just as well.) Psychology isn't like that; punishment and lack-of-reward are very different things—although not quite so different as one might think. In an environment where behavior X is rewarded with praise and status, and behavior Y is ignored—not punished, not condemned, but ignored—what kind of mind would it take to persist in behavior Y? It would either have to be very stubborn, unshakeably convinced in the righteousness of Y, or very stupid, desperately willing to endlessly chase a satisfaction that will never, ever come.

Friendship Deficits

Posted on by

I'm not sure, but I suspect that I'm running a friendship deficit—that I need my friends more than they need me.

In a naively romanticized world of "pure" and unconditional love, you would never have occasion to think of such things: friends are always there for each other, no matter what, and no one would dream of anything so monstrous as consciously evaluating whether it's worth maintaining a friendship given the costs and benefits of doing so (including the opportunity cost of forgoing something else that could be done with the same amount of time and attention).

And in a world of Bayesian expected-utility-maximizing decision agents, there would be no loyalty and no concept of friendship.

Part of the beauty of our world is that it lies somewhere between the two extremes, but that we don't know exactly where.

Telling Her There

Posted on by

"And so," said Synthia, "if you feel too self-conscious to write an email, if you don't know what to say or are afraid of saying the Wrong Thing, it might help to lower your quality standard and just start typing as if it were realtime communication, and edit later. It's less tempting to procrastinate replying in a realtime medium like instant messaging, and hardly tempting at all in meatspace, so you can try to import that same mindset to start your email."

"I don't usually have that problem," said Quiana.

"But, arguably, it's still a good thing that I told you, because your analogue in a nearby alternate universe who does have that problem would have been grateful for the tip, and I had to tell you here to ensure that my analogue there tells her."

"Or you could have conditioned your telling me on whether or not your local Quiana had the problem."

"Well, the reason I had to tell you here in order to sure that my analogue told her is that neither I nor my analogue previously knew which of us was which," Synthia explained. She shrugged apologetically. "Now we know."

Bounded but Not Totally Bounded, Redux

Posted on by

Theorem. An open set in real sequence space under the ℓ∞ norm is not totally bounded.

Proof. Consider an open set U containing a point p. Suppose by way of contradiction that U is totally bounded. Then for every ε > 0, there exists a finite ε-net for U. Fix ε, and let m be the number of points in our ε-net, which net we'll denote {Si}i∈{1, ..., m}. We're going to construct a very special point y, which does not live in U. For all i ∈ {1, ..., m}, we can choose the ith component yi such that the absolute value of its difference from the ith component of the ith point in the net is strictly greater than ε (that is, |yi – Si,i| > ε) but also so that the absolute value of its difference from the ith component of p is less than or equal to ε (that is, |yi – pi| ≤ ε). Then for j > m, set yj = pj. Then |y – p| ≤ ε, but that means there are points arbitrarily close to p which are not in U, which is an absurd thing to happen to a point in an open set! But that's what I've been trying to tell you this entire time.

The Quieted Scare Convention

Posted on by

Everyone knows ("everyone knows") about "scare quotes," where you enclose a phrase in quotation marks to indicate that the literal interpretation of the words should be regarded with skepticism, but sometimes I do this thing where I'll use a phrase normally and then repeat it in scare quotes and parentheses, as if to say, "I do partially intend this sincerely, but also with some irony or skepticism, although not so much as to justify outright scare quotes."

Of course, this practice immediately suggests the "dual" (dual) practice of using a phrase with scare quotes and then repeating it unquoted in parentheses, as if to say, "I do partially intend this ironically or in a way that should be regarded with skepticism, but also with a some sincerity, although not so much as to justify not using any scare quotes at all."

Bounded but Not Totally Bounded

Posted on by

The idea of total boundedness in metric space (for every ε, you can cover the set with a finite number of ε-balls; discussed previously on An Algorithmic Lucidity) is distinct from (and in fact, stronger than) the idea of mere boundedness (there's an upper bound for the distance between any two points in the set), but to an uneducated mind, it's not immediately clear why. What would be an example of a set that's bounded but not totally bounded? Wikipedia claims that the unit ball in infinite-dimensional Banach space will do. Eric Hayashi made this more explicit for me: consider sequence space under the ℓ∞ norm, and the "standard basis" set (1, 0, 0 ...), (0, 1, 0, 0, ...), (0, 0, 1, 0, 0, ...). The distance between any two points in this set is one, so it's bounded, but an open 1-ball around any point doesn't contain any of the other points, so no finite number of open 1-balls will do, so it's not totally bounded, which is what I've been trying to tell you this entire time.

Dreams

Posted on by

Friend of the blog Alicorn tweets:

Why is the word "dreams" used to describe both pseudorandom nocturnal hallucinations and also heartfelt aspirations for real life?

A cynic might reply: because both the nocturnal hallucinations and the heartfelt aspirations are, for the most part, composed of lies. How many people, what proportion of the time, will actually lift a finger (or open a book, or make a telephone call) to work towards actually achieving what they believe to be heartfelt aspirations?

Don't Resent That No One Cares

Posted on by

It's tempting to be resentful that other people don't value your time the way you do. You complain at every opportunity: "Why, why, why do I get socially rewarded for working on this-and-such random chore that doesn't even help anyone, when obviously my great masterpiece (in progress, in potentia, coming soon) on such-and-this is so much more valuable?!"

But I think it's better not to be resentful and not to complain, mostly because it doesn't work. Other people don't care about your great masterpiece on such-and-this. They really don't. Maybe someone, somewhere will care after it's done, but it's not reasonable to expect anyone's support in advance—or, alternatively and isomorphically, it is reasonable, but given that there's nothing you can do to force people to be reasonable, reasonableness is not the correct criterion to be paying attention to.

Continue reading →