Questions tagged [order-theory]
The order-theory tag has no usage guidance.
645
questions
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 ...
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 $...
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
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 (“...
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 ...
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 ...
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’ \...
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-...
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 ...
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 = \...
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 ...
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} } \...
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 ...
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 ...
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 ...
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 &...
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 ...
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 ...
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 ...
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 $\...
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 ...
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):=|\{(...
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&...
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}(\...
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 ...
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\}...
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 ...
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 ...
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 ...
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-...
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$ ...
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}$ ...
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 ...
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 ...
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\...
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 ...
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) ...
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\...
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 ...
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 ...
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)\...
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 ...
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 ...
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 ...
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 ...
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 \;\&\; ...
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 ...
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 ...
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 ...
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 ...