0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Don't replace the question with some "stupid" placeholder text if you can't delete it. It's just confusing... $\endgroup$ – skyking Jul 6 '16 at 10:37
  • $\begingroup$ 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? $\endgroup$ – CiaPan Jul 7 '16 at 9:09
  • $\begingroup$ @bof: I was wrong, sorry. $\endgroup$ – Tom Jul 8 '16 at 15:06
2
$\begingroup$

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

More generally speaking, my advice would be to focus less on formal rigour and more on content.

$\endgroup$

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.