58 votes
Accepted

Zorn's lemma: old friend or historical relic?

I agree with almost everything in your post. But still, I believe I know why people use Zorn's lemma. My answer. Zorn's lemma encapsulates succinctly many of the consequences of AC via transfinite ...
Joel David Hamkins's user avatar
41 votes

Zorn's lemma: old friend or historical relic?

I agree with the existing answers, but I personally like Zorn's lemma both pedagogically and mathematically for an additional reason: the "poset of partial solutions" that it introduces is a ...
Noah Schweber's user avatar
37 votes
Accepted

What is the cofinality of the co-infinite subsets of ${\bf N}$?

Every such cofinal family $\mathcal{A}'$ must have size continuum. The reason is that there is an almost disjoint family $\mathcal{D}$ of size continuum, a family of infinite co-infinite sets $A\...
Joel David Hamkins's user avatar
36 votes
Accepted

Expected height of a poset?

In Asymptotic Enumeration of Partial Orders on a Finite Set (1975), Kleitman and Rothschild showed that almost all partial orders on an $n$-element set have a simple description: they have three "...
Jacob Manaker's user avatar
29 votes

Applications of Zorn’s lemma that aren’t chain-complete/directed-complete?

On the one hand, one might expect that there can be no fully satisfactory example of the phenomenon, in light of the observations mentioned in the comments, namely, that every partial order fulfilling ...
Joel David Hamkins's user avatar
27 votes

Does there exist a full and faithful embedding of $\mathsf{Poset}$ in $\mathsf{Set}$?

The poset $\{0,1\}$ with $0<1$ has three endomorphisms. Since there is no set with exactly three endomorphisms, there cannot be a fully faithful embedding of posets into sets.
Julian Rosen's user avatar
  • 8,941
24 votes

Open questions about posets

The 1/3-2/3 conjecture is probably considered one of the most significant open problems about finite posets; see the Wikipedia page: https://en.wikipedia.org/wiki/1/3%E2%80%932/3_conjecture.
22 votes

When does a graph underlie the Hasse diagram of a poset?

This problem was proved to be NP-complete in https://link.springer.com/article/10.1007/BF00340774, but a mistake was discovered, and later corrected, for a simple proof and brief history, see https://...
domotorp's user avatar
  • 18.4k
20 votes
Accepted

Listing all posets on 9 points?

See the "Partially-ordered sets (posets)" section here, where Brendan McKay has provided the posets up to 10 points.
RobPratt's user avatar
  • 5,169
20 votes

Listing all posets on 9 points?

Using posets(9) from Finite posets in SageMath will give you an iterator of all posets (up to isomorphism) on 9 elements. So, this isn't a list you can download ...
John Machacek's user avatar
19 votes
Accepted

How is this fixed point theorem related to the axiom of choice?

I'll deduce Zorn's Lemma from your fixed-point theorem. Suppose $P$ is a poset violating Zorn's Lemma; so all chains in $P$ have upper bounds, but there's no maximal element. Consider the poset $Q=P\...
Andreas Blass's user avatar
19 votes
Accepted

Suprema of directed sets

Yes, a poset that has suprema of all chains also has suprema of all directed sets. This is known, and I vaguely recall seeing it attributed to Solovay. The proof consists of showing, by induction on ...
Andreas Blass's user avatar
19 votes

Zorn's lemma: old friend or historical relic?

Your choice (ha) to prove the existence of a basis by using a well-ordering in place of Zorn’s Lemma turns things around historically: the first proof of the existence of algebraic bases (using only ...
KConrad's user avatar
  • 49.6k
18 votes
Accepted

Are these two quotients of $\omega^\omega$ isomorphic?

Very nice question! They are not isomorphic. What I claim is that when we take the quotient with respect to density, there is a countably infinite antichain above $0$ having a minimal upper bound, ...
Joel David Hamkins's user avatar
18 votes
Accepted

Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$

It may be clarifying to work with equivalence relations $E$ on $X$ rather than partitions on $X$. The two are in natural bijection, with $E$ inducing a partitioning quotient map $q: X \to X/E$, and $X/...
Todd Trimble's user avatar
  • 52.4k
18 votes

Open questions about posets

Here's a problem that I believe has little chance of being resolved, and it's also not so clear to me what the motivation behind the problem is, but it involves some very pretty algebraic ...
18 votes

What is the minimum size of a partial order containing all partial orders of size 5?

(Edited several times from earlier partial answer, which gave $f(5) \ge 11$.) We have exact results $f(5) = 11$ and $f(6)=16$, and bounds $16 \le f(7) \le 25$. 1. Proving $f(5)=11$ A short proof shows ...
Jukka Kohonen's user avatar
17 votes
Accepted

Non-homeomorphic connected $T_2$-spaces with isomorphic topology poset

There aren't any. Hausdorff spaces are sober spaces. If $X, Y$ are sober, then every frame map $\mathcal{O}(Y) \to \mathcal{O}(X)$, i.e., every poset map between their topologies that preserves finite ...
Todd Trimble's user avatar
  • 52.4k
17 votes

Are arbitrary nonempty intersections of principal filters principal?

Let $L$ be the lattice of finite and cofinite subsets of $\mathbb N$. Let $\mathcal F_n$ be the principal filter of elements of $L$ that contain the element $n$ (i.e., $\mathcal F_n$ contains the ...
Keith Kearnes's user avatar
17 votes
Accepted

Are the Boolean algebras ${\cal P}(\omega)/(\text{fin})$ and ${\cal P}(\omega)/(\text{thin})$ isomorphic?

The answer is no. In the Boolean algebra $P(\omega)/\text{Fin}$ every strictly descending sequence $A_0>A_1>A_2>\cdots$ has a nonzero lower bound, by the famous construction of Hausdorff. ...
Joel David Hamkins's user avatar
15 votes
Accepted

Matrices of combinatorial sequences that are inverse in two ways

Following up on David's nice answer, there is a different parametrization that makes the pattern much more obvious. Namely, let $s_1,s_2,\dots$ be arbitrary, then you can write $$A=\Big(h_{i-j}(s_1,...
Gjergji Zaimi's user avatar
14 votes
Accepted

Group structure for distributive lattices

No: If it's natural, it should be invariant under the automorphism group of the original lattice. let $X$ be the free distributive lattice on 2 generators $x,y$: it has 6 elements, $$0\quad<\quad x\...
YCor's user avatar
  • 60.1k
13 votes
Accepted

What is known about ideal and divisibility lattices of GCD domains and their generalizations?

Given a ring $R$, let us denote by $L(R)$ the lattice of two-sided ideals of $R$ for which the infimum and supremum are given by $\inf(I, J) = I \cap J$ and $\sup(I, J) = I + J$. Such lattices are ...
Luc Guyot's user avatar
  • 7,423
13 votes

Are arbitrary nonempty intersections of principal filters principal?

There are two good answers already; but I’ll add a little motivation for how one might find the way to them. If $L$ is complete, then as you say, it’s easy to see that any intersection of principal ...
Peter LeFanu Lumsdaine's user avatar
13 votes

Zorn's lemma: old friend or historical relic?

The answers and comments so far contain a lot of abstract and philosophical discussion. Personally I think that, when comparing the advantages and disadvantages of two approaches, concrete examples ...
Jochen Glueck's user avatar
13 votes

Homotopy type of the geometric realization of a poset

Once more, with feeling. Thanks to comments from Tyler Lawson and Neil Strickland. Let me use $B_n$ for the finite Boolean lattice of subsets of $[n] := \{1,2,\ldots,n\}$ (your $\mathcal{P}(S)$), and ...
Sam Hopkins's user avatar
  • 22.8k
13 votes
Accepted

If $P\times{\bf2}$ order-embeds in $Q\times{\bf2}$, does the poset $P$ embed in the poset $Q$?

The two-element anti-chain $\{0,0'\}$ does not embed into ${\bf 4} = \{0,1,2,3\}$, but $\{0,0'\} \times {\bf 2}$ embeds into ${\bf 4} \times {\bf 2}$ using the embedding \begin{align*} (0,0) &\...
Terry Tao's user avatar
  • 109k
12 votes
Accepted

A meet-semilattice with top element that is not a lattice?

It is well-known that a finite meet-semi-lattice with a maximum element is a lattice. The reason is that we can define $a \vee b := \wedge \{c\colon \textrm{$c$ is an upper bound for $a,b$}\}$, where ...
Sam Hopkins's user avatar
  • 22.8k
12 votes
Accepted

Smallest ordinal $\mu$ not embeddable in ${\cal P}(\omega)$

This is just $\omega_1$. The naive argument ("pick the least new thing") that no uncountable linear order embeds into $\mathcal{P}(\omega)$ actually establishes that no uncountable well-...
Noah Schweber's user avatar
12 votes
Accepted

Reference request: number of antichains of a partially ordered set

Let me convert my comments into an answer. Your poset $P=P_n$ can also be written as $P=J([2]\times[n-1])$, the lattice of order ideals of the product of a $2$-element chain and an $(n-1)$-element ...
Sam Hopkins's user avatar
  • 22.8k

Only top scored, non community-wiki answers of a minimum length are eligible