Is there an explicit construction of a Hamel basis of the vector space of real numbers $\mathbb R $ over the field of rational numbers $\mathbb Q $?

14$\begingroup$ Given that the existence of a Hamel basis requires some amount of the Axiom of Choice, I don't think any construction of such a basis can be called entirely "explicit." Does the usual proof that such a basis exists  involving a wellordering of the reals  not satisfy your criterion for "explicit definition?" $\endgroup$ – Noah Schweber Nov 14 '10 at 19:40

4$\begingroup$ Noah, different wellorderings of $\mathbb{R}$ may have different descriptive settheoretic complexities. It's not like every wellorder is an enigma that we cannot understand. Some models of set theory have relatively tame wellorders of $\mathbb{R}$, others do not. So the question can be taken as: what is the descriptive settheoretic complexity of a Hamel basis. The answer is highly independent of ZFC, but settled by large cardinals. $\endgroup$ – Joel David Hamkins Nov 14 '10 at 20:04

3$\begingroup$ While Joel has found an interesting way to interpret the question, I think this says more about his version than about the original. $\endgroup$ – Yemon Choi Nov 14 '10 at 20:29

$\begingroup$ @Joel: I was aware of that, and it's a fair point. I'm just not sure that $\Delta^1_2$ satisfies (my, at least) intuitive notion of "explicit," especially when "explicit" is modifying "construction." To be fair, if I understand the result correctly, we can construct a pair of formulas $\phi$ and $\psi$ such that $\phi$ is $\Pi^1_2$, $\psi$ is $\Sigma^1_2$, and (under some settheoretic assumptions) we have that $\phi$ and $\psi$ are equivalent and define a wellordering of the reals, so that may constitute an explicit construction? $\endgroup$ – Noah Schweber Nov 14 '10 at 20:34

2$\begingroup$ Michael, you need at least some AC for this space, since it is consistent with ZF (assuming some amount of consistency) that there is no Hamel basis for $\mathbb{R}$ over $\mathbb{Q}$, as the existence of such a basis implies the existence of a nonLebesgue measurable set. $\endgroup$ – Joel David Hamkins Nov 16 '10 at 16:48
It is consistent with the axioms of ZFC that there is a Hamel basis of $\mathbb{R}$ over $\mathbb{Q}$ with complexity $\Delta^1_2$ in the descriptive set theoretic hierarchy. This is true, for example, in the constructible universe $L$, where there is a $\Delta^1_2$ wellordering of the reals, as I explain in this MO answer, which is closely related to this question. Complexity $\Delta^1_2$ is a surprisingly low complexity, since such a set (and its complement) can both be obtained by starting with a certain closed set in $\mathbb{R}^3$, projecting it to $\mathbb{R}^2$, taking the complement, and projecting down to $\mathbb{R}$, and so it would seem to count as fairly explicit.
Meanwhile, there can never be a Hamel basis of $\mathbb{R}$ over $\mathbb{Q}$ that is Borel, that is, with complexity $\Delta^1_1$, since from any Borel Hamel basis one can produce a nonLebesgue measurable set of the same complexity by the Vitali argument (remove an element, take the span of the other elements, and consider its cosets). But of course every Borel set is Lebesgue measurable.
At the same time, it is a consequence of the existence of large cardinals that every projective set of reals is Lebesgue measurable, and in this case, there can be no projective Hamel basis for $\mathbb{R}$ over $\mathbb{Q}$, again by the Vitali argument. The projective hierarchy of sets arises by closing the Borel sets under continuous images, as well as complements, countable unions and intersections. Thus, in such a situation, there can be no easilydescribed Hamel basis for $\mathbb{R}$ over $\mathbb{Q}$.

2$\begingroup$ OK, what is the closed subset of $\mathbb{R}^3$? (sorry for being such a jerk...) $\endgroup$ – Sheikraisinrollbank Nov 15 '10 at 15:12

$\begingroup$ Sheikraisin, the construction is only guaranteed to work in the settheoretic universe $L$, and the description of the wellorder (and hence the Hamel basis) makes use of the detailed structure of that universe (so it won't really be comprehensible without knowledge of the structure of $L$). The closed set corresponds to the realquantifier free part $\psi(x,y,z)$ of the $\Sigma^1_2$ description $\varphi(x)\iff\exists y\forall z\ \neg\psi(x,y,z)$. We may assume that $\psi$ has complexity $\Pi^0_1$, which means it describes a closed set in $\mathbb{R}^3$. $\endgroup$ – Joel David Hamkins Nov 15 '10 at 17:12

3$\begingroup$ I think you and I are using different definitions of the word "explicit". There isn't any pornography made by logicians, is there? $\endgroup$ – Sheikraisinrollbank Nov 17 '10 at 13:06

$\begingroup$ Oh yes, there is some here mathoverflow.net/questions/45951/sexyvacuity and here mathoverflow.net/questions/1924/… and here mathoverflow.net/questions/11540…. $\endgroup$ – Joel David Hamkins Nov 17 '10 at 14:59
If you have such a basis, you also have a subspace of codimension 1, and this turns out to be a Vitali set, that is quite a nonconstructible object. For details, e.g. check this answer and this.
Arnie Miller has shown that if V=L then one can do a bit better than what Joel said; there will be a $\Pi^1_1$ Hamel basis for the reals over the rationals. The reference is "Infinite combinatorics and definability," Annals of Pure and Applied Logic 41 (1989) 179203. This paper also improves the complexity bound from $\Delta^1_2$ to $\Pi^1_1$ for several other constructions under the hypothesis V=L.

$\begingroup$ Is this a general method whenever there is a $\Delta^1_2$ wellordering of $\mathbb{R}$, or does it use more of the $V=L$ hypothesis? $\endgroup$ – Joel David Hamkins Nov 14 '10 at 23:18

1$\begingroup$ @Andreas: I read Miller's paper years ago, so I do not remember the details. Do you know if, from his techniques, similar results can be obtained higher up in the projective hierarchy starting with suitable versions of K? $\endgroup$ – Andrés E. Caicedo Nov 14 '10 at 23:30

1$\begingroup$ @Andres: I don't remember the details, but I think Arnie's central idea here was to (recursively) code levels of the L hierarchy into the Hamel base. On the one hand, coding becomes easier higher in the hierarchy, but on the other hand you'll have to code more complicated things (like mice). My guess is that the benefits at least match the burdens, so that the construction will continue to work, but that's only a guess. $\endgroup$ – Andreas Blass Nov 15 '10 at 13:56

1$\begingroup$ I'm confused. Suppose $A$ is a $\Pi_1^1$ Hamel basis. It seems to me that: * with out loss of generality we may assume 1 is in $A$. * Let $B$ be the rational span of $A\setminus\{1\}$, then $B$ is still $\Pi_1^1$. Hence, Lebesque measurable. * Every real can be uniquely written as the sum of an element of $B$ plus a rational. But then the Vitali argument tell us $B$ is no measurable. Where is my mistake? $\endgroup$ – Dave Marker Nov 16 '10 at 15:36

4$\begingroup$ Dave, isn't your set $B$ actually $\Sigma^1_2$? That is, $z\in B$ iff $\exists \vec x\in A$ such that $z$ is rational linear combination of $\vec x$. $\endgroup$ – Joel David Hamkins Nov 16 '10 at 18:36
Re Andreas' comment, I have a writeup of a generalization of Miller's result: https://ivv5hpp.unimuenster.de/u/rds/talks_kiel.pdf

$\begingroup$ I think you should be commended for using "writeup" in the literal sense! I will also join others in warmly welcoming you to MO! $\endgroup$ – François G. Dorais♦ Sep 14 '17 at 19:48
