## There are k! distinct lex, grlex, and grevlex orders on a polynomial ring in k indeterminates

Prove that there are $k!$ distinct lex orders on $F[x_1,\ldots,x_k]$. Show similarly that there are $k!$ distinct grlex and grevlex orders.

Each lex (and grlex and grevlex) order on $F[x_1,\ldots,x_k]$ is (by definition) induced by a linear order of the indeterminates $x_1, \ldots, x_k$. Each linear order of $[1,k]$ certainly corresponds to a permutation, so that there are at most $|S_k| = k!$ distinct lex (and grlex and grevlex) orders. It remains to be shown that distinct permutations $\tau \in S_k$ induce distinct monomial orders.

Suppose $>_1$ and $>_2$ are distinct linear orders of $[1,k]$. That is, there exist $a,b \in [1,k]$ such that $x_a >_1 x_b$ and $x_b >_2 x_a$. We immediately see that the lex, grlex, and grevlex orders induced by $>_1$ and $>_2$ are distinct, as those orders coincide with $>_1$ and $>_2$ on the set $\{x_1, \ldots, x_k\}$.