# Minimum set of component wise ordering relation

$\leq_{cw}$ is the partial component wise ordering relation. Given a set $M \subset \mathbb{N}_0^n$ we define $N = \min_{cw}(M)$ with $v \in N$ iff if $u \in M$ and $u \leq_{cw} v$ then $u = v$. I want to prove that $N$ is finite.

The intuition is quite clear to me from a combinatorical point of view. But I don't know how to formally proof that. There is hint in the exercise to first prove that $\mathbb{N}_0^n$ is countable. I proved that but I do not see a connection.

-
So $\langle a_1,\ldots,a_k\rangle\leq_{cw}\langle b_1,\ldots,b_k\rangle$ if and only if for all $i\in\{1,\ldots,k\}$ we have $a_i\leq b_i$? – Asaf Karagila May 2 '12 at 19:17
Yes, exactly like this. – joachim May 2 '12 at 19:18
Do you mean "if $u \in M$..." in the definition of $N = \min_{cw}(M)$ – Desiato May 2 '12 at 22:43
Yes, I do. Sorry! – joachim May 2 '12 at 22:45

Let us prove the somewhat stronger claim:

Theorem: Every anti-chain in $\langle\mathbb N^n,\leq_{cw}\rangle$ is finite.

Before that we will prove two small Lemma's which will make the proof of the above claim much simpler.

Lemma I: Suppose $x\in\mathbb N^n$, then $\{y\in\mathbb N^n\mid y\leq_{cw} x\}$ is finite.

Proof: Note that $y\leq_{cw} x$ if and only if for all $i<n$ we have $y(i)\leq x(i)$. This means that there are at most $\max\{x(i)\mid i<n\}\cdot n$ many possible vectors with this property, as wanted. $\square$

Lemma II: Suppose $x_1,\ldots x_k\in\mathbb N^n$ then there is $y\in\mathbb N^n$ such that for all $i\leq k$, $x_i\leq_{cw} y$.

Proof: Let $y(i)=\max\{x_j(i)\mid j=1,\ldots,k\}$. It is clear that $y$ is as wanted. $\square$

Finally we prove the theorem:

Proof: Suppose $M\subseteq\mathbb N^n$ is an infinite set, we will find two elements comparable. Let $x_i\in M$ be such that the $i$-th coordinate of $x_i$ is minimal in $M$, now let $x\in\mathbb N^n$ be as described in Lemma II.

Since $T=\{y\in\mathbb N^n\mid y\leq_{cw} x\}$ is finite, we have that $M\setminus T$ is infinite therefore it contains some $y$, but $y$ is necessarily larger than all $x_i$'s we have constructed therefore we have at least two elements comparable in $M$ (I am saying at least two because it is possible that the $x_i$'s are all the same). $\square$

Corollary: If $M\subseteq\mathbb N^n$ is non-empty then $\min M$ is finite.

Proof: Using the theorem above it is enough to show that this set forms an anti-chain, which is immediate from the definition of $\min M$. $\square$

(Do note, that the Corollary is equivalent to the Theorem. If we assume the Corollary, take $M$ to be an anti-chain then $M=\min M$, and therefore it is finite.)

-

The result can be proved by induction on $n$. It's certainly true for $n=1$. If it's not true for all $n$, let $m$ be minimal such that it's not true for $m$. Then there is some $M\subseteq\Bbb N_0^m$ that has an infinite set $\{\langle a_k(1),\dots,a_k(m)\rangle:k\in\Bbb N_0\}$ of minimal elements.

Suppose that the sequence $\langle a_k(1):k\in\Bbb N_0\rangle$ has an infinite constant subsequence $\langle a_{k(i)}(1):i\in\Bbb N_0\rangle$. Then $\{\langle a_{k(i)}(2),\dots,a_{k(i)}(n)\rangle:i\in\Bbb N_0\}$ is an subset of $\Bbb N_0^{m-1}$, all of whose elements are minimal, contradicting the choice of $m$. It follows easily that $\langle a_k(1):k\in\Bbb N_0\rangle$ has a strictly increasing infinite subsequence $\langle a_{k(i)}(1):i\in\Bbb N_0\rangle$. Thus, we can replace $\{\langle a_k(1),\dots,a_k(m)\rangle:k\in\Bbb N_0\}$ by its infinite subset $\{\langle a_{k(i)}(1),\dots,a_{k(i)}(m)\rangle:i\in\Bbb N_0\}$, and we might therefore just as well assume that $\langle a_k(1):k\in\Bbb N_0\rangle$ is strictly increasing to begin with.

By repeating this argument on the other coordinates, we may assume that $\langle a_k(i):k\in\Bbb N_0\rangle$ is strictly increasing for $i=1,\dots,m$. But then $$\big\langle a_k(1),\dots,a_k(m)\big\rangle <_{cw}\big\langle a_{k+1}(1),\dots,a_{k+1}(m)\big\rangle$$ for every $k\in\Bbb N_0$, which very badly violates the choice of $\{\langle a_k(1),\dots,a_k(m)\rangle:k\in\Bbb N_0\}$. This contradiction establishes the desired result.

Added: I finally managed to track down a vagrant memory: this result is sometimes known as Dickson's lemma. It's a special case of the more general result that if $\langle Q,\le\rangle$ is a well-quasi-order, then so is $\langle Q^n,\le_{cw}\rangle$ for any positive integer $n$.

-

Let $R = \mathbb{Z}[x_1,\cdots,x_n]$ be the polynomial ring of $n$ variables over the ring of integers. We denote by $x^a$ the monomial $x_1^{a_1}\cdots x_n^{a_n}$ in $R$ for $a \in \mathbb{N}_0^n$. We identify $a$ with $x^a$. Let $I$ be the ideal of $R$ generated by $M$. By the Hilbert's Basis Theorem, there exists a finite subset $B$ of $M$ such that $I$ is generated by $B$. Let $a \in M$. Then $x^a = f_1x^{b_1} + \cdots + f_m x^{b_m}$, where $f_i \in R, b_i \in B$ for $i = 1,\cdots m$. Since $x^a$ must appear in the right-hand side, $x^a$ must be divisible by $x^{b_i}$ for some $i$. Hence $a \geq_{cw} b_i$. Hence min$(M) \subset B$.

-