-8
$\begingroup$

Let $\mathcal{A}$ be the set of all arithmetic progressions in $\mathbb{N}$ i.e

\begin{align*} \mathcal{A} = \{a + b\mathbb{N} : a,b\in\mathbb{N}, b\neq 0\}. \end{align*}

Does there exist a set $X \subseteq \mathbb{N}$ such that for each $A \in \mathcal{A}$, both $A \cap X$ and $A \cap X^c$ are infinite?

$\endgroup$
0

2 Answers 2

Reset to default
7
$\begingroup$

If $A$ is an infinite subset of $\mathbb N$, a random subset $X\subseteq\mathbb N$ will satisfy the condition $|A\cap X|=|A\cap X^c|=\aleph_0$ with probability one. Inasmuch as there are only countably many arithmetic progressions, a random subset will satisfy that condition for all of them with probability one.

Alternatively, just define $X$ to be the set of all natural numbers with an odd number of digits.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice, even simpler than my example. $\endgroup$
    – Gerry Myerson
    Commented Feb 3 at 11:37
5
$\begingroup$

There are only a countable infinity of arithmetic progressions, so list them as $A_1,A_2,\dotsc$. Then write out a list in which each $A_i$ occurs infnitely many times, e.g., $A_1,A_1,A_2,A_1,A_2,A_3,A_1,A_2,A_3,A_4,\dotsc$, Rename this new list as $B_1,B_2,B_3,\dotsc$. Now go through the $B_i$, taking one previously unused term from each to put into $X$, and one previously unused term from each to put into the complement of $X$. When you're done, $X$ will have infinitely many terms from each AP, and so will its complement. There may be some naturals left over, not having been selected for either $X$ or its complement; put them wherever you like, it makes no difference.

EDIT: As user @bof notes, the question has to do with set theory, not arithmetic. But I reckon we can bring it back to arithmetic by letting $X$ contain the even numbers between $1$ and $10$, the odd numbers between $11$ and $100$, the evens between $101$ and $1000$, odds between $1001$ and $10000$, and so on.

Improve this answer
$\endgroup$
1
  • $\begingroup$ And of course this has nothing to do with arithmetic, it's just basic set theory. More generally, if $\kappa$ is an infinite cardinal, and if $|I|=\kappa$ and $|A_i|=\kappa$ for each $i\in I$, then there are pairwise disjoint sets $B_i\subseteq A_i$ ($i\in I$) with $|B_i|=\kappa$, and there are $\kappa$ pairwise disjoint sets $X_\alpha$ ($\alpha\in\kappa)$ with $|X_\alpha\cap A_i|=|X_\alpha\cap B_i|=\kappa$ for all $\alpha\in\kappa$ and $i\in I$. $\endgroup$
    – bof
    Commented Feb 2 at 23:43

You must log in to answer this question.

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