How to use Zorn's lemma | Hacker News Reader

How to use Zorn's lemma

tricki.org

35 pointsColinWright37 comments

There is a standard and well-known joke that goes:

    “The Axiom of Choice is obviously true,
     the well-ordering principle obviously
     false, and who can tell about Zorn’s
     lemma?” — Jerry Bona

It's a joke because all three statements are equivalent, and yet AC seems like it should be true, and the well-ordering principle seems too much to ask for.

The submitted page is intended to help those who don't understand what Zorn's lemma is about, or how or why one might use it.

Some math required ...

Do you know why people have the inconsistent misconceptions mocked in the joke?

At a glance, choice seems obvious because every nonempty set has an element, so taking one element from each set in a collection looks like a perfectly reasonable thing to do. For well-ordering, it asserts a property that people are typically not taught to treat the reals as having. "Everybody knows" that a set of reals doesn't necessarily have a smallest element. The "next-largest"/"next-smallest" construction is something you see a lot in (mistaken) attempts to prove 1 ≠ 0.999….

My usual experience is that people presented with well-ordering principle try to figure out how it works with the reals -- what is the order relation? It seems like asserting the existence of this structure pushes them into a more constructivist mode of thinking, whereas they don't typically feel like they need to come up with a way to construct choice functions.

Zorn's lemma deals with a setting that has somewhat more structure to it, so it doesn't really seem obvious whether it's true or not.

Why does WO seem like too much to ask for, and why are people so-so on Zorn's? I find them both just as intuitive as AC if not moreso.

I think the canonical example is that WO means there's a well ordering of the reals. We have to accept it as true, but what the hell would that look like? It's generally assumed that such a well ordering wouldn't be constructible, so it does seem like a little much to ask for.

Edit: For those curious why this is problematic, a well ordering on a set means that for any non-empty subset of the set, there's a consistent way to define the least element of the set.

An easy example is the natural numbers starting from 0 going up. The well ordering on the naturals is the usual <, and 0 is the lowest of the entire set.

This doesn't work this way for the integers. Because the integers go to negative infinity, we have to order them in a different way (but we know it's possible because the well ordering principle says so). It turns out the way to do it is to define the order on the integers this way: 0 1 -1 2 -2 3 -3 etc. Now the integers are ordered in such a way that we have a well defined least element, 0.

Now, WO says the real numbers have a well ordering as well. What would that look like? For instance, < fails us because the open interval (0,1) has no least element. The well ordering has to hold for any non-empty subset, and there are ways to create very strange and pathological subsets of R. To think that the entirety of R can be ordered in such a way like the integers is asking for a lot. But the well ordering principle states that even if we can't figure out the order, we can assume that one exists and use it in proofs. But it's weird because we're pretty much resigned to never knowing how it'd actually look.

Great explanation.

I guess the following won't work then.

0 / 0.1, 0.2, 0.3...0.9 / 0.01, 0.02, 0.03...0.09, 0.11, 0.12, 0.13...0.19, 0.21...0.99 / 0.001, 0.002, 0.003...0.009, 0.011, 0.012...

And when ever you list x, you also list -x, 1/x, and -1/x. Except for 0 of course. And you have to throw in +1 and -1 somewhere. Somehow it feels like you should cover all the reals eventually but that can't be true because that would imply there are only countable infinite many reals. It actually looks more like a convoluted version of the standard way to enumerate the rationals by visiting diagonals in order of increasing distance from the origin on a two dimensional integer lattice.

If you could provide some way to construct the WO we could ditch AC. I guess it is not happening soon...

Yeah, that's obviously just an ordering of the rationals.

I don't think it's that obvious, actually I think it's not actually an ordering of the rationals. If this were an ordering of the rationals, then it better included rationals with an infinite number of non-zero decimal digits, for example one third. But if this would include one third, then I am unable to see why it wouldn't also include square root two. Why would this be able to include repeating decimal expansions but not non-repeating ones?

You're right, I misread what you wrote. You're actually only covering a small portion of the rationals.

Either way, to order the reals, you have to include the non-computable ones, which cannot be written down in any systematic way. This also means that ordering and equality relations cannot be systematically defined either.

Can you give me a well ordering of the reals?

(Hint: No, you cannot - no matter how hard you try. Yet the WO principle says it exists).

Why wouldn't the following ordering work? {(x,y) | (|x| ≤ |y|) & ((|x| = |y| & x ≠ y) ⇒ x < 0 < y)}

With your ordering, what is the least element of the open interval (0,1)?

Ah, right. Makes sense.

What if you order the absolute values of the differences from the midpoint of the interval, where the midpoint is supremum - infimum if bounded, or zero if unbounded? Obviously this fails for closed/open sets like [a,infinity), but wouldn't it work for fully open sets?

Ultimately, the point becomes moot because we focus too much on "normal" sets. Such a definition does nothing to help us answer questions like, what is the least element of the irrationals?

I don't find the AC intuitive at all. It assumes that a choice function exists for any set of non-empty sets, including infinite ones. How can anyone have an intuition for such things? Except of course when the intuition is built upon taking finite cases to some limit. But in those cases the AC is reduced to a theorem, making it completely unnecessary.

I once had a homework assignment to attempt to construct the choice function for the set made up of all non-empty subsets of the reals. A lot of intuitive ideas come to mind and it's a good exercise to show why they don't work. You should feel weird about the axiom of choice after working through a few.

AC is equivalent to the statement: The Cartesian product of any family of nonempty sets is nonempty.

This is very intuitive.

So how does anyone form an intuition for even defining the Cartesian product of infinite sets in general, without assuming the AC in the first place?

Consider something like the Cartesian product of countably infinitely many copies of the naturals: this is nothing more than the set of all countably-infinitary tuples (n1,n2,...). It's obviously nonempty, e.g. because it contains (0,0,...). It seems intuitively obvious that similar reasoning should make any arbitrary Cartesian product of nonempty sets be empty.

That reasoning applies only to products of an arbitrary family of the same set, provided you know an element of that set. That is an exceptionally simple special case, don't you think?

Yes, that particular example is intuitive. But I don't see how a similar reasoning should apply to arbitrary infinite sets however. That's a huge intuitive leap in my opinion, and it's one that I can't follow.

Ok, you're presenting to an audience consisting of lots of tables, each with at least one person at it. You say: "Will every table please have a representative stand up."

To question the AC is to suggest that for some configuration of (sufficiently many) tables, it's impossible for the audience to fulfill your request, on account of there not existing a function f(table)=representative. This sounds absurd, because obviously each table can independently choose a representative, and it isn't like they need to coordinate with the other tables in order to fulfill your request.

"Lots of tables" is the finite case, for which the AC is a theorem. An infinite set of tables is qualitatively different. An arbitrary f(table) function will have to contain an infinite amount of information, which is beyond anything my intuition can grasp. For f(table) functions that contain finite information, the intuition is easy and the AC is reduced to a theorem.

It's only intuitive if you take cartesian products infinite families for granted. I think it's only considered intuitive because when people think "cartesian product" their model is finite families.

Do you have an example of a union without a known choice function?

Doing Reverse Mathematics, AC is waaaay to strong for me :P (We stick to weak subsystems of second order arithmetic, by and large) But this is a really nice treatment of the Lemma :D Thanks!

My favorite application of the Axiom of Choice, which Computer Scientists will appreciate:

Theorem ("Konig's Lemma"): If a tree has infinitely many nodes, and every node has only finitely many children, then the tree must have an infinite branch.

Proof: The tree's root, X1, has infinitely many descendants. Since the root has only finitely many children, some child, X2, of the root, must have infinitely many descendants. Since X2 has only finitely many children, some child, X3, of X2, must have infinitely many descendants. This process repeats forever, producing a sequence X1, X2, X3, ... which is an infinite branch through the tree.

You don't need the axiom of choice for the countable case, which is all that's required for computer science.

Why is the AC necessary for this recursive tree traversal?

The AC is necessary[1] because at each of the infinitely many steps, you have to choose which of possibly several candidates to use.

[1] As mrmyers points out, you actually only need a weaker version of AC, called Countable Choice.

Apologies for the appalling Mathmo joke, but...

* What's yellow and equivalent to the Axiom of Choice?

* Zorn's Lemon

That was the Bananach space...

> then Zorn's lemma may well be able to help you.

Sure , stuff is easier to prove if you add unrealistic axioms.

Which other ZFC axiom would be "realistic"?

Reply on news.ycombinator.com