# How many partial orders can be defined on $\varnothing$ and a finite set?

Let $A$ be a set. I want to count the number of partial orders on $A$.
I found out that there is a relation called empty relation and I am not sure whether it comes from $0$-ary map.

Anyway, my first question is that if $A=\varnothing$, how many partial orders can be defined on $A$.

-My idea is that there is only one relation, in particular it is a partial order, namely $\varnothing$- relation.

My second question is that what happens when $A=\{a_1,\dots,a_k\}$, how can we count the number of partial orders on it?

-My idea is that it is at least $1$, the empty relation. I know that it has to be less than or equal to $|A| \times |A|$-many.

If $A = \emptyset$ then the empty relation is the only partial order on $A$.

Furthermore, if $A \neq \emptyset$, then the empty relation is not a partial order on $A$ since it is not reflexive.

Finally, it is not true that there are at most $|A| \times |A|$ many partial orders on $A$. The smallest counterexample (ignoring $A = \emptyset$) occurs if $A$ has $3$ elements. Here is a diagram listing $10$ partial orders on $A = \{1,2,3\}$ -- there are more than $10$.

• OEIS has the first couple of terms of the sequence you are looking for. It's A001035 and no closed form seems to be known.(? Don't quote me on that -- I'm not very experienced with OEIS and may simply missinterpret their entry.) – Stefan Mesken Mar 5 '18 at 17:28
• I suppose your diagrams are "kind of" labelled by the horizontal position of the nodes; otherwise the last three ones would be isomorphic. Considering labelled posets, we have that $n!$ total orderings in a $n$-element set, which is more than $n^2$ if $n \geq 3$ and provide a simpler justification. – amrsa Mar 5 '18 at 17:44
• @amrsa Yes, the elements are represented by their horizontal position, the order by the relative vertical position restricted to those that are connected by a path. I haven't looked up the formal definition but I'm pretty sure this is just some variation of the Hasse diagram for posets. – Stefan Mesken Mar 5 '18 at 17:46
• @Ninja My answer contains a justification for why the empty set is not a partial order on any nonempty set. – Stefan Mesken Mar 5 '18 at 17:46
• @Ninja Yes, it's a total order as well. To see reflexitivity: We have to show that $\forall x \in \emptyset \colon (x,x,) \in \emptyset$ is true. Since there are no $x \in \emptyset$, this is trivially the case. (There is no $x \in \emptyset$ such that $\neg (x,x) \in \emptyset$, since there is no $x \in \emptyset$ period.) – Stefan Mesken Mar 5 '18 at 17:52

A partial order on $A$ is strictly speaking a certain sort of special subset of $A\times A$ satisfying some rules. In any case, how many elements are there in $\emptyset \times \emptyset$... this should imply how many partial relations can be defined.