12
$\begingroup$

Can someone kindly confirm whether the ultrafilter lemma for arbitrary (i.e., not necessarily Boolean) bounded lattices is equivalent to Zorn's lemma?

To be precise, if $\mathbf{L} = (L, \leq, \land, \lor, 0, 1)$ is a bounded lattice, then an $\mathbf{L}$-filter is a non-empty subset $F \subseteq L$ such that
(i) for any $x, y \in F$, there exists some $a \in F$ such that $a \leq x \land y$, and
(ii) if $x \in F$, $z \in L$, and $x \leq z$, then $z \in F$.

A generalized version of the ultrafilter lemma would be that every proper $\mathbf{L}$-filter can be extended to an $\mathbf{L}$-ultrafilter. When $\mathbf{L}$ is a Boolean algebra (such as the power set of a non-empty set equipped with the standard set-theoretic operations), we have the well-known result that the ultrafilter lemma is equivalent to the Boolean prime ideal theorem, the compactness theorem for PL, etc., and that these are strictly weaker than the axiom of choice. But when $\mathbf{L}$ is an arbitrary lattice, I suppose that Krull's theorem and hence Zorn's lemma can be derived from the ultrafilter lemma. Am I mistaken here?

$\endgroup$
8
  • 3
    $\begingroup$ You have defined $L$-filter, but not $L$-ultrafilter. Is an $L$-ultrafilter just a maximal $L$-filter? $\endgroup$ Dec 26, 2022 at 18:14
  • 2
    $\begingroup$ @AlexKruckman Yes, an $L$-ultrafilter would in this case just be a proper $L$-filter that is not properly contained in a proper $L$-filter. $\endgroup$
    – Menander I
    Dec 26, 2022 at 18:19
  • 3
    $\begingroup$ Maybe the tag (axiom-of-choice) would be suitable here? (If I understand the question correctly, it is a question whether a certain statement is equivalent to AC.) $\endgroup$ Dec 27, 2022 at 11:58
  • 3
    $\begingroup$ Note that you need to restrict to bounded lattices. Your notation $(L, \leq, \wedge, \vee)$ suggests that you are not making this assumption. Otherwise, it's not true that each filter extends to a maximal filter. For example, the real line with the standard order is a lattice which has no maximal filter at all. $\endgroup$ Dec 27, 2022 at 15:36
  • $\begingroup$ @AdamPřenosil Yes, you are right. Thank you for pointing out this counterexample. In the standard context where a filter is defined as a subset of some power set, the proof that AC => UL using Zorn's lemma tends to invoke the result that a filter $F$ is proper if and only if $\emptyset \notin F$. When I was considering the more general case of an arbitrary lattice, I noticed that the analogue of this argument doesn't apply if the lattice does not have a smallest element. $\endgroup$
    – Menander I
    Dec 27, 2022 at 19:37

2 Answers 2

12
$\begingroup$

It is equivalent to AC.

Consider any collection $A$ of nonempty sets, and let $\newcommand\P{\mathbb{P}}\P$ be the set of partial choice functions, so that $p\in\P$ if and only if $p$ is a partial function on $A$ for which $p(a)\in a$ for every $a\in\text{dom}(p)$. We place the forcing order on $\P$, so that $q\leq p$ if $q$ extends $p$ to a larger domain, or equivalently, $p=q\upharpoonright\text{dom}(p)$. In particular, being lower in the order means having more information, larger domain, and so on. The empty function is at the top, the largest element of $\P$. Let us also add an object $\bot$ to $\P$ below all others.

The motivating idea is that $\P$ is the forcing notion that adds a choice function for $A$, augmented with $\bot$.

This is a nontrivial bounded lattice, because any two partial functions $p$, $q$ have a least upper bound $p\vee q$, which is their common part as functions, and a greatest lower bound, which is their union $p\cup q$ if they are compatible as functions, and otherwise $\bot$.

I assume that ultrafilters for you cannot be the whole lattice (since otherwise the ultrafilter assertion would become trivialized). Every proper filter in $\P$, I claim, gives rise to a unifying limit partial choice function, the union of the all the functions in the filter, since the filter cannot contain $\bot$ and so all elements of it must be compatible as functions. Furthermore, the limit function arising in this way from an ultrafilter must be totally defined on $A$, since otherwise we could extend it by defining the choice function on one more set $a\in A$ in the collection.

So from an ultrafilter in $\P$ we get a choice function on $A$.

Let me add a note about distributivity, since the lattice $\P$ is not generally a distributive lattice, one for which $p\vee(q\wedge r)=(p\vee q)\wedge (p\vee r)$. The reason is that it could be that $q$ and $r$ are incompatible, which would make $q\wedge r=\bot$ and consequently the LHS would be $p$, but if $q$ and $r$ differ from $p$ on some point $a\in\text{dom}(p)$, then the RHS will be strictly above $p$, lacking that point $a$ in its domain.

So a question remains, I suppose, about the strength of the ultrafilter lemma for distributive lattices. [Update Keith Kearnes posted an answer with references to Herrlich & Klimosky, showing that it is also equivalent to AC with nontrivial bounded distributive lattices.]

$\endgroup$
15
  • 4
    $\begingroup$ This is an excellent answer. Thank you very much! $\endgroup$
    – Menander I
    Dec 26, 2022 at 18:33
  • 3
    $\begingroup$ I'd expect the ultrafilter lemma for distributive lattices to follow from the boolean prime ideal theorem. The idea is that we can get an ultrafilter on $L$ by using a suitable ultrafilter on the set of finite subsets of $L$ to "average" ultrafilters on the finitely generated sublattices of $L$. This should work because finitely generated distributive lattices are finite (unlike finitely generated lattices in general). Unfortunately I don't have time now to check details. $\endgroup$ Dec 26, 2022 at 21:23
  • 3
    $\begingroup$ I think that Goldstern's alphabet convention should become standard when discussing forcing. $\endgroup$
    – Asaf Karagila
    Dec 26, 2022 at 23:13
  • 2
    $\begingroup$ What is the alphabet convention? Is it something about which letters we should use to denote conditions? $\endgroup$ Dec 26, 2022 at 23:17
  • 2
    $\begingroup$ The ultrafilter lemma for distributive lattices is equivalent to the ultrafilter lemma for Boolean algebras, as every nontrivial distributive lattice admits a homomorphism into a nontrivial Boolean algebra (so a homomorphism to the 2-element lattice from the latter yields one from the former. If we also want the ultrafilter to extend a given proper filter, start by quotienting the distributive lattice suitably). Indeed, it is relatively straightforward to see syntactically that the homomorphism from a lattice to the free Boolean algebra upon it is injective iff the lattice is distributive. $\endgroup$ Dec 27, 2022 at 8:11
9
$\begingroup$

Regarding the question about the strength of the ultrafilter lemma for distributive lattices, let me cite the relevant theorem from Herrlich's book:

Theorem 4.32. Equivalent are:

  1. Every lattice has a maximal filter.
  2. Every complete lattice has a maximal filter.
  3. Every distributive lattice has a maximal filter.
  4. Every closed lattice has a maximal filter.
  5. AC.

In this theorem a closed lattice is a lattice that is isomorphic to the lattice of closed subsets of a nonempty topological space (Definition 4.28).

Herrlich, Horst
Axiom of choice
Lecture Notes in Mathematics, 1876.
Springer-Verlag, Berlin, 2006.

Herrlich credits the equivalence of Item 3 and Item 5 to

G. Klimowsky.
El Theorema de Zorn y la existencia de filtros e ideales maximales en los reticulados distributivos.
Rev. Union Mat. Argentina, 18:160-164, 1958.

Where Herrlich writes in terms of AC and in terms of the existence of a maximal filter, Klimowsky writes that Zorn's Lemma is equivalent to 'En todo reticulado distributivo con primer elemento, todo filtro está contenido en un ultrafiltro'. (In every distributive lattice with first element, every filter is contained in an ultrafilter.)

$\endgroup$
3
  • 2
    $\begingroup$ Thanks. I was too lazy to open the book and write an answer, and when Joel posted his answer to the question at hand, I figured it wasn't as relevant. But I'm glad that someone took the time. $\endgroup$
    – Asaf Karagila
    Dec 27, 2022 at 12:00
  • 3
    $\begingroup$ In light of Adam's comment, shouldn't the theorem be about bounded lattices? $\endgroup$ Dec 27, 2022 at 15:39
  • 5
    $\begingroup$ @JoelDavidHamkins On page 57 in the edition I have here: "For convenience we adopt the following slightly restricted definition of lattices. (By standard terminology our lattices would have to be called non–trivial bounded lattices.) Definition 4.27. A lattice is a partially ordered set $L$ in which each finite subset $F$ has an infimum, $\inf F$, and a supremum, $\sup F$, (in particular L has a smallest element, $0=\sup\emptyset$, and a largest element, $1=\inf\emptyset$) and such that $0\ne1$." (I suppose it should be mentioned.) $\endgroup$ Dec 27, 2022 at 16:12

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.