The assertion "Every vector space has a basis" implies the axiom of choice in ZF. This means that without the axiom of choice there are spaces that have no basis.
It is open at the moment whether or not this implies that there is a space with a trivial dual as well. However, it is consistent that there is a space whose dual is trivial. That is to say that the only linear functional is indeed $0$.
The usual construction yields a vector space $W$ with the following properties:
- $W$ is not spanned by any finite set (i.e. it does not have a finite dimension),
- Every proper subspace has a finite dimension,
- The only linear transformation from $W$ into itself are multiplication by scalars from the field. In particular this implies that there is only one linear functional: the zero functional.
Let us consider this case: Let $V$ be $\mathbb R^n$ for some $n$, and let $W$ be as described above (with the field being $\mathbb R$).
Choose $n$ vectors, $w_1,\ldots,w_n$, which are linearly independent (this process requires no axiom of choice since it can be described in finitely many steps). Let $W'$ be the span of $w_1,\ldots,w_n$.
There is a natural map $f$ from $V$ into $W'$, and hence into $W$. Consider $f^*$, its domain is $W^*=\{0\}$. It is far far from being onto $V$.
Wait, it gets worse. Consider $f\colon V\to M=W\oplus \mathbb R^{n-1}$ as the map which maps $e_1\to w\in W$ (which is nonzero) and $e_2,\ldots,e_n$ into the $\mathbb R^{n-1}$ part.
Every functional on $M$ is $0$ on $W$ and a usual functional on $\mathbb R^{n-1}$. However there is no surjective map from $M^*$ onto $V^*$, simply since $\dim(M^*)=n-1<\dim(V^*)=n$.
There is no really elementary proof, since this is in fact independent of the "constructive" part of the usually axioms of set theory.
However if one has a basic understanding of the axiom of choice then one can easily construct the injection. The axiom of choice says that if we have a family of non-empty sets then we can choose exactly one element from each set in our family.
Suppose that $g\colon Y\to X$ is a surjection then for every $x\in X$ there is some $y\in Y$ such that $g(y)=x$. I.e., the set $\{y\in Y\mid g(y)=x\}$ is non-empty.
Now consider the family $\Bigg\{\{y\in Y\mid g(y)=x\}\ \Bigg|\ x\in X\Bigg\}$, by the above sentence this is a family of non-empty sets, and using the axiom of choice we can choose exactly one element from every set. Let $y_x$ be the chosen element from $\{y\in Y\mid g(y)=x\}$. Let us see that the function $f(x)=y_x$ is injective.
Suppose that $y_x=y_{x'}$, in particular this means that both $y_x$ and $y_{x'}$ belong to the same set $\{y\in Y\mid g(y)=x\}$ and this means that $x=g(y_x)=g(y_{x'})=x'$, as wanted.
Some remarks:
The above proof uses the full power of the axiom of choice, we in fact construct an inverse to the injection $g$. However we are only required to construct an injection from $X$ into $Y$, which need not be an inverse of $g$ -- this is known as The Partition Principle:
If there exists a surjection from $Y$ onto $X$ then there exists an injection from $X$ into $Y$
It is still open whether or not the partition principle implies the axiom of choice, so it might be possible with a bit less than the whole axiom of choice.
However the axiom of choice is definitely needed. Without the axiom of choice it is consistent that there exist two sets $X$ and $Y$ such that $Y$ has both an injection into $X$ and a surjection onto $X$, but there is no injection from $X$ into $Y$.
Best Answer
This cannot be proved "naively". Indeed this question is an equivalent formulation of an axiom known as The Axiom of Choice.
The axiom of choice says that given a family of non-empty sets, we can choose one element from each member of the family.
Using the axiom of choice, note that for every $y\in Y$ the set $f^{-1}(y)$ is non-empty. We therefore have a function which chooses one element from each preimage, call it $g$. This function is as wanted, since $g(y)\in f^{-1}(y)$ and therefore $f(g(y))=y$ as wanted, this also implies $g$ is injective because if $y_1\neq y_2$ then $g(y_1)$ and $g(y_2)$ are taken from disjoint sets.