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
Accepted

Characterizing $\mathbf{R}$ as an ordered group

The linearly ordered group $(\mathbb{Z},+,\le)$ is a counterexample, but that is probably not what the OP had in mind. To give a detailed description of the situation, let us use the following ...
Jochen Glueck's user avatar
26 votes
Accepted

Why do we need "canonical" well orders?

This isn't about just any choice for a 'canonical' well-order, but the von Neumann ordinals in particular have nice properties that you don't get just from well-orders. They admit a logically simple ...
Kameryn Williams's user avatar
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
22 votes
Accepted

Has the exponentiation of ordinals a nice geometric model?

Ordinal exponentiation is a special case of linear order exponentiation. For any linear order $L$, element $a\in L$, and ordinal $\beta$ we can define the $\beta$th power of $L$ at $a$, which I'll ...
Noah Schweber's user avatar
20 votes
Accepted

Representation theorem for modular lattices?

There are lots of relations satisfied in lattices of submodules besides the ones implied by modularity. For example, there is the Desarguesian identity mentioned here (which holds in any lattice of ...
Todd Trimble's user avatar
  • 52.4k
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

Does there exist an ordering-functor?

Conceptual answer. There can be no such functor. Let $C$ be any concrete category of finite sets and mappings such that the only automorphisms in $C$ are trivial. I claim there is no underlying set ...
Benjamin Steinberg'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
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
18 votes

Is the theory of a partial order bi-interpretable with the theory of a pre-order?

They are not one dimensional bi-interpretable. The pre-order on $\{a,b,c,d\}$ given by $a\equiv b$ and $c\equiv d$ (and $a, b$ not related to $c, d$) is homogeneous in the sense that for any ...
Rodrigo Freire'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

Class of lattices that excludes $M_3$?

This is a (slightly edited) copy of the answer I posted on math.SE to the question What do we call a lattice that does not have a sublattice the shape of the diamond $M_3$?: Let $\mathbf K$ be the ...
bof's user avatar
  • 11.9k
14 votes

Representation theorem for modular lattices?

The lattice of submodules of a module satisfies a stronger identity, namely the Arguesian law: $$ (x_0\vee y_0)\wedge (x_1\vee y_1)\wedge (x_2\vee y_2)\leq ((z\vee x_1)\wedge x_0) \vee ((z\vee y_1)\...
Pedro Sánchez Terraf's user avatar
14 votes
Accepted

Complete Boolean algebras of subsets of $\mathbb N$

The answer is negative. Let $A$ be the completion of the denumerable atomless BA $B$. Then $A$ is complete and atomless. $A$ can be isomorphically embedded in $\mathrm{Pow}(\omega)$. In fact, $B$ can ...
Don Monk's user avatar
  • 156
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
12 votes

Associative mean

Let $(L, <)$ be any linear order. Fix an arbitrary well-order $\sqsubset$ on $L$. For any $a\le b$ define $m(a,b)=m(b,a):= $ the $\sqsubset$-least element in the interval $[a,b]$. Then $m$ is ...
Goldstern's user avatar
  • 13.9k
12 votes
Accepted

Associative mean

Yes there are more such functions, even if we require them to be symmetric, monotonic and continuous. For example pick any $C$ and take $m_C(a,b)=\min(a,b)$ if $a,b\ge C$, $m_C(a,b)=\max(a,b)$ if $a,...
Yaakov Baruch's user avatar
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.9k
11 votes

Whether a total order set of size $n$ has the fewest endomorphisms among posets of size $n$

No. The zig-zag poset on 4 elements has only 31 endomorphism, whereas the total order has 35 endomorphisms. I added the number of automorphisms and endomorphisms of a poset to http://www.findstat.org,...
Martin Rubey's user avatar
  • 5,563
11 votes
Accepted

Are free ultrafilters as posets product-irreducible?

No. Every nonprincipal ultrafilter $U$, considered as a partial under $\subseteq$, is a nontrivial product order. To see this, suppose that $U$ is a nonprincipal ultrafilter on $\kappa$. Partition $\...
Joel David Hamkins's user avatar
11 votes

On Applications of Forcing in Domain Theory

It may not be well known outside domain theory that there are several different groups who work in domain theory for different reasons. People interested in domains as modeling partial information in ...
Carl Mummert's user avatar
  • 9,603

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