# How many total orders consistent with a partial order?

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

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