Question 37
Let $\mathbb{N}^2$ denote the set of ordered pairs of positive integers. A finite subset $S$ of $\mathbb{N}^2$ is *stable* if whenever $(x, y)$ is in $S$, then so are all points $(x', y')$ of $\mathbb{N}^2$ with both $x' \le x$ and $y' \le y$.
Prove that if $S$ is a stable set, then among all stable subsets of $S$ (including the empty set and $S$ itself), at least half of them have an even number of elements.
Prove that if $S$ is a stable set, then among all stable subsets of $S$ (including the empty set and $S$ itself), at least half of them have an even number of elements.