6
$\begingroup$

I have a finite set of objects $X$, whose power set is partially ordered by $\subseteq$.

  1. Consider all possible total orderings of the power set $\mathscr{P}(X)$ which are compatible with the partial order $\subseteq$ in the sense that $A \subsetneq B \Rightarrow A \prec B$. How many compatible total orders are there?

  2. Some orders $\prec$ have the special property that they can be concretely quantified by assigning numerical weights to each element in the set; then a subset has a smaller total weight than another subset if and only if the subsets are related by $\prec$.

    Specifically, this means that you can find a weight assignment function $f:\mathscr{P}(X)\rightarrow \mathbb{R}^+$ such that every subset's weight is the sum of its elements' weights: $$\forall S\subseteq X,\quad f(S) = \sum_{x\in S} f(\{x\})$$ and the weight respects order in that $f(S) < f(T) \iff S \prec T.$

    How many quantifiable total orders are there? (For my applications, I'm interested in weight assignments where $f(S) = 0 \iff S = \varnothing$.)

$\endgroup$
  • $\begingroup$ What do you mean "compatible with"? $\endgroup$ – AJY Aug 5 '17 at 21:05
  • $\begingroup$ I guess $A\subsetneq B \implies A \prec B$. $\endgroup$ – Paolo Leonetti Aug 5 '17 at 21:07
  • $\begingroup$ A possibly-interesting "between" class of orders are the total orders where if $S\prec T$ then $T^{c}\prec S^{c}$. $\endgroup$ – Thomas Andrews Aug 5 '17 at 21:12
  • $\begingroup$ @PaoloLeonetti Yes, that's right. I've adjusted my question to clarify that. $\endgroup$ – user326210 Aug 6 '17 at 0:10
  • 2
    $\begingroup$ The answer to the first question is OEIS sequence A046873, "Number of total orders extending inclusion on $P(\{1,\dots,n\})$." $\endgroup$ – bof Aug 6 '17 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.