Suppose we have a set $P$ (an infinite set), and we have a partition of $P$ into (finitely many) disjoint subsets $P_i$, so that $P = \cup_i P_i$, and $P_i \cap P_j = \emptyset$ for $i \neq j$.

Suppose now that we have a set of partial orderings of $P$, such that for each of the orderings, we know that they strictly order some of the partitions. I'm not sure if that is proper math-speak, but what I mean is, for example, for the first partial ordering given, it guarantees $a < b$ for all $a \in P_1$ and for all $b \in P_2$ (I will write this as $P_1 < P_2$). There may, for example, be another partial ordering given that guarantees $P_2 < P_1$.

My question is, given a finite set of $p_i \in P$ with a finite number of partitions $P_j$, as well as a finite set of partial orderings, is it possible to infer set membership of the $p_i$'s into the partitions ($P_j$'s)? If so, then what is required of the $p_i$ and the partial orderings? How many and which kinds of orderings need to be supplied?

Since I don't know the proper math terminology, I'm making this a wiki.


Your problem is a little unclear at the end. In particular, you need to spell out more clearly what the inputs to the question are. As written now, it seems to me that part of the initial data you're given are explicit elements $p_i\in P$. But then it seems that you should know right off the bat which partition $P_i$ each element is in.

Maybe the problem you're interested in is trying to determine set membership from a certain number of unspecified elements and the partial ordering on them induced by that on P. This question then has a similar feel to trying to give necessary conditions for a partially-ordered set to be order-embeddable in another.

Why not work out a simple non-trivial example to make your question more clear?


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.