On set with $n$ elements, number of equivalence relations is greater then the number of partial-order relations?

Question

On set with $n$ elements, number of equivalence relations is greater then the number of partial-order relations? Or the opposite? Transitive relations make it hard to count these numbers. Can anyone help?

Answer 1

The partial orders are more numerous than the equivalence relations. First, let's order the elements of the set. Indeed, without loss of generality, we'll make the set $S = \lbrace 1, 2, \ldots, n\rbrace$.

Recall that equivalence relations correspond to partitions, i.e. sets $\lbrace P_1, \ldots, P_k \rbrace$ such that $\bigcup_{i=1}^k P_k = S$, $P_i \neq \emptyset$ for all $i$, and $P_i \cap P_j \neq \emptyset \implies i = j$. Let's fix such a partition. Moreover, we can totally order the parts in the partition by forcing $P_i \le P_j \iff \min P_i \le \min P_j$.

Then, define a partial order on $S$ by $a \preceq b$ if and only if $a \in P_i$ and $b \in P_j$ such that $P_i \le P_j$. It's not difficult to show reflexivity, anti-symmetry, and transitivity of this relation. Basically, I'm constructing the partial order through its Hasse Diagram: the partitions form the layers of the diagram, and arrows pass freely up the diagram between the layers.

So, we have a method for constructing a partial order from an equivalence relation. This forms a function from the equivalence relations on $S$ to the partial orders on $S$. If we can show that such a function is injective, we are done; the equivalence relations are equinumerous with a subset of the partial orders.

Suppose we have two equivalence relations, with corresponding partitions $\lbrace P_1, \ldots, P_k \rbrace$ and $\lbrace Q_1, \ldots, Q_m\rbrace$, such that the above method produces the same equivalence relation. Note that, according to the preceding construction, $k$ and $m$ are both the size of the longest chain (totally ordered subset) of the poset, so $k = m$. Moreover, the parts of the partition correspond to the maximal anti-chains (sets that have no relationship between any two elements), so the partitions are the same.

Therefore, yes, the partial orders are more numerous than the equivalence relations.

Answer 2

The Wikipedia link here has the answer: https://en.wikipedia.org/wiki/Partially_ordered_set#Number_of_partial_orders

It appears that there are more partial orders than equivalence relations for n=2 through n=19. It also seems likely that this pattern continues, but as no distinct formulas are given for them, this is not guaranteed.