Is it possible to exhibit a (Hamel) basis for the vector space l^infinity, given by the bounded sequences of real numbers?

6$\begingroup$ My guess is, "not without the axiom of choice." $\endgroup$ – Qiaochu Yuan Nov 13 '09 at 2:48

2$\begingroup$ To expand on Qiaochu's comment: what precisely do you mean by "exhibit"? If you're asking whether there EXISTS a basis for l^infinity, then presumably you know the answer (assuming the axiom of choice). One way to make your question precise is this: do some specific axioms for set theory, excluding Choice, imply the existence of a basis for l^infinity? $\endgroup$ – Tom Leinster Nov 13 '09 at 3:03

$\begingroup$ It could also mean "give an explicit description of such a basis" (rather than simply proving that one exists); that's usually how I interpret the verb "exhibit" in mathematics. $\endgroup$ – Darsh Ranjan Nov 13 '09 at 3:42

1$\begingroup$ Darsh, I agree. But then the question becomes: what precisely does "explicit" mean? It's still not at the level of a wellposed mathematical question. Anyway, along with Qiaochu, I suspect that however you formalize the original question ("Is it possible to exhibit a basis?"), the answer is "no". $\endgroup$ – Tom Leinster Nov 13 '09 at 3:52

3$\begingroup$ A bit of googling reveals the existence of a theorem stating that it is consistent with ZF set theory (without the axiom of choice) that $\mathbb{R}$ has no Hamel basis over $\mathbb{Q}$. Which does not answer the question, but it lends a small bit of support to a “no” answer. $\endgroup$ – Harald HancheOlsen Nov 13 '09 at 4:03
The question is about the complexity of the simplest possible Hamel basis of l^infty, and this is a perfectly sensible thing to ask about even in a context where one wants to retain the Axiom of Choice. That is, we know by AC that there is a basishow complex must it be?
Such a question finds a natural home in descriptive set theory, a subject concerned with numerous similar complexity issues. In particular, descriptive set theory provides tools to make the question precise.
My answer is that one can never prove a negative answer to the question, because it is consistent with the ZFC axioms of set theory that Yes, one can concretely exhibit a Hamel basis of l^infty.
To explain, one natural way to measure the complexity of sets of reals (or subsets of R^infty) is with the projective hierarchy. This is the hierarchy that begins with the closed sets (in R, say, or in R^omega), and then iteratively closes under complements and projections (or equivalently, continuous images). The Borel sets appear near the bottom of this hierarchy, at the level called Delta^{1}_{1}, and then the analytic sets Sigma^{1}_{1} and coanalytic sets Pi^{1}_{1}, and so on up the hierarchy. Sets in the projective hierarchy are exactly those sets that can be given by explicit definition in the structure of the reals, with quantification only over reals and over natural numbers. If we were to find a projective Hamel basis, then it will have been exhibited in a way that is concrete, free of arbitrary choices. Thus, a very natural way of making the question precise is to ask:
Question. Does l^infty have a Hamel basis that is projective?
If the axioms of set theory are consistent, then they are consistent with a positive answer to this question. This is not quite the same as proving a positive answer, to be sure, but it does mean that noone will ever prove a negative answer to the question.
Theorem. If the axioms of ZFC are consistent, then they are consistent with the existence of a projective Hamel basis for l^infty. Indeed, there can be such a basis with complexity Pi^{1}_{3}.
Proof. I will prove that under the settheoretic assumption known as the Axiom of Constructibility V=L, there is a projective Hamel basis. In my answer to question about Wellorderings of the reals, I explained that in Goedel's constructible universe L, there is a definable wellordering of the reals. This wellordering has complexity Delta^{1}_{2} in the projective hierarchy. From this wellordering, one can easily construct a wellordering of l^infty, since infinite sequences of reals are coded naturally by reals. Now, given the wellordering of l^infty, one defines the Hamel basis as usual by taking all elements not in the span of elements preceding it in the wellorder. The point for this question is that if the wellorder has complexity Delta^{1}_{2}, then this definition of the basis has complexity Pi^{1}_{3}, as desired. QED
OK, so we can write down a definition, and in some settheoretic universes, this definition concretely exhibits a Hamel basis of l^infty. There is no guarantee, however, that this definition will work in other models of set theory. I suspect that one will be able to find other models of ZFC, in which there is no projective Hamel basis of l^infty. It is already known that there might be no projective well ordering of the reals (a situation that follows from large cardinals and other set theoretic hypotheses), and perhaps this also implies that there is no projective Hamel basis. In this case, it would mean that the possibility of exhibiting a concrete Hamel basis is itself independent of ZFC. This would be an interesting and subtle situation. To be clear, I am not referring here merely to the existence of a basis requiring AC, but rather, fully assuming the Axiom of Choice, I am proposing that the possibility of finding a projective basis is independent of ZFC.
Conjecture. The assertion that there is a projective Hamel basis of l^infty is independent of ZFC.
I only intend to consider the question in models of ZFC, so that l^infty has a Hamel basis of some kind, and the only question is whether there is a projective one or not. In this situation, the fact that AD seems to imply that there is no Hamel basis is not relevent, since that axiom contradicts AC.
Apart from this, I also conjecture that there can never be a Hamel basis of l^infty that is Borel. This would be a lower bound on the complexity of how concretely one could exhibit the basis.
From the preview page of Garnir's Dream Spaces with Hamel Bases, by Norbert Brunner [Arch. Math. Logik 26 (1987), 123126]: "The situation changes completely, if one drops AC and instead assumes e.g. the axiom determinacy AD plus the principle of dependent choices DC. Then every linear map $A:X \to Y$ from a Banach space $X$ into a normed space $Y$ is continuous." (Brunner then says that Garnir establishes this from a weaker hypothesis.) Also, Wikipedia tells me that the axiom of dependent choice implies countable choice, and countable choice implies that every infinite set has a countably infinite subset. If $\ell^\infty$ (or any other infinitedimensional Banach space $X$) has a Hamel basis, this contradicts the above setup. A Hamel basis for an infinitedimensional Banach space $X$ is infinite, and assuming a countably infinite subset, you can make an unbounded and therefore discontinuous linear map from $X$ to $\mathbb{R}$.
(This topic is not my business at all, but maybe I am right as a naive student.)

$\begingroup$ Eric Schechter's book "Handbook of Analysis and its Foundations" (which I've only glanced at) has a lot of discussion of issues closely related to this. In particular, his web page for the book includes statements which point to an argument of the sort you just gave. $\endgroup$ – Mark Meckes Nov 13 '09 at 15:20

4

$\begingroup$ Thanks! :) Seriously, people who know more about it seem to like the answer, and Schechter's book indeed says a lot of things like the above. So maybe the disclaimer is not helpful. $\endgroup$ – Greg Kuperberg Dec 10 '09 at 15:54