Is l2 separable

[ex-xian]

The hilbert space l2, the set of all square summable sequences...is it separble? Separble means that it has a countable dense subset, but I can't find one.

I've googled, and all I find are references to a orthonormal basis, but I don't really follow what that means.

Help...please...

[Undercurrent]

Originally posted by ex-xian
I've googled, and all I find are references to a orthonormal basis, but I don't really follow what that means.

An orthonormal basis of a Hilbert space is a set of elements {e_0, e_1, e_2, e_3, ...} whose span (set of linear combinations of) is dense in the space, and <e_i, e_j> = 0 for i != j, and <e_i, e_i> = 1 for all i. An orthonormal basis for l2 would be:

e_0 = (1, 0, 0, 0, 0, ....)
e_1 = (0, 1, 0, 0, 0, ....)
e_2 = (0, 0, 1, 0, 0, ....)
e_3 = (0, 0, 0, 1, 0, ....)
....

It is stated here (http://en.wikipedia.org/wiki/Separable_space) that any Hilbert space with a countable orthonormal basis is separable, which would make l2 separable since the above basis is countable.

It's been a while since I studied this though, so don't believe me unless you've convinced yourself.

[ex-xian]

Originally posted by Undercurrent
An orthonormal basis of a Hilbert space is a set of elements {e_0, e_1, e_2, e_3, ...} whose span (set of linear combinations of) is dense in the space, and <e_i, e_j> = 0 for i != j, and <e_i, e_i> = 1 for all i. An orthonormal basis for l2 would be:

e_0 = (1, 0, 0, 0, 0, ....)
e_1 = (0, 1, 0, 0, 0, ....)
e_2 = (0, 0, 1, 0, 0, ....)
e_3 = (0, 0, 0, 1, 0, ....)
....

It is stated here (http://en.wikipedia.org/wiki/Separable_space) that any Hilbert space with a countable orthonormal basis is separable, which would make l2 separable since the above basis is countable.

It's been a while since I studied this though, so don't believe me unless you've convinced yourself.
I had seen that definition in a couple of places. If one is going to use the defintion that separable means a set contains a countable dense subset, would the set you've described work?

I don't see how it would, since the sum squared of each set is only 1, so how could any set of out of l2 be less than epsilon in norm?

[Undercurrent]

Originally posted by ex-xian
I had seen that definition in a couple of places. If one is going to use the defintion that separable means a set contains a countable dense subset, would the set you've described work?

That set clearly isn't a countable dense subset, it is a basis. The claimed theorem is countable basis <==> separable, which implies separability because of the countable basis, but the countable dense subset is not the basis itself.

I haven't seen a proof of this theorem, but I suspect the proof would show you how to construct a countable dense subset from a countable basis.

When I first saw your post, I thought that a suitable dense subset would be l2(Q) (the space of square-summable sequences of rationals), since Q is countable and dense in R. But, as it turns out l2(Q) is non-countable, as can be seen from a diagonal argument.

[ex-xian]

Originally posted by Undercurrent
That set clearly isn't a countable dense subset, it is a basis. The claimed theorem is countable basis <==> separable, which implies separability because of the countable basis, but the countable dense subset is not the basis itself.
I see.

I haven't seen a proof of this theorem, but I suspect the proof would show you how to construct a countable dense subset from a countable basis.

When I first saw your post, I thought that a suitable dense subset would be l2(Q) (the space of square-summable sequences of rationals), since Q is countable and dense in R. But, as it turns out l2(Q) is non-countable, as can be seen from a diagonal argument.
That was my first thought also, but I came to the conclusion you did. If you have any more ideas, I'd appreciate them.

[Undercurrent]

Originally posted by ex-xian
That was my first thought also, but I came to the conclusion you did. If you have any more ideas, I'd appreciate them.

Ok, so now you've set me thinking about this thing and pissed off my gf royally what with the suddenly enhanced geekiness and all :) , but I think I have a solution.

The required dense subset is not l2(Q) since that is uncountable, but a slightly modified version, l2(Q)* (notation by me), the set of all sequences from l2(Q) with finite support; that is, every sequence {x_n} of l2(Q)* has some index j such that every x_k == 0 for all k > j. This set is smaller than l2(Q), since it, for example, does not contain the sequence {1/2^n}, which has non-zero elements out to infinity.

Claim: l2(Q)* is countable.

Proof: Define l2(Q)_n to be the set of sequences of rationals where every element of index greater than n equal to zero. Clearly for each n, l2(Q)_n is countable, since it is isomorphic to Q^n, which is a finite Cartesian product of countable sets.

Now l2(Q)* is equal to l2(Q)_0 U l2(Q)_1 U l2(Q)_2 U l2(Q)_3 U .... (where "U" means "union"). This is a countable union of countable sets, so it is itself countable. QED.

Claim: l2(Q)* is dense in l2.

Proof: Let {x_n} be an element of l2, and epsilon > 0. If {x_n} is all zero after an index, N say, it is easy to find a sequence of elements of l2(Q)* that converges to it -- just take elements out of the subset l2(Q)_N whose prefixes converge to the non-zero prefix of {x_n}. Since it converges to {x_n}, there must be an element that is within epsilon of {x_n}.

If {x_n} has non-zero elements for all n, we need to take advantage of the fact that sum{|x_n|^2},n=0..infinity converges to say that there must be some index N for which the tail of of the sum, sum{|x_n|^2},n=N+1..infinity, is less than epsilon/2.

Define then {x'_n} by x'_i = x_i if i <= N, and x'_i = 0 if i > N.

Now we can do what we did in the previous case and find a sequence of elements out of l2(Q)_N whose prefixes converge to the non-zero prefix of {x'_n}. We can pick an element of this sequence that is within epsilon/2 of {x'_n}, call this element {w_n}. So {w_n} is within epsilon/2 of {x'_n} which is within
epsilon/2 of {x_n}, so, by the triangle inequality, {w_n} is within epsilon of {x_n}. And since {x_n} and epsilon were general, this means that l2(Q)* is dense in l2. QED.

[ex-xian]

I had forgotten about this what with learning the new stuff after the switch and some other mod duties I had to attend (ohhh..mysterious).

I think I understand what you're saying, but I have a few questions.

Let a_n=(0,0,0,0,0,10000,0,0,0,...)
How does what sequence out your set works for this?

Or this one,
b_n=(1,1,1,1,0,0,0,...)

[Undercurrent]

I had forgotten about this what with learning the new stuff after the switch and some other mod duties I had to attend (ohhh..mysterious).

I think I understand what you're saying, but I have a few questions.

Let a_n=(0,0,0,0,0,10000,0,0,0,...)
How does what sequence out your set works for this?

Or this one,
b_n=(1,1,1,1,0,0,0,...)

Both a_n and b_n (let me rename them to a and b to avoid the subscript) are both in l2(Q)*. In fact, a is in l2(Q)_6, and b is in l2(Q)_4.

So a trivial sequence (of sequences) all in l2(Q)* that converge to a is {a, a, a, a, a, ...}. Similar for b. (I'm following you to use parentheses for l2 elements and curly braces for sequences of such elements).

A less trivial example would be c = (1, 1/2, 1/3, 1/4, 1/5, ...). This is not in l2(Q)* because it does not terminate, but it is in l2(Q) since its elements are all rational. A sequence of sequences from l2(Q)* that converges to this is:

{
(1, 0, 0, 0, 0, 0, 0, ....),
(1, 1/2, 1/3, 0, 0, 0, 0, ...),
(1, 1/2, 1/3, 1/4, 0, 0, 0, ...),
(1, 1/2, 1/3, 1/4, 1/5, 0, 0, ...),
(1, 1/2, 1/3, 1/4, 1/5, 1/6, 0, ...),
...
}

Since each of these sequences terminates, they are all in l2(Q)*, but they converge to c.

An even less trivial example would be d = pi * c = (pi, pi/2, pi/3, pi/4, pi/5, ...). This element isn't even in l2(Q), so the previous trick doesn't work, but we can still construct a sequence of sequences from l2(Q)* that converge to it by:

{
(3, 0, 0, 0, 0, 0, 0, ...),
(3.1, 3.1/2, 3.1/3, 3.1/4, 0, 0, 0, ...),
(3.14, 3.14/2, 3.14/3, 3.14/4, 3.14/5, 0, 0, ...),
(3.141, 3.141/2, 3.141/3, 3.141/4, 3.141/5, 3.141/6, 0, ...),
...
}

So not only do successive squences use more and more elements from the target sequence (like before), the approximation of pi in the numerator becomes more and more accurate, converging to the right number.

[ex-xian]

Maybe I'm missing something key here, but I don't follow. For l2 to be separable, it has to contain a countable dense subset. You defined the candidate to be the set of all sequences of l2 that contain rational numbers where the terms eventually are all 0's? Or was it the the set of sequences out of l2 such that l2(Q)*_n contains every rational number up to the nth term at which point all the terms are 0's?

If the former, is this set countable? If the latter, I don't follow how it is dense.

Thanks for taking the time to help me with these questions.

Also, do you know how the hilbert space l2 fits with fast fourier transforms?

[Undercurrent]

If the former, is this set countable? If the latter, I don't follow how it is dense.

The former. It is countable since it is a countable union of countable sets (the l2(Q)_n -- do you see why these are countable?).

To see that a countable union of countable sets is itself countable, consider a countably infitite set S of countable sets. Since S is countable, we can enumerate it as {S_0, S_1, S_2, S_3, ...}. Similarly, since each of the S_n is countable, we can enumerate their elements by S_n = {S_n_0, S_n_1, S_n_2, S_n_3, ...}. Write the union of all of the sets as an infinite matrix like:

S_0_0 S_0_1 S_0_2 S_0_3 S_0_4 ...
S_1_0 S_1_1 S_1_2 S_1_3 S_1_4 ...
S_2_0 S_2_1 S_2_2 S_2_3 S_2_4 ...
S_3_0 S_3_1 S_3_2 S_3_3 S_3_4 ...
S_4_0 S_4_1 S_4_2 S_4_3 S_4_4 ...
...

We can enumerate this by taking successive diagonals (you might have seen something similar to this in the proof that the rationals are countable):

S_0_0 S_1_0 S_0_1 S_2_0 S_1_1 S_0_2 S_3_0 S_2_1 S_1_2 S_0_3 ...

(On a blackboard I'd draw a bit more of a diagram to show this, but UUB will have to do here.)

Notably, a countably infinite Cartesian product of countable sets is not itself countable, but it's just a countable union here.

Thanks for taking the time to help me with these questions.

No problem. I'm just an old-school functional analysis geek. I know it.

Also, do you know how the hilbert space l2 fits with fast fourier transforms?

I don't know abut the "fast" part, specifically, but on L2[-pi, pi] (the space of complex-valued Lebesgue-integrable generalized functions on the interval -pi <= x <= pi), the stanard Fourier set, {e_n} = {exp(iwx/n)} that you take fourier expansions with is a basis set for the space. This is a generalization of the concept of a basis for ordinary vector spaces like R^n. The Fourier expansion of a function f is f = Sum {c_i * e_i} where c_i = <e_i, f> where <x, y> is the L2 innner product of x and y.

But you could think of the coefficients of the Fourier expansion as a sequence in l2(C), namely (c_0, c_1, c_2, c_3, ....) and the Fourier transform as a function from L2 to l2 (domains omitted). Using this representation you can start proving things about L2 using what you know about l2. For example, since we've just proven that l2 is separable, you're very close to proving that L2 is separable (i.e. a countable dense set in L2 is the preimage of a countable dense set in l2) which is certainly not obvious otherwise.

[ex-xian]

The former. It is countable since it is a countable union of countable sets (the l2(Q)_n -- do you see why these are countable?).

To see that a countable union of countable sets is itself countable, consider a countably infitite set S of countable sets. Since S is countable, we can enumerate it as {S_0, S_1, S_2, S_3, ...}. Similarly, since each of the S_n is countable, we can enumerate their elements by S_n = {S_n_0, S_n_1, S_n_2, S_n_3, ...}. Write the union of all of the sets as an infinite matrix like:

S_0_0 S_0_1 S_0_2 S_0_3 S_0_4 ...
S_1_0 S_1_1 S_1_2 S_1_3 S_1_4 ...
S_2_0 S_2_1 S_2_2 S_2_3 S_2_4 ...
S_3_0 S_3_1 S_3_2 S_3_3 S_3_4 ...
S_4_0 S_4_1 S_4_2 S_4_3 S_4_4 ...
...

We can enumerate this by taking successive diagonals (you might have seen something similar to this in the proof that the rationals are countable):

S_0_0 S_1_0 S_0_1 S_2_0 S_1_1 S_0_2 S_3_0 S_2_1 S_1_2 S_0_3 ...

(On a blackboard I'd draw a bit more of a diagram to show this, but UUB will have to do here.)

Notably, a countably infinite Cartesian product of countable sets is not itself countable, but it's just a countable union here.
So the following sequences would all be in l2(Q)*?

a=(1, 1/2, 1/3, 1/4, ..., 0,0,0,...)
b=(0,0,0,1, 1/2, 1/3, 1/4, ...., 0,0,0...)
c=(0,0,0,1,1/2,1/3,0,0,0,1/4,...,0,0,0...)

But you arranged the elements of l2(Q)* in an order,
l2(Q)*_0, l2(Q)*_1, l2(Q)*_2, l2(Q)*_3, ...

Is each term of the above sequence a list of sequences itself? That is, would l2(Q)*_n be the set of all sequences that have zeros after the nth term?

[Undercurrent]

So the following sequences would all be in l2(Q)*?

a=(1, 1/2, 1/3, 1/4, ..., 0,0,0,...)
b=(0,0,0,1, 1/2, 1/3, 1/4, ...., 0,0,0...)
c=(0,0,0,1,1/2,1/3,0,0,0,1/4,...,0,0,0...)

Yes, all of them. So long as there is an index after which all of the elements are zero, it's in. There is no guarentee that the sequences will be all non-zero before that index.

But you arranged the elements of l2(Q)* in an order,
l2(Q)*_0, l2(Q)*_1, l2(Q)*_2, l2(Q)*_3, ...

Is each term of the above sequence a list of sequences itself? That is, would l2(Q)*_n be the set of all sequences that have zeros after the nth term?

Remember that we defined l2(Q)_n as the set of all sequneces that terminate before or at the nth index. I have claimed that all of these sets are countable, since they are isomorphic to a finite Cartesian product of countable sets. (BTW, do you believe that statement?)

l2(Q)* is the union of all of the l2(Q)_n. Since there are only a countably infinite number of the l2(Q)_n, this is a countable union of countable sets, and the proof in my last post shows that the common union is itself a countable set, since we can construct an enumeration for it from the enumerations of the subsets.

[ex-xian]

Remember that we defined l2(Q)_n as the set of all sequneces that terminate before or at the nth index. I have claimed that all of these sets are countable, since they are isomorphic to a finite Cartesian product of countable sets. (BTW, do you believe that statement?)
I believe, but I don't follow the proof...I think this is the part I'm having trouble with. If l2(Q)_n is countable for every n a positive integer, then clearly the union of all of them is countable.

If you don't mind, could you state that proof again with more details?

[Undercurrent]

If you don't mind, could you state that proof again with more details?

Ok, do you believe the following statement: The union of countably many finite sets is itself countable.

This is fairly straightforward to prove. An enumeration of the combined set would be an enumeration that goes through the first set, then the second, then the third, &c, in order.

What we can show is that any union of a countably infinite number of countably infinite sets is equal to a union of countably many finite sets. To show this, we use the infinite matrix from my previous post:

S_0_0 S_0_1 S_0_2 S_0_3 S_0_4 ...
S_1_0 S_1_1 S_1_2 S_1_3 S_1_4 ...
S_2_0 S_2_1 S_2_2 S_2_3 S_2_4 ...
S_3_0 S_3_1 S_3_2 S_3_3 S_3_4 ...
S_4_0 S_4_1 S_4_2 S_4_3 S_4_4 ...
...

Recal that S_n is a countably infinte set, and the nth row of this matrix is an enumeration of S_n. Every element in the union of the S_n is shown in this diagram. If I put this diagram in between some curly braces, it would be a picture of the union set that we're worried about. Lets call the combined set W. So W = S_0 U S_1 U S_2 U S_3 U ...

Now consider the diagonals of this diagram. Define the sets D_n by:

D_0 = { S_0_0 }
D_1 = { S_1_0 , S_0_1 }
D_2 = { S_2_0 , S_1_1 , S_0_2 }
D_3 = { S_3_0 , S_2_1 , S_1_2 , S_0_3 }
....

So basically D_n is set of elements on the nth diagonal of the matrix starting from the upper left an proceeding outwards. It is clear that in addition to its previous construction as the union of the S_n, W is also precisely the union of the D_n. That is:

W = D_0 U D_1 U D_2 U D_3 U ....

But the D_n are all finite. And there are only countably many of them. So W is the union of countably many finite sets. And as we said at the top of this post, a union of countably many finite sets is countable, so W is countable.

The only thing we have assumed about W is that it is the union of countably many countably infinite sets, so any union of countably many countably infinite sets is itself countable. QED.

BTW, is this thread at all interesting to the broader community? If not we could take it into PMs.

[ex-xian]

I do follow that if all the l2(Q)*'s are countable, then the union of all of them is countable. What I'm not following is that any particular element, l2(Q)*_n, is countable. If your above proof showed this, tell me and I'll try to see it.

BTW, is this thread at all interesting to the broader community? If not we could take it into PMs.
The PM format since the change to vb3 isn't all that great, IMO. I think it's fine to discuss this in this thread.

[Undercurrent]

I do follow that if all the l2(Q)*'s are countable, then the union of all of them is countable. What I'm not following is that any particular element, l2(Q)*_n, is countable. If your above proof showed this, tell me and I'll try to see it.

I misunderstood where your misunderastanding lies. My last post is a proof that the countable union of countable sets is countable. Now to show that every l2(Q)_n is countable

Consider a particular l2(Q)_n. Since all of the sequences in this set terminate after the nth index, we can construct a bijection between l2(Q)_n and the Cartesian product of n copies of Q (that is Q^n) by:

(x_1, x_2, x_3, ... , x_n, 0, 0, 0, ....) <---> (x_1, x_2, x_3, ... , x_n)

This means that if Q^n is countable, so is l2(Q)_n.

To see that Q^n is countable, first note that Q is countable. If it is true that a finite Cartesian product of countable sets is countable, then Q^n is countable and therefore so is l2(Q)_n. So we set to prove that.

Lemma: The Cartesian product of two countably infinite sets is countable.

(Sketch) Proof: Let A = {A_0, A_1, A_2, ...} and B = {B_0, B_1, B_2, ... } be two countable sets. Then we car write the Cartesian product A x B in a table similar to the previous proof as:

A x B = {
(A_0, B_0) , (A_0, B_1) , (A_0, B_2) , (A_0, B_3) , ....
(A_1, B_0) , (A_1, B_1) , (A_1, B_2) , (A_1, B_3) , ....
(A_2, B_0) , (A_2, B_1) , (A_2, B_2) , (A_2, B_3) , ....
(A_3, B_0) , (A_3, B_1) , (A_3, B_2) , (A_3, B_3) , ....
...
}

Using an argument with the diagonals like we did in my previous post, we see that this is countable. QED.

In fact this is very similar to the way that one proves that Q is countable in the first place.

Now the proof that any finite Cartesian products of countable sets are countable follows by induction:

Theorem: A Caretsian product of a finite number countably infinite sets is itself countable.

Proof: As a basis case, note that a Cartesian product of one countable set is trivially countable.

Now suppose as an inductive hypothesis that a Cartesian product of k countably infinte sets is countable. Consider a Cartesian product of k+1 countably infinte sets:

S_1 x S_2 x S_3 x ... x S_k x S_(k+1)

Because the Cartesian product is associative then we can write this expression in two factors (indicated by curly braces) as:

{S_1 x S_2 x S_3 x ... x S_k} x {S_(k+1)}

The former term is countable by the inductive hypothesis, and the latter is countable by the basis, so this is the Cartesian product of two countable sets. By the lemma, this product is itself countable.

So, by induction on the number of factors in the Cartesian product, any finite Cartesian product of countably infinite sets is countable. QED.

So, as a special case when all of the S_n are Q, Q^n is countable, so l2(Q)_n is countable.