Minimum set of component wise ordering relation

Question

$\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.

Answer 1

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.)

Answer 2

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$.