13
$\begingroup$

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 !?

$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Jan 5, 2013 at 14:43
  • 1
    $\begingroup$ 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? $\endgroup$
    – Todd Trimble
    Jan 5, 2013 at 16:15
  • $\begingroup$ By a qualifying exam old chestnut, any measurable set of positive Lebesgue measure contains arithmetic progressions of arbitrary length. $\endgroup$ Jan 5, 2013 at 17:07
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 5, 2013 at 17:20
  • 1
    $\begingroup$ I feel like I'm missing something silly: doesn't the set of reals whose (say nonterminating) base 3 expansions avoid the digit 1 work? $\endgroup$ Jan 5, 2013 at 19:32

1 Answer 1

24
$\begingroup$

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\}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.