Questions tagged [order-theory]
The order-theory tag has no usage guidance.
645
questions
0
votes
1
answer
83
views
Permutations which respect a partial order
I have been studying the following situation, and I have a claim I believe to be true, but am unsure on how to approach it. I would appreciate any references I could look into where others have ...
2
votes
1
answer
205
views
Order on Euclidean space in which a finite poset embeds
Fix positive integers $k$ and $n$.
For which finite posets $(X,\lesssim)$ with $\#X=k$ does there exist an order embedding $\phi\colon(X,\lesssim)\to (\mathbb{R}^n,\le)$, where $\le$ is the standard ...
2
votes
1
answer
215
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 ...
25
votes
0
answers
539
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 ...
5
votes
1
answer
663
views
Is any order bounded continuous linear functionals a difference of positive continuous functionals?
Let $B$ be a Banach space and $K$ a closed proper cone in $B$ such that the induced partial order makes $B$ a vector lattice. Let $K'=\{x^*\in B':\langle x^*, x\rangle\geq 0\ \forall x\in K\}$ the ...
5
votes
1
answer
176
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 ...
6
votes
1
answer
212
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
191
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 ...
18
votes
3
answers
1k
views
Is there a natural measurable structure on the $\sigma$-algebra of a measurable space?
Let $(X, \Sigma)$ denote a measurable space. Is there a non-trivial $\sigma$-algebra $\Sigma^1$ of subsets of $\Sigma$ so that $(\Sigma, \Sigma^1)$ is also a measurable space?
Here is one natural ...
4
votes
1
answer
331
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 ...
3
votes
1
answer
215
views
Fractional ideals of maximal orders in quaternion algebras
Let D be a skew field that is central and finite-dimensional over a number field F (in particular: a quaternion algebra over F). Let $\Delta$ $\subseteq$ D be a maximal $\mathcal{O}$$_{F}$-order. Let $...
4
votes
1
answer
160
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
108
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(...
3
votes
0
answers
164
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 ...
4
votes
0
answers
103
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 ...
1
vote
0
answers
66
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&...
8
votes
1
answer
499
views
Can one characterize maximal antichains in terms of distributive lattices?
This is inspired by the recent question Verification of a maximal antichain
The celebrated duality between finite posets and finite distributive lattices has several nice formulations. One of them ...
16
votes
4
answers
1k
views
Can Suslin (or Aronszajn) lines ever be orderings of abelian groups?
I am interested in realizing linear orders as orderings of abelian groups. In particular, can Suslin lines (and other classes of line) be realised in this way?
Let $\mathcal{C}$ be a class of (...
2
votes
0
answers
70
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
206
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 (“...
9
votes
1
answer
351
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 ...
12
votes
4
answers
1k
views
Universal order type
Every countable order type, such as the countable ordinals, $\mathbb Z$, etc. can be embedded in $\mathbb Q$, so it is universal for countable order types. Is there a universal space for all linear ...
9
votes
1
answer
499
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
465
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 ...
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 ...
1
vote
1
answer
140
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 ...
3
votes
1
answer
134
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
79
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 ...
35
votes
3
answers
2k
views
How much choice is needed to show that formally real fields can be ordered?
Background: a field is formally real if -1 is not a sum of squares of elements in that field. An ordering on a field is a linear ordering which is (in exactly the sense that you would guess if you ...
19
votes
1
answer
457
views
Large Borel antichains in the Cantor cube?
Let $2^\omega$ be the Cantor cube $\{0,1\}^\omega$, endowed with the standard compact metrizable topology and the standard product measure, called the Haar measure. The Cantor cube is considered as a ...
4
votes
2
answers
253
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 ...
6
votes
3
answers
307
views
Does the rank (=height) of a well partial order bound its type (=length, =stature)?
Terminology and context
(This should all be standard, but is recalled because terminology sometimes varies, and also to put the question into perspective.)
A partially ordered set is called well-...
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 ...
3
votes
1
answer
192
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
307
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
409
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 ...
5
votes
2
answers
1k
views
Definition of continuous functions in order theory
If we have a complete partial order (i.e. directed complete) I find frequently the following definition of a continuous function. A function $f:A\to B$ where $A$ and $B$ are cpos is called continuous ...
2
votes
2
answers
290
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
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
482
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
368
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)$?
13
votes
1
answer
262
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 ...
6
votes
2
answers
239
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,...
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 ...
1
vote
1
answer
91
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 ...
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 \...
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 ...
13
votes
2
answers
2k
views
Ordinals that are not sets
The class of all ordinal numbers $\mathbf{Ord}$, aside being a proper class, can be thought of an ordinal number (of course it contains all ordinal numbers that are sets, not itself). Then one could ...
2
votes
3
answers
1k
views
Countable atomless boolean algebra covered by a larger boolean algebra
Suppose $Q$ is an atomless countable boolean algebra, and $B$ is an arbitrary atomless boolean algebra. $Q$ is unique modulo isomorphisms. There is a subalgebra in $B$ that is isomorphic to $Q$. There ...