2
$\begingroup$

Is there a way to deduce Zorn's lemma from Zermelo theorem (that any set may be well ordered), which is essentially shorter then deduction of Zorn's lemma from the usual form of Axiom of Choice?

$\endgroup$
3
  • 1
    $\begingroup$ Well-orders for themselves are relatively useless. The main strength they have is transfinite recursion. And you want to take that away from them... $\endgroup$
    – Asaf Karagila
    Feb 21, 2015 at 21:21
  • 3
    $\begingroup$ The usual proof using transfinite recursion takes like three lines. How do you expect it to get any shorter, and how do you define “essentially shorter” anyway? $\endgroup$ Feb 21, 2015 at 21:32
  • $\begingroup$ I would like to save it, not because of question itself, but rather due to the interesting answer by Noah. $\endgroup$ Feb 22, 2015 at 11:42

2 Answers 2

1
$\begingroup$

I assume the "usual proof" goes by defining the obvious chain of elements $p_\eta$ by induction on $\eta$, and then arguing that that constitutes a chain with no upper bound.

I'm not sure if this counts, but: let $<$ be a well-ordering of the set of chains through $\mathbb{P}$. Now we can define a sequence of chains $C_\eta$ as: $C_\eta$ is the $<$-least chain such that $$\forall \beta<\eta, C_\beta\subsetneq C_\eta.$$ If we assume that $\mathbb{P}$ satisfies the hypothesis of Zorn's lemma but has no maximal elements - equivalently, that every chain $C$ through $\mathbb{P}$ has an upper bound not contained in $C$ - then $C_\eta$ exists for every ordinal $\eta$, which is a clear contradiction once we let $\eta$ exceed the cardinality of the set of chains.

Of course this still hinges on a transfinite induction/recursion argument - as Asaf comments, transfinite recursion is basically the only technique we have for utilizing well-orderings, so I don't think there's going to be a proof which avoids it. But notice that in this proof these arguments are pretty easy:

  • The recursion defining $C_\eta$ is very short.

  • To argue that $C_\eta$ always exists, only the limit case is at all interesting, and even then we only need the fact that $\bigcup_{\beta<\eta} C_\beta$ is a chain.

Additionally, to me at least this seems more direct than the usual one - in particular, we never need dirty our hands with individual elements of $\mathbb{P}$.

I'm not sure this satisfies the OP, though.


Having just written this, now let me argue that it stinks, at least in one respect dear to my heart:

The usual proof uses a well-ordering of $\mathbb{P}$, whereas this one uses a well-ordering of $Chain(\mathbb{P})$, the set of chains through $\mathbb{P}$. Clearly a well-ordering of the latter yields a well-ordering of the former (even "effectively," although some care must be taken to pin down what "effectively" means here); meanwhile it is consistent with $ZF$ that $\mathbb{P}$ is well-orderable but $Chain(\mathbb{P})$ is not (e.g., take $\mathbb{P}$ to be the usual ordering on $\omega$).

So, if we are interested in the inherent logical strength of Zorn's lemma, and not just its truth, then this proof is extremely bad.

This interest in logical strength, and in proofs which are "efficient" in terms not of length but of axioms used, is the driving force behind reverse mathematics, which has been investigated extensively over the last few decades. Unfortunately for us, reverse mathematics lives in the realm of second-order arithmetic, that is, it focuses only on natural numbers and sets of natural numbers. This is really the wrong setting for Zorn's lemma. So, even though we can give an intuitive reason for the proof above being "bad" from the point of view of reverse math, it's not clear that we can make this precise.

Fortunately, we're getting there! Over the last few years, interest in higher-order reverse mathematics has developed: for example, see http://www.brics.dk/RS/00/49/BRICS-RS-00-49.pdf which introduced HORM, http://arxiv.org/abs/1502.03618 on HORM and nonstandard analysis, and http://arxiv.org/abs/1109.3902 for a study of ultrafilters in HORM. This provides a system and base theory over which we can reasonably study actual choice principles. So far this has not been investigated very much; however, let me mention one result you may find interesting.

Consider the following two choice principles: (1) "The reals are well-ordered" and (2) "Every real-indexed family of nonempty sets of reals has a choice function." The former clearly implies the latter - just pick the least element out of each set - but this proof requires a nontrivial amount of comprehension (specifically, ($\Pi^1_1$ with type-2 parameters)-comprehension for type-2 functionals). From the effective point of view, the situation is far from clear. It turns out that this implication is false: over any reasonable$^1$ (from the point of view of effective mathematics) base theory, (1) does not imply (2), in fact (1) and (2) are incomparable. This proof isn't really written up yet, but a typo-y version can be found in my paper http://arxiv.org/pdf/1310.5792v1.pdf (page 16).

The natural question to ask at this point is: "Is there a reasonable base theory for higher-order reverse mathematics which proves the implication 'well-ordering implies Zorn' but not 'well-ordering implies choice'?" I strongly suspect the answer is "no."


$^1$Okay yes this is provocative nonsense, but one can isolate hypotheses on the base system which are fairly convincing from the point of view of computability theory and which imply the separation mentioned.

$\endgroup$
3
  • 1
    $\begingroup$ This is just the usual argument, but applied indirectly to the poset of chains in $\mathbb P$ instead of $\mathbb P$ itself. $\endgroup$ Feb 21, 2015 at 22:23
  • $\begingroup$ Yes, but it is shorter, which is what was asked for. Like I said though, I'm not sure it counts. $\endgroup$ Feb 21, 2015 at 22:26
  • $\begingroup$ "Reverse mathematics" is sometimes (often?) defined as the project of determining which axioms are needed to prove theorems of ordinary mathematics. If one accepts this definition (and doesn't insist on working in second-order arithmetic), then much of the work on weak forms of the axiom of choice is reverse mathematics (with ZF or a variant allowing atoms as the base theory). (I realize this isn't relevant to the present question, which isn't about weak forms, but it seems relevant to part of Noah's answer.) $\endgroup$ Feb 22, 2015 at 1:20
-5
$\begingroup$

Of course. Well ordering theorem easily implies the existence of a choice set and then you can run Zermelo's argument.

$\endgroup$
9
  • 4
    $\begingroup$ You didn't read the question carefully, which explicitly says shorter than the proof you just named. $\endgroup$
    – Todd Trimble
    Feb 21, 2015 at 21:07
  • 2
    $\begingroup$ Once you have a well ordering of your poset the construction of a maximal element is a simple transfinite construction. I don't know what more is being asked for here. $\endgroup$
    – Sheman
    Feb 21, 2015 at 21:11
  • 2
    $\begingroup$ A well ordering allows you to choose a witness to the non maximality of the current member of the poset. At limit stages you take an upper bound using the assumption of Zorn's lemma. Please show some politeness. Thanks. $\endgroup$
    – Sheman
    Feb 21, 2015 at 21:25
  • 3
    $\begingroup$ Sheman, why don't you rewrite your answer, using the argument you just gave in a comment? (BTW, I didn't see that Fedor was being impolite; I believe he was asking an innocent question.) $\endgroup$
    – Todd Trimble
    Feb 21, 2015 at 21:32
  • 4
    $\begingroup$ Wait, if there's nothing to answer here, why did you answer it? $\endgroup$ Feb 21, 2015 at 21:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.