# Questions tagged [order-theory]

The order-theory tag has no usage guidance.

569
questions

3
votes

1
answer

49
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

100
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

119
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

85
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

43
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}$ ...

2
votes

0
answers

76
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

816
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

149
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

103
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 ...

15
votes

2
answers

879
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

94
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\...

13
votes

4
answers

571
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

81
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

98
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

84
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

31
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

53
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 ...

7
votes

1
answer

310
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

93
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

431
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

182
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

91
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

124
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 ...

1
vote

0
answers

82
views

### Connected posets $P\not \cong Q$ such that $\text{Hom}(P,P) \cong \text{Hom}(Q,Q)$

Given posets $A, B$, we denote by $\text{Hom}(A,B)$ the collection of order-preserving functions $f:A\to B$. We put a partial order $\leq_{\text{Hom}(A,B)}$ on $\text{Hom}(A,B)$ by setting $$f \leq_{\...

7
votes

2
answers

230
views

### RELU representation of $\max(x,y,z)$

Here is a question that occurred to me while learning about neural networks. For $t\in\mathbb{R}$ put $t_+=\max(0,t)$, so $t_+=t$ if $t\geq 0$ and $t_+=0$ if $t\leq 0$. (This is RELU=rectified linear ...

0
votes

0
answers

123
views

### How to estimate sums over arithmetic progressions?

For $x>1$
$$
N(x)=\sum_{0<n<x \\n \equiv 1 \pmod 4\\ n\text{ squarefree}} 1
$$
How to estimate $N(x)$'s order? (Like $N(x) \sim Ax$)
Furthermore, for $n=p_1p_2\cdots p_v$, define $\alpha (n)=...

4
votes

1
answer

114
views

### Example of a bicontinuous poset which is not jointly bicontinuous?

Recall that a poset $P$ is said to be continuous if, for every $p \in P$, the set $\{q \in P \mid q \ll p \}$ is directed with supremum $p$. Here $q \ll p$ is the "way below" relation (see ...

5
votes

1
answer

341
views

### Poset of automorphism groups of variants of a structure

Say that two structures $\mathfrak{A},\mathfrak{B}$ in possibly different finite languages are parametrically equivalent - and write "$\mathfrak{A}\approx\mathfrak{B}$" - iff they have the ...

5
votes

0
answers

153
views

### Weak compactness is to trees as [?] is to lattices?

Let $\kappa$ be an inaccessible cardinal. Recall that $\kappa$ is weakly compact if every tree of height $\kappa$ has either a level of size $\kappa$ or a branch of size $\kappa$.
So if $\kappa$ is a ...

2
votes

1
answer

100
views

### Dedekind-MacNeille completion of ${\cal P}(\omega)/({\rm fin})$

Let ${\cal P}(\omega)/({\rm fin})$ be the quotient of the Boolean algebra ${\cal P}(\omega)$ where two sets are considered to be equivalent if they differ by a finite number of elements.
It turns out ...

1
vote

0
answers

59
views

### Derivative of a function of ordered variables

Can I differentiate
$$(\pmb{y}^o - (\pmb{x}\cdot\pmb{a})^o)^\top(\pmb{y}^o - (\pmb{x}\cdot\pmb{a})^o)$$ with respect to $\pmb{a}$? (I want to minimize the expression with respect to $\pmb{a}$.)
Here, $...

2
votes

1
answer

116
views

### Supremum with respect to the order of measures on $(X,A)$

Suppose that $(X,\leq )$ is an ordered set, we can define the maximum and the infimum of this set,now let $(X,A)$ be a measurable space and let $M(X,A)$ be the set of all measures on $(X,A)$, we now ...

3
votes

2
answers

234
views

### "Pseudo-Boolean" lattice (almost every element has several complements)

If $(L,\leq)$ is a lattice with bottom element $0$ and top element $1$ and $x\in L$ we say that $y$ is a complement of $x$ if $x\vee y = 1$ and $x\wedge y = 0$.
Is there a lattice $(L,\leq)$ with more ...

3
votes

1
answer

105
views

### A closed subset of a Dedekind-complete order has subspace topology equal to order topology

Here's a fairly easy fact from point-set topology that I'm having trouble finding a reference for. Say $X$ is a total order satisfying the least-upper bound property, and $S$ is a closed subset of it....

2
votes

1
answer

131
views

### Is the set of "endomorphisms" of a directed set again a directed set?

Let $(I,\leq)$ be a directed set, that is $\leq$ is reflexive and transitive and for every $a,b\in I$ we find $c\in I$ such that $a,b\leq c$. Now consider the set $M$ consisting of all maps $\sigma:I\...

2
votes

0
answers

115
views

### In a constructive order/lattice theory are the arbitrary join and the weak suprema the same?

For a poset $X$ we define an upperbound $w \in X$ of a subset $S \subseteq X$ to be a weak-supremum if
$(\forall a \in S (a \leq b)) \implies w \leq b$.
While a supremum is defined more carefully (in ...

6
votes

0
answers

178
views

### A representation of a partial order by a slowly changing sequence of linear orders

We study visualizations of attractors, which occur in chaotic dynamic systems, and for a few years trying to prove or refute Conjecture [3]. It has an equivalent formulation in terms of order theory, ...

1
vote

1
answer

113
views

### Density and compactness of Boolean embeddings

Let A and B be Boolean algebras and $h:A\rightarrow B$ a
Boolean embedding.
If every element of $B$ can be expressed both as a join
of meets and as a meet of joins of elements in $h(A)$, then the ...

5
votes

0
answers

117
views

### Chains of length $2^\kappa$ in ${\cal P}(\kappa)$ [duplicate]

It is a fact that continues to boggle my mind: There is a set ${\cal C}\subseteq {\cal P}(\omega)$ such that $|{\cal C}|=\frak{c}=2^{\aleph_0}$ and for all $A,B\in{\cal C}$ we have $A\subseteq B$ or $...

1
vote

0
answers

169
views

### Is there an algorithm to merge $d$ chains into $\left\lceil\frac{d}{k}\right\rceil$ chains?

I've come up with a problem as follow:
Given an integer $k > 1$, a queue $Q$ as a permutation of integers $1$ to $N$. You can apply an operation to the queue as follows:
split the queue into no ...

1
vote

1
answer

54
views

### inequivalent vertex weights on finite poset

Let $m\geq1$ and $P$ be an arbitrary poset with vertex set $V=\{v_1,\dots,v_n\}$, edge set $E,$ and set $O$ of orbits under $\text{Aut}(P).$ Can we efficiently generate all inequivalent nonnegative ...

4
votes

0
answers

103
views

### What do you call such a relation between subsets in a poset

Consider a poset $(X, \geq)$. Let's define a new relation $\succsim$ on subsets of $X$: for $A, B\subseteq X$, say $A\succsim B$ if for any $a\in A$ and any $b\in B$, we have $a\geq b$.
Does such a ...

3
votes

1
answer

163
views

### Obtaining an antichain from affine subspace

Suppose $a\in \{0,1\}^n$ and $S \subseteq \mathbb{F}_2^n$ is a subspace of dimension $d$. Define an affine subspace $S_a$ as follows:
$$S_a=\{a+x \mid x\in S\}.$$
What is the largest possible size of ...

3
votes

0
answers

88
views

### When is it possible to extend several linear orders defined "locally" into a single linear order defined "globally"?

This is a somewhat fuzzy question, so I will try my best to give a formulation which includes everything relevant while excluding everything else. I would like to find out if anyone else has studied ...

8
votes

1
answer

687
views

### What is the theory of the random poset?

$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random ...

6
votes

1
answer

194
views

### Maximal independent sets in MAD families

We call ${\cal A}\subseteq {\cal P}(\omega)$ almost disjoint if ${\cal A}\neq \varnothing$, every member of ${\cal A}$ is infinite, and for $A_1\neq A_2\in {\cal A}$ we have that $A_1\cap A_2$ is ...

6
votes

1
answer

105
views

### Tameable hypergraphs

Let $H=(V,E)$ be a hypergraph. We say that $I\subseteq V$ is an independent set if $e\not\subseteq I$ for all $e\in E$.
We say that $H$ is tameable if every independent set is contained in a maximal ...

9
votes

1
answer

281
views

### Origin and context of adjunctions inducing equivalences between full subcategories

The following is well-known.
Theorem. Let $F\dashv U$ be a pair of adjoint functors
$$F\colon \mathcal C\to \mathcal D, \qquad U\colon \mathcal D\to\mathcal C$$
with unit $(\eta_A\colon A\to U(F(A)))_{...

1
vote

0
answers

73
views

### Monoids with three or more "natural" partial orders

For any given monoid $M$ there may exist lots and lots of compatible pre-orders $\leq$. Only few of these are usually any interesting though. I can find some examples of monoids that have two non-...

1
vote

0
answers

116
views

### Strongly graded rings

In Theorem 3.1 of Graded rings over arithmetical orders, the authors prove that for a strongly $\mathbb{Z}$-graded ring $R$, if $R_0$ is left and right Goldie and a maximal order in its (classical) ...