Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11 votes
1 answer
345 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.6k
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
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 ...
Gro-Tsen's user avatar
  • 29.8k
3 votes
1 answer
205 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 (“...
Gro-Tsen's user avatar
  • 29.8k
11 votes
1 answer
646 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 ...
მამუკა ჯიბლაძე's user avatar
2 votes
1 answer
160 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 ...
Matteo Casarosa's user avatar
2 votes
0 answers
62 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’ \...
Zach Hunter's user avatar
  • 3,393
22 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-...
Vivaan Daga's user avatar
2 votes
1 answer
77 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 ...
stalinon's user avatar
5 votes
2 answers
483 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 = \...
Gro-Tsen's user avatar
  • 29.8k
8 votes
1 answer
333 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 ...
Noah Schweber's user avatar
6 votes
1 answer
245 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} } \...
Matteo Casarosa's user avatar
3 votes
0 answers
127 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 ...
Noah Schweber's user avatar
4 votes
1 answer
196 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 ...
Holo's user avatar
  • 1,633
28 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 ...
Terry Tao's user avatar
  • 108k
6 votes
1 answer
216 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 &...
Dominic van der Zypen's user avatar
5 votes
1 answer
161 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 ...
Bob's user avatar
  • 476
2 votes
1 answer
211 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 ...
Dominic van der Zypen's user avatar
0 votes
0 answers
38 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 ...
mathlete42's user avatar
4 votes
2 answers
185 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 $\...
Dominic van der Zypen's user avatar
10 votes
0 answers
361 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 ...
Joel David Hamkins's user avatar
1 vote
1 answer
97 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):=|\{(...
Ben Tom's user avatar
  • 107
3 votes
1 answer
230 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&...
Arthur B's user avatar
  • 1,882
2 votes
0 answers
113 views

Product-decomposition of ${\cal P}(\omega)/\rm{fin}$ [closed]

For $A,B\in {\cal P}(\omega)$ let us say that $A\simeq_{\rm{fin}} B$ if both $A\setminus B$ and $B\setminus A$ are finite. It is easy to see that this establishes an equivalence relation on ${\cal P}(\...
Dominic van der Zypen's user avatar
1 vote
1 answer
184 views

Lower bound on ratio of extreme order statistics

This question relates to bounds on expectations of order statistics, elaborated upon in the Book by Arnold and Balakrishnan (1989). Let $X_1,\ldots,X_n$ be i.i.d. continuous random variables ...
oyy's user avatar
  • 67
7 votes
2 answers
477 views

Counterexample for Chvatal's conjecture in an infinite set

Let $X \neq \emptyset$ be a set. We say that ${\cal F} \subseteq {\cal P}(X)$ is a down-set if ${\cal F}$ is closed under taking subsets. Whenever $a \in X$, we let ${\cal F}_a = \{ S \in F : a \in S\}...
Dominic van der Zypen's user avatar
5 votes
1 answer
248 views

Question about a family of nested countable subsets of $\mathbb{R}$

Let $\mathcal{F}$ denote a family of countable subsets of $\mathbb{R}$, such that for each $U, V\in\mathcal{F}$ we have that $U\subseteq V$, or $V\subseteq U$. Let $(\mathcal{F}, \preceq)$ denote the ...
solver6's user avatar
  • 291
4 votes
1 answer
103 views

Searching for cofinal subsets of directed sets subject to finite constraints

Let $(P,\leq)$ be a directed set with uncountable cofinality. For every element $p\in P$, we are given a finite set $c_p\subset P\smallsetminus \{p\}$ of "incompatible elements". We say that ...
Federico Vigolo's user avatar
4 votes
0 answers
173 views

To whom is the classification of atomic, modular finite lattices due?

Here lattice means a poset with meets and joins. A lattice is called atomic if every element is a join of atoms. There are a few different ways to define modular for finite lattices: one is that the ...
Sam Hopkins's user avatar
  • 22.7k
3 votes
1 answer
133 views

Ideals of an ordered ring

Suppose $R$ is a strictly ordered (non-commutative) ring, in particular $ab > 0$ for any $a,\, b > 0$, that is also discrete in that there are no elements between $0$ and $1$. Now consider a two-...
user avatar
1 vote
0 answers
94 views

Reference request: Time and proofs of shared pasts

Is there research about structures for notions of time with distributed systems of information, as with blockchains? I am thinking of tuples $(I, T, P, A, \prec, s, \eta, u)$ where $I$, $T$ and $P$ ...
Gerrit Begher's user avatar
2 votes
0 answers
50 views

Can we decompose an increasing net of functions into two increasing nets with prescribed supports?

Let $K$ be a compact Hausdorff space and let $U,V\subset K$ be open. Let $\left(f_{i}\right)_{i\in I}$ be an increasing net of continuous non-negative functions such that $f_{i}\le 1$ and $f_{i}$ ...
erz's user avatar
  • 5,385
3 votes
0 answers
95 views

Order type of monotone functions on $\Bbb N$ up to affine conjugation

Let's introduce order on non-strictly monotone functions $\Bbb N \to \Bbb N$ such that $f \leq g$ if $f(n) \leq Cg(Cn + C) + C$ and, of course, identify such $f, g$ if $f \leq g \leq f$. (Note absence ...
Denis T's user avatar
  • 4,416
10 votes
4 answers
897 views

Are arbitrary nonempty intersections of principal filters principal?

Suppose $\langle L,\leq\rangle$ is a lattice with join $\sqcup$. Let $F_1$ and $F_2$ be principal filters on $L$. Thus, for $i\in I=\{1,2\}$ there are $x_i\in L$ so that $F_i=\{y\in L:x_i\leq y\}$. In ...
underwhelmer's user avatar
2 votes
2 answers
221 views

Maximal uncountable chains in ${\cal P}(\omega)$

Let ${\cal P}(\omega)$ denote the power-set of $\omega$. We order it by set inclusion $\subseteq$ and say that ${\cal C}\subseteq {\cal P}(\omega)$ is a chain if for all $A, B\in {\cal C}$ we have $A\...
Dominic van der Zypen's user avatar
6 votes
0 answers
148 views

Natural bijection between join- and meet-irreducibles in modular lattices?

A well known property of finite modular lattices is that they have the same number of join-irreducible and meet-irreducible elements. I was wondering if there exists a natural bijection between these ...
Igor Makhlin's user avatar
  • 3,493
19 votes
1 answer
1k views

Is the theory of a partial order bi-interpretable with the theory of a pre-order?

A partial order relation $\leq$ on a set $A$ is a binary relation that is reflexive, transitive, and antisymmetric. A preorder relation $\unlhd$ (also sometimes known as a quasi order or pseudo order) ...
Joel David Hamkins's user avatar
3 votes
1 answer
114 views

When does a clone on a two-element set have almost abelian symmetry groups?

Say that a clone (in the sense of universal algebra) $\mathfrak{C}$ has almost abelian symmetry groups (= aasg) iff for each function $f(x_1,...,x_n)\in\mathfrak{C}$ there is an abelian subgroup $A\...
Noah Schweber's user avatar
14 votes
5 answers
804 views

Birkhoff's representation theorem vs matroid-geometric lattice correspondence

This question is motivated by the superficial observation that Birkhoff's representation theorem and the cryptomorphism between matroids and geometric lattices are sort of similar. The former says ...
Igor Makhlin's user avatar
  • 3,493
3 votes
1 answer
122 views

Spectral join in a $C^*$-algebra relative to its enveloping von Neumann algebra

I have a $C^*$-algebra $\mathcal{A}$, and would like to make use of the spectral order $\preceq$ coming from (the self-adjoint part of) its enveloping von Neumann algebra $\mathcal{A}^{**}$. I am most ...
Sean's user avatar
  • 135
1 vote
2 answers
129 views

Embedding $^\omega\omega$ and $S_\omega$ with lexicographic order into $\mathbb{R}$

Let $^\omega\omega$ be the collection of all functions $f:\omega\to\omega$. We order $^\omega\omega$ lexicographically, that is: For $f\neq g \in \,^\omega\omega$ let $m(f,g):= \min\{n\in\omega:f(n)\...
Dominic van der Zypen's user avatar
5 votes
1 answer
99 views

Computable functionals avoiding embeddings of linear orderings

Given a linear order $\mathcal{S}$, let $\mathbb{A}_\mathcal{S}$ be the class of all ordertypes which do not embed $\mathcal{S}$ (= do not have a suborder isomorphic to $\mathcal{S}$). Say that a ...
Noah Schweber's user avatar
2 votes
0 answers
38 views

Continuous analogue for Szpilrajn Theorem: complete preorder extends a continuous preorder

A corollary of Szpilrahn Theorem states: Any preorder on nonempty $X$ has a complete and transitive extension. I am thinking about the "Szpilrahn Theorem" for continuous preorder on ...
dodo's user avatar
  • 589
4 votes
0 answers
57 views

Are the countable (rayless) trees with wqo labels wqo?

It has been proved by Corominas that the countable trees with vertex-labels coming from a better-quasi-ordered set are better-quasi-ordered. My question is whether this holds if we replace bqo by wqo ...
Agelos's user avatar
  • 1,844
8 votes
1 answer
390 views

Smallest relation in complement of partial order that prohibits its extension

Let $P$ be a partial order on a finite set $S$ (assume that every element is related to at least one other element besides itself…this raises a few quick questions: is this implied by the definition ...
mathematrucker's user avatar
0 votes
1 answer
145 views

Partial orders on downward closed sets [closed]

Let $P = (V, \sqsubseteq)$ be a partial order and $\mathfrak{D}(P)$ denote the class of downward-closed subsets of the partial order $P$ (i.e, the class of $A \subseteq V$ such that $y\in A \;\&\; ...
user65526's user avatar
  • 629
3 votes
1 answer
553 views

Sum of $q$-binomial coefficients

Denote by $ \binom{n}{k}_q = \prod_{i=0}^{k-1} \frac{ q^{n-i} - 1 }{ q^{k-i} - 1 } $, $ k = 0, 1, \ldots, n $, the $ q $-binomial (Gaussian) coefficients. These numbers are symmetric, in the sense ...
aleph's user avatar
  • 503
5 votes
1 answer
213 views

Classification of multiplicative lattices

Question 1:Is there a classification of finite lattices which admit a multiplication making them into a finite multiplicative lattices? (see https://encyclopediaofmath.org/wiki/Multiplicative_lattice ...
Mare's user avatar
  • 25.8k
2 votes
0 answers
95 views

References discussing the category of ordered commutative rings

Is there a reference anywhere discussing the category of ordered commutative rings? I'm thinking of ordered commutative rings and ring homomorphisms preserving the order, but I would also be ...
Alec Rhea's user avatar
  • 8,977
7 votes
0 answers
138 views

poset of lattice properties

Is there a good overview of the dependencies between properties that a (finite) lattice poset can have? To give a practical example, I was looking for a property weaker than congruence uniform and ...
Martin Rubey's user avatar
  • 5,533

1
2
3 4 5
13