# Questions tagged [posets]

A poset or partially ordered set is a set endowed with a partial order, meaning a binary relation $\leq$ which is reflexive ($x \leq x$ for all $x$), antisymmetric ($x\leq y$ and $y\leq x$ implies $x=y$), and transitive ($x\leq y$ and $y\leq z$ implies $x \leq z$).

**2**

votes

**2**answers

119 views

### Infima and suprema in the “transfer” function ordering

Let $X,Y$ be sets, $f, g:X\to Y$ be functions. We say $u:Y\to Y$ is a transfer function for $g$ to $f$ if $$f = u \circ g.$$ In that case we write $f \leq_t g$. Let $\mathrm{Fct}(X,Y)$ denote the ...

**2**

votes

**0**answers

45 views

### Obtaining the reduced incidence algebra in QPA

Given a finite poset $P$ (we can assume it is connected), the reduced incidence algebra of $P$ is the subalgebra of the incidence algebra of $P$ consisting of functions constant on isomorphic ...

**16**

votes

**1**answer

510 views

### How is this fixed point theorem related to the axiom of choice?

I'm hoping the answer to this is well-known.
Let $X$ be an ordered set (i.e. poset). An inflationary operator $f$ on $X$ is a function $f: X \to X$, not necessarily order-preserving, such that $f(x) ...

**6**

votes

**1**answer

224 views

### Does there exist a full and faithful embedding of $\mathsf{Poset}$ in $\mathsf{Set}$?

Does there exist a full and faithful embedding of the category of posets into the category of sets? I suspect no, but I don't know how to prove or disprove this.

**0**

votes

**3**answers

189 views

### Is every graph an incomparability graph?

Let $G=(V,E)$ be a simple, undirected graph. Is there a partial ordering $\leq\subseteq (V\times V)$ with the following property? $$\{v,w\} \in E \text{ if and only if } v||y$$
(We write $v||w$ in ...

**11**

votes

**1**answer

154 views

### Connected incomparability graph

Let $X$ be a finite set equipped with a partial order. (Not a preorder: $a < b$ implies $b \not< a$.) The corresponding incomparability graph has vertex set $X$ with an edge between two points ...

**11**

votes

**1**answer

244 views

### “Scott completion” of dcpo

If $A$ is poset with all directed suprema, it is common to consider the Scott topology on $A$, whose open subsets are the $U \subset A$ such that $U$ is upward closed and if $\bigcup_I a_i \in U $ for ...

**8**

votes

**2**answers

274 views

### Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$

Let $X$ be a set, and let $\text{Part}(X)$ denote the collection of all partitions of $X$. For $A, B\in \text{Part}(X)$ we set $A\leq B$ if $A$ refines $B$, that is for all $a\in A$ there is $b\in B$ ...

**4**

votes

**1**answer

156 views

### Embedding ordinals with the order topology into connected $T_2$-spaces

Is there a limit ordinal $\kappa_0$ with $\kappa_0 \lt 2^{\aleph_0}$ and such that for every limit ordinal $\lambda$ with $\kappa_0\leq \lambda\lt 2^{\aleph_0}$ there is a connected $T_2$-space $X_\...

**3**

votes

**0**answers

151 views

### The name for injective map $f:\mathbb{N}\rightarrow\mathbb{N}$ with $f(n)\geq n$ property

What is the name for map $f:\mathbb{N}\rightarrow\mathbb{N}$ (from natural numbers into natural numbers) with the following propeties:
1) $f$ is injective
2) $f(n)\geq n$ for every $n$?

**0**

votes

**1**answer

114 views

### Upward generators of $[\omega]^\omega$

If $(P,\leq)$ is a poset and $S\subseteq P$ we let $$\uparrow S = \{p\in P: p\geq s\text{ for some }s\in S\}.$$
Let $([\omega]^\omega,\subseteq)$ denote the collection of infinite subsets of $\omega$,...

**7**

votes

**0**answers

190 views

### Counting hyperplane arrangements up to combinatorial equivalence, simple examples and history

Two arrangements of (affine) hyperplanes in $d$-dimensional Euclidean space are combinatorially isomorphic (or combinatorially equivalent) if they have isomorphic posets of faces.
Counting the ...

**4**

votes

**1**answer

127 views

### Order convergence vs topological convergence in partially ordered sets

Short version of the question. If $(P,\leq)$ is a partially ordered set (poset), a topology denoted by $\tau_o(P)$ can be defined (see below). There is also another notion of convergence, called order-...

**3**

votes

**0**answers

66 views

### Embedding finite partially ordered sets into antisymmetric monoids

I am wondering if there is an easy answer to the following question:
Let us consider a finite partially ordered set $P$. It is clear that there exists a $k$ such that there is an order embedding $P\...

**3**

votes

**0**answers

52 views

### (When) is the Dedekind-MacNeille completion of a po-set Hausdorff?

Let $X$ be a p.o. Consider the topology on $X$ generated by
$$U_{x}^{-}:=X\setminus (x\uparrow),\quad U_{x}^{+}:=X\setminus (x\downarrow), \quad x\in X$$
Throughout this discussion I shall refer to ...

**0**

votes

**1**answer

103 views

### Ordered group acting freely on partially ordered set

Let $(G, <)$ be a totally ordered group, and let $<$ be left-invariant. Let $G$ act (freely?) on a partially ordered set $(S, <)$, such that this group action preserves the ordering:
$$ s_1 &...

**8**

votes

**1**answer

197 views

### Is the measurable space $(\omega_1,\mathcal{P}(\omega_1))$ separable?

Here $\omega_1$ is the first uncountable ordinal, and $\mathcal{P}(\omega_1)$ denotes the power set of $\omega_1$. Separable means countably generated as a $\sigma$-algebra.

**0**

votes

**0**answers

40 views

### A weaker locally convex topology on a pospace

A pospace is a topological space $X$ endowed with a closed partial order $\le$. A pospace $X$ is locally convex if it has a base of the topology consisting of open order-convex sets. A subset $A$ of a ...

**0**

votes

**1**answer

171 views

### $\text{Max}\big(\text{Sub}(\text{Sym}(\omega))\setminus \{\text{Sym}(\omega)\}\big)$

If $G$ is any group, then by $\text{Sub}(G)$ we denote the collection of all subgroups, ordered by $\subseteq$. If $(P,\leq)$ is a partially ordered set we let $\text{Max}(P)$ and the set of maximal ...

**2**

votes

**1**answer

94 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'$ ...

**6**

votes

**2**answers

236 views

### Is an Eulerian lattice shellable?

The notion of Eulerian lattice generalizes the notion of face lattice of a convex polytope.
(Bruggesse-Mani): The boundary complex of a convex polytope is shellable.
(Björner-Wachs): A poset is ...

**4**

votes

**2**answers

92 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

352 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$-...

**7**

votes

**0**answers

95 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$, ...

**7**

votes

**1**answer

326 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

133 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,\...

**10**

votes

**0**answers

139 views

### Poset of nonvanishing minors of a matrix

This question was posed on MSE here three days ago, but hasn't gotten any answers or suggestions. I hope it's okay to ask it on MO, but if I should wait a little longer, please just let me know.
Say $...

**1**

vote

**0**answers

49 views

### What is known about the following partial order (subquotients of linearly ordered set)

Fix two numbers $n,k\in \mathbb{N}$ and abbreviate $[n]:= \{0,1,\dots,n\}$ (as linearly ordered set). Consider diagrams $(I,\varphi)$ of the form
$$[n]\supset I\xrightarrow{\varphi}[k]$$ where $\...

**6**

votes

**4**answers

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

**3**

votes

**1**answer

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

**3**

votes

**3**answers

255 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

140 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

162 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

106 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) ...

**11**

votes

**2**answers

478 views

### What is known about ideal and divisibility lattices of GCD domains and their generalizations?

The divisibility relation "$a$ divides $b$", or concisely, $a \vert b$ defined over a commutative integral domain $R$ with identity induces a partial order on the multiplicative semigroup $R/R^{\times}...

**2**

votes

**1**answer

89 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

263 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

**1**answer

140 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

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

**5**

votes

**0**answers

89 views

### Probability of a maximal chain in a random subposet of a finite poset

Let $P$ be a finite poset, and let $0<p<1$. Choose a random subposet
$Q$ of $P$ by letting each $t\in P$ belong to $Q$ with probability
$p$. What is the best way to compute the probability that $...

**4**

votes

**1**answer

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

**4**

votes

**0**answers

210 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

146 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 $\...

**3**

votes

**1**answer

225 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

108 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$,...

**2**

votes

**1**answer

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

**2**

votes

**1**answer

76 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

44 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

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

**7**

votes

**0**answers

104 views

### Bound on number of nxn grids with lexicographical ordering / poset structure

Given $n\in\mathbb{N}$, consider the numbers $\{1,\ldots,n^2\}$ and a permutation $\pi\in S_{n^2}$. It induces pairs $(1,\pi(1))$, $\ldots$, $(n^2,\pi(n^2))$.
Consider an $n\times n$ grid. How many ...