Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.