A partial order is a binary relation which is reflexive, antisymmetric and transitive. (See Wikipedia Defn for more details.) Consider the set $S=\{ 0,1\}^n$. A partial order on this set can be described as follows. $\forall x,y \in S, x \preceq y $ iff $\forall i \in \{1,2,\ldots n\}, x_i \le y_i$. This relation is indeed reflexive, antisymmetric and transitive and hence a partial order. Another example of such relation could be $a \mid b$ i.e. a divides b if $a,b$ are thought of as integers converted from the Boolean strings. What are some other partial orders that one can think of on the set $S$ above?


2 Answers 2


In all of the following, take $x\le y$ if it there a strict inequality in the named quantity, or if $x=y$.

Cardinality of number of entries that are $1$'s. (Lower cardinality = lower rank. Possible more interesting for infinite $n$.)

$x_i\lt y_i$ in the first two coordinates.

Value of the dot product with a fixed vector.

Index of the first $1$.

Many of these are close to linear orders, but allow ties, which we convert here to "incomparable".

  1. Lexicographic ordering
  2. The reverse of the first one (since reverse of a partial order is also a partial order).
  3. Order on the basis of the number of zeroes ($x\preceq y$ iff $x=y$ or number of zeroes in $x$ is less than that in $y$).
  4. The same with the number of ones ;)
  5. Ordered on basis of a particular coordinate (for example, $x\preceq y$ iff $x=y$ or $x_i<y_i$ for a particular $i$).
  6. Since you're talking about binary strings converted to integers, any partial order on integers can be converted to a partial order on this set.
  7. An interesting one that I can think is: Given points can be seen as points on the corners of a cube in $n$ dimensional space. Take any fixed point $\vec c$ in that space, and order these points with respect to distance from $\vec c$.
  8. From a practical point of view, you can also order them on the basis of the number of sequences in OEIS in which they occur (assumed as numbers, taking $0001101$ as $1101$ for example).
  9. For every particular $p\in(0,1)$, suppose that there is a coin which flips head with probability $p$. You can flip that coin $n$ times and order the given points on the basis of probability of occurrence of that observation (taking $1$ as head and $0$ as tail).
  • $\begingroup$ Several of these, like 3, 4, and 5 are not partial orders since you can have $x\ne y$, $x\le y$, and $x\ge y$ simultaneously. That's ok for a preorder but not for a partial order. $\endgroup$
    – C Monsour
    Mar 31, 2021 at 23:06
  • $\begingroup$ @CMonsour, that can be appropriately managed (for example, relating every element to themeselves to make it reflexive, but taking strict inequality in other cases). $\endgroup$
    – Martund
    Apr 1, 2021 at 8:26
  • $\begingroup$ I'm aware that it can be (for example, see my answer), but you are answering a question for someone who is presumably not aware, so you probably shouldn't be giving a wrong answer. $\endgroup$
    – C Monsour
    Apr 1, 2021 at 10:54
  • $\begingroup$ @CMonsour, edited $\endgroup$
    – Martund
    Apr 1, 2021 at 14:39

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.