A.4 Zorn's lemma · Matrix Theory

In a finite-dimensional space, a basis is built by adding vectors one at a time until the list spans; the process stops because an independent list has at most $dim 𝑉$ vectors (Theorem 4.1.16). In a space such as $𝐹^{ℕ}$ or $ℝ$ over $ℚ$ , the process need not stop after finitely many steps, or after countably many, and there is no last step to point to. Zorn’s lemma replaces the process by a single statement: if every partial result can be extended to an upper bound, then a maximal one exists. It is the standard way to prove that objects of linear algebra exist in infinite dimensions, and Section 15.1 uses it to show that every vector space has a basis.

A.4.1Partial orders and chains

Definition A.4.1 (Partial order). A partial order on a set $𝑃$ is a relation $\leq$ that is

reflexive: $𝑝 \leq 𝑝$ ;
antisymmetric: if $𝑝 \leq 𝑝^{'}$ and $𝑝^{'} \leq 𝑝$ , then $𝑝 = 𝑝^{'}$ ;
transitive: if $𝑝 \leq 𝑝^{'}$ and $𝑝^{'} \leq 𝑝^{″}$ , then $𝑝 \leq 𝑝^{″}$ .

The pair $(𝑃, \leq)$ is a partially ordered set. We write $𝑝 < 𝑝^{'}$ if $𝑝 \leq 𝑝^{'}$ and $𝑝 \neq 𝑝^{'}$ . Two elements $𝑝, 𝑝^{'}$ are comparable if $𝑝 \leq 𝑝^{'}$ or $𝑝^{'} \leq 𝑝$ . A chain is a subset $𝐶 \subseteq 𝑃$ in which any two elements are comparable.

Definition A.4.2 (Upper bound, maximal element). Let

(𝑃, \leq)

be a partially ordered set. An upper bound of a subset

𝑆 \subseteq 𝑃

is an element

𝑢 \in 𝑃

with

𝑠 \leq 𝑢

for every

𝑠 \in 𝑆

; it need not lie in

𝑆

. An element

𝑚 \in 𝑃

is maximal if no element of

𝑃

is strictly larger:

𝑚 \leq 𝑝

implies

𝑝 = 𝑚

In linear algebra, $𝑃$ is almost always a collection of sets, such as subspaces or independent sets, ordered by inclusion $\subseteq$ . A chain is then a family of sets that is nested: of any two, one contains the other. A maximal element is one that cannot be enlarged within the collection. It need not be the largest element: there may be many maximal elements, none containing the others.

Example A.4.3 (Chains and maximal elements).

(a)In $𝑃 (𝑋)$ , ordered by $\subseteq$ , every chain has the upper bound $𝑋$ , and $𝑋$ is the only maximal element.
(b)Let $𝑃$ be the set of subspaces of $ℝ^{3}$ of dimension at most $2$ , ordered by $\subseteq$ . The maximal elements are the planes through $𝟎$ , and there are infinitely many of them. Every chain has an upper bound: a nonempty chain has at most three distinct members, of dimensions $0$ , $1$ , $2$ , and its largest member is an upper bound, while the empty chain is bounded by ${𝟎}$ .
(c)Let $𝑃$ be the set of proper subspaces of $𝐹 [𝑥]$ , ordered by $\subseteq$ . The subspaces ${𝐹 [𝑥]}_{\leq 𝑛}$ of polynomials of degree at most $𝑛$ form a chain, and it has no upper bound in $𝑃$ : a subspace containing every ${𝐹 [𝑥]}_{\leq 𝑛}$ contains every polynomial, so it is $𝐹 [𝑥]$ , which is not proper.
(d) $ℕ$ with $\leq$ is a chain with no upper bound, and it has no maximal element.

In (b), an upper bound of a chain was its largest member. In (c) and (d) the chains are infinite with no largest member, and nothing in $𝑃$ lies above all of their members; in (c), the natural candidate, the union, is $𝐹 [𝑥]$ , which is not in $𝑃$ . Zorn’s lemma says that this failure is the only obstruction to a maximal element.

A.4.2Zorn’s lemma

Theorem A.4.4 (Zorn’s lemma). Let

(𝑃, \leq)

be a partially ordered set in which every chain has an upper bound. Then

𝑃

has a maximal element.

The empty set is a chain, and an upper bound of it is any element of $𝑃$ . So the hypothesis includes $𝑃 \neq \emptyset$ , and in practice one checks that $𝑃$ is nonempty and that every nonempty chain has an upper bound.

Zorn’s lemma is equivalent to the axiom of choice (Remark A.1.13): Exercise A.4.11 derives the axiom of choice from it, and the proof below derives it from the axiom of choice. The proof is not needed anywhere in the book, and it uses a transfinite construction that the rest of the book does not, so it is marked beyond and the reader can skip it.

Intuition (Why Zorn’s lemma should be true). Suppose

𝑃

has no maximal element. Then every chain

𝐶

has a strict upper bound: it has an upper bound

𝑢

, and

𝑢

is not maximal, so something is larger than

𝑢

. Start from any element

𝑝_{0}

, take a strict upper bound

𝑝_{1}

{𝑝_{0}}

, then

𝑝_{2}

{𝑝_{0}, 𝑝_{1}}

, and so on. After all finite stages, the chain

{𝑝_{0}, 𝑝_{1}, \dots}

again has a strict upper bound

𝑝_{𝜔}

, and we continue. The process never gets stuck, and it never repeats an element, so it should eventually use up more elements than

𝑃

has. The proof makes “continue forever, through all stages” precise without ordinals, by looking at all chains that are built by this rule at once.

Proof.challenge

Uses. Remark A.1.13 (The axiom of choice), Definition A.4.1 (Partial order), Definition A.4.2 (Upper bound, maximal element)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Suppose there is no maximal element. Show that every chain

𝐶

then has a strict upper bound, and use the axiom of choice to fix one,

𝑠 (𝐶)

, for every chain.

Hint 2. Call

𝑊 \subseteq 𝑃

a tower if every nonempty subset of

𝑊

has a least element, and every

𝑤 \in 𝑊

equals

𝑠 (𝑊_{< 𝑤})

, where

𝑊_{< 𝑤} =

{𝑥 \in 𝑊 | 𝑥 < 𝑤}

. Show that of any two towers, one is an initial segment of the other.

Hint 3. For the comparison, take the union

𝐼

of all sets that are downward closed in both towers

𝑊

and

𝑉

. If

𝐼 \neq 𝑊

and

𝐼 \neq 𝑉

, the least elements of

𝑊 ∖ 𝐼

and of

𝑉 ∖ 𝐼

are both

𝑠 (𝐼)

Hint 4. Then the union

𝑈

of all towers is a tower, and

𝑈 \cup {𝑠 (𝑈)}

is a strictly larger tower, a contradiction.

Sketch. Assume no maximal element; then every chain has a strict upper bound, and choice gives a function

𝑠

picking one. A tower is a well-ordered

𝑊

with

𝑤 = 𝑠 (𝑊_{< 𝑤})

for all

𝑤 \in 𝑊

. Any two towers are comparable, one an initial segment of the other: the largest common downward closed set

𝐼

is all of one of them, since otherwise

𝑠 (𝐼)

would extend it. So the union

𝑈

of all towers is a tower, and so is

𝑈 \cup {𝑠 (𝑈)}

, which contradicts

𝑠 (𝑈) \notin 𝑈

Suppose that $𝑃$ has no maximal element. Let $𝐶$ be a chain, and let $𝑢$ be an upper bound of $𝐶$ . Since $𝑢$ is not maximal, there is $𝑝 \in 𝑃$ with $𝑢 < 𝑝$ . Then $𝑐 < 𝑝$ for every $𝑐 \in 𝐶$ : we have $𝑐 \leq 𝑢 \leq 𝑝$ , and $𝑐 = 𝑝$ would give $𝑝 \leq 𝑢 \leq 𝑝$ , so $𝑢 = 𝑝$ . So the set of strict upper bounds of $𝐶$ is nonempty, and by the axiom of choice there is a function $𝑠$ that assigns to every chain $𝐶$ a strict upper bound $𝑠 (𝐶)$ .

A subset $𝑊 \subseteq 𝑃$ is well ordered if every nonempty subset of $𝑊$ has a least element; then $𝑊$ is a chain, since every pair ${𝑥, 𝑦} \subseteq 𝑊$ has a least element. For $𝑤 \in 𝑊$ write $𝑊_{< 𝑤} =$ ${𝑥 \in 𝑊 | 𝑥 < 𝑤}$ . Call $𝑊$ a tower if it is well ordered and $𝑤 = 𝑠 (𝑊_{< 𝑤})$ for every $𝑤 \in 𝑊$ . (For instance $\emptyset$ , ${𝑠 (\emptyset)}$ , and ${𝑠 (\emptyset), 𝑠 ({𝑠 (\emptyset)})}$ are towers.) A subset $𝐴 \subseteq 𝑊$ is downward closed in $𝑊$ if $𝑥 \in 𝐴$ , $𝑦 \in 𝑊$ , and $𝑦 < 𝑥$ imply $𝑦 \in 𝐴$ .

Step 1. If $𝐴$ is downward closed in a well-ordered $𝑊$ and $𝐴 \neq 𝑊$ , then $𝐴 = 𝑊_{< 𝑚}$ , where $𝑚$ is the least element of $𝑊 ∖ 𝐴$ . If $𝑦 \in 𝑊$ and $𝑦 < 𝑚$ , then $𝑦 \in 𝐴$ by minimality of $𝑚$ . If $𝑦 \in 𝐴$ , then $𝑚 \leq 𝑦$ is impossible, since it would put $𝑚$ in $𝐴$ (either $𝑚 = 𝑦$ or $𝑚 < 𝑦$ and $𝐴$ is downward closed); as $𝑊$ is a chain, $𝑦 < 𝑚$ .

Step 2. If $𝑊$ and $𝑉$ are towers, then one of them is downward closed in the other. Let $𝐼$ be the union of all subsets of $𝑊 \cap 𝑉$ that are downward closed in both $𝑊$ and $𝑉$ . A union of downward closed sets is downward closed, so $𝐼$ is downward closed in both, and it is the largest such set. Suppose $𝐼 \neq 𝑊$ and $𝐼 \neq 𝑉$ . By Step 1, $𝐼 = 𝑊_{< 𝑚}$ and $𝐼 = 𝑉_{< 𝑛}$ , where $𝑚$ and $𝑛$ are the least elements of $𝑊 ∖ 𝐼$ and $𝑉 ∖ 𝐼$ . Since $𝑊$ and $𝑉$ are towers,

𝑚 = 𝑠 (𝑊_{< 𝑚}) = 𝑠 (𝐼) = 𝑠 (𝑉_{< 𝑛}) = 𝑛 .

Then $𝐼 \cup {𝑚}$ is downward closed in $𝑊$ (an element of $𝑊$ below $𝑚$ lies in $𝑊_{< 𝑚} = 𝐼$ ), and likewise in $𝑉$ . By maximality of $𝐼$ , $𝑚 \in 𝐼$ , which is false. So $𝐼 = 𝑊$ or $𝐼 = 𝑉$ ; that is, $𝑊$ is downward closed in $𝑉$ , or $𝑉$ in $𝑊$ .

Step 3. The union $𝑈$ of all towers is a tower. Let $𝑊$ be a tower and $𝑤 \in 𝑊$ . We claim $𝑈_{< 𝑤} = 𝑊_{< 𝑤}$ . Clearly $𝑊_{< 𝑤} \subseteq 𝑈_{< 𝑤}$ . If $𝑢 \in 𝑈$ and $𝑢 < 𝑤$ , then $𝑢 \in 𝑉$ for some tower $𝑉$ . By Step 2, either $𝑉$ is downward closed in $𝑊$ , so $𝑉 \subseteq 𝑊$ and $𝑢 \in 𝑊$ ; or $𝑊$ is downward closed in $𝑉$ , and then $𝑢 \in 𝑉$ , $𝑢 < 𝑤 \in 𝑊$ give $𝑢 \in 𝑊$ . Either way $𝑢 \in 𝑊_{< 𝑤}$ .

Now $𝑈$ is a chain: for $𝑥, 𝑦 \in 𝑈$ , say $𝑥 \in 𝑊$ and $𝑦 \in 𝑉$ , Step 2 puts both in $𝑊$ or both in $𝑉$ , which are chains. It is well ordered: let $𝐴 \subseteq 𝑈$ be nonempty, pick $𝑎 \in 𝐴$ in some tower $𝑊$ , and let $𝑚$ be the least element of $𝐴 \cap 𝑊$ . If $𝑏 \in 𝐴$ had $𝑏 < 𝑚$ , then $𝑏 \in$ $𝑈_{< 𝑚} =$ $𝑊_{< 𝑚}$ , so $𝑏 \in 𝐴 \cap 𝑊$ and $𝑏 < 𝑚$ , which is impossible. As $𝑈$ is a chain, $𝑚 \leq 𝑏$ for all $𝑏 \in 𝐴$ . Finally, for $𝑢 \in 𝑈$ , say $𝑢 \in 𝑊$ , we have $𝑠 (𝑈_{< 𝑢}) =$ $𝑠 (𝑊_{< 𝑢}) =$ $𝑢$ . So $𝑈$ is a tower.

Step 4. Contradiction. Let $𝑝 = 𝑠 (𝑈)$ , a strict upper bound of the chain $𝑈$ , so $𝑝 \notin 𝑈$ . Then $𝑈^{'} = 𝑈 \cup {𝑝}$ is a tower: a nonempty subset of $𝑈^{'}$ has as least element its least element in $𝑈$ if it meets $𝑈$ , and $𝑝$ otherwise; $𝑈_{< 𝑝}^{'} = 𝑈$ and $𝑠 (𝑈) = 𝑝$ ; and for $𝑢 \in 𝑈$ , $𝑈_{< 𝑢}^{'} =$ $𝑈_{< 𝑢}$ since $𝑝 > 𝑢$ , so $𝑠 (𝑈_{< 𝑢}^{'}) = 𝑢$ . Hence $𝑈^{'} \subseteq 𝑈$ by definition of $𝑈$ , and $𝑝 \in 𝑈$ , a contradiction. So $𝑃$ has a maximal element. □

A.4.3Using Zorn’s lemma

Every application in linear algebra has the same three steps, and the second step rests on one small fact: a union of a chain of sets is “finitary”, in that any finitely many of its elements already lie in one member of the chain. Spans and linear relations only ever involve finitely many vectors, so this is what lets linear properties pass to the union.

Technique A.4.5 (Apply Zorn’s lemma). To prove that an object with some property exists in a possibly infinite-dimensional setting:

Let $𝑃$ be the set of partial objects (independent sets, subspaces meeting $𝑈$ only in $𝟎$ , maps defined on part of the space, $\dots$ ), ordered by inclusion or by extension. Check that $𝑃 \neq \emptyset$ .
Show that every nonempty chain in $𝑃$ has an upper bound in $𝑃$ . The candidate is almost always the union. The work is to show that the union is still in $𝑃$ , and Lemma A.4.6 does most of it.
Let $𝑚$ be a maximal element. Show that $𝑚$ is a complete object, by contradiction: if it were not, enlarge it by one vector (or one point), and check that the enlargement is still in $𝑃$ .

Reach for it whenever a finite-dimensional proof proceeds by “add one more until done”. The canonical example is Theorem A.4.7; Section 15.1 applies it to linearly independent sets.

Used in 2 places

Theorem A.4.7, Exercise A.4.11.

Lemma A.4.6 (Finitely many elements of a union of a chain). Let

Γ

be a nonempty set of sets that is a chain under

\subseteq

, and let

𝑥_{1}, \dots, 𝑥_{𝑘}

, with

𝑘 \geq 0

, be elements of the union

⋃ Γ

. Then some single member of

Γ

contains all of

𝑥_{1}, \dots, 𝑥_{𝑘}

Proof.routine

Uses. Definition A.4.1 (Partial order), Theorem A.2.1 (Induction, strong induction, and well-ordering)

Hint 1. Each

𝑥_{𝑖}

lies in some member

𝐶_{𝑖}

. Among finitely many members of a chain, one contains all the others.

Hint 2. Prove the last statement by induction on the number of members.

Sketch. Pick

𝐶_{𝑖} \in Γ

with

𝑥_{𝑖} \in 𝐶_{𝑖}

. Finitely many members of a chain have a largest one, by induction: the larger of

𝐶_{𝑘}

and the largest of

𝐶_{1}, \dots, 𝐶_{𝑘 - 1}

. It contains every

𝑥_{𝑖}

. For

𝑘 = 0

, any member works.

For

𝑘 = 0

any member of

Γ

works, since

Γ \neq \emptyset

. For

𝑘 \geq 1

, pick

𝐶_{𝑖} \in Γ

with

𝑥_{𝑖} \in 𝐶_{𝑖}

for each

𝑖

. We show by induction on

𝑘

that one of

𝐶_{1}, \dots, 𝐶_{𝑘}

contains all the others. For

𝑘 = 1

this is clear. If

𝐶_{𝑗}

contains

𝐶_{1}, \dots, 𝐶_{𝑘 - 1}

, then

𝐶_{𝑗}

and

𝐶_{𝑘}

are comparable since

Γ

is a chain, and the larger of the two contains all of

𝐶_{1}, \dots, 𝐶_{𝑘}

. That member contains

𝑥_{1}, \dots, 𝑥_{𝑘}

. □

In Section 4.4, every subspace of a finite-dimensional space was shown to have a complement by extending a basis of the subspace (Proposition 4.4.16). The same statement holds in every vector space, and the proof is a direct application of Zorn’s lemma, without bases.

Theorem A.4.7 (Complements exist). Let

𝑉

be any vector space over

𝐹

, and

𝑈

a subspace of

𝑉

. Then there is a subspace

𝑊

𝑉

with

𝑉 = 𝑈 \oplus 𝑊

Intuition. We want

𝑊

as large as possible subject to

𝑊 \cap 𝑈 = {𝟎}

, because then

𝑈 + 𝑊

should be all of

𝑉

: if some

𝐯

were missing, we could add it to

𝑊

without creating an intersection with

𝑈

. In finite dimensions “as large as possible” can be achieved by adding one vector at a time. Here Zorn’s lemma provides it, once we check that the union of a nested family of such subspaces is again one.

Proof.hard

Uses. Theorem A.4.4 (Zorn’s lemma), Lemma A.4.6 (Finitely many elements of a union of a chain), Theorem 1.4.3 (Subspace criterion), Theorem 4.4.7 (Criteria for direct sums)

Techniques. Apply Zorn’s lemma (Technique A.4.5), Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Let

𝑃

be the set of subspaces

𝑊

with

𝑊 \cap 𝑈 = {𝟎}

, ordered by

\subseteq

. Why is

𝑃

nonempty?

Hint 2. For a nonempty chain in

𝑃

, show that the union is a subspace and still meets

𝑈

only in

𝟎

. Two vectors of the union lie in one member of the chain.

Hint 3. If

𝑊

is maximal and

𝐯 \notin 𝑈 + 𝑊

, show that

𝑊 + span (𝐯)

is in

𝑃

. If

𝐰 + 𝑐 𝐯 \in 𝑈

, why must

𝑐 = 0

Sketch. Let

𝑃 =

{𝑊 subspace | 𝑊 \cap 𝑈 = {𝟎}}

, which contains

{𝟎}

. The union of a nonempty chain is a subspace, since any two of its vectors lie in a common member, and it meets

𝑈

only in

𝟎

; so it is an upper bound. Zorn gives a maximal

𝑊

. If

𝐯 \notin 𝑈 + 𝑊

, then

𝑊 + span (𝐯)

still meets

𝑈

trivially:

𝐰 + 𝑐 𝐯 \in 𝑈

with

𝑐 \neq 0

would put

𝐯

𝑈 + 𝑊

. This contradicts maximality, so

𝑈 + 𝑊 = 𝑉

, and the sum is direct.

Let $𝑃$ be the set of subspaces $𝑊$ of $𝑉$ with $𝑊 \cap 𝑈 = {𝟎}$ , ordered by inclusion. It contains ${𝟎}$ , so it is nonempty.

Let $Γ$ be a nonempty chain in $𝑃$ , and $𝑊^{*} = ⋃ Γ$ . We show that $𝑊^{*} \in 𝑃$ ; it is then an upper bound of $Γ$ . It contains $𝟎$ . If $𝐰, 𝐰^{'} \in 𝑊^{*}$ and $𝑎 \in 𝐹$ , then by Lemma A.4.6 both lie in one $𝐶 \in Γ$ , which is a subspace, so $𝐰 + 𝐰^{'} \in 𝐶 \subseteq 𝑊^{*}$ and $𝑎 𝐰 \in 𝐶 \subseteq 𝑊^{*}$ . So $𝑊^{*}$ is a subspace (Theorem 1.4.3). If $𝐰 \in 𝑊^{*} \cap 𝑈$ , then $𝐰 \in 𝐶$ for some $𝐶 \in Γ$ , so $𝐰 \in 𝐶 \cap 𝑈 = {𝟎}$ . Hence $𝑊^{*} \in 𝑃$ .

By Zorn’s lemma (Theorem A.4.4), $𝑃$ has a maximal element $𝑊$ . Suppose for contradiction that $𝑈 + 𝑊 \neq 𝑉$ , and pick $𝐯 \in 𝑉 ∖ (𝑈 + 𝑊)$ . Let $𝑊^{'} = 𝑊 + span (𝐯)$ , a subspace containing $𝑊$ , with $𝑊^{'} \neq 𝑊$ since $𝐯 \notin 𝑊$ . We claim $𝑊^{'} \in 𝑃$ . Let $𝐰 + 𝑐 𝐯 \in 𝑈$ with $𝐰 \in 𝑊$ and $𝑐 \in 𝐹$ , say $𝐰 + 𝑐 𝐯 = 𝐮$ . If $𝑐 \neq 0$ , then $𝐯 =$ $𝑐^{- 1} (𝐮 - 𝐰) \in$ $𝑈 +$ $𝑊$ , which is false. So $𝑐 = 0$ , and $𝐰 = 𝐮 \in 𝑊 \cap 𝑈 = {𝟎}$ . Hence $𝑊^{'} \cap 𝑈 = {𝟎}$ , so $𝑊^{'} \in 𝑃$ and $𝑊 ⊊ 𝑊^{'}$ , contradicting maximality.

Therefore $𝑈 + 𝑊 = 𝑉$ and $𝑈 \cap 𝑊 = {𝟎}$ , so $𝑉 = 𝑈 \oplus 𝑊$ by Theorem 4.4.7. □

The proof gives no way to write $𝑊$ down. For $𝑉 = ℝ$ over $ℚ$ and $𝑈 = ℚ$ , the theorem produces a $ℚ$ -subspace $𝑊$ of $ℝ$ with $ℝ = ℚ \oplus 𝑊$ , so that every real number is uniquely a rational plus an element of $𝑊$ , but nobody can describe such a $𝑊$ explicitly. Such sets are the price of the axiom of choice. In Section 4.6, this is one reason to prefer the quotient $𝑉 / 𝑈$ to a complement: the quotient is constructed, not chosen.

Exercises

Exercise A.4.8.routine Without using Zorn’s lemma, show that every finite nonempty partially ordered set has a maximal element.

Solution.

Uses. Definition A.4.1 (Partial order), Definition A.4.2 (Upper bound, maximal element), Corollary A.1.18 (Cardinality is well defined)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Look at strictly increasing sequences

𝑝_{1} <

𝑝_{2} <

\dots <

𝑝_{𝑘}

. Why are their entries distinct, and why is

𝑘 \leq | 𝑃 |

Hint 2. Take such a sequence with

𝑘

as large as possible. Its last entry is maximal.

Sketch. The entries of a strictly increasing sequence are distinct (by transitivity and antisymmetry), so its length is at most

| 𝑃 |

. A longest one exists, since one-term sequences exist, and its last entry

𝑝_{𝑘}

is maximal:

𝑝_{𝑘} < 𝑝

would give a longer sequence.

In a strictly increasing sequence

𝑝_{1} <

𝑝_{2} <

\dots <

𝑝_{𝑘}

, the entries are distinct: if

𝑖 < 𝑗

, then

𝑝_{𝑖} < 𝑝_{𝑗}

by transitivity, and if

𝑝_{𝑖} = 𝑝_{𝑗}

this would read

𝑝_{𝑖} \leq 𝑝_{𝑖 + 1}

and

𝑝_{𝑖 + 1} \leq 𝑝_{𝑗} = 𝑝_{𝑖}

, so

𝑝_{𝑖} = 𝑝_{𝑖 + 1}

by antisymmetry, contradicting

𝑝_{𝑖} < 𝑝_{𝑖 + 1}

. So

𝑖 \mapsto 𝑝_{𝑖}

is an injection

[𝑘] \to 𝑃

, and

𝑘 \leq | 𝑃 |

(Corollary A.1.18). Since

𝑃 \neq \emptyset

, there are sequences of length

1

, so there is a strictly increasing sequence of maximal length

𝑘

. Its last entry

𝑝_{𝑘}

is maximal: if

𝑝_{𝑘} \leq 𝑝

with

𝑝 \neq 𝑝_{𝑘}

, then

𝑝_{1} <

\dots <

𝑝_{𝑘} <

𝑝

would be longer.

Exercise A.4.9.standard Find the error in the following argument.

Claim: Every nonzero vector space $𝑉$ has a maximal proper subspace. Proof: Let $𝑃$ be the set of proper subspaces of $𝑉$ , ordered by $\subseteq$ . It contains ${𝟎}$ . If $Γ$ is a nonempty chain in $𝑃$ , its union is a subspace by the argument in the proof of Theorem A.4.7, and it contains every member of $Γ$ , so it is an upper bound. By Zorn’s lemma, $𝑃$ has a maximal element.

Solution.

Uses. Theorem A.4.4 (Zorn’s lemma), Example A.4.3 (Chains and maximal elements)

Hint 1. An upper bound has to be an element of

𝑃

. Is the union of a chain of proper subspaces proper?

Hint 2. Look at Example A.4.3(c).

Sketch. The union is a subspace, but it need not be proper, so it need not lie in

𝑃

: in

𝐹 [𝑥]

the union of the chain

{𝐹 [𝑥]}_{\leq 𝑛}

𝐹 [𝑥]

. The claim is still true (Exercise A.4.10), but the proof must keep the union away from

𝑉

, for instance by fixing a vector it must avoid.

The union of the chain is a subspace containing every member, but an upper bound must be an element of $𝑃$ , that is, a proper subspace, and the argument never checks this. It can fail: in $𝑉 = 𝐹 [𝑥]$ , the subspaces ${𝐹 [𝑥]}_{\leq 𝑛}$ , $𝑛 \geq 0$ , form a chain of proper subspaces whose union is $𝐹 [𝑥]$ (Example A.4.3(c)). So the hypothesis of Zorn’s lemma has not been verified.

The claim itself is true. One way to repair the proof is to fix $𝐯 \neq 𝟎$ and let $𝑃$ be the set of subspaces that do not contain $𝐯$ . It contains ${𝟎}$ , and the union of a nonempty chain in $𝑃$ is a subspace that does not contain $𝐯$ , so it lies in $𝑃$ . Let $𝑀$ be a maximal element. If some $𝐱$ were not in $𝑀 + span (𝐯)$ , then $𝑀 + span (𝐱)$ would not contain $𝐯$ (from $𝐯 = 𝐦 + 𝑐 𝐱$ we would get $𝑐 \neq 0$ and $𝐱 =$ $𝑐^{- 1} (𝐯 - 𝐦) \in$ $𝑀 +$ $span (𝐯)$ ), contradicting maximality. So $𝑉 = 𝑀 + span (𝐯)$ . Every subspace strictly containing $𝑀$ contains $𝐯$ , by maximality, and hence equals $𝑉$ ; so $𝑀$ is a maximal proper subspace. Exercise A.4.10 gives another route.

Exercise A.4.10.standard Let

𝑉

be any vector space,

𝑈

a subspace, and

𝐯 \in 𝑉 ∖ 𝑈

. Show that there is a linear map

𝜑 : 𝑉 \to 𝐹

with

𝜑 (𝐮) = 0

for all

𝐮 \in 𝑈

and

𝜑 (𝐯) = 1

. Deduce that every nonzero vector space has a maximal proper subspace.

Solution.

Uses. Theorem A.4.7 (Complements exist), Theorem 4.4.7 (Criteria for direct sums), Definition 4.4.4 (Direct sum), Definition 2.1.1 (Linear map)

Techniques. Check that a definition does not depend on the representative (Technique 4.6.18)

Hint 1. The sum

𝑈 + span (𝐯)

is direct. Take a complement

𝑊

of it.

Hint 2. Every vector is uniquely

𝐮 + 𝑐 𝐯 + 𝐰

. Let

𝜑

read off

𝑐

Hint 3. For the last part,

ker 𝜑

is a proper subspace. Why is it maximal?

Sketch.

𝑈 \cap span (𝐯) = {𝟎}

, so

𝑈^{'} = 𝑈 \oplus span (𝐯)

; by Theorem A.4.7,

𝑉 = 𝑈 \oplus span (𝐯) \oplus 𝑊

. Define

𝜑 (𝐮 + 𝑐 𝐯 + 𝐰) = 𝑐

, well defined by uniqueness of decompositions and linear by comparing decompositions. With

𝑈 = {𝟎}

ker 𝜑

is a proper subspace with

𝑉 = ker 𝜑 \oplus span (𝐯)

, and any subspace strictly containing it contains

𝐯

If $𝑐 𝐯 \in 𝑈$ with $𝑐 \neq 0$ , then $𝐯 \in 𝑈$ ; so $𝑈 \cap span (𝐯) = {𝟎}$ , and the sum $𝑈^{'} = 𝑈 + span (𝐯)$ is direct (Theorem 4.4.7). By Theorem A.4.7 there is $𝑊$ with $𝑉 = 𝑈^{'} \oplus 𝑊$ . So every $𝐱 \in 𝑉$ has exactly one decomposition $𝐱 = 𝐮 + 𝑐 𝐯 + 𝐰$ with $𝐮 \in 𝑈$ , $𝑐 \in 𝐹$ , $𝐰 \in 𝑊$ (the coefficient $𝑐$ is unique because $𝐯 \neq 𝟎$ ). Define $𝜑 (𝐱) = 𝑐$ . This is a function because the decomposition is unique. It is linear: if $𝐱 = 𝐮 + 𝑐 𝐯 + 𝐰$ and $𝐱^{'} = 𝐮^{'} + 𝑐^{'} 𝐯 + 𝐰^{'}$ , then $𝑎 𝐱 +$ $𝐱^{'} =$ $(𝑎 𝐮 + 𝐮^{'}) +$ $(𝑎 𝑐 + 𝑐^{'}) 𝐯 +$ $(𝑎 𝐰 + 𝐰^{'})$ is the decomposition of $𝑎 𝐱 + 𝐱^{'}$ , so $𝜑 (𝑎 𝐱 + 𝐱^{'}) =$ $𝑎 𝑐 +$ $𝑐^{'}$ . Clearly $𝜑 (𝐮) = 0$ for $𝐮 \in 𝑈$ and $𝜑 (𝐯) = 1$ .

Now let $𝑉 \neq {𝟎}$ , pick $𝐯 \neq 𝟎$ , and apply this with $𝑈 = {𝟎}$ . Then $𝑀 = ker 𝜑$ is a subspace not containing $𝐯$ , so it is proper. Every $𝐱 \in 𝑉$ equals $(𝐱 - 𝜑 (𝐱) 𝐯) +$ $𝜑 (𝐱) 𝐯$ with the first term in $𝑀$ , so $𝑉 = 𝑀 + span (𝐯)$ . If $𝑀^{'}$ is a subspace with $𝑀 ⊊ 𝑀^{'}$ , pick $𝐱 \in 𝑀^{'} ∖ 𝑀$ ; then $𝐱 -$ $𝜑 (𝐱) 𝐯 \in$ $𝑀 \subseteq$ $𝑀^{'}$ and $𝜑 (𝐱) \neq 0$ , so $𝐯 \in 𝑀^{'}$ and $𝑀^{'} \supseteq$ $𝑀 +$ $span (𝐯) =$ $𝑉$ . So $𝑀$ is a maximal proper subspace.

Exercise A.4.11.hard Use Zorn’s lemma to prove that every surjective function

𝑓 : 𝑋 \to 𝑌

has a right inverse, without using the axiom of choice directly. (So Zorn’s lemma implies the axiom of choice, by Remark A.1.13.)

Solution.

Uses. Theorem A.4.4 (Zorn’s lemma), Lemma A.4.6 (Finitely many elements of a union of a chain), Theorem A.1.12 (One-sided inverses of functions)

Techniques. Apply Zorn’s lemma (Technique A.4.5)

Hint 1. Let

𝑃

be the set of partial right inverses: pairs

(𝐴, 𝑔)

with

𝐴 \subseteq 𝑌

and

𝑔 : 𝐴 \to 𝑋

such that

𝑓 (𝑔 (𝑎)) = 𝑎

for all

𝑎 \in 𝐴

. Order them by extension:

(𝐴, 𝑔) \leq (𝐴^{'}, 𝑔^{'})

𝐴 \subseteq 𝐴^{'}

and

𝑔^{'}

agrees with

𝑔

𝐴

Hint 2. For a nonempty chain, define

𝑔^{*}

on the union of the domains by “use any member of the chain whose domain contains the point”. Why is this well defined?

Hint 3. If a maximal

(𝐴, 𝑔)

has

𝐴 \neq 𝑌

, extend

𝑔

to one more point

𝑦

by choosing one preimage of

𝑦

. A single choice needs no axiom.

Sketch. Partial right inverses, ordered by extension, form a partially ordered set containing

(\emptyset, empty function)

. The union of a chain is a partial right inverse, well defined because any two members agree where both are defined. A maximal

(𝐴, 𝑔)

has

𝐴 = 𝑌

: otherwise send one

𝑦 \notin 𝐴

to one of its preimages, which extends

𝑔

strictly.

Let $𝑃$ be the set of pairs $(𝐴, 𝑔)$ with $𝐴 \subseteq 𝑌$ and $𝑔 : 𝐴 \to 𝑋$ such that $𝑓 (𝑔 (𝑎)) = 𝑎$ for every $𝑎 \in 𝐴$ . Order $𝑃$ by $(𝐴, 𝑔) \leq (𝐴^{'}, 𝑔^{'})$ if $𝐴 \subseteq 𝐴^{'}$ and $𝑔^{'} (𝑎) = 𝑔 (𝑎)$ for all $𝑎 \in 𝐴$ . This is a partial order: reflexivity and transitivity are clear, and if $(𝐴, 𝑔) \leq$ $(𝐴^{'}, 𝑔^{'}) \leq$ $(𝐴, 𝑔)$ , then $𝐴 = 𝐴^{'}$ and $𝑔 = 𝑔^{'}$ . $𝑃$ contains $(\emptyset, 𝑔_{\emptyset})$ with $𝑔_{\emptyset}$ the empty function, so $𝑃 \neq \emptyset$ .

Let $Γ \subseteq 𝑃$ be a nonempty chain, and let $𝐴^{*}$ be the union of the domains $𝐴$ of its members. For $𝑦 \in 𝐴^{*}$ , define $𝑔^{*} (𝑦) = 𝑔 (𝑦)$ for any $(𝐴, 𝑔) \in Γ$ with $𝑦 \in 𝐴$ . This does not depend on the member chosen: if $𝑦 \in 𝐴$ and $𝑦 \in 𝐴^{'}$ for $(𝐴, 𝑔),$ $(𝐴^{'}, 𝑔^{'}) \in$ $Γ$ , these are comparable, say $(𝐴, 𝑔) \leq (𝐴^{'}, 𝑔^{'})$ , and then $𝑔^{'} (𝑦) = 𝑔 (𝑦)$ . So $𝑔^{*} : 𝐴^{*} \to 𝑋$ is a function with $𝑓 (𝑔^{*} (𝑦)) =$ $𝑓 (𝑔 (𝑦)) =$ $𝑦$ , and $(𝐴^{*}, 𝑔^{*}) \in 𝑃$ is an upper bound of $Γ$ .

By Zorn’s lemma, $𝑃$ has a maximal element $(𝐴, 𝑔)$ . Suppose $𝐴 \neq 𝑌$ and pick $𝑦_{0} \in 𝑌 ∖ 𝐴$ . Since $𝑓$ is surjective, there is some $𝑥_{0}$ with $𝑓 (𝑥_{0}) = 𝑦_{0}$ ; this is one choice, which needs no axiom. Extending $𝑔$ by $𝑔 (𝑦_{0}) = 𝑥_{0}$ gives an element of $𝑃$ strictly larger than $(𝐴, 𝑔)$ , a contradiction. So $𝐴 = 𝑌$ , and $𝑓 \circ 𝑔 = {id}_{𝑌}$ .

More practice

The practice bank has 3 exercises on this section’s topics.