Proving that basis always exists and is not unique 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$.

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$.
