\documentclass[11pt]{article}

\usepackage[margin=1.25in,nohead]{geometry}

\usepackage{amsmath,amsfonts,amssymb}
\usepackage{amsthm}
\usepackage{enumerate}

\usepackage[dvips]{color}
% \usepackage[color,notref,notcite]{showkeys}

\definecolor{refkey}{gray}{0.5}
\definecolor{labelkey}{gray}{0.5}

\DeclareMathOperator{\lspan}{span}


\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{remark}[definition]{Remark}


\theoremstyle{plain}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{proposition}[definition]{Proposition}
\newtheorem{corollary}[definition]{Corollary}
%
\newtheorem*{statement}{Statement}

% environment definitions

\newcommand{\nC}{\mathbb C}
\newcommand{\nF}{\mathbb F}
\newcommand{\nK}{\mathbb K}
\newcommand{\nM}{\mathbb M}
\newcommand{\nN}{\mathbb N}
\newcommand{\nP}{\mathbb P}
\newcommand{\nQ}{\mathbb Q}
\newcommand{\nR}{\mathbb R}
\newcommand{\nS}{\mathbb S}
\newcommand{\nZ}{\mathbb Z}


\newcommand{\cA}{{\mathcal A}}
\newcommand{\cB}{{\mathcal B}}
\newcommand{\cC}{{\mathcal C}}
\newcommand{\cD}{{\mathcal D}}
\newcommand{\cE}{{\mathcal E}}

\newcommand{\cV}{{\mathcal V}}
\newcommand{\cU}{{\mathcal U}}
\newcommand{\cW}{{\mathcal W}}


% date and time functions \today \now
\begingroup
\count0=\time \divide\count0by60 % Hour
\count2=\count0 \multiply\count2by-60 \advance\count2by\time%Minute
\def\2#1{\ifnum#1<10 0\fi\the#1}
\xdef\isodayandtime%
{\the\year-\2\month-\2\day\space\2{\count0}:\2{\count2}}
\xdef\now{\space\2{\count0}:\2{\count2}}
\endgroup



\begin{document}

\title{\LARGE \bf Bases}
\author{Branko \'{C}urgus}

\date{\today \ at \hspace*{-9pt} \now}

\maketitle

Throughout this note $\cV$ is a vector space over a scalar field $\nF$. $\nN$ denotes the set of positive integers and $i, j, k, l, m, n, p \in \nN$.

\section{Linear independence}

\begin{definition}
If $m \in \nN$, $\alpha_1, \ldots, \alpha_m \in \nF$ and $v_1, \ldots, v_m \in \cV$, then
\[
\alpha_1 v_1 +\cdots + \alpha_m v_m
\]
is called a {\it linear combination} of vectors in $\cV$. A linear combination is {\it trivial} if $\alpha_1 = \cdots =\alpha_m = 0$; otherwise it is a {\it nontrivial} linear combination.
\end{definition}

\begin{definition}
Let $\cA$ be a nonempty subset of $\cV$.  The {\it span of} $\cA$ is the set of all linear combinations of vectors in $\cA$. The span of $\cA$ is denoted by $\lspan \cA$. The span of the empty set is the trivial vector space $\{0_\cV\}$; that is, the vector space which consists only of $0_\cV$.  If $\lspan \cA = \cV$, then $\cA$ is said to be a {\it spanning set} for $\cV$.
\end{definition}

\begin{proposition} \label{pss}
If $\cU$ is a subspace of $\cV$ and $\cA \subseteq \cU$, then $\lspan \cA \subseteq \cU$.
\end{proposition}

\begin{definition} \label{dld}
Let $\cA \subseteq \cV$. The set $\cA$ is {\em linearly
dependent} if there exist  $m \in \nN$,  $\alpha_1,\ldots,\alpha_m \in \nF$ and distinct vectors $v_1, \ldots, v_m  \in \cA$ such that
\[
\alpha_1 v_1 +\cdots + \alpha_m v_m = 0_{\cV} \quad \text{and} \quad \alpha_k \neq 0 \ \,  \text{for some} \ \,  k \in \{1,\ldots,m\}.
\]
\end{definition}

\begin{remark} \label{rld}
The definition of linear dependence is equivalent to the following statement: Let $\cA \subseteq \cV$. The set $\cA$ is linearly
dependent if there exist  $k \in \nN$,  $\alpha_1,\ldots,\alpha_k \in \nF \setminus \{0\}$ and distinct $v_1, \ldots, v_k  \in \cA$ such that
\[
\alpha_1 v_1 +\cdots + \alpha_k v_k = 0_{\cV}.
\]
\end{remark}


\begin{definition} \label{dli}
Let $\cA \subseteq \cV$. The set $\cA$ is {\em linearly
independent} if for each $m \in \nN$ and arbitrary $\alpha_1, \ldots, \alpha_m \in \nF$ and distinct vectors $v_1, \ldots, v_m \in \cA$ we have
\[
\alpha_1 v_1 +\cdots + \alpha_n v_n = 0_{\cV} \quad \text{implies} \quad \alpha_k = 0 \ \, \text{for all} \ \, k \in \{1,\ldots,m\}.
\]
The empty set is by definition linearly independent.
\end{definition}

It is an interesting exercise in mathematical logic to show that the last two definitions are formal negations of each other. Notice also that the last two definitions can briefly be stated as follows: A set $\cA \subseteq \cV$ is linearly dependent if there exists a nontrivial linear combination of vectors in $\cA$ whose value is $0_\cV$. A set $\cA \subseteq \cV$ is linearly independent if the only linear combination whose value is $0_\cV$ is the trivial linear combination.

The following proposition is an immediate consequence of the definitions.

\begin{proposition} \label{pdep}
Let $\cA \subseteq \cB \subseteq \cV$.  If
$\cA$ is linearly dependent, then $\cB$ is linearly dependent. Equivalently, if $\cB$ is linearly independent, then $\cA$ is linearly independent.
\end{proposition}

\begin{proposition} \label{pld}
Let $\cA$ be a linearly independent subset of $\cV$. Let $u \in \cV$ be such that $u \notin \cA$.  Then $\cA \cup \{u\}$ is linearly dependent if and only if $u \in \lspan \cA$. Equivalently, $\cA \cup \{u\}$ is linearly independent if and only if $u \notin \lspan \cA$.
\end{proposition}
\begin{proof}
Assume that $u \in \lspan \cA$. Then there exist $m\in \nN, \alpha_1, \ldots,\alpha_m \in \nF$ and distinct $v_1,\ldots, v_m \in \cA$ such that $u = \sum_{j=1}^m \alpha_j v_j$. Then
\[
1\cdot u - \alpha_1 v_1 - \cdots - \alpha_mv_m = 0.
\]
Since $1\neq 0$ and $u, v_1,\ldots, v_m \in \cA\cup\{u\}$ this proves that $\cA\cup\{u\}$ is linearly dependent.

Now assume that $\cA\cup\{u\}$ is linearly dependent. Then there exist
$m \in \nN$,  $\alpha_1,\ldots,\alpha_m \in \nF$ and distinct vectors  $v_1, \ldots, v_m  \in \cA\cup\{u\}$ such that
\[
\alpha_1 v_1 + \cdots + \alpha_m v_m = 0_{\cV} \quad \text{and} \quad \alpha_k \neq 0 \ \,  \text{for some} \ \,  k \in \{1,\ldots,m\}.
\]
Since $\cA$ is linearly independent it is not possible that $v_1, \ldots, v_m  \in \cA$. Thus, $u \in \bigl\{v_1, \ldots, v_m\bigr\}$. Hence  $u = v_j$ for some $j \in \{1,\ldots,m\}$. Again, since $\cA$ is linearly independent $\alpha_j = 0$ is not possible. Thus $\alpha_j \neq 0$ and consequently
\[
u = v_j = -\frac{1}{\alpha_j} \ \sum_{\substack{
i=1 \\ i \neq j
}}^m \ \alpha_i \, v_i. \qedhere
\]
\end{proof}

\begin{proposition} \label{pld1}
Let $\cB$ be a nonempty subset of $\cV$. Then $\cB$ is linearly independent if and only if $u \not\in \lspan\bigl(\cB\setminus\{u\}\bigr)$ for all $u \in \cB$. Equivalently, $\cB$ is linearly dependent if and only if there exists $u \in \cB$ such that $u \in \lspan\bigl(\cB\setminus\{u\}\bigr)$.
\end{proposition}
\begin{proof}
Assume that $\cB$ is linearly independent. Let $u \in \cB$ be arbitrary.  Then $\cB\setminus\{u\}$ is linearly independent by Proposition~\ref{pdep}. Now, with $\cA = \cB\setminus\{u\}$, since $\cB = \cA \cup \{u\}$ is linearly independent, Proposition~\ref{pld} yields that $u \not\in \lspan \bigl(\cB\setminus\{u\}\bigr)$.

We prove the converse by proving its contrapositive. Assume that $\cB$ is linearly dependent. Then there exist $m \in \nN$,  $\alpha_1,\ldots,\alpha_m \in \nF$ and distinct vectors $v_1, \ldots, v_m  \in \cB$ such that
\[
\sum_{j=1}^m \alpha_j v_j = 0_{\cV} \quad \text{and} \quad \alpha_k \neq 0 \ \,  \text{for some} \ \,  k \in \{1,\ldots,m\}.
\]
Consequently,
\[
v_k = -\frac{1}{\alpha_k} \ \sum_{\substack{
j=1 \\ j\neq k
}}^m  \ \alpha_j v_j,
\]
and thus $v_k \in \lspan \bigl( \cB\setminus\{v_k\} \bigr)$.
\end{proof}

\section{Finite dimensional vector spaces. Bases}

\begin{definition}
A vector space $\cV$ over $\nF$ is {\em finite dimensional} if there
exists a finite subset $\cA$ of $\cV$ such that $\cV = \lspan \cA$.
A vector space which is not finite dimensional is said to be {\em
infinite dimensional}.
\end{definition}

Since the empty set is finite and since $\lspan \emptyset = \bigl\{0_\cV \bigr\}$, the trivial vector space $\bigl\{0_\cV \bigr\}$ is finite dimensional.

\begin{definition}
A linearly independent spanning set is called a {\it basis} of $\cV$.
\end{definition}

The next theorem shows that each finite dimensional vector
space has a basis.

\begin{theorem} \label{trs}
Let $\cV$ be a finite dimensional vector space over $\nF$. Then $\cV$ has a basis.
\end{theorem}
\begin{proof}
If $\cV$ is a trivial vector space its basis is the empty set. Let  $\cV \neq \{0\}$ be a finite dimensional vector space. Let $\cA$ be a finite subset of $\cV$ such that $\cV = \lspan \cA$. Let $p = |\cA|$. Set
\[
\nK = \bigl\{  |\cC|  \, : \, \cC  \subseteq \cA  \ \ \text{and} \ \
\cC \ \text{is linearly independent}
  \bigr\} .
\]

We first prove that $1 \in \nK$. Since $\cV \neq \{0\}$ there exists $v \in \cA$ such that $v \neq 0_\cV$. Set $\cC = \{v\}$. Then clearly $\cC \subseteq \cA$ and $\cC$ is linearly independent. Thus $|\cC| = 1 \in \nK$.

If $\cC \subseteq \cA$, then $|\cC| \leq |\cA|  = p$. Thus
$\nK \subseteq \{0,1, \ldots, p\}$.
As a subset of a finite set the set $\nK$ is finite. Thus $\nK$ has a maximum. Set $n = \max \nK$.  Since $n \in \nK$ there exists $\cB \subseteq \cA$ such that $\cB$ is linearly independent and $n = |\cB|$.

Next we will prove that $\lspan \cB = \cV$. In fact we will prove that $\cA \subseteq \lspan \cB$. If $\cB = \cA$, then this is trivial. So Assume that $\cB \subsetneqq \cA$ and let $u \in \cA \setminus \cB$ be arbitrary. Then
\[
\bigl| \cB\cup \{u\} \bigr| = n+1 \quad \text{and} \quad \cB\cup \{u\} \subseteq \cA.
\]
Since $n = \max \nK$, $n+1 \not\in \nK$. Therefore $\cB\cup \{u\}$ is linearly dependent. By Proposition~\ref{pld} $u \in \lspan \cB$.
Hence $\cA \subseteq \lspan \cB$. By Proposition~\ref{pss}, $\cV = \lspan \cA \subseteq \lspan \cB$. Since $\lspan \cB  \subseteq \cV$ is obvious, we proved that $\lspan \cB = \cV$. This proves that $\cB$ is a basis of $\cV$.
\end{proof}

\begin{proof}[The second proof of Theorem~{\rm\ref{trs}}] We will reformulate Theorem~{\rm\ref{trs}} so that we can use the Mathematical induction. Let $n$ be a nonnegative integer. Denote by $P(n)$ the following statement: If $\cV = \lspan \cA$ and $|\cA| = n$, then there exists linearly independent set $\cB \subseteq \cA$ such that $\cV =\lspan \cB$.

First we prove that $P(0)$ is true. Assume that $\cV = \lspan \cA$ and $|\cA| = 0$. Then $\cA = \emptyset$. Since $\emptyset$ is linearly independent we can take $\cB = \cA = \emptyset$.

Now let $k$ be an arbitrary nonnegative integer and assume that $P(k)$ is true. That is we assume that the following implication is true:  If $\cU = \lspan \cC$ and $|\cC| = k$, then there exists linearly independent set $\cD \subseteq \cC$ such that $\cU =\lspan \cD$. This is the inductive hypothesis.

Next we will prove that $P(k+1)$ is true. Assume that $\cV = \lspan \cA$ and $|\cA| = k+1$. Let $u \in \cA$ be arbitrary. Set $\cC = \cA \setminus\{u\}$. Then $|\cC| = k$. Set $\cU = \lspan \cC$. The inductive hypothesis $P(k)$ applies to the vector space $\cU$. Thus we conclude that there exists a linearly independent set $\cD \subseteq \cC$ such that $\cU =\lspan \cD$.

We distinguish two cases: Case 1. $u \in \cU = \lspan \cC$ and Case 2. $u \not\in \cU = \lspan \cC$.  In Case 1 we have $\cA \subseteq \lspan \cC$. Therefore, by Proposition~\ref{pss}, $\cV = \lspan \cA \subseteq \cU \subseteq \cV$. Thus $\cV = \cU$ and we can take $\cB = \cD$ in this case. In Case 2, $u \not\in \cU = \lspan \cD$. Since $\cD$ is linearly independent Proposition~\ref{pld} yields that $\cD \cup \{u\}$ is linearly independent. Set $\cB = \cD \cup \{u\}$. Since $\cU = \lspan \cC = \lspan \cD \subseteq \lspan \cB$ we have that $\cC \subseteq \lspan \cB$. Clearly $u \in \lspan \cB$. Consequently, $\cA \subseteq \lspan \cB$. By Proposition~\ref{pss} $\cV = \lspan \cA \subseteq \lspan \cB \subseteq \cV$. Thus $\cV = \lspan \cB$. As proved earlier $\cB$ is linearly independent and $\cB \subseteq \cA$. This proves $P(k+1)$ and completes the proof.
\end{proof}

\section{Dimension}

\begin{theorem}[The Steinitz exchange lemma] \label{tsel}
Let $\cA \subseteq \cV$ be a spanning set for $\cV$ such that $|\cA| = p$. Let $\cB \subseteq \cV$ be a finite linearly independent set such that $|\cB| = m$. Then $m \leq p$ and there exists $\cC \subseteq \cA$ such that $|\cC| = p-m$ and $\cB \cup \cC$ is a spanning set for $\cV$.
\end{theorem}
\begin{proof}
Let $\cA \subseteq \cV$ be a spanning set for $\cV$ such that $|\cA| = p$.

The proof is by mathematical induction on $m$. Since the empty set is linearly independent the statement makes sense for $m = 0$. The statement is trivially true in this case. (You should do a proof of the case $m=1$ as an exercise.)

Now let $k$ be a nonnegative integer and assume that the following statement (the inductive hypothesis) is true: If $\cD \subseteq \cV$ is a linearly independent set such that $|\cD| = k$,  then $k \leq p$ and there exists $\cE \subseteq \cA$ such that $|\cE| = p-k$ and $\cD \cup \cE$ is a spanning set for $\cV$.

To prove the inductive step we will prove the following statement: If $\cB \subseteq \cV$ is a linearly independent set such that $|\cB| = k+1$,  then $k+1 \leq p$ and there exists $\cC \subseteq \cA$ such that $|\cC| = p-k-1$ and $\cB \cup \cC$ is a spanning set for $\cV$.

Assume that $\cB \subseteq \cV$ is a linearly independent set such that $|\cB| = k+1$. Let $u \in \cB$ be arbitrary. Set $\cD = \cB \setminus\{u\}$. Since $\cB = \cD \cup \{u\}$ is linearly independent, by Proposition~\ref{pld1} we have $u \not\in \lspan \cD$.  Also, $\cD$ is linearly independent and $|\cD| = k$. The inductive assumption implies that $k \leq p$ and there exists $\cE \subseteq \cA$ such that $|\cE| = p - k$ and $\cD \cup \cE$ is a spanning set for $\cV$. Since $\cD \cup \cE$ is a spanning set for $\cV$ and $u \in \cV$, $u$ can be written as a linear combination of vectors in $\cD \cup \cE$. But, as we noticed earlier, $u \not\in \lspan \cD$. Thus, $\cE \neq \emptyset$. Hence, $p-k = |\cE| \geq 1$. Consequently, $k+1 \leq p$ is proved. Since $u \in \lspan \bigl(\cD\cup\cE\bigr)$,  there exist $i,j \in \nN$ and $u_1, \ldots, u_i\in \cD$ and $v_1, \ldots, v_j \in \cE$ and $\alpha_1, \ldots, \alpha_i, \beta_1, \ldots, \beta_j \in \nF$ such that
\[
u = \alpha_1 u_1 + \cdots + \alpha_i u_i + \beta_1 v_1 + \cdots + \beta_j v_j. \]
Since $u \not\in \lspan \cD$ at least one of $\beta_1, \ldots, \beta_j \in \nF$ is nonzero. But, by dropping $v$-s with zero coefficients we can assume that all $\beta_1, \ldots, \beta_j \in \nF$ are nonzero. Then
\begin{equation*} % \label{equlc}
v_1 = \frac{1}{\beta_1} \bigl(u - \alpha_1 u_1 - \cdots - \alpha_i u_i - \beta_2 v_2 - \cdots - \beta_j v_j \bigr).
\end{equation*}
Now set $\cC = \cE \setminus \{v_1\}$.  Then $|\cC| = p-k-1$. Notice that $u, u_1, \ldots, u_i \in \cB$ and $v_2, \ldots, v_j \in \cC$; so the last displayed equality implies that
 $
v_1 \in \lspan \bigl(\cB \cup \cC\bigr).
 $
Since $\cE = \cC \cup \{v_1\}$ and $\cD \subseteq \cB$, it follows that
 $
\cD \cup \cE \subseteq \lspan \bigl(\cB \cup \cC\bigr).
 $
Therefore,
\[
\cV = \lspan \bigl(\cD \cup \cE\bigr) \subseteq \lspan \bigl(\cB \cup \cC\bigr).
\]
Hence, $\lspan \bigl(\cB \cup \cC\bigr) = \cV$ and the proof is complete.
\end{proof}


% A. H. Lightstone: Linear algebra, 1969, p. 191

% M. Pearl: Matrix theory and finite mathematics, 1973

% F. E. Hohn: Elementary matrix algebra, 1962

%B. Fincher: Eclectic linear algebra, 1986

The following corollary is a direct logical consequence of the Steinitz exchange lemma. It is in fact a partial contrapositive of the lemma.

\begin{corollary} \label{crt}
Let $\cB$ be a finite subset of $\cV$. If $\cV$ is a finite dimensional space over $\nF$, then there exists $p\in \nN$ such that $|\cB| > p$ implies $\cB$ is linearly dependent.
\end{corollary}
\begin{proof}
Assume that $\cB$ be a finite subset of $\cV$ and $\cV$ is a finite dimensional space over $\nF$. Then there exists a finite subset $\cA$ of $\cV$ such that $\cV = \lspan \cA$. Set $p = |\cA|$. Then the Steinitz exchange lemma yields the following implication: If $\cB$ is linearly independent, then $|\cB| \leq p$. The contrapositive of the last implication is the claim of the corollary.
\end{proof}


\begin{corollary} \label{crtlif}
Let $\cV$ be a finite dimensional space over $\nF$. If $\cC$ is an infinite subset of $\cV$, then $\cC$ is linearly dependent.
\end{corollary}
\begin{proof}
Let $p \in \nN$ be a number whose existence has been proved in Corollary~\ref{crt}. Let $\cC$ be an infinite subset of $\cV$. Since $\cC$ is infinite it has a finite subset $\cA$ such that $|\cA| = p+1$. Corollary~\ref{crt} yields that $\cA$ is linearly dependent. Since $\cA \subseteq \cC$, by Proposition~\ref{pdep}, $\cC$ is linearly dependent.
\end{proof}

\begin{theorem}
Let $\cV$ be a finite dimensional vector space and let $\cB$ and $\cC$ be bases of $\cV$. Then $|\cB| = |\cC|$.
\end{theorem}
\begin{proof}
Let $\cB$ and $\cC$ be bases of $\cV$. Since both $\cB$ and $\cC$ are linearly independent Corollary~\ref{crtlif} implies that they are finite. Now we can apply the Steinitz exchange lemma to the finite spanning set $\cB$ and the finite linearly independent set $\cC$. We conclude that $|\cC| \leq |\cB|$. Applying again the Steinitz exchange lemma to the finite spanning set $\cC$ and the finite linearly independent set $\cB$ we conclude that $|\cB| \leq |\cC|$. Thus $|\cB| = |\cC|$.
\end{proof}

\begin{definition}
The {\em dimension} of a finite dimensional vector space is the number of vectors in its basis.
\end{definition}

\begin{proposition} \label{p3s}
Let $\cV$ be a finite dimensional vector space over $\nF$ and let $\cB$ he a finite subset of $\cV$. Then any two of the following
three statements imply the remaining one.
\begin{enumerate}[{\rm (a)}]
\item \label{ip3sa}
$|\cB| = \dim \cV$.
\item \label{ip3sb}
$\lspan \cB = \cV$.
\item \label{ip3sc}
$\cB$ is linearly independent.
\end{enumerate}
\end{proposition}
\begin{proof}
The easiest implication is: (\ref{ip3sb}) and (\ref{ip3sc}) imply (\ref{ip3sa}). This is the definition of the dimension.

It is easier to prove the partial contrapositive of the implication  (\ref{ip3sa}) and (\ref{ip3sb}) imply (\ref{ip3sc}). First observe that Theorem~\ref{tsel} yields that (\ref{ip3sb}) implies $|\cB| \geq \dim \cV$. Therefore a partial contrapositive of (\ref{ip3sa}) and (\ref{ip3sb}) imply (\ref{ip3sc}) is the following implication:
\[
\text{(\ref{ip3sb}) \ and \ not\! (\ref{ip3sc})} \quad \Rightarrow \quad |\cB| > \dim \cV.
\]
Here is a simple proof. Assume that $\lspan \cB = \cV$ and $\cB$ is linearly dependent. Then $\cB$ is nonempty and by Proposition~\ref{pld1} there exists $u \in \cB$ such that $u \in \lspan\bigl(\cB \setminus\{u\}\bigr)$. Consequently, $\cB \subseteq \lspan\bigl(\cB \setminus\{u\}\bigr)$ and by Proposition~\ref{pss}, $\cV = \lspan\bigl(\cB \setminus\{u\}\bigr)$. By the Steinitz exchange lemma $|\cB \setminus\{u\}| \geq \dim \cV$. Therefore $|\cB| > \dim \cV$.

Now assume (\ref{ip3sa}) and (\ref{ip3sc}). Let $\cA$ be a basis of $\cV$. By the Steinitz exchange lemma there exists $\cC \subseteq \cA$ such that $|\cC| = |\cA| - |\cB| = 0$ such that $\lspan\bigl(\cB \cup \cC\bigr) = \cV$. Since $\cC = \emptyset$, (\ref{ip3sb}) follows.
\end{proof}

In the following proposition we characterize infinite dimensional vector  spaces.

\begin{proposition} \label{pidli}
Let $\cV$ be a vector space over $\nF$. Set $\cA_0 = \emptyset$.  The following statements are equivalent.
\begin{enumerate}[\rm{(}a\rm{)}]
\item \label{pidlia}
The vector space $\cV$ over $\nF$ is infinite dimensional.
\item \label{pidlib}
For every $n \in \nN$ there exists linearly independent set $\cA_n  \subseteq \cV$ such that $|\cA_n| = n$ and $\cA_{n-1} \subset \cA_n$.
\item \label{pidlic}
There exists an infinite linearly independent subset of $\cV$.
\end{enumerate}
\end{proposition}
\begin{proof}
We first prove (\ref{pidlia})$\Rightarrow$(\ref{pidlib}). Assume (\ref{pidlia}). For $n\in\nN$, denote by $P(n)$ the following statement:
\begin{center}
There exists linearly independent set $\cA_n \subseteq \cV$ such that $|\cA_n| = n$ and $\cA_{n-1} \subset \cA_n$.
\end{center}
We will prove that $P(n)$ holds for every $n \in \nN$.
Mathematical induction is a natural tool here. Since the space
$\{0_\cV\}$ is finite dimensional, we have $\cV \neq \{0_\cV\}$.
Therefore there exists $v \in \cV$ such that $v \neq 0_\cV$. Set $\cA_1 =\{v\}$ and the proof of $P(1)$ is complete. Let $k\in\nN$ and assume that $P(k)$ holds. That is assume that there exists linearly independent set $\cA_k \subseteq \cV$ such that $|\cA_k| = k$. Since $\cV$ is an infinite dimensional, $\lspan \cA_k$ is a proper subset of $\cV$. Therefore there exists $u \in \cV$ such that $u \not\in \lspan \cA_k$. Since $\cA_k$ is also linearly independent, Proposition~\ref{pld} implies that $\cA_k\cup\{u\}$ is linearly independent. Set $\cA_{k+1} = \cA_k\cup\{u\}$. Then, since $|\cA_{k+1}| = k+1$ and $\cA_k \subset \cA_{k+1}$, the statement $P(k+1)$ is proved. This proves  (\ref{pidlib}).

Now we prove (\ref{pidlib})$\Rightarrow$(\ref{pidlic}). Assume (\ref{pidlib}) and set $\cC = \cup \bigl\{\cA_n : n \in \nN \bigr\}$. Then $\cC$ is infinite. To prove that $\cC$ is linearly independent, let $m \in \nN$ be arbitrary and let $v_1,\ldots,v_m$ be distinct vectors in $\cC$ and let $\alpha_1,\ldots,\alpha_m \in \nF$ such that
\[
\alpha_1 v_1 + \cdots + \alpha_m v_m = 0_\cV.
\]
By the definition of $\cC$, for every $k \in \{1,\ldots,m\}$ there exists $n_k \in \nN$ such that $v_k \in \cA_{n_k}$. Set $q = \max\bigl\{n_k : k \in \{1,\ldots,m\} \bigr\}$. By the inclusion property of the sequence $\cA_n$, we have $\cA_{n_k} \subseteq \cA_q$ for all $k \in \{1,\ldots,m\}$. Therefore, $v_k \in \cA_q$ for all $k \in \{1,\ldots,m\}$. Since the set $\cA_q$ is linearly independent we conclude that $\alpha_k = 0_\nF$ for all $k \in \{1,\ldots,m\}$. This proves (\ref{pidlic}).

The implication (\ref{pidlic})$\Rightarrow$(\ref{pidlia}) is a partial contrapositive of Corollary~\ref{crtlif}. This completes the proof.
\end{proof}

\section{Subspaces}

\begin{proposition} \label{psfd}
Let $\cU$ be a subspace of $\cV$. If $\cU$ is infinite dimensional, then $\cV$ is infinite dimensional. Equivalently, if $\cV$ is finite dimensional, then $\cU$ is finite dimensional. (In plain English, every subspace of a finite dimensional space is finite dimensional.)
\end{proposition}
\begin{proof}
Assume that $\cU$ is infinite dimensional. Then, by the sufficient part of   Proposition~\ref{pidli}, for every $n \in \nN$ there exists $\cA \subseteq \cU$ such that $|\cA| = n$ and $\cA$ is linearly independent. Since $\cU \subseteq \cV$, we have that for every $n \in \nN$ there exists $\cA \subseteq \cV$ such that $|\cA| = n$ and $\cA$ is linearly independent. Now by the necessary part of Proposition~\ref{pidli} we conclude that $\cV$ is infinite dimensional.
\end{proof}


\begin{theorem} \label{tsc}
Let $\cV$ be a finite dimensional vector space and let $\cU$ be a subspace of $\cV$. Then there exists a subspace $\cW$ of $\cV$ such that $\cV = \cU \oplus \cW$.
\end{theorem}
\begin{proof}
Let $\cB$ be a basis of $\cV$ and let $\cA$ a basis of $\cU$. By Proposition~\ref{psfd}, the Steinitz exchange lemma applies to the finite spanning set $\cB$ and the finite linearly independent set $\cA$. Consequently, there exists $\cC \subseteq \cB$ such that $|\cC| = |\cB| - |\cA|$ and such that $\lspan\bigl(\cA \cup \cC\bigr) = \cV$. Applying the Steinitz exchange lemma again to the linearly independent set $\cB$ and the spanning set $\cA \cup \cC$ we conclude that $|\cA \cup \cC| \geq |\cB|$. Since clearly $|\cA \cup \cC| \leq |\cA| + |\cC| = |\cB|$ we have $|\cA \cup \cC| = |\cA| + |\cC| = |\cB| = \dim \cV$. Now the statement  (\ref{ip3sa}) and (\ref{ip3sb}) imply (\ref{ip3sc}) from  Proposition~\ref{p3s} yields that $\cA \cup \cC$ is a basis of $\cV$. Set $\cW = \lspan \cC$. Then, since $\cA \cup \cC$ is a basis of $\cV$, $\cV = \cU + \cW$. It is not difficult to show that $\cU \cap \cW = \{0_\cV\}$. Thus $\cV = \cU \oplus \cW$. This proves the theorem.
\end{proof}

\begin{lemma} \label{ldsd}
Let $\cV$ be a finite dimensional vector space and let $\cU$ and $\cW$ be subspaces of $\cV$ such that $\cV = \cU \oplus \cW$. Then $\dim \cV = \dim \cU + \dim \cW$.
\end{lemma}
\begin{proof}
Let $\cA$ and $\cB$ be basis of $\cU$ and $\cW$ respectively. Using $\cV = \cU + \cW$, it can be proved that $\cA \cup \cB$ spans $\cV$. Using $\cU \cap \cW = \{0_\cV\}$, it can be shown that $\cA \cup \cB$ is linearly independent and $\cA \cap \cB = \emptyset$. Therefore $\cA \cup \cB$ is a basis of $\cV$ and consequently $\dim \cV = |\cA \cup \cB| = |\cA| + |\cB| = \dim \cU + \dim \cV$.
\end{proof}


\begin{theorem}
Let $\cV$ be a finite dimensional vector space and let $\cU$ and $\cW$ be subspaces of $\cV$ such that $\cV = \cU + \cW$. Then
\[
\dim \cV = \dim \cU + \dim \cW - \dim \bigl(\cU \cap \cW \bigr).
\]
\end{theorem}
\begin{proof}
Since $\cU \cap \cW$ is a subspace of $\cU$ Theorem~\ref{tsc} implies that there exists a subspace $\cU_1$ of $\cU$ such that $\cU = \cU_1 \oplus (\cU\cap\cW)$ and $\dim \cU = \dim \cU_1 + \dim \bigl(\cU \cap \cW \bigr)$. Similarly, there exists a subspace $\cW_1$ of $\cW$ such that $\cW = \cW_1 \oplus (\cU\cap\cW)$ and $\dim \cW = \dim \cW_1 + \dim \bigl(\cU \cap \cW \bigr)$.  Next we will prove that $\cV = \cU\oplus \cW_1$. Let $v \in \cV$ be arbitrary. Since $\cV = \cU + \cW$ there exist $u \in \cU$ and $w\in \cW$ such that $v = u + w$. Since $\cW = \cW_1 \oplus (\cU\cap\cW)$ there exist $w_1 \in \cW_1$ and $x \in \cU\cap\cW$ such that $w = w_1 + x$. Then $v = u + w_1+x = (u+x)+w_1$. Since $u+x \in \cU$ this proves that $\cV = \cU+\cW_1$. Clearly $\cU \cap \cW_1 \subseteq \cU \cap \cW$ and $\cU \cap \cW_1 \subseteq \cW_1$. Thus,
\[
\cU \cap \cW_1 \subseteq \bigl(\cU \cap \cW\bigr) \cap \cW_1 = \{0_\cV\}.
\]
Hence, $\cU \cap \cW_1 = \{0_\cV\}$. This proves $\cV = \cU\oplus \cW_1$. By Lemma~\ref{ldsd}, $\dim \cV = \dim \cU + \dim \cW_1 = \dim \cU + \dim \cW - \dim \bigl(\cU\cap\cV\bigr)$. This completes the proof.
\end{proof}

Combining the previous theorem and Lemma~\ref{ldsd} we get the following corollary.

\begin{corollary}
Let $\cV$ be a finite dimensional vector space and let $\cU$ and $\cW$ be subspaces of $\cV$ such that $\cV = \cU + \cW$. Then the sum $\cU + \cW$ is direct if and only if $\dim \cV = \dim \cU + \dim \cW$.
\end{corollary}

The previous corollary holds for any number of subspaces of $\cV$. The proof is by mathematical induction on the number of subspaces.

\begin{proposition}
Let $\cV$ be a finite dimensional vector space and let $\cU_1, \ldots, \cU_m$ be subspaces of $\cV$ such that $\cV = \cU_1 +\cdots +\cU_m$. Then the sum $\cU_1 +\cdots +\cU_m$ is direct if and only if $\dim \cV = \dim \cU_1 + \cdots + \dim \cU_m$.
\end{proposition}

\end{document}

%% independence is a negation of dependence


The formal negation of the statement in Definition~\ref{dld} is: For each $m \in \nN$ and for all $\alpha_1, \ldots, \alpha_m \in \nF$ and for all $v_1, \ldots, v_m \in \cA$ we have
\[
\alpha_1 v_1 +\cdots + \alpha_n v_n \neq 0_{\cV} \quad \text{or} \quad \alpha_k = 0 \ \, \text{for all} \ \, k \in \{1,\ldots,m\}.
\]

The last statement is equivalent to:  For each $m \in \nN$ and for all $\alpha_1, \ldots, \alpha_m \in \nF$ and for all $v_1, \ldots, v_m \in \cA$ we have
\[
\alpha_1 v_1 +\cdots + \alpha_n v_n = 0_{\cV} \quad \text{implies} \quad \alpha_k = 0 \ \, \text{for all} \ \, k \in \{1,\ldots,m\}.
\]
This leads to the definition of linear independence.

%% m=1 in the replacement theorem

\begin{remark}
Just to be on a safe side let us prove the statement of the Steinitz replacement theorem for $m = 1$. Then $\cB = \{u\} \subseteq \cV$ and $u \neq 0$. Since $u \in \cV$ and $u \neq 0$ it is not possible that $\cA = \emptyset$. Thus $\cA$ is nonempty. Consequently $n \geq 1 =m$. Since $u \in \cV$ and since $\cA$ is a spanning set for $\cV$, there exist $k \in \nN$, $\alpha_1, \ldots, \alpha_k  \in \nF$ and $v_1, \ldots, v_k \in \cA$ such that
\[
u = \alpha_1 v_1 + \cdots + \alpha_k v_k.
\]
Since $u \neq 0$, we can assume that all $\alpha_1, \ldots, \alpha_k$ are nonzero. (If some are zero, we just do not include the corresponding vector in the sum.)

Set $\cC = \cA \setminus \{v_1\}$. Since $\alpha_1 \neq 0$ we have
\[
v_1 =  \frac{1}{\alpha_1} \bigl( u - \alpha_2 v_2 - \ldots - \alpha_k v_k \bigr).
\]
Thus $v_1 \in \lspan \bigl(\cB \cup \cC \bigr)$. Since $\cC = \cA \setminus \{v_1\}$, it follows that
\[
\cA \subseteq \lspan \bigl(\cB \cup \cC \bigr).
\]
Hence $\cV = \lspan \cA \subseteq \lspan \bigl(\cB \cup \cC\bigr)$. Consequently $\cV =  \lspan \bigl(\cB \cup \cC\bigr)$.
\end{remark}



