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.

  • 3
    $\begingroup$ The problem doesn't seem to be asking you to make up your own relation. Certainly there exist relations where you can find infinite pairwise noncomparable sets (just declare everything noncomparable). I assume the relation is supposed to be that $(x_1,y_1) \ge (x_2,y_2)$ if $x_1 \ge y_1$ and $x_2 \ge y_2)$. $\endgroup$ – Carl May 24 '18 at 6:19
  • $\begingroup$ Thank you, I think you are right, the theorem mentioned in the suggestion of other question also using "normal" $\leq$ relation. $\endgroup$ – duqu May 24 '18 at 6:36

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.

  • $\begingroup$ Thanks for the solution, but I do not vote your answer yet. I just asked for verifying my confusion. $\endgroup$ – duqu May 24 '18 at 7:15
  • $\begingroup$ It’s ok I’ll just leave the answer there for future reference $\endgroup$ – Μάρκος Καραμέρης May 24 '18 at 7:20

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.


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.