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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#### Related Tags

order-theory × 647posets × 165

set-theory × 142

lattice-theory × 125

co.combinatorics × 109

gn.general-topology × 84

lo.logic × 80

reference-request × 66

linear-orders × 40

ct.category-theory × 39

graph-theory × 35

gr.group-theory × 34

ordered-groups × 29

model-theory × 25

universal-algebra × 22

boolean-algebras × 22

terminology × 18

semigroups-and-monoids × 18

infinite-combinatorics × 17

ordinal-numbers × 17

lattices × 16

measure-theory × 15

ra.rings-and-algebras × 14

pr.probability × 12

ac.commutative-algebra × 12