# Math proof: Linear Independence

Tags:
1. Nov 12, 2016

### kregg34

1. The problem statement, all variables and given/known data
How can I show that if a vector (in a vector space V) cannot be written as a linear combination of a linearly independent set of vectors (also in space V) then that vector is linearly independent to the set?

2. Relevant equations
To really prove this rigorously it would make sense to use only the following axioms:
1)For every x,y in V, x+y is also in V.
2) (x+y)+z = x+(y+z) = x+y+z
3) 0 is in V, and 0+x = x for all x in V
4) All x in V have an inverse -x such that x+(-x)=0
5)For all scalars 'a' and 'b', a(bx) = (ab)x
6) For all x in V, 1x=x
7)For all scalars 'a' and 'b', (a+b)x = ax+bx
8)for all scalars 'a', a(x+y) = ax+ay
9)For all x in V, -x = (-1)x
10) A set of N linear independent vectors implies that if a linear combination of them is zero, then all the coefficients are zero.

3. The attempt at a solution
I feel like I need to use a proof by contradiction, but not really sure how to start. This is actually my simplification of the true proof, and that is to prove that all vectors can be written as a linear combination of a basis set.

2. Nov 12, 2016

### Staff: Mentor

Firstly it's helpful to name the objects which you're dealing with. Say you have a vector $v$ and a set $S = \{v_1,v_2, \ldots , v_n\}$ of linear independent vectors $v_i$. (With an infinite set things must be handled with a bit more care but the way is the same.) Next one usually assumes, that either $v$ can be written as linear combination of the $v_i$ and a contradiction is deduced, or one shows that all vectors $v,v_1, \ldots v_n$ are linear independent (see #10 in your list).

Last edited: Nov 13, 2016
3. Nov 12, 2016

### Mr Davis 97

You could argue by contraposition. That is, instead of proving that $p \implies q$ you could prove that $\neg q \implies \neg p$, since they are logically equivalent.

The contrapositive of your problem: If a vector is linearly dependent to a set of linearly independent vectors, then that vector can be written as a linear combination of vectors in the set.

4. Nov 13, 2016

### Staff: Mentor

There's also a proof by contradiction, where you assume that p is true and that q is false. If you arrive at a contradiction, then it must be true that $p \implies q$.
The idea here is that $\neg(p \wedge \neg q) \equiv p \implies q$