MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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