Does the fact that this vector space is not isomorphic to its double-dual require choice? Let $V$ denote the vector space of sequences of real numbers that are eventually 0, and let $W$ denote the vector space of sequences of real numbers.  Given $w \in W$ and $v \in V$, we can take their "dot product" $w \cdot v$, and for any give $w \in W$, this defines a linear functional $V \to \mathbb{R}$.  In fact, under this association, we see that $W \cong V^{\ast}$.  Assuming choice, $W$ has a basis and has uncountable dimension, whereas $V$ has countable dimension.  So $\mathrm{dim} (V) < \mathrm{dim} (V^{\ast}) \leq \dim(V^{\ast \ast})$ so $V$ is not isomorphic to its double-dual.  In particular, the canonical map $\widehat{\cdot} : V \to V^{\ast \ast}$ defined by $\widehat{x} (f) = f(x)$ is not an isomorphism.
Question 1: Can you explicitly write down an element of $V^{\ast \ast}$ that isn't of the form $\widehat{x}$?
Question 2: What's the situation if we don't assume choice? (i.e. might the canonical map be an isomorphism, might $W$ not even have a basis, might $V$ be isomorphic to its double-dual but not via the canonical map, etc?)

In light of Daniel's and Yemon's comments, and Konrad's related question here, I'd like to reorganize my question(s).  So consider the following statements:


*

*The canonical map $\widehat{\cdot} : V \to V^{\ast \ast}$ is injective but not surjective.

*The canonical map is not an isomorphism.

*There is no isomorphism from $V$ to its double-dual.

*The double-dual is non-trivial.

*$V^{\ast}$ has a basis.


This is the question I'm really interested in, and which clarifies and makes more precise my original Question 1:
Revised Question 1: Are there models without choice where (1) holds?  If so, can we find some $x \in V^{\ast \ast}$ witnessing non-surjectivity to describe a witness to non-surjectivity in choice models?  Are there models of choice where (1) fails?  
The following question is a more precise version of Question 2.  
Revised Question 2: Under AC, all 5 statements above are true.  There are $2^5 = 32$ ways to assign true-false values to the 5 sentences above that might hold in some model of ZF where choice fails.  Not all 32 are legitimate possibilites, some of them are incompatible with ZF since, for instance, (1) implies (2), (5) implies (4), and the negation of (4) implies (1) through (3), etc.  Which of the legitimate possibilites actually obtains in some model of ZF where choice fails?
This second question is rather broad, and breaks down into something on the order of 32 cases, so seeing an answer to any one of the legitimate cases would be cool.
 A: I have recently noticed$^1$ that in models of ZF+DC+"All sets of real numbers have the Baire property" (e.g. Solovay's model or Shelah's model mentioned by Andreas) there is a very interesting property for Banach spaces:

If $V$ is a Banach space, $W$ is a normed space and $T\colon V\to W$ is linear then $T$ is continuous.

In particular this means that if $V$ is a Banach space over $\mathbb R$ then every functional is continuous. This means that the algebraic dual of a Banach space is the same as the continuous dual of the space.
For example, $\ell_p$ for $p\in(1,\infty)$ have this property, using DC we can develop the basic tools of functional analysis just fine (except Hahn-Banach, though). This implies that $\ell_p$ is reflexive in the algebraic sense, not only in the topological sense.
We further remark$^2$ that the assertion $\ell_1\subsetneq\ell_\infty^\prime$ (where the $\prime$ denotes all the continuous functionals, but in our model these are all the functionals) implies the negation of "All sets of real numbers have the Baire property". The result is that $\ell_1$ is also reflexive in the algebraic sense and in the topological sense.
So with this in mind we have $V_p=\ell_p\oplus\ell_q$ (where $\frac1p+\frac1q=1$) is a self-dual as well algebraically reflexive space, and for distinct $p_1,p_2\in[1,2]$ we have $V_{p_1}\ncong V_{p_2}$ as well, so there are many non-isomorphic examples for this.

Notes:


*

*After sitting to write all the details of the above I found out it is mentioned in Eric Schechter's book, Handbook of Analysis and its Foundations in the last section of chapter 27.

*The above reference does not discuss the case of $p=1$, which is discussed later in the end of chapter 29.
A: 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).
A: A simple uncountable linearly independent set in $V^*$ ($V$ dual--- the space of infinite sequences of reals) is the collection of vectors:
$A^r_n = r^n$
For all nonzero real values $r$. There can be no linear relation between $M$ of these, just restricting to the first $M$ positions, because of the non-vanishing of the Vandermonde determinant. This does nothing to answer the question.

Question 4 is simple： $V^*$ is the space of all infinite sequences, and the space of finite sequences dotted into these give nontrivial linear maps. The interesting question is whether these are all of the linear maps in the absence of choice.

For question 5: if probability arguments work (i.e. if every subset of $\mathbb R$ is measurable) then $V^*$ does not have a basis.
Preliminary comment: If $m$ and $n$ are two positive integers both distributed with probability distribution $P$, their sum $m+n$ does not have the same distribution $P$. To prove this, let $N>0$ be the first integer position where $P(N)$ is nonzero. Then $m\ge N$, $n\ge N$, so $m+n\ge 2N$, so the probability that $m+n$ is $N$ is zero.
Suppose that there is a basis set $B$. Then any vector $v$ in $V^*$ has an integer degree $n$ and $n$ uniquely determined elements of $B$, $e_1,...,e_n$ such that $v$ is a linear combination of the $e$'s. Generate the sequence $A_n$ by picking a Gaussian random number with width $1$ at each position $n$. Generate $B_n$ in the same way. Then the degree of $A$ is some integer $n$, with probability distribution $P(n)$, and the degree of $B$ is an integer $m$ with a probability distribution $P(m)$. The degree of $(A+B)/\sqrt{2}$ is then $m+n$ by adding the expansion of $A$ and the expansion of $B$ (there is no chance that $A$ and $B$ share basis elements, the probability of meeting any finite dimensional subspace is zero), and its distribution is the distribution of the sum of two random integers with distribution $P$. But $(A+B)/\sqrt{2}$ is identically distributed with $A$ and $B$, therefore its degree must have distribution $P$, and there is no such distribution $P$ on positive integers.
I'm repeating the argument in the form I came up with so as to make the rest of the answer more obvious. A closer inspection reveals that the nonmeasurable sets here are the sets of all vectors with degree $n$. These union up to the whole space, so they need to add to the full measure, but the larger $n$ degrees necessarily swamp the lower $n$ degrees in measure because of the properties of linear combination, forbidding a consistent assignment of measures.

For the main question, questions 1,2,3, I show that the existence of any map $f$ in $V^{**}$, other than the ones given by dotting with elements of $V$, either leads to a probabilistic contradiction or a nonprincipal ultrafilter on the integers. Both of these cannot be "explicit", so there is no explicit linear map in $V$ double-dual other than the canonical images of those in $V$.
Proposition: $f$ of any infinite sequence of independent Gaussian random numbers is Gaussian distributed.
Proof: let two picks of the sequence be $S$ and $S'$, $(a S+ b S')\over \sqrt{a^2 + b^2}$ is identically distributed as $S$ and $S'$, so $(a f(S) + b f(S'))\over\sqrt{a^2 + b^2}$ is identically distributed as $f(S)$. Note also that $f(-S)=-f(S)$, so that the probability distribution of $f$ is symmetric around zero. This implies that $f$ has the convolution properties of a Gaussian symmetric about zero, and is therefore a Gaussian with zero mean (or a delta function at zero, which I will call a Gaussian of zero width below).
This means that the linear function $f$ gives a map $\Sigma$ from every sequence of variances to a variance. The function $f$ has variance $\Sigma(\sigma_k)$ when evaluated on the sequence of Gaussian random variables of variance $\sigma_k$
Proposition: If the variances $\sigma_k$ are each individually bigger than $\sigma'_k$, then $\Sigma(\sigma)>\Sigma(\sigma')$
Proof: Let $\alpha_k$ be such that $\alpha_k^2 + \sigma_k^{'2} = \sigma_k^2$. Generate a sequence of Gaussian random picks $A_k$ with variance $\sigma'_k$, and a second Gaussian sequence $B_k$ with variance $\alpha_k$. By construction, $A_k+B_k$ has variance sequence $\sigma_k$.
$f(A)$, $f(B)$, and $f(A+B)=f(A)+f(B)$ are each Gaussian distributed, and the variance of $f(A)$ squared plus the variance of $f(B)$ squared equals the variance of $f(A+B)$ squared. This proves the result.
Theorem: Define the sequence $A^N_n$ to be zero for $n\le N$, and a Gaussian random number with unit variance for $n>N$. If probabilistic arguments work, there is an $N$ for which $f$ on $A^N$ is zero with probability $1$.
Proof: If $f$ on $A^k$ is nonzero for all $k$, consider the infinite sum
$S = C_1 A^1 + C_2 A^2 + C_3 A^3 + C_4 A^4 + \cdots$
since each $A^k$ is zero on the first $k$ positions, this just defines $S$ as a sequence of Gaussians of increasing variance (this is not really an infinite sum--- it is just a trick for writing an infinite sequence of variances in a more illuminating way). For any sequence $C_1, C_2, C_3, \ldots$, the function $f$ produces a Gaussian with a given width which is an non-decreasing function of the $C$'s.
By assumption, $f(A^k)$ has some nonzero variance $a_k$ for all $k$. Choose $C_k$ to be $1/a_k$. Then the width of $f$ on $S$ is greater than any integer $k$, a contradiction.
Therefore there is an integer $N$ such that $f$ has zero variance acting from some $A^N$ on, i.e. $f$ acting on a sequence which is zero at the first $N$ positions, and Gaussian random with unit variance on the remaining positions, gives $0$ with certainty.
What remains is to deal with the case that $f$ is nonzero on some specific vector $v$ which has no chance of ever being generated by random Gaussian picking. To deal with this, you need the following:
Theorem: If $f$ is of zero width on all Gaussian random variables, and $f$ is nonzero on some vector $v$ (and probability works), then there is a nonprincipal ultrafilter on the integers.
proof: Suppose $f(v)$ is nonzero for some infinite sequence $v$. By the zero width property, $f$ is zero on sequences which are nonzero only at finitely many places.
Define a set $S$ of integers to be "zeroing" iff: for any collection $g(S)$ of independent Gaussian random variables defined on $S$, and a Gaussian random variable $g$, $f$ acting on $g v_S + g(S)$ is certainly zero. $g v_S$ is $g$ times the restriction of $v$ to zero on the complement of $S$, while $g(S)$ is a sequence of random variables inside $S$, and zero outside $S$.
Any finite set is zeroing, while the full-set is nonzeroing since $f(gv+g(N))$ has the variance of $g$ times $f(v)$ (since $f$ is zero acting on the Gaussian random sequence $g(N)$).
If $S$ is zeroing, $S$ complement is nonzeroing by linearity. (Note that the converse is not true--- $S$ can be nonzeroing and also $S$ complement nonzeroing--- this is not automatically an ultrafilter).
If $S$ is zeroing and $S'$ is a subset of $S$, then $S'$ is zeroing (by the positivity of adding Gaussian widths).
If $S$ is zeroing and $S'$ is zeroing then $S$ union $S'$ is zeroing, since the sum of independent Gaussian random variables on $S$ and $S'$ are again independent Gaussian random variables on $S$ union $S'$, and any independent Gaussian random variables on the union of $S$ and $S'$ can be decomposed in this way. Therefore the nonzeroing sets form a nonprincipal filter extending the finite-complement filter.
Using dependent choice, either you have an infinite sequence of disjoint restrictions of $v$ $S_1$, $S_2$, $S_3,\ldots$ which are nonzeroing, or the restriction onto one of the sets makes an ultrafilter. An infinite sequence of disjoint nonzeroing restrictions leads to a probabilistic contradiction, as before, by considering
$A = \sum_k C_k g(S_k)$
with appropriate fast-growing choice of $C_k$, just like before. The terminating case gives an ultrafilter.
Putting the two theorems together, the function $f$ has to be certainly zero on Gaussian sequences from position $N$ onward, so $f$ is a linear function on the first $N$ values plus a residual. The residual is zero on the first $N$ positions, and makes a linear function on the values past $N$, and the residual is zero on any Gaussian random sequence.
If the residual function is nonvanishing on some vector $v$, then it either leads to a probabilistic contradiction or it defines a nonprincipal ultrafilter on $\mathbb Z$. So in a universe with every subset of $\mathbb R$ measurable, with dependent choice, and with no nonprincipal ultrafilter on the integers, $V$ double dual is the canonical image of $V$, and questions 1,2,3 are answered.
A: edit I'm leaving the "answer" as is but now I realize that it doesn't get that far. I think it gives a subspace $W' \subset  W=V^{\ast}$ with an uncountable basis. And $(W')^{\ast}$ includes but is much bigger than the set of all $\widehat{x}$. Maybe that is not that helpful.
No, it doesn't require the axiom of choice. It takes choice to show that $W$ has a basis but not to show that it has a subspace that has an uncountable basis. I remembered that I once saw a great construction due to Von Neumann so I Googled it and ended up at explicit big linearly independent sets. I suggest checking out the web site! 
I think that should do it. Well actually Von Neumann's set is algebraically independent. Earlier in the answer it is pointed out that $T_r = \sum_{q_n < r} \frac{1}{n!}$ (where $q_0, q_1, \ldots$ is an enumeration  $\mathbb{Q}$) is independent over $\mathbb{Q}$. So write each $T_r$ in binary and convert it into a $0,1$ element of $W$.
