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 ...

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 ...

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\...

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 "...

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 ...

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.

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.

Community wiki

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://...

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.

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 ...

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\...

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 ...

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 ...

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, ...

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/...

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 ...

Community wiki

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 ...

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 ...

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 ...

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. ...

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,...

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\...

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 ...

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 ...

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 ...

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 ...

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) &\...

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 ...

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-...

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 ...

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

#### Related Tags

posets × 403order-theory × 165

co.combinatorics × 151

lattice-theory × 78

set-theory × 70

reference-request × 35

gn.general-topology × 33

lo.logic × 26

ct.category-theory × 21

graph-theory × 19

gr.group-theory × 13

forcing × 13

rt.representation-theory × 12

infinite-combinatorics × 12

linear-algebra × 11

terminology × 11

at.algebraic-topology × 10

enumerative-combinatorics × 10

boolean-algebras × 9

ra.rings-and-algebras × 8

lattices × 8

algorithms × 7

algebraic-combinatorics × 7

matrices × 6

discrete-geometry × 6