Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Fabio's user avatar
  • 329
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 ...
Dominic van der Zypen's user avatar
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 ...
jcdornano's user avatar
  • 469
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 ...
jcdornano's user avatar
  • 469
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'$ ...
Dominic van der Zypen's user avatar
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 ...
Dino Rossegger's user avatar
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 ...
Peter LeFanu Lumsdaine's user avatar
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 ...
user avatar
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)...
Ethan Splaver's user avatar
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 ...
Dominic van der Zypen's user avatar
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$-...
Dominic van der Zypen's user avatar
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$ ...
Goldstern's user avatar
  • 13.9k
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 ...
Christopher King's user avatar
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 ...
Daron's user avatar
  • 1,761
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$, ...
Michael Engen's user avatar
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 $...
mukhujje's user avatar
  • 281
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,\...
Dominic van der Zypen's user avatar
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 ...
jcdornano's user avatar
  • 469
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}_{\...
Joseph Van Name's user avatar
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 \...
Max New's user avatar
  • 785
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 ...
Alec Rhea's user avatar
  • 8,977
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 ...
András Salamon's user avatar
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 ...
Mike Shulman's user avatar
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 ...
Maiaux's user avatar
  • 151
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 ...
Dominic van der Zypen's user avatar
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 ...
Hauke Reddmann's user avatar
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$ ...
Christopher King's user avatar
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 \...
Dominic van der Zypen's user avatar
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]$?
Dominic van der Zypen's user avatar
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}$?
Dominic van der Zypen's user avatar
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) ...
Dominic van der Zypen's user avatar
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), ...
Christopher King's user avatar
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_{...
Dominic van der Zypen's user avatar
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_{...
Dominic van der Zypen's user avatar
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 ...
poset's user avatar
  • 63
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:...
Dominic van der Zypen's user avatar
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\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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:...
Dominic van der Zypen's user avatar
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 ${\...
Dominic van der Zypen's user avatar
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 $\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
-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$,...
Dominic van der Zypen's user avatar
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$ ...
Karen Yeats's user avatar
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\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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?
daon's user avatar
  • 239

1
4 5
6
7 8
13