0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

10 partial orders on A

$\endgroup$
  • 2
    $\begingroup$ 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.) $\endgroup$ – Stefan Mesken Mar 5 '18 at 17:28
  • 1
    $\begingroup$ 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. $\endgroup$ – amrsa Mar 5 '18 at 17:44
  • $\begingroup$ @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. $\endgroup$ – Stefan Mesken Mar 5 '18 at 17:46
  • $\begingroup$ @Ninja My answer contains a justification for why the empty set is not a partial order on any nonempty set. $\endgroup$ – Stefan Mesken Mar 5 '18 at 17:46
  • 2
    $\begingroup$ @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.) $\endgroup$ – Stefan Mesken Mar 5 '18 at 17:52
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.