Dimension theorem for vector spaces

<h2 id="proof">Proof</h2>
Let V be a vector space, {ai: i ∈ I} be a <a href="/facts/Linearly_independent/8JrHfIIa">linearly independent</a> set of elements of V, and {bj: j ∈ J} be a <a href="/facts/Generating_set/Jo1eBRbD">generating set</a>. One has to prove that the <a href="/facts/Cardinality/m6VPojwT">cardinality</a> of I is not larger than that of J.
If J is finite, this results from the <a href="/facts/Steinitz_exchange_lemma/jMqEmNmJ">Steinitz exchange lemma</a>. (Indeed, the Steinitz exchange lemma implies every finite subset of I has cardinality not larger than that of J, hence I is finite with cardinality not larger than that of J.) If J is finite, a proof based on <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> theory is also possible.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> 
Assume that J is infinite. If I is finite, there is nothing to prove. Thus, we may assume that I is also infinite. Let us suppose that the cardinality of I is larger than that of J.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> We have to prove that this leads to a contradiction. 
By <a href="/facts/Zorn%2527s_lemma/ssCublFT">Zorn's lemma</a>, every linearly independent set is contained in a maximal linearly independent set K. This maximality implies that K spans V and is therefore a basis (the maximality implies that every element of V is linearly dependent from the elements of K, and therefore is a linear combination of elements of K). As the cardinality of K is greater than or equal to the cardinality of I, one may replace {ai: i ∈ I} with K, that is, one may suppose, without loss of generality, that {ai: i ∈ I} is a basis. 
Thus, every bj can be written as a finite sum

b
          
            j
          
        
        =
        
          ∑
          
            i
            ∈
            
              E
              
                j
              
            
          
        
        
          λ
          
            i
            ,
            j
          
        
        
          a
          
            i
          
        
        ,
      
    
    {\displaystyle b_{j}=\sum _{i\in E_{j}}\lambda _{i,j}a_{i},}

where 
 
 
 
 
 E
 
 j
 
 
 
 
 {\displaystyle E_{j}}
 
 is a finite subset of 
 
 
 
 I
 .
 
 
 {\displaystyle I.}
 
 As J is infinite, 
 
 
 
 
 ⋃
 
 j
 ∈
 J
 
 
 
 E
 
 j
 
 
 
 
 {\textstyle \bigcup _{j\in J}E_{j}}
 
 has the same cardinality as J.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> Therefore 
 
 
 
 
 ⋃
 
 j
 ∈
 J
 
 
 
 E
 
 j
 
 
 
 
 {\textstyle \bigcup _{j\in J}E_{j}}
 
 has cardinality smaller than that of I. So there is some 
 
 
 
 
 i
 
 0
 
 
 ∈
 I
 
 
 {\displaystyle i_{0}\in I}
 
 which does not appear in any 
 
 
 
 
 E
 
 j
 
 
 
 
 {\displaystyle E_{j}}
 
. The corresponding 
 
 
 
 
 a
 
 
 i
 
 0
 
 
 
 
 
 
 {\displaystyle a_{i_{0}}}
 
 can be expressed as a finite linear combination of 
 
 
 
 
 b
 
 j
 
 
 
 
 {\displaystyle b_{j}}
 
s, which in turn can be expressed as finite linear combination of 
 
 
 
 
 a
 
 i
 
 
 
 
 {\displaystyle a_{i}}
 
s, not involving 
 
 
 
 
 a
 
 
 i
 
 0
 
 
 
 
 
 
 {\displaystyle a_{i_{0}}}
 
. Hence 
 
 
 
 
 a
 
 
 i
 
 0
 
 
 
 
 
 
 {\displaystyle a_{i_{0}}}
 
 is linearly dependent on the other 
 
 
 
 
 a
 
 i
 
 
 
 
 {\displaystyle a_{i}}
 
s, which provides the desired contradiction.

<h2 id="kernel-extension-theorem-for-vector-spaces">Kernel extension theorem for vector spaces</h2>
This application of the dimension theorem is sometimes itself called the dimension theorem. Let

T: U → V
be a <a href="/facts/Linear_transformation/Q1PBKNVV">linear transformation</a>. Then

dim(range(T)) + dim(ker(T)) = dim(U),
that is, the dimension of U is equal to the dimension of the transformation's <a href="/facts/Range_of_a_function/66CeTV6u">range</a> plus the dimension of the <a href="/facts/Kernel_(algebra)/GGSpUPMJ">kernel</a>. See <a href="/facts/Rank%25E2%2580%2593nullity_theorem/3wN4gcJu">rank–nullity theorem</a> for a fuller discussion.

<h2 id="notes">Notes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Howard, P., Rubin, J.: "Consequences of the axiom of choice" - Mathematical Surveys and Monographs, vol 59 (1998) ISSN 0076-5376. <a href="/wiki/Jean_E._Rubin" target="_blank">/wiki/Jean_E._Rubin</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Hoffman, K., Kunze, R., "Linear Algebra", 2nd ed., 1971, Prentice-Hall. (Theorem 4 of Chapter 2). <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">This uses the axiom of choice. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">This uses the axiom of choice. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
</ol>

Dimension theorem for vector spaces open-in-new

Dimension theorem for vector spaces