Lexicographic order is a partial order on the the set of all partitions of the positive integer n.

Question

I think the above statement is false, if not then please give a hint to prove.I know majorization is a partially order.

Answer 1

I’m assuming that by partition of $n$ you mean a $k$-tuple $\langle p_1,\ldots,p_k\rangle$ of positive integers (for some $k\in\Bbb Z^+$) such that $p_1+\ldots+p_k=n$ and $p_1\ge\ldots\ge p_k$. Let $P_n$ be the set of all partitions of $n$.

Suppose that $p=\langle p_1,\ldots,p_k\rangle,q=\langle q_1,\ldots,q_\ell\rangle\in P_n$, and $p\ne q$. Without loss of generality we may assume that $k\le\ell$. If $p_i=q_i$ for $1\le i\le k$, then $k=\ell$ and $p=q$ (why?), so for $p\ne q$ we can define $j(p,q)=j(q,p)=\min\{i:p_i\ne q_i\}$.

Now define a relation $\preceq$ on $P_n$ by $p\preceq q$ if and only if either $p=q$, or $p_{j(p,q)}<q_{j(p,q)}$. Clearly $\preceq$ is reflexive. Suppose that $p\preceq q$ and $q\preceq p$. If $p\ne q$, then $p_{j(p,q)}<q_{j(p,q)}$ and $q_{j(p,q)}<p_{j(p,q)}$, which is absurd, so $p=q$, and $\preceq$ is antisymmetric.

Since $\preceq$ is the lexicographic order on $P_n$, all that remains is to show that $\preceq$ is transitive. I’ll leave that to you, since it uses the same kinds of ideas as what I’ve already done.

One final note: $\preceq$ is also total, so it’s not just a partial order: it’s a total (or linear) order. The second paragraph shows that if $p\ne q$, then $j(p,q)$ exists, and clearly either $p_{j(p,q)}<q_{j(p,q)}$, in which case $p\preceq q$, or $q_{j(p,q)}<p_{j(p,q)}$, in which case $q\preceq p$.

Answer 2

The above statement is true. The hint would be to simply reason by induction on $M\geq 1$. Let $X:=\{(x_1,...,x_k)|k\in\mathbb{N}\text{ and } x_1+...+x_k=n\}$. Then the induction statement would be if :

$$(x_1,...,x_k)\text{ and } (y_1,...,y_{k'})\text{ are in } X \text{ and } k,k'\leq M\text{ then either } $$

$$(x_1,...,x_k)\leq (y_1,...,y_{k'}) \text{ or } (y_1,...,y_{k'})\leq (x_1,...,x_k) $$