Prove that a partial ordered set $\mathbb{N}\times\mathbb{N}$ does not contain infinite subset whose any two elements are noncompareable

Question

A. Shen - Basic Set Theory, problem 83:

Prove that a partially ordered set $\mathbb{N}\times\mathbb{N}$ (with componentwise ordering) does not contain an infinite subset $X$ such that any two distinct elements of $X$ are noncomparable.

I construct a binary relation $\mathcal{R}$ on $\mathbb{N}$ as follows:

• $x\mathcal{R}y$, for all $x,y \in \mathbb{N}$, that $x$ is odd, and $y$ is even, or $x=y$. Example: $1\mathcal{R}4$, $2\mathcal{R}2$.
• If $x,y\in\mathbb{N}$ are odd, then $x\mathcal{R}y$ if $x>y$. Example: $3\mathcal{R}1$.
• If $x,y\in\mathbb{N}$ are even, then $x\mathcal{R}y$ if $x<y$. Example: $2\mathcal{R}4$.

I verified that $\mathcal{R}$ is partial order, satisfies reflexivity, antisymmetry, and transitivity porperties.

By description of "componentwise ordering" in the book, two elements $\left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right)$ of $\mathbb{N}\times \mathbb{N}$ are not comparable if $x_{1}\mathcal{R}x_{2}$ and $y_{2}\mathcal{R}y_{1}$.

By that, $X=\left\{ \left(2,1\right),\left(4,3\right),\left(6,5\right),\dots\right\}$ is infinite subset of $\mathbb{N}\times\mathbb{N}$ and any two distinct elements of $X$ are not comparable.

I've seen a similar question, which has suggestion. I afraid that my example is wrong, but I'm not sure.

Answer 1

Notice that one of the sets $A=\{(x,y)\in{}X: x>a\}$ or $B=\{(x,y)\in{}X: y>b\}$ is infinite for a fixed $(a,b)\in{}X$. Suppose it is $A$ then for every $(x,y)\in{}A$ we have $y<b$ otherwise $(x,y)>(a,b)$. By the pigeonhole principle there exist thus $(x_1,y_1),(x_2,y_2)\in{}A: y_1=y_2$ and since they are different elements either $x_1>x_2$ or $x_2>x_1$ which completes the proof.

Note that for any $\mathbb{N}^k$ by induction there is a similar proof: if $u=(x_1,...,x_k)\in{}X$ consider all of the possible $2^n-2$ subsets $A_i: \forall{}v\in{}A_i$ neither $u>v$ or $v>u$. One of these sets is infinite since $\cup{}A_i\cup\{u\}=X$ .Then at least one of the coordinates of $A_i$ is $a_j<x_j$ and by the pigeonhole principle there exist infinitely many elements of $A_i$ with $a_j=c$ for some fixed $c$. Then the set of tuples $(a_1,...,a_{j-1},a_{j+1},...,a_k)$ is a subset of $\mathbb{N}^{k-1}$ and thus contains two comparable elements, plugging in $a_j$ we get the desired result.

Answer 2

Let X = { $(x_j,y_j)$ | n in N } be a denumerable antichain.
Let (a,b) be the element in X with the smallest $x_j.$

For all the other elements of X, a < $x_j, y_j$ < b.
Show that for those elements, $y_j = y_k$ implies j = k.
Thus there are infinitely many elements in X with $y_j$ < b,
an impossiblity.