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

630 Views Asked by At

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.

2

There are 2 best solutions below

9
On BEST ANSWER

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

0
On

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.