The Existence of a Basis

Maximal

Definition 1. Let $\mathcal{F}$ be a family of sets. A member $M$ of $\mathcal{F}$ is called maximal if $M$ is contained in no member of $\mathcal{F}$ other than $M$ itself.

    말 그대로 포함 관계에 있어서 가장 최상위에 있는 원소를 maximal 이라고 한다. 예컨대 어떤 집합의 power set에서 그 집합은 자명하게 maximal element 이다. 

Chain

Definition 2. A collection of sets $\mathcal{C}$ is called a chain (or nest or tower) if for each pair of sets $A$ and $B$ in $\mathcal{C}$, either $A \subseteq B \vee B \subseteq A$.

    즉 원소들끼리 어떻게든 포함 관계라는 order를 줄 수 있다면, 그 collection은 chain이라고 부른다. 

Maximal Principle

Maximal Principle. Let $\mathcal{F}$ be a family of sets. If, for each chain $\mathcal{C} \subseteq \mathcal{F}$, there exists a member of $\mathcal{F}$ that contains each member of $\mathcal{C}$, then $\mathcal{F}$ contains a maximal member.

Maximal linearly independent subset

Definition 3. Let $S$ be a subset of a vector space $V$. A maximal linearly independent subset of $S$ is a subset $B$ of $S$ satisfying both of the following conditions.
(a) $B$ is linearly independent.
(b) The only linearly independent subset of $S$ that contains $B$ is $B$ itself.

    말 그대로 linearly independent subset 중에서 maximal인 집합을 말한다. 정의에서도 볼 수 있듯, maximal linearly independent subset은 unique할 필요는 없다. 

    이러한 정의 하에, 어떤 집합이 basis일 조건은 maximal linearly independent subset 일 조건과 동치임을 다음의 정리로부터 알 수 있다.

Theorem 1

Theorem 1. Let $\beta$ be a subset of a vector space $V$. Then $\beta$ is a basis for $V$ $\Longleftrightarrow$ $\beta$ is a maximal linearly independent subset of $V$.

Proof.
($\Longrightarrow$) Let $v \in V$ but $v \notin \beta$. Since $\beta$ is linearly independent and $v \in$ span($\beta$), $\beta \cup \{v\}$ is linearly dependent. Hence $\beta$ is a maximal linearly independent subset of $V$.

($\Longleftarrow$) Let $v \in V$ but $v \notin \beta$. Then $\beta \cup \{v\}$ is linearly dependent. ($\because$ If $\beta \cup \{v\}$ is linearly independent, $\beta \cup \{v\}$ contains $\beta$. $\bigotimes$) By theorem 2, $v \in$ span($\beta$). Hence $\beta$ generates V and is linearly independent, so $\beta$ is a basis for $V$. $\blacksquare$

    이제 우리는 모든 vector space가 maximal linearly independent subset을 가진다는 것을 보임으로 basis의 존재성을 말할 수 있다.

Theorem 2

Theorem 2. Let $S$ be a linearly independent subset of a vector space $V$. Then there is a maximal linearly independent subset of $V$ that contains $S$.

Proof. Let $\mathcal{F}$ be a collection of linearly independent subsets of $V$ and $C \subseteq \mathcal{F}$ a chain. Set $$U = \bigcup_{A \in C} A$$ We claim that $U \in \mathcal{F}$. 
($\because$) Let $u_1, ..., u_n$ be vectors in $U$ and $a_1, ..., a_n$ scalars such that $$a_1u_1 + \cdots a_nu_n = \mathbf{0}.$$ Since each $u_i$ is in $U$, there is $A_i \in C$ such that $u_i \in A_i$. Since $C$ is a chain, for each pair of sets $A_i$ and $A_j$ ($1 \leq i < j \leq n$), $A_i \subseteq A_j \vee A_j \subseteq A_i \Longleftrightarrow u_i, u_j \in A_i \vee u_i, u_j \in A_j$. Hence there is a set $B \in C$ such that $u_1, ..., u_n \in B$. Since $B$ is linearly independent, $a_i = 0 (i = 1, ..., n)$. Hence $U$ is linearly independent and so $U \in \mathcal{F}$. 
Note that $U$ contains each members of $C$. Then the Maximal principle asserts that $\mathcal{F}$ has a maximal element. Thus this maximal element is a maximal linearly independent subset of $V$. $\blacksquare$

Corollary

Corollary. Every vector space has a basis.

Theorem 3

Theorem 3. Let $V$ be a vector space having dimension $n$, and let $S$ be a subset of $V$ that generates $V$. 
(a) There is a subset of $S$ that is a basis for $V$.
(b) $S$ contains at least $n$ vectors.

    이 정리에서 $S$를 finite로 한정시킨다면 Theorem 2로 환원된다. 이 정리는 굳이 $S$를 finite로 한정시키지 않더라도, 즉 $S$가 infinite더라도 동일한 결과를 얻는다는 것을 말해준다.

Proof.
(a) If $S$ is finite, then it is held by Theorem 2. So we may assume that $S$ is infinite. Since $S \neq \emptyset$, take a nonzero vector $u_1 \in S$. And take $u_2 \in S \backslash$ span($\{ u_1 \}$). Inductively, we can choose $u_n \in S \backslash$ span($\{ u_1, u_2, ..., u_{n-1}\}$). Then the set $\beta = \{ u_1, u_2, ..., u_n\}$ is linearly independent. Since a basis for $V$ is a generating set for $V$, it follows from the replacement theorem that if we adjoin to $\beta$ any vector in $V$, then the set is linearly dependent. Hence $\beta \subseteq S$ and $\beta$ is a basis for $V$ by corollary 3 - 2 (b).
(b) By (a), $S$ contains a basis for $V$. Since $V$ has dimension $n$, $S$ contains at least $n$ vectors. $\blacksquare$

---

Reference is here: https://product.kyobobook.co.kr/detail/S000003155051

Linear Algebra | Stephen Friedberg - 교보문고