18
$\begingroup$

There is a revised version, which I might substitute for this one, but I would like to keep this as evidence of priority for the "special condition".

Are there uses of the sledgehammer Zorn's Lemma that are embedded in arguments similar to the more delicate one below, showing that the thing being constructed is actually unique?

Many uses of Zorn's Lemma are equivalent to Choice because it is actually necessary to choose one of many things, eg maximal ideals or points of a frame.

[Strictly, I should have said "unique up to unique isomorphism" in the title: Constructing the algebraic closure of a field may be done with Zorn's Lemma and is unique, but there is a (typically infinite) Galois group of automorphisms. Choice is needed essentially to pick the identity of this group, so this is not an example of what I'm looking for. Unfortunately I don't have a version of this order-theoretic argument generalised to categories with filtered colimits.]

This is a revised attempt to get feedback on the following question that I asked last year. I was led to formulating this fixed point theorem instead of a variation on the Knaster-Tarski one because my setting does not have binary joins. My suspicion is that this situation must occur frequently in algebraic constructions elsewhere.

To try to settle all the misunderstandings of this question, I'm trying to get MO contributors to do the kind of semantic literature search that is not possible with computers: in your knowledge of constructions that use Zorn's Lemma, ordinals, the Knaster-Tarski theorem etc, does the surrounding argument look like anything below? Is my fixed point theorem original, or have others used it before (even implicitly)? If it is original, are there proofs in the literature that could be improved by using it?

Algebraic applications of an order-theoretic idiom of recursion

Many algebraic constructions must surely use the following observation, probably disguised as one of its proofs:

Lemma Let $s:X\to X$ be an endofunction of a poset such that

  • $X$ has a least element $\bot$;
  • $X$ has joins of directed subsets (or chains, classically),
  • $s$ is monotone: $\forall x y.x\leq y\Rightarrow sx\leq s y$;
  • $s$ is inflationary: $\forall x.x\leq s x$;
  • $\forall x y.x=s x\leq y=s y\Rightarrow x=y$.

Then

  • $X$ has a greatest element $\top$;
  • $\top$ is the unique fixed point of $s$;
  • if $\bot$ satisfies some predicate and it is preserved by $s$ and directed joins then it holds for $\top$.

Proof 1 Using the lemma for which Max Zorn denied responsibility, $X$ has at least one maximal element.

If $a$ and $b$ are maximal then there is also $c$ that is maximal with $a\geq c\leq b$. Then $a=s a$ and $b=s b$ since $s$ is inflationary. Since it's also mototone, $c\leq s c\leq s a,s b$, so $c=s c$. By the final condition, $a=c=b$.

This also explains why the "obvious" simple counterexamples aren't.

Proof 2 [added] If $X$ also has binary and therefore all joins, Tarksi's elaboration of Knaster's fixed point theorem says that there is a lattice of fixed points, but the final condition collapses this to just one.

Proof 3 Using ordinal recursion, not forgetting to cite von Neumann to justify that and Hartogs to say when to stop.

Using this argument, we could start from any basepoint, not just $\bot$, but by monotonicity and the final condition, the least fixed point over another basepoint must still be the same as the one over $\bot$.

Proof 4 Using the Bourbaki-- Witt Theorem, that the subset of $X$ generated by $\bot$, $s$ and joins of chains is itself a chain, indeed a well ordered set.

Comparing this with the previous argument, the fifth condition does a similar job as restricting to the subset generated by $\bot$, $s$ and joins of chains.

Proof 5 Using Pataraia's fixed point theorem. Just using composition, the set of monotone inflationary endofunctions of $X$ is directed and therefore has a join (greatest element) $t:X\to X$. Then $t$ is idempotent and its fixed points are also fixed by any $s$. Since $X$ is connected and the set of fixed points of $s$ is discrete, there can only be one of them, which must be the top element of $X$.

Proof of the induction principle The subset of elements satisfying the predicate has the same properties as $X$ itself, so includes $\top$.

This result has some superficial similarity to "Zorn's Lemma", but is superior to it because

  • it produces a unique result and proves properties of it; and
  • Pataraia's proof is constructive (it doesn't use the Axiom of Choice or Excluded Middle, although it is Impredicative).

I am looking for places where this result has been used, and maybe even where it has been identified as above.

The historical reasons for expecting to find it in algebra are:

  • well founded induction is sometimes (though questionably) attributed to Emmy Noether
  • Ernst Witt and Max Zorn were algebraists
  • a rambling proof of the Bourbaki-Witt theorem appears in an appendix to the 9th printing (but not the first) of Serge Lang's Algebra.

I am writing a paper about Well founded coalgebras and recursion. This is a categorical formulation of von Neumann's proof justifying recursion over ordinals, but in a generality without binary unions, which necessitated using Pataraia's theorem. However, it has taken me some months to learn how to use it and formulate the Lemma above.

The fifth condition is the less obvious part. Recall that Alfred Tarski's paper says that there is a lattice of fixed points (in the complete lattice case): this condition reduces the lattice to a single point.

It is common for binary unions to be very complicated or non-existent in algebraic constructions, which is why I believe this result may have occurred many times before.

Dito Pataraia presented his proof at the 65th PSSL in Aarhus in 1996 but never wrote it up before his death in 2011 at the age of 48. I never met him or saw the original version of his proof: I heard that it involved composition and reconstructed it myself, but I don't know what was the punchline of his argument. I am hoping Mamuka Jibladze (@მამუკაჯიბლაძე) will fill in some details.

Trying again to explain myself

My fifth axiom is the essential one, the part that seems to be original with me. It came from a lot of head-scratching: I knew that I had to use Pataraia's fixed point theorem, but it took me a long time to work out how. That is, the idiom.

My Lemma is simple, but sometimes the significance of the simplest things is the hardest to understand.

I asked this question to challenge others to find prior occurrences (to test my claim to originality, if you want to put it in competitive terms): in places where you use Zorn's lemma, ordinals or whatever, but thing is actually unique, what additional fact about your situation entails uniqueness? Is it that there cannot be two fixed points linked by the order?

Yes, I know about ordinals. However, if you make "full disclosure" of your proof using them, you will find that it is a very clumsy beast. It relies on von Neumann's recursion theorem, and Hartogs' Lemma for stabilisation. My observation is that many pure mathematicians do not know these things, even though most set theory textbooks include an (unattributed) proof of the recursion theorem. Stabilisation often goes without any proof at all.

Besides this, the traditional theory of ordinals uses excluded middle at every step. My notion of plump ordinal rectifies this. (@MikeShulman discovered it independently for his construction of the Conway numbers in Homotopy Type Theory). Hartogs' Lemma is apparently irretrievable.

Even if you don't care about excluded middle but you believe G.H. Hardy's maxim that "there is no permanent place in the world for ugly mathematics" you should want to eliminate use of the ordinals from your proofs.

I am asking this question here because I suspect that my Lemma has much wider application, but I came upon it in my (constructive categorical) work on recursion. I originally wanted a constructive account of the ordinals for my book. I built an intuitionistic theory of the ordinals to prove the fixed point theorem, but could not replicate Hartogs' Lemma. Then Pataraia came along with his far simpler proof, and I really "kicked myself", because I had known every step of it but had failed to put them in the right order.

The version of the recursion theorem in Section 7.3 of the book follows von Neumann's proof very closely, but in the setting of well founded coalgebras (which I introduced) for a functor that preserves inverse images. I then left the subject for a long time, but came back to it under provocation, because a certain person was trying to write me out of the history.

The new draft paper only requires the functor to preserve monos, and is applicable in many other categories besides $\mathbf{Set}$. However, several key steps in von Neumann's argument then fail, obliging me to find a more subtle proof using Pataraia's theorem, but not verbatim. I asked this question to try to find out whether anyone else had used my key argument.

Formulation of the Lemma

My first four conditions are familiar properties that are typically verified routinely. If the conclusion holds, the fixed point is unique, so the fifth property actually says that it is sufficient to test that two fixed points linked by the order are equal.

So the key ingredient to set up this situation is really the choice of the poset $X$, maybe as a subset of some other structure $Y$. The Bourbaki--Witt theorem takes $X$ to be the subset generated by $\bot$, $s$ and joins of chains, but I think this kind of begs the question. Section 10 of my draft paper (really an appendix) introduces a notion of "well founded element" $x$ $$ x\;\leq\; s x \quad\mbox{and}\quad \forall u:X.\ (s u \land x \;\leq\; u) \Rightarrow\ x\;\leq\; u, $$ which does the same job, but in a more elementary way. Under stronger hypotheses, $X$ has to be the subset of well founded elements of $Y$.

As I described, my setting is a categorical study of induction and recursion, but I tried to formulate this question without prejudicing the application. However, the previous remark suggests that my Lemma is necessarily about induction.

It would seem that my best hope of an application or previous occurrence of my Lemma outside my own subject is for Noetherian modules or something similar. So I would welcome an example of that.

I would like to thank @PaceNielsen for agreeing to delete his Answers that distracted from the purpose of this Question.

$\endgroup$
23
  • 3
    $\begingroup$ Without AC, the algebraic closure of a field is not in general unique up to isomorphism. In fact, it is consistent with ZF that the rational field has uncountable algebraic closures as well as countable ones. $\endgroup$ May 21, 2021 at 19:11
  • 1
    $\begingroup$ Isn't it simply incorrect historically to attribute well-founded induction to Noether? This concept is due to Cantor, significantly predating Noether. I said essentially the same in my answer to the post to which you link. $\endgroup$ May 21, 2021 at 19:14
  • 1
    $\begingroup$ @JoelDavidHamkins: I was trying to exclude algebraic closure from the discussion. If you have comments re Noether, I suggest making them on the other question. There is a historical discussion of well-foundedness in my draft paper; whilst you probably disagree with my views on set theory, I would appreciated your comments on that. $\endgroup$ May 21, 2021 at 19:18
  • 4
    $\begingroup$ Paul, I'm not sure I understand your question. If you are asking whether Zorn's lemma is ever used to prove the existence of something that is later shown to be unique (up to an iso), the answer is of course yes. If you are asking whether Zorn's lemma is ever used in situations where the axiom of choice was not necessary and we only needed well-founded recursion, then the answer is also of course yes. If you are asking about the setting of your lemma, it looks a lot like closure operator theory (but the last condition is extremely strong). $\endgroup$ May 21, 2021 at 19:37
  • 6
    $\begingroup$ I don't mean this rudely, but the new version seems more appropriate for a blog than here; what exactly is your question? (In particular, I think a lot of the text - e.g. "I am editing it (again) instead of starting a new one because I want to retain the date as a record of when I proposed the Fifth or Special Condition. [...] I would like to challenge other mathematicians, particularly those in (various kinds of) Algebra, to re-examine their (allegedly transfinite) constructions by recursion to see whether the result described above does the job more neatly" - doesn't fit the role of MO.) $\endgroup$ Feb 28, 2023 at 18:27

1 Answer 1

1
$\begingroup$

Consider any fact whatsoever characterising when a ring $R$ is local. By definition, a local ring is one which has a unique maximal ideal. Assume that $R$ is Noetherian. Presumably (referring to the notation in the question) the poset $X$ might consist of increasing sequences of non-$R$ ideals of $R$ (suitably represented) and the expression $s((I_n)_{n\in \mathbb N})$ might simply remove the first element from the sequence $(I_n)$. This seems to trip up on your first axiom though, but maybe this can be fixed.

Also, consider some of the theory surrounding local rings. I'm not sure, but consider the fact that a projective module over a local ring is necessarily free. This provides some of the intuition and motivation for studying projective modules: They're like vector bundles in that they're locally free.

Also, consider any property of a module $M$ which is true for $M$ whenever it's true for its localisations, like flatness.

$\endgroup$
1
  • $\begingroup$ There seems to be a seed of an idea here, so it would be good to see you or someone else develop it (my ring theory is too rusty). However, to be an example of the idiom of argument about which I'm asking, having a unique maximal ideal needs to be the conclusion, not the hypothesis. So the example would be something special, not generic. The sequences should also not be a hypothesis, but the result of some (globally defined, monotone) "successor" operation on ideals. $\endgroup$ Feb 5, 2023 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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