-2
$\begingroup$

We say a set $A\subseteq\mathbb{Z}$ is arithmetical if there are integers $a>0,b\geq 0$ such that $A=\{ax+b:x\in\mathbb{Z}\}$.

Is there $S\subseteq\mathbb{Z}$ such that $$S\cap A\neq\varnothing \neq (\mathbb{Z}\setminus S)\cap A$$ for every arithmetical set $A\subseteq\mathbb{Z}$?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
5
$\begingroup$

Yes. Enumerate all arithmetic sets $A_1, A_2, \ldots$. Choose $n_k\in A_k$ with $|n_k|>2^k$. The set $\{n_1, n_2, \ldots\}$ intersects any arithmetic set by construction, but it has zero density, thus does not contain a whole arithmetic set.

Actually you may construct such $S$ for each infinite sequence $A_1, A_2, \ldots$ of infinite sets: on $k$-th step choose $n_k\in A_k\cap S$ and $m_k\in A_k\setminus S$ so that $n_1, m_1, n_2, m_2, \ldots$ remain distinct.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ If $\kappa$ is an infinite cardinal number, and if $H$ is a hypergraph with at most $\kappa$ edges, and each edge contains at least $\kappa$ vertices, then $H$ is $2$-colorable. I'm surprised this hasn't come up yet, among all these questions about chromatic numbers of hypergraphs. $\endgroup$
    – bof
    Commented Dec 31, 2020 at 10:02
  • 1
    $\begingroup$ @bof Not quite the statement you mention, but another question which exactly answers this problem has already been asked. $\endgroup$
    – Wojowu
    Commented Dec 31, 2020 at 18:39
7
$\begingroup$

Another construction that works is to take any set $S$ such that both $S$ and $\mathbb Z\setminus S$ contain intervals of arbitrary length.

Improve this answer
$\endgroup$
1
  • 11
    $\begingroup$ A simple example would be to let $S$ be the set of all positive integers. $\endgroup$
    – Gerry Myerson
    Commented Dec 31, 2020 at 11:40

Not the answer you're looking for? Browse other questions tagged .