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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .