Questions tagged [order-theory]
The order-theory tag has no usage guidance.
644
questions
7
votes
2
answers
399
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
128
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
134
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 ...
6
votes
1
answer
371
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
195
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
112
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
61
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, $...
3
votes
1
answer
200
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
466
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
151
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
136
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
139
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
187
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
130
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
126
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
189
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
65
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
110
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
169
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
92
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 ...
10
votes
1
answer
820
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
239
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
109
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
302
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
183
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) ...
3
votes
1
answer
169
views
Well-foundedness of divisibility vs well-foundedness of right- and left-divisibility
Say that a preorder (i.e., a reflexive and transitive binary relation) $\preceq$ on a set $X$ is
artinian if there is no sequence $(x_n)_{n \ge 1}$ of elements of $X$ with $x_{n+1} \prec x_n$ for ...
4
votes
0
answers
122
views
Cofinality without choice: can this coarse definition suffer badly?
This is a rephrased version of a question previously asked at MSE without success.
Working in $\mathsf{ZF}$, it is no longer possible in general to give every linear order an ordinal cofinality. For ...
3
votes
0
answers
203
views
Does every finite lattice embed into a finite Eulerian lattice?
A finite Boolean lattice is a lattice isomorphic to the subset lattice of a finite set. Every Boolean lattice is Eulerian, namely, a graded lattice $L$ such that $\mu(a,b) = (-1)^{|b|-|a|}$ for all $a,...
3
votes
1
answer
152
views
Is it true that the structure of a commutative ordered semiring is unique on a commutative ordered monoid?
Is it true that the structure of a commutative ordered semiring with identity is unique on a commutative ordered monoid (i.e., the structure of the monoid and the order are consistent)? I am not ...
3
votes
1
answer
186
views
${\frak b}$ and ${\frak d}$ in the Rudin-Keisler preordering
If $(Q,\leq)$ is any preordered set (that is, $\leq$ is a reflexive and transitive, but not necessarily anti-symmetric relation), then we say that $S\subseteq Q$ is
unbounded if for all $q\in Q$ ...
2
votes
1
answer
211
views
closure operator on a complete lattice arising from adjunction on lattice itself
Define a closure operator on a complete lattice $L$ as a function $f:L \to L$ which is order preserving and idempotent and satisfies $x \leq fx$.
Every closure operator arises from an adjunction ...
0
votes
1
answer
83
views
Countable sup property of extended measurable functions
Let $(S,\Sigma,\mu)$ a $\mu$-finite measure space. Denote by $\bar{L}^0(\Sigma)$ the set of extended-real valued $\Sigma$-measurable functions. Does this set have the countable sup property when ...
1
vote
1
answer
91
views
Minimizing the set of monochromatic edges
For sets $A, B$ we write $B^A$ for the set of all functions $f:A\to B$.
Let $H = (V,E)$ be a hypergraph such that $V,E\neq\varnothing$ and $|e| \geq 2$ for all $e\in E$. Let $\kappa>1$ be a ...
6
votes
1
answer
195
views
Sum of order polynomials of a set of posets
Let $n\in \mathbb{Z}_{>0}$. For every subset $S\subseteq \left[ n-1\right]$ we define a poset $P_S=\left([n],\le_{P_S}\right)$ given by the covering relation $\lessdot$ which is defined as
\begin{...
8
votes
1
answer
497
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 ...
8
votes
1
answer
540
views
Verification of a maximal antichain
In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the ...
1
vote
1
answer
140
views
Is the Rudin-Keisler ordering a continuous relation?
If $X, Y$ are topological, and $R\subseteq X\times Y$ we say that $R$ is continuous (from $X$ to $Y$) if for every $V\subseteq Y$ with $V$ open, we have $$R^{-1}(V) = \{u\in U: \exists v\in V:(u,v)\...
3
votes
1
answer
160
views
Is there an explicit linear extension for the subsequence partial order?
Consider the set of finite sequences (of bounded length $\leq k$, if necessary) whose elements are taken from some finite alphabet $\Sigma$. We define a partial order on this set so that
$X = (X_1,...,...
1
vote
1
answer
165
views
A diffuse probability distribution in high dimensions with order constraints
Consider the following subset of the unit cube in $\mathbb R^n$:
$$
\mathcal D = \{ p = (p_1,p_2,\dots,p_n) \in [0,1]^n:\; p_1 \le p_2 \le \cdots \le p_n\}.
$$
We would like to construct a probability ...
8
votes
2
answers
199
views
Constructing a $0/1$ polytope from an abstract simplicial complex
Let us fix $\Delta$ a finite simplicial complex, and label the vertices of $\Delta$ as $\{1,2,\ldots,n\}$. For each $F\in \Delta$ let us consider the point in $\mathbb{R}^n$ given by:
$$e_F := \sum_{i\...
0
votes
1
answer
108
views
Ordering preserved by an inverse frame homomorphism
Recall that a frame homomorphism $h:L\to M$ is called ($L$ and $M$ are frames):
Dense if, for any $x ∈ L$, $h(x) = 0$ implies $x = 0$.
Codense if, for any $x ∈ L$, $h(x) = 1$ implies $x = 1$.
...
18
votes
1
answer
1k
views
Suprema of directed sets
Let $(X, \le)$ be a partially ordered set. We call a subset $S \subseteq X$...
... a chain if each two elements in $S$ are comparable with respect to $\le$ (in other words, $S$ is linearly ordered ...
8
votes
2
answers
249
views
Euler characteristic of the simplicial complex of sets of elements in a semilattice with non-zero meet
In a combinatorial computation, I came across the following quantity:
Consider a finite meet semilattice $L$, that is, a finite poset which is closed under $\min$. Denote the least element of $L$ by $...
14
votes
1
answer
781
views
Does there exist an ordering-functor?
This sounds like a very silly question which should have have a negative answer but I don't see an argument. The precise question is this:
Does there exist a covariant functor $ord$ from the category ...
4
votes
2
answers
373
views
Non-homeomorphic connected $T_2$-spaces with isomorphic topology poset
What are examples of non-homeomorphic connected $T_2$-spaces $(X_i,\tau_i)$ for $i=1,2$ such that the posets $(\tau_1, \subseteq)$ and $(\tau_2,\subseteq)$ are order-isomorphic?
5
votes
1
answer
308
views
Complete Boolean algebras of subsets of $\mathbb N$
Let $\mathfrak A$ be a subset of $\mathrm{Pow}(\mathbb N)$, the powerset of $\mathbb N$. Assume that $\mathfrak A$ is a complete Boolean algebra in the induced order, i.e., the inclusion order. Does ...
18
votes
3
answers
758
views
What is the minimum size of a partial order containing all partial orders of size 5?
This earlier MO question asks to find the minimum size of a partial order that is universal for all partial orders of size $n$, i.e. any partial order of size $n$ embeds into it, preserving the order. ...
4
votes
1
answer
299
views
How to define a function that has these specific properties?
Suppose $x = (x_1,x_2,\dots,x_K) \in \mathbb{Z}^K_{\geq 0}$. For $x,y \in \mathbb{Z}^K_{\geq 0}$, we write $x \succ y$ or $y \prec x$ if $x \neq y$ and
\begin{align*}
x_{i(x,y)} > y_{i(x,y)...
11
votes
0
answers
240
views
Existence of a strong antichain
Call an antichain (set of pairwise incomparable elements) $A$ of a poset $P$ strong if for every $p,q \in P$ with $p \leq q$ there exists an $a\in A$ which is comparable with both $p$ and $q$.
...
11
votes
0
answers
269
views
Does every finite poset have a rigid endomorphism?
Crossposted on Mathematics.
In this post, an order-preserving self-map of a poset $X$ will be called an endomorphism of $X$, and such an endomorphism $f$ will be called rigid if the only automorphism ...