# Questions tagged [order-theory]

The order-theory tag has no usage guidance.

622
questions

5
votes

2
answers

322
views

### Generalization of the concept of a measure

Consider the following generalization of the concept of a measure:
Let $L = (X, \lor, \land, \bot)$ be a semi-bounded lattice.
Let $M = (Y, \bullet, e)$ be a commutative monoid.
An $(L, M)$-measure is ...

4
votes

1
answer

157
views

### Find an order-embedding of $S_3\times{\bf2}\times{\bf2}$ into ${\mathbb Z}^4$

A function $f:P\to Q$ from a poset $(P,\le_P)$ to a poset $(Q,\le_Q)$ is an order-embedding if, for all $p,p'\in P$, $p\le_P p'$ if and only if $f(p)\le_Q f(p')$.
We partially order the Cartesian ...

7
votes

1
answer

425
views

### Progress on determining which partial orders embed into the rationals

The following result is relatively well-known: (for example in Math StackExchange answer #37161)
For every countable linear order $(R,\prec)$, there is an $X\subseteq\mathbb Q$ such that $(R,\prec)$ ...

10
votes

4
answers

340
views

### Universal poset for cardinals $\kappa \geq \aleph_0$

Given a cardinal $\kappa\geq \aleph_0$, is there a poset $(P,\leq)$ with $|P| = \kappa$ such that every poset of cardinality $\kappa$ can be order-embedded into $(P,\leq)$?

1
vote

1
answer

86
views

### Choosing a net of projections from a given collection

Let $\mathcal M$ be a von Neumann algebra. Let $S$ be a nonempty set. Consider $\Omega$ to be the collection of all finite subsets of $S$. Suppose for all $\omega\in\Omega$ we have $I_\omega$ a ...

6
votes

2
answers

193
views

### "Minimal" connected matroids

I'm interested in connected matroids $M$ on the ground set $[n]$ for which there is no connected matroid on $[n]$ of the same rank but with a strictly smaller set of bases (by inclusion). Equivalently,...

5
votes

0
answers

177
views

### Is this "trimming" of a supersolvable semimodular lattice known?

Let $L$ be a finite (upper) semimodular lattice. Recall that this means $L$ is graded and its rank function $\rho\colon L \to \mathbb{N}$ satisfies
$$ \rho(x) + \rho(y) \geq \rho(x\vee y)+\rho(x \...

2
votes

1
answer

102
views

### Decomposition of weak* convergent nets into positive weak* convergent nets

Let $F$ be an order unit Banach space with order unit $e$ and topological dual space $F^*$ ordered by the dual cone. Let $E\subset F^*$ be a closed subspace that separates points of $F$ and such that ...

13
votes

1
answer

235
views

### Can any poset of cardinality $\leq 2^{\aleph_0}$ be embedded in ${\cal P}(\omega)/(\text{fin})$?

We endow ${\cal P}(\omega)$ with an equivalence relation by saying that $A\simeq_{\text{fin}} B$ iff the symmetric difference $A\Delta B$ is finite. The resulting set of equivalence classes is denoted ...

3
votes

2
answers

191
views

### Posets such that the collection of principal down-sets does not have property ${\bf B}$

We say that a hypergraph $H=(V,E)$ has property ${\bf B}$ if there is $S\subseteq V$ such that for all $e\in E$ with $|e|>1$ we have $S\cap e \neq \emptyset \neq e \setminus S$.
Let $(P,\leq)$ be a ...

2
votes

2
answers

249
views

### Topological characterisations of properties of posets

Finite connected partially ordered sets are in bijective correspondence to connected finite topological spaces that satisfy T_0, see for example the Wikipedia article Finite topological space. Here ...

4
votes

1
answer

249
views

### Is every finite poset a subset of a finite complemented distributive lattice?

Let $(X,\succeq)$ be a poset. I have the following two questions:
Is it true that there exists a finite complemented distributive lattice (a Boolean lattice) $(S, \succeq^*)$ such that $X\subseteq S$ ...

0
votes

0
answers

29
views

### When can we separate two pairs in ${\mathbb H}_n$, although it is not a lattice?

Recall that a lattice is a partially ordered set $E$ for which any pair $a,b\in E$ admits a least upper bound and a greatest lower bound. Remark that given four elements $a_i,b_j$ ($j=1,2$), in order ...

5
votes

0
answers

101
views

### Which monomials are "leadable"?

Question: Let $k$ be a field, let $f \in k[t_1,\ldots,t_N]$ be a nonzero polynomial. Which monomials
$m_a = t_1^{a_1} \cdots t_N^{a_n}$ appearing in $f$ are leadable in the sense that they are the ...

2
votes

0
answers

82
views

### Can this order relation, defined in terms of all topological spaces, be defined in terms of the reals alone?

Let $K$ be the operator monoid under composition of Kuratowski's $14$ set operators generated by topological closure $k$ and complement $c.$ Kuratowski's 1922 paper gives the poset diagram of the ...

3
votes

0
answers

111
views

### A class of Kripke frames which preserves validity

The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $1\leq s\leq n-2$, the frame $\mathcal{C}_n(s)$ denotes the frame which is ...

1
vote

0
answers

75
views

### What computable pseudo-ordinals are there with initial segment $\omega_1^{CK}(1+\eta+1)$?

The notion of a “computable pseudo-ordinal”, i.e. a computable linear order with no hyperarithmetical descending chains, is an old one going back to Stephen Kleene. Joe Harrison wrote the definitive ...

1
vote

1
answer

182
views

### does this relation associated with a poset have a name?

Given a partial order $P$ on a set $S$ does the set of ordered pairs $(x,y)$ in $S\times S\setminus P$ such that $P\cup\{(x,y)\}$ is a partial order have a name? (If so then it would apply to all ...

3
votes

0
answers

62
views

### What are all the order types of maximal chains of $\Delta^0_2$ sets?

A set of natural numbers is $\Delta^0_2$ if it’s computable from the halting set. Consider the quasi-order/pre-order of all $\Delta_0^2$ sets ordered by $m$-reduction, or equivalently consider the ...

2
votes

0
answers

65
views

### Ordered vector space that can be embedded into its bidual

We say that an ordered vector space $(V, \ge)$ (over $\mathbb{R}$) is "bidual embeddable" (I made up this name, not sure whether this concept already exists) if for every $x \in V$, if $x$ ...

10
votes

0
answers

235
views

### Let $X$ be a finite set of $n$ ($>1$) elements and $\tau$ be a topology on $X$ having exactly $m$ elements. Can we give any description of $m$?

Let $X$ be a finite set of $n$ ($>1$) elements and $\tau$ be a topology on $X$ having exactly $m$ elements.
Can we give any description of $m$ as it relates to $n$?
Obviously $2\le m\le 2^n$ and ...

2
votes

0
answers

139
views

### End elementary extension in infinitary logic of some $L_\alpha$ producing a $L_\beta$

Let $L_\alpha$ be some admissible level of the constructible hierarchy and $M \supseteq L_\alpha$ an extension of $L_\alpha$. I am looking for conditions under which $M \simeq L_\beta$. It is not ...

6
votes

1
answer

342
views

### Is every homogeneous poset a lattice?

A poset $(P,\leq)$ is homogeneous if $P\cong [a,b]$ for all $a,b\in P$ with $a<b$ (where $[a,b] := \{x\in P: a\leq x\leq b\}$).
Examples of homogeneous posets include $[0,1]$, $[0,1]\cap \mathbb{Q}$...

4
votes

1
answer

234
views

### Is ${\cal P}(\omega)/\text{(fin)}$ a fractal poset?

If $(P,\leq)$ is a partially ordered set and $a,b\in P$ we set $[a,b]:=\{x\in P: a\leq x\leq b\}$. We say that $P$ is fractal if whenever $a,b\in P$ and $[a,b]$ contains more than one element, then $[...

-3
votes

1
answer

90
views

### Order-embeddability of ${\frak b}$ and ${\frak d}$ in $\mathbb{R}$ [duplicate]

The starting point of this question is the observation that in ${\sf (ZFC)}$, all ordinals $\alpha < \omega_1$ can be order-embedded in $\mathbb{R}$.
Let $\omega^\omega$ denote the set of all ...

1
vote

0
answers

96
views

### Causal-net category and poset category

Order is a fundamental mathematical structure. There are two natural ways to represent order structures, by posets and by causal-nets (acyclic directed graph). How can we compare these two ways, and ...

1
vote

1
answer

72
views

### Characterization of edge posets

Given an acyclic directed graph $G$, the set $E(G)$ of edges of $G$ equipped with the reachable order $\to$ is called the edge poset of $G$, where for two edges $e_1\to e_2$ means that there is a ...

10
votes

1
answer

315
views

### Synthetic differential / conformal geometry of Lorentzian manifolds?

Let $M$ be a sufficiently nice Lorentzian manifold of dimension $\geq 3$. It's known [1] (see also [2]) that the differential and even conformal structure of $M$ is completely encoded in the causal ...

2
votes

0
answers

59
views

### Countable highly order-transitive subgroups of $\mathrm{Aut}(\mathbb{Q},\leq)$

Consider $A := \mathrm{Aut}(\mathbb{Q},\leq)$, the group of order-automorphisms of $(\mathbb{Q},\leq)$. Call a subgroup $U$ highly order-transitive if for any two finite ordered sequences $s_1$ and $...

2
votes

0
answers

48
views

### What is known about sublocales defined by regular nuclei?

(For basic terminology, which is supposed to be standard anyway, see this other question, which inspired this one.)
I am interested in nuclei $j\colon L\to L$ on a frame $L$ which are regular elements ...

3
votes

1
answer

178
views

### Computing the Heyting operation on the frame of nuclei

(The following definitions are meant to be standard and are reproduced for completeness of the question.) A frame is a partially ordered set in which every finite subset has a greatest lower bound (“...

11
votes

1
answer

617
views

### Do all toposes satisfy the internal Zorn's lemma?

I came up with this question when trying to give a more detailed answer to a question by Tim Campion in a comment to Ingo Blechschmidt's answer to Examples of statements that are valid in every ...

2
votes

1
answer

150
views

### Non-cofiltered derived limits

As far as I know, the inverse limit and its derived functors can be defined even in case we are dealing with a functor $F: I \to A$ from a category $I$ that is not cofiltered. I would content myself ...

2
votes

0
answers

60
views

### Total orders on subsets

Let $X$ be some finite ground set. Let $\prec$ be a total order on the powerset $\mathcal{P}(X)$, such that if $A\prec A’,B\preceq B’$ and $A\cap B= A’ \cap B’ = \emptyset$, then $A \cup B \prec A’ \...

21
votes

1
answer

2k
views

### Why do we need "canonical" well orders?

(I asked this question on Math.SE earlier but received no response and am therefore moving it here, please note that I realise this question is probably incredibly naïve for the experienced set-...

2
votes

1
answer

73
views

### Request for literature recommendations on isotonic mappings

An isotonic mapping is a function between two partially ordered sets that preserves the ordering between the elements. Specifically, given two partially ordered sets $(X,\le)$ and $(Y,\le)$, a ...

5
votes

2
answers

471
views

### Do germs of open sets around a point form a frame?

Let $X$ be a topological space and $x \in X$ a point. Let $\Omega$ be the set of open sets (viꝫ. the topology) of $X$, and $\Omega_x$ the set of germs around $x$ of open sets, that is, $\Omega_x = \...

8
votes

1
answer

317
views

### Example of trickiness of finite lattice representation problem?

I'm trying to come up with a good explanation for my students of why the finite lattice representation problem is difficult. I've already shown that the "greedy approach" to representing the ...

6
votes

1
answer

232
views

### Poset as union of posets of lower cofinality

Let $ \mathbb{P}$ be any directed, well-founded poset of cofinality $ \aleph_{n+1}$, where $n$ is a natural.
Can we write it as an increasing union $ \mathbb{P} = \bigcup_{\alpha < \omega_{n+1} } \...

3
votes

0
answers

116
views

### Is there an ordered algebra analogue of the HSP theorem?

For an algebraic signature (= set of function symbols) $\Sigma$, say that an ordered $\Sigma$-algebra is a pair $\mathfrak{A}=(\mathcal{A};\le)$ where $\mathcal{A}$ is a $\Sigma$-algebra in the sense ...

4
votes

1
answer

189
views

### Exactly how much (and how little) can partial ordered sets (classes) embed to the cardinalities

In the paper "Convex Sets of Cardinals", Truss mentioned a result of Jech:
If $M$ is a countable transitive model of ZFC, and $(P,<)∈M$ is a poset, then there exists a Cohen extension of ...

27
votes

1
answer

6k
views

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

Let ${\mathcal A}$ be the family of subsets $A$ of the natural numbers ${\mathbf N}$ which are co-infinite (i.e., their complement is infinite). We partially order this family by set inclusion. A ...

6
votes

1
answer

210
views

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

The motivation for this question is the startling fact that there is an order-preserving injective map (embedding) from $\mathbb{R}$ into ${\cal P}(\omega)$. (Think Dedekind cuts.) I am wondering how &...

5
votes

1
answer

158
views

### Scott topology: Suprema of sequences are topological limits

I read that, with the Scott topology, suprema of sequences are topological limits (See page 1 of this article).
Let $(X, \le)$ be a DCPO, and $D$ be a directed subset of $X$.
I can easily see that the ...

2
votes

1
answer

208
views

### Measuring how "close" $\alpha\in[0,1]\setminus\mathbb{Q}$ is to being rational

Let $\mathbb{N}_+$ denote the set of positive integers and let $\mathbb{N}_0 = \mathbb{N}_+\cup\{0\}$. Fix $\alpha\in[0,1]\setminus \mathbb{Q}$. For $n\in\mathbb{N}_+$ we let the approximation radius ...

0
votes

0
answers

36
views

### Is the set of sub-dcpos a dcpo (directed-complete partial order)?

$\newcommand{\sub}{\mathrm{sub}}$Given a dcpo (directed-complete partial order) $\mathcal{X} = (\le, X)$, consider the set $\mathcal{X}^{\sub}$ of all sub-dcpos of $\mathcal{X}$. Can one define a ...

4
votes

2
answers

174
views

### Ordinal-universal linear order on $\kappa$ elements

The starting point of this question is the observation that if $\lambda$ is a countable ordinal, then there is an order-embedding $e:\lambda \hookrightarrow \mathbb{Q}$.
Given an infinite cardinal $\...

10
votes

0
answers

345
views

### Can one define in ZFC a directed system of embeddings on the class of all linear orders realizing the surreal line as the direct limit?

Consider the surreal line $\langle\newcommand\No{\text{No}}\No,\leq\rangle$, in its order structure only. This is a proper class linear order, which is universal for all set-sized linear orders, as ...

1
vote

1
answer

89
views

### The quantity of poset with a given number of pairs of incomparable elements

$\DeclareMathOperator\inc{inc}$Let $|X|=n$ and $\inc(X,\leq)=\{\{x,y\} : \neg (x\leq y)\wedge \neg (y\leq x)\}$, where $(X,\leq)$ is poset (possibly unconnected). Define the function:
$$\pi(n,m):=|\{(...

3
votes

1
answer

226
views

### Representing a binary relation

Consider a binary relation $R$ over a finite set $X$ of size $n$. Assume $R$ is antisymmetric and connected but not necessarily transitive. In essence, we are modeling an "option x beats option y&...