Questions tagged [order-theory]
The order-theory tag has no usage guidance.
645
questions
1
vote
0
answers
38
views
Orderings derived from function sets (Marshall and Olkin book): looking for literature
I am looking into the book "Inequalities: Theory of Majorization and Its Applications, second ed. " of Marshall and Olkin.
In chapter 14 (Ordering Extending Majorization, section E) the definition of ...
8
votes
2
answers
204
views
Spaces without maximal homogeneous subspaces
A homogeneous space $(X,\tau)$ is a topological space such that for all $x,y\in X$ there is a homeomorphism $\varphi:X\to X$ such that $\varphi(x)=y$. As a previous question implies, the union of an ...
2
votes
1
answer
353
views
getting one tower from two
Suppose that $(L,\leq_L,0,1)$ is a distributive and complemented Lattice that is dense as an order (i.e. if $a<_L b\in L$ then there exists $x\in L$, s.t. $a<_L x<_L b$)
Suppose that there ...
1
vote
0
answers
112
views
reflexive relations that are "tridiagonally cycle-indexed" (or "almost ordered" matrices/relations)
Let's take $M$ be a $n\times n$ matrix whose entries are $0$ or $1$. (then we can call it the characteristic matrix of any relation $R_M\subset \left\{a_1,...,a_n\right\}^2$, such that $M_{ij}=1$ iff ...
2
votes
1
answer
296
views
Boolean completion of a partially ordered set
Given a poset $(P, \leq)$, is there a complete Boolean lattice $B$ and an order-preserving map $i_P: P\to B$ such that for any complete Boolean lattice $B'$ and order-preserving map $f: P\to B'$ ...
4
votes
1
answer
142
views
Kruskal's tree theorem and $\Pi_1$ sentences of linear orderings with finitely many constants
In their paper "Theories with recursive models" [1] Lerman and Schmerl used a version of Kruskal's tree theorem about finite n-augmented trees.
An n-augmented tree is a tree T together with $n$ unary ...
3
votes
2
answers
166
views
Terminology: product on strict preorders corresponding to direct product of preorders?
I’ve had trouble finding a well-established term for the following very obvious and elementary construction on strict partial orders (i.e. transitive, irreflexive relations):
Given two strict partial ...
2
votes
0
answers
163
views
Galois action on posets of number fields and $p$-adic fields
In the theory of group actions on posets one studies the action of a group $G$ on a poset $\mathcal{P}$ (via order-preserving permutations) partly through its derived action on the order complex of ...
3
votes
2
answers
135
views
In the context of directed graphs is it standard notation to allow an element of an independent vertex set to be contained in a loop?
Given any relation $R$, that is, any set of ordered pairs, we can associate a unique digraph $D$ to our relation $R$ by setting $D=(\text{fld}(R),R)$ where $\text{fld}(R)=\text{dom}(R)\cup\text{rng}(R)...
4
votes
2
answers
283
views
Order-embedding, but no lattice embedding between distributive lattices
Let $L$ be the power set lattice ${\cal P}(\{0,1,2\})$. It is clear that there is an order-preserving injective map from $M_3$ into $L$, but no injective lattice homomorphism (because $L$ is ...
9
votes
3
answers
404
views
Does the lattice of all topologies embed into the lattice of $T_1$-topologies?
Let $\kappa$ be an infinite cardinal, and let $\text{Top}(\kappa)$ be the lattice of all topologies on $\kappa$, ordered by $\subseteq$. Let $\text{Top}^{T_1}(\kappa)$ be the lattice of all $T_1$-...
5
votes
2
answers
324
views
A "strong" Galois-Tukey connection between orders with suborders
(Background, may be skipped by the knowledgeable reader: A Galois-Tukey connection between two partial orders $(P,\le)$ and $(Q,\le)$ is a pair of maps $\varphi^+:P\to Q$ and $\varphi^-:Q\to P$ ...
1
vote
0
answers
119
views
Ordinal corresponding to well-quasi-order on graphs
Let $K$ be an infinite cardinal. Then, by the Robertson–Seymour theorem, the set of graphs with fewer than $K$ vertices and edges form a well-quasi-order.
In terms of $K$, what is the maximal order ...
8
votes
0
answers
226
views
Is there a 'local' version of Near Coherence of Filters?
The axiom Near Coherence of Filters (NCF) is known to be independent of ZFC.
Axiom (NCF I): For any two free ultrafilters $\mathcal D$ and $\mathcal E$ on $\mathbb N$, there exist finite-to-one ...
7
votes
0
answers
115
views
Dimension of a union of downsets
We have established the following result regarding the Dushnik–Miller dimension of posets.
Let $P$ be a poset with downsets $C, D \subseteq P$. If the dimensions of $C$ and $D$ are $m$ and $n$, ...
9
votes
1
answer
423
views
Structure of $Hom(L_1,L_2)$, where $L_i$ are distributive lattices
Is there known structures/ or has there been studies on $Hom(L_1,L_2)$ of distributive lattices? Could it be made into a lattice naturally? Is there any structure on the set of ring valued functions $...
3
votes
1
answer
143
views
Maximal elements in the partially ordered set of image spaces
If $(X,\tau)$ is a topological space, let $\text{Im}(X)$ denote the collection of subsets $S$ of $X$ such that there is a continuous function $f:X\to X$ with $\text{im}(f) = S$.
Is there a space $(X,\...
0
votes
0
answers
101
views
Monotone conservation of a family of families with lower bound equal to 0
Let $(A,<_A,0_A)$ and $(B,<_B,0_B)$ be partial ordered sets and $\psi$ an increasing surjection from $A$ to $B$ such that $\psi^{-1}(0_B)=\left\{0_A\right\}$. If $P\subset A$ has a greater lower ...
4
votes
0
answers
109
views
Obtaining linear orderings on the classical Laver tables from large cardinals
If $k:V_{\lambda}\rightarrow V_{\lambda}$ is an elementary embedding and
$R\subseteq V_{\lambda}$, then let $k^{+}(R)=\bigcup_{\alpha<\lambda}k(R\cap V_{\alpha})$.
Recall that $\mathcal{E}_{\...
3
votes
0
answers
95
views
Poset where every Upper Set has a Greatest Element
Does anyone know of a term for (equivalently)
A preorder $P$ where for every $x \in P$ there exists $x_\top \ge x$ such that for any $y \ge x $, $x_\top \ge y $.
A preorder $P$ where for every $x \...
2
votes
1
answer
293
views
Name for this algebraic structure?
I've found myself looking at a structure $\mathbb{M}$ whose important properties are:
$\mathbb{M}$ is a discretely ordered additive monoid.
$\mathbb{M}$ has a least element, and this least element is ...
2
votes
1
answer
139
views
Efficiently embedding finite Boolean algebras into lattices of set partitions?
Let $P_n$ be the lattice of set partitions of $[n] = \{1,2,\dots,n\}$, let $B_n$ be the Boolean algebra of subsets of $[n]$.
Is there some $n_0$ such that for all $n \ge n_0$ it is possible to ...
7
votes
4
answers
2k
views
Strict and non-strict orderings
Consider a set $A$ equipped with two binary relations $\le$ and $<$, related in the appropriate ways for the strict and non-strict version of an ordering. One might make different choices about ...
1
vote
0
answers
59
views
Opposite of "holistic" for an operator
I am dealing with preference relations, i.e., strict partial orders on a given domain of objects. For example, if $R$ is a preference relation, the preference $a R b$ indicates that $a$ is better than ...
3
votes
1
answer
142
views
The Wallman and interval topologies on non-principal ultrafilters with the Rudin-Keisler preorder
If $(P,\leq)$ is a pre-odered set (that is, $\leq$ is a reflexive and transitive relation) and $x\in P$, we set $(\uparrow_{\leq} x) = \{p\in P: p\geq x\}$ and $(\downarrow_{\leq} x) = \{p\in P: p\leq ...
9
votes
3
answers
590
views
Associative mean
Can there be a function $m(a,b)$ that is both associative and a mean, i.e.,
$\min (a,b) \leq m(a,b) \leq \max (a,b)$? The obvious solutions are $m(a,b) = \max(a,b)$ or $\min(a,b)$, but are there ...
5
votes
1
answer
406
views
Growth rate of longest sequence of strings where no string is a subsequence of a later one
We define $STR(n)$ to be the longest sequence of strings with $n$ symbols such that the $k$th string has at most k symbols, the symbols of the string are taken from an alphabet consisting of $n$ ...
3
votes
3
answers
313
views
Countably infinite posets isomorphic to its intervals
Let $(P,\leq)$ be a countably infinite poset with the property that whenever $a<b\in P$ then $P\cong [a,b]$.
Question. If $P$ does contain elements $a,b$ with $a<b$, does this imply that $P \...
0
votes
2
answers
176
views
Is ${\cal P}(\omega)/\mathrm{(fin)}$ order-isomorphic to its intervals?
Let $a, b \in {\cal P}(\omega)/\mathrm{(fin)}$ with $a<b$. Do we have ${\cal P}(\omega)/(fin)\cong [a,b]$?
3
votes
1
answer
183
views
Order-preserving surjective map $f: {\cal P}(\omega)/(fin) \to [0,1]$
Is there an order-preserving surjective map $f: {\cal P}(\omega)/(fin) \to [0,1]$? Or from ${\cal P}(\omega)/(fin)$ onto $[0,1]\cap \mathbb{Q}$?
4
votes
1
answer
173
views
"Gaps" in the Rudin-Keisler ordering
If $(P,\leq)$ is a poset and $p\in P$, then we say that $p$ is the lower part of a gap there is $q \in P$, $q>p$ such that $[p,q] = \{p,q\}$. (This is equivalent to the statement that $(\uparrow p) ...
5
votes
1
answer
468
views
What ordinal corresponds to the T(3)?
Let's play a game. You start with the ordinal $\alpha$ and I start with the empty sequence. Each turn, you decrease your ordinal, and I add a tree (where each node can have one of three labels), ...
2
votes
1
answer
137
views
Is $({\cal P}(\omega), \leq_{\text{inj}})$ a distributive lattice?
For $A, B \subseteq \omega$ we set $A \leq_{\text{inj}} B$ if there is an injective and order-preserving map $f:\omega\to \omega$ , such that $f(A)$ is a down-set of $B$. It is easy to see that $\leq_{...
5
votes
1
answer
303
views
A different ordering on ${\cal P}(\omega)$
For $A, B \subseteq \omega$ we set $A \leq_{\text{inj}} B$ if there is an injective and order-preserving map $f:\omega\to \omega$ , such that $f(A)$ is a down-set of $B$. It is easy to see that $\leq_{...
3
votes
0
answers
584
views
Group acting freely on tree
A tree is a connected acyclic (symmetric) graph. A group acts freely on a graph if there are no inversion of edges and stabilizers of vertices are trivial.
The Bass-Serre Theorem states that A group ...
4
votes
1
answer
226
views
Cardinality of maximal chains in the poset of ultrafilters with Rudin-Keisler ordering
Let $\text{NPU}(\omega)$ be the set of non-principal ultafilters on $\omega$. The Rudin-Keisler preorder on $\text{NPU}(\omega)$ is defined by
$${\cal U} \leq_{RK} {\cal V} :\Leftrightarrow (\exists f:...
3
votes
1
answer
133
views
Unboundedness number and domination number of a poset $(P,\leq)$
Suppose $(P,\leq)$ is a poset without maximal elements. For $X\subseteq P$ we set $X^u = \{p\in P: p \geq x \text{ for all } x\in X\}$ and call this the set of upper bounds of $X$. We say that $B\...
4
votes
1
answer
153
views
Posets as graphs with the direct neighbor relation
Given any poset $(P,\leq)$ we define the "direct neighbor graph" as follows. Let $$E_P = \big\{\{a,b\}: (a<b \text{ or } a>b) \text{ and } \; ]\min\{a,b\},\max\{a,b\}[ = \emptyset\big\}.$$
It is ...
2
votes
1
answer
272
views
Infima in the Rudin-Keisler ordering
Let $\text{NPU}(\omega)$ be the set of non-principal ultafilters on $\omega$. The Rudin-Keisler preorder on $\text{NPU}(\omega)$ is defined by
$${\cal U} \leq_{RK} {\cal V} :\Leftrightarrow (\exists f:...
4
votes
0
answers
408
views
Can infinite bounded distibutive lattices be "arbitrarily wide"?
I was always thinking, in an informal way, that the powerset lattices ${\cal P}(X)$ (where $X$ is an infinite set) are the "widest" bounded distributive lattices with respect to their height. (In ${\...
6
votes
0
answers
166
views
Katetov ordering on ideals on $\omega$
Recall that a nonempty set ${\cal I}\subseteq {\cal P}(\omega)$ is a (set) ideal if
$B\in{\cal I}$ and $A\subseteq B$ imply $A\in{\cal I}$, and
$A,B \in {\cal I}$ implies $A\cup B\in {\cal I}$.
By $\...
2
votes
1
answer
236
views
Chains of maximum cardinality in distributive lattices
It's quite straightforward to construct a (complete) lattice in which no chain has maximum cardinality: for each $n\in \omega\setminus\{0\}$ let $C_n$ be a copy of $n$ with the chain ordering ...
3
votes
1
answer
261
views
Antichains of maximum cardinality: posets vs lattices
The following construction gives a poset such that no antichain has maximum cardinality: For $n\in\mathbb{N}\setminus\{0\}$, let "layer" $n$ consist of an antichain of $n$ points, and as for the ...
-1
votes
1
answer
141
views
Covering property of complete distributive lattices
Let $(L,\land,\lor)$ be a complete distributive lattice. Given $x\neq y \in L$, is there a finite set ${\cal I}$ of closed intervals in $L$ such that
no member of ${\cal I}$ contains both $x$ and $y$,...
10
votes
1
answer
156
views
necklace reconstruction in the permutation case
Suppose I want a necklace with $n$ beads labelled (bijectively) by $\{1, 2, \ldots n\}$, that is I want a cyclic order on $\{1, 2, \ldots, n\}$ (so for example $132$ is the same cyclic order as $321$ ...
2
votes
1
answer
158
views
Adjoints of the interval topology functor
Given a poset $(P,\leq)$ the interval topology $\tau_i(P)$ on $P$ is generated by
$$\{P\setminus{\downarrow x} : x\in P\} \cup \{P\setminus{\uparrow x} : x\in P\},$$
where $\downarrow x = \{y\in P: y\...
3
votes
1
answer
113
views
Hausdorff interval topology on distributive lattices
Given a poset $(P,\leq)$ the interval topology $\tau_i(P)$ on $P$ is generated by
$$\{P\setminus\downarrow x : x\in P\} \cup \{P\setminus\uparrow x : x\in P\},$$
where $\downarrow x = \{y\in P: y\leq ...
0
votes
1
answer
63
views
Order-preserving surjections on the Dedekind MacNeille completion
Suppose $L$ is a complete lattice, $P$ is a poset, and $f: L \to P$ is a surjective order-preserving map. If ${\bf DM}(P)$ is the Dedekind MacNeille completion of $P$, is there necessarily a ...
3
votes
2
answers
338
views
Order-preserving surjection ${\mathbb N}^{\mathbb N}\to [0,\infty)$
This is kind of a continuation of a recent (closed) question.
Is there an order-preserving surjective function $f:{\mathbb N}^{\mathbb N}\to [0,\infty)$ (where for $a,b\in {\mathbb N}^{\mathbb N}$ we ...
0
votes
2
answers
404
views
Ordered measurable spaces
Let $(X, \leq)$ be a partial order and $\Sigma_X$ a $\sigma$-algebra on $X$. Is the set $\{(x, y) \in X\times X \mid x \leq y\}$ measurable with respect to the product $\sigma$-algebra?