Sequence which has countably many convergent subsequences.

August 22, 2011

This post is about a question I just thought about that I thought had a pretty neat solution.  The values we consider below are all in the Reals.

So, we’re all familiar with sequences which have subsequences which converge to two different values; for example, take $\{1,-1,1,-1,1,-1,\dots\}$ which has a subsequence converging to 1 and a subsequence converging to -1.  Similarly, we can construct a sequence containing subsequences converging to three different values in a similar way; for example: $\{-1,0,1,-1,0,1, \dots\}$.  Indeed, for any finite number, we can make a sequence containing subsequences converging to that number of different values.

The obvious next question is: can a sequence have subsequences which converge to a countable number of different values?  What about an uncountable number of different values?

For the former question, I thought of this solution.  First, enumerate your countable list of distinct values (think of the integers or the rationals, for example) as $\{q_{1}, q_{2}, \dots\}$.  To construct the sequence, we do the following:

• Let $a_{1} = 0$.
• Let $a_{b} = 0$ if $b$ is not some positive power of a prime (for example, if $b$ is 15, 21, 35, 100, etc.)
• For $a_{k}$ where $k$ is a positive power of a prime, we do the following: If $k = p_{i}^{r}$ for $r\in {\mathbb N}$ and $p_{i}$ is the $i$-th prime (so $p_{1} = 2$, $p_{2} = 3$, $p_{3} = 5$, and so on) then set $a_{k} = q_{i}$ where $q_{i}$ is the $i$-th element from your list above.

How does this actually work?  Let’s take a simple example.  Let’s let our countable set be the set of natural numbers.  This is easily ordered as $\{1,2,3,4,5,\dots\}$ and so, for this example, $q_{1} = 1$, $q_{2} = 2$, $q_{3} = 3$, and so forth.  Our sequence is now:

$\{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}, a_{9}, a_{10},\dots\}$

$= \{a_{1}, a_{2}, a_{3}, a_{2^{2}}, a_{5}, a_{2\cdot 3}, a_{7}, a_{2^{3}}, a_{3^{2}}, a_{2\cdot 5}, \dots\}$

$= \{0, q_{1}, q_{2}, q_{1}, q_{3}, 0, q_{4}, q_{1}, q_{2}, 0, \dots\}$

$= \{0, 1, 2, 1, 3, 0, 4, 1, 2, 0, \dots\}$

and if we kept going like this,

$= \{0, 1, 2, 1, 3, 0, 4, 1, 2, 0, 5, 0, 6, 0, 0, 1, 7, 0, 8, 0, 0, 0, 0, 0, 3, 0,\dots\}$

You kinda see the pattern going on here.  The 1 will appear infinitely many times, but the spaces between it grow exponentially.  Same for 2, 3, 4, and so on.  Thus, this sequence has the subsequence $\{n, n, n, n, \dots\}$ for any $n\in {\mathbb N}$ which obviously will converge to $n$.

Do you have another neat way to do this?  Encoding this in the primes was my first thought, but you never know!

As for uncountable, my guess is no.  Of course, thinking of the sequence as a SET, we would get the reals from the rationals which is uncountable, but as a SEQUENCE it is not so trivial I feel.  I don’t want to spend too much time thinking about this (as analysis is calling me!) but I’m sure the proof isn’t too crazy.

Edit: Of course, a nice example exists where a sequence has subsequences converging to an uncountable number of distinct point.  In fact, two nice examples exist, and both were provided to me by Brooke (as usual!).

Uncountable Example 1:

It was a bit difficult for me to see the first one, but after doing a nice little thought experiment everything became much clearer.  Here it is:

Let $\{q_{1}, q_{2}, \dots\}$ be an enumeration of the rationals.  The claim is that there is actually a subsequence which converges to any real number.  Think about it for a minute.

Here’s a sketch for the proof.  Take your favorite real number.  Let’s start easy and just say we want a subsequence which converges to $\pi$.  Let $a_{1}$ be the first element in our enumeration of the rationals above which is a distance less than 1 away from $\pi$; let’s say it’s $q_{k}$.  Now let $a_{2}$ be the first element in our enumeration which is after $q_{k}$ and which is a distance less than $\frac{1}{2}$ away from $\pi$

After that, you just keep picking the "next" element from the list that’s $\frac{1}{2^{n}}$ away from $\pi$.  There must be one due to the density of the rationals in the reals (or, assume not and see what happens!).  We end up with $\{a_{1}, a_{2}, \dots\}$ as a subsequence of our enumeration of the rationals which converges to $\pi$.  Obviously, replacing $\pi$ with any other real number works exactly the same.

Uncountable example 2:

This was one that Brooke presented to me that I liked quite a bit since it’s really easy to state.  Here’s the sequence (broken up by lines for clarity):

$0.0\,,\, 0.1\,,\, 0.2\,,\, \dots\,,\, 0.9,$

$0.00\,,\, 0.01\,,\, 0.02\,,\, \dots\,, \,0.09\,,\, 0.10\,,\, 0.11\,,\, \dots\,,\, 0.99\,,$

$0.000\,,\, 0.001\,,\, 0.002\,,\, \dots\,,\, 0.999\,, \dots$

This converges to any real number in $[0,1]$.  To see this is easy: decimal expand your chosen real number and pick the element "from each line" (as I’ve written it above) which is closest to it.  They’ll be at most $10^{-j}$ away (for some suitable $j$ depending on the line you’re on) and thus a subsequence exists which converges to whatever element you picked.

Lim Sup: Life Lessons.

August 22, 2011

I’ve always felt a little uneasy with Lim Sup and Lim Inf’s.  Today while reading Rudin’s Complex book, I finally "got" it.

To find the lim sup of your sequence: take every convergent subsequence’s limit and find the sup of those limits.

This is, of course, exactly what the definition is, but it wasn’t "visual" to me until I thought about it this way.  Is there something you learned early on that you weren’t quite clear with until much, much later?

A Quick Note on Fatou’s Lemma.

August 16, 2011

Above is a sweet picture of this French mathematician Pierre Fatou.  Of course he had a nice mustache, but a few math things that are kind of neat about him: he was the first person to study the Mandelbrot set (though there is some controversy regarding the word "first" here…) and he also enjoyed iterative and recursive processes before they became really cool, making him a computer science hipster.  Also, he has a lemma in measure theory named after him.  That’s what this post is about.

Lemma (Fatou’s):  Let $\{f_{i}\}_{i}$ be a sequence of non-negative measurable functions on ${\mathbb R}$ with the Lebesgue measure $\mu$,  and let $\displaystyle f(x) = \lim_{n\rightarrow\infty}\inf_{m \geq n} f_{n}(x)$ for all $x\in {\mathbb R}$.  Then, $f$ is measurable and we have the inequality

$\displaystyle \int f\, d\mu \leq \lim_{n\rightarrow\infty}\inf_{m \geq n} \int f_{n}\, d\mu$.

Nested Sequences of Measurable Sets.

August 10, 2011

On nearly every practice qualifying exam that I’ve been studying from, the following question (in some guise) comes up:

Question: Let $\{E_{i}\}_{i=1}^{\infty}$ be a sequence of Lebesgue measurable sets in ${\mathbb R}$.  Denote the Lebesgue measure by $\mu$

1. If $E_{n}\subseteq E_{n+1}$ for every $n\in {\mathbb N}$, then is it true that $\displaystyle \mu(\bigcup_{i=1}^{\infty} E_{i}) = \lim_{n\rightarrow\infty}\mu (E_{n})$?  If not, add a criteria to make it true.
2. If $E_{n}\supseteq E_{n+1}$ for every $n\in {\mathbb N}$, then is it true that $\displaystyle \mu(\bigcap_{i=1}^{\infty} E_{i}) = \lim_{n\rightarrow\infty}\mu (E_{n})$? If not, add a criteria to make it true.

I’ll write up the solutions, since they are available elsewhere, but take a little bit of time to think about the second one if you haven’t.  I’ll put the remainder of the post under a cut so that I don’t spoil it right away.

Jordan’s Lemma.

August 9, 2011

[This post is for those of you who are already comfy with doing some basic contour integrals in complex analysis.]

So you’re sitting around, evaluating contour integrals, and everything is fine.  Then something weird comes up.  You’re asked to evaluate an integral that looks like

$\displaystyle \int_{-\infty}^{\infty} e^{aix}g(x)\, dx$

for $g(x)$ is continuous.  Eek.  Don’t panic though, because Camille Jordan’s gonna help you out.

Brief "Where are we going?" Motivation.

So far we’ve been talking about measure theory, which is nice to study just for the sake of measuring things, but when we talk about functions and measurements, we generally want to know the integral.  The Riemann integral was wonderful because of its simplicity in defining it: you have a big sheet of wavy paper (the total area under a function) and you keep slicing the pieces until they look like rectangles — once they look sufficiently close to a rectangle, just use length-times-width, and add up all the rectangles.  This is one interpretation of the Riemann integral, and, for the most part, it works wonderfully.  But there are many functions where it fails miserably.  This is where Lebesgue takes over.

So what’s different about Lebesgue?  While Riemann cuts apart the domain, Lebesgue says, "Okay, how large is the set of x-values that have the range value $c\in {\mathbb R}$?"  Specifically, we cut up the function into sets which have the same range value, then multiply that range value with the measure of the set.

As an example, take the step function $f$ defined on, say, $[-10,10]$ such that $f(x) = 1$ for $0\leq x < 1$ and $f(x) = 2$ for $1\leq x < 2$ and $f(x) = 0$ elsewhere.  The Lebesgue integral will say, "Where does $f$ take on the value 0?  Well, $[-10,0)\cup(2,10]$ which has measure of 18.  Since the value is 0, we have $18\cdot 0 = 0$, so this contributes nothing to the integral.  Where does $f$ take on the value 1?  On $[0,1)$, which has a measure 1.  So this contributes $1\cdot 1$ to the integral.  Similarly, the function takes on a value 2 onn $[1,2)$, this has measure 1, so this contributes $1\cdot 2$ to the integral.  No other values are taken on, so this integral is 0 + 1 + 2 = 3."

This extremely simple example shows the difference between Riemann and Lebesgue at the most fundamental level.  To do Riemann would be much easier in this case: it’s just adding up the rectangles.

There is a slight hitch at this point. Suppose we naively tried to apply what we’ve just said to a more complex function like $f(x) = x$ defined, say, on $[0,2]$.  We know (because this forms a triangle) that the area should be 2.  At every number between $[0,2]$ in the range, though, the function only takes on the value at a single point which has measure 0.  Thus, every one of these contributes 0 to the integral; and the sum of 0’s will be 0.  So the integral is 0?  That’s not right!

The problem here is that we must define the Lebesgue integral for functions which take on simple functions (which take on a countable number of values) and somehow approximate more general functions.  As we know, a function is measurable if and only if there is a sequence of simple functions which converge uniformly to it; and this will give us the means to integrate general (measurable) functions: we will take the integrals of each element of the sequence, and then define that limit to be the integral of the measurable function.  A number of questions will arise instantly, like, "Does this work?  Does this make sense?  Is this well-defined?", all of which can easily be put down with the elegant slashing of our proof-swords.

So, let’s get down to it.

The Lebesgue Integral and Simple Functions.

We’ve already gone over simple functions (ones with a countable number of values, the pre-image of each of these being measurable making simple functions, themselves, measurable) so we might as well dive right in.  We will begin by defining, after long last, the Lebesgue Integral for these simple functions.  It will be defined exactly as we have motivated it above.

Definition.  Let $f$ be a measurable simple function on a (measurable) set $A$ taking the values $a_{1}, a_{2}, \dots$.  Let $A_{i}$ be defined as the set of all $x$ such that $f(x) = a_{i}$; that is, $A_{i}$ is the pre-image of $a_{i}$.  Then we define

$\displaystyle \int_{A}f(x)\, d\mu$

to be exactly the sum

$\displaystyle \sum_{i=1}^{\infty} a_{i}\mu(A_{i})$

provided that the sum converges absolutely (that is, the sum converges with $|a_{i}|$ replacing $a_{i}$).

We call this the Lebesgue integral of $f$ over the set $A$.

Note that we have explicitly noted that $A$ must be measurable, though this is not specifically stated in the texts I am using.  I don’t feel I am losing much in assuming this (expect, perhaps, for more pathological examples such as being able to integrate some function which is non-zero only on a measurable subset of the non-measurable set).  Notice that we have also assumed that our sum must converge absolutely, and not just conditionally.

[Note: At this point, it is not entirely clear to me why this should be necessary; in finite cases, we will generally not worry about it, but perhaps there is some reasoning as to why in infinite measured sets, we need this absolute qualification.  Feel free to weigh in here.]

It is reasonable to want to check the well-defined-ness of this, but I will not do this here since it is available where ever Lebesgue integrals are gone over.  I will also not define the integral of $f + g$ or $\alpha f$ for $\alpha\in {\mathbb R}$, because these should be relatively obvious.

TO BE CONTINUED.