% Version correcting typos from printed version; 9/18/2001

% Small correction by KC 5/31/2001
% spellchecked: 3/16/01 cew
% last edit: 3/16/01 cew
% gallies sent: 3-20-01pdh
% gallies corrected: 5-29-01pdh
% set in production style: 3/16/01 cew
% Inroads from Editor Brown
%% Send galleys to Ciesielski.

\documentclass{rae}
\usepackage{amsmath,amsthm,amssymb}

%\coverauthor{Krzysztof Ciesielski and Janusz Pawlikowski}
%\covertitle{Small Combinatorial Cardinal Characteristics and Theorems of Egorov and Blumberg}

\received{November 17, 2000}

\MathReviews{Primary 26A15, 03E35; Secondary 26A03, 03E17.}
\keywords{cofinality, null sets, uniform convergence,
Ramsey ultrafilter, Blumberg theorem, magic set.}

\firstpagenumber{905}

\markboth{Krzysztof Ciesielski and Janusz Pawlikowski}
{Small Combinatorial Cardinal Characteristics 
}

\author{
Krzysztof Ciesielski%
\thanks{Papers authored or
co-authored by a Contributing Editor are managed
by a Managing Editor or one of the other Contributing Editors.}%
,
Department of Mathematics, West Virginia
University, Morgantown, WV 26506-6310, USA,
email: {\tt K\_Cies@math.wvu.edu},
internet: {\tt http://www.math.wvu.edu/\~{}kcies}
\and
Janusz Pawlikowski%
\thanks{
The work of the second author was partially supported by
KBN Grant 2 P03A 031~14.}%
, Department of Mathematics, University of  Wroc\l aw,
pl. Grunwaldzki 2/4, 50-384 Wroc\l aw, Poland,
email: {\tt pawlikow@math.uni.wroc.pl} and \\
Department of Mathematics, West Virginia University,
Morgantown, WV 26506-6310, USA,  email: {\tt pawlikow@math.wvu.edu}
}

\title{SMALL COMBINATORIAL CARDINAL CHARACTERISTICS AND THEOREMS OF EGOROV
AND BLUMBERG}

%%%Put Author's Definitons Below Here%%%
\newcommand{\NN}{{\cal N}}
\newcommand{\cf}{{\rm cof}}

\newcommand{\real}{{\mathbb R}}
\newcommand{\R}{{\real}}
\newcommand{\la}{{\langle}}
\newcommand{\ra}{{\rangle}}
\newcommand{\B}{{\cal B}}
\newcommand{\F}{{\cal F}}
\newcommand{\I}{{\cal I}}
\newcommand{\M}{{\cal M}}
\newcommand{\W}{{\cal W}}

\renewcommand{\split}{{\mathfrak s}}

% characteristic function
     \newcommand{\charf}[1]{\mbox{\raise.48ex\hbox{$\chi$}$_{#1}$}}

\def\cof{{\rm cof}}
\def\continuum{{\mathfrak c}}
\def\co{\continuum}
\def\range{{\rm range}}

\newcommand{\add}{{\rm add}}

%% Theorems, etc.

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}

\newcommand{\thm}[2]{\begin{theorem}\label{#1}{\sl #2}\end{theorem}}
\newcommand{\cor}[2]{\begin{corollary}\label{#1}{\sl #2}\end{corollary}}
\newcommand{\prop}[2]{\begin{proposition}\label{#1}{\sl #2}\end{proposition}}
\newcommand{\lem}[2]{\begin{lemma}\label{#1}{\sl #2}\end{lemma}}
\newcommand{\ex}[2]{\begin{example}\label{#1}{\sl #2}\end{example}}

%%%%%%
\begin{document}
\maketitle

\begin{abstract}
We will show that the following set theoretical assumption
\begin{quote}
$\continuum=\omega_2$, the dominating number
${\mathfrak d}$ equals to $\omega_1$,
and there exists an $\omega_1$-generated
Ramsey ultrafilter on $\omega$
\end{quote}
(which is consistent with ZFC) implies that for
an arbitrary sequence
$f_n\colon\real\to\real$ of uniformly bounded functions
there is a set $P\subset\real$ of cardinality continuum
and an infinite $W\subset\omega$
such that
$\{f_n\restriction P\colon n\in W\}$ is a monotone uniformly
convergent sequence of uniformly continuous functions.
Moreover, if
functions $f_n$ are measurable or have the Baire property then
$P$ can be chosen as a perfect set.

We will also show that $\cof(\NN)=\omega_1$ implies existence
of a magic set and of a function
$f\colon\real\to\real$ such that
$f\restriction D$ is discontinuous for every $D\notin\NN\cap\M$.
\end{abstract}


%\section{Preliminaries}



Our set theoretic terminology is standard and follows that of~\cite{CiBook}.
In particular, $|X|$ stands for the cardinality of a set $X$
and $\continuum=|\real|$.
We are using symbols $\NN$ and $\M$
to denote the ideals of Lebesgue measure zero
and meager subsets of
$\real$, respectively. For the ideal $\I\in\{\M,\NN\}$ its
{\em cofinality}\/  is defined by
$\cof(\I)=\min\{|\B|\colon \B\subset\I\mbox{ generates } \I\}$.
A set $L\subset\real$ is a
{\em $\kappa$-Luzin set\/} if $|L|=\kappa$ but
$|L\cap N|<\kappa$ for every nowhere dense subset $N$ of $\real$.
Recall that Martin's Axiom, MA,  implies the existence of
a $\continuum$-Luzin set.
The {\em dominating number}\/ is defined as
\[
{\mathfrak d}=\min\left\{|T|\colon T\subset\omega^\omega\ \&\
      (\forall f\in \omega^\omega) (\exists g\in T)
      (\forall n<\omega)\ f(n)<g(n)\right\}.
\]
It is well known that $\omega_1\leq{\mathfrak d}\leq\cof(\NN)$.
(See e.g.~\cite{BJ}.)
In this paper we use term {\em Polish space}\/
for a complete separable metric space {\tt without
isolated points}.


\section{On a Convergence of Subsequences}

This section can be viewed as an extension of the discussion
around Egorov's theorem presented in~\cite[Ch. 9]{Kh}.
In 1932 Mazurkiewicz~\cite{Maz} proved the following variant
of Egorov's theorem, where
a sequence $\la f_n\ra_{n<\omega}$ of real-valued functions is
{\em uniformly bounded}\/
provided there exists an $r\in\real$ such that $\range(f_n)\subset[-r,r]$
for every $n$.

\medskip\noindent{\bf Mazurkiewicz's Theorem}
{\it Every uniformly bounded sequence $\la f_n\ra_{n<\omega}$
of real-valued continuous functions
defined on a Polish space $X$
has a subsequence which is uniformly convergent on some perfect set $P$.}

\medskip Of course Mazurkiewicz' theorem cannot be proved if we do not assume
some regularity of the functions $f_n$ even if $X=\real$.
But is it at least true that
\begin{itemize}
\item[($*$)]
for every
uniformly bounded sequence $\la f_n\colon\real\to\real\ra_{n<\omega}$
the conclusion of Mazurkiewicz' theorem
holds for some $P\subset\real$ of cardinality $\continuum$?
\end{itemize}
The consistency of the negative answer follows from
the next example, which is essentially due
to Sierpi\'nski~\cite{Sier}.%
\footnote{Sierpi\'nski constructed this example under
the assumption of the Continuum Hypothesis.}
(See~\cite[pp.~193-194]{Kh}, where it is proved under the
assumption of the existence of $\omega_1$-Luzin set.
The same proof works also for our more general statement.)

\ex{exSierpKhara}{Assume that there exists a $\kappa$-Luzin set.
Then for every 
$X$ of cardinality $\kappa$ 
%Polish space $X$ 
there exists a sequence 
$\la f_n\colon X\to\{0,1\}\ra_{n<\omega}$ with the property that
for every $W\in[\omega]^\omega$ the subsequence
$\la f_n\ra_{n\in W}$ converges pointwise
for less than $\kappa$-many points $x\in X$.

In particular, under Martin's Axiom the above sequence exists 
for 
every Polish space $X$ and 
$\kappa=\continuum$. 
}
%
Note also that under MA the above example can hold only for $\kappa=\continuum$,
since MA implies that
\begin{quote}
for every set $S$ of cardinality less than $\continuum$
every uniformly bounded sequence $\la f_n\colon S\to\real\ra_{n<\omega}$
has a pointwise convergent subsequence.
\end{quote}
(See~\cite[p.~195]{Kh}.)
Sharper results
concerning the above two facts were recently obtained
by Fuchino and Plewik~\cite{FP}, in which they relate them
to the splitting number $\split$.
(For the definition of $\split$ see e.g.~\cite{BJ}.
For us it is only important that
$\omega_1\leq\split\leq{\mathfrak d}$.)
More precisely, the authors show there that:
{\it For any $X\in[\real]^{<\split}$ any sequence
$\la f_n\colon X\to[-\infty,\infty]\ra_{n<\omega}$ has a
subsequence convergent pointwise on $X$; however for
any $X\in[\real]^{\split}$ there exists a sequence
$\la f_n\colon X\to[0,1]\ra_{n<\omega}$
with no pointwise convergent subsequence.}


Our main goal of this section is to prove that ($*$)
is consistent with (so, by the example, also independent from)
the usual axioms of set theory ZFC.
To state this precisely we need the following terminology and facts.

A maximal non-principal filter $\F$ on $\omega$ is said to be
{\em Ramsey}\/ provided for every $B\in\F$
and $h\colon[B]^2\to\{0,1\}$ there exist $i<2$ and
$A\in\F$ such that $A\subset B$ and $h\left[ [A]^2\right]=\{i\}$.
We say that a family $\W\subset\F$ {\em generates}\/ filter $\F$
provided for every $F\in\F$ there exists a $W\in\W$ such that $W\subset F$.

\thm{thmSeqConv}{Assume that ${\mathfrak d}=\omega_1$
and there exists a Ramsey ultrafilter $\F$ on $\omega$
generated by a family $\W\subset\F$ of cardinality $\omega_1$.

Let $X$ be an arbitrary set
and $\la f_n\colon X\to\real\ra_{n<\omega}$ be a sequence of
functions such that the set $\{f_n(x)\colon n<\omega\}$
is bounded for every $x\in X$. Then
there are sequences:
$\la P_\xi\colon\xi<\omega_1\ra$ of subsets of $X$
and $\la W_\xi\in\F\colon\xi<\omega_1\ra$
such that $X=\bigcup_{\xi<\omega_1}P_\xi$ and for every $\xi<\omega_1$:
\begin{quote}
the sequence
$\la f_n\restriction P_\xi\ra_{n\in W_\xi}$ is
monotone and uniformly convergent.
\end{quote}
}

The conclusion of Theorem~\ref{thmSeqConv} is obvious for
sets $X$ with cardinality $\leq\omega_1$,
since sets $P_\xi$ can be chosen just as singletons.
Thus, we will be interested in the theorem only for the sets
$X$ of cardinality greater than $\omega_1$.
If $X$ is a Polish space this
leads to $\continuum=|X|>\omega_1$.
Luckily, the assumptions of Theorem~\ref{thmSeqConv}
are consistent with ZFC+``$\continuum=\omega_2$''.
This holds in the iterated perfect set model.
More precisely, the fact that in this model we have
$\continuum=\omega_2$  and $\cf(\NN)=\omega_1$
can be
found in~\cite[p. 339]{BJ}.
The fact that in this model there exists a desired
Ramsey ultrafilter has been proved in
Baumgartner, Laver~\cite{BL}.
(They proved there that there exists a selective
$\omega_1$-generated ultrafilter on $\omega$.
But it is well known that an ultrafilter on $\omega$ is
selective if and only if it is Ramsey.)
All these facts follow also from the axiom CPA,
which is a subject of a forthcoming monograph~\cite{CPAbook}.
(Some of the results proved here may also
be included in~\cite{CPAbook} as the examples
of interesting consequences of CPA.)

In particular, we get the following corollary which, under
additional set theoretical assumptions, generalizes
Mazurkiewicz' theorem and implies~($*$).


\cor{cor1}{
\begin{sloppypar}It is consistent with ZFC+``$\continuum=\omega_2$''
that for each Polish space $X$
and each uniformly bounded sequence $\la f_n\colon X\to\real\ra_{n<\omega}$
there exist sequences:
$\la P_\xi\colon\xi<\omega_1\ra$ of subsets of $X$
and $\la W_\xi\in[\omega]^\omega\colon\xi<\omega_1\ra$
such that $X=\bigcup_{\xi<\omega_1}P_\xi$ and for every $\xi<\omega_1$:
\begin{quote}
the sequence
$\la f_n\restriction P_\xi\ra_{n\in W_\xi}$ is
monotone and uniformly convergent.
\end{quote}
In particular, there exists a $\xi<\omega_1$
such that $|P_\xi|=\continuum$.

Moreover, if functions $f_n$ are
continuous then we can additionally require that
all sets $P_\xi$ are closed in $X$.
\end{sloppypar}
}

\noindent {\sc Proof.} The main part follows immediately from the discussion above
and the Pigeon Hole Principle.
To see the additional part it is enough to note that
for continuous functions sets $P_\xi$ can be replaced by their closures,
since for any sequence $\la f_n\colon P\to\real\ra_{n<\omega}$ of
continuous functions if $\la f_n\restriction D\ra_{n<\omega}$
is monotone and uniformly convergent for some dense subset $D$ of $P$
then so is~$\la f_n\ra_{n<\omega}$.
\qed

\medskip \noindent{\sc Proof of Theorem~\ref{thmSeqConv}.}
For every $x\in X$ define $h_x\colon[\omega]^2\to\{0,1\}$
by putting for every $n<m<\omega$
\begin{center}
$h_x(n,m)=1$ if and only if $f_n(x)\leq f_m(x)$.
\end{center}
Since $\F$ is Ramsey and $\W$ generates $\F$
we can find a $W_x\in\W$
and an $i_x<2$ such that $h_x[[W_x]^2]=\{i_x\}$.
Thus, the sequence $S_x=\la f_n(x)\ra_{n\in W_x}$ is monotone.
It is increasing when $i_x=1$ and it is decreasing for $i_x=0$.


For $W\in\W$ and $i<2$  let $P_W^i=\{x\in X\colon W_x=W\ \&\ i_x=i\}$.
Then $\{P^i_W\colon W\in\W\ \&\ i<2\}$ is a partition of $X$ and
for every $W\in\W$ and $i<2$ the sequence
$\la f_n\restriction P^i_W\ra_{n\in W}$
is monotone and pointwise convergent to some
function $f\colon P^i_W\to\real$.

To get uniform convergence
note that for every $x\in P^i_W$ there exists an $s_x\in\omega^\omega$
such that
\[
(\forall k<\omega)\ (\forall n\in W\setminus s_x(k))\
|f_n(x)-f(x)|<2^{-k}.
\]
Since ${\mathfrak d}=\omega_1$, there exists a
$T\in[\omega^\omega]^{\omega_1}$  dominating $\omega^\omega$.
In particular, for every
$x\in P^i_W$ there exists a $t_x\in T$ such that
$s_x(n)\leq t_x(n)$ for all $n<\omega$.
For $t\in T$ let
\[
P^i_W(t)=\{x\in P^i_W\colon t_x=t\}.
\]
Since
every sequence
$\la f_k\restriction P^i_W(t)\ra_{k\in W}$
is monotone and uniformly convergent,
%$\{P^i_W(t)\colon i<2,\ W\in\W,\ t\in T\}$
%is the desired covering, 
%$\{P_\xi\colon\xi<\omega_1\}$ of $X$, 
$\{P^i_W(t)\colon i<2,\ W\in\W,\ t\in T\}$
is the desired covering 
$\{P_\xi\colon\xi<\omega_1\}$ of $X$. 
\qed



\section{$\cf(\NN)=\omega_1$, Blumberg Theorem, and Magic Set}

In this section we will show two consequences of
$\cof(\NN)=\omega_1$.


In 1922 Blumberg~\cite{Bl} proved that
{\em for every $f\colon\real\to\real$ there
exists a dense subset $D$ of\/ $\real$ such that
$f\restriction D$ is continuous}. This theorem sparked a
lot of discussion and generalizations, see
e.g.~\cite[pp.~147--150]{KCsurv}.
In particular, Shelah~\cite{Sh2} showed that there is a model
of ZFC in which
{\em for every $f\colon\real\to\real$ there is a nowhere meager
subset $D$ of\/ $\real$ such that
$f\restriction D$ is continuous.}
The dual measure result, that is the consistency of a statement
{\em for every $f\colon\real\to\real$ there is a
subset $D$ of\/ $\real$ of positive outer Lebesgue measure such that
$f\restriction D$ is continuous},
has been also recently established by
Ros\l anowski and Shelah~\cite{RS}.
Below we note that each of these properties
contradicts $\cof(\NN)=\omega_1$.
(We use here the well known inequality $\cof(\M)\leq\cof(\NN)$.
See e.g.~\cite{BJ}.)



\thm{th:blum}{Let $\I\in\{\NN,\M\}$. If $\cof(\I)=\omega_1$
then there exists an $f\colon\real\to\real$ such that
$f\restriction D$ is discontinuous for every $D\in{\cal P}(\real)\setminus\I$.
}

\noindent {\sc Proof.}  We will assume that $\I=\NN$, the proof for $\I=\M$ being essentially
identical.

Let $\{N_\xi\subset\real^2\colon \xi<\omega_1\}$ be a family
cofinal in the ideal of null subsets of $\real^2$
and for each $\xi<\omega_1$ let
\[
N_\xi^*=\{x\in\real\colon (N_\xi)_x\notin\NN\},
\]
where
$(N_\xi)_x=\{y\in\real\colon \la x,y\ra\in N_\xi\}$.
By Fubini's theorem each $N_\xi^*$ is null.
For each $x\in N_\xi^*\setminus\bigcup_{\zeta<\xi}N_\zeta^*$ we choose
$f(x)$ so that
\[
f(x)\notin\bigcup_{\zeta<\xi}(N_\zeta)_x.
\]
Then function $f$ is as desired.

Indeed, if $f\restriction D$ is continuous for some $D\subset\real$
then $f\restriction D$ is null in $\real^2$. In particular,
there exists a $\xi<\omega_1$ such that
$f\restriction D\subset N_\xi$. But this means that
$D\subset\bigcup_{\zeta\leq\xi}N_\zeta^*$. \qed

Note that essentially the same proof works
if we assume only that $\cof(\I)$
is equal to the additivity number $\add(\I)$ of $\I$.



\cor{cor:Blum}{Assume $\cof(\NN)=\omega_1$. Then there exists an
$f\colon\real\to\real$ such that
if $f\restriction D$ is continuous then $D\in\NN\cap\M$.
}

\noindent {\sc Proof.} Let $f_\NN$ and $f_\M$ be from
Theorem~\ref{th:blum} constructed for the ideals $\NN$ and $\M$,
respectively.
Let $G\subset\real$ be a dense $G_\delta$ of measure zero
and put
$f=[f_\M\restriction G]\cup [f_\NN\restriction (\real\setminus G)]$.
Then this $f$ is as desired. \qed


Recall that a set $M\subset\real$ is a {\em magic set}\/ (or
{\em set of range uniqueness}\/)
if for every different nowhere constant
functions $f,g\in C(\real)$ we have $f[M]\neq g[M]$.
It has been proved by Berarducci and Dikranjan \cite[thm. 8.5]{BD}
that a magic set exists under CH.
We like to note here that the same is implied by
a much weaker assumption that $\cof(\M)=\omega_1$.
However, the existence of a magic set
is independent of ZFC, as proved
by Ciesielski and Shelah in~\cite{CShel}.

\prop{propMagic}{If $\cof(\M)=\omega_1$ then there exists a magic set.}

\noindent {\sc Proof.} An uncountable set $L\subset\real$ is a {\em 2-Luzin set}\/
provided for every disjoint subsets $\{x_\xi\colon \xi<\omega_1\}$
and $\{y_\xi\colon \xi<\omega_1\}$ of $L$, where
the enumerations are one-to-one,
the set of pairs $\{\la x_\xi,y_\xi\ra\colon \xi<\omega_1\}$
is not a meager subset of $\real^2$.
In \cite[prop. 4.8]{BC} it was noticed that
every $\omega_1$-dense 2-Luzin set is a magic set.
It is also a standard and easy diagonal argument that
$\cof(\M)=\omega_1$ implies
the existence of a $\omega_1$-dense 2-Luzin set.
(The proof presented in \cite[prop. 6.0]{To}
works also under the assumption $\cof(\M)=\omega_1$.)
So, $\cof(\M)=\omega_1$ implies that there is a magic set.
\qed

Recall also that the existence of a magic set for the
class $D^1$ of all differentiable functions can be proved in ZFC.
This follows from \cite[thm.~3.1]{BC2},
since every function from $D^1$ belongs to the class $(T_2)$.
(Compare also \cite[cor.~3.3 and 3.4]{BC2}.)






\begin{thebibliography}{22}

\bibitem{BJ} T.~Bartoszy\'{n}ski, H.~Judah,
{\em Set Theory}, A~K~Peters, 1995.

\bibitem{BL} J.~Baumgartner, R.~Laver,
{\em Iterated perfect-set forcing},
%Annals of Mathematical Logic
Ann. Math. Logic {\bf 17} (1979), 271--288.

\bibitem{BD} A. Berarducci, D. Dikranjan, {\it Uniformly approachable
functions and $UA$ spaces}, Rend. Ist. Matematico Univ. di Trieste {\bf 25}
(1993), 23--56.



\bibitem{Bl}  H.~Blumberg, {\it New properties of all real functions},
Trans. Amer. Math. Soc. {\bf 24} (1922), 113--128.

\bibitem{BC} M.~R.~Burke, K.~Ciesielski, {\it Sets on which measurable
functions are determined by their range}, Canad. J. Math. {\bf 49} (1997),
1089--1116.
(Preprint$^\star$ available.%
\footnote{Preprints marked by $^\star$ are available in electronic form
from {\it Set Theoretic Analysis Web Page:}
http://www.math.wvu.edu/\~{}kcies/STA/STA.html})


\bibitem{BC2} M.~R.~Burke, K.~Ciesielski,
{\it Sets of range uniqueness for classes of continuous functions},
Proc. Amer. Math. Soc. {\bf 127} (1999), 3295--3304.
(Preprint$^\star$ available.)


\bibitem{KCsurv} K.~Ciesielski,
{\it Set theoretic real analysis}, J. Appl. Anal. {\bf 3}(2) (1997), 143--190.
(Preprint$^\star$ available.)

\bibitem{CiBook} K.~Ciesielski,
{\it Set Theory for the Working Mathematician},
London Math. Soc. Stud. Texts {\bf 39}, Cambridge Univ. Press 1997.

\bibitem{CPAbook}
K.~Ciesielski, J.~Pawlikowski,
{\it Covering property axiom CPA},
work in progress$^\star$.

\bibitem{CShel}  K.~Ciesielski, S.~Shelah, {\it Model with no magic set},
J. Symbolic Logic {\bf 64(4)} (1999), 1467--1490.
(Preprint$^\star$ available.)

\bibitem{FP} S.~Fuchino, Sz.~Plewik, {\it On a theorem of E.~Helly},
Proc. Amer. Math. Soc. {\bf 127(2)} (1999), 491--497.

\bibitem{Kh} A.~B. Kharazishvili, {\it Strange Functions in Real Analysis},
Pure and Applied Mathematics
{\bf 229}, Marcel Dekker, 2000.

\bibitem{Maz}  S.~Mazurkiewicz, {\it Sur les suites de fonctions
continues}, Fund. Math. {\bf 18} (1932), 114--117.

\bibitem{RS} A.~Ros\l anowski, S.~Shelah, {\it Measured Creatures},
preprint.

\bibitem{Sh2}  S.~Shelah,
{\it Possibly every real function is continuous on a
non--meagre set}, Publ. Inst. Mat. (Beograd) (N.S.)
{\bf 57}(71) (1995), 47--60.

\bibitem{Sier}  W.~Sierpi\'nski, {\it Remarque sur les suites infinies de
fonctions (Solution d'un probl\` eme de M.~S.~Saks)},
Fund. Math. {\bf 18} (1932), 110--113.

\bibitem{To} S.~Todorcevic, {\em Partition problems in topology},
Contemp.  Math. {\bf 84}, Amer.  Math.  Soc. 1989.



\end{thebibliography}

\end{document}
\end{document}