Our starting point is Rado’s theorem which says that each vector space over
$\mathbb{Q}$
can be colored with countably many colors, so that no arithmetic progression of length 3 (in short, 3-AP) is monocolored (unpublished, but see [Reference Ceder1]).
There is a general machinery to obtain similar coloring theorems, and in some cases it even gives the existence of a well ordering such that each point is the last element of only finitely many of the configurations in question. In one example, Erdős and Hajnal proved that
$\mathbb{R}^{2}$
can be colored with countably many colors so the no two points in rational distance get the same color, and their argument gives a well ordering
${<}$
of
$\mathbb{R}^{2}$
such that for each
$x\in \mathbb{R}^{2}$
the set
$$\begin{eqnarray}\{y<x:d(x,y)\in \mathbb{Q}\}\end{eqnarray}$$
is finite (see [Reference Erdős2]). The latter implies the former: given a well ordering
${<}$
as above, the coloring can be constructed by transfinite recursion.
The proof of Rado’s theorem, however, goes differently: one fixes a basis
$\{b_{\unicode[STIX]{x1D6FC}}:\unicode[STIX]{x1D6FC}<\unicode[STIX]{x1D705}\}$
of
$V$
and if
$$\begin{eqnarray}x=\mathop{\sum }_{i=0}^{n-1}\unicode[STIX]{x1D706}_{i}b_{\unicode[STIX]{x1D6FC}_{i}}\end{eqnarray}$$
for some
$n$
non-zero rational numbers
$\unicode[STIX]{x1D706}_{0},\ldots ,\unicode[STIX]{x1D706}_{n-1}$
such that
$\unicode[STIX]{x1D6FC}_{0}<\cdots <\unicode[STIX]{x1D6FC}_{n-1}$
, then color
$x$
with (some code of) the string
$\langle \unicode[STIX]{x1D706}_{0},\ldots ,\unicode[STIX]{x1D706}_{n-1}\rangle$
(vector 0 obtains a separate color). An easy calculation shows that there is no (non-trivial) 3-AP with all terms of the same color.
In the paper we use the following notation. If
$S$
is a set,
$\unicode[STIX]{x1D705}$
a cardinal, we define
$[S]^{\unicode[STIX]{x1D705}}=\{x\subseteq S:|x|=\unicode[STIX]{x1D705}\}$
,
$[S]^{{\geqslant}\unicode[STIX]{x1D705}}=\{x\subseteq S:|x|\geqslant \unicode[STIX]{x1D705}\}$
,
$[S]^{{<}\unicode[STIX]{x1D705}}=\{x\subseteq S:|x|<\unicode[STIX]{x1D705}\}$
. In particular,
$[S]^{{<}\unicode[STIX]{x1D714}}$
is the set of finite subsets of
$S$
.
A set mapping is any function
$f:S\rightarrow {\mathcal{P}}(S)$
for some set
$S$
. A subset
$A\subseteq S$
is free for
$f$
, if
$x\notin f(y)$
holds for
$x,y\in A$
,
$x\neq y$
.
If
$f:S\rightarrow [S]^{{<}\unicode[STIX]{x1D714}}$
is a set mapping, then by Fodor’s theorem [Reference Fodor5],
$S$
is the union of countably many free sets, i.e.
$S=S_{0}\cup S_{1}\cup \cdots \,$
such that if
$x\neq y\in S_{i}$
, then
$y\notin f(x)$
.
We show that if
$|V|\leqslant \aleph _{1}$
then there is a well order of
$V$
such that each vector is the last element of only finitely many 3-APs. In fact, there is a set mapping
$f:V\rightarrow [V]^{{<}\unicode[STIX]{x1D714}}$
such that each set that is free for
$f$
is linearly independent. This implies, via Fodor’s theorem that
$V$
is the union of countably many linearly independent sets, a result of Erdős and Kakutani (cf. [Reference Erdős and Kakutani3]). On the other hand, if
$|V|>\aleph _{1}$
then even the following holds: for every set mapping
$f:V\rightarrow [V]^{{<}\unicode[STIX]{x1D714}}$
there is a free set which is a 3-AP.
Using this we obtain yet another equivalent form of the Continuum Hypothesis (see [Reference Sierpiński9]): there is a set mapping
$f:\mathbb{R}\rightarrow [\mathbb{R}]^{{<}\unicode[STIX]{x1D714}}$
with no free set which is a 3-AP.
We also give the general forms of the these theorems: if
$3\leqslant n<\unicode[STIX]{x1D714}$
and
$V$
is a vector space over
$\mathbb{Q}$
with
$|V|\leqslant \aleph _{n-2}$
, then there is a well ordering of
$V$
such that each vector is the last element of finitely many
$n$
-APs, and consequently there is a set mapping
$f:V\rightarrow [V]^{{<}\unicode[STIX]{x1D714}}$
with no free
$n$
-AP. If, however,
$|V|\geqslant \aleph _{n-1}$
then every set mapping
$f:V\rightarrow [V]^{{<}\unicode[STIX]{x1D714}}$
contains a free set which is an
$n$
-AP.
As an example similar to Corollary 5 we also show that the Continuum Hypothesis is equivalent to the existence of a set mapping
$f:\mathbb{R}^{2}\rightarrow [\mathbb{R}^{2}]^{{<}\unicode[STIX]{x1D714}}$
with no free set which consists of the four nodes of a rectangle (Theorem 6).
One might notice that Theorem 4 is somewhat similar to the famous Kuratowski–Sierpiński theorem on set mappings [Reference Kuratowski7, Reference Sierpiński8] and the proof also bears some resemblance. There is, however, an essential difference; the Kuratowski–Sierpiński theorem concerns set mappings of the form
$f:[S]^{n}\rightarrow [S]^{{<}\unicode[STIX]{x1D714}}$
for some set
$S$
with
$n>1$
. In our case, no such thing can be done, because if
$V$
is a vector space, then there is no free 3-AP for the set mapping
$f:[V]^{2}\rightarrow [V]^{1}$
where
$$\begin{eqnarray}f(\{x,y\})=\biggl\{\frac{x+y}{2}\biggr\}.\end{eqnarray}$$
Our results can be generalized to higher cardinals, as well. One has to replace “finitely many” with “of size
${<}\unicode[STIX]{x1D707}$
” for some infinite cardinal
$\unicode[STIX]{x1D707}$
and
$\aleph _{n}$
with the
$n$
th successor of
$\unicode[STIX]{x1D707}$
,
$\unicode[STIX]{x1D707}^{+n}$
. The proofs are identical.
The paper [Reference Hindman, Leader and Strauss6] also gives somewhat similar results: the authors investigate Ramsey type theorems on
$\mathbb{R}$
where the monocolored set has to satisfy certain arithmetical properties.
Theorem 1. If
$V$
is a vector space over
$\mathbb{Q}$
,
$|V|=\aleph _{1}$
, then there is a set mapping
$f:V\rightarrow [V]^{{<}\unicode[STIX]{x1D714}}$
such that if
$\{a_{0},\ldots ,a_{m-1}\}$
is a linearly dependent system of non-zero vectors, then
$a_{i}\in f(a_{j})$
for some
$i\neq j$
.
Proof. Let
$V=\bigcup \{V_{\unicode[STIX]{x1D6FC}}:\unicode[STIX]{x1D6FC}<\unicode[STIX]{x1D714}_{1}\}$
be an increasing decomposition of
$V$
into countable subspaces, which is continuous, i.e.
$V_{\unicode[STIX]{x1D6FC}}=\bigcup \{V_{\unicode[STIX]{x1D6FD}}:\unicode[STIX]{x1D6FD}<\unicode[STIX]{x1D6FC}\}$
for
$\unicode[STIX]{x1D6FC}$
limit, and
$V_{0}=\{0\}$
. Enumerate
$V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}$
as
$\{v_{n}^{\unicode[STIX]{x1D6FC}}:n<\unicode[STIX]{x1D714}\}$
. Define
$f$
by
$f(v_{n+1}^{\unicode[STIX]{x1D6FC}})=\{v_{0}^{\unicode[STIX]{x1D6FC}},\ldots ,v_{n}^{\unicode[STIX]{x1D6FC}}\}$
.
In order to show that
$f$
is as claimed, let
$A=\{a_{0},\ldots ,a_{m}\}$
be a linearly dependent set of non-zero vectors. We can as well assume that
$A$
is a minimal linearly dependent system. Let
$\unicode[STIX]{x1D6FC}$
be minimal such that
$A\subseteq V_{\unicode[STIX]{x1D6FC}+1}$
, say
$a_{m}\in V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}$
. As
$A$
is a minimal linearly dependent system,
$a_{m}$
is a linear combination of
$a_{0},\ldots ,a_{m-1}$
. We cannot have that
$a_{0},\ldots ,a_{m-1}\in V_{\unicode[STIX]{x1D6FC}}$
as then
$a_{m}$
would also be in
$V_{\unicode[STIX]{x1D6FC}}$
, a contradiction. We must have, therefore, another element of
$A$
in
$V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}$
, say
$v_{i}^{\unicode[STIX]{x1D6FC}},v_{j}^{\unicode[STIX]{x1D6FC}}\in A$
for some
$i\neq j$
. But then, if
$i<j$
, we have
$v_{i}^{\unicode[STIX]{x1D6FC}}\in f(v_{j}^{\unicode[STIX]{x1D6FC}})$
, and we are finished.◻
If
$V$
is a vector space over
$\mathbb{Q}$
, let
${\mathcal{H}}_{k}$
be the set of
$k$
-element arithmetic progressions in
$V$
and
$$\begin{eqnarray}{\mathcal{H}}_{s,k}=\bigcup \{[A]^{{\geqslant}s}:A\in {\mathcal{H}}_{k}\}.\end{eqnarray}$$
Theorem 2. If
$s<\unicode[STIX]{x1D714}$
,
$V$
is a vector space over
$\mathbb{Q}$
,
$X\subseteq V$
,
$|X|\leqslant \aleph _{s}$
, then
$X$
has a well ordering such that for each
$x\in X$
,
$x$
is the last element of finitely many
$A\in {\mathcal{H}}_{s+2,k}$
.
Proof. The proof is by induction on
$s$
. If
$s=0$
, any well ordering of
$X$
into type
$\unicode[STIX]{x1D714}$
is as required.
Assume that we have the result for
$s$
, and
$|X|=\aleph _{s+1}$
. By replacing both
$X$
and
$V$
with the subspace generated by
$X$
, we can assume that
$X=V$
.
Decompose
$V$
as the increasing, continuous union
$V=\bigcup \{V_{\unicode[STIX]{x1D6FC}}:\unicode[STIX]{x1D6FC}<\unicode[STIX]{x1D714}_{s+1}\}$
such that each
$V_{\unicode[STIX]{x1D6FC}}$
is a subspace,
$V_{0}=\{0\}$
, and
$|V_{\unicode[STIX]{x1D6FC}}|\leqslant \aleph _{s}$
.
By the inductive hypothesis, there is a well ordering
${<}_{\unicode[STIX]{x1D6FC}}$
of
$V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}$
such that for each
$x\in V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}$
there are only finitely many
$B\in {\mathcal{H}}_{s,k}$
,
$B\subseteq V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}$
, whose last element is
$x$
. Let
$V$
be the sum of the well orders
${<}_{\unicode[STIX]{x1D6FC}}$
, that is, if
$x\in V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}$
,
$y\in V_{\unicode[STIX]{x1D6FD}+1}-V_{\unicode[STIX]{x1D6FD}}$
, then we let
$x<y$
if either
$\unicode[STIX]{x1D6FC}<\unicode[STIX]{x1D6FD}$
or else
$\unicode[STIX]{x1D6FC}=\unicode[STIX]{x1D6FD}$
and
$x{<}_{\unicode[STIX]{x1D6FC}+1}y$
. Clearly,
${<}$
is a well ordering of
$V$
.
In order to show that
${<}$
is as required, assume that
$x\in V$
is the last element of
$B\in {\mathcal{H}}_{s+3,k}$
. Clearly,
$x$
is not in
$V_{0}=\{0\}$
. There is a unique
$\unicode[STIX]{x1D6FC}<\unicode[STIX]{x1D705}$
such that
$x\in V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}$
. Necessarily
$|B\cap V_{\unicode[STIX]{x1D6FC}}|\leqslant 1$
, as otherwise
$B\subseteq V_{\unicode[STIX]{x1D6FC}}$
(for
$V_{\unicode[STIX]{x1D6FC}}$
is a subspace). We then have
$B^{\prime }=B-V_{\unicode[STIX]{x1D6FC}}\in {\mathcal{H}}_{s+2,k}$
. By the inductive hypothesis,
$x$
is the last element of finitely many sets
$B^{\prime }$
. For a fixed
$B^{\prime }$
, as
$|B^{\prime }|\geqslant 2$
and it is a subset of an arithmetic progression of length
$k$
, there are finitely many
$B\in {\mathcal{H}}_{s+2,k}$
with
$B\supseteq B^{\prime }$
, which gives the statement.◻
Corollary 3. If
$V$
is a vector space over
$\mathbb{Q}$
,
$|V|=\aleph _{n}$
, then there is a well ordering such that each element is the last member of only finitely many arithmetic progressions of length
$n+1$
. Consequently, there is a set mapping
$f:V\rightarrow [V]^{{<}\unicode[STIX]{x1D714}}$
with no free arithmetic progression of length
$n+1$
.
Proof. The first statement is Theorem 2 with
$s=n-1$
,
$k=n$
. Given the well ordering, we set
$f(x)$
as the union of all elements of all arithmetic progressions whose last element is
$x$
.◻
Theorem 4. If
$V$
is a vector space over
$\mathbb{Q}$
with
$|V|=\aleph _{n-1}$
,
$f:V\rightarrow [V]^{{<}\unicode[STIX]{x1D714}}$
is a set mapping, then there is a free arithmetic progression of length
$n$
.
Proof. Let
$A_{j}\subseteq V$
be arbitrary with
$|A_{j}|=\aleph _{n-1-j}$
(
$j<n$
).
We first choose
$a_{0}\in A_{0}$
in such a way that for every sequence
$$\begin{eqnarray}\langle x_{1},\ldots ,x_{n-1}\rangle \in A_{1}\times \cdots \times A_{n-1}\end{eqnarray}$$
we have
$$\begin{eqnarray}ia_{0}+\mathop{\sum }_{j=1}^{n-1}(i-j)x_{j}\notin f\biggl(-\mathop{\sum }_{j=1}^{n-1}jx_{j}\biggr)\quad (1\leqslant i\leqslant n-1).\end{eqnarray}$$
This is possible, as this requirement for each sequence
$\langle x_{1},\ldots ,x_{n-1}\rangle$
excludes finitely many values for
$a_{0}$
, there are
$\aleph _{n-2}$
such sequences and
$|A_{0}|=\aleph _{n-1}$
.
Assume now that we have selected
$a_{0},\ldots ,a_{r-1}$
.
Pick
$a_{r}\in A_{r}$
in such a way that for every sequence
$$\begin{eqnarray}\langle x_{r+1},\ldots ,x_{n-1}\rangle \in A_{r+1}\times \cdots \times A_{n-1}\end{eqnarray}$$
if
$$\begin{eqnarray}b_{r}=\mathop{\sum }_{j<r}(r-j)a_{j}+\mathop{\sum }_{j>r}(r-j)x_{j}\end{eqnarray}$$
then
$$\begin{eqnarray}\mathop{\sum }_{j<r}(i-j)a_{j}+(i-r)a_{r}+\mathop{\sum }_{j>r}(i-j)x_{j}\notin f(b_{r})\quad (i\neq r).\end{eqnarray}$$
If
$r=n-1$
we also require
$$\begin{eqnarray}a_{0}+\cdots +a_{n-1}\neq 0.\end{eqnarray}$$
This is possible, as there are
$\aleph _{n-r-2}$
such sequences
$\langle x_{r+1},\ldots ,x_{n-1}\rangle$
, each excludes finitely many values of
$a_{r}$
and
$|A_{r}|=\aleph _{n-r-1}$
. If
$r=n-1$
, then there are
$|A_{n-1}|=\aleph _{0}$
possible values for
$a_{n-1}$
and finitely many of them are excluded.
Finally, when we have selected
$a_{0},\ldots ,a_{n-1}$
, set
$$\begin{eqnarray}v_{i}=\mathop{\sum }_{j=0}^{n-1}(i-j)a_{j}.\end{eqnarray}$$
Then
$v_{0},v_{1},\ldots ,v_{n-1}$
form an arithmetic progression of length
$n$
, with difference
$$\begin{eqnarray}a_{0}+\cdots +a_{n-1}\neq 0,\end{eqnarray}$$
and
$v_{i}\notin f(v_{r})$
as the condition
$$\begin{eqnarray}v_{i}=\mathop{\sum }_{j=0}^{n-1}(i-j)a_{j}\notin f\biggl(\mathop{\sum }_{j=0}^{n-1}(r-j)a_{j}\biggr)=f(v_{r})\end{eqnarray}$$
was satisfied when
$a_{r}$
was chosen.◻
Corollary 5. The following are equivalent:
-
(a) the Continuum Hypothesis;
-
(b) there is a well ordering
${<}$
of
$\mathbb{R}$
such that each real is the maximal element of finitely many 3-APs under
${<}$
; -
(c) there is a set mapping
$f:\mathbb{R}\rightarrow [\mathbb{R}]^{{<}\unicode[STIX]{x1D714}}$
with no free 3-AP; -
(d) there is a set mapping
$f:\mathbb{R}\rightarrow [\mathbb{R}]^{{<}\unicode[STIX]{x1D714}}$
with no linearly dependent free set.
Proof. The implications (a)
$\rightarrow$
(b)
$\rightarrow$
(c) are Corollary 3.
The implication (c)
$\rightarrow$
(a) is Theorem 4 for
$n=3$
.
The implication (a)
$\rightarrow$
(d) is Theorem 1.
The implication (d)
$\rightarrow$
(c) is obvious.◻
Theorem 6. The following are equivalent:
-
(a) the Continuum Hypothesis;
-
(b) there is a set mapping
$f:\mathbb{R}^{2}\rightarrow [\mathbb{R}^{2}]^{{<}\unicode[STIX]{x1D714}}$
with no free rectangle.
Proof. (a)
$\rightarrow$
(b) By the Continuum Hypothesis,
$|\mathbb{R}^{2}|=\aleph _{1}$
, and so
$\mathbb{R}^{2}$
can be written as the increasing, continuous union of countable sets
$\mathbb{R}^{2}=\bigcup \{V_{\unicode[STIX]{x1D6FC}}:\unicode[STIX]{x1D6FC}<\unicode[STIX]{x1D714}_{1}\}$
so that
$V_{0}=\{0\}$
and if
$a,b,c\in V_{\unicode[STIX]{x1D6FC}}$
are distinct then
$a+b-c\in V_{\unicode[STIX]{x1D6FC}}$
. Enumerate
$V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}$
as
$V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}=\{x_{n}^{\unicode[STIX]{x1D6FC}}:n<\unicode[STIX]{x1D714}\}$
. Define the set mapping
$f:\mathbb{R}^{2}\rightarrow [\mathbb{R}^{2}]^{{<}\unicode[STIX]{x1D714}}$
by
$f(x_{n+1}^{\unicode[STIX]{x1D6FC}})=\{x_{0}^{\unicode[STIX]{x1D6FC}},\ldots ,x_{n}^{\unicode[STIX]{x1D6FC}}\}$
. Assume now that
$R\subseteq \mathbb{R}^{2}$
is a rectangle. Let
$\unicode[STIX]{x1D6FC}<\unicode[STIX]{x1D714}_{1}$
be minimal such that
$R\subseteq V_{\unicode[STIX]{x1D6FC}+1}$
. We cannot have
$|R\cap V_{\unicode[STIX]{x1D6FC}}|=3$
, because in that case if
$R=\{a,b,c,d\}$
,
$R\cap V_{\unicode[STIX]{x1D6FC}}=\{a,b,c\}$
, then
$d=a+b-c\notin V_{\unicode[STIX]{x1D6FC}}$
, contradicting the closure property of
$V_{\unicode[STIX]{x1D6FC}}$
. We have, therefore,
$|R\cap (V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}})|\geqslant 2$
, say,
$x_{i}^{\unicode[STIX]{x1D6FC}},x_{j}^{\unicode[STIX]{x1D6FC}}\in V_{\unicode[STIX]{x1D6FC}+1}-V_{\unicode[STIX]{x1D6FC}}$
. But then, if
$i<j$
, then
$x_{i}^{\unicode[STIX]{x1D6FC}}\in f(x_{j}^{\unicode[STIX]{x1D6FC}})$
, so
$R$
is not free for
$f$
.
(b)
$\rightarrow$
(a) Assume that the Continuum Hypothesis fails, yet there is a set mapping
$f:\mathbb{R}^{2}\rightarrow [\mathbb{R}^{2}]^{{<}\unicode[STIX]{x1D714}}$
with no free rectangle. By Fodor’s theorem,
$\mathbb{R}^{2}$
can be decomposed into the union of countably many free sets:
$\mathbb{R}^{2}=A_{0}\cup A_{1}\cup \cdots \,$
. By a result of Erdős and Komjáth (see [Reference Erdős and Komjáth4]), if the Continuum Hypothesis fails and
$\mathbb{R}^{2}$
is decomposed into countably many parts, then one of them contains a rectangle:
$R\subseteq A_{i}$
. As
$A_{i}$
is free for
$f$
, so is
$R$
.◻
Acknowledgement
The author is thankful to the referee for a careful job.
