Hilbert vs. Banach Spaces
I’ve finally started studying Hilbert spaces, which can be used to define conditional expectation for square-integrable random variables (see e.g. Chapter 23 in Jacod & Protter’s Probability Essentials). Of course, every Hilbert space is a Banach space; as I sat and tied my shoes after Mysore practice this morning, I wondered whether it’s easy to show that the converse is false. I’d been thinking about counterexamples in general after hearing about Tsirelson’s drift in class yesterday. Before getting his PhD, Tsirelson also came up with a counterexample in the theory of Banach spaces; interestingly, his construction was inspired by the method of forcing, which Paul Cohen invented to prove his celebrated independence results.
It turned out to be way easier than I thought it would be. Consider the space B(X) of bounded functions on an arbitrary set X, and endow B(X) with the supremum norm ||·||. It’s well-known that B(X) is a Banach space; here’s a standard proof. This space is very useful in the theory of Markov decision processes, via the theory of contraction mappings.
To see that B(X) isn’t a Hilbert space, take any non-empty subset A of X and its complement Ac. Then the parallelogram law doesn’t hold for their corresponding indicator functions 1A and 1Ac, because 2||1A||2 + 2||1Ac||2 = 4 and ||1A + 1Ac||2 + ||1A – 1Ac||2 = 2. But since the parallelogram law holds for every Hilbert space, it follows that B(X) isn’t a Hilbert space.
Weak vs. Setwise Convergence of Measures
In class today, my advisor pointed out a subtlety in the statement of Theorem 18.9 in Jacod & Protter’s Probability Essentials. The theorem reads:
Let Xn, X be random variables with at most countably many values. Then Xn converges in distribution to X if and only if P(Xn = j) tends to P(X = j) for each j in the state space S of the Xn‘s, and X.
This is true when the state space S is endowed with the discrete topology; in fact, this assumption is stated in the paragraph preceding the theorem in the book. But, the following simple example shows that it may be false otherwise: Let S be the real line endowed with its usual topology. For n = 1, 2, …, let the distribution measure of Xn be the Dirac measure sitting at 1/n, and let the distribution measure of X be the Dirac measure sitting at 0.
On the one hand, consider any bounded continuous function f on S. For each n, the integral of f with respect to the distribution measure of Xn is f(1/n), its integral with respect to the distribution measure of X is f(0), and the continuity of f implies that the former tends to the latter. This means Xn converges in distribution to X, i.e. the distribution measures of the Xn‘s converge weakly to the distribution measure of X.
On the other hand, P(Xn = 0) = 0 certainly doesn’t tend to P(X = 0) = 1. In other words, the distribution measures of the Xn‘s don’t converge strongly to the distribution measure of X. A perhaps more evocative name for strong convergence is setwise convergence, which seems to be the more usual terminology in the context of Markov decision processes.
Numerosity of the Transcendentals
Last night, as usual, I was flipping through some books before going to bed. In Srivastava’s book A Course on Borel Sets, I saw a result that probably shows up in most textbook expositions of countability, namely the countability of the set of all algebraic numbers. I think I’d first learned about this from doing Exercise 2 in Chapter 2 of Baby Rudin.
As I was walking back to the apartment in the snow (!) today, I was thinking about how this result neatly shows that there are (a heck of a lot of) non-algebraic, i.e. transcendental, numbers; Cantor himself noted this in his 1874 paper. Actually, the existence of transcendentals was settled constructively in 1844 by Liouville. But what Cantor’s proof shows is that, in fact, almost all real numbers are transcendental; e.g. π and e are transcendental. Interestingly, it’s unknown whether things like π + e are transcendental.
The countability of the set of all (I’m reminded to remember to say “all” by Edward Frenkel) algebraic numbers follows pretty straightforwardly if you know the fundamental theorem of algebra: First, show that the set of all polynomials with integer coefficients is countable (e.g. by showing that it’s equinumerous to the set of all finite sequences of integers, which is countable), and then note that each such polynomial has a finite number of roots. Another way, which is hinted at in Baby Rudin (and, I think, is how it’s done in Cantor’s paper) is to note that for every positive integer N there’re only a finite number of values of n, a0, …, an satisfying n + |a0| + … + |an| = N.
Blade of the Ronin
I listened to Cannibal Ox for the first time yesterday. I had a huge smile on my face the entire time. I need to check out The Cold Vein and Bill Cosmiq‘s work.
Purity Ring‘s new album is out next Tuesday too. So much great stuff’s been coming out (B4.DA.$$ in Jan., Kinison earlier last month, Sour Soul last week). Plus Action Bronson‘s new album‘s out later this month, and oh man Day of the Dead is back (I guess I really like New York hip hop):
The Guest House
After Mysore practice with Dhruva & Jackie Corrigan at the Barn in Avalon Park & Preserve this morning (where I bound myself on the second side of Marichyasana C for the first time!), Dhruva told us about the poem The Guest House by Rumi. This is the translation by Coleman Barks:
THE GUEST HOUSE
This being human is a guest house.
Every morning a new arrival.A joy, a depression, a meanness,
some momentary awareness comes
as an unexpected visitor.Welcome and entertain them all!
Even if they are a crowd of sorrows,
who violently sweep your house
empty of its furniture,
still, treat each guest honorably.
He may be clearing you out
for some new delight.The dark thought, the shame, the malice.
meet them at the door laughing and invite them in.Be grateful for whatever comes.
because each has been sent
as a guide from beyond.
Uncountability Via a Topological Game
A standard way to show that the closed interval [0, 1] is uncountable is to use a diagonal argument. Another way, given by Matthew Baker in a nice article published in Mathematics Magazine, is to use a topological game.
The game, played by Alice and Bob, is as follows. After a subset S of [0, 1] is specified, they take turns picking numbers in a certain way. In particular, letting a0 = 0 and b0 = 1, on turn n = 1, 2, … Alice chooses a number an satisfying an-1 < an < bn-1, and Bob chooses a number bn satisfying an < bn < bn-1. Since the sequence {an} is increasing and bounded above, it has a limit a. If a belongs to the set S, Alice wins; otherwise Bob wins. So, Alice is trying to steer the sequence {an} into S, while Bob’s trying to push it out of S.
Note that if S = [0, 1], Alice wins no matter what. But, if S = {sn} is countable, Bob can always win by doing this: on turn n, pick sn if possible, and otherwise pick any allowable number. Then on every step n, either sn ≤ an (if Bob couldn’t pick sn) or bn = sn (if Bob picked sn). But since an < a < bn for each n, this means a doesn’t belong to S, so Bob wins. Hence [0, 1] can’t be countable!
Baire functions vs. Borel functions
In many early papers on Markov decision processes (e.g. Blackwell’s 1965 classic Discounted Dynamic Programming), the one-step cost function is assumed to be a Baire function. Then at some point, “Baire function” became “Borel function“, and I’ve yet to see a modern paper on MDPs mention Baire functions. It took me a while to find out that for the purposes of studying MDPs, these two definitions are equivalent. I guess using Borel functions has the advantage of not having to mention continuous functions right away.
In particular, both the state space X and action space A of an MDP are usually taken to be metrizable (more specifically, Borel subsets of Polish spaces). The real-valued one-step cost function c is defined on a subset K of the product space XA, which by the metrizability of X and A is also metrizable. Then, letting R denote the set of real numbers, the function c is a Baire function if it belongs to B(K, R), the smallest class of functions from K to R containing the continuous functions and closed under pointwise limits of sequences of functions. On the other hand, c is a Borel function if the preimage of any Borel subset of R is a Borel subset of K. The result that c is a Baire function if and only if it’s a Borel function then follows from Proposition 3.1.32 and Theorem 3.1.36 on pages 90 and 91, respectively, of Srivastava’s book A Course on Borel Sets.
The Cantor set and the Lebesgue σ-algebra
Yesterday, while my advisor and I were discussing a possible appendix on measure theory in his forthcoming introductory book on Markov decision processes, he mentioned that there are 2c Lebesgue-measurable subsets of the real line, where c is the cardinality of the continuum. In other words, the number of subsets of the real line that are Lebesgue-measurable is the same as the number of subsets of the real line. There are, however, subsets of the real line that aren’t Lebesgue-measurable, e.g. the Vitali set. By the way, the existence of non-measurable subsets of the real line is somehow closely related to the assumption of the Axiom of Choice; in particular, Robert Solovay showed that there is a model of Zermelo-Fraenkel set theory without the Axiom of Choice where every set of real numbers is Lebesgue-measurable.
A nice way to show that there’re 2c Lebesgue-measurable sets is to consider the famous Cantor set, which was apparently discovered by Henry John Stephen Smith, Paul du Bois-Reymond, and Vito Volterra – in that order – several years before being introduced by Georg Cantor in 1883.
First, the Cantor set is both tiny and huge; it’s tiny in the sense of “length” as defined by Lebesgue measure, and huge in the sense of “how many elements it contains” as defined by cardinality. Namely, its Lebesgue measure is equal to zero, and its cardinality is the cardinality of the continuum c; there’s a nice discussion of this starting on page 75 of the book Understanding Analysis by Stephen Abbott. But since the Lebesgue measure is a complete measure, i.e. every subset of any set of Lebesgue measure zero is Lebesgue-measurable (whew), the fact that the Cantor set has Lebesgue measure zero implies that the number of Lebesgue-measurable subsets of the real line is at least the size of the power set of a set with cardinality c, i.e. is at least 2c (whew!). In fact, since each of these subsets is a subset of the real line, and the power set of the real line has cardinality 2c, it follows from the Cantor-Bernstein-Schröder theorem that there are precisely 2c Lebesgue-measurable subsets of the real line!
Cantor’s Theorem
After Richard Taylor’s talk at the Math Museum last Sunday, I finally bought a copy of Paul Cohen’s Set Theory and the Continuum Hypothesis at the Strand Bookstore (for $7!). This got me to take another look at Smullyan & Fitting’s Set Theory and the Continuum Problem, which looks promising; they cover Gödel and Cohen’s consistency and independence proofs for the axiom of choice and the continuum hypothesis relative to von Neumann–Bernays–Gödel set theory.
On pages 6-8, Smullyan & Fitting discuss Cantor’s theorem, which says that any set X cannot be put in 1-1 correspondence with the set P(X) of all its subsets. This has a nice, short proof: first, for each element x of X, assign to it an element Sx of P(X). Let S denote the set of all elements x of X such that x doesn’t belong to Sx. Then any x in X either belongs to Sx or S, but not both; hence there’s no Sx equal to S. In other words, under any correspondence between X and P(X) there’ll be an element of P(X) that isn’t paired with any element of X.
Cantor’s (generalized) continuum hypothesis is that for any infinite set X, there’s no set that’s both larger than X and smaller than P(X) (in terms of cardinality). In particular, the hypothesis says that there’s no set that’s both larger than the set of all natural numbers and smaller than the set of all real numbers. Gödel showed in 1938 that, if the axioms of set theory are consistent (i.e. it’s impossible to derive a contradiction from them), then the continuum hypothesis cannot be disproved; about 25 years later, Cohen showed that it cannot be proved either. One interpretation of this is that the standard axioms of set theory in use today aren’t powerful enough to decide whether the continuum hypothesis is true or not (and it turns out that this is also the case for the axiom of choice).
Incompleteness
I’ve been watching the lectures from the Kurt Gödel Centenary at the IAS in 2006 over breakfast, which reminded me of this neat little puzzle from page 2 of Gödel’s Incompleteness Theorems by Raymond Smullyan. I’m going to blurt out the solution after the next paragraph.
There’s a machine that prints the symbols ~, P, N, (, and ). A finite sequence of symbols, e.g. )P(~N, is printable if the machine will eventually print it. Letting X stand for any finite sequence of symbols, the following sequences are called sentences: P(X), PN(X), ~P(X), ~PN(X). For sentences, there’s a notion of truth; in particular, P(X) is true if and only if (iff.) the finite sequence X of symbols is printable, PN(X) is true iff. the sequence X(X) is printable, ~P(X) is true iff. X isn’t printable, and ~PN(X) is true iff. X(X) isn’t printable. Finally, the only requirement on what the machine can print is that it can’t print a sentence that isn’t true. The question is: Will the machine print every true sentence?
The answer’s no: consider the sentence ~PN(~PN). First, note that this is a sentence of the form ~PN(X), which is true iff. X(X) isn’t printable. But for our particular sentence, X stands for ~PN, so ~PN(~PN) is true iff. ~PN(~PN) isn’t printable! This means that if the machine were to print ~PN(~PN), then the sentence ~PN(~PN) wouldn’t be true. Since the machine can’t print sentences that aren’t true, ~PN(~PN) can’t possibly be printed, which also means that ~PN(~PN) is true!
It's easy as pie, 3.14 