axiom-of-choicelinear algebraset-theory
Let $V$ be an infinite-dimensional vector space over a field $K$. Then it is known that $\dim V < \dim V^*$. More precisely, by a result attributed to Kaplansky and Erdos, we have $\dim V^* = |K|^{\dim V}$.
I have not seen an actual construction of a basis of $V^*$. My question is: given a basis $B$ of $V$, is there an explicit description of a basis of $V^*$ in terms of $B$? Can you do this at least in the case where $\dim V$ is countable?
In the structure theory of an operator acting on an infinite-dimensional vector space over a field $F$, there is some good news and a lot of bad news. The best news (as Matthew Emerton mentions) is the classification of finitely generated modules over a PID. This beautiful theorem immediately generalizes the Jordan canonical form theorem and the classification of finite or finitely generated abelian groups. It says that every f.g. module over a PID $R$ is a direct sum of cyclic modules $R/d$, and the summands are unique in either the primary decomposition (which comes from the proof by isotypic submodules and Jordan blocks) or the invariant factor decomposition (which comes from the Smith normal form proof). You can take $R = \mathbb{Z}$, or $R = F[x]$ for a field $F$, or of course there are other choices.
I suspect that the bad news is likely to be uniformly bad for countably generated modules over any PID. I found a reference for the case of torsion-free abelian groups, so I will concentrate on that case first. Consider the abelian groups $A$ that lie between $\mathbb{Z}^2$ and $\mathbb{Z}[\frac1p]^2$ for a prime $p$. Those choices for $A$ that are free abelian are just lattices in the plane (whose coordinates have denominators that are powers of $p$). There is an important theorem from the theory of affine buildings that you can make an infinite tree of valence $p+1$ out of these lattices. Two lattices are equivalent if they are the same lattice up to homothetic expansion (by a power of $p$). Two lattices are connected by an edge if they are nested and their quotient is $\mathbb{Z}/p$. So, the theorem says that this graph whose vertices are lattices is acyclic and has degree $p+1$ everywhere; the graph is an affine Bruhat-Tits building of type $A_1$.
Given a general $\mathbb{Z}^2 \subseteq A \subseteq \mathbb{Z}[\frac1p]^2$, you can let $A_n = (\frac1{p^n}\mathbb{Z}^2) \cap A$. This is the type of direct limit that Matthew Emerton describes, which looks good, but bad news is coming. For a while, $A_n/A_{n-1}$ can be $(\mathbb{Z}/p)^2$, then it can be $\mathbb{Z}/p$, and then $A_n$ might stop growing. If it stops growing, then $A$ is free with two generators. If it always grows by $(\mathbb{Z}/p)^2$, then $A = \mathbb{Z}[\frac1p]^2$. But in the middle case, if it grows by $\mathbb{Z}/p$, then $A$ is described by a path in the affine building from the origin to infinity. There are uncountably many ($2^{\aleph_0}$) such paths, and they have a $p$-adic topology.
So when are two such modules $\mathbb{Z}^2 \subseteq A \subseteq \mathbb{Z}[\frac1p]^2$ and $\mathbb{Z}^2 \subseteq B \subseteq \mathbb{Z}[\frac1p]^2$ isomorphic? The outer module is obtained by tensoring either $A$ or $B$ with $\mathbb{Z}[\frac1p]$, so the question is when $A$ and $B$ are equivalent under the action of $\text{GL}(2,\mathbb{Z}[\frac1p])$, which is a countable group. After localizing at all of the other primes, this question was studied by Hjorth, Thomas, and other logicians and algebraists. As Brian Conrad suggests, they have several theorems that indicate that the answer is wild, similar in spirit to the classification of infinite graphs up to isomorphism.
Now suppose that $F$ is a field, most conveniently a countable or finite field, and suppose that $V$ is an $F[x]$-module lying between $F[x]^2$ and $F[x,x^{-1}]^2$. Then you get the same geometric picture as before: The $F[x]$-free choices for $V$, up to homothety by powers of $x$, form an affine building which is an infinite tree, such that the neighbors of each vertex are a projective line $FP^1$. The complicated submodules are the ones that correspond to paths in this tree from the origin to infinity. If $F$ is finite or countable, then $\text{GL}(2,F[x,x^{-1}])$ is also countable, but the set of these paths is always uncountable and the group action is always far from transitive. I don't know if Hjorth's and Thomas' results extend to this case (because I am not qualified to read their papers), but my guess is that they would be comparably pessimistic.
There are other cases in which you get good news, basically by making infinite-dimensional operators look like finite-dimensional operators. The module $V$ in the previous paragraph has no $x$-eigenvectors even after passing to the algebraic closure $\bar{F}$. This is the same statement as that $V$ is torsion-free over $F[x]$. I think that a torsion module over a PID $R$ behaves much better, if it is the direct sum of its isotypic summands. For instance, if $x$ is locally nilpotent on $V$, then I think that it is a direct sum of Jordan blocks, possibly including infinite Jordan blocks (like the differentiation operator $x = \partial/\partial t$ on $\mathbb{Q}[t]$).
Let me give an alternative proof of the result in Ron Maimon's answer, that the canonical map $V\to V^{**}$ can consistently, in the absence of the axiom of choice, be surjective. The only technical advantage of my proof is that it uses only the consistency of ZF plus countable choice plus "all sets (in Polish spaces) have the Baire property". That consistency was proved (by Shelah) relative to just ZF, whereas the consistency of "all sets are Lebesgue measurable" needs an inaccessible cardinal. I think my proof is also a bit simpler than the one using measure. (Also, I don't need to mention ultrafilters, which some people might consider an advantage.)
Let $f:V^*\to\mathbb R$ be a linear map, and let me identify $V^*$ with the space of infinite sequences of reals. Topologize $V^*$ with the product topology, where each factor $\mathbb R$ has the usual topology of the reals. That makes $V^*$ a Polish space, so I can use the assumption about Baire category. In particular, if I partition $\mathbb R$ into intervals of length 1, then the inverse images of these intervals under $f$ have the Baire property, and they can't all be meager, by the Baire category theorem. So at least one of them, call it $f^{-1}(I)$, differs by a meager set from a nonempty open set. Inside that nonempty open set, I can find a basic open set of the form `B=$\prod_iU_i$ where, for some $n$, the first $n$ of the factors $U_i$ are intervals of some length $\delta$ and the later factors $U_i$ are $\mathbb R$. For the first $n$ indices $i$, let $U'_i$ be the interval with the same midpoint as $U_i$ but only half the length, and let $B'$ be the product that is like $B$ except using the $U'_i$ instead of the $U_i$ for the first $n$ factors. Consider an arbitrary $z\in V^*$ whose first $n$ components are smaller than $\delta/2$ in absolute value. Then translation by $z$ in $V^*$ maps $B'$ homeomorphically to another subset of $B$. So the two sets $f^{-1}(I)\cap B'$ and $\{x\in B':z+x\in f^{-1}(I)\}$ are both comeager in $B'$ and therefore must intersect. Let $x$ be in their intersection. Both $f(x)$ and $f(z+x)$ are in the interval $I$ of length 1. Subtracting (and remembering that $f$ is linear), we get that $|f(z)|\leq 2$.
Summarizing, we have that $|f(z)|\leq 2$ for all $z\in V^*$ whose first $n$ components are smaller than $\delta/2$ in absolute value. By linearity, if the first $n$ components of $z$ are smaller than $\alpha\delta/2$ in absolute value, for some positive $\alpha$, then $|f(z)|\leq2\alpha$. In particular, if the first $n$ components of $z$ are zero, then so is $f(z)$. That is, the kernel of $f$ includes the subspace $N$ consisting of those $z\in V^*$ whose first $n$ components vanish. So $f$ factors through the quotient $V^*/N$, which is finite-dimensional (in fact, $n$-dimensional). Knowing what linear functionals on finite-dimensional spaces look like, we immediately conclude that $f$ is given by inner product with a member of $V$ (having non-zero components in at most the first $n$ positions).
Best Answer
It is consistent with the axioms of $\sf ZF$ that this is impossible. Specifically, if you consider $\Bbb R[x]$, then its dual space is just $\Bbb{R^N}$. And it is consistent with $\sf ZF$ that $\Bbb{R^N}$ does not have a Hamel basis.
(Under $\sf ZF+DC$, if all sets are Lebesgue measurable, or have the Baire property, then every group homomorphism between Polish groups is continuous. It follows that if $\Bbb{R^N}$ has a basis, then there is a discontinuous functional from $\Bbb{R^N}$ to $\Bbb R$ simply by cardinality arguments. And therefore such theories prove that $\Bbb{R^N}$ does not have a Hamel basis.)
It follows that there is no explicit way to specify how you get a basis of the dual space. You have to appeal to Zorn's lemma.