Does anyone have a simple proof of the uncountability of bases of the vector space of all functions $f : \mathbb{N} \to \mathbb{R}$. I have seen a proof which uses the determinant of the Vandermonde matrix to show the linear independence of functions of the form $f_c=c^n$ but I believe that there might be a simpler one that doesn't require the use of matrices.

I have attached a link of another proof that I found online but I find the use of the limit unsettling. https://minhyongkim.wordpress.com/2013/10/23/a-vector-space-of-uncountable-dimension/

  • 2
    $\begingroup$ Zorn's lemma gives you the existence of a basis. Not the fact that it is uncountable. $\endgroup$
    – Asaf Karagila
    Feb 12, 2017 at 14:29
  • $\begingroup$ I was thinking along the lines of finding an uncountable linearly independent set of functions which implies that the bases cannot be countable. $\endgroup$
    – Jhon Doe
    Feb 12, 2017 at 14:43
  • 1
    $\begingroup$ And Zorn's lemma would help you how? $\endgroup$
    – Asaf Karagila
    Feb 12, 2017 at 14:53
  • $\begingroup$ @AsafKaragila: I think he simply mean that Zorn's Lemma guarantees that every linearly independent set we find is a subset of a basis. $\endgroup$ Feb 12, 2017 at 14:56

4 Answers 4


Here is a diaginalisation argument.

Let $\{f_i\}$ be a countable set we find $g\not \in span \{f_i\} $.

Construct $g$ as follows.

Look at the vector $$(f_0(0), f_0(1))$$ define $(g(0),g(1))$ not to be a linear multiple of this vector. Now look at the vectors

$$(f_0(2), f_0(3), f_0(4))$$ $$(f_1(2), f_1(3), f_1(4))$$ define $(g(2),g(3),g(4))$ not a linear combination of these vectors. Now look at the vectors $$(f_0(5), f_0(6), f_0(7),f_0(8))$$ $$(f_1(5), f_1(6), f_1(7),f_1(8))$$ $$(f_2(5), f_2(6), f_2(7),f_2(8))$$

define $(g(5),g(6),g(7),g(8))$ not in the span of these three vectors, etc. I think the construction in clear, and $g$ is not in the span. Thus there is no countable basis.

  • $\begingroup$ That's a nice argument! $\endgroup$ Feb 12, 2017 at 14:49
  • $\begingroup$ Sry i can't see how g is not in the span. $\endgroup$
    – Jhon Doe
    Feb 12, 2017 at 14:50
  • 5
    $\begingroup$ @JhonDeo: If it's in the span, then by definition is has to be in the span of finitely many of the $f_i$s. And there's a sequence of elements of $g$ that have been chosen explicitly not to be in the span of the first $n$ vectors, for any $n$. $\endgroup$ Feb 12, 2017 at 14:52
  • $\begingroup$ @JhonDeo $g$ not in the span of $f_0$ since the first two coordinates of $g$ is not a multiple of the first two of $f_0$. $g$ is not in the span of $\{f_0,f_1\}$ since the coordinates $g(2),g(3),g(4)$ is not in the span or the same coordinates for $\{f_0,f_1\}$ etc. $\endgroup$ Feb 12, 2017 at 14:53
  • $\begingroup$ @Henning Makholm, what does mean "not to be linear multiple of this vector"? $\endgroup$
    – ZFR
    Nov 15, 2019 at 0:51

There are uncountably many functions $\mathbb N\to\{0,1\}$. Well-order them all, and then remove each one that is a (finite) linear combination of vectors that come earlier in the well-order. The result is, by contruction, a linearly independent set in your vector space. How large is it?

I claim that each of the removed vectors is not just a linear combination of vectors that remain, but a rational linear combination of such vectors. In each case, when we express the new vector as a linear combination of finitely many already-accepted ones, we have to solve an equation involving a matrix that is infinitely tall but has finite width. But because all elements are either $0$ or $1$, there are actually only finitely many different rows in the matrix, so we can find the coefficients by doing ordinary finite-dimensional linear algebra over $\mathbb Q$.

Now, if the reduced set of $0,1$-vectors were countable, there would be only countably many different finite rational combinations of them -- but this contradicts the fact that there are uncountably many vectors to express.

So we have an uncountable linearly independent set in your vector space, and if we extend that to a basis, we get an uncountable basis.


I don't have a proof with Zorn's Lemma, but probably you like this one aswell:

The space you consider contains $\ell^\infty$, the space of bounded sequences, so if we can show that this space has an uncountable base the same is true for the space of all sequences.

The space $\ell^\infty$ can be made a Banach-space if we consider the supremum-norm on it. But infinite dimensional Banach-spaces can't have a countable Hamel-Base which is due to Baire's theorem.

If $(b_n)_{n\in\mathbb N}$ was a Hamel-base of $\ell^\infty$ then $\ell^\infty = \bigcup_{n\in\mathbb N}\operatorname{span}(b_1,...,b_n)$. Baire's theorem tells us that one of the sets in the union has nonempty interior, thus is all of $\ell^\infty$ because it is also a subspace. This is a contradiction because it would make $\ell^\infty$ finite-dimensional.

  • $\begingroup$ Thanks I have seen this proof. However, I try to avoid such proofs as i have not learnt stuff like Banach Spaces and Hamel-base $\endgroup$
    – Jhon Doe
    Feb 12, 2017 at 14:39

One easy way is the following, find a norm which makes the space complete and then uses baire theorem. Zorn's lemma implies that exist a basis, baire theorem implies it must be uncountable

  • $\begingroup$ How do you find such a norm? $\endgroup$
    – Asaf Karagila
    Feb 13, 2017 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.