In Quantum Mechanics, the quantum state of the physical system lives in an infinite-dimensional Hilbert space and can be written in terms of two different bases, the position basis (uncountably infinite) and the energy basis (countably infinite). Apparently, the two bases are of different cardinalities, which violates a theorem in Linear Algebra that all bases of a vector space must be of the same cardinality. How to explain this confusion?
I am a mathematician and not a physicist, so I don't know the physical context and other physicists here are very welcome to correct my answer if it is wrong.
I think your confusion comes from the unfourtantate terminology of "basis" in the context of Hillbert spaces. There are two different concepts both happen to be called basis:
Hamel Basis: That's just a basis in the sense of linear algebra. ie A linearly independent subset such that any vector can be written as a finite linear combination of the members of your basis.
Hillbert Orthonormal basis: That's a linearly independent orthonormal subset of your Hilbert space such that any vector in your vector space can be approximated with arbitrary precision using finite linear combinations of your basis. It follows mathematically that any vector in your hillbert space can be expressed as an infinite sum of members of your basis.
I don't know the physical context, but I suspect that what you call an "energy basis" is the second type of basis I talked about above and not the first one(ie Hillbert Orthonormal basis and not Hamel Basis). However, the theorem of linear algebra which you quote refers to Hamel Basis and not Hillbert orthonormal basis. Hence, you are applying the linear algebra theorem in a wrong way/invalid context and that should solve the confusion.
See this link of Wikipedia: