# Is it necessary to use AC to solve this problem ?

Dear All,

As a routine application of Zorn's Lemma, one can show that there is a subset $A$ of $\mathbb{R}$ such that $A$ contains no arithmetic progression of length 3 but for any $x\not \in A$, $A\cup \lbrace x\rbrace$ contains an arithmetic progression of length 3.

So there exists such a set (Using AC) but I failed to construct, or even prove the existence without AC, of such set which forced me to ask here if anybody can prove the existence without AC or Show that its existence is depended on AC !?

-
A good way to solve this would be to show that such $A$ must have "pathological" properties (i.e. non-measurable, or non-Baire property, or no perfect set property...) in which case it is consistent with the failure of choice that such sets do not exist. –  Asaf Karagila Jan 5 '13 at 14:43
Nice observation, Asaf. It seems the question is about sets $A \subset \mathbb{R}$ such that the subtraction operation $A \times A \to \mathbb{R}$ is injective (and about maximal such sets). What can one say about the subtraction operation on measurable sets and when it is injective? –  Todd Trimble Jan 5 '13 at 16:15
By a qualifying exam old chestnut, any measurable set of positive Lebesgue measure contains arithmetic progressions of arbitrary length. –  Anthony Quas Jan 5 '13 at 17:07
Todd, the subtraction operation isn't necessarily injective for such sets. For example, {1,2,10,11} doesn't contain arithmetic sequences of length three, and you can extend this to a maximal set, but there are two pairs with difference 1. –  Joel David Hamkins Jan 5 '13 at 17:20
Oops, yes of course you're right Joel -- sorry. –  Todd Trimble Jan 5 '13 at 17:56

I can't find the error in this argument, but everybody seems convinced (in the comments) that such a simply definable set with the desired property doesn't exist so there must be an error somewhere.

Let $A$ be the set of reals whose nonterminating base three expansion avoid the digit $1$. As usual, there is some hassle dealing with negative reals, so a more precise definition would be that $x \in A$ iff the nonterminating base three expansion of $2\cdot 3^k + x$ avoids the digit $1$ for all sufficiently large natural $k$. This definition makes it clear how to translate everything into the positive reals, where arithmetic is easier.

First let's check that $A$ contains no $3$-term arithmetic progression. Suppose towards a contradiction that it contains such a sequence $x < y < z$. For large $k$, look at the leftmost (most significant) digit where $2\cdot 3^k + x$ and $2\cdot 3^k + z$ differ; this is (eventually) independent of $k$. Moreover, since $x < z$, this digit must be $0$ in $2\cdot 3^k + x$ and $2$ in $2\cdot 3^k + z$. That means it must be $1$ in $2\cdot 3^k + y$ (since $y$ is the average of $x$ and $z$), contradicting the hypothesis that $y \in A$.

Now suppose that $x \not\in A$. By considering translations as above it is enough to argue in the case that $x$ is positive. Since $x$ is not in $A$, it has at least one digit which is $1$. Build distinct elements $y, z \in A$ simply by "un-averaging the $1$s," i.e., $y$ and $z$ agree with those digits of $x$ which are $0$ or $2$, and on those digits of $x$ which are $1$, make the corresponding digit of exactly one of $y,z$ equal to $0$ and the other equal to $2$. Note that if $x$ has infinitely many digits which are $1$, it's important to pick both $0$ and $2$ infinitely often for $y$ (and thus $z$) to avoid accidentally making a terminating base three expansion. Then by construction, $y, x, z$ forms an arithmetic progression in $A \cup \{x\}$.

-
Looks OK to me. And (as expected) this set has measure 0. –  Gerald Edgar Jan 5 '13 at 21:15
Great ! –  Joel David Hamkins Jan 5 '13 at 21:19
Very clever! +1 –  Todd Trimble Jan 5 '13 at 21:31
Error somewhere could just as well be in comment to the question! :-) –  Asaf Karagila Jan 6 '13 at 0:32
@Clinton: Very Nice. $A$ is the transfers of the Cantor ternary set. –  user30230 Jan 6 '13 at 7:33