Infinite sets and arithmetic progressions If $S\subset\mathbb N$ is infinite, prove that we can find $p,q\in\mathbb N$, such that either whenever $ n\equiv p\pmod q$, we have$$
n\in S
$$
or else whenever  $n\equiv p\pmod q$, we have $$
n\notin S.
$$
 A: This is false. Enumerate all pairs $(p,q)$ as $pair_1,pair_2,\dots$ Now build two disjoint sets $S$ and $T$ by stages. First, set $S_0=T_0=\emptyset$. Our construction will ensure that $S_0\subsetneq S_1\subsetneq S_2\subsetneq\dots$ and similarly with the $T_i$, while maintaining that $S_i, T_i$ are disjoint. At the end, we set $S=\bigcup_n S_n$ and $T=\bigcup_n T_n$ and note that, by construction, these sets are indeed disjoint. At stage $k$ we have $S_k,T_k$, the constructed sets so far, and consider $pair_k=(a,b)$. Find $n\ne m$, both large enough (larger than all elements in $S_k\cup T_k$) and congruent to $a$ mod $b$. Set $S_{k+1}=S_k\cup\{n\}$ and $T_{k+1}=T_k\cup\{m\}$.
The construction ensures that, for any $p,q$, both $S$ and its complement (that necessarily contains $T$) have elements congruent to $p$ mod $q$. This means that $S$ does not contain all these elements, but does not miss all of them either.
(By ensuring for instance that each pair is listed infinitely often, we may also arrange that both $S$ and $T$ meet each such congruence class in an infinite set.)
