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

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?

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 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).
• 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. Mar 31, 2021 at 23:06
• @CMonsour, that can be appropriately managed (for example, relating every element to themeselves to make it reflexive, but taking strict inequality in other cases). Apr 1, 2021 at 8:26
• 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. Apr 1, 2021 at 10:54
• @CMonsour, edited Apr 1, 2021 at 14:39