Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
  • 19.6k
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}$ ...
  • 5,057
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 ...
  • 3,457
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 ...
  • 3,028
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,028
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 ...
  • 53
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 ...
  • 567
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 ...
  • 1,364
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 \;\&\; ...
  • 617
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 ...
  • 425
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 ...
  • 22.5k
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 ...
  • 6,857
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 ...
  • 5,029
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)=...
  • 1
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 ...
  • 51.1k
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 ...
  • 51.1k
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, $...
  • 133
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 ...
  • 405
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,525
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 ...
  • 361
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, ...
  • 2,737
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 ...
  • 151
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 ...
  • 229
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 ...
  • 171
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 ...
  • 173
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-...
  • 11
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) ...
  • 263

1
2 3 4 5
12