Questions tagged [order-theory]
The order-theory tag has no usage guidance.
643
questions
16
votes
0
answers
262
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 ...
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), $$
...
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 ...
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 ...
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&...
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(...
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&...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 - ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$ ...
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)$?
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 ...
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,...
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 \...
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 ...
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 ...
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 ...
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 ...
4
votes
1
answer
287
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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}$...
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 $[...
-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 ...
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 ...
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 ...
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 ...
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 $...