I know that the proof that every vector space has a basis uses the Axiom of Choice, or Zorn's Lemma. If we consider an axiom system without the Axiom of Choice, are there vector spaces that provably have no basis?
Linear Algebra – Vector Spaces and Axiom of Choice
axiom-of-choicehamel-basislinear algebravector-spaces
Related Solutions
If $k$ is a field and $V$ is an infinite dimensional $k$-vector space, then $V\cong V\oplus V$. Using this, what you want to show follows from the fact that as $\mathbb Q$-vector spaces, $\mathbb C\cong \mathbb R\oplus \mathbb R$.
Can you see how to prove those two claims?
Later. Ok, apparently not. Let's do it.
(1) If $B$ is a basis for $V$, then the set $$B'=\{(b,0):b\in B\}\cup \{(0,b):b\in B\}$$ is a basis for $V\oplus V$. There is an obvious bijection $B'\cong \{1,2\}\times B$.
Now, if $X$ is an infinite set, then $X$ and $\{1,2\}\times X$ are in bijection. It follows from this that there is a bijection between the basis $B$ of $V$ and the basis $B'$ of $V\oplus V$. As you know, this implies that there is a linear isomorphism between $V$ and $V\oplus V$. This proves my first claim above.
(2) Consider the map $$\phi:a+bi\in\mathbb C\mapsto (a,b)\in\mathbb R\oplus\mathbb R.$$ It is very easy to show that it is an isomorphism of $\mathbb Q$-vector spaces, so that $\mathbb C\cong\mathbb R\oplus\mathbb R$, as my second claim states.
(3) Finally, let's prove your claim that if $\mathbb R$ and $\mathbb C$ are isomorphic $\mathbb Q$-vector spaces: since $\mathbb R$ is a $\mathbb Q$-vector space of infinite dimensions, my first claim tells us that $\mathbb R\cong\mathbb R\oplus\mathbb R$ as $\mathbb Q$-vector spaces. On the other hand, my second claim tells us that $\mathbb R\oplus\mathbb R\cong\mathbb C$ as $\mathbb Q$-vector spaces. Transitivity, then, allows us to conclude that $\mathbb R\cong\mathbb C$ as $\mathbb Q$-vector spaces.
Nov. 6th, 2011 After several long months a post on MathOverflow pushed me to reconsider this math, and I have found a mistake. The claim was still true, as shown by Läuchli $\small[1]$, however despite trying to do my best to understand the argument for this specific claim, it eluded me for several days. I then proceeded to construct my own proof, this time errors free - or so I hope. While at it, I am revising the writing style.
Jul. 21st, 2012 While reviewing this proof again it was apparent that its most prominent use in generating such space over the field of two elements fails, as the third lemma implicitly assumed $x+x\neq x$. Now this has been corrected and the proof is truly complete.
$\newcommand{\sym}{\operatorname{sym}} \newcommand{\fix}{\operatorname{fix}} \newcommand{\span}{\operatorname{span}} \newcommand{\im}{\operatorname{Im}} \newcommand{\Id}{\operatorname{Id}} $
I got it! The answer is that you can construct such vector space.
I will assume that you are familiar with ZFA and the construction of permutation models, references can be found in Jech's Set Theory $\small[2, \text{Ch}. 15]$ as well The Axiom of Choice $\small{[3]}$. Any questions are welcomed.
Some notations, if $x\in V$ which is assumed to be a model of ZFC+Atoms then:
- $\sym(x) =\{\pi\in\mathscr{G} \mid \pi x = x\}$, and
- $\fix(x) = \{\pi\in\mathscr{G} \mid \forall y\in x:\ \pi y = y\}$
Definition: Suppose $G$ is a group, $\mathcal{F}\subseteq\mathcal{P}(G)$ is a normal subgroups filter if:
- $G\in\mathcal{F}$;
- $H,K$ are subgroups of $G$ such that $H\subseteq K$, then $H\in\mathcal{F}$ implies $K\in\mathcal{F}$;
- $H,K$ are subgroups of $G$ such that $H,K\in\mathcal{F}$ then $H\cap K\in\mathcal{F}$;
- ${1}\notin\mathcal{F}$ (non-triviality);
- For every $H\in\mathcal{F}$ and $g\in G$ then $g^{-1}Hg\in\mathcal{F}$ (normality).
Now consider the normal subgroups-filter $\mathcal{F}$ to be generated by the subgroups $\fix(E)$ for $E\in I$, where $I$ is an ideal of sets of atoms (closed under finite unions, intersections and subsets).
Basics of permutation models:
A permutation model is a transitive subclass of the universe $V$ that for every ordinal $\alpha$, we have $x\in\mathfrak{U}\cap V_{\alpha+1}$ if and only if $x\subseteq\mathfrak{U}\cap V_\alpha$ and $\sym(x)\in\mathcal{F}$.
The latter property is known as being symmetric (with respect to $\mathcal{F}$) and $x$ being in the permutation model means that $x$ is hereditarily symmetric. (Of course at limit stages take limits, and start with the empty set)
If $\mathcal{F}$ was generated by some ideal of sets $I$, then if $x$ is symmetric with respect to $\mathcal{F}$ it means that for some $E\in I$ we have $\fix(E)\subseteq\sym(x)$. In this case we say that $E$ is a support of $x$.
Note that if $E$ is a support of $x$ and $E\subseteq E'$ then $E'$ is also a support of $x$, since $\fix(E')\subseteq\fix(E)$.
Lastly if $f$ is a function in $\mathfrak{U}$ and $\pi$ is a permutation in $G$ then $\pi(f(x)) = (\pi f)(\pi x)$.
Start with $V$ a model of ZFC+Atoms, assuming there are infinitely (countably should be enough) many atoms. $A$ is the set of atoms, endow it with operations that make it a vector space over a field $\mathbb{F}$ (If we only assume countably many atoms, we should assume the field is countable too. Since we are interested in $\mathbb F_2$ this assertion is not a big hassle). Now consider $\mathscr{G}$ the group of all linear automorphisms of $A$, each can be extended uniquely to an automorphism of $V$.
Now consider the normal subgroups-filter $\mathcal{F}$ to be generated by the subgroups $\fix(E)$ for $E\in I$, where $E$ a finite set of atoms. Note that since all the permutations are linear they extend unique to $\span(E)$. In the case where $\mathbb F$, our field, is finite then so is this span.
Let $\mathfrak{U}$ be the permutation model generated by $\mathscr{G}$ and $\mathcal{F}$.
Lemma I: Suppose $E$ is a finite set, and $u,v$ are two vectors such that $v\notin\span(E\cup\{u\})$ and $u\notin\span(E\cup\{v\})$ (in which case we say that $u$ and $v$ are linearly independent over $E$), then there is a permutation which fixes $E$ and permutes $u$ with $v$.
Proof: Without loss of generality we can assume that $E$ is linearly independent, otherwise take a subset of $E$ which is. Since $E\cup\{u,v\}$ is linearly independent we can (in $V$) extend it to a base of $A$, and define a permutation of this base which fixes $E$, permutes $u$ and $v$. This extends uniquely to a linear permutation $\pi\in\fix(E)$ as needed. $\square$
Lemma II: In $\mathfrak{U}$, $A$ is a vector space over $\mathbb F$, and if $W\in\mathfrak{U}$ is a linear proper subspace then $W$ has a finite dimension.
Proof: Suppose $W$ is as above, let $E$ be a support of $W$. If $W\subseteq\span(E)$ then we are done. Otherwise take $u\notin W\cup \span(E)$ and $v\in W\setminus \span(E)$ and permute $u$ and $v$ while fixing $E$, denote the linear permutation with $\pi$. It is clear that $\pi\in\fix(E)$ but $\pi(W)\neq W$, in contradiction. $\square$
Lemma III: If $T\in\mathfrak{U}$ is a linear endomorphism of $A$, and $E$ is a support of $T$ then $x\in\span(E)\Leftrightarrow Tx\in\span(E)$, or $Tx=0$.
Proof: First for $x\in \span(E)$, if $Tx\notin\span(E)$ for some $Tx\neq u\notin\span(E)$ let $\pi$ be a linear automorphism of $A$ which fixes $E$ and $\pi(Tx)=u$. We have, if so:
$$u=\pi(Tx)=(\pi T)(\pi x) = Tx\neq u$$
On the other hand, if $x\notin\span(E)$ and $Tx\in\span(E)$ and if $Tx=Tu$ for some $x\neq u$ for $u\notin\span(E)$, in which case we have that $x+u\neq x$ set $\pi$ an automorphism which fixes $E$ and $\pi(x)=x+u$, now we have: $$Tx = \pi(Tx) = (\pi T)(\pi x) = T(x+u) = Tx+Tu$$ Therefore $Tx=0$.
Otherwise for all $u\neq x$ we have $Tu\neq Tx$. Let $\pi$ be an automorphism fixing $E$ such that $\pi(x)=u$ for some $u\notin\span(E)$, and we have: $$Tx=\pi(Tx)=(\pi T)(\pi x) = Tu$$ this is a contradiction, so this case is impossible. $\square$
Theorem: if $T\in\mathfrak{U}$ is an endomorphism of $A$ then for some $\lambda\in\mathbb F$ we have $Tx=\lambda x$ for all $x\in A$.
Proof:
Assume that $T\neq 0$, so it has a nontrivial image. Let $E$ be a support of $T$. If $\ker(T)$ is nontrivial then it is a proper subspace, thus for a finite set of atoms $B$ we have $\span(B)=\ker(T)$. Without loss of generality, $B\subseteq E$, otherwise $E\cup B$ is also a support of $T$.
For every $v\notin\span(E)$ we have $Tv\notin\span(E)$. However, $E_v = E\cup\{v\}$ is also a support of $T$. Therefore restricting $T$ to $E_v$ yields that $Tv=\lambda v$ for some $\lambda\in\mathbb F$.
Let $v,u\notin\span(E)$ linearly independent over $\span(E)$. We have that: $Tu=\alpha u, Tv=\mu v$, and $v+u\notin\span(E)$ so $T(v+u)=\lambda(v+u)$, for $\lambda\in\mathbb F$. $$\begin{align} 0&=T(0) \\ &= T(u+v-u-v)\\ &=T(u+v)-Tu-Tv \\ &=\lambda(u+v)-\alpha u-\mu v=(\lambda-\alpha)u+(\lambda-\mu)v \end{align}$$ Since $u,v$ are linearly independent we have $\alpha=\lambda=\mu$. Due to the fact that for every $u,v\notin\span(E)$ we can find $x$ which is linearly independent over $\span(E)$ both with $u$ and $v$ we can conclude that for $x\notin E$ we have $Tx=\lambda x$.
For $v\in\span(E)$ let $x\notin\span(E)$, we have that $v+x\notin\span(E)$ and therefore: $$\begin{align} Tx &= T(x+u - u)\\ &=T(x+u)-T(u)\\ &=\lambda(x+u)-\lambda u = \lambda x \end{align}$$
We have concluded, if so that $T=\lambda x$ for some $\lambda\in\mathbb F$. $\square$
Set $\mathbb F=\mathbb F_2$ the field with two elements and we have created ourselves a vector space without any nontrivial automorphisms. However, one last problem remains. This construction was carried out in ZF+Atoms, while we want to have it without atoms. For this simply use the Jech-Sochor embedding theorem $\small[3, \text{Th}. 6.1, \text p. 85]$, and by setting $\alpha>4$ it should be that any endomorphism is transferred to the model of ZF created by this theorem.
(Many thanks to t.b. which helped me translating parts of the original paper of Läuchli.
Additional thanks to Uri Abraham for noting that an operator need not be injective in order to be surjective, resulting a shorter proof.)
Bibliography
Läuchli, H. Auswahlaxiom in der Algebra. Commentarii Mathematici Helvetici, vol 37, pp. 1-19.
Jech, T. Set Theory, 3rd millennium ed., Springer (2003).
Jech, T. The Axiom of Choice. North-Holland (1973).
Best Answer
If you only consider a system without the axiom of choice you cannot prove that there is such vector space, simply because while you are not assuming AC -- it might still be true.
However Andreas Blass proved in 1984 that if every vector space has a basis then the axiom of choice holds [1]. In particular it means that if you assume the axiom of choice fails then there is provably a space without a basis.
Semi-constructively, the proof given by Blass uses the equivalence (in ZF) between the axiom of choice the axiom of multiple choice.
Blass used this equivalence as follows: given a family of non-empty sets he defines a vector space using this family and by the existence of a basis he constructs $F$ showing that AMC holds.
If we assume the axiom of choice fails, then also AMC fails in this model. Therefore there is a family of sets each containing at least two elements, but there is no $F$ as required. Using this family we can construct the same vector space, but now we can prove that it has no basis. If it had a basis then Blass' proof would follow and a contradiction would be found.
Note that this is semi-constructive since we cannot constructively point out a family of non-empty sets without a choice function, simply because it is consistent that there is none of those. However if we assume that the axiom of choice fails, then we can only infer that such family exists, give it a name and move along. For more see [2].
We can assume "anti-choice" axioms which also tell us particular sets cannot be well-ordered (or families without choice functions), for example we may assume that the real numbers cannot be well-ordered or even a stronger assumption: we can directly assume that the real numbers do not have a basis over $\mathbb Q$. Such assumptions are indeed consistent with ZF, but they are "focused" versions of the negation of the axiom of choice, they tell us a lot about how it fails.
Bibliography:
Andreas Blass, Existence of bases implies the axiom of choice. Contemporary Mathematics vol. 31 pp. 31-33, 1984.
Asaf Karagila, Which set is unwell-orderable? Mathematics StackExchange, Sep. 2012.