5
$\begingroup$

Lately I have been considering a certain partial ordering on the subsets of a totally-ordered set. My question is:

Does this ordering have a name?

The ordering is defined as follows:

If $\langle S, \le\rangle$ is totally ordered and $A, B\in 2^S$ then we say

$$A\preceq B$$ if and only if there is an injective mapping $m:A\to B$ such that $$a \le m(a)$$ for all $a$ in $A$.

Here are the Hasse diagrams for $\langle 2^S, \preceq\rangle $ when $S$ has three or four elements: (In the diagrams, we assume that $a\le b \le c \le d$ and abbreviate $\{a, c, d\}$ as just “$acd$”.)

enter image description here enter image description here

It can be shown that when $S$ is finite, $\preceq$ is a partial order on $2^S$ that refines the usual partial order of subset containment. $A\preceq B$ whenever $A\subseteq B$, since in that case we can take $m$ to be the obvious embedding mapping. But $\preceq$ is stronger than $\subseteq$ since $\{a\}$ and $\{b\}$ are not comparable under the usual $\subseteq$ ordering but $\{a\}\preceq \{b\}$ holds whenever $a\le b$.

Is there any standard name for this ordering, or perhaps some simpler way to understand it as a variation on something better-known?

Also, is there a standard name for the property that a function $m$ of an ordered set has when $a \le m(a)$ for all $a$?

$\endgroup$
6
  • 3
    $\begingroup$ Concerning that last, and less important (?) question, a function $f$ on a poset that satisfies $x \leq f(x)$ is usually called extensive, in the context of closure operators. I suppose you knew that, but might have overlooked it. $\endgroup$
    – amrsa
    Jul 24 at 8:03
  • $\begingroup$ Might be it's of less importance, since in general it is not antisymmetric ? $\endgroup$
    – Ulli
    Jul 24 at 8:55
  • $\begingroup$ @amrsa I did not know “extensive”, thanks. $\endgroup$
    – MJD
    Jul 24 at 14:31
  • 1
    $\begingroup$ Usually, by definition, a partial order has to be antisymmetric (i.e., if $A\preceq B \preceq A$, then $A = B$). However, since this need not be the case for the relation you defined, people might be less interested in it. $\endgroup$
    – Ulli
    Jul 24 at 15:10
  • 1
    $\begingroup$ Right, thanks. It is antisymmetric on finite sets, which is all I am considering at present. I have updated the question to reflect this. $\endgroup$
    – MJD
    Jul 24 at 15:24

1 Answer 1

Reset to default
1
$\begingroup$

The OEIS sequence A009997 is closely related to this ordering. It lists the number of possible orderings of all $2^S$ subsets of $S$ that are achievable as orderings of the sums of the subsets.

A 1999 paper by Diane Maclagan discusses and enumerates these orders, which are called "boolean term orders" or "antisymmetric comparative probability orders". An additional distinction is drawn between coherent term orders, which are consistent with the subset sum interpretation, versus a generic boolean term order, which need only obey the "more elements or bigger elements" ordering requirement given in the question.

For instance, the third element of A009997 is 2, because there are two possible orderings of the sums of the subsets of a 3-element set, depending in whether $AB$ is bigger than $C$.

I asked a codegolf question about this sequence a while back, which has more examples.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .