What are some partial orders on the set $S=\{0,1\}^n$?

Question

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?

Answer 1

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".

Answer 2

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