Functional Analysis – Motivation for Zorn’s Lemma

axiom-of-choicefunctional-analysisintuitionset-theory

I have been reading Kreyszig's book on functional analysis, where it uses Zorn's lemma to prove the Hahn Banach theorem. However I don't quite get what Zorn's lemma is saying.

I understand that it is an axiom and it is equivalent to the axiom of choice, but axiom of choice seems much more intuitive to me. So is there any way to understand the Zorn's lemma in a more intuitive way?

Best Answer

I had similar conceptual trouble until I came across Tim Gowers' blog post on How to use Zorn's lemma. Its main thesis:

If you are building a mathematical object in stages and find that (i) you have not finished even after infinitely many stages, and (ii) there seems to be nothing to stop you continuing to build, then Zorn’s lemma may well be able to help you.

He shows how to use the Lemma in a number of cases where my intuitive approach would have been something like "ah, but we can construct the thing by transfinite induction ... let's find a sufficiently large ordinal to induct over (work, work, work) ... and then fix a choice function such that we can make choices at each step along the way (work, work, work) ... and if the thing is still not made when we reach the top of our chosen ordinal, it would be (work, work) a contradiction".

Compared to that, Zorn's Lemma packs a lot of boilerplate argument into a simple, tidy, reuseable tool where one just needs to specify the minimal properties of the situation for the construction to work. In particular the apparently ill-motivated condition about chains is exactly what is needed for the tedious transfinite-induction argument to keep rolling when we hit a limit ordinal.

Related Solutions

[Math] Bourbaki Proof of Zorn’s Lemma in Lang’s Algebra

The proof I saw was using, essentially, the Hausdorff Maximality Principle.

Hausdorff Maximality Principle (HMP). Every partially ordered chain has a $\subseteq$-maximal chain.

Clearly if $(P,\leq)$ is a partially ordered set satisfying the conditions for Zorn's lemma, and $C\subseteq P$ is a maximal chain then $C$ has an upper bound $c$ and by the maximality of $C$ we have to have $c\in C$ and that it is a maximal element.

The proof seems to go through other means to prove HMP, and it uses the Bourbaki-Witt theorem.

The Bourbaki-Witt theorem does not rely on the axiom of choice at all. It is provable in ZF, as remarked by Brian here. The reason it is provable in ZF is that it assumes the existence of a least upper bound of every chain, and therefore allows a canonical choice for $a_1$ when moving from $D_0$ to $D_1$ (and so on).

The axiom of choice comes in, full-blown power, in the proof of Corollary 2.4:

Suppose that $A$ does not have a maximal element. Then for each $x\in A$ there is an element $y_x\in A$ such that $x<y_x$. Let $f\colon A\to A$ be the map such that $f(x)=y_x$ for all $x\in A$.

Here we actually say that $f$ is a choice function. In the proof of the Bourbaki-Witt theorem we needed to know what is the next step in "growing up", but we assumed that $f$ was given to us. From that it was just a matter of finishing the proof.

But in this corollary we need to actually define $f$. And this requires the axiom of choice.

I should add that there are books full of equivalents to the axiom of choice, and there are a lot of them which are very not-set theoretical axioms, or very unrelated to well-ordering (e.g. "Every non-empty set can be made into a group"). Since they are all equivalent to the axiom of choice, all of them are equivalent to Zorn's lemma.

[Math] Hahn-Banach Theorem for separable spaces without Zorn’s Lemma

Note: I completely rewrote my previous attempt - posted in another (now deleted) answer, since the previous version was incorrect. Thanks to Asaf Karagila for pointing out the problem with my previous proof. And also to Eric Wofsey for simplifying some steps in the proof.

Let us hope that this time I have avoided mistakes. The formulation of the version of HBT which I am trying to prove in ZF is adapted from the claims mentioned in this paper. Some remarks explaining what this paper proves about the relation between ZF, AC and HBT for separable spaces can be found below.

As the OP wrote, there are several formulations of Hahn-Banach Theorem. So maybe it is good to start by clearly stating this result.

Hahn-Banach Theorem. Let $X$ be a vector space and let $p:X\to{\mathbb R}$ be any sublinear function. Let $M$ be a vector subspace of $X$ and let $f:M\to{\mathbb R}$ be a linear functional dominated by $p$ on $M$. Then there is a linear extension $\widehat{f}$ of $f$ to $X$ that is dominated by $p$ on $X$.

The formulation that $f$ is dominated by $p$ on $M$ means that $(\forall x\in M) f(x)\le p(x)$.

This is basically the usual formulation of Hahn-Banach Theorem; although you can find many slight variations.

We will try to prove this in ZF:

Hahn-Banach Theorem in ZF. Let $X$ be a separable topological vector space and let $p:X\to{\mathbb R}$ be a continuous sublinear function. Let $M$ be a vector subspace of $X$ and let $f:M\to{\mathbb R}$ be a linear functional dominated by $p$ on $M$. Then there is a linear extension $\widehat{f}$ of $f$ to $X$ that is dominated by $p$ on $X$.

You may notice that this implies that every bounded functional on a subspace $M$ of a separable normed space $X$ can be extended to a functional on $X$ with the same norm. This is is the version of HBT stated here.

Notice a few changes in the formulation of the theorem. Since we want to speak about separable spaces, we need some kind of topology. So it is not that surprising that we work now with topological vector spaces. Maybe it is a little bit surprising that we require $p$ to be continuous. (On the other hand, if we want to use separability, then it is perhaps natural that we will probably use somewhere in the proof that $p$ behaves reasonable w.r.t. the topological structure.) But let us try to prove this version first. We will return to the question, whether continuity of $p$ is needed, later.

The standard proof of HBT uses as one of the steps the following fact:

Lemma. Let $X$ be a vector space and let $p:X\to{\mathbb R}$ be a sublinear function. Let $M$ be a vector subspace of $X$ and let $f:M\to{\mathbb R}$ be a linear functional dominated by $p$ on $M$. Let $x\in X$ and let $c\in\mathbb R$ be a number such that $$\sup_{y\in M} [f(y)-p(y-{x})] \le c \le \inf_{y\in M} [p(y+{x})-f(y)].$$

Then there exists a linear function $\overline f \colon [M\cup\{x\}]\to \mathbb R$ which extends $f$, it is dominated by $p$ on $[M\cup\{x\}]$ and $$f(x)=c.$$

Now we can prove this version of HBT in the following steps:

Prove the above lemma. And also check that under the assumptions of the lemma $$\sup_{y\in M} [f(y)-p(y-x)] \le \inf_{y\in M} [p(y+{x})-f(y)].$$ which means that we have at least one possible choice of $c$ in such situation.
If $X$ is separable and $\{x_n; n\in\mathbb N\}$ is a countable dense subset of $X$, then we can prove using induction and the above lemma that there exists a linear functional $f_n$ defined on $A_n=[M\cup\{x_1,\dots,x_n\}]$ which agrees with $f$ on $M$ and is dominated by $p$ on $A_n$. Moreover, each $f_n$ extends $f_{n-1}$.
Notice that in the induction step of this proof we choose some value of $c$ from a non-empty interval. Since the interval is closed, we can simply take the left endpoint at each step of the induction. So we do not need Axiom of Choice here.
The above gives us a new linear functional $g$ defined on a dense subspace $A=\bigcup A_n$. (Given simply by $g=\bigcup f_n$, i.e., $g(x)=f_n(x)$ if $x\in A_n$.) Moreover, $g$ is dominated by $p$ on $A$ and $g$ extends $f$.
Now it only remains to get from the function defined on the set $A$ the extension to the $\overline A=X$. I.e., we want to show get a function $\widehat f \colon X \to \mathbb R$ which is also linear, dominated by $p$ and fulfills $\widehat f|_M=f$. If we have $x\in X$ then there exists a sequence $(a_n)$ of points of $A$ such that $a_n\to x$. We define $$\widehat f(x):=\lim\limits_{n\to\infty} g(a_n).$$ If we can show that this indeed defines a function (i.e., that the above limit exists and that the value of $\widehat f(x)$ does not depend on the choice of the sequence $(a_n)$), then proving that $\widehat f$ is linear, extends $f$ and is dominated by $p$ is more-or-less straightforward. (Notice that here we will have to use continuity of $p$.)

Let us have a closer look at a more detailed proof of existence and uniqueness of the above limit. (Since this is precisely the place where my previous attempt failed.)

It is worth pointing out that we repeatedly use continuity of $p$. To be more precise, we use $p(a_n)\to p(x)$.

We will use rather simple observation that $g(x)=-g(-x)\ge -p(-x)$, so we have $$-p(-x)\le g(x) \le p(x)$$ for any $x\in A$. Now if we have a sequence $a_n\to x$, we can use the inequality $$-p(a_n-a_m) \le g(a_m-a_n) \le p(a_m-a_n)$$ to show that the sequence $(g(a_n))$ is Cauchy sequence in $\mathbb R$, and therefore it has a limit. Similarly if we have $a_n\to a$ and $b_n\to a$, we can use $$-p(b_n-a_n)\le g(a_n-b_n) \le p(a_n-b_n)$$ to show that $\lim g(a_n)=\lim g(b_n)$.

Putting all things mentioned above together we get the proof of the above result.

Would it be possible to prove stronger result - to omit condition that $p$ is continuous and just leave the sublinearity? The answer is no, which shows that these problems might be a bit more subtle than they could appear on the first glance. It is shown in the paper Juliette Dodu and Marianne Morillon: The Hahn-Banach Property and the Axiom of Choice (Mathematical Logic Quarterly, Volume 45, Issue 3, pages 299–314, 1999, DOI: 10.1002/malq.19990450303) that if every separable normed space satisfies the Hahn-Banach property (i.e., if the above theorem holds without the assumption that the sublinear function $p$ is continuous), then there are non-trivial finitely-additive measures on the set of positive integers. Therefore this result cannot be shown in ZF. (See Theorem 6 and Corollary 4 in Section 9 of this paper for details.)

The authors also say the following:

If a topological vector space $E$ has a dense subset which is well-orderable, then $E$ satisfies the continuous Hahn-Banach property, and the proof relies on some transfinite recursion and the following classical lemma... In particular, separable norme spaces satisfy the continuous Hahn-Banach property.

The "classical lemma" mentioned there is the lemma I formulated above. And if the dense subset is countable, then this is the above claim (for which I tried at least to sketch a proof).

If $X$ is not separable, then the argument above cannot be used to get a function $\widehat f$ defined on the whole space $X$. But the usual proof of Hahn-Banach Theorem is along the same lines, we just use Zorn's Lemma or transfinite induction instead of mathematical induction. (Zorn's lemma is known to be equivalent to the Axiom of Choice. The proof based on transfinite induction uses AC too, since we start by choosing some well-ordering of $X$. Well-ordering theorem is equivalent to AC.)

The only step in which the above proof and the usual proof of HBT differ substantially is the extensions from a dense subspace to the whole space. This is the point of the proof where we used continuity of the sublinear function $p$. (And this condition is not needed if AC is available.)

Best Answer

Related Solutions

[Math] Bourbaki Proof of Zorn’s Lemma in Lang’s Algebra

[Math] Hahn-Banach Theorem for separable spaces without Zorn’s Lemma

Related Question