Finitely many minimal elements

Question

I've been working on various exercises to get a better understanding of some topics for an upcoming course.

I have a relation $R$ on $\mathbb{N} \times \mathbb{N}$ defined as follows: $(x_0, x_1) R (y_0, y_1)$ if and only if $x_0 \leq y_0$ and $x_1 \leq y_1$. The exercise asks to show that $R$ is well-founded on $\mathbb{N}$ but is not a total order. I was able to show this successfully.

Then, it asks to show that every non-empty subset $X \subset \mathbb{N} \times \mathbb{N}$ contains only finitely many $R$-minimal elements, and, for each $n \in \mathbb{N}$, there is such an $X$ with exactly $n$ $R$-minimal elements. In a relation $R$, and a set $X$, $y \in X$ is said to be $R$-minimal in $X$ if and only if

$$ \neg \exists z ( z \in X \wedge zRy)$$

It seems like it should be very obvious to show that there are only finitely many $R$-minimal elements, but I can't formally come up with a valid argument. If a non-empty subset contained infinitely many $R$-minimal subsets, I'm thinking it would somehow lead to a contradiction.

Any help would be greatly appreciated.

Answer 1

For each $k\in\mathbb N$, there is at most one minimal element of $X$ in $\{k\}\times \mathbb N$ and at most one in $\mathbb N\times\{k\}$. If $(n,m)$ is any minimal element of $X$, there can be at most $n+m-2$ other minimal elements, namely at most one in each $\{k\}\times \mathbb N$ for $k<n$ and at most one in each $\mathbb N\times\{k\}$ with $k<m$.

Answer 2

If $(x_0,y_0)$ and $(x_1,y_1)$ are incomparable, it's because either:

1. $x_0>x_1$ and $y_0<y_1$, or
2. $x_0<x_1$ and $y_0>y_1$.

So if $X$ is an infinite subset of mutually incomparable elements, you can pick a sequence $(x_n,y_n)$, using choice, such that either $(1)$ or $(2)$ holds for all $(x_n,y_n),(x_{n+1},y_{n+1})$, then we would have that $x_0>x_1>x_2>\cdots$ or $y_0>y_1>y_2>\cdots$.