Proving that basis always exists and is not unique

Question

How to prove that basis in a vector space $V$ always exists? Basis is a collection of vectors that are linearly independent and span $V$.

If $\dim(V)=n$ then $n$ linearly independent vectors form a basis because of basis extension theorem (to every set of linearly independent vectors we can add new vectors to make it a basis). It utilizes the fact that all bases are of equal length, therefore we don't need to add any new vectors, because we already $n$ of them. It means they form a basis.

But the key thing here is to prove that basis always exists and is not unique (to make the arguments valid), because we assumed bases exist and they are not unique in the theorem that all bases have equal length. You can find a bunch of basic theorems here.

If I were to show that there exists a collection of vectors that spans $V$, I'd simply say that you can simply take every single vector of $V$ - this collection will certainly span $V$.

Answer 1

The proof every vector space has a basis uses the axiom of choice; the proof is similar to that of the well-ordering theorem. Let $f$ be a choice function on the set of nonempty subsets of $V$. By transfinite recursion we define for ordinals $\alpha$ a function $e\left(\alpha\right) :=f(V\backslash\text{span}\left\{ e\left(\beta\right)|\beta\in\alpha\right\} )$. This definition malfunctions iff the argument of $f$ is empty, i.e. we define $e\left(\alpha\right)$ until the span covers all of $V$. This is guaranteed to eventually happen, since otherwise one could inject the ordinals into the set $V$.

Replacing two basis elements $e_1,\,e_2$ with $a e_1\pm b e_2,\,a\neq 0\neq b$ is the usual way of showing a basis isn't unique. For this argument to work, we need the same span from this alternative. Certainly $2a e_1,\,2b e_2$ are included. In fields of characteristic 2, such as $\mathbb{F}_2$ (discussed in the above comments), we can't then divide by $2a,\,2b$ to finish the proof, because $2:=1+1=0$.

Answer 2

Your question (with the extra hypothesis that you added in the comments that you are assuming that the space is finite-dimensional) is not without problems. In fact, usually one defines the dimension of a vector space as the cardinal of any of its basis (after proving that they all have the same cardinal). So, your hypothesis already assumes the existence of a basis.

However, let us say that a vector space $V$ over a field $k$ is finite-dimensional if it is generated by a finite set $S$. In that case, it makes sense to ask if every finite-dimensional space has a basis. And the answer is affirmative — unless, of course, $V=\{0\}$.

Let $B$ be, among the subsets of $S$ which generate $V$, one with the minimal number of elements. So, $B=\{v_1,v_2,\ldots,v_n\}$ (with $n\in\mathbb N$), $B$ generates $V$, and no subset of $B$ (other than $B$ itself) generates $V$. I will prove that $B$ is linearly independent, thereby proving that it is a basis of $V$. In order to do that, let $\alpha_1,\alpha_2,\ldots,\alpha_n\in k$ and suppose that $\alpha_1v_1+\alpha_2v_2+\cdots+\alpha_nv_n=0$. Suppose also that one of the $\alpha_k$'s is not $0$. We can, without loss of generality, suppose that $k=1$. Then$$v_1=-\frac{\alpha_2}{\alpha_1}v_2-\frac{\alpha_3}{\alpha_1}v_3-\cdots-\frac{\alpha_n}{\alpha_1}v_n$$and therefore the subspace of $V$ generated by $v_2,v_3,\ldots,v_n$ contains $v_1$. Since $B$ generates $V$, it follows from this observation that $V$ is generated by $B\setminus\{v_1\}$, which is absurd, since$$\#B\setminus\{v_1\}=n-1<n=\#B$$and we were assuming that $B$ had the minimal number of elements among the subsets of $S$ which generate $V$.

So, I proved that any finite-dimensional vector space $V\neq\{0\}$ has a basis. I cannot prove that it is not unique though, since this is not true. As it has been remarked in the comments, $\mathbb{F}_2$, as a vector field over itself, has a single basis: $\{1\}$.