Are the position eigenkets $\lvert x \rangle$ really a basis for the space of states?

In my current understanding, matrix formulation and wave-function formulation of QM are basically the same because $\left|\psi\right>$ and $\psi(x)$ are really the same mathematical object: A vector in the (vector) space of complex functions. My issue with this is the status of $\hat{x}$ and its eigenvectors $\left|x\right>$.

Let’s ask a simple question: What is the dimensionality of the vector space? We can simply write that every vector can be decomposed in a sum of energy eigenstates:

$\left|\psi\right> = \sum E_n\left|n\right>$

Or every vector can be decomposed in a sum of position eigenstates:

$\left|\psi\right> = \int \psi(x)\left|x\right>dx$

In the first case, we have an infinite enumerable basis. In the second case, we have an infinite non-enumerable basis. But they are supposed to be two different orthonormal basis of the same vector space!

Or put another way, how can we write $\psi(x) = \left<\psi|x\right>$ if the set of $\left|x\right>$s is enumerable but the domain of $\psi(x)$ isn’t ?

$\lvert x \rangle$ as an "eigenvector" of the position operator is not a vector in the physical Hilbert space of states $\mathcal{H}$ - it's not normalizable, for one, as the odd "inner product" $$\langle x' \vert x \rangle = \delta(x' - x)$$ indicates. To deal with it mathematically, one has to introduce the concept of rigged Hilbert spaces, see also this question and answer. It boils down to the fact that the statement "But they are supposed to be two different orthonormal basis of the same vector space!" is simply false - they are not two bases of the same space.
It's completely non-obvious, but nevertheless surprisingly often true, that one can get away with pretending that the identity on $\mathcal{H}$ can be written as $\int \lvert x \rangle \langle x \rvert \mathrm{d}x$ as if the $\lvert x \rangle$ were a basis of $\mathcal{H}$, when, in fact, the space is separable in all physical cases and has a countable basis $\lvert \psi_i \rangle$ so that the identity is $\sum_{i\in\mathbb{N}}\lvert\psi_i\rangle\langle\psi_i\rvert$. Note that the $\lvert\psi_i\rangle$ are not always energy eigenstates, since the Hamiltonian need not have discrete spectrum (and indeed hasn't for the free states, usually).
• @CuriousOne Qualitatively, because Heisenberg uncertainty takes phase-space (position, momentum) and says that you have to cut it up into little areas of size $\hbar$ or so over which the wavefunction can't vary too much. Mathematically this transforms $\mathbb R^2$ (which has the same cardinality as $\mathbb R$) to $\mathbb Z^2$ (which has the same cardinality as $\mathbb N$ as we can enumerate the points in a spiral out from the center). – CR Drost Sep 23 '15 at 13:28
• @CuriousOne: Ah, no, that basis indeed isn't countable. But the plane waves $\exp(\mathrm{i}xp)$ aren't physical states, anyway. All physical states are wavepackets constructed from those, which lie in $L^2(\mathbb{R}^3)$ again, which has a countable basis as a separable Hilbert space. The plane waves are like the $\lvert x \rangle$ in this question - they lie in a larger space of which you may pretend its vectors form a basis for the smaller physical Hilbert space, but they really aren't. – ACuriousMind Sep 23 '15 at 13:54
• @CuriousOne If it helps further, notice that if $B =\{0,1\}$, then $B \cup B^2 \cup B^3 \cup \dots$ is essentially a definition of $\mathbb N$ with cardinality $\aleph_0$, but $B^{\aleph_0}$ is essentially a definition of the real interval $[0, 1]$ (if prefixed with "0.") and therefore has cardinality $\mathbb R$. Even if the coefficients were drawn from a finite set at each stage, the set of infinitely-long vectors of them would have continuous cardinality. That's the mechanism by which a countable basis builds an uncountable space. – CR Drost Sep 23 '15 at 15:09