Prove every linearly independent set is contained in a basis 
Suppose that linear space L has a basis with a finite number of points, B = {P1,
  P2, P3, ... Pn} Then every linearly independent set is contained in a
  basis.

I'm not sure how to go about proving this. I know that no linearly independent set can be larger than basis B, but I'm not sure how to prove there isn't a linearly independent set outside of the basis. 
 A: You show this by simply adding vectors to some linearly independent set $X$ until you find a basis. You start with some linearly independent set $X = X_0$, and $k = 0$.


*

*Let $S_k = \textrm{span }X_k$.

*If $S_k = L$, we're done. By construction $X_k$ is linearly independent, and it spans $L$, so by definition it's a basis.

*Otherwise, pick an arbitrary $x_k \in L \setminus S_k$. Since $x_k \notin S_k$, $x_k$ is linearly independent from $X_k$.

*Set $X_{k+1} = X_k \cup \{x_k\}$, which by (3) is a linearly independent set

*Continue at (1), with $k := k + 1$


Since $L$ is finite-dimensional, this algorithm must stop at some point, because if $L$ has dimension $n$, no set with more than $n$ elements can be linearly independent. But if the algorithm stops during iteration $k$, then $X_k$ is a basis, and by construction $X_k \supset X$.
Therefore, whenever we're given a linearly independent set $X$, we can run this algorithm to find a basis $X_k$ which includes $X$.
A: For this proof you need to show that:


*

*Any linearly independent set with less than $n$ vectors can be extended to be a basis. fgp shows how to do that another answer

*There can bo no linearly independent set with more vectors than a basis.


I am not going to repeat part 1 - fgp did a good job of that (+1 from my side ;)). For part 2 you need to pick any $n+1$ vectors and show that they are linearly dependent. This means you must show in the standard way: if \begin{equation} \sum_{i=1}^{n+1} a_i\beta_i=0 \end{equation} then there exist $a_i$ so that not all the $a_i$ are zero. It is quite straightforward (but a little cumbersome) in this case,: you do it by just expressing each of the $\beta_i$ in terms of the basis $B$ (so $\beta_i=\sum_{j=1}^n b_{ji}B_j$), and then substitute each sum into the equation above, and after some rearrangement you will end up with: \begin{equation} \sum_{j=1}^{n+1} b_{1j}a_j B_1+\sum_{j=1}^{n+1} b_{2j}a_j B_2 + \cdots + \sum_{j=1}^{n+1} b_{nj}a_j B_n = 0. \end{equation} Now each of the coefficients is a sum which must be zero (by the linear independence of the basis), so taking each of these "coefficient equations" together we then have a homogenous system with more unknowns than equations, meaning it will always have a nontrivial solution.
