Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
13