# Countable/uncountable basis of vector space

I've stumbled upon this exercise in algebra book, in chapter dealing with vector spaces' dimensions.

Prove that basis of the field of real numbers $\mathbb R$ as vector space over the field of rational numbers $\mathbb Q$ is not countable.

Book doesn't cover terms "countable" and "uncountable" and I'm not able to put web info about these topics into something useful for this exercise.

updated:

After receiving great answer by Asaf Karagila, which I unfortunately cannot fully comprehend, I've come with my own idea of proof.

Let's count all real numbers in this situation. We have countable basis, and any vector of vector space $\mathbb R$ can have only finite subset of coefficients in it not equal to zero. We can pick different combination of finite coefficients which will not be equal to zero with countable number of ways (Asaf Karagila's fact III). So, already we have countable number of different ways to choose single vector. But more than that, in every choosen finite set of the coefficients every one of it will be different from vector to vector. Every coefficient can be one different value taken from countable $\mathbb Q$ set, and we have finite number of coefficients for any finite set choosen earlier. To sum up, we have countable number of ways to choose set of coefficients for any vector, and finite number of countable sequent ways to choose concrete values for each coefficient in basis representation of vector. We've got Cartesian product of (finite + 1) = finite countable sets, which is countable set again (property of countable set). So, we conclude that there are countable number of different real numbers, and that's wrong, so the basis of vector space $\mathbb R$ cannot be countable.

I have very strong doubts about it though. Please correct me and point to unclear parts of it.

-
Related is an explicit construction of such an uncountable linearly independent set: mathoverflow.net/questions/23202/… –  Myself Dec 16 '11 at 2:07

Definition: $A$ is a countable set if there exists a function $f\colon A\to\mathbb N$ which is a injective. If $A$ is not countable we say that $A$ is uncountable.

Fact I: The set $\mathbb Q$ of the rational numbers is countable.

Fact II: The set of the real numbers, $\mathbb R$ is uncountable. Furthermore, there is a bijection between the set $\mathbb R$ and $\{A\mid A\subseteq\mathbb N\}$ and the collection of sequences of natural numbers.

Fact III: If $A$ is countable then the set of all finite subsets of $A$ is countable too.

Suppose that $\mathbb R$ was of a countable dimension over $\mathbb Q$, this means that there was a countable set $\{x_i\mid i\in\mathbb N\}$ such that every real number is a linear combination over $\mathbb Q$ of a finite set of $x_i$'s.

However the collection of finite subsets of a countable set is countable. In particular we have that the span of countably many real number over $\mathbb Q$ is countable. The real numbers, however, are uncountable. Therefore the dimension cannot be countable!

-
Thank you very much for your answer, it makes things much more clear. But I don't understand some links. First of all, why are there words "finite set of x_i's" related to linear combination? Shouldn't it be "countable set of x_i's", like in the middle of sentence? –  furikuretsu Dec 16 '11 at 0:24
@furikuretsu: Linear combinations are, by definition, sums of finitely many elements from a given set. So every set can be identified with the finitely many elements which generate it along with their coefficients. Both are finite subsets of a countable set. –  Asaf Karagila Dec 16 '11 at 0:26
Thank you for your great support, but I'm feeling that second sentence and third sentence of your last comment confused me even more. I need to do some research with great solutions you've already provided. –  furikuretsu Dec 16 '11 at 1:41
@Asaf: Careful: "countable" is often used to mean "finite or denumerably infinite"; under that meaning, your first definition should say that $f$ is an injection, not a bijection. –  Arturo Magidin Dec 16 '11 at 6:43
@furikuretsu: One of the properties of a basis is that there is a unique linear combination to generate every element. This means that every element of the space is determined exactly by a sequence of coefficients, which only finitely many of them are nonzero. –  Asaf Karagila Dec 16 '11 at 8:11

I am posting this as an answer because it is too long for a comment. I thought that it might be interesting for you to know that the basis is not only uncountable, it has cardinality $\mathfrak c=2^{\aleph_0}$.

If you search for "hamel basis" "R over Q" at google or google books you'll probably find many proofs that the basis is uncountable and, moreover, that the cardinality is $\mathfrak c$.

For example:

A detailed proof that the cardinality of each Hamel basis of $\mathbb R$ over $\mathbb Q$ is $\mathfrak c$ is given in Theorem 4.2.3 in Kuczma's book An introduction to the theory of functional equations and inequalities.