Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
17 votes
0 answers
276 views

A conjecture about inclusion–exclusion

$\newcommand\calF{\mathcal{F}} \def\cupdot {\stackrel{\bullet}{\cup}} \def\minusdot {\stackrel{\bullet}{\setminus}}$This post presents a conjecture that we have with some colleagues. It is about ...
M.Monet's user avatar
  • 271
6 votes
1 answer
208 views

Fixed points for finitary distributive lattices bijection

Birkhoff's Fundamental Theorem of Finite Distributive Lattices says that there is a bijection $$ \{ \textrm{finite posets}\} \to \{ \textrm{finite distributive lattices}\} $$ $$ P \mapsto J(P), $$ ...
Sam Hopkins's user avatar
  • 22.5k
3 votes
1 answer
189 views

Embedding of a poset with "desirable" characteristics

Let $(P, \succeq)$ be a poset (you can assume $\succeq$ is not empty). I am interested in finding a poset $(X, \succeq^*)$ that embeds $(P, \succeq)$, and $\forall x,y \in X$ both of the following ...
Pedram's user avatar
  • 97
4 votes
1 answer
326 views

Kuratowski's 14 theorem and universal algebra

For a tuple of functions $\overline{p}$ on a set $Y$, let $cl_{\overline{p}}$ be the associated closure operation: $cl_{\overline{p}}(Z)$ is the smallest subset of $Y$ containing $Z$ and closed under ...
Noah Schweber's user avatar
4 votes
1 answer
157 views

Lattice description of matroid duality

Apologies for this very basic question in matroid theory, but I could not find anything about it online after a bit of searching. There is a well-known bijective correspondence ("cryptomorphism&...
Sam Hopkins's user avatar
  • 22.5k
0 votes
0 answers
107 views

"Infima" and "suprema" in the homomorphism preorder on hypergraphs on $\omega$

$\newcommand{Po}{{\cal P}(\omega)}$ $\newcommand{lh}{\leq_{\text{hom}}}$ If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(...
Dominic van der Zypen's user avatar
1 vote
0 answers
65 views

Ordered combinatorial classes and partitions

Let $\mathcal{C}$ be a combinatorial class and let $\leq$ be a partial order on $\mathcal{C}$. We say that $(\mathcal{C},\leq)$ is an ordered combinatorial class if for all $x,y\in\mathcal{C}$, $$x&...
smoneh's user avatar
  • 11
4 votes
0 answers
102 views

Can we extend "every finite lattice is a sublattice of partitions of a finite set" to linear and/or finitary lattices?

Pudlák and Tůma https://link.springer.com/article/10.1007/BF02482893 proved that every finite lattice can be embedded as a sublattice of the partition lattice of a finite set. Can this be generalized ...
Dale's user avatar
  • 429
9 votes
1 answer
350 views

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

A set $A\subseteq \omega$ is said to be thin if $$\lim\sup_{n\to\infty}\frac{|A\cap \{0,\ldots, n\}|}{n+1} = 0.$$ We say for $A, B\subseteq \omega$ that $A\simeq_\text{fin} B$ if the symmetric ...
Dominic van der Zypen's user avatar
9 votes
1 answer
497 views

Reference request: number of antichains of a partially ordered set

Let $\mathbb{N}$ denote the set of all positive integers. For each $n \in \mathbb{N}$, define the set $$ P_n = \{ (a,b) \in \mathbb{N} \times \mathbb{N} : 1 \leq a \leq b \leq n \} $$ and consider the ...
E W H Lee's user avatar
  • 563
12 votes
1 answer
461 views

Is the Tukey order well-founded

Consider the Tukey order restricted to directed orders of the form $(U,\supseteq)$, where $U$ is an ultrafilter on $\omega$. It is defined as follows: For two ultrafilters $U,W$ on $\omega$, we say ...
Tom Benhamou's user avatar
3 votes
0 answers
163 views

Can the set of parafinite congruences be descriptive-set-theoretically complicated?

Fix an algebra $\mathfrak{A}$ with underlying set $\mathbb{N}$ and finite language $\Sigma$. The set of congruences on $\mathfrak{A}$ is a closed subset $C_\mathfrak{A}$ of $2^\mathbb{N}$ (with the ...
Noah Schweber's user avatar
1 vote
1 answer
139 views

Congruences that aren't "finite from above," take 2: semigroups

This is a hopefully less trivial version of this question. Briefly, say that a congruence is parafinite if it is the largest congruence contained in some equivalence relation with finitely many ...
Noah Schweber's user avatar
5 votes
3 answers
526 views

Congruences that aren't "finite from above"

Let $\mathfrak{A}=(A;...)$ be an algebra in the sense of universal algebra. Say that a congruence $\sim$ on $\mathfrak{A}$ is parafinite iff there is an equivalence relation $E\subseteq A^2$ with ...
Noah Schweber's user avatar
3 votes
1 answer
133 views

Posets of equational theories of "bad quotients"

This is a follow-up to an older question of mine: Suppose $\mathfrak{A}=(A;...)$ is an algebra (in the sense of universal algebra) and $E$ is an equivalence relation - not necessarily a congruence - ...
Noah Schweber's user avatar
1 vote
1 answer
78 views

Sizes of linearly ordered subalgebras of powers

On the grounds that I'm currently teaching a linear algebra class and I enjoy making my students furious, let a linear algebra be an algebra $\mathcal{A}$ in the sense of universal algebra equipped ...
Noah Schweber's user avatar
5 votes
1 answer
167 views

Order bounded version of monotone complete $C^*$-algebras

Let $A$ be a $C^*$-algebra with self-adjoint part $A_{\operatorname{sa}}$. Then $A$ is called monotone complete if every increasing norm bounded net in $A_{\operatorname{sa}}$ has a supremum (with ...
Jochen Glueck's user avatar
4 votes
2 answers
252 views

Does strong stochastic ordering exist?

For two probability measure $\mu$ and $\nu$ on $\mathbb{R}$, we call $\mu$ is stochastically smaller than $\nu$ (i.e., $\mu\leq\nu$) , if $\int f \, d\mu\leq\int f \, d\nu$ for any nonnegative bounded ...
Jinxiang Yao's user avatar
0 votes
0 answers
74 views

Conditions for logarithmic upper bound on size of antichains in a partial order

Suppose I have a partial order $(P,\le)$ (in practice I have a very specific one, but let's start with a generic question). Are there known conditions that would imply that the size of any antichain ...
Nicola Gigante's user avatar
3 votes
1 answer
191 views

Reference Request for "Finite Semilattice with Top and Bottom is a Lattice"

Let $\mathcal{O}(P)$ be a finite, completely distributive lattice of all lower sets ordered by set inclusion. Moreover, let $K =\; \mathrel{\{} h(x) \mathrel{|} x \in \mathcal{O}(P) \mathrel{\}}$ be ...
Björn's user avatar
  • 33
1 vote
1 answer
306 views

Is there anyway to formulate the Alexandrov topology algebraically?

One knows that the Alexandrov topology on a preordered set is the finest topology that induces the same [specialization] preorder on the set. Given this, one finds a one-to-one correspondence between ...
Bastam Tajik's user avatar
5 votes
2 answers
408 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 ...
user76284's user avatar
  • 1,793
4 votes
1 answer
175 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 ...
Tri's user avatar
  • 1,366
7 votes
1 answer
478 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)$ ...
C7X's user avatar
  • 1,176
10 votes
4 answers
367 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)$?
Dominic van der Zypen's user avatar
1 vote
1 answer
90 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 ...
A beginner mathmatician's user avatar
6 votes
2 answers
237 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,...
Igor Makhlin's user avatar
  • 3,493
5 votes
0 answers
187 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 \...
Sam Hopkins's user avatar
  • 22.5k
2 votes
1 answer
122 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 ...
Nick's user avatar
  • 61
13 votes
1 answer
260 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 ...
Dominic van der Zypen's user avatar
3 votes
2 answers
201 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 ...
Dominic van der Zypen's user avatar
2 votes
2 answers
289 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 ...
Mare's user avatar
  • 25.7k
4 votes
1 answer
288 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$ ...
Pedram's user avatar
  • 97
1 vote
0 answers
69 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 ...
Denis Serre's user avatar
  • 51.5k
5 votes
0 answers
122 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 ...
Pete L. Clark's user avatar
2 votes
0 answers
90 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 ...
mathematrucker's user avatar
3 votes
0 answers
123 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 ...
mahu's user avatar
  • 63
1 vote
0 answers
90 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 ...
Keshav Srinivasan's user avatar
1 vote
1 answer
193 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 ...
mathematrucker's user avatar
3 votes
0 answers
69 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 ...
Keshav Srinivasan's user avatar
2 votes
0 answers
79 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$ ...
Cheuk Ting Li's user avatar
10 votes
0 answers
256 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 ...
Sourav Ghosh's user avatar
2 votes
0 answers
157 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 ...
Johan's user avatar
  • 491
6 votes
1 answer
349 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}$...
Dominic van der Zypen's user avatar
4 votes
1 answer
254 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 $[...
Dominic van der Zypen's user avatar
-3 votes
1 answer
96 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 ...
Dominic van der Zypen's user avatar
1 vote
0 answers
102 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 ...
xuexing lu's user avatar
1 vote
1 answer
79 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 ...
xuexing lu's user avatar
11 votes
1 answer
343 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 ...
Tim Campion's user avatar
  • 60.5k
2 votes
0 answers
60 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 $...
THC's user avatar
  • 4,313

1
2 3 4 5
13