Intereting Posts

Sum of all real solutions for $x$ to the equation $\displaystyle (x^2+4x+6)^{{(x^2+4x+6)}^{\left(x^2+4x+6\right)}}=2014.$
Simplifying $\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}\binom{n}{2k}2^{2k}$
Limit Summation interchanging
This is a possible proof of the Riemann Hypothesis
Subgroups of $S_6$
Proving no polynomial $P(x)$ exists such that $P(a) = b$, $P(b) = c$, $P(c) = a$
A polynomial that is zero on an open set
The same bit of trivial algebra in two different places?
Show that for all real numbers $a$ and $b$, $\,\, ab \le (1/2)(a^2+b^2)$
$\epsilon$-$\delta$ proof that $\lim\limits_{x \to 1} \frac{1}{x} = 1$.
Showing associativity of (x*y) = (xy)/(x+y+1)
Dimension of the sum of two vector subspaces
Prove the inequality: $\frac{a}{c+a-b}+\frac{b}{a+b-c}+\frac{c}{b+c-a}\ge{3}$
Showing $~\prod (a^{2}+2)\geq 9\sum ab$
How to show that $f$ is constant by using Liouville's theorem?

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?

- Is there an element with no fixed point and of infinite order in $\operatorname{Sym}(X)$ for $X$ infinite?
- Hahn-Banach Theorem for separable spaces without Zorn's Lemma
- There's non-Aleph transfinite cardinals without the axiom of choice?
- Prove that every set with more than one element has a permutation without fixed points
- A confusion about Axiom of Choice and existence of maximal ideals.
- Is Zorn's lemma required to prove the existence of a maximal atlas on a manifold?

- How generalize the bicommutant theorem?
- Existence of a prime ideal in an integral domain of finite type over a field without Axiom of Choice
- Example of a compact set that isn't the spectrum of an operator
- polynomial approximation in Hardy space $H^\infty$
- Why a non-diagonalizable matrix can be approximated by an infinite sequence of diagonalizable matrices?
- (ZF)subsequence convergent to a limit point of a sequence
- Is this equality true or it is not necessarily true?
- Finite-dimensional subspaces of normed vector spaces are direct summands
- Trying to prove that operator is compact
- To show that the complement of the kernel of an unbounded linear functional is path connected

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.

This blog post by Tim Gowers has a nice discussion.

Suppose you have some process of choosing elements from a partially ordered set, and nothing seems to stop you from choosing bigger and bigger elements, no matter how many elements you already have. Zorn’s Lemma says that the process must stop.

For example, to prove that every vector space has a basis: Start with the empty set, and keep on adding elements that are linearly independent of the existing elements. No matter how big the set gets, if it’s not already a basis, then you can add another element to it, even after infinitely many steps: If $X$ is a linearly independent subset of a vector space $V$, then either $X$ is a basis, or else (no matter how big $X$ is), there exists some $x \in V$ which is independent of $X$, and you can add it to $X$ to get a bigger linearly independent set. Zorn’s Lemma says this process must terminate, at which point you have a basis.

In fact, this intuitive description can be turned into a proof of Zorn’s Lemma: Let $X$ be a nonempty partially ordered set in which every totally ordered subset has an upper bound. Suppose $X$ has no maximal element. Choose $x_1 \in X$. It’s not maximal, so I can find $x_2 > x_1$. But $x_2$ is not maximal, so I can find $x_3 > x_2$, etc., leading to $x_1 < x_2 < x_3 < x_4 < \ldots$ These $x_i$’s form a totally ordered subset, hence there is an element $x_\omega$ dominating all of them. But $x_\omega$ is not maximal, so there is $x_{\omega+1}$, etc. Nothing stops me from obtaining an $x_\alpha \in X$ for every ordinal $\alpha$. But the size of every set is bounded by a fixed ordinal (see the Burali-Forti paradox), contradiction.

Zorn’s lemma, in simple words, tells us that if every chain has an upper bound then there is a maximal element. This is not necessarily a maximum and there could be many maximal elements.

The fact that we need this lemma to begin with is that the “road” to that maximal element can be *very* non-constructive, and we need to assert its existence using the axiom of choice.

If you want to try and understand it a bit better, try comparing the various equivalence (at least the main ones) to the axiom of choice:

- The axiom of choice: the product of every family of non-empty sets is non-empty.
- The well ordering principle: for every set there exists an ordering which is a well ordering.
- Zorn’s lemma: If we have a poset in which every chain is bounded then there is a maximal element.
- Hasudorff’s maximality principle: In a poset every chain is contained in a maximal chain.

There are many many many more equivalents (every vector space has a basis; in a poset every anti-chain is contained in a maximal anti-chain; Every infinite set is equipollent with its square; etc. etc.)

The plethora of equivalences only tells us that the axiom of choice can be formulated in many different ways in many different fields of mathematics. Zorn’s lemma is an order-theoretic assertion.

I wrote a proof of the equivalence here if you haven’t seen such proof before.

Let $F$ be a finite set and $\leq$ a partial order on $F$. Then there is a $\leq$-maximal element in $F$.

*Proof:* Suppose not. Then for every $x\in F$ there is $x’\in F$ with $x’>x$. So you can build a sequence $(x_1,x_2,x_3,\ldots)$ with $x_{n+1}>x_n$ for all $n$ and all terms are distinct, contradicting the finiteness of $F$.

Now this proof obviously doesn’t work for infinite sets and there are infinite partially ordered sets without a maximal element. But let’s make the assumption of Zorn’s lemma that every chain has an upper bound and see what we can do with it.

Suppose we have created the sequence $(x_1,x_2,\ldots)$ in an infinite partially ordered set $(X,\leq)$ satisfying the conditon of Zorn’s lemma but without a maximal element (we use the Axiom of choice to choose larger and larger elements). Such a sequence is consistent. But the set $\{x_1,x_2,\ldots\}$ is a chain, so there is an element larger than every element in this sequence. Now we employ heavy set theoretic machinery, the theory of ordinals to create a transfinite sequence of the form $(x_1,x_2,\ldots,x_\omega)$.Since there is no maximal element we can construct a larger transfinite sequence $(x_1,x_2,\ldots,x_\omega,x_{\omega+1})$. And we can proceed this way to get larger and larger transfinite sequences, and all terms are always distinct. Eventually, we get a transfinite sequence with more distinct terms than elements in $X$, which gives us a contradiction.

The axiom of choice is used for selecting for each element a larger one. In the finite case, this selection exists by induction alone.

This can be made into a rigorous proof. An accessible book containing this proof is for example “Introduction to Set Theory” by Jech and Hrbacek.

- For $n \in \mathbb{N}$ $\lfloor{\sqrt{n} + \sqrt{n+1}\rfloor} = \lfloor{\sqrt{4n+2}\rfloor}$
- Are all mathematicians human calculators?
- Determining quickly whether this Integer Linear Program has any solution at all
- Why do $x^{x^{x^{\dots}}}=2$ and $x^{x^{x^{\dots}}}=4$ have the same positive root $\sqrt 2$?
- Degree of the splitting field of $x^{p^2} -2$ over $\mathbb{Q}$, for prime p.
- Algorithm for constructing primes
- Evaluating $\sum_{n=1}^{\infty} \frac{1}{n^2+1}$
- Intuitive explanation of the Burnside Lemma
- Multivariable Calculus Book Reference
- Dual of a rational convex polyhedral cone
- How to solve the integral $\int \frac {(x^2 +1)}{x^4- x^2 +1} dx$
- Trying to show that $\sup \{b^p:p\in Q,\;0<p<x\} = \inf\{b^q:q\in Q,\;x<q\}$
- Euler characteristic of an $n$-sphere is $1 + (-1)^n$.
- Probability of flipping 10,000 coins and getting at least one 10 consecutive heads?
- Can we extend the definition of a homomorphism to binary relations?