If $R$ is a partial order on $[n],$ prove that $|R| \le n(n+1) / 2$

Question

I have to prove that:

if $R$ is partial order on $[n],$ then $|R| \le n(n+1) / 2.$

Because a partial order is reflexive, antisymmetric and transitive we know that:

• for all $a$ in $[n],$ $(a,a)$ belong to $R,$
• if $(a,b)\in R$ and $(b,a)\in R,$ then $a=b,$
• if $(a,b)\in R$ and $(b,c)\in R,$ then $(a,c)\in R,$

but I don't know what to do next. Thanks for help.

Answer 1

Let $R$ be an antisymmetric relation on $[n]=\{1,2,\dots,n\}.$ (Reflexivity and transitivity will not be used.)

For each of the $\frac{n(n-1)}2$ ordered pairs $(i,j)\in[n]^2$ such that $i<j,$ at most one of the pairs $(i,j)$ or $(j,i)$ belongs to $R.$

For each of the $n$ elements $i\in[n],$ the pair $(i,i)$ belongs to $R$ or not.

Therefore, $$|R|\le\frac{n(n-1)}2+n=\frac{n(n+1)}2.$$