Which partially ordered sets admits an order preserving map that preserves maximal elements from a proper subset containing all max. elements?

Question

Let $X$ be a (finite) partially ordered set. I am wondering if there is any necessary and sufficient condition for there to exist a proper subset $X' \subsetneq X$ which contains all maximal elements in $X$ and an order-preserving map $f: X \rightarrow X'$ which acts as the identity on maximal elements (of $X$). It's obviously not always true, since if $X$ is the poset with just 1 element, there are no proper non-empty subsets. On the other hand, if $|X| > 1$, the existence of a top or bottom element is clearly sufficient but not necessary. For example, $\{a, b, c, d\}$ with $a < b$ and $c < d$ has no top or bottom element but we can define $f(a) = f(b) = b, f(c) = f(d) = d$ which is a map with the desired properties.

In principle, for a given $X$ it suffices to check whether there exists such a map from $X$ to $X \backslash \{x\}$ for any $x \in X$ but even then it is not clear how to do it. Intuitively, one might guess that the map can always take the form $f(y) = y$ for all $y \neq x$ but this is not true. Consider the poset with maximal elements $A, B, C, D$ and elements $a_i, c_i, d_i$ for $i=1,2$ such that $a_i < A, c_i; c_i < B, C; d_i < D$. Then, if we try to map $X$ to, e.g. $X \backslash \{c_2\}$, and try to impose $f(a_2) = a_2$ and $f(d_2) = d_2$, then we need $a_2, d_2 \leq f(c_2) \leq B, C$ but the only element with these properties is $c_2$. Thus, we are forced to map $a_2, c_2, d_2$ to $a_1, c_1, d_1$. The same happens if you consider $X \backslash \{a_2\}$ and everything else follows from symmetry.

At a higher level of abstraction the question could also be phrased like this:

Denote the set of maximal elements of $X$ as $\text{max}(X)$ and define $\tilde{X} = X \backslash \text{max}(X)$. Define the preorder over the powerset $P(\tilde{X})$ in the following way: $A \geq B$ if there exists an order-preserving map $f: A \cup \text{max}(X) \rightarrow B \cup \text{max}(X)$ such that $f$ acts as the identity on $\text{max}(X)$. As any subset of $X$ can be order-embedded into $X$, $\tilde{X}$ is a bottom element of this preorder. When is $\tilde{X}$ the unique bottom element?

This feels like it might be helpful somehow, either via some category theoretic trick or some relationship between preorders over the powerset of the partial order and the partial order itself, but I'm honestly not sure how.

Answer 1

Edit - as Izaak notes in the comment, while I was thinking about the problem, I lost sight of the fact that $X'$ can contain more points than the maximal elements. So consider this a solution for only the case where $X'$ consists of just the maximal elements.

$X'$ is the set of all maximal elements of $X$. The elements of $X'$ are not comparable to each other, as otherwise the lower one would not be maximal. If $x \le y$, but $f(x) \ne f(y)$, then it would not be true that $f(x) \le f(y)$, since they are distinct elements of $X'$, and thus not comparable. So it must be that $f(x) = f(y)$ if and only if $x$ and $y$ are comparable.

Further, if $x \in X$ and $x \le y' \in X'$, because $x$ is comparable to $y'$, it must be that $f(x) = f(y') = y'$. Thus $x$ can only be under one maximal element.

Thus for each $x',y' \in X', x' \ne y'$ implies that no element of $f^{-1}(x')$ is comparable to any element of $f^{-1}(y')$. But inside $f^{-1}(x')$ every element is comparable to every other element.

Thus such a function $f$ is only possible if $X$ is the disjoint union of a collection of totally ordered sets, each of which has a unique maximal element. with the ordering on $X$ also being the union of the orderings on the subsets.

Note that this applies regardless of whether $X$ is finite or infinite, depending only on the existence of $f$.

Answer 2

Am I right that you're asking "when is there a non-surjective order endomorphism on $X$ which fixes each maximal element?" It's an interesting question! Since $X$ is finite, it's equivalent to ask about non-injective or non-bijective endomorphisms.

I've spent a little bit of time thinking about counterexamples. This is not an answer, but I thought I'd record some of my observations here in case they're useful to anyone (and specifically in an answer because they don't fit in a comment!)

The counterexamples I've cooked up so far rely on the following property:

Let $X_0$ be the set of maximal elements. For each $x \in X$, define $M^0(x) = \{y \in X_0 \mid x \le y\}$. Define $M_0(x) = \{y \in X_0 \mid x \ge y\}$ (this is trivial now, but more useful later). Let $X_1 = X_0 \cup \{x \in X \setminus X_0 \mid \forall y \in X \setminus \{x\}, M_0(x) \nsubseteq M_0(y)\ \text{or}\ M^0(x) \nsubseteq M^0(y)\}.$

This condition forces any such $f$ to also fix everything in $X_1$, because when $f$ sends $x$ to $y$, we must have $M_0(x) \subseteq M_0(y)$ and $M^0(x) \subseteq M^0(y)$, because $f$ is order-preserving and fixes everything in $X_0$. So now we have a (hopefully bigger) set of fixed elements. Continue defining $M_n, M^n, X_{n + 1}$ etc similarly in terms of $X_n$. If $X_n$ is eventually $X$, then any such $f$ must be the identity, so we have a counterexample.

This property was essentially just the most general reason I could come up with that would force no such $f$ to exist.

Some observations:

This condition is always sufficient for the failure of the existence of such an $f$.

Every element of $X_1 \setminus X_0$ is minimal in $X \setminus X_0$. (Since $y \le x$ implies $M^0(x) \subseteq M^0(y)$, and $M_0$ are all empty).

In a poset where every element of $X \setminus X_0$ is minimal (ie where $X \setminus X_0$ has the trivial "equality" ordering), this condition is necessary and sufficient for the failure of the existence of such an $f$. You can therefore generate all "two-level" counterexamples by starting with $n$ maximal elements, then taking an anti-chain $\mathcal A$ in $\mathcal P([n])$ not containing any singletons, and adding to the poset an element $x_S$ for each $S \in \mathcal A$, which is below precisely each maximal element in $S$. (By Sperner's Lemma the biggest possible anti-chain is the set of all $\lfloor n/2 \rfloor$-element subsets, so these examples can have many more elements than maximal elements). Here is a Hasse diagram of the case where $n = 4$ and $\mathcal A$ is the set of all $2$-sets.

There are examples where $X_0 \subsetneq X_1 \subsetneq X_2 = X$, so there is a point in continuing past $n = 1$. Here is the one I came up with (here $X_1$ is the bottom level and $X_2$ is the middle level):

I believe I also have a "four-level" example, whose levels have sizes $16, 8, 8, 3$ going from top to bottom. However, I have not managed to come up with a general $N$-level construction.

You can see exactly how it fails in some nice classes of examples where there is such an $f$:

If there is a bottom element $\bot$, then $X_1 \subseteq X_0 \cup \{\bot\}$ and the sequence stabilises from that point on, since all $x$ have $M^1(x) \subseteq M^1(\bot)$ and $M_1(x) \subseteq M_1(\bot)$.

If there is a top element $\top$, then $X_0 = \{\top\}$ and $M_0(x)$ are all just $\{\top\}$, so $X_1 = X_0$.

If there is a pair of elements $x, y$ such that $y$ is the unique element that covers $x$ (ie, in the Hasse diagram there is a single line coming up out of $x$, and it goes to $y$), then there is such an $f$ (send $x$ to $y$), and indeed $x$ will never belong to any $X_i$ (because $M_n(x) \subseteq M_n(y)$ and $M^n(x) \subseteq M^n(y)$ provided that $x \notin X_{n - 1}$), and neither will $y$, provided that $y \notin X_0$, by a similar argument. (Note that this generalises the "top element" and "bottom element" cases)

I haven't seriously tried to prove that this condition is necessary in general. I am not terribly convinced that it will be, because when it fails it's not so obvious to me how to extract an endomorphism from that.

Maybe it's interesting to ask if there are other types of counterexample, in the sense that this condition fails but there is still no such $f$, or in the sense that there is no such $f$ but there are nontrivial automorphisms. Also, if there are $n$-level counterexamples (counterexamples where $X_0 \subsetneq X_1 \subsetneq X_2 \subsetneq \dotsb \subsetneq X_n$) for arbitrarily large $n$.