%  ------------------------------------------------
%  LaTeX paper
%
%  authors : J.Cichon, A.Jasinski, A.Kamburelis, P.Szczepaniak.
%  title   : On translations of subsets of the real line
%  e-mail  : akamb@math.uni.wroc.pl
%
%  last correction : 27.11.2000
%  -------------------------------------------------
%  1. It must be LaTeX'ed twice, to obtain correct labels.
%  2. The below commands \textwidth ... etc may be removed.
%  3. Resolve correctly the \continuum newcommand below.
%  -------------------------------------------------

\documentstyle[12pt]{article}

\textwidth 434pt
\textheight 650pt
\headheight 0pt
\headsep 0pt
\topmargin 0pt
\footskip 50pt
\footheight 90pt
\parskip 0pt
\oddsidemargin 16pt
\evensidemargin 16pt

%\newcommand{\continuum}{\frak{c}}
\newcommand{\continuum}{{\bf c}} % should be gothic small letter c

\newcommand{\CH}{{\bf CH}}
\newcommand{\MA}{{\bf MA}}
\newcommand{\ZFC}{{\bf ZFC}}
\newcommand{\CPA}{{\bf CPA}}
\newcommand{\Kat}{{\cal K}}
\newcommand{\Leb}{{\cal L}}
\newcommand{\B}{{\cal B}}
\newcommand{\F}{{\cal F}}

\newcommand{\al}{{\alpha}}
\newcommand{\be}{{\beta}}
\newcommand{\ga}{{\gamma}}
\newcommand{\ep}{{\epsilon}}
\newcommand{\ka}{{\kappa}}
\newcommand{\om}{{\omega}}
\newcommand{\lam}{{\lambda}}

\newcommand{\la}{{\langle}}
\newcommand{\ra}{{\rangle}}


\newcommand{\add}{{\it add}\/}
\newcommand{\cov}{{\it cov}\/}
\newcommand{\non}{{\it non}\/}
\newcommand{\cf}{{\it cf}\/}
\newcommand{\real}{{\bf R}}
\newcommand{\integer}{{\bf Z}}
\newcommand{\rational}{{\bf Q}}
\newcommand{\cyclic}{{\bf C}}
\newcommand{\cantor}{{2^\om}}

\newcommand{\subgr}{{\lhd}}
\newcommand{\sd}{{\bigtriangleup}}  %symmetric difference
\newcommand{\power}{{\cal P}\/}
\newcommand{\Tr}{{\rm Tr}\/}
\newcommand{\Fix}{{\rm Fix}\/}
\newcommand{\LSP}{{\rm LSP}\/}
\newcommand{\FIN}{{\rm FIN}\/}
\newcommand{\Perf}{{\rm Perf}\/}
\newcommand{\Borel}{{\rm Borel}\/}

\newcommand{\proof}{\noindent{\bf Proof.}\hspace{0.3cm}}
\newcommand{\qed}{{\hspace{0.3cm}\unitlength1mm\thicklines\framebox(2,2){}}}
\newtheorem{proposition}{Proposition}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}[proposition]{Theorem}
\newtheorem{corollary}[proposition]{Corollary}
\newtheorem{lemma}[proposition]{Lemma}

\title{On translations of subsets of the real line}
\author{ Jacek Cicho\'{n}, Andrzej Jasi\'{n}ski,
Anastasis Kamburelis, \and Przemys{\l}aw Szczepaniak
\thanks{
1991 Mathematics Subject Classification: Primary 04A15; Secondary 03E15.
\newline Key words: Lebesgue measure, Baire property,
almost invariant sets.
}}
\date{}


\begin{document}
\maketitle

\begin{abstract}
In this paper we discuss various questions connected with
translations of subsets of the real line.
Most of these questions originate from W.~Sierpi\'{n}ski.
We discuss the number of translations a single subset of
the reals may have.
Later we discuss almost invariant subsets of Abelian groups.
\end{abstract}


\section{Introduction}

We shall use standard set theoretical notation.
By $|X|$ we denote the cardinality of set $X$.
If $\ka$ is a cardinal number then by $\cf(\ka)$
we denote its cofinality.
We identify the first infinite cardinal number $\om$ with the
set of natural numbers. By $\continuum$ we denote the
cardinality of continuum, i.e., $\continuum=2^{\om}$.
The Continuum Hypothesis (denoted by \CH) is the statement that
$\continuum=\om_1$. By \MA\ we denote the Martin's Axiom (see [J]).

For any set $X$ and a cardinal number $\ka$ let $[X]^{\ka}$
(resp.~$[X]^{<\ka}$) be the family of all subsets
of $X$ of cardinality $\ka$ (resp.~less than $\ka$).
By $A^{c}$ we denote the complement of the set $A$.
The real line is denoted by $\real$. Let $\Leb$ be the
$\sigma$-ideal of Lebesgue measure zero subsets of $\real$.
Let also $\Kat$ be the $\sigma$-ideal of
first category subsets of $\real$.

If $J$ is an ideal of subsets of a set X we define
the following cardinal coefficients:
$\add(J)=\min\{|S|:S\subseteq J\mbox{ and }\bigcup S\notin J\}$,
$\cov(J)=\min\{|S|:S\subseteq J\mbox{ and }\bigcup S=X\}$,
$\non(J)=\min\{|T|:T\subseteq X\mbox{ and } T\notin J\}$.
If some cardinal number is not defined, then we assume that this
number is $\infty$, where $\infty>\ka$
for every cardinal number $\ka$.
We write $H\subgr G$ if $H$ is a subgroup of the group $G$.

We would like to thank the referee for many helpful comments.


\section{Preliminaries}

Suppose that $(G,+)$ is a group.
For $A,B\subseteq G$ and $g\in G$ define
$A\pm g = \{a\pm g:a\in A\}$ and
$A\pm B = \{a\pm b:a\in A \wedge b\in B\}$.
Let $J$ be an ideal of subsets of $G$.
We say that $J$ is {\em invariant},
if $A+g\in J$ for every $A\in J$ and $g\in G$.

\bigskip\noindent
{\bf Convention.} In what follows, we always assume that $G$
is an Abelian group and $J$ is an invariant ideal of subsets of $G$.

\bigskip
For $A\subseteq G$ define $\Fix(A,J) = \{g\in G: (A+g)\sd A\in J\}$.
Here $\sd$ denotes the symmetric difference of sets.
Then $\Fix(A,J)$ is a subgroup of $G$. Note also that
$\Fix(A^c,J) = \Fix(A,J)$

\bigskip\noindent
{\bf Definition.} We say that $A$ is $J$-{\em almost invariant},
if $\Fix(A,J)=G$.

\begin{lemma}\label{easychar}
Let $A\subseteq G$. The following conditions are equivalent :
\begin{itemize}
\item[{1.}] $A$ is $J$-almost invariant,
i.e., $\forall g\in G\;\; (A+g)\sd A\in J$;
\item[{2.}] $\forall g\in G\;\; (A+g)\setminus A\in J$;
\item[{3.}] $\forall g\in G\;\; A\setminus (A+g)\in J$.
\end{itemize}
\end{lemma}

Note that the family of all $J$-almost invariant sets
forms a field of subsets of $G$. This field is $\add(J)$-complete,
i.e., it is closed under taking unions of length less than $\add(J)$.
If $A\in J$ then obviously $A$ and $A^c$ are $J$-almost invariant.
We consider such sets as a {\em trivial} $J$-almost invariant set.
Otherwise we say that $A$ is {\em nontrivial}.

Let us notice the following easy fact concerning translations.

\begin{lemma}\label{easyor}
If $G=A\cup B$ where $A\cap B=\emptyset$ and $T\subseteq G$
then either $T+g\subseteq B$ for some $g\in G$ or else $A-T=G$.
\end{lemma}

This gives us another simple characterization of $J$-almost invariant sets.

\begin{lemma}\label{transchar}
$A$ is $J$-almost invariant iff
$\;\forall\; T\subseteq A$, if $\; T\notin J$ then $A-T=G$.
\end{lemma}

We omit the easy proof.
By this Lemma $A-A=G$, if $A$ is $J$-almost invariant and $A\notin J$.
This shows that certain almost invariant subsets of $\real$ are destroyed
after forcing a new real.
Next observation gives a condition on $J$ ensuring that all
$J$-almost invariant sets are trivial.
This was also proved in [L] (Theorem~{2}).

\begin{proposition}\label{usecov}
Suppose that $J$ satisfies the following condition :
\begin{quote}
If $A\notin J$ then there exists $T\subseteq A$
such that $T\notin J$ and $|T|<\cov(J)$.
\end{quote}
Then all $J$-almost invariant sets are trivial.
\end{proposition}
\proof Suppose on the contrary that $A$
is a nontrivial $J$-almost invariant set.
Then so is $B=A^{c}$ and $A,B\notin J$.
Since our assumptions are symmetric, we may assume that $B$ cannot be
covered by less than $\cov(J)$ sets from $J$.
Choose $T\subseteq A$ such that $T\notin J$ and $|T|<\cov(J)$.
By Lemma {\ref{transchar}} we have $A-T=G$.
That is $G=\bigcup_{g\in T} A-g$.
So $B=\bigcup_{g\in T} (A-g)\cap B$.
But $A$ is $J$-almost invariant,
so $(A-g)\cap B\in J$ for every $g\in G$.
We have just covered the set $B$ by less than $\cov(J)$ sets from $J$.
A contradiction. \qed

\begin{corollary}\label{ongroup}
Suppose $\om\leq\ka<|G|$. Let $G=A\cup B$, $A\cap B=\emptyset$
and $|A|=|B|=|G|$.
Then there exists $g\in G$ such that $|(A+g)\cap B|\geq\ka$.
\end{corollary}
\proof
Let $J=\{X\subseteq G:|X|<\ka\}$. Then $\cov(J)=|G|$ and $J$ satisfies
the condition from Proposition {\ref{usecov}}.
So we conclude that $A$ is not $J$-almost invariant,
so there exists $g\in G$ such that $(A+g)\setminus A=(A+g)\cap B\notin J$.
\qed

\section{Translations of subsets of the real line}

In this section we discuss some translation properties of subsets of
the real line $\real$. Hence our basic group is the real line and
the basic ideal is $\{\emptyset\}$.
Sierpi\'{n}ski ([S2]) asked how many distinct translations
a given set $A\subseteq\real$ has, i.e.,
what the cardinality of $\Tr(A):=\{A+g: g\in\real\}$ is.
It is obvious that $|\Tr(A)|=1$ iff $A=\emptyset$ or $A=\real$.
It is also easy to see that $|\Tr(A)|=\continuum$
for every bounded nonempty set $A\subseteq\real$.
Recall that $\Fix(A)=\{g\in\real: A+g=A\}$ is a subgroup of $\real$.
It is easy to observe that $|\Tr(A)|=|\real/\Fix(A)|$.
But $\real$ is a divisible group.
Therefore, if $|\Tr(A)|\geq 2$ then $|\Tr(A)|\geq\om$.

For any cardinal number $\ka$ such that $\om\leq\ka\leq\continuum$
one can find $G\subgr\real$ such that $|\Tr(G)|=\ka$. To see this,
let $\{x_\al:\al<\continuum\}$ be any Hamel basis.
Let $G=\LSP(x_\al:\al\geq\ka)$ be the linear space over rationals
generated by the set $\{x_\al:\al\geq\ka\}$
(note that $\Fix(G)=G$ for $G\subgr\real$).

A classical construction yields a Vitali set $V\subseteq (0,1)$.
Then $|\Tr(V)|=\continuum$. But there exists a Vitali set with
only $\om$
translations\footnote{This remark is due to J.~Pawlikowski.}.
Just take a Hamel basis $H$ with $1\in H$ and
let $V=\LSP(H\setminus\{1\})$.

All the above mentioned examples used ``strange'' subsets of $\real$.
The following theorem was proved by Sierpi\'{n}ski
(see [S2]) under the additional assumption of the Continuum Hypothesis.

\begin{theorem}
Suppose that $A\subseteq\real$ is Lebesgue measurable or
has the Baire property. Then $|\Tr(A)|\in\{1,\continuum\}$.
\end{theorem}
\proof
Let us prove the theorem for the measure case.
Let $G=\Fix(A)$.
If $G$ is a discrete subgroup of the real line then $|\real/G|=\continuum$.
Hence we may assume that $G$ is a dense subgroup of the real line.
If $A=\emptyset$ or $A=\real$ then $|\Tr(A)|=1$.
Hence we may assume that $\emptyset\neq A\neq\real$.
We claim that $A\in\Leb$ or that $A^{c}\in\Leb$.
Suppose otherwise. Then, by Steinhaus' theorem (see [Ox])
the interior of the set $A-A^{c}$ is nonempty,
so $(A-A^{c})\cap G\neq\emptyset$. Let $a\in A$, $b\in A^{c}$
and $g\in G$ be such that $g=a-b$.
Then $b=a-g$ and this is impossible, since $G=\Fix(A)$.
Since $\Fix(A)=\Fix(A^{c})$ we may assume that $A\in\Leb$.
Let $a\in A$. Then $a+G\subseteq A$, so $G\in\Leb$.
Let $H=\{(x,y)\in\real^{2}: x-y\in G\}$.
Then $H$ is a Lebesgue measure zero subset of the plane $\real^{2}$.
Hence, by Mycielski's theorem (see [M2])
there exists a perfect subset $P$ of the real line $\real$ such that
$P\times P\setminus\{(x,x):x\in\real\}\subseteq\real^{2}\setminus H$.
Hence, if $t_1,t_2\in P$ and $t_1\neq t_2$ then $(t_1,t_2)\notin H$,
hence $t_1-t_2\notin G$, so $G+t_1\neq G+t_2$.
Therefore $|\real/G|=\continuum$.

The proof of the second case of the theorem is similar to the presented one.
Instead of Steinhaus' theorem for the Lebesgue measure it is necessary to
use Steinhaus' theorem for the Baire property (see [Ox]) and Mycielski's
theorem for measure should be replaced by Mycielski's theorem for the
Baire property (see [M1]).
\qed

\bigskip
Let us consider the Cantor dyadic group $(\cantor,+)$
(where $2=\{0,1\}$ and $+$ is the usual pointwise addition modulo $2$).
Let us fix a natural number $n$ and let us consider the
group $G_n=\{x\in\cantor:\forall i<n\;x(i)=0\}$.
Then $|\cantor/G_n|=2^n$. Hence there are sets $A\subseteq\cantor$
such that $1<|\Tr(A)|<\om$.

\begin{lemma}
Let $A\subseteq\cantor$. Then
$|\Tr(A)|\in\{2^n:n\in\om\}\cup\{\ka:\om\leq\ka\leq\continuum\}$.
If $A$ is a Lebesgue measurable set or has the Baire property then
$|\Tr(A)|\in\{2^n:n\in\om\}\cup\{\continuum\}$.
\end{lemma}
\proof
Let $G=\Fix(A)$. Suppose that $L=\cantor/G$ is finite.
Then $L$ is a linear space over the field $\integer_2$,
hence $|L|=2^n$ for some natural number $n$.
Notice that Steinhaus and Mycielski's theorems hold for Lebesgue
measurable subsets of $\cantor$ or sets with the Baire property.
Hence we may repeat arguments from the previous theorem for
the topological group $\cantor$ and show that $|\Tr(A)|\leq\om$ or
$|\Tr(A)|=\continuum$ for Lebesgue measurable subsets
$A\subseteq\cantor$ or sets with the Baire property.
\qed

\section{Almost invariant subsets of uncountable groups}

For an infinite group $G$ let $F_G = \{A\subseteq G: |A|<|G|\}$
be the Frechet ideal.
Note that $F_G$ is invariant and $\add(F_G)=\cf(|G|)$.

\bigskip\noindent
{\bf Definition.}
We say that $A\subseteq G$ is {\em almost invariant},
if $A$ is $F_G$-almost invariant,
i.e., if $|(A+g)\sd A|<|G|$ for every $g\in G$.

\bigskip
In this section we consider almost invariant sets $A\subseteq G$
where $G$ is an uncountable (Abelian) group.
We start our considerations with a technical lemma which
extends the original Sierpi\'{n}ski's construction.

\begin{lemma}\label{technics}
Suppose that $G$ is an uncountable group. Let $|G|=\ka$.
Suppose that we are given $A\subseteq G$ and
a sequence $\la P_\al:\al<\ka\ra$ of subsets of $G$ such that
$$\forall \al<\ka\;\; \forall B\in [G]^{<\ka}
\;\; |\bigcap_{g\in B} (A-g)\cap P_\al|=\ka.$$
Let $\la G_\al:\al<\ka\ra$ be an increasing family of subgroups
of $G$ such that $\bigcup_{\al<\ka} G_\al = G$ and
$|G_\al|<\ka$ for each $\al<\ka$
(if not specified otherwise we let $G_\al$ be the subgroup of $G$
generated by $\la g_\be:\be\leq\al\ra$ where $\la g_\be:\be<\ka\ra$
is some fixed enumeration of $G$).

\medskip\noindent
Then there exists a sequence $\la t_\al:\al<\ka\ra\subseteq G$
such that :
\begin{itemize}
\item[{1.}] the sets $G_\al+t_\al$ are pairwise disjoint;
\item[{2.}] $G_\al+t_\al\subseteq A$ for $\al<\ka$;
\item[{3.}] $(G_\al+t_\al)\cap P_\al\neq\emptyset$
for $\al<\ka$;
\item[{4.}] if $Z\subseteq\ka$ is cofinal in $\ka$ then
$\bigcup_{\al\in Z} (G_\al+t_\al)$ is an almost invariant set of
cardinality $\ka$.
\end{itemize}
\end{lemma}
\proof First note that $(B+t)\cap C\neq\emptyset$ iff $t\in C-B$.
Moreover $t\in\bigcap_{g\in B} (A-g)$ iff $B+t\subseteq A$.
Build $\la t_\al:\al<\ka\ra$ by induction. Suppose
that $\be<\ka$ and $\la t_\al:\al<\be\ra$ has been defined.
Then, it is possible to choose $t_\be$ such that
$$t_\be\in\bigcap\limits_{g\in {G_\be}} (A-g)\cap P_\be$$ and
$$(G_\be+t_\be)\cap\bigcup\limits_{\al<\be}
(G_\al+t_\al)=\emptyset$$
(note that $|G_\al+t_\al|=|G_\al|\leq|G_\be|<\ka$).
The sequence $\la t_\al:\al<\ka\ra$ is the required one.
Conditions {\it 1, 2\/} and {\it 3\/} are satisfied.
Let $Z\subseteq\ka$ be cofinal in $\ka$ and
$S=\bigcup_{\al\in Z} (G_\al+t_\al)$.
Fix $g\in G$ and let $\be<\ka$ be such that $g\in G_\al$
for every $\al\geq\be$.
Then $G_\al+t_\al+g=(G_\al+g)+t_\al=G_\al+t_\al$.
Hence
$$(S+g)\setminus S\subseteq\bigcup\limits_{\al<\be} (G_\al+g)$$
and this last union has cardinality less than $\ka$.
In the end it suffices to observe that
$|S|=|Z|\cdot\sup_{\al\in Z}|G_\al|=\ka$.
\qed

\bigskip
It follows easily from Lemma {\ref{technics}} that nontrivial
almost invariant sets exist in every uncountable group.
The following observation extends Sierpi\'{n}ski's result from [S1].

\begin{proposition}\label{decomposition}
Suppose that $G$ is an uncountable group and $2\leq\lambda\leq|G|$.
Then there exists a decomposition of $G$ into $\lambda$
nontrivial almost invariant sets.
\end{proposition}
\proof
Let $\ka=|G|$.
We apply Lemma {\ref{technics}} (with $A=P_\al=G$)
and obtain a sequence $\la t_\al:\al<\ka\ra$.
Write $\ka=\bigcup_{\al<\ka} Z_\al$ where
$Z_\al$'s are pairwise disjoint sets of cardinality $\ka$.
Put $S_\al=\bigcup_{\be\in Z_\al} (G_\be+t_\be)$.
It follows from Lemma {\ref{technics}} that $S_\al$'s
are pairwise disjoint almost invariant sets of cardinality $\ka$.

Suppose first that $2\leq\lambda<\cf(\ka)$.
Then the set $\bigcup_{\al<\lambda} S_\al$ is almost invariant because
$\cf(\ka)=\add(F_G)$. Therefore the remainder
$R=G\setminus\bigcup_{\al<\lambda} S_\al$ is also almost invariant.
Hence $\{S_\al:\al<\lambda\}\cup\{R\}$ is the required
decomposition (if $\lambda$ is finite then just glue $R$ with $S_0$).

Suppose now that $\cf(\ka)\leq\lambda\leq\ka$.
The remainder $R=G\setminus\bigcup_{\al<\lambda} S_\al$ has
cardinality at most $\ka$. Write $R=\bigcup_{\al<\lambda} R_\al$
where $R_\al$'s are pairwise disjoint sets of cardinality
less than $\ka$ (some of them may be empty).
Put $T_\al = S_\al\cup R_\al$.
Clearly $\{T_\al:\al<\lambda\}$ works.
\qed

\bigskip
We can ask whether a given set $A\subseteq G$ with $|A|=|G|$
can be decomposed into many nontrivial almost invariant sets.
Of course this is not always possible (note that a nontrivial
almost invariant subset of $\real$ must be unbounded).
But if $A$ itself is almost invariant then we can repeat
the construction from {\ref{technics}} {\em inside} $A$.
It follows in particular that there are no almost invariant ``atoms''.
In fact we can prove a bit more. Recall that two sets
$A,B\subseteq G$ are {\em almost disjoint}, if $|A\cap B|<|G|$.

\begin{proposition}
Suppose that $G$ is an uncountable group and $A$ is
an almost invariant subset of $G$ such that $|A|=|G|$.
Then $A$ contains $\cf(|G|)^{+}$
nontrivial almost invariant sets which are pairwise almost disjoint.
\end{proposition}
\proof
Let $\ka=|G|$. Let $A$ be almost invariant and $|A|=\ka$.
Assume first that $\ka$ is a regular cardinal.
Then $|\bigcap_{g\in B} (A-g)|=\ka$ for every $B\in[G]^{<\ka}$.
Let us apply the Lemma {\ref{technics}} for the set $A$ (with $P_\al=G$).
Let $\F\subseteq [\ka]^\ka$ be a family consisting of pairwise
almost disjoint sets such that $|\F|=\ka^{+}$.
For each $X\in\F$ we put $X^\ast = \bigcup_{\al\in X} (G_\al+t_\al)$.
Then $\{X^\ast:X\in\F\}$ is the required family.

Assume now that $\ka$ is singular and $\lam=\cf(\ka)$. Fix an
increasing sequence of infinite cardinals $\la\ka_\al:\al<\lam\ra$
less than $\ka$ and cofinal in $\ka$. Fix also an increasing sequence
$\la H_\al:\al<\lam\ra$ of subgroups of $G$ such that
$|H_\al|\le\ka_\al$ and $G=\bigcup_{\al<\lam} H_\al$.
We have to be more careful in the proof of the Lemma {\ref{technics}}.
Let $J_\al=\{B\subseteq G:|B|\leq\ka_\al\}$. Then $J_\al$ is an
invariant ideal. Put $G_\al=\Fix(A,J_\al)\cap H_\al$.
Then $G_\al\subgr G$ and $G=\bigcup_{\al<\lam} G_\al$.
Now we can repeat the construction of the sequence
$\la t_\al:\al<\lam\ra$ exactly as in the proof of {\ref{technics}}
(letting $P_\al=G$). To see this note that
$\bigcap_{g\in G_\al}(A-g)$ has cardinality $\ka$.
Again, fix an almost disjoint family $\F\subseteq [\lam]^\lam$
such that $|\F|=\lam^{+}$ and for $X\in\F$ put
$X^\ast = \bigcup_{\al\in X} (G_\al+t_\al)$.
Then $\{X^\ast:X\in\F\}$ is as required.
\qed

\bigskip
Previous results imply that there are a lot of nontrivial
almost invariant subsets of the real line.
However, we shall show that none of them can be a Borel set.

\begin{proposition}\label{noborel}
Suppose that $A,B$ are two disjoint Borel subsets of the real line
such that $\real=A\cup B$ and $|A|=|B|=\continuum$.
Then there exists a real number $x$ such that
$|(A+x)\cap B|=\continuum$.
\end{proposition}
\proof
Suppose first that \CH\ is false.
Let us use Corollary {\ref{ongroup}} for $G=\real$
and $\ka=\om_1$. Let $x\in\real$ be such that
$|(A+x)\cap B|>\om$. But $(A+x)\cap B$ is a Borel set,
hence $|(A+x)\cap B|=\continuum$.

Suppose now that \CH\ is true.
Let us consider any generic extension $V^{\prime}$
of the universe $V$ in which \CH\ is false. Then
$$
V^{\prime}\models(\exists x)(\exists P)(P\in\Perf\wedge(\forall t)
(t\in P\rightarrow t\in(A+x)\cap B))
$$
where $\Perf$ denotes the space of all perfect subsets of the real line.
Observe that this property of the universe $V^{\prime}$ is a
$\Sigma_2^1$-sentence with parameters from the ground universe $V$,
so - by Shoenfield absoluteness theorem (see [J]) -
it holds also in the universe $V$. Hence the theorem is proved.
\qed

\bigskip
With some additional assumptions we can extend the above
proposition to the case when $A$ is an analytic set.

\begin{proposition}\label{noanalytic}
Suppose that $A\subseteq\real$ is an uncountable analytic set
such that its complement contains a perfect subset.
Then $A$ is not almost invariant.
\end{proposition}
\proof
Let $B=A^{c}$. Both $A$ and $B$ have the Baire property.
If $A,B\notin\Kat$ then we can find nonempty open intervals $I$, $J$
and a set $F\in\Kat$ such that $I\setminus F\subseteq A$
and $J\setminus F\subseteq B$. Let $x\in\real$ be such that
$(I+x)\cap J\neq\emptyset$. Then $|(A+x)\cap B|=\continuum$
and hence $A$ is not almost invariant.

Therefore, we can assume that $A\in\Kat$ or $B\in\Kat$.
For both sets there exists a canonical decomposition into $\om_1$
Borel sets (constituents), which is absolute
for $\om_1$ preserving generic extensions.
Say $A=\bigcup_{\al<\om_1} A_\al$
and $B=\bigcup_{\be<\om_1} B_\be$.
If \CH\ is false then we add a single Cohen real
$c$ to the universe $V$ and we work in $V[c]$.
Assume that $B\in\Kat$ (the case when $A\in\Kat$ is similar).
Note that if $x\in\real\cap V$ then the number $x+c$ is a Cohen
real over $V$. Therefore $\real\cap V+c \subseteq A^{\ast}$, where
by $A^{\ast}$ we denote the set $A$ encoded in $V[c]$.
Hence $\real\cap V\subseteq A^{\ast}-c$ and so
$B^{\ast}\cap V\subseteq (A^{\ast}-c)\cap B^{\ast}$.
As $|B^{\ast}\cap V|=\continuum>\om_1$
(by absoluteness $B^{\ast}\cap V$ is just the set $B$ in $V$)
we can find $\al,\be<\om_1$ such that
$|(A^{\ast}_\al-c)\cap B^{\ast}_\be|=\continuum$.
Thus $V[c]$ models the absolute sentence
``$(\exists x)( (A^{\ast}_\al-x)\cap B^{\ast}_\be\mbox{ is uncountable})$''
and we conclude that (in $V$) there exists $x$ such that
$(A-x)\cap B$ is uncountable.

If \CH\ is true we first extend the universe by adding $\om_2$ Sacks reals
either to the set $A$ (if $A\in\Kat$) or to the set $B$ (if $B\in\Kat$).
In both cases it is possible because $A$ and $B$ contain perfect subsets.
Then we can argue as we did previously.
\qed

\begin{corollary}
Assume that every co-analytic set $B\subseteq\real$
of cardinality $\continuum$ contains a perfect subset
(this assumption follows e.g.~from the negation of \CH\ or from the
existence of a measurable cardinal).
Then all analytic almost invariant subsets of $\real$ are trivial.
\end{corollary}


Note that the proof of Proposition {\ref{noanalytic}} breaks down
when $B$ is a co-analytic set such that all its constituents are
countable. It is impossible then to force new elements to $B$ without
collapsing $\om_1$.

Next theorem, due to A.~Miller\footnote{
We would like to thank Arnold Miller for his kind permission to
include his result.}
shows that such sets are possible in the constructible universe $L$.


\begin{theorem}\label{miller} {\rm (A.~Miller)}
If V=L, then there exists a nontrivial almost
invariant $\Pi^1_1$ subset of $\real$.
Similarly, there is such a subset of $\cantor$.
\end{theorem}
\proof To see
that a given transfinite construction of a set of reals
can be converted into the construction of a $\Pi^1_1$ set under
V=L, what must be seen is that the construction itself can be
coded into each real which is appearing at a given stage.
In the transfinite construction of the sets
$\la t_\al+G_\al:\al<\om_1\ra$ it is enough to see that
each $u\in t_\al+G_\al$ can code up an arbitrary real $z\in\cantor$.
(In the proof below $z$ will be recursive in each $u\in t_\al+G_\al$,
but more generally it would be enough for $z$ to be $\Delta_1^1$ in
each $u$.)
The real $z$ in turn can code up the construction of
$\la t_\be+G_\be:\be<\al\ra$ as well as the initial part of the
$L$ hierarchy, i.e., some $L_\ga$, in which it appears.  This makes every
real entering the set ``self-constructible'' and hence we can make our
set $\bigcup _{\be<\om_1} t_\be+G_\be$ into a $\Pi^1_1$ set.
(We suppose we can guarantee it is nontrivial
by only taking the even $\be$'s.)
If we also take $z$ to be not recursive in any
$u\in \bigcup_{\be<\al} t_\be+G_\be$,
then this also automatically guarantees that $t_\al+G_\al$ is
disjoint from $\bigcup_{\be<\al} t_\be+G_\be$.

The coding argument is easier for
the Cantor group $(\cantor,+)$ so we do it first.

\begin{lemma}
Given $G\subseteq\cantor$ countable and $z\in\cantor$ there exists
$t\in\cantor$ such that $z\leq_T t+g$ for each $g\in G$.
The proof shows that such $t$ can be found recursive in $z$
and any enumeration of $G$.
\end{lemma}
\proof
Let $G=\{g_n:n\in\om\}$ be any enumeration. Let $\la A_n:n\in\om\ra$
be a recursive partition of $\om$ into infinite sets and for each
$n$ let $A_n=\{k_0^n<k_1^n<k_2^n<\ldots\}$.

Define $t\in\cantor$ by $$t(k^n_m)+g_n(k^n_m)=z(m)$$
Then we have $z\leq_T t+g_n$ as required.
\qed

\begin{lemma}
Given $G\subseteq\real$ countable and $z\in\cantor$ there exists $t\in \real$
such that $z\leq_T t+g$ for each $g\in G$.  The proof shows that
such $t$ can be found recursive in $z$ and any enumeration of $G$.
\end{lemma}
\proof
Let $\{g_n:n\in\om\}$ and $\la A_n:n\in\om\ra$ be as in the proof above.
Define $\ep_n=6^{-n}$ for $n\in\om$ and let $J_m^n$ be the closed intervals
of length $\ep_n$ defined by
$$J^n_m=[m\ep_n,(m+1)\ep_n]\mbox{ for }m\in\integer$$
For each $n$ these intervals cover $\real$ and
overlap only on their endpoints.

We will construct a sequence $\la I_n:n\in\om\ra$ of closed intervals such
that  $|I_n|\geq {1\over 2}\ep_n$. The $t$ we want will be in the
intersection of the $I_n$'s.

Let $I_0=\real$. Suppose that $n+1=k^j_i\in A_j$. Given $I_n$ with
$|I_n|\geq {1\over 2}\ep_n$, since $\ep_{n+1}={1\over 6}\ep_n$
we know that $|I_n|\geq 3\ep_{n+1}$ and therefore $g_j+I_n$ covers at
least two consecutive intervals of length $\ep_{n+1}$, say
 $$J^m_{n+1}\cup J^{m+1}_{n+1} \subseteq g_j+I_n $$
Now choose $\hat{m}\in\{m,m+1\}$ so that $\hat{m}$ is even iff $z(i)=0$.
Next choose $I_{n+1} \subseteq I_n$ with length at least ${1\over 2}\ep_{n+1}$
and so that $$g_j+I_{n+1} \subseteq {\rm interior}(J^{\hat{m}}_{n+1})$$
This finishes the construction of the sequence $\la I_n:n\in\om\ra$.

Let $t$ be the unique real in the intersection of all the $I_n$.
We claim that for each $j$ that $z\leq_T g_j+t$.  To calculate
$z(i)$ let $n+1=k^j_i$.  By our construction there exists
a unique $m$ such that $g_j+t\in J^m_{n+1}$ (we are assuming
that our coding of real numbers is such that we can effectively
find this $m$).  Then $z(i)=0$ iff $m$ is even.
\qed

\bigskip
The Theorem {\ref{miller}} follows from these two lemmas using an
argument similar to that of [M] (Lemma~{7.22} and Theorem~{7.21}).
\qed


\bigskip
Let us go back to Proposition {\ref{noborel}} (Borel set case).
We shall finish this section with a few comments.
It is not true in general that given
two perfect sets $P$ and $Q$ one can find $x\in\real$ such that
$(P+x)\cap Q$ is uncountable. To see this just take two disjoint
perfect sets $P$ and $Q$ which are subsets of perfect set
of algebraically independent reals. Then $|(P+x)\cap Q|\leq 1$
for every $x\in\real$.

The trick with a Cohen real from {\ref{noanalytic}} gives the
following alternative proof of {\ref{noborel}}.
We can assume that $B\in\Kat$.
Assume that $(A-x)\cap B$ is countable for every $x\in\real$. From
Lusin-Novikov Uniformization Theorem (see [K]) there exists
a sequence of Borel measurable functions $f_n:\real\to\real$ such that
$(A-x)\cap B\subseteq\{f_n(x):n<\om\}$.
For $y\in B$ we have $A-y \subseteq\bigcup_n f^{-1}_n (y)$.
So there exists $n<\om$ such that $f^{-1}_n (y)\notin\Kat$
for uncountably many $y\in B$.
But this is impossible because the Boolean
algebra $\Borel(\real)/\Kat$ satisfies the countable chain condition.

\section{Almost invariant subsets of countable groups}

Here we assume that $G$ is an Abelian group and $|G|=\om$.
We shall write $\FIN$ for the Frechet ideal $F_G$.

It is easy to see that Lemma {\ref{technics}} generalizes to
the case when $G$ can be written as a chain of finite subgroups
(this means simply that every element of $G$ has finite order).
This works e.g.~for $\cyclic_{p^{\infty}}$ or for the group
of rational rotations of the unit circle.

Consider now $(\integer,+)$. It is easy to see that almost invariant
subsets of $\integer$ are of four types.
They are equal (modulo $\FIN$) to either
$\emptyset$ or $\integer$ or $P:= \{n:n>0\}$ or $N:=\{n:n<0\}$.
Thus $P$ and $N$ are nontrivial. But the next lemma shows that
{\ref{technics}} cannot be generalized to all countable groups.

\begin{lemma}\label{notinzz}
Almost invariant subsets of $(\integer\times\integer,+)$ are trivial.
Similarly, almost invariant subsets of $(\rational,+)$ are trivial.
\end{lemma}
\proof Let $A\subseteq\integer\times\integer$.
Suppose on the contrary that $A$ and $B:=A^c$ are
almost invariant and $|A|=|B|=\om$.
Consider (horizontal) sections $A^m=\{n:\la n,m\ra\in A\}$.
Each such section must be almost invariant in $\integer$ and therefore,
is equal (modulo $\FIN$) to $\emptyset$, $\integer$, $P$ or $N$.
But observe that all sections must be of the same type.
Thus, (by passing to the complement if necessary) we may assume that
all nonempty sections have the greatest element.
Moreover, infinitely many sections must be nonempty. To obtain a
contradiction it suffices to shift $A$ by $\la 1,0\ra$.

The case of $(\rational,+)$ is left as an exercise.
\qed

\section{Almost invariant sets modulo an ideal}

In this section we consider $J$-almost invariant
subsets of the real line $\real$,
where $J$ is an ideal of subsets of $\real$ with a Borel base.
Recall that an ideal $J\subseteq\power(\real)$ has a Borel base, if for
every $X\in J$ there exists a Borel set $B\in J$ such that $X\subseteq B$.
Well known examples of such ideals
are the $\sigma$-ideals $\Leb$ and $\Kat$.
Recall also that a set $X\subseteq\real$ is called a {\em Bernstein set},
if $X\cap P\neq\emptyset\neq X^{c}\cap P$ for
every perfect set $P$.

\begin{theorem}\label{bernstein}
Suppose that $J$ is a proper invariant ideal on $\real$ with a Borel base
such that $\non(J)=\continuum$. Then there exists a nontrivial
$J$-almost invariant
set which is also a Bernstein set.
\end{theorem}
\proof
Let $Z\subseteq\continuum$ be such that $|Z|=|Z^{c}|=\continuum$
and let $\la P_\al:\al<\continuum\ra$ be an enumeration of all perfect
subsets of $\real$ such that each perfect set has an index both
in $Z$ and $Z^{c}$. We use Lemma {\ref{technics}} (with $A=\real$)
and obtain a sequence $\la t_\al:\al<\continuum\ra$.
Put $X=\bigcup_{\al\in Z} (G_\al+t_\al)$. It is easy to see that $X$
is a Bernstein set. From Lemma {\ref{technics}} we know that $X$
is almost invariant. Therefore $X$ is $J$-almost invariant
because $\non(J)=\continuum$.
It suffices to show that $X\notin J$ and $X^{c}\notin J$.
It follows from the fact that $X$ (and also $X^{c}$) is a Bernstein set.
Assume e.g.~that $X\in J$. Then there exists a Borel set $B\in J$
such that $X\subseteq B$.
Its complement $B^{c}$ is an uncountable Borel set and
therefore it contains a perfect set $P\subseteq B^{c}$.
But $X\cap P\neq\emptyset$. A contradiction.
\qed

\bigskip
It is a well known fact that Martin's Axiom implies that
$\add(\Leb)=\non(\Leb)=\continuum$ and also
$\add(\Kat)=\non(\Kat)=\continuum$ (see [J]).
Thus we have.

\begin{corollary}\label{underma}
Martin's Axiom implies that there are nontrivial $\Leb$-almost invariant
sets and nontrivial $\Kat$-almost invariant sets.
In fact under \MA\ there is a set which
is simultaneously nontrivial $\Leb$-almost invariant
and nontrivial $\Kat$-almost invariant.
\end{corollary}

We\footnote{
This was also proved in [L] (see Theorem~{8}).}
show that this cannot be proved in the theory \ZFC\ alone.

\begin{theorem}
Let $M$ be a transitive model of {\ZFC$+$\CH}.
Add $\om_2$ random reals to $M$ (by measure algebra).
Then in the generic extension $M[r_\al:\al<\om_2]$
there exists a nontrivial $\Kat$-almost invariant set but there are no
nontrivial $\Leb$-almost invariant sets.
\end{theorem}
\proof
Let $N=M[r_\al:\al<\om_2]$. It is well known that in the model $N$ we
have $\cov(\Leb)=\om_2=\continuum$. By Rothberger's theorem also
$\non(\Kat)=\continuum$ in $N$. Hence by Theorem {\ref{bernstein}}
there exists a nontrivial $\Kat$-almost invariant set.

{} To show that there are no nontrivial $\Leb$-almost invariant
sets we shall use Proposition {\ref{usecov}} for
the $\sigma$-ideal $\Leb$.
We have to show that in $N$ the following is true :
\begin{quote}
if $X=\{x_\al:\al<\om_2\}\notin\Leb$ then
$\{x_\al:\al<\beta\}\notin\Leb$
for some $\be<\om_2$.
\end{quote}
This fact is probably less known
but it is also a part of folklore (see [LM], Lemma~{8}).
Let us sketch the main idea of the proof.
We slightly abuse the notation by treating an object from $N$
as a {\em name} for it.
The required $\be$ will be the limit of an increasing sequence of
ordinals $\{\be_\delta:\delta<\om_1\}$.
Put $\be_0=\om$ and use limits at limit steps.
Having $\be_\delta$ look at the set $\B_\delta$
of all Borel sets from $\Leb$ coded in the submodel
$M[r_\al:\al<\be_\delta]$. Then $|\B_\delta|=\om_1$
because this submodel satisfies \CH.
As $X\notin\Leb$ it is possible to find
$\be_{\delta+1}>\be_\delta$ such that
for all $B\in\B_\delta$ there exists $\al<\be_{\delta+1}$
such that $x_\al\notin B$ and $x_\al\in M[r_\al:\al<\be_{\delta+1}]$.
Put $Y=\{x_\al:\al<\be\}$ and $M^\prime=M[r_\al:\al<\be]$.
It follows that $Y\in M^\prime$ and $M^\prime \models Y\notin\Leb$.
But the complementary extension, from $M^\prime$ to $N$ is
also by a measure algebra and it is known that it preserves
the Lebesgue outer measure. It follows that $N\models Y\notin\Leb$.
\qed

\bigskip
The above proof can be dualized for the Baire category.

\begin{theorem}
Let $M$ be a transitive model of {\ZFC$+$\CH}.
Add $\om_2$ Cohen reals to $M$ (by product forcing).
Then in the generic extension $M[c_\al:\al<\om_2]$
there exists a nontrivial $\Leb$-almost invariant set but there are no
nontrivial $\Kat$-almost invariant sets.
\end{theorem}

We don't know any model where there are no nontrivial
$\Leb$-almost invariant sets
nor nontrivial $\Kat$-almost invariant sets.
Surprisingly, in the iterated $\om_2$ Sacks model
we have the same effect as in Corollary {\ref{underma}} :
there exists\footnote{This fact was communicated to us by
K.~Ciesielski and J.~Pawlikowski.}
a set which is simultaneously nontrivial $\Leb$-almost invariant
and nontrivial $\Kat$-almost invariant.
Namely, it follows from the Covering Property Axiom (\CPA; see [CP])
that there exists a Hamel basis which consists of $\om_1$ closed sets.
It is possible then to repeat Sierpi\'{n}ski's construction.


\bigskip

\begin{center} {\bf References} \end{center}

\begin{itemize}

\item[{[CP]}] K.~Ciesielski and J.~Pawlikowski,
{\em A combinatorial core of the iterated perfect set model},
preprint.

\item[{[J]}] T.~Jech,
{\em Set Theory},
Academic Press, New York, 1978.

\item[{[K]}] A.~S.~Kechris,
{\em Classical Descriptive Set Theory},
Grad.~Texts in Math.~156, Springer, 1995.

\item[{[L]}] M.~Laczkovich,
{\em Two constructions of Sierpi\'{n}ski
and some cardinal invariants of ideals},
Real Analysis Exchange 24 (1998/9), 663-676.

\item[{[LM]}] M.~Laczkovich and A.~W.~Miller,
{\em Measurability of functions with approximately continuous
vertical sections and measurable horizontal sections},
Colloq.~Math. 69 (1995), 299-308.

\item[{[M]}] A.~W.~Miller,
{\em Infinite combinatorics and definability},
Ann.~Pure Appl.~Logic 41 (1989), 179-203.

\item[{[M1]}]
J.~Mycielski,
{\em Independent sets in topological algebras},
Fund.~Math.~65 (1964), 139-147.

\item[{[M2]}]
J.~Mycielski,
{\em Algebraic independence and measure},
Fund.~Math.~71 (1967), 165-169.

\item[{[Ox]}]
J.~C.~Oxtoby,
{\em Measure and category},
Springer, Berlin, 1970.

\item[{[S1]}]
W.~Sierpi\'{n}ski,
{\em Sur les translation des ensembles lineares},
Fund.~Math.~19 (1932), 22-28.

\item[{[S2]}]
W.~Sierpi\'{n}ski,
{\em Sur les translation des ensembles lineares},
Fund.~Math.~35 (1948), 159-164.

\end{itemize}

\bigskip

{\small\sc
\indent institute of mathematics, wroc{\l}aw university, \\
\indent pl.~grunwaldzki 2/4, 50--384 wroc{\l}aw, poland} \\
\indent {\em e--mail} : {\rm akamb@math.uni.wroc.pl}

\end{document}

%
% End of file EOF
%