# Proving that every set has a finite subset of smallest elements''.

Update: I would like to have this deleted but I'm behind a firewall which prevents from using most features -- including commenting. Reason for deleting: $c-x\in \Bbb N_0^n\setminus\{(0,0,\dots,0)\}$ does not hold true, so I need to rethink my argument. Update 2: CiaPan, that's right. I've been trying to think of a proof that there are finitely many corners. But it's elusive. Update 3: It's Dickson's lemma (https://en.wikipedia.org/wiki/Dickson%27s_lemma). I found a proof in von zur Gathen, Modern Computer Algebra, Thm 21.18, p. 576.

I've been working on the following problem for a few days and I finally have a solution. But I'm unsure whether my reasoning actually works. Could you have a look?

Problem: Consider the partial order $\leq_\pi$ on $\Bbb N^n$ (w/o zero) defined by $$a\leq_\pi b\Leftrightarrow \forall i.\, a_i\leq b_i$$ Prove that every any non-empty set $X\subset\Bbb N^n$ contains a finite set $Y\subseteq X$ s. t. $$\forall x\in X.\,\exists y\in Y.\, y\leq_\pi x$$

My solution'':

Definition: Let $X\subset\Bbb N^n$, then a corner of $X$ is a point $c$ s. t. $$\forall k\in\Bbb N_0^n\setminus\{(0,0,\dots,0)\}.\, c-k\notin X$$ We use the notations $$\mathrm{corner}(x,X)=[\forall k\in\Bbb N_0^n\setminus\{(0,0,\dots,0)\}.\, c-k\notin X]$$ (where $[\cdot]$ is the Iverson bracket) and $$\mathcal{C}_X=\{x\in X:\mathrm{corner}(x,X)=1\}$$

Lemma 1: Let $x\in X$, then there is a corner $c$ and a vector $k\in\Bbb N^n$ s. t. $$x=c+k$$ i. e. $c\leq_\pi x$.

Proof: Let $x\in X$ be fix. We'll prove that for some $k\in\Bbb N^n$, the vector $x-k$ is a corner. I. e. $$\exists k\in\Bbb N^n.\,\forall l\in\Bbb N_0^n\setminus\{(0,0,\dots,0)\}.\,x-k-l\notin X$$ Suppose that it isn't so, i. e. suppose that $$\forall k\in\Bbb N^n.\,\exists l\in\Bbb N_0^n\setminus\{(0,0,\dots,0)\}.\,x-k-l\in X$$ but then, by letting $k=x$, it would hold that $$\exists l\in\Bbb N_0^n\setminus\{(0,0,\dots,0)\}.\, -l\in X$$ which is nonsense.

Lemma 2: For any set $X$, the set of corners $\mathcal{C}_X$, is finite.

Proof: There must be some ball that contains all corners. In other words it must hold that \begin{align} \exists k\in\Bbb N^n.\,\forall|c-(1,1,\dots,1)|_2>|k-(1,1,\dots,1)|_2.\,\mathrm{corner}(c,X)=0\\ \text{(1)} \end{align} Suppose that it isn't so, i. e. suppose that $$\forall k\in\Bbb N^n.\,\exists|c-(1,1,\dots,1)|_2>|k-(1,1,\dots,1)|_2.\, \forall l\in\Bbb N_0^n\setminus\{(0,0,\dots,0)\}.\,c-l\notin X$$ Then since $X\subseteq\Bbb N^n$, we get $$\forall x\in X.\,\exists|c-(1,1,\dots,1)|_2>|x-(1,1,\dots,1)|_2.\, \forall l\in\Bbb N_0^n\setminus\{(0,0,\dots,0)\}.\,c-l\notin X$$ We note that $c\neq x$ and hence $c-x\in \Bbb N_0^n\setminus\{(0,0,\dots,0)\}$ and hence, by setting $l=c-x$, we get $$\forall x\in X.\,\exists|c-(1,1,\dots,1)|_2>|x-(1,1,\dots,1)|_2.\,c-(c-x)\notin X$$ but this implies $$\forall x\in X.\, x\notin X$$ which means that $X=\emptyset$, contrary to assumption. Let now $k$ be a vector as in (1), and set $R=|k-(1,1,\dots,1)|_2$, $S=\{l\in\Bbb N^n:|l-(1,1,\dots,1)|_2\leq R\}$, then $$\mathcal{C}_X\subseteq S$$ but $S$ is finite, so $\mathcal{C}_X$ must be finite.

Theorem: Every non-empty set $X\subset\Bbb N^n$ contains a finite set $Y\subseteq X$ s. t. $$\forall x\in X.\,\exists y\in Y.\, y\leq_\pi x$$

Proof: Lemma 1 yields that for every $x\in X$ there exist a corner $c\in\mathcal{C}_X$ s. t. $c\leq_\pi x$. By lemma 2, the set $\mathcal{C}_X$ is finite. We're done.

• Don't replace the question with some "stupid" placeholder text if you can't delete it. It's just confusing... – skyking Jul 6 '16 at 10:37
• Is $\Bbb N^n$ a set of $n$–term sequences of natural numbers? The $\leq_\pi$ relation seems to require sequences of equal lengths, so I suppose you mean a set of sequences of some arbitrary, but fixed length $n$. Is that right? – CiaPan Jul 7 '16 at 9:09
• @bof: I was wrong, sorry. – Tom Jul 8 '16 at 15:06

I didn't follow all of the proof of Lemma $2$, but from the rest of the proof it seems that you're equivocating on whether corners of $X$ need to be elements of $X$. You don't specify this in your definition of a corner, and the proof of Lemma $1$ only works if corners of $X$ need not be elements of $X$. (In fact the proof of Lemma $1$ is unnecessarily complicated and simply boils down to saying that the origin is always a corner, hence there exists at least one corner.) But if corners of $X$ need not be elements of $X$, the lemmata don't do what you want them to do in the proof of the theorem, since the elements of $Y$ do need to be elements of $X$.