One form of Dickson's Lemma states: For every infinite set of $n$-tuples of natural numbers, there exist two tuples $(a_1,\ldots,a_n),(b_1,\ldots,b_n)$ such that $a_i\leq b_i$ for all $i$.

I've tried to prove it by induction on $n$. The case $n=1$ is clear. Assume the result for $n-1$.

Suppose there exists $x$ such that the $n$-th coordinate equals $x$ for infinitely many tuples. Then the inductive hypothesis applies.

So, assume that for any $x$, there are only finitely many tuples with last coordinate $x$. So we may choose an infinite list $(a_{1,1},\ldots,a_{1,n}), (a_{2,1},\ldots,a_{2,n}),\ldots$ such that $a_{1,n}<a_{2,n}<\cdots$.

If we can find $i<j$ such that $a_{i,k}\leq a_{j,k}$ for $k=1,\ldots,n-1$, we'll be done. How can we find them?


You are almost there, you need only to repeat this for all the coordinates (note that this would fail if your tuples were of infinite size).

As you have observed, any infinite sequence of natural numbers $(a_n)_{n \in \mathbb N} \subseteq \mathbb{N}$ contains an infinite non-decreasing subsequence, in particular, either there is an element $k \in \mathbb{N}$ that happens infinitely many times, or there is an infinite increasing subsequence.

Let $F$ be any function $F : \mathbb{N}^\mathbb{N} \to \mathbb{N}^\mathbb{N}$ that extracts indices of some subsequence with the aforementioned property, that is,

$$F\Big((a_k)_{k \in \mathbb{N}}\Big) \in \Big\{ (i_k)_{k \in \mathbb{N}} \subseteq \mathbb{N} \ \Big|\ i_k \text{ is increasing in }k \land a_{i_k} \text{ is non-decreasing in }k \Big\}.$$

That being set, let's make your infinite set $S \subseteq \mathbb{N}^n$ of tuples into an infinite sequence $S^0$ of tuples and then let $S^i$ be a subsequence of $S^{i-1}$ such that its $i$-th coordinate is non-decreasing

$$S^{i}_k = S^{i-1}_{F(\pi_i \circ S^{i-1})_k}.$$

Finally, any two tuples of $S^n$ would give you what you want.

I hope this helps $\ddot\smile$


You can show the lemma is equivalent to the statement that any infinite subset of $n$-tuples has an infinite increasing sequence. To induct from $n-1$ to $n$, start with your infinite set $S$ of $n$-tuples and generate $S'$ by only considering the first $n-1$ entries.If $S'$ is finite, then some $(n-1)$-tuple in $S'$ shows up in $S$ with an infinite number of last values, and you can pick an increasing sequence from those. Otherwise $S'$ is infinite and has a sequence $a_1' < a_2' < a_3' $... Then add back the last entry (picking one) of $a_k'$ to get $a_k$ as values in $S$. Consider those last values. If there's a finite number of them, then for some value there's an infinite number of $a_k$, and they form an infinite increasing sequence. Otherwise, starting with $a_1$ at some point there will be an $a_j$ whose last value is larger, then $a_1' < a_j'$ implies $a_1 < a_j$. Iterating that process gets an infinite increasing sequence in $S$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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