Return to Answer

For $k\ge2$, if we partition $\mathbb N$ into $k+1$ infinite sets $S_0,S_1,\dots,S_k$, then each $S_i$ is coinfinite, and every $k$-element subset of $\mathbb N$ is contained in the complement of some $S_i$.

This is best possible: for $k\ge2$, given $k$ nonempty proper subsets if $\mathbb N$, there is a $k$-element set which meets all of those sets and their complements. The proof is by induction.

For $k=2$, suppose $S_1$ and $S_2$ are nonempty proper subsets of $\mathbb N$. If neither is contained in the other, choose $x_1\in S_1\setminus S_2$ and $x_2\in S_2\setminus S_1$; if one is contained in the other, say $S_1\subseteq S_2$, choose $x_1\in S_1$ and $x_2\in\mathbb N\setminus S_2$. In either case the set $\{x_1,x_2\}$ meets each of the sets $S_1,S_2,\mathbb N\setminus S_1,\mathbb N\setminus S_2$.

For the induction step, let $S_1,\dots,S_k,S_{k+1}$ be nonempty proper subsets of $\mathbb N$, and let $F=\{x_1,\dots,x_k\}$ be a $k$-element set which meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k$. Choose $x_{k+1}\in\mathbb N$ so that $x_{k+1}\in S_{k+1}\iff x_1\notin S_{k+1}$. Then the set $F\cup\{x_{k+1}\}$ has at most $k+1$ elements and meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k+1$.

For $k\ge2$, if we partition $\mathbb N$ into $k+1$ infinite sets $S_0,S_1,\dots,S_k$, then each $S_i$ is coinfinite, and every $k$-element subset of $\mathbb N$ is contained in the complement of some $S_i$.

This is best possible: for $k\ge2$, given $k$ nonempty proper subsets of $\mathbb N$, there is a $k$-element set which meets all of those sets and their complements. The proof is by induction.

For $k=2$, suppose $S_1$ and $S_2$ are nonempty proper subsets of $\mathbb N$. If neither is contained in the other, choose $x_1\in S_1\setminus S_2$ and $x_2\in S_2\setminus S_1$; if one is contained in the other, say $S_1\subseteq S_2$, choose $x_1\in S_1$ and $x_2\in\mathbb N\setminus S_2$. In either case the set $\{x_1,x_2\}$ meets each of the sets $S_1,S_2,\mathbb N\setminus S_1,\mathbb N\setminus S_2$.

For the induction step, let $S_1,\dots,S_k,S_{k+1}$ be nonempty proper subsets of $\mathbb N$, and let $F=\{x_1,\dots,x_k\}$ be a $k$-element set which meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k$. Choose $x_{k+1}\in\mathbb N$ so that $x_{k+1}\in S_{k+1}\iff x_1\notin S_{k+1}$. Then the set $F\cup\{x_{k+1}\}$ has at most $k+1$ elements and meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k+1$.

For $k\ge2$, if we partition $\mathbb N$ into $k+1$ infinite sets $S_0,S_1,\dots,S_k$, then each $S_i$ is coinfinite, and every $k$-element subset of $\mathbb N$ is contained in the complement of some $S_i$.

This is best possible: for $k\ge2$, given $k$ nonempty proper subsets if $\mathbb N$, there is a $k$-element set which meets all of those sets and their complements. The proof is by induction.

For $k=2$, suppose $S_1$ and $S_2$ are nonempty proper subsets of $\mathbb N$. If neither is contained in the other, choose $x_1\in S_1\setminus S_2$ and $x_2\in S_2\setminus S_1$; if one is contained in the other, say $S_1\subseteq S_2$, choose $x_1\in S_1$ and $x_2\in\mathbb N\setminus S_2$. In either case the set $\{x_1,x_2\}$ meets each of the sets $S_1,S_2,\mathbb N\setminus S_1,\mathbb N\setminus S_2$.

For the induction step, let $S_1,\dots,S_k,S_{k+1}$ be nonempty proper subsets of $\mathbb N$, and let $F=\{x_1,\dots,x_k\}$ be a $k$-element set which meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k$. Choose $x_{k+1}\in\mathbb N$ so that $x_{k+1}\in S_{k+1}\iff x_1\notin S_{k+1}$. Then the set $F\cup\{x_{k+1}\}$ has at most $k+1$ elements meets $S_i$ and $\mathbb N\setminus S_i$ fo andr $1\le i\le k+1$.

For $k\ge2$, if we partition $\mathbb N$ into $k+1$ infinite sets $S_0,S_1,\dots,S_k$, then each $S_i$ is coinfinite, and every $k$-element subset of $\mathbb N$ is contained in the complement of some $S_i$.

This is best possible: for $k\ge2$, given $k$ nonempty proper subsets if $\mathbb N$, there is a $k$-element set which meets all of those sets and their complements. The proof is by induction.

For $k=2$, suppose $S_1$ and $S_2$ are nonempty proper subsets of $\mathbb N$. If neither is contained in the other, choose $x_1\in S_1\setminus S_2$ and $x_2\in S_2\setminus S_1$; if one is contained in the other, say $S_1\subseteq S_2$, choose $x_1\in S_1$ and $x_2\in\mathbb N\setminus S_2$. In either case the set $\{x_1,x_2\}$ meets each of the sets $S_1,S_2,\mathbb N\setminus S_1,\mathbb N\setminus S_2$.

For the induction step, let $S_1,\dots,S_k,S_{k+1}$ be nonempty proper subsets of $\mathbb N$, and let $F=\{x_1,\dots,x_k\}$ be a $k$-element set which meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k$. Choose $x_{k+1}\in\mathbb N$ so that $x_{k+1}\in S_{k+1}\iff x_1\notin S_{k+1}$. Then the set $F\cup\{x_{k+1}\}$ has at most $k+1$ elements and meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k+1$.

For $k\ge2$, if we partition $\mathbb N$ into $k+1$ infinite sets $S_0,S_1,\dots,S_k$, then each $S_i$ is cofinite, and every $k$-element subset of $\mathbb N$ is contained in the complement of some $S_i$.

This is best possible: for $k\ge2$, given $k$ nonempty proper subsets if $\mathbb N$, there is a $k$-element set which meets all of those sets and their complements. The proof is by induction.

For $k=2$, suppose $S_1$ and $S_2$ are nonempty proper subsets of $\mathbb N$. If neither is contained in the other, choose $x_1\in S_1\setminus S_2$ and $x_2\in S_2\setminus S_1$; if one is contained in the other, say $S_1\subseteq S_2$, choose $x_1\in S_1$ and $x_2\in\mathbb N\setminus S_2$. In either case the set $\{x_1,x_2\}$ meets each of the sets $S_1,S_2,\mathbb N\setminus S_1,\mathbb N\setminus S_2$.

For the induction step, let $S_1,\dots,S_k,S_{k+1}$ be nonempty proper subsets of $\mathbb N$, and let $F=\{x_1,\dots,x_k\}$ be a $k$-element set which meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k$. Choose $x_{k+1}\in\mathbb N$ so that $x_{k+1}\in S_{k+1}\iff x_1\notin S_{k+1}$. Then $F\cup\{x_{k+1}\}$ is a $(k+1)$-element set which meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k+1$.

For $k\ge2$, if we partition $\mathbb N$ into $k+1$ infinite sets $S_0,S_1,\dots,S_k$, then each $S_i$ is coinfinite, and every $k$-element subset of $\mathbb N$ is contained in the complement of some $S_i$.

This is best possible: for $k\ge2$, given $k$ nonempty proper subsets if $\mathbb N$, there is a $k$-element set which meets all of those sets and their complements. The proof is by induction.

For $k=2$, suppose $S_1$ and $S_2$ are nonempty proper subsets of $\mathbb N$. If neither is contained in the other, choose $x_1\in S_1\setminus S_2$ and $x_2\in S_2\setminus S_1$; if one is contained in the other, say $S_1\subseteq S_2$, choose $x_1\in S_1$ and $x_2\in\mathbb N\setminus S_2$. In either case the set $\{x_1,x_2\}$ meets each of the sets $S_1,S_2,\mathbb N\setminus S_1,\mathbb N\setminus S_2$.

For the induction step, let $S_1,\dots,S_k,S_{k+1}$ be nonempty proper subsets of $\mathbb N$, and let $F=\{x_1,\dots,x_k\}$ be a $k$-element set which meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k$. Choose $x_{k+1}\in\mathbb N$ so that $x_{k+1}\in S_{k+1}\iff x_1\notin S_{k+1}$. Then the set $F\cup\{x_{k+1}\}$ has at most $k+1$ elements meets $S_i$ and $\mathbb N\setminus S_i$ fo andr $1\le i\le k+1$.