\documentclass[12pt]{article}
\usepackage{amssymb}

\newcommand{\UpdateDate}{January 25, 2004}

\date{}
 
\title{Small coverings with smooth functions  
under the Covering Property Axiom
}


\pagestyle{myheadings}

\newcommand{\reap}{{\mathfrak r}}
\newcommand{\ultraN}{{\mathfrak u}}
\newcommand{\spleat}{{\mathfrak s}}
\newcommand{\madN}{{\mathfrak a}}
\newcommand{\indN}{{\mathfrak i}}


\markboth{K.~Ciesielski and J.~Pawlikowski
\ \ \ \ \ \UpdateDate
}{Small coverings with smooth functions  
under CPA \ \ \ \ \ \UpdateDate
}

 
\author{
Krzysztof Ciesielski%
\thanks{%\endgraf 
%%%The work of the first author was partially supported by 
%%%NSF Cooperative
%%%Research Grant INT-9600548, with its Polish part %being 
%%%financed by Polish Academy of Science PAN.\endgraf
AMS classification numbers: Primary 26A24; Secondary 03E35. \endgraf
\ \ Key words and phrases: continuous, smooth, covering.\endgraf 
\ \ The work of the first author was partially supported by 
NATO Grant PST.CLG.977652 and 2002/03 West Virginia
University Senate Research Grant.
}
\\
{\footnotesize Department of Mathematics,}
{\footnotesize West Virginia University,} \\
{\footnotesize Morgantown, WV 26506-6310, USA}\\
{\footnotesize e-mail: K\_Cies@math.wvu.edu}; %\\
{\footnotesize web page: {\tt http://www.math.wvu.edu/\~{}kcies}}
\and
Janusz Pawlikowski\thanks{
The second
author wishes to thank West Virginia University for its hospitality
during 1998--2001, where the results presented here were obtained. 
}\\
{\footnotesize Department of Mathematics,}
{\footnotesize University of  Wroc\l aw,} \\
{\footnotesize pl. Grunwaldzki 2/4, 50-384 Wroc\l aw, Poland;} %\\
{\footnotesize e-mail: pawlikow@math.uni.wroc.pl}
}

\newcommand{\new}{\marginpar{{\tiny NEW}}}
\newcommand{\ch}[1]{\marginpar{{\tiny #1}}}


\newcounter{ChartNo}
\newcommand{\Ccounter}{\refstepcounter{ChartNo}\theChartNo}


\newcommand{\forces}{\mathrel{\|}\joinrel\mathrel{-}}
\newcommand{\dec}{{\rm dec}}

\newcommand{\ignore}[1]{}
\newcommand{\IntTh}{{\rm IntTh}}
\newcommand{\Implies}{\Longrightarrow}
\newcommand{\SoIC}{{s_0^{\rm prism}}}
\newcommand{\SoST}{{s_0^{\rm cube}}}
\newcommand{\psm}{{\rm CPA}}
\newcommand{\psmC}{\mbox{{\rm CPA$_{\rm cube}$}}}
\newcommand{\psmP}{\mbox{{\rm CPA$_{\rm prism}$}}}
\newcommand{\psmCsec}{\mbox{{\rm CPA$_{\rm cube}^{\rm sec}$}}}
\newcommand{\psmPsec}{\mbox{{\rm CPA$_{\rm prism}^{\rm sec}$}}}
\newcommand{\psmPLUS}{{\rm CPA$_{\rm cube}^+$}}
\newcommand{\psmPrPLUS}{{\rm CPA$_{\rm prism}^+$}}
\newcommand{\psmPrGame}{{\rm CPA$_{\rm prism}^{\rm game}$}}
\newcommand{\psmCGame}{{\rm CPA$_{\rm cube}^{\rm game}$}}
\newcommand{\cpa}{{\rm CPA}}
\newcommand{\cf}{{\rm cof}}
\newcommand{\code}{{\rm code}}
\newcommand{\suc}{{\rm succ}}
%\newcommand{\cc}{{\rm con}}
\newcommand{\ccc}{{\rm con}}
\newcommand{\supp}{{\rm supp}}
\newcommand{\nor}{{\rm norm}}
\newcommand{\norsup}{{\rm\underline{norm}}}
\newcommand{\sq}{\subseteq}
\newcommand{\mathPerf}{{\mathbb P}}
\newcommand{\mathS}{{\mathbb S}}
\newcommand{\mathF}{{\mathbb F}}
\newcommand{\real}{{\mathbb R}}
\newcommand{\R}{{\real}}
\newcommand{\rational}{{\mathbb Q}}
\newcommand{\Q}{{\rational}}
\newcommand{\integer}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}} 
\newcommand{\NN}{{\cal N}}
\newcommand{\nnn}{{\rm N}}
\newcommand{\Sg}{{\Sigma}}
\newcommand{\s}{{\sigma}}
\newcommand{\h}{{\aleph}}
\newcommand{\la}{{\langle}}
\newcommand{\ra}{{\rangle}}
\newcommand{\restr}{{\hbox{$\,|\grave{}\,$}}}
\newcommand{\srestr}{{\hbox{${\scriptstyle\,|\grave{}\,}$}}}
\newcommand{\A}{{\cal A}}
\newcommand{\B}{{\cal B}}
\newcommand{\C}{{\cal C}}
\newcommand{\D}{{\cal D}}
\newcommand{\E}{{\cal E}}
\newcommand{\F}{{\cal F}}
\newcommand{\G}{{\cal G}}
%\renewcommand{\H}{{\cal H}}
\newcommand{\I}{{\cal I}}
\newcommand{\J}{{\cal J}}
\newcommand{\K}{{\cal K}}
\newcommand{\M}{{\cal M}}
\renewcommand{\P}{{\cal P}}
\newcommand{\T}{{\cal T}}
\newcommand{\U}{{\cal U}}
\newcommand{\W}{{\cal W}}
\newcommand{\V}{{\cal V}}
\newcommand{\e}{{\varepsilon}}
\newcommand{\p}{{\varphi}}
\newcommand{\g}{{\gamma}}
\renewcommand{\d}{{\delta}}
\newcommand{\const}{{\rm Const}}
\newcommand{\bor}{\mbox{${\cal B}or$}}
\newcommand{\nd}{\I_{\rm nd}}

\newcommand{\Fcube}{{\cal F}_{\rm cube}}
\newcommand{\Ccube}{{\cal C}_{\rm cube}}
\newcommand{\Fpr}{{\cal F}_{\rm prism}}
\newcommand{\Cpr}{{\cal C}_{\rm prism}}

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



%\newcommand{\proj}{\operatorname{pr}}
%\newcommand{\proj}{\mathop{\rm pr}}
\newcommand{\proj}{{\pi}}

\def\lin{{\rm LIN}}

\def\cof{{\rm cof}}
\def\cl{{\rm cl}}
\def\diam{{\rm diam}}
\def\dist{{\rm dist}}
\def\inter{{\rm int}}
\def\bd{{\rm bd}}
\def\continuum{{\mathfrak c}}
\def\co{\continuum}
\def\Cantor{{\mathfrak C}}
\def\la{\langle}
\def\ra{\rangle}

\def\dom{{\rm dom}}
\def\range{{\rm range}}

\def\proof{\noindent {\sc Proof. }}
\def\qed{\hfill\vrule height6pt width6pt depth1pt\medskip}
\def\endproof{{\qed}}
\def\AA{{\cal A}}
\newcommand{\tr}{{\rm tr}}
\newcommand{\sru}{{\rm sru}}
\newcommand{\perf}{{\rm Perf}}
\newcommand{\cov}{{\rm cov}}
\newcommand{\add}{{\rm add}}

\def\implies{\longrightarrow}
\newcommand{\Equi}{\Leftrightarrow}

 
%% Theorems, etc.

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{Fact}[theorem]{Fact}
\newtheorem{Claim}[theorem]{Claim}

\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{\pr}[2]{\begin{problem}\label{#1}{\rm #2}\end{problem}}
\newcommand{\ex}[2]{\begin{example}\label{#1}{\sl #2}\end{example}}
\newcommand{\defi}[2]{\begin{definition}\label{#1}{\rm #2}\end{definition}}
\newcommand{\rem}[2]{\begin{remark}\label{#1}{\rm #2}\end{remark}} 
\newcommand{\fact}[2]{\begin{Fact}\label{#1}{\sl #2}\end{Fact}} 
\newcommand{\claim}[2]{\begin{Claim}\label{#1}{\sl #2}\end{Claim}}

 
\begin{document}
 
\maketitle



\begin{abstract}
In the paper we formulate a Covering Property Axiom \psmP,
which holds in the iterated perfect set model, 
and show that it implies the following facts
of which (a) and (b) are the generalizations 
of results of Stepr\={a}ns~\cite{St2}. 
\begin{itemize}
\item[(a)]
There exists a family $\F$ of less then continuum many
$\C^1$ functions from $\real$ to $\real$ 
such that $\real^2$ is covered by
functions from $\F$ in the sense that 
for every $\la x,y\ra\in\real^2$ there exists an
$f\in\F$ such that either $f(x)=y$ or $f(y)=x$. 

\item[(b)]
For every Borel function $f\colon\real\to\real$ there exists
a family $\F$ of less than continuum many ``$\C^1$'' functions
(i.e., differentiable functions 
with continuous derivatives, where derivative can be infinite)
whose graphs cover the graph of $f$. 

\item[(c)]
For every $n>0$ and 
a $D^n$ function $f\colon\real\to\real$ there exists
a family $\F$ of less than continuum many $\C^n$ functions
whose graphs cover the graph of $f$. 
\end{itemize}
We also provide the examples showing that 
in the above properties the smotheness conditions are the best
possible. Parts (b), (c), and the examples are closely related
to work of Olevski\v{\i}~\cite{Ol}. 
\end{abstract}

\section{Basic notation} 
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|$. 
The Cantor set $2^\omega$ will be denoted by a symbol $\Cantor$. 
We use term {\em Polish space}\/
for a complete separable metric space {\tt without
isolated points}. 
A subset of a Polish space is {\it perfect}\/ if it is closed 
and contains no isolated points. 
For a Polish space $X$ symbol $\perf(X)$
will stand for a 
collection of all subsets of $X$ homeomorphic to the Cantor set $\Cantor$.
Thus, in general, $\perf(X)$ is just a (coinitial) subfamily 
of the family of perfect subsets of $X$, though these two collections coincide
if $X$ is zero dimensional. 
For a fixed $0<\alpha<\omega_1$ and $0<\beta\leq\alpha$
a symbol $\pi_\beta$\label{PageProjPi} 
will stand for the projection  
from $\Cantor^{\alpha}$ onto $\Cantor^\beta$.
We will always consider $\Cantor^\alpha$
with the following standard metric $\rho$:
fix an enumeration
$\{\la \beta_k,n_k\ra\colon k<\omega\}$ of
$\alpha\times\omega$ and 
for distinct $x,y\in\Cantor^\alpha$ define
\begin{equation}\label{eqRHO}
\rho(x,y)=2^{-\min\{k<\omega\colon x(\beta_k)(n_k)\neq y(\beta_k)(n_k)\}}.
\end{equation}
An open ball in $\Cantor^\alpha$ 
with a center at $z\in\Cantor^\alpha$ and radius $\e>0$
will be denoted by $B_\alpha(z,\e)$.\label{PageBallB} 
Notice that in this metric any two open balls are either disjoint 
or one is a subset of the other. 
Also for every $\gamma<\alpha$ 
\begin{equation}\label{eq18x}
\pi_\gamma[B_\alpha(s,\e)]=\pi_\gamma[B_\alpha(t,\e)] \ \ 
\mbox{ for every $s,t\in\Cantor^\alpha$ with 
$s\restriction \gamma=t\restriction \gamma$. }
\end{equation}
It is also easy to see that any $B_\alpha(z,\e)$
is a clopen set.

We will use standard notation for the classes of 
differentiable partial functions from $\real$ into $\real$.
Thus, if $X$ is an arbitrary subset of $\real$
without isolated points 
we will write $\C^0(X)$ or $\C(X)$ for the class
of all continuous functions $f\colon X\to\real$
and $D^1(X)$ for the class of all differentiable functions $f\colon X\to\real$,
that is, those for which the limit 
$$
f'(x_0)=\lim_{x\to x_0,\ x\in X}\frac{f(x)-f(x_0)}{x-x_0}
$$ 
exists and is finite for all $x_0\in X$. 
Also, for $0<n<\omega$
we will write $D^n(X)$\label{PageDsupN}
to denote the class of all functions 
$f\colon X\to\real$ which are 
$n$-times differentiable with all derivatives being finite
and $\C^n(X)$\label{PageCsupN} 
for the class of all $f\in D^n(X)$ whose $n$-th derivative $f^{(n)}$ 
is continuous. 
Symbol $\C^\infty(X)$\label{PageCinf} 
will be used for all infinitely many times differentiable functions
from $X$ into $\real$. 
In addition, we say that 
a function $f\colon X\to\real$
is in the class 
``$D^n(X)$'' if $f\in\C^{n-1}(X)$ and it has 
the $n$-th derivative which can be infinite; $f$ 
is in the class
``$\C^n(X)$'' when  $f$ is in ``$D^n(X)$'' and 
its $n$-th derivative is continuous when its range
$[-\infty,\infty]$ is considered with the standard topology. 
``$\C^\infty(X)$'' will stand for all functions $f\colon X\to\real$
which are either in $\C^\infty(X)$ or, for some $0<n<\omega$, they are
in ``$\C^n(X)$'' and $f^{(n)}$ is constant equal to $\infty$ or $-\infty$. 
(Thus, in general, ``$\C^\infty(X)$'' is not a subclass of ``$\C^n(X)$.'')
In addition we assume that functions defined on a singleton
are in the $\C^\infty$ class, that is, $\C^\infty(\{x\})=\real^{\{x\}}$.
We will use these symbols mainly for $X$'s which are either in the class
$\perf(\real)$ or are the singletons. 
In particular, $\C^n_{\rm perf}$\label{PageCnPERF} 
will stand for the union of all 
$\C^n(P)$ for which $P\subset \real$ is either in $\perf(\real)$ or a 
{\tt singleton}.  The classes $D^n_{\rm perf}$, $\C^\infty_{\rm perf}$, and 
``$\C^\infty_{\rm perf}$''
are defined the similar way.  
We will drop parameter $X$ if $X=\real$.
In particular, $D^n=D^n(\real)$ and $\C^n=\C^n(\real)$.
The relations between these classes for $n<\omega$ are 
given in a chart below, where arrows $\longrightarrow$ 
indicate the strict inclusions $\subsetneq$. 



%\hspace{1.4in}
\hspace{1.1in}
%\noindent 
\begin{picture}(0,110)
\put(0,30){\makebox(0,0){$\C^n$}}
\put(45,30){\vector(-1,0){30}}
\put(68,30){\makebox(0,0){``$D^{n+1}$''}}
\put(120,30){\vector(-1,0){30}}
\put(143,30){\makebox(0,0){``$\C^{n+1}$''}}
%\put(55,72){\vector(-4,-3){40}}
\put(65,72){\vector(0,-1){30}}
\put(140,72){\vector(0,-1){30}}
\put(70,85){\makebox(0,0){$D^{n+1}$}}
\put(120,85){\vector(-1,0){30}}
\put(145,85){\makebox(0,0){$\C^{n+1}$}}
\end{picture}
\hfill Chart \Ccounter. \label{count2}
\hfill\mbox{ }
%\hspace{1.46in}
\hspace{1.1in}
\mbox{ }
\bigskip 


In addition for 
$F\subset\real^2$ we define $F^{-1}=\{\la y,x\ra\colon\la x,y\ra\in F\}$
and for $\F\subset\P(\real^2)$ we put $\F^{-1}=\{F^{-1}\colon F\in\F\}$. 

\section{Axiom \psmP}

Axiom \psmP\ is a simpler version of the axiom
\psm\ which is described in~\cite{CPAbook}. 
The main notion needed for the axiom is that of
a prism and prism-density. 

Let $A$ be a non-empty countable set of ordinal numbers
and let  
$\Phi_{\rm prism}(A)$\label{PagePhiPrism}
be the family of all continuous injections 
$f\colon\Cantor^A\to\Cantor^A$ 
with the property that
\begin{equation}\label{con:PrKeep}
\!\!\!\!\!\!
f(x)\restriction\alpha=f(y)\restriction\alpha\ \Equi\ 
x\restriction\alpha=y\restriction\alpha
\ \ \ \ \ \mbox{ for all $\alpha\in A$ and $x,y\in \Cantor^A$}
\end{equation}
or, equivalently, such that for every $\alpha\in A$
\[
f\restriction\restriction\alpha\stackrel{\rm def}{=}
\{\la x\restriction\alpha,y\restriction\alpha\ra\colon\la x,y\ra\in f\}
\]
is a one-to-one function from $\Cantor^{A\cap\alpha}$
into $\Cantor^{A\cap\alpha}$. 
Functions $f$ from $\Phi_{\rm prism}(A)$ were first introduced, 
in more general setting, in~\cite{Ka} where they are called
{\em projection-keeping homeomorphisms}.
Note that 
\begin{equation}\label{eq:compPr}
\mbox{$\Phi_{\rm prism}(A)$ is closed under compositions}
\end{equation}
and that for every ordinal number $\alpha>0$
\begin{equation}\label{eq:restr}
\mbox{if $f\in\Phi_{\rm prism}(A)$ then
$f\restriction\restriction\alpha\in\Phi_{\rm prism}(A\cap\alpha)$.}
\end{equation}
For $0<\alpha<\omega_1$ let 
\[
\mathPerf_\alpha=\{\range(f)\colon f\in \Phi_{\rm prism}(\alpha)\}.
\]
Note that 
\begin{equation}\label{eq17}
\mbox{
if $f\in\Phi_{\rm prism}(\alpha)$ and $P\in\mathPerf_\alpha$ then 
$f[P]\in\mathPerf_\alpha$.
}
\end{equation}
Indeed, if $P=g[\Cantor^\alpha]$ for some $g\in\Phi_{\rm prism}(\alpha)$
then, by condition (\ref{eq:compPr}), we have
$f[P]=f[g[\Cantor^\alpha]]=(f\circ g)[\Cantor^\alpha]\in\mathPerf_\alpha$.



We will write $\Phi_{\rm prism}$ for 
$\bigcup_{0<\alpha<\omega_1}\Phi_{\rm prism}(\alpha)$
and define 
\[
\mbox{$
\mathPerf_{\omega_1}\stackrel{\rm def}{=}
\bigcup_{0<\alpha<\omega_1}\mathPerf_\alpha=
\{\range(f)\colon f\in \Phi_{\rm prism}\} 
$.}
\]
Following~\cite{Ka} we will refer to elements of 
$\mathPerf_{\omega_1}$ as {\em iterated perfect sets}. 


The simplest elements of 
$\mathPerf_{\omega_1}$ are {\em cubes}\/ (in $\Cantor^A$), that is, 
the sets of the form 
$C=\prod_{a\in A} C_a$, where $C_a\in\perf(\Cantor)$ for each $a\in A$.
(This is justified by a function 
$f=\la f_a\ra_{a\in A}\in \Phi_{\rm prism}(A)$,
where each $f_a$ is a homeomorphism from
$\Cantor$ onto $C_a$.)
In particular, since any open ball $B_\alpha(z,\e)$
(in the metric given by (\ref{eqRHO})) 
is a cube in $\Cantor^\alpha$,
it belongs to $\mathPerf_\alpha$. 
In fact, more can be said:
\begin{equation}\label{eq19}
\mbox{if }\ 
\B_\alpha\stackrel{\rm def}{=}\{B\subset\Cantor^\alpha\colon
\mbox{ $B$ is clopen in $\Cantor^\alpha$\} \  then } \ 
\B_\alpha\subset\mathPerf_\alpha.
\end{equation}
This is the case, since any clopen $E$ in $\Cantor^\alpha$
is a finite union of disjoint open balls, each of which belongs to
$\mathPerf_\alpha$, and it is easy to see that 
$\mathPerf_\alpha$ is closed under finite unions of open balls. 



In general, the structure of elements of $\mathPerf_{\omega_1}$ 
can be considerably more complex.
However, there is only one non-trivial fact about
$\mathPerf_{\omega_1}$  that we will use in this paper:
the family $\mathPerf_{\omega_1}$ satisfies the following 
fusion lemma.

\lem{SimpleFusionLemma}{{\rm\bf (Fusion Lemma)}
Let $0<\alpha<\omega_1$, 
$\A\in\{\B_\alpha,\mathPerf_\alpha\}$, 
and let 
$\la\D_k\subset[\A]^{<\omega}\colon k<\omega\ra$
be such that for every $k<\omega$ the following holds.
\begin{description}
\item{\rm (P1)} ($\D_k$ is $\A$-open) 
If $\{E_0,\ldots,E_n\}\in\D_k$ and
$E_0',\ldots,E_n'\in\A$ are such that
$E_i'\subset E_i$ for every  $i\leq n$ then 
$\{E_0',\ldots,E_n'\}\in\D_k$.

\item{\rm (P2)} (sequence splits) 
If $\{E_0,\ldots,E_n\}\in\D_k$ and $\{E^i_0,E^i_1\}\in\D_{k+1}$ 
for every $i\leq n$ is such that
$E^i_0\cup E^i_1\subset E_i$ then $\{E^i_j\colon i\leq n\ \&\ j<2\}\in\D_{k+1}$. 

\item{\rm (P3)} ($\D_k$ is nicely $\A$-dense) 
For every $E\in\A$ and $\gamma<\alpha$ there are disjoint
$E_0,E_1\in\A$ such that 
$E_0\cup E_1\subset E$, $\{E_0,E_1\}\in\D_k$,
and $\pi_{\gamma}[E_0]=\pi_{\gamma}[E_1]$.
\end{description}
Then 
there exists a sequence $\la \E_k\in \D_k\colon k<\omega\ra$ 
with the property that 
its fusion $Q=\bigcap_{k<\omega}\bigcup\E_k$ 
belongs to $\mathPerf_\alpha$.
}

Although the lemma looks quite complicated, it should be stressed
that in all its application 
we will be checking only condition (P3),
since the other two conditions will be trivially satisfied. 
The proof of Lemma~\ref{SimpleFusionLemma} will be postponed till
the end of this paper. 

The only other fact we will use on $\mathPerf_{\omega_1}$
(or, more precisely, on cubes) is the following 

\claim{claim1}{If $G\subset \Cantor^\omega$ is 
comeager in $\Cantor^\omega$
then it contains a perfect cube $\prod_{i<\omega}P_i$. 
}

\proof It  follows easily, by induction
on coordinates, from the following well known fact.
\begin{quotation}
\noindent 
For every comeager 
subset $H$ of $\Cantor\times \Cantor$ there are
perfect set $P\subset \Cantor$ and a comeager subset
$\hat H$ of $\Cantor$ 
such that $P\times \hat H\subset H$. 
\end{quotation}
(See~\cite[Exercise~19.3]{Ke}. 
Its version for $\real^2$ is also proved 
in \cite[condition ($\star$), p. 416]{CW}.)
\qed


To state \psmP\ we need a few more definitions. 
For a fixed Polish space $X$ 
let $\Fpr(X)$ 
(or just $\Fpr$, if $X$ is clear 
from the context) be the family of 
all continuous injections $f\colon E\to X$, where 
$E\in\mathPerf_{\omega_1}$.
Each such injection $f$ is called a {\em prism}\/
in $X$ and is
considered as a coordinate system imposed 
on~$P=\range(f)$.\footnote{In a language of forcing 
a coordinate function 
$f$ is simply a nice
name for an element from~$X$.}
We will usually abuse this terminology and 
refer to $P$ itself as a {\em prism}\/ (in $X$)
and to $f$ as a {\em witness function}\/ for $P$. 
A function $g\in\Fpr$ is {\em subprism}\/ of $f$ provided 
$g\subset f$. 
In the above spirit we call 
$Q=\range(g)$ a {\em subprism of a prism}\/ $P$.
Thus, when we say that {\em $Q$~a subprism of a prism $P\in\perf(X)$}\/ 
we mean that $Q=f[E]$, where $f$ is a witness function for $P$,
$E\in\mathPerf_{\omega_1}$, and 
$E\subset \dom(f)$. A family $\E\subset\perf(X)$ is 
{\em $\Fpr$-dense}\/ provided 
\[
\forall f\in\Fpr\ \exists g\in\Fpr\ 
(g\subset f\ \&\ \range(g)\in\E). 
\]
Using (\ref{eq:compPr}) it is easy to show that 

\fact{factFprism}{ 
$\E\subset\perf(X)$ is $\Fpr$-dense if and only if
\[
\forall \alpha<\omega_1\ 
\forall f\in\Fpr,\ f\colon \Cantor^\alpha\to X,\ \exists g\in\Fpr\ 
(g\subset f\ \&\ \range(g)\in\E).
\]
}
Thus, to establish $\Fpr$-density
we can always assume that the witness 
function $f$ for the prism $P$ 
is in a {\em standard form}, that is, 
defined on the entire set $\Cantor^\alpha$. 

Now we are ready to state the axiom.
\begin{description}
\item[{\bf \psmP:}] $\continuum=\omega_2$ and 
for every Polish space $X$ and every $\Fpr$-dense
family $\E\subset\perf(X)$ there is an $\E_0\subset\E$ 
such that $|\E_0|\leq\omega_1$ and $|X\setminus\bigcup\E_0|\leq\omega_1$. 
\end{description}


The proof of the consistency of \psmP\ can be found in \cite[Prop.~4.2]{CP83}.
(See also \cite{CPAbook}.) 
We finish this section with yet another
lemma which will be used in our applications. 

\lem{lem:dual1}{For every $0<\alpha<\omega_1$, $E\in\mathPerf_\alpha$,
a Polish space $X$, 
and a continuous function $f\colon E\to X$ 
there exist 
$0<\beta\leq\alpha$ and $P\in\mathPerf_\alpha$, $P\subset E$, such that 
$f\circ \pi_\beta^{-1}$ is a function on $\pi_\beta[P]\in\mathPerf_\beta$
which is either one-to-one or constant.}

Lemma~\ref{lem:dual1} is a particular case of~\cite[Thm.~20]{Ka}.
It can be also easily deduced from 
Lemma~\ref{SimpleFusionLemma}. (See also~\cite[Lemma~3.2.5]{CPAbook}.)
 



\section{Covering results and their discussion} 

The main consequence of \psmP\ we discuss in this paper is 
the following theorem. 

\thm{thOth2}{The following facts follow from \psmP.
\begin{itemize}
\item[(a)] For every Borel measurable 
           function $g\colon\real\to\real$
           there exists a family of functions 
           $\{f_\xi\in``\C^\infty_{\rm perf}\mbox{''}\colon\xi<\omega_1\}$
           such that 
           $$g=\bigcup_{\xi<\omega_1} f_\xi.$$
           Moreover for each $\xi<\omega_1$ there exists an extension 
           $\bar f_\xi\colon\real\to\real$ of $f_\xi$ such that 
           \begin{itemize}
               \item[(i)] $\bar f_\xi\in``\C^1$'' and
               \item[(ii)] either $\bar f_\xi\in\C^1$
                 or $\bar f_\xi$ is 
                 a homeomorphism from $\real$ onto $\real$
                 such that $\bar f_\xi^{-1}\in\C^1$. 
           \end{itemize}
\item[(b)] There exists a sequence 
           $\{f_\xi\in\real^\real\colon\xi<\omega_1\}$
           of $\C^1$ functions such that
           $$\real^2=\bigcup_{\xi<\omega_1} (f_\xi\cup f_\xi^{-1}).$$
\end{itemize}
}

The essence of Theorem~\ref{thOth2} lies in the following real
analysis fact.  Its proof is combinatorial in nature and uses no
extra set-theoretical assumptions. 

\prop{propDens}{Let $g\colon\real\to\real$ be Borel and $0<\alpha<\omega_1$.
\begin{itemize}
\item[(a)] For  every continuous 
injection $h\colon\Cantor^\alpha\to\real$ there exists an $E\in\mathPerf_\alpha$
such that $g\restriction h[E]\in``\C^\infty_{\rm perf}$''
and there is an extension $f\colon\real\to\real$ of $g\restriction h[E]$ such that 
$f\in``\C^1$'' and either $f\in\C^1$
               or $f$ is a self-homeomorphism
  of $\real$ with $f^{-1}\in\C^1$. 
\item[(b)] For  every continuous 
injection $h\colon\Cantor^\alpha\to\real^2$ there exists an $E\in\mathPerf_\alpha$
such that either $F=h[E]\subset\real^2$ or its inverse, $F^{-1}$,
is a function which can be extended to a $\C^1$ function $f\colon\real\to\real$. 
\end{itemize}
}

With Proposition~\ref{propDens} in hand the proof of 
Theorem~\ref{thOth2} becomes an easy exercise.

\medskip

\noindent{\sc Proof of Theorem~\ref{thOth2}.} 
(a) Let $g\colon\real\to\real$ be a Borel
function and let $\E$ be the family of all $P\in\perf(\real)$ such that 
\begin{quote}
$g\restriction P\in``\C^\infty_{\rm perf}$''
and there is an extension $f\colon\real\to\real$ of $g\restriction P$ such that 
$f\in``\C^1$'' and either $f\in\C^1$
               or $f$ is a self-homeomorphism of $\real$ with $f^{-1}\in\C^1$. 
\end{quote}
By Proposition~\ref{propDens}(a) family $\E$ is $\Fpr$-dense:
if $P\in\perf(\real)$ is a prism and $h\colon\Cantor^\alpha\to\real$
from $\Fpr$ witnesses it then $Q=h[E]$ as in the proposition 
is a subprism of $P$ with $Q\in\E$. 
So, by \psmP, there exists an $\E_0\in[\E]^{\leq\omega_1}$ 
such that $|\real\setminus\bigcup\E_0|\leq\omega_1$. 
Let $\E_1=\E_0\cup\{\{r\}\colon r\in \real\setminus\bigcup\E_0\}$.
Then the family $\{g\restriction P\colon P\in\E_1\}$ satisfies the theorem. 

(b) Let $\E$ be the family of all $P\in\perf(\real^2)$ such that 
either $P$ or $P^{-1}$ is a function 
which can be extended to a $\C^1$ function $f\colon\real\to\real$.
By Proposition~\ref{propDens}(b) family $\E$ is $\Fpr$-dense, so 
there exists an $\E_0\in[\E]^{\leq\omega_1}$ 
such that $|\real\setminus\bigcup\E_0|\leq\omega_1$. 
Let $\E_1=\E_0\cup\{\{x\}\colon x\in \real^2\setminus\bigcup\E_0\}$.
For every $P\in\E_1$ let $f_P\colon\real\to\real$ be a $\C^1$ function
which extends either $P$ or $P^{-1}$.
Then family $\{f_P\colon P\in\E_1\}$ is as desired. \qed

The proof of Proposition~\ref{propDens} will be left to 
the next sections.  
Meanwhile we like to present a discussion of Theorem~\ref{thOth2}.

First we like to reformulate Theorem~\ref{thOth2} 
in a language of a {\em covering number}\/ $\cov$ defined below, where 
$X$ is an infinite set 
(in our case $X\subset\real^2$ with $|X|=\continuum$) and 
$\A,\F\subset\P(X)$:
\[
\cov(\A,\F)=\min\left(
\left\{\kappa\colon (\forall A\in\A)
(\exists \G\in[\F]^{\leq\kappa})\ A\subset\bigcup\G\right\}\cup\{|X|^+\}\right).
\]

If $A\subset X$ we 
will write $\cov(A,\F)$ for $\cov(\{A\},\F)$. Notice the following
monotonicity of $\cov$ operator: 
for every $A\subset B\subset X$, $\A\subset \B\subset\P(X)$, and
$\F\subset\G\subset\P(X)$
\[
\cov(\A,\G)\leq\cov(\B,\G)\leq\cov(\B,\F)
\ \ \ \&\ \ \ 
\cov(A,\G)\leq\cov(B,\G)\leq\cov(B,\F).
\]

In terms of the $\cov$ operator Theorem~\ref{thOth2}
can be expressed in the following form,
where ${\rm Borel}$ stands for the class of all Borel 
functions $f\colon\real\to\real$. 

\pagebreak

\cor{corth2}{\psmP\ implies that
\begin{itemize}
  \item[(a)] $\cov\left({\rm Borel},``\C_{\rm perf}^\infty\mbox{''}\right)
                =\omega_1<\continuum$;
  \item[(b)] $\cov\left({\rm Borel},``\C^1\mbox{''}\right)=\omega_1<\continuum$;
  \item[(c)] $\cov\left({\rm Borel},\C^1\cup(\C^1)^{-1}\right)=\omega_1<\continuum$;
  \item[(d)] $\cov\left(\real^2,\C^1\cup(\C^1)^{-1}\right)=\omega_1<\continuum$.
\end{itemize}
}

\proof The fact that all numbers $\cov(\A,\G)$ listed above are $\leq \omega_1$
follows directly from Theorem~\ref{thOth2}.
The other inequalities follow from Examples~\ref{CD4} and~\ref{CD5}. \qed 


Theorem~\ref{thOth2}(b) and Corollary~\ref{corth2}(d)
can be treated as generalizations of
a result of Stepr\={a}ns~\cite{St2} who 
proved that in the iterated perfect set model we have 
$\cov\left(\real^2,\left(``D^1\mbox{''}\right)
\cup\left(``D^1\mbox{''}\right)^{-1}\right)\leq\omega_1$.
This clearly follows from 
Corollary~\ref{corth2}(d) since
$\C^1\subsetneq``D^1\mbox{''}$.
(See survey article~\cite{Br1}. For more 
information how to ``locate'' 
Stepr\={a}ns' result in~\cite{St2} see also~\cite[Cor.~9]{CN}.)

The following proposition shows that Theorem~\ref{thOth2} is, in a way,
the best possible. 
(Parts (i), (ii), and (iii) relate, respectively, to
items (b), (c)$\&$(d), and (a) from Corollary~\ref{corth2}.)

\prop{PropTh2Bound}{The following is true in ZFC. 
\begin{itemize}
    \item[(i)] $\cov\left({\rm Borel},\C^1\right)=\cov\left(``\C^1\mbox{''},\C^1\right)=
               \cov\left(``\C^1\mbox{''},D_{\rm perf}^1\right)=\continuum$. Moreover, 
               
               $\cov(``\C^n\mbox{''},\C^n)=\cov(``\C^n\mbox{''},D_{\rm perf}^n)=\continuum$ 
               for every $0<n<\omega$.
               
    \item[(ii)]  $\cov\left({\rm Borel},\C^2\cup(\C^2)^{-1}\right)=
               \cov\left(``\C^2\mbox{''},D_{\rm perf}^2\cup(D_{\rm perf}^2)^{-1}\right)
               =\continuum$, and 

               $\cov\left(\real^2,\C^2\cup(\C^2)^{-1}\right)=
               \cov\left(``\C^2\mbox{''},D_{\rm perf}^2\cup(D_{\rm perf}^2)^{-1}\right)
               =\continuum$.

    \item[(iii)] $\cov\left({\rm Borel},\C_{\rm perf}^\infty\right)=
               \cov\left(``\C^1\mbox{''},\C_{\rm perf}^\infty\right)=
               \cov\left(``\C^1\mbox{''},D_{\rm perf}^1\right)=\continuum$, and

               $\cov\left({\rm Borel},``\C^\infty\mbox{''}\right)=
               \cov\left(\C^1,``\C^\infty\mbox{''}\right)=
               \cov\left(\C^1,``D^2\mbox{''}\right)=\continuum$. Moreover, 
               
               $\cov\left(\C^n,``D^{n+1}\mbox{''}\right)=\continuum$ for every $0<n<\omega$.
\end{itemize}
}

\proof (i) follows immediately from Examples~\ref{CD1} and \ref{CD1a}. 

(ii) follows from monotonicity of $\cov$ operator and Example~\ref{exZUc2}.

The first part of (iii) follows from (i).  The remaining two parts follow,
respectively, from Examples~\ref{CD3} and \ref{CD3a}. 
\qed

Corollary~\ref{corth2} and Proposition~\ref{PropTh2Bound}
establish the values of $\cov$ operator for all classes 
in Chart~\ref{count2} except for  $\cov\left(D^n,\C^n\right)$ and 
$\cov\left(``D^n\mbox{''},``\C^n\mbox{''}\right)$. These are 
established in the following theorem,
which proof will be left
to Sections~\ref{sec6}. 

\thm{thcCov3}{If \psmP\ holds then for every $0<n<\omega$
\[
\cov\left(D^n,\C^n\right)=
\cov\left(``D^n\mbox{''},``\C^n\mbox{''}\right)=\omega_1<\continuum.
\]
}


With this theorem in hand we can summarize the values
of the $\cov$ operator between the classes 
from Chart~\ref{count2} in the following graphical form.
Here the mark ``$\continuum$'' next to the arrow means that 
the covering of the larger class by the functions
from the smaller class is equal to $\continuum$ and that
this can be proved in ZFC. The mark ``$<\continuum$''
next to the arrow means that it is consistent
with ZFC (and it follows from \psmP) that the appropriate 
$\cov$ number is $<\continuum$. 
(From Examples~\ref{CD4}, \ref{CD4a}, and~\ref{CD5}
it follows that all these numbers
are greater than or equal to $\min\{\cov(\M),\cov(\NN)\}>\omega$.
So under the continuum hypothesis CH or Martin's Axiom MA all these numbers are 
equal to~$\continuum$.)



\noindent 
\hspace{0.1in}
%\hspace{0.02in}
\begin{picture}(0,110)
\put(0,30){\makebox(0,0){$\C^0$}}
\put(45,30){\vector(-1,0){30}}
\put(30,24){\makebox(0,0){$<\continuum$}}
\put(68,30){\makebox(0,0){``$D^{1}$''}}
\put(120,30){\vector(-1,0){30}}
\put(105,24){\makebox(0,0){$<\continuum$}}
\put(143,30){\makebox(0,0){``$\C^{1}$''}}
%\put(55,72){\vector(-4,-3){40}}
\put(65,72){\vector(0,-1){30}}
\put(71,57){\makebox(0,0){$\continuum$}}
\put(140,72){\vector(0,-1){30}}
\put(146,57){\makebox(0,0){$\continuum$}}
\put(70,85){\makebox(0,0){$D^{1}$}}
\put(120,85){\vector(-1,0){30}}
\put(105,79){\makebox(0,0){$<\continuum$}}
\put(145,85){\makebox(0,0){$\C^{1}$}}
\end{picture}
%\hspace{2.45in}
\hspace{2.8in}
%\noindent 
\begin{picture}(0,110)
\put(0,30){\makebox(0,0){$\C^n$}}
\put(45,30){\vector(-1,0){30}}
\put(30,24){\makebox(0,0){$\continuum$}}
\put(68,30){\makebox(0,0){``$D^{n+1}$''}}
\put(120,30){\vector(-1,0){30}}
\put(105,24){\makebox(0,0){$<\continuum$}}
\put(143,30){\makebox(0,0){``$\C^{n+1}$''}}
%\put(55,72){\vector(-4,-3){40}}
\put(65,72){\vector(0,-1){30}}
\put(71,57){\makebox(0,0){$\continuum$}}
\put(140,72){\vector(0,-1){30}}
\put(146,57){\makebox(0,0){$\continuum$}}
\put(70,85){\makebox(0,0){$D^{n+1}$}}
\put(120,85){\vector(-1,0){30}}
\put(105,79){\makebox(0,0){$<\continuum$}}
\put(145,85){\makebox(0,0){$\C^{n+1}$}}
\end{picture}

\vspace{-12pt}
\begin{center}
Chart \Ccounter. \label{count3}
Values of $\cov$ operator: 
for $n=0$ (left) and $n>0$ (right).
\end{center}
The values of $\cov$ next the vertical arrows 
are justified by 
$\cov(``\C^n\mbox{''},D^n)=\continuum$ (Proposition~\ref{PropTh2Bound}(i)),
while marks ``$<\continuum$'' below the upper horizontal arrows
and that directly below them follow from Theorem~\ref{thcCov3}.
The remaining arrow of the right part of the chart is the restatement of
the last part of Proposition~\ref{PropTh2Bound}(iii),
while its counterpart in the left part of the chart
follows from Corollary~\ref{corth2}(b):
$\cov\left(\C,``\C^1\mbox{''}\right)=
\cov\left({\rm Borel},``\C^1\mbox{''}\right)
<\continuum$ is a consequence of \psmP. 
Finally let us mention that 
in Corollary~\ref{corth2}(b)
there is no chance to 
increase family ${\rm Borel}$ in any essential way and keep the result.
This follows from the following fact 
\begin{equation}
\cov({\rm Sc},\C)=\cov\left(\real^\real,\C\right)\geq\cf(\continuum),
\end{equation}
where symbol ${\rm Sc}$ stands for the family of all symmetrically continuous
functions $f\colon\real\to\real$ which are, in particular,
continuous outside of some set of measure zero and first category. 
(See \cite[Cor.~1.1]{KCdecomp} and the remarks below on 
the operator ${\rm dec}$.)

Number $\cov(\A,\F)$ is very closely related to 
the following decomposition number 
\[
\dec(\A,\F)=\min\!\left(
\left\{\kappa\geq\omega\colon (\forall A\in\A)
(\exists\mbox{ a partition $\G\in[\F]^\kappa$ of }A\right\}\cup\{|X|^+\}
\right)
\]
which was first studied 
by Cicho\'{n}, Morayne, Pawlikowski, and
Solecki~\cite{cimopaso} for the Baire class $\alpha$ functions. 
(More information on ${\rm dec}(\F,\G)$
can be found in a survey article \cite[sec.~4]{KCsurv}.)
It is easy to see that if $\A$ and $\F$ are some classes of partial functions
and $\F_r$ denotes all possible restrictions of
functions from $\F$ then
$\cov(\A,\F)=\dec(\A,\F_r)$. 
In particular, for all situations relevant to our discussion above
the operators $\cov$ and $\dec$ have the same values. 

Our number $\cov$ is also related to the following
general class of problems. 
We say that the families $\A,\F\subset\P(X)$ 
satisfy {\em Intersection Theorem,}
which we denote by
\[
\IntTh(\A,\F),
\]
if for every $A\in\A$ there exists an $F\in\G$ such that $|A\cap F|=|X|$. 
If $\A=\{A\}$ we will write $\IntTh(A,\F)$ in place of $\IntTh(\A,\F)$.
This kind of theorems have been studied for a big
part of this century. In particular, 
in early 1940's Ulam asked in the 
{\it Scottish Book} \cite[Problem~17.1]{ScotB}
if $\IntTh(\C,{\rm Analytic})$ holds, that is, whether
for every $f\in\C$ there exists a real analytic function
$g\colon\real\to\real$ which agrees with $f$ 
on a perfect set. (See~\cite{Ulam}.)
In 1947 Zahorski~\cite{Za} gave a negative answer to this question
by proving that the proposition 
$\IntTh(\C^\infty,{\rm Analytic})$ is false. In the same paper he
also raised a natural question, which has become known as
Ulam-Zahorski Problem:
{\it Does $\IntTh(\C,\G)$ hold for $\G=\C^\infty$ 
(or $\G=\C^n$ or $\G=D^n$)?}
Here is a quick summary of what is known on this problem. (See \cite{Br1}.)


\prop{UZaccount}{
\begin{itemize}
\item[{\rm (a)}] {\rm (Zahorski~\cite{Za})} $\neg \IntTh(\C^\infty,{\rm Analytic})$. 
\item[{\rm (b)}] {\rm (Agronsky, Bruckner, Laczkovich, Preiss~\cite{ABLP})}
      $\IntTh(\C,\C^1)$.
\item[{\rm (c)}] {\rm (Olevski\v{\i}~\cite{Ol})} $\IntTh(\C^1,\C^2)$.
\item[{\rm (d)}] {\rm (Olevski\v{\i}~\cite{Ol})}
      $\neg\IntTh(\C,\C^2)$ and $\neg\IntTh(\C^n,\C^{n+1})$ for $n\geq 2$.
\end{itemize}
}
We are interested in these problems since for 
the families $\A,\F\in\P(\real^n)$ of uncountable Borel sets
\begin{equation}\label{IntVScov}
\neg\IntTh(\A,\F)\ \Implies\ \cov(\A,\F)=\continuum
\end{equation}
as, in this situation, if $\neg\IntTh(\A,\F)$ then 
there exists an $A\in\A$, $|A|=\continuum$,  
such that $|A\cap F|\leq\omega$ for every $F\in\F$. 
Thus in the examples 
relevant to Proposition~\ref{PropTh2Bound}
instead of proving 
$\cov(\A,\F)=\continuum$ we will be in fact showing 
a stronger fact that $\neg\IntTh(A_0,\F)$
for appropriate $A_0\subset A\in\A$.



\section{Proof of Proposition~\ref{propDens}}

Proposition~\ref{propDens} will be deduced from the following 
fact, which is a generalization of a theorem of Morayne~\cite{Mor}.
(Morayne proved his results for $E$ and $E_1$ being perfect sets, that is,
for $\alpha=1$.) 
For a set $X$ we will use symbol $\Delta_X$ to denote the diagonal
in $X\times X$, that is, 
$\Delta_X=\{\la x,x\ra\colon x\in X\}$. 
We will usually write simply $\Delta$ in place of $\Delta_X$, since $X$ 
is always clear from the context. 

\prop{prMainUCsym}{Let $0<\alpha<\omega_1$, $E\in\mathPerf_\alpha$,
$h\colon E\to\real$ be a continuous injection, and 
$G$ be a function from $(h[E])^2\setminus\Delta$ into $[0,1]$
which is continuous and symmetric, 
that is,
such that $G(x,y)=G(y,x)$ for all $x,y\in(h[E])^2\setminus\Delta$. 
Then there exists an $E_1\in\mathPerf_\alpha$, $E_1\subset E$, such that 
$G$ is uniformly continuous on 
$(h[E_1])^2\setminus\Delta$. 
}

The proof of Proposition~\ref{prMainUCsym} will be presented in the next
section. 
In the proof of Proposition~\ref{propDens}
we will also use the following lemma. 


\lem{lemDens1}{Let $g\colon\real\to\real$ be Borel, $0<\alpha<\omega_1$, 
and $E\in\mathPerf_\alpha$. For every continuous 
injection $h\colon E\to\real$ there exist subset 
$E_1\in\mathPerf_\alpha$ of $E$
and a $``\C^1$'' function $f\colon\real\to\real$ such that
$f$ extends $g\restriction h[E_1]$. 

In addition we can require that either $f\in\C^1$ or 
\begin{itemize}
\item[{\rm ($\star$)}] 
$f'\restriction h[E_1]$ is constant equal to $\infty$ or $-\infty$ 
and $f$ is a self-homeomorphism of $\real$ such that $f^{-1}\in\C^1$.
\end{itemize}
}

\proof First note that there exists an 
$E'\in\mathPerf_\alpha$, $E'\subset E$, such that 
\begin{equation}\label{eqLemDens}
\mbox{$g\restriction h[E']$ is continuous.}
\end{equation}
Indeed, let $h_0\in \Phi_{\rm prism}$
be such that $E=h_0\left[\Cantor^\alpha\right]$
and let $U$ be a comeager subset of 
$h[E]=(h\circ h_0)\left[\Cantor^\alpha\right]$  
such that the restriction $g\restriction U$ is continuous. 
Then $(h\circ h_0)^{-1}(U)$ is comeager in $\Cantor^\alpha$
and, by Claim~\ref{claim1}, there is a perfect cube $Q\subset (h\circ h_0)^{-1}(U)$.
The set $E'=h_0[Q]\in\mathPerf_\alpha$ has the desired property 
since $h[E']=h[h_0[Q]]\subset U$.

Now let $k\colon[-\infty,\infty]\to[0,1]$ be a homeomorphism and let
$G$ be defined on $(h[E'])^2\setminus\Delta$ by
\[
G(x,y)=k\left(\frac{g(x)-g(y)}{x-y}\right).
\]
Then, by Proposition~\ref{prMainUCsym}, there exists 
an $E'_1\in\mathPerf_\alpha$, $E'_1\subset E'$, such that 
$G$ is uniformly continuous on $(h[E'_1])^2\setminus\Delta$.
So, there exists a 
uniformly continuous extension
of $G\restriction (h[E'_1])^2\setminus\Delta$ to 
$\hat G\restriction (h[E'_1])^2$.
Clearly $k^{-1}(\hat G(x,x))$ is the derivative 
(possibly infinite) 
of $g_0=g\restriction h[E'_1]$
for every $x\in h[E'_1]$, so $g_0\in``\C^1(h[E'_1])$''.

Now, if $(g'_0)^{-1}(\real)$ is non-empty then, 
as in the argument for (\ref{eqLemDens}),
we can find an 
$E_1\in\mathPerf_\alpha$, $E_1\subset E'_1$, such that
$h[E_1]\subset (g'_0)^{-1}(\real)$.
This obviously implies  
$g\restriction h[E_1]\in\C_{\rm perf}^1$.
But we also know that
the difference quotient function $\frac{g(x)-g(y)}{x-y}$ 
is uniformly continuous on 
$(h[E_1])^2\setminus\Delta$.
So, by Whitney's extension theorem~\cite{Wh}
(see also Lemma~\ref{3.4Lem1}), 
we can find a $\C^1$ extension $f\colon\real\to\real$ 
of $g\restriction h[E_1]$.


So, assume that $(g'_0)^{-1}(\real)=\emptyset$.
Then either $(g'_0)^{-1}(\infty)$  or $(g'_0)^{-1}(-\infty)$
is non-empty and open in $h[E'_1]$. Assume the former case. 
Similarly as above we can find an $E''_1\in\mathPerf_\alpha$, $E''_1\subset E'_1$, 
such that $g'_0[h[E''_1]]=\{\infty\}$.
Then, by a version of Whitney's extension theorem
from \cite[Thm.~2.1]{Br2}, we can find a ``$\C^1$''
extension $f_0\colon\real\to\real$ of $g\restriction h[E''_1]$. 

But then there exists
an open interval $J$ in $\real$ intersecting $h[E''_1]$
on the closure of which $f_0'$ is positive. 
So $f_1=f_0\restriction \cl(J)$ is strictly increasing
and the derivative of $f_1^{-1}$ is continuous, non-negative, and bounded. 
Thus there exists a homeomorphism $f_2\colon\real\to\real$ extending $f_1^{-1}$ with
$f_2\in\C^1$. Now put $f=f_2^{-1}$ and 
take an $E_1\in\mathPerf_\alpha$ with $E_1\subset E''_1\cap h^{-1}(J)$.
It is easy to see that $E_1$ and $f$ are as required. \qed

\noindent{\sc Proof of Proposition~\ref{propDens}}(a). 
By Lemma~\ref{lemDens1} we can find an $E_0\in\mathPerf_\alpha$ 
for which 
there is an extension $f\colon\real\to\real$ of $g\restriction h[E_0]$ such that 
$f\in``\C^1$'' and either $f\in\C^1$
or $f$ is a self-homeomorphism of $\real$ with $f^{-1}\in\C^1$. 
Thus, it is enough to find a subset $E\in\mathPerf_\alpha$ of $E_0$ for which 
$g\restriction h[E]\in``\C^\infty_{\rm perf}$''.

If there exist a subset $E\in\mathPerf_\alpha$ of $E_0$ and $n<\omega$ such that 
\begin{equation}\label{eqiii1}
\mbox{$f=g\restriction h[E]\in``\C_{\rm perf}^n$''
and $f^{(n)}$ has a constant value $\infty$ or $-\infty$}  
\end{equation}
then this $E$ is as desired.
So assume that there is no such $E$. 
We will use Fusion Lemma \ref{SimpleFusionLemma}
with $\A=\mathPerf_\alpha$ 
to find a subprism $E$ of $E_0$ for which 
$g\restriction h[E]\in\C^\infty_{\rm perf}$.

First notice that we can assume that $E_0=\Cantor^\alpha$, since 
we can replace $h$ with $h\circ h_0$, where 
$h_0\in \Phi_{\rm prism}$
is such that $E_0=h_0\left[\Cantor^\alpha\right]$. 
For $k<\omega$ let 
$\D_k\subset[\mathPerf_\alpha]^{<\omega}$ 
be the collection of all finite families $\E$ of 
pairwise disjoint sets each of the diameter 
less than $2^{-k}$ such that
\begin{equation}\label{eqiii}
g\restriction \bigcup\{h[E]\colon {E\in\E}\}\in \C_{\rm perf}^k. 
\end{equation}
We need to show that $\D_k$'s 
satisfy the assumptions of Lemma~\ref{SimpleFusionLemma}. 

It is obvious that the conditions (P1) and (P2) are satisfied. 
To see that (P3) holds for $k<\omega$ fix 
$\bar E\in\mathPerf_\alpha$ and $\gamma<\alpha$.
Applying Lemma~\ref{lemDens1} $k$-times and using the fact that 
(\ref{eqiii1}) is false we can find a sequence 
$\bar E=P_0\supset \cdots \supset P_k$ from $\mathPerf_\alpha$ 
such that $g\restriction h[P_i]\in \C_{\rm perf}^i$ for each $i\leq k$. 
Take disjoint $E_0,E_1\in\mathPerf_\alpha$ subsets of 
$P_k$, each of diameter less than $2^{-k}$, such that 
$\pi_\gamma[E_0]=\pi_\gamma[E_1]$. It is easy to see that
$E_0$ and $E_1$ satisfy the requirements of the condition (P3).  


Now, by Lemma \ref{SimpleFusionLemma}, there exist 
$\E_k\in\D_k$ such that 
$E=\bigcap_{k<\omega}\bigcup\E_k\in\mathPerf_\alpha$.
Clearly $g\restriction h[E]\in\C_{\rm perf}^\infty$
for such an $E$. \qed

\noindent{\sc Proof of Proposition~\ref{propDens}}(b). 
Let $\pi_x$ and $\pi_y$ be the projections of $\real^2$ onto $x$-axis and
$y$-axis, respectively, and consider functions
$h_x=\pi_x\circ h$ and 
$h_y=\pi_y\circ h$.
Applying Lemma~\ref{lem:dual1} two times we can find
$\beta_x,\beta_y\leq\alpha$ and $E=P_y\subset P_x$ from 
$\mathPerf_\alpha$ such that 
$h_x\circ\pi_{\beta_x}^{-1}$ is a function on 
$\pi_{\beta_x}[P_x]\in\mathPerf_{\beta_x}$,
$h_y\circ\pi_{\beta_y}^{-1}$ is a function on 
$\pi_{\beta_y}[P_y]\in\mathPerf_{\beta_y}$,
and each of these functions is either one-to-one or constant.
Notice that
\begin{equation}\label{condPlane}
\mbox{either $h_x$ or $h_y$ is one-to-one on $E$.}
\end{equation}
To see this first note that for every $z\in E$ we have 
\[
h(z) =\la\pi_x\circ h(z),\pi_y\circ h(z)\ra 
= \la (h_x\circ\pi_{\beta_x}^{-1})(\pi_{\beta_x}(z)),
(h_y\circ\pi_{\beta_y}^{-1})(\pi_{\beta_y}(z))\ra.
\]
Since $h$ is one-to-one this implies that $\max\{\beta_x,\beta_y\}=\alpha$.
By symmetry, we can assume that $\alpha=\beta_x$. 
Thus, $h_x=h_x\circ\pi_{\beta_x}^{-1}$ is  either one-to-one or constant on 
$P_x=\pi_{\beta_x}[P_x]$. If $h_x$ is one-to-one on $P_x$ 
then (\ref{condPlane}) holds.
So, assume that $h_x$ is constant on $P_x$.
Then $\pi_x\circ h=h_x$ is constant on $E\subset P_x$, 
and so $h_y=\pi_y\circ h$ must be one-to-one on $E$, since $h$ is one-to-one.
Thus, (\ref{condPlane}) holds.

By symmetry, we can assume that $h_x$ is one-to-one on $E$. 
So $\pi_x\circ h$ is a
one-to-one function from $E$ onto
$\pi_x[h[E]]\subset\real$. 
In particular, $F_0=h[E]\subset\real^2$  is a function
from $\pi_x[h[E]]$ into $\real$. 
Then, by Lemma~\ref{lemDens1} used with $g=F_0$ and $h=\pi_x\circ h\restriction E$,  
we can find a subset $E_1\in\mathPerf_\alpha$ of $E$ 
and a function $f\colon\real\to\real$ extending $h[E_1]=g\restriction h[E_1]$
such that either $f$ or $f^{-1}$ belongs to~$\C^1$. 
\qed

\section{Proposition~\ref{prMainUCsym}: a generalization of 
a theorem of Morayne}

Our proof of  Proposition~\ref{prMainUCsym}
is based on the following lemmas, the  
first of which is a version of a theorem of Galvin \cite{Ga1,Ga2}.
(For the proof see \cite[Thm.~19.7]{Ke} or \cite{Burges}.
Galvin proved his results for $\alpha=1$.)



\lem{lemGal}{For every $0<\alpha<\omega_1$ and every continuous
symmetric function $h$ from 
$(\Cantor^\alpha)^2\setminus \Delta$
into $2=\{0,1\}$ there exists a $P\in\mathPerf_\alpha$ such that 
$h$ is constant on $P^2\setminus\Delta$. 
}

\proof For $j<2$ let $G_j$ be the set of all $s\in\Cantor^\alpha$ such that
\[ 
     (\forall \beta<\alpha)(\forall \e>0) (\exists t\in\Cantor^\alpha)\ 
     0<\rho(s,t)<\e\ \&\ s\restriction\beta=t\restriction\beta\ \&\ h(s,t)=j
\]
and notice that 
\begin{equation}\label{eqGalv}
\mbox{each $G_j$ is a $G_\delta$-set \ \  and \ \ $\Cantor^\alpha=G_0\cup G_1$}.
\end{equation}
Indeed, to see that $G_j$ is a $G_\delta$-set it is enough to
note that for every $\beta<\alpha$ and $\e>0$ the set
\[
G_j^{\beta,\e}=\{s\in\Cantor^\alpha\colon(\exists t\in\Cantor^\alpha)\ 
     0<\rho(s,t)<\e\ \&\ s\restriction\beta=t\restriction\beta\ \&\ h(s,t)=j\}
\]
is open in $\Cantor^\alpha$. So let $s\in G_j^{\beta,\e}$
and take $t\in\Cantor^\alpha$ witnessing it, that is, such that 
$0<\rho(s,t)<\e$, $s\restriction\beta=t\restriction\beta$, and $h(s,t)=j$.
We can choose 
basic open neighborhoods $U$ and $V$ of $s$ and $t$, respectively,
such that $U\times V\setminus\Delta\subset h^{-1}(j)$.
In addition we can 
assume 
that
$\pi_\beta[U]=\pi_\beta[V]$ and that each of the sets $U$ and $V$ has 
diameter less than $\delta=(\e-\rho(s,t))/3$. 
Then $s\in U\subset G_i^{\beta,\e}$ since for every
$s'\in U$ there exists 
a $t'\in V$, $t'\neq s'$, with $s'\restriction\beta=t'\restriction\beta$
(since $\pi_\beta[U]=\pi_\beta[V]$), 
$h(s',t')\in h[U\times V\setminus\Delta]=\{j\}$ and
\[
0<\rho(s',t')\leq\rho(s',s)+\rho(s,t)+\rho(t,t')\leq \delta+\rho(s,t)+\delta<\e.
\]
Thus each $G_j^{\beta,\e}$ is open and $G_j$ is a $G_\delta$-set.

To see the second part of (\ref{eqGalv}) assume, by way of contradiction, that
there exists an $s\in \Cantor^\alpha\setminus (G_0\cup G_1)$. 
Let $\beta_0$, $\e_0$ and $\beta_1$, $\e_1$ witness that
$s\notin G_0$ and $s\notin G_1$, respectively. 
Put $\e=\min\{\e_0,\e_1\}>0$ and $\beta=\max\{\beta_0,\beta_1\}<\alpha$
and find $t\in\Cantor^\alpha$ such that $t\restriction\beta=s\restriction\beta$,
$\rho(s,t)<\e$, and $t(\beta)\neq s(\beta)$. 
Then there exists a $j<2$ such that $h(s,t)=j$ and
this, together with $t\restriction\beta_j=s\restriction\beta_j$ and
$\rho(s,t)<\e_j$ contradicts the choice of $\beta_j$ and $\e_j$.
This finishes the proof of (\ref{eqGalv}).

Next find a $j<2$ and a basic clopen set $U$ in $\Cantor^\alpha$
such that $G_j$ is residual in $U$. 
Replacing $\Cantor^\alpha$ with $U$, if necessary, we can
assume that $G_j$ is residual in $\Cantor^\alpha$. 
Using Fusion Lemma \ref{SimpleFusionLemma} with $\A=\B_\alpha$ 
we will find a $P\in\mathPerf_\alpha$ for which
$P^2\setminus\Delta \subset h^{-1}(j)$.

For each $k<\omega$ let $\D_k\subset[\B_\alpha]^{<\omega}$ 
be the collection of all families 
$\left\{P_i\colon i<m\right\}$ of 
sets of the diameter less than $2^{-k}$ such that
\begin{equation}\label{eqBigGal}
P_i\times P_n\subset h^{-1}(j)\ \mbox{ for all \ $i<n<m$.} 
\end{equation}
It is obvious $\D_k$'s satisfy conditions (P1) and (P2) 
from Lemma~\ref{SimpleFusionLemma}.
Thus, we need only to check (P3). 

So, take $E\in\B_\alpha$ and $\gamma<\alpha$.
It is enough to find disjoint 
$E_0,E_1\in\B_\alpha$ subsets of $E$ 
such that $\pi_{\gamma}[E_0]=\pi_{\gamma}[E_1]$ and
\begin{equation}\label{eq29}
E_0\times E_1\subset h^{-1}(j). 
\end{equation}
For this choose an $s\in E\cap G_j$ and let $\e_0>0$ be such that 
$B_\alpha(s,\e_0)\subset E$.
By the definition of $G_j$ 
we can find a $t\in \Cantor^\alpha$ for which 
$0<\rho(s,t)<\e_0$, $s\restriction\gamma=t\restriction\gamma$, and $h(s,t)=j$.
In particular $s,t\in E$ and $\la s,t\ra\in h^{-1}(j)$.
Since $h$ is continuous we can find an $\e>0$ small enough that 
$E_0=B_\alpha(s,\e)$ and $E_1=B_\alpha(t,\e)$
are disjoint subsets of $E$ for which (\ref{eq29}) holds. 


Now, by Lemma \ref{SimpleFusionLemma}, there exist 
$\E_k=\left\{P^k_i\colon i<m_k\right\}\in \D_k$ such that 
$P=\bigcap_{k<\omega}\bigcup_{i<m_k}P^k_i\in\mathPerf_\alpha$.
It is enough to show that
$P^2\setminus\Delta \subset h^{-1}(j)$.
To see this, take different $s,t\in P$ and 
let $k<\omega$ be such that the distance between 
$s$ and $t$ is greater than $2^{-k}$. 
Then they must belong to different $P_i^k$'s from $\E_k$ and so,
by (\ref{eqBigGal}), 
$\la s,t\ra\in  h^{-1}(j)$.
\qed

We will also need the following simple fact, which must be
well known. 

\lem{lemFact}{There exists a continuous function $h\colon \Cantor\to[0,1]$
with the following property. 
If $X$ is a zero-dimensional Polish space then for every
continuous function $f\colon X\to[0,1]$ there exists a continuous
$g\colon X\to\Cantor$ such that $f=h\circ g$. 
}

\proof Let $\{U_\sigma\colon\sigma\in 2^{<\omega}\}$ be an open basis for $[0,1]$
such that $U_\emptyset=[0,1]$ and, for every $\sigma\in 2^k$,
$U_\sigma=U_{\sigma\hat{\ }0}\cup U_{\sigma\hat{\ }1}$ and $\diam(U_\sigma)\leq 2^{1-k}$.
For every $s\in 2^\omega$ let 
$h(s)\in[0,1]$ be such that $\{h(s)\}=\bigcap_{n<\omega}\cl(U_{s\restriction n})$.
It is clear that $h$ is continuous. 

To see that $h$ is as required take $X$ and $f$ as in the lemma. 
For every $\sigma\in 2^{<\omega}$ 
choose an open set $V_\sigma\subset f^{-1}(U_\sigma)$ such that $V_\emptyset=X$,
$V_{\sigma\hat{\ }0}$ and $V_{\sigma\hat{\ }1}$ are disjoint, and 
$V_{\sigma\hat{\ }0}\cup V_{\sigma\hat{\ }1}=V_\sigma$.
This can be easily done by induction on the length of $\sigma$ 
using zero-dimensionality of $X$.\footnote{Recall that every 
second countable zero-dimensional space $X$ is strongly zero-dimensional,
see e.g. \cite[Thm.~6.2.7]{Eng}. 
In particular, for every open cover $\{W_0,W_1\}$ of $X$ there are disjoint clopen
sets $V_0\subset W_0$ and $V_1\subset W_1$ such that $V_0\cup V_1=X$.
} 
Thus for every $n<\omega$ the sets $\{V_\sigma\colon\sigma\in 2^n\}$
form a clopen partition of $X$. 

Define $g(x)$ as the unique $s\in\Cantor$ for which 
$x\in\bigcap_{n<\omega}V_{s\restriction n}$.
Clearly $g$ is continuous. Moreover, if $g(x)=s$ then
\[
x\in \bigcap_{n<\omega}V_{s\restriction n}\subset 
f^{-1}\left(\bigcap_{n<\omega}\cl(U_{s\restriction n})\right)=f^{-1}(\{h(s)\})=f^{-1}(\{h(g(x))\})
\]
so that $f(x)\in \{h(g(x))\}$. Hence $f=h\circ g$. \qed

The next lemma is already a very close approximation of Proposition \ref{prMainUCsym}.

\lem{lemMainUCsym}{If $\alpha<\omega_1$ and 
$H$ is a continuous symmetric function from a set 
$(\Cantor^\alpha)^2\setminus \Delta$ into $\Cantor$
then there exists an $E\in\mathPerf_\alpha$ such that 
$H$ is uniformly continuous on $E^2\setminus\Delta$.
}

\proof 
For $n<\omega$ define $h_n\colon (\Cantor^\alpha)^2\setminus \Delta\to 2$
by $h_n(s,t)=H(s,t)(n)$.
Thus each $h_n$ satisfies the assumptions 
of Lemma~\ref{lemGal}.

Using Fusion Lemma~\ref{SimpleFusionLemma} with $\A=\mathPerf_\alpha$ 
we will find an $E\in\mathPerf_\alpha$ for which
each $h_n$ is uniformly continuous on $E^2\setminus\Delta$.
Then clearly $H=\la h_n\colon n<\omega\ra$ 
is also uniformly continuous on this set. 


For $k<\omega$ let 
$\D_k\subset[\mathPerf_\alpha]^{<\omega}$ 
be the collection of all families 
$\left\{P_i\colon i<m\right\}$ of pairwise disjoint sets 
such that
\begin{equation}\label{eqMainUCsym}
h_k\ \mbox{ is constant on $P_i\times P_i\setminus\Delta$ \ for each $i<m$.} 
\end{equation}
Clearly sets $\D_k$'s satisfy conditions (P1) and (P2) from 
Lemma~\ref{SimpleFusionLemma}.
Thus, we need to verify only (P3). 

So, fix $k<\omega$, $E\in\mathPerf_\alpha$, and  $\gamma<\alpha$.
It is enough to find 
disjoint subprisms 
$E_0,E_1$ of $E$ 
such that $\pi_{\gamma}[E_0]=\pi_{\gamma}[E_1]$ and
\[
h_k\ \mbox{ is constant on $E_j\times E_j\setminus\Delta$ \ for each $j<2$.} 
\]
Let $f\in\Phi_{\rm prism}(\alpha)$ be such that
$E=f\left[\Cantor^\alpha\right]$
and let
$h\colon(\Cantor^\alpha)^2\setminus \Delta\to 2$
be defined by $h(s,t)=h_k(f(s),f(t))$. 
Then $h$ satisfies the assumptions of Lemma \ref{lemGal}
so there exists a $P\in\mathPerf_\alpha$ such that 
$h$ is constant on $P^2\setminus\Delta$.
Choose disjoint subsets $E_0,E_1\in\mathPerf_\alpha$ of $P$
such that $\pi_{\gamma}[E_0]=\pi_{\gamma}[E_1]$.
(If $g\in\Phi_{\rm prism}(\alpha)$ is such that
$P=f\left[\Cantor^\alpha\right]$ and 
$B_i=\{x\in\Cantor^\alpha\colon x(\gamma)(0)=i\}$ 
then we can put $E_i=g[B_i]$.)
Then $E_0$ and $E_1$ satisfy (P3). 



Now, by Lemma~\ref{SimpleFusionLemma}, there exist 
$\E_k=\left\{P^k_i\colon i<m_k\right\}\in \D_k$ such that 
$E=\bigcap_{k<\omega}\bigcup_{i<m_k}P^k_i\in\mathPerf_\alpha$.
Notice that if $\left\{P_i^k\colon i<m_k\right\}$ belongs to $\D_k$
then $h_k$ is uniformly continuous on 
\[
\left(\bigcup_{i<m_k}P_i^k\right)^2\setminus\Delta=
\left(\bigcup_{i\neq n}P_i^k\times P_n^k\right)\cup
\bigcup_{i<m_k}\left(P_i^k\times P_i^k\setminus\Delta\right).
\]
So each $h_k$ is uniformly continuous $E^2\setminus\Delta\subset
\left(\bigcup_{i<m_k}P_i^k\right)^2\setminus\Delta$.
\qed



\medskip

\noindent{\sc Proof of Proposition \ref{prMainUCsym}.} 
Let $f_0\in\Phi_{\rm prism}(\alpha)$ be such that $E=f_0\left[\Cantor^\alpha\right]$
and put 
\begin{equation}\label{eqMora1}
F=G\circ\la h\circ f_0,h\circ f_0\ra\colon 
(\Cantor^\alpha)^2\setminus\Delta\to[0,1].
\end{equation}
Note also that
\begin{equation}\label{eqMora2}
F=h_0\circ H
\end{equation}
for some continuous symmetric function from 
$H\colon (\Cantor^\alpha)^2\setminus\Delta\to \Cantor$
and continuous $h_0\colon \Cantor\to[0,1]$.
This follows immediately from Lemma~\ref{lemFact}
used with 
$f=F\restriction \left\{\la x,y\ra\in 
\Cantor^\alpha\times\Cantor^\alpha\colon x<y\right\}$,
where $<$ is the lexicographical order on~$\Cantor^\alpha$. 
(We use the lexicographical order in which $\Cantor^\alpha$ is identified with
$2^{\alpha\times\omega}$ and $\alpha\times\omega$ is ordered in type $\omega$.
Then the set $\left\{\la x,y\ra\in \Cantor^\alpha\times\Cantor^\alpha\colon x<y\right\}$
is open in $\Cantor^\alpha\times\Cantor^\alpha$.) 

Now, by Lemma~\ref{lemMainUCsym}, 
then there exists an $E_0\in\mathPerf_\alpha$ such that 
$H$ is uniformly continuous on $(E_0)^2\setminus\Delta$.
So $H$ can be extended to a uniformly continuous 
function $\hat H$ on $(E_0)^2$.
Then function 
\[
\hat G=h_0\circ \hat H\circ \la h\circ f_0,h\circ f_0\ra^{-1}
=h_0\circ \hat H\circ \la(f_0)^{-1}\circ h^{-1},(f_0)^{-1}\circ h^{-1}\ra
\]
is also uniformly continuous on $(h[f_0[E_0]])^2$. 
Put $E_1=f_0[E_0]$ and notice that it is as desired.

Indeed, clearly $E_1\in\mathPerf_\alpha$ and $E_1\subset E$.
Moreover, 
it is not difficult to see that 
$G\restriction (h[E_1])^2\setminus\Delta=
\hat G\restriction (h[E_1])^2\setminus\Delta$. 
So $G$ is uniformly continuous on 
$(h[E_1])^2\setminus\Delta$. \qed



\section{Theorem~\ref{thcCov3}: on 
$\cov\left(D^n,\C^n\right)<\continuum$}\label{sec6}

In the proof we will use the following lemma.

\lem{3.4Lem1}{For $n<\omega$ let 
$f\in\C^n$ and let $P\subset\real$ be a perfect set 
for which the function $F\colon P^2\setminus\Delta\to\real$
defined by 
\[
F(x,y)=\frac{f^{(n)}(x)-f^{(n)}(y)}{x-y}
\]
is uniformly continuous and bounded. Then $f\restriction P$ can be extended
to a $\C^{n+1}$ function. 
}

\proof This follows from the fact that $f\restriction P$ satisfies the 
assumptions of Whitney's extension theorem.
To see this notice first that $F$ naturally extends to a continuous function
on $P^2$ with $F(a,a)=f^{(n+1)}(a)$. 
Next, for $q=1,2,3,\ldots$ and $a\in P$ let
\[
\eta_q(a)=\sup
\left\{\left|\frac{f^{(n)}(x)-f^{(n)}(a)}{x-a}-f^{(n+1)}(a)\right|
\colon 0<|x-a|<\frac{1}{q}\right\}.
\]
In the second part of the proof of~\cite[Thm.~3.1.15]{Fed} 
it is shown that if 
\begin{equation}\label{eqWhitney1}
\lim_{q\to\infty}\sup\{\eta_q(a)\colon a\in P\}=0
\end{equation}
then $f\restriction P$ satisfies the 
assumptions of Whitney's extension theorem. However we have
\[
\frac{f^{(n)}(x)-f^{(n)}(a)}{x-a}-f^{(n+1)}(a)=F(x,a)-F(a,a),
\]
so uniform continuity of $F$ clearly implies (\ref{eqWhitney1}). 
\qed


\medskip

\noindent{\sc Proof of Theorem~\ref{thcCov3}.} 
The lower bound inequalities
$\cov\left(D^n,\C^n\right)>\omega$ and 
$\cov\left(``D^n\mbox{''},``\C^n\mbox{''}\right)>\omega$
follow from Example~\ref{CD4a}.
So it is enough to prove only that these numbers are 
$\leq\omega_1$. 


To prove $\cov\left(D^n,\C^n\right)\leq \omega_1$, take an $f\in D^n$
and note that, by \psmP, it is enough to show that
the following set  
\[
\E=\left\{E\in\perf(\real)\colon(\exists h\in\C^{n}(\real))
\ h\restriction E=f\restriction E \right\}
\]
is $\Fpr$-dense. So fix a prism $P$ in $\real$. 
Let $k\colon[-\infty,\infty]\to[0,1]$ be a homeomorphism. 
Applying $n$-times Proposition~\ref{prMainUCsym}
in the same way as in the proof of Lemma~\ref{lemDens1} 
we find a subprism $E$ of $P$ such that for 
each $i< n$ the function 
$k\circ F_i\colon E^2\setminus\Delta\to[0,1]$
is uniformly continuous, where 
$F_i\colon E^2\setminus\Delta\to\real$ is defined by
\[
F_i(x,y)=\frac{f^{(i)}(x)-f^{(i)}(y)}{x-y}.
\]
So each $F_i$ can be extended to a continuous
function $\bar F_i\colon E^2\to[-\infty,\infty]$.
Note also that since $\bar F_i(x,x)=f^{(i+1)}(x)\in\real$,
as $f\in D^n$, we in fact have $\bar F_i[E^2]\subset\real$.


Next, starting with $f_0=f$ 
we use Lemma~\ref{3.4Lem1} to prove by induction that
for every $i< n$ there exists an $f_{i+1}\in\C^{i+1}(\real)$
extending $f_i\restriction E$. Then 
function $h=f_n\in\C^n(\real)$
witnesses that $E\in\E$. 

To prove $\cov\left(``D^n\mbox{''},``\C^n\mbox{''}\right)\leq \omega_1$, 
take an $f\in``D^n\mbox{''}$. As before it is enough to show that
\[
\E'=\left\{E'\in\perf(\real)\colon(\exists h\in``\C^{n}(\real)\mbox{''})
\ h\restriction E'=f\restriction E' \right\}
\]
is $\Fpr$-dense. So fix a prism $P$ in $\real$ and find $E$,   
$F_i$'s, and $\bar F_i$'s as above. 
Note that $F_i$'s are well defined since
$f\in``D^n\mbox{''}\subset\C^{n-1}$.
By the same reason we have that $\bar F_i[P^2]\subset\real$
for all $i<n-1$.
However, $\bar F_{n-1}$ can have infinite values. 

Proceeding as in the proof of Lemma~\ref{lemDens1}, 
decreasing $E$ if necessary, 
we can assume that either the range of 
$\bar F_{n-1}$ is bounded
or $\bar F_{n-1}\restriction P^2\cap\Delta$ is constant equal to 
$\infty$ or $-\infty$. 
If $\bar F_{n-1}$ is bounded then, taking $E'=E$, we are done as in 
the previous case.
So, assume that $\bar F_{n-1}[P^2\cap\Delta]=\{\infty\}$.
(The case of $-\infty$ is handled by replacing $f$ with $-f$.)
Then $f^{(n-1)}$ and $E$ satisfy the assumptions
of Brown's version of Whitney's extension 
theorem~\cite[Thm.~2.1]{Br2}.
So, we can find a ``$\C^1$''
extension $g\colon\real\to\real$ of $f^{(n-1)}\restriction E$
such that $g'[E]=(f^{(n-1)})'[E]=\{\infty\}$
and $g'[\real\setminus E]\subset\real$. 
By $(n-1)$-times integrating $g$ we can find a $G\colon\real\to\real$
such that $G^{(n-1)}=g$. 
Then $G\in``\C^n$''. 
Next notice that $G-f\in\C^n(E)$, since
$(G-f)^{(n-1)}=g-f^{(n-1)}\equiv 0$ on $E$. 
Now, proceeding as above for the case 
of $f\in\C^n$
we can find a subprism $E'$ of $E$
and a function $\hat h\in\C^n(\real)$ extending $G-f\restriction E'$.
Then function $h=G-\hat h$ belongs to $``\C^n$''
as a difference of functions from $``\C^n$'' and $\C^n$.
Moreover, $h$ extends $f\restriction E'$ since 
$h=G-\hat h=G-(G-f)=f$ on $E'$. 
So, $h$ witnesses $E'\in\E'$. \qed


\section{Examples related to $\cov$ operator}

We will start with the examples needed for 
the proof of Proposition~\ref{PropTh2Bound}
which give $\continuum$ as a lower bound for 
the appropriate numbers $\cov(\A,\F)$.

\ex{exZUc2}{There exist a homeomorphism $h\colon\real\to\real$
and a perfect set $P\subset\real$ such that $h,h^{-1}\in``\C^2$'',
$h''\restriction P\equiv\infty$, and 
$(h^{-1})''\restriction h[P]\equiv -\infty$.
In particular 
$\neg\IntTh
\left(h\restriction P,D_{\rm perf}^2\cup(D_{\rm perf}^2)^{-1}\right)$
and
\[
\cov\left(``\C^2\mbox{''},D_{\rm perf}^2\cup(D_{\rm perf}^2)^{-1}\right)=
\cov\left(h,D_{\rm perf}^2\cup(D_{\rm perf}^2)^{-1}\right)=
\continuum.
\]
}

\proof First notice that there exist a strictly
increasing homeomorphism $h_0$
from $\real$ onto $(0,\infty)$ and a perfect set $P\subset\real$
such that 
\begin{equation}\label{eq:FunGa}
\mbox{$h_0\in``\C^1$''\ \  and\ \  $h_0'\restriction P\equiv\infty$.}
\end{equation}

Indeed, let $C$ be an arbitrary nowhere dense perfect subset of 
$[2,3)$ with $2\in C$ and let $d(x)$ denotes the distance between $x\in\real$ and $C$.
Let $f_0\colon(0,\infty)\to[0,\infty)$ be defined by
$f_0(x)=x^{-2}$ for $x\in(0,1]$ and 
$f_0(x)=d(x)$ for $x\in[1,\infty)$. Then $f_0$ is continuous
and $f_0(x)=0$ precisely when $x\in C$. 
Define a strictly increasing function $f$ from 
$(0,\infty)$ onto $\real$ by a formula 
$f(x)=\int_1^x f_0(t)\, dt$.
Then $f'=f_0$ and $f(x)=1-\frac{1}{x}$ on $(0,1)$. 
It is easy to see that $h_0=f^{-1}$ and $P=f[C]\subset(0,\infty)$ 
satisfy (\ref{eq:FunGa}).

Now put $h(x)=\int_0^x h_0(t)\, dt$. Then clearly $h$ is strictly
increasing since $h_0$ is positive.
Also $h$ is onto $\real$ as on $(-\infty,0)$ we have
$h_0(x)=\frac{1}{1-x}$ and so $h(x)=-\ln(1-x)$. 
It is easy to see that $h'=h_0$ so, by (\ref{eq:FunGa}), 
$h\in``\C^2$'' and $h''\restriction P\equiv\infty$.
Also, if $g=h^{-1}$ then $g'(x)=1/h'(g(x))=1/h_0(g(x))>0$
is strictly decreasing and $h^{-1}=g\in\C^1$.
Thus, to see that $h^{-1}=g\in``\C^2$'' 
and that 
$(h^{-1})''\equiv-\infty$ 
on $h[P]=h[f[C]]$ it is enough
to differentiate 
$g'(x)$ (note that the differentiation formulas are valid, if just one of 
the terms is infinite) to get 
$g''(x)=-[h'(g(x))]^{-2} h''(g(x)) g'(x)=-h''(g(x)) (g'(x))^3$.
Thus, $h$ and $P$ have the desired properties. 

To see the additional part note first that for every $f\in D_{\rm perf}^2$
functions $f$ and $h\restriction P$ may agree on at most countable set $S$
since at any point $x$ of a perfect subset $Q$ of $S$ we would have
\[
(h\restriction Q)''(x)=\infty\neq(f\restriction Q)''(x).
\]
Similarly, $|f\cap(h\restriction P)|\leq\omega$ for every 
$f\in(D_{\rm perf}^2)^{-1}$.
This clearly implies the additional part. \qed

\ex{CD1}{There exists a perfect set $P\subset\real$ and a function 
$f\in``\C^1$'' such that $f'(x)=\infty$ for every $x\in P$. In particular
$\neg\IntTh
\left(f\restriction P,D_{\rm perf}^1\right)$
and
\[
\cov\left({\rm Borel},\C^1\right)=\cov\left(``\C^1\mbox{''},\C^1\right)=
\cov\left(``\C^1\mbox{''},D_{\rm perf}^1\right)=\cov\left(f,D_{\rm perf}^1\right)=\continuum.
\]
}
\proof If $f$ is a function $h_0$ from (\ref{eq:FunGa}) then it has the desired properties.  

For such an $f$ and any function $g\in D_{\rm perf}^1$
the intersection $f\cap g$ must be finite. 
So
\[
\continuum\geq
\cov\left({\rm Borel},\C^1\right)\geq
\cov\left(``\C^1\mbox{''},D_{\rm perf}^1\right)
\geq\cov\left(f,D_{\rm perf}^1\right)\geq\continuum.
\]
Monotonicity of $\cov$ operator gives the other equations. \qed 


\ex{CD1a}{For every $0<n<\omega$ there exists an $f\in``\C^n\mbox{''}$ 
and a perfect set $P\subset\real$ 
such that 
$\neg\IntTh
\left(f\restriction P,D^n_{\rm perf}\right)$
so that
\[
\cov(``\C^n\mbox{''},\C^n)=\cov(``\C^n\mbox{''},D_{\rm perf}^n)=
\cov(f,D_{\rm perf}^n)=\continuum.
\]
}

\proof For $n=1$ this is a restatement of Example \ref{CD1}. 
The general case can be done by induction: If $f$ is good for some $n$
and $F$ is a definite integral of $f$ then 
$F\in``\C^{n+1}\mbox{''}$ and 
$\neg\IntTh(F\restriction P,D_{\rm perf}^{n+1})=\continuum$.
\qed

\ex{CD3}{There exists an $f\in\C^1$ and a perfect set $P\subset\real$
such that $|(f\restriction P)\cap g|\leq\omega$ for every $g\in ``D^2$''. 
In particular
$\neg\IntTh\left(f\restriction P,``D^2\mbox{''}\right)$
and 
\[
\cov\left(\C^1,``D^2\mbox{''}\right)=
\cov\left(f,``D^2\mbox{''}\right)=\continuum.
\]
}

\proof In~\cite[Thm.~22]{ABLP} the authors construct a
perfect set $P\subset[0,1]$ and a function $f\in\C^1$ 
which have the desired properties. The argument for this is implicitly
included in the proof of \cite[Thm.~22]{ABLP} and goes like that.

Function $f$ has the property that $f'(x)=0$ for all $x\in P$.
Now, assume that some $g\in``D^2$'' agrees with $f$ on a perfect set $Q\subset P$.
Then clearly we would have 
$(g\restriction Q)''\equiv[(g\restriction Q)']'\equiv[(f\restriction Q)']'\equiv
[0]'\equiv 0$. On the other hand, in \cite[Thm.~22]{ABLP} it is 
shown\footnote{Actually, the calculation in~\cite[thm. 22]{ABLP} 
is done under the assumption that
$g\in C^2$, but it works also under our weaker assumption that $g\in``D^2$''.}
that for such a $g$
we would have $g''(x)\in\{\pm\infty\}$ 
for every $x\in Q$, a contradiction. \qed


\ex{CD3a}{For every $0<n<\omega$ there exist an $f\in\C^n$ 
and a perfect set $P\subset\real$ such that
$\neg\IntTh\left(f\restriction P,``D^{n+1}\mbox{''}\right)$
and
\[
\cov\left(\C^n,``D^{n+1}\mbox{''}\right)=
\cov\left(f,``D^{n+1}\mbox{''}\right)=\continuum.
\]
}

\proof For $n=1$ this is a restatement of Example \ref{CD3}. 
The general case can be done by induction: If $f$ is good for some $n$
and $F$ is a definite integral of $f$ then 
$F\in\C^{n+1}$ and $\neg\IntTh(F\restriction P,D_{\rm perf}^{n+1})=\continuum$.
\qed


Next we will describe the 
examples showing that the $\cov(\A,\F)$ numbers 
considered in Corollary~\ref{corth2} and Theorem~\ref{thcCov3}
have values greater than $\omega$. 
In what follows $\cov({\cal M})$ ($\cov({\cal N})$, respectively)  
will stand for the smallest cardinality of a family $\F\subset\P(\real)$
of measure zero sets (nowhere dense, respectively) 
such that $\real=\bigcup\F$. 

\ex{CD4}{There exists a function $f\in D^1$ such that 
\[
\cov\left(f,``\C^1\mbox{''}\cup(D^1)^{-1}\right)\geq\cov({\cal M})>\omega.
\]
In particular
\[
\cov\left({\rm Borel},``\C^1\mbox{''}\right)\geq 
       \cov\left(D^1,``\C^1\mbox{''}\right)\geq\cov({\cal M})>\omega
\]
and 
\[
\cov\left({\rm Borel},\C^1\cup(\C^1)^{-1}\right)\geq
       \cov\left(D^1,\C^1\cup(\C^1)^{-1}\right)\geq\cov({\cal M})>\omega.
\]
}

\proof We will construct function $f$ only on $[0,1]$. It can be easily modified to
a function defined on $\real$.

Let $E\subset[0,1]$ be an $F_\sigma$-set of measure $1$ such that $E^c=[0,1]\setminus E$
is dense in $[0,1]$. It is well known that there exists a derivative
$g\colon[0,1]\to[0,1]$ such that
$g[E]\subset(0,1]$ and $g[E^c]=\{0\}$. 
(See e.g. \cite[p.~24]{Bruckner}.) Let $f\colon[0,1]\to\real$
be such that $f'=g$. We claim that this $f$ is as desired.

Indeed, by way of contradiction assume that for some $\kappa<\cov({\cal M})$
there exists a family 
$\{h_\xi\in\real^\real\colon \xi<\kappa\}\subset 
``\C^1\mbox{''}\cup(D^1)^{-1}$ such that 
$f\subset\bigcup_{\xi<\kappa} h_\xi$. 
Since $h_\xi$ are closed subsets of 
$\real^2$ and the graph of $f$ is compact, we
see that the $x$-coordinate projections $P_\xi=\pi_x[f\cap h_\xi]$ 
are closed. So, $[0,1]$ is covered by less than $\cov({\cal M})$
closed sets $P_\xi$. Thus, there exists an $\eta<\kappa$ such that
$P_\eta$ has non-empty interior $U=\inter(P_\eta)$. 

Now, if $h_\eta\in``\C^1\mbox{''}$ then 
$h_\eta'=f'=g$ on $U$, which is impossible, since
$h_\eta'$ is continuous, while $g$ is not continuous on any
non-empty open set. 
So assume that $h_\eta\in(D^1)^{-1}$. 
Note that $f$ is strictly increasing as an integral of 
function $g$ which is strictly positive a.e.
So $f^{-1}$ is a strictly increasing and agrees with 
$h=h_\eta^{-1}\in D^1$ on an open set $f[U]$. 
But then if $x\in U\setminus E$ then 
$h'(f(x))=(f^{-1})'(f(x))=\frac{1}{f'(x)}=\infty$
which contradicts $h\in D^1$. \qed

Note also that if $f$ from Example~\ref{CD4} is replaced by its 
\mbox{$(n-1)$-st}
antiderivative then we get also the following example. 

\ex{CD4a}{For any $0<n<\omega_1$ there exists an $f\in D^n$ such that 
\[
\cov\left(D^n,``\C^n\mbox{''}\right)\geq
\cov\left(f,``\C^n\mbox{''}\right)\geq\cov({\cal M})>\omega.
\]
}

\ex{CD5}{There exists an $f\in\C^0$ such that
\[
\cov(\C^0,``D^1_{\rm perf}\mbox{''})\geq
\cov(f,``D^1_{\rm perf}\mbox{''})
\geq\cov({\cal N})>\omega.
\]
Moreover, for every $n<\omega$ if $F\in\C^n$ is such that $F^{(n)}=f$ then
\[
\cov(\C^n,``D^{n+1}_{\rm perf}\mbox{''})\geq
\cov(F,``D^{n+1}_{\rm perf}\mbox{''})
\geq\cov({\cal N})>\omega
\]
and
\[
\cov\left({\rm Borel},``\C_{\rm perf}^\infty\mbox{''}\right)\geq
\cov\left(\C^n,``\C_{\rm perf}^\infty\mbox{''}\right)\geq
\cov\left(F,``\C_{\rm perf}^\infty\mbox{''}\right)
\geq\cov({\cal N})>\omega.
\]
}

\proof A continuous function $f$ justifying
$\cov(f,``D^1_{\rm perf}\mbox{''})\geq\cov({\cal N})$
was pointed by Morayne: just take 
any $f\in\C$ for which there is a set $A\subset\real$ of positive 
measure for which $|f^{-1}(a)|=\continuum$ for all $a\in A$. 
(See~\cite[Thm.~6.1]{St2}.)

To see the additional part, let $\G=\{g_\xi\colon\xi<\kappa\}$ be 
an infinite subset of
$``D^{n+1}_{\rm perf}\mbox{''}\cup``\C_{\rm perf}^\infty\mbox{''}$ 
such that $F\subset\bigcup\G$. 
We need to show that $\kappa\geq\cov({\cal N})$. 
For this first note that for every $\xi<\kappa$ the domain of 
$F\cap g_\xi$ can be represented as a union of a perfect set $P_\xi$ 
(which can be empty) and a countable (scattered) set $S_\xi$. 
Let $S=\bigcup_{\xi<\kappa}S_\xi$ and note that it has cardinality 
at most $\kappa$. 
Since $F\restriction P_\xi=g_\xi\restriction P_\xi$, 
by an easy induction on $i\leq n$ we can prove that
\begin{equation}\label{con:exCD5}
\mbox{$F^{(i)}\restriction P_\xi=(g_\xi\restriction P_\xi)^{(i)}$
\ \  provided \ \ $g_\xi\in``D^{i}_{\rm perf}\mbox{''}$ \ and \ $P_\xi\neq\emptyset$.}
\end{equation}
Thus, 
\begin{center}
if $g_\xi\in``D^{n+1}_{\rm perf}\mbox{''}$ and $P_\xi\neq\emptyset$ then
$f\restriction P_\xi=
F^{(n)}\restriction P_\xi=(g_\xi\restriction P_\xi)^{(n)}\in``D^1_{\rm perf}\mbox{''}$.
\end{center}
On the other hand, 
\begin{center}
if $g_\xi\in ``\C_{\rm perf}^\infty\mbox{''}\setminus
``D^{n+1}_{\rm perf}\mbox{''}$ then $P_\xi=\emptyset$. 
\end{center}
Indeed, otherwise there is an $i\leq n$ 
such that $g_\xi\in``D^{i}_{\rm perf}\mbox{''}$ and $g_\xi^{(i)}$ 
is constant equal to $\infty$ or $-\infty$. 
So, by (\ref{con:exCD5}), for any $x\in P_\xi$ a real number
$F^i(x)$ belongs to $\{-\infty,\infty\}$, a contradiction.  

Thus
$\F=\{f\restriction P_\xi\colon \xi<\kappa\ \&\ P_\xi\neq\emptyset\}
\cup\{f\restriction\{x\}\colon x\in S\}
\subset``D^1_{\rm perf}\mbox{''}$
has cardinality at most $\kappa$ and it covers $f$.
So, by the first part, $\kappa\geq\cov({\cal N})$. \qed

\section{Proof of Fusion Lemma \ref{SimpleFusionLemma}}

Notice that if $P\in\mathPerf_\alpha$ and $0<\beta<\alpha$ then 
\begin{equation}\label{eq20x} 
\mbox{$P\cap\pi_\beta^{-1}(P')\in \mathPerf_\alpha$ \ \ \ 
for every $P'\in\mathPerf_\beta$ with $P'\subset\pi_\beta[P]$. 
}
\end{equation}
Indeed, let 
$f\in\Phi_{\rm prism}(\beta)$ and 
$g\in\Phi_{\rm prism}(\alpha)$ be such that 
$f[\Cantor^\beta]=P'$ and $g[\Cantor^\alpha]=P$.
Let 
$Q=(g\restriction\restriction\beta)^{-1}[P']
=(g\restriction\restriction\beta)^{-1} \circ f[\Cantor^\beta]$. 
Then, $Q\in\mathPerf_\beta$ since, by (\ref{eq:restr}),  
$(g\restriction\restriction\beta)^{-1} \circ f\in \Phi_{\rm prism}(\beta)$.
Thus $\pi_\beta^{-1}(Q)$ belongs to $\mathPerf_\alpha$ and 
$P\cap\pi_\beta^{-1}(P')=g[\pi_\beta^{-1}(Q)]\in\mathPerf_\alpha$. 

For a fixed $0<\alpha<\omega_1$ 
let $\{\la \beta_k,n_k\ra\colon k<\omega\}$ be an enumeration of
$\alpha\times\omega$ used in the definition 
(\ref{eqRHO}) of the metric $\rho$ and let
\begin{equation}\label{NiceEnum}
A_k=\{\la \beta_i,n_i\ra\colon i< k\}\ \ \ \mbox{ for every $k<\omega$}.
\end{equation}



\lem{MasterFusionLemma}{{\rm\bf (Master Fusion Lemma)}
Let $0<\alpha<\omega_1$ and for every $k<\omega$ let
$\E_k=\left\{E_s\in\mathPerf_\alpha\colon s\in 2^{A_k}\right\}$.  
Assume that for every $k<\omega$, $s,t\in 2^{A_k}$, 
and $\beta<\alpha$ we have: 
\begin{itemize}
\item[\rm (i)] the diameter of $E_s$ is less than  or equal to $2^{-k}$,
\item[\rm (ii)] if $r\in\bigcup_{i<\omega}2^{A_i}$ and 
$r\subset s$ then $E_s\subset E_r$, 
\item[\rm (iii)] if
  $s\restriction(\beta\times\omega)=t\restriction(\beta\times\omega)$
    then $\pi_{\beta}[E_s]=\pi_{\beta}[E_t]$, 
\item[\rm (iv)] if
  $s\restriction(\beta\times\omega)\neq t\restriction(\beta\times\omega)$
    then $\pi_{\beta}[E_s]\cap\pi_{\beta}[E_t]=\emptyset$.
\end{itemize}
Then $Q=\bigcap_{k<\omega}\bigcup\E_k$ 
belongs to $\mathPerf_\alpha$.
}


\proof For $x\in\Cantor^\alpha$ let $\bar x\in 2^{\alpha\times\omega}$
be defined by $\bar x(\beta,n)=x(\beta)(n)$. 

First note that, by conditions (i) and (iv), for every $k<\omega$ 
the sets
in $\E_k$ are pairwise 
disjoint and each of the diameter at most $2^{-k}$. 
Thus, taking into account (ii), function 
$h\colon\Cantor^\alpha\to\Cantor^\alpha$ defined by 
\[
h(x)=r\ \ \Longleftrightarrow\ \  
\{r\}=\bigcap_{k<\omega}E_{\bar x\restriction A_k}
\]
is well defined and is one-to-one.  It is also easy
to see that $h$ is continuous and that 
$Q=h\left[\Cantor^\alpha\right]$.
Thus, we need to prove only that $h\in\Phi_{\rm prism}(\alpha)$,
that is, that $h$ is projection-keeping. 

To show this 
fix $\beta<\alpha$, put $S=\bigcup_{i<\omega}2^{A_i}$,
and notice that, by (i) and (iii), for every $x\in\Cantor^\alpha$
we have
\begin{eqnarray*}
\{h(x)\restriction\beta\}
& = & \pi_{\beta}\left[
\bigcap\{E_{\bar x\restriction A_k}\colon k<\omega\}\right]\\
& = & 
\bigcap\{\pi_{\beta}[E_{\bar x\restriction A_k}]\colon k<\omega\}\\
& = & 
\bigcap\{\pi_{\beta}[E_s]\colon s\in S\ \&\ s\subset\bar x\}\\
& = & 
\bigcap\{\pi_{\beta}[E_s]\colon s\in S\ \&\ 
s\restriction(\beta\times\omega)\subset\bar x\}.
\end{eqnarray*}
Now, if $x\restriction\beta=y\restriction\beta$
then for every $s\in S$
\[
s\restriction(\beta\times\omega)\subset\bar x\ \ \Equi\ \ 
s\restriction(\beta\times\omega)\subset\bar y
\]
so
$h(x)\restriction\beta=h(y)\restriction\beta$.

On the other hand, if $x\restriction\beta\neq y\restriction\beta$
then there exists $k<\omega$ big enough such that for 
$s=\bar x\restriction A_k$ and 
$t=\bar y\restriction A_k$ we have 
$s\restriction (\beta\times\omega)\neq t\restriction (\beta\times\omega)$.
But then  
$\{h(x)\restriction\beta\}$ and $\{h(y)\restriction\beta\}$
are subsets of $\pi_{\beta}[E_s]$ and $\pi_{\beta}[E_t]$,
respectively, which, by (iv), are disjoint. 
So, $h(x)\restriction\beta\neq h(y)\restriction\beta$. \qed

\medskip

\noindent{\sc Proof of Lemma~\ref{SimpleFusionLemma}}.
Let us define  $\D_{-1}=\{\{\Cantor^\alpha\}\}$. 
It is enough to 
construct a sequence $\la \E_k\in \D_{k-1}\colon k<\omega\ra$ 
satisfying conditions (i)-(iv) from
Lemma~\ref{MasterFusionLemma}. This will be done by induction 
on $k<\omega$. 

We start with $\E_0=\{\Cantor^\alpha\}$. 
Clearly at this stage (i)-(iv) are satisfied. 
So, assume that for some $k<\omega$
a sequence $\la \E_j\colon j\leq k\ra$ satisfying (i)-(iv)
is already defined. We will construct $\E_{k+1}$.

Let $\{s_i\colon i<2^k\}$ be an enumeration of
$2^{A_k}$. Thus $\E_k=\{E_{s_i}\colon i<2^k\}$.  Also, 
let $\gamma=\max\{\beta_0,\ldots,\beta_{k}\}<\alpha$,
and for every $i,m<2^k$ put
\[
\beta^m_i=\max\{\beta\leq\gamma\colon 
s_i\restriction(\beta\times\omega)=s_m\restriction(\beta\times\omega)\}.
\]
As a first step of the proof 
we will construct, by induction on $m\leq 2^k$, the sequences 
$\la\{E_{s_i}^m\in\A\colon i<2^k\}\colon m\leq 2^k\ra$ and 
$\la P_m^j\in\A\colon j<2\ \&\ m<2^k\ra$
such that for every $n<m\leq 2^k$ and $i<2^k$
\begin{itemize}
\item[(a)] $\E^m\stackrel{\rm def}{=}\{E_{s_i}^m\in\A\colon i<2^k\}$ satisfies (iii), 
\item[(b)] $E_{s_i}^n\supset E_{s_i}^m$,
\item[(c)] $P_n^0$ and $P_n^1$ are disjoint subsets of 
$E_{s_n}^{n}$ such that $\{P_n^0,P_n^1\}\in\D_k$ and 
$\pi_{\gamma}[P_n^0]=\pi_{\gamma}[P_n^1]=\pi_{\gamma}[E_{s_n}^{n+1}]$.
\end{itemize}

We start with putting $E_{s_i}^0=E_{s_i}$ for every $i<2^k$.
So, (a)-(c) clearly hold. 
Next, if for an $m<2^k$ family 
$\E^m$ satisfying (iii) is already constructed
apply (P3) to find disjoint 
$P_m^0,P_m^1\in\D_k$
subsets of $E_{s_m}^m$ for which 
$\pi_\gamma[P_m^0]=\pi_\gamma[P_m^1]$.
Then for $i<2^k$ we put 
\begin{equation}\label{xxx}
E^{m+1}_{s_i}=
E^m_{s_i}\cap\pi_{\beta^m_i}^{-1}(\pi_{\beta^m_i}[P_m^0])
=\left\{x\in E^m_{s_i}\colon x\restriction \beta^m_i\in 
\pi_{\beta^m_i}[P_m^0]\right\}.
\end{equation}
Notice that $\pi_{\beta^m_i}[P_m^0]\subset
\pi_{\beta^m_i}[E_{s_m}^m]=\pi_{\beta^m_i}[E_{s_i}^m]$
so, by (\ref{eq20x}), 
$E^{m+1}_{s_i}\in\A$. Also, by the inductive assumption (a), 
\[
\pi_{\beta^m_i}[E^{m+1}_{s_i}]
=\pi_{\beta^m_i}[E^m_{s_i}]\cap\pi_{\beta^m_i}[P_m^0]
=\pi_{\beta^m_i}[E^m_{s_m}]\cap\pi_{\beta^m_i}[P_m^0]
=\pi_{\beta^m_i}[P_m^0].
\]
Since $\beta^m_m=\gamma$, this implies immediately (c).
It is clear that (b) holds.
Thus, it is enough to show that $\E^{m+1}$ satisfies (iii).
So, pick $\beta<\alpha$ and different $i<j<2^k$
such that 
$s_i\restriction(\beta\times\omega)=s_j\restriction(\beta\times\omega)$.
If $\beta\leq\beta^m_i$ then also $\beta\leq\beta^m_j$
and 
$\pi_{\beta}[E^{m+1}_{s_i}]=\pi_{\beta}[P_m^0]=\pi_{\beta}[E^{m+1}_{s_j}]$.
So, assume that 
$\beta>\beta^m_i$ and $\beta>\beta^m_j$. Then
$\beta^m_i=\beta^m_j$ and
\begin{eqnarray*}
\pi_\beta[E^{m+1}_{s_i}]
& = &
\left\{\pi_\beta(x)\colon x\in E^m_{s_i}\ \&\ 
\pi_\beta(x)\restriction \beta^m_i\in \pi_{\beta^m_i}[P_m^0]\right\}\\
& = &
\left\{\pi_\beta(x)\colon x\in E^m_{s_j}\ \&\ 
\pi_\beta(x)\restriction \beta^m_j\in \pi_{\beta^m_j}[P_m^0]\right\}\\
& = &
\pi_\beta[E^{m+1}_{s_j}].
\end{eqnarray*}
So $\E^{m+1}$ satisfies (iii). This finishes the construction. 

\medskip

Next for $i<2^k$ put $E_{s_i}'=E_{s_i}^{2^k}\subset E_{s_i}$ and notice that
\begin{itemize}
\item[\rm (P$3'$)] 
for every $n<2^k$ there are disjoint
$F_{s_n}^0,F_{s_n}^1\in\A$ such that 
$F_{s_n}^0\cup F_{s_n}^1\subset E_{s_n}'$, $\{F_{s_n}^0,F_{s_n}^1\}\in\D_k$,
and $\pi_{\gamma}[F_{s_n}^0]=\pi_{\gamma}[F_{s_n}^1]=\pi_{\gamma}[E_{s_n}']$.
\end{itemize}
Indeed, for $j<2$ define 
$F_{s_n}^j=P_n^j\cap\pi_\gamma^{-1}(\pi_\gamma[E_{s_n}'])$
and note that $F_{s_n}^j\in\A$ by (\ref{eq20x}), 
since $\pi_\gamma[E_{s_n}']
\subset\pi_{\gamma}[E_{s_n}^{n+1}]=\pi_{\gamma}[P_n^j]$. 
So, $\{F_{s_n}^0,F_{s_n}^1\}\in\D_k$ by (P1). The equations hold since, by (c), 
\begin{eqnarray*}
\pi_{\gamma}[F_{s_n}^j]
& = &
\left\{\pi_{\gamma}(x)\colon x\in P_n^j\ \&\ x\restriction \gamma\in 
\pi_\gamma[E_{s_n}']\right\}\\
& = &
\left\{\pi_{\gamma}(x)\colon x\in E_{s_n}^{n+1}\ \&\ x\restriction \gamma\in 
\pi_\gamma[E_{s_n}']\right\}\\
& = &
\pi_\gamma[E_{s_n}'].
\end{eqnarray*}
Finally, 
$F_{s_n}^j=\{x\in P_n^j\colon x\restriction \gamma\in 
\pi_\gamma[E_{s_n}']\}$ is a subset of $E_{s_n}'$
since $P_n^j\subset E_{s_n}^{n+1}$
and, by (\ref{xxx}), if $x\in E_{s_n}^{n+1}\setminus E_{s_n}'$
then $x\restriction \gamma\notin\pi_\gamma[E_{s_n}']$.
So, (P$3'$) holds. 


Next, by induction on $i<2^{k}$, 
choose a sequence $\la x_i^j\in F_{s_i}^j\colon j<2\ \&\ i<2^{k}\ra$
such that 
for every $j<2$ and $m\leq i<2^{k}$
\begin{equation}\label{defXs}
\mbox{$x_i^0\restriction\beta_k=x_i^1\restriction\beta_k$,
$x_i^0(\beta_k)\neq x_i^1(\beta_k)$, and
$x_i^j\restriction\beta_i^m=x_m^j\restriction\beta_i^m$.}
\end{equation}
By (P$3'$) it is easy to find $x_0^0$ and $x_0^1$ satisfying 
(\ref{defXs}). 
So, assume that for some $0<i<2^k$ we already have 
defined $\la x_m^j\colon j<2\ \&\ m<i\ra$. 
To find $x_i^0$ and $x_i^1$ let 
$\beta=\max\{\beta^m_i\colon m<i\}$ and choose an $n<i$ which
witnesses it, that is such that $\beta=\beta^n_i$. 
Since, by (a) and (P$3'$), 
$\pi_{\beta}[F_{s_i}^j]=\pi_{\beta}[F_{s_n}^j]$, for $j<2$,
we can find an 
$x_i^0\in F_{s_i}^0$ extending $x_{n}^0\restriction\beta$. 
Then $x_i^0\restriction\beta_i^m=x_n^0\restriction\beta_i^m=x_m^0\restriction\beta_i^m$
for all $m<i$. 

Next, if $\beta_k<\beta$ as above we choose an 
$x_i^1\in F_{s_i}^1$ extending $x_{n}^1\restriction\beta$
and note that (\ref{defXs}) is satisfied since this was the case for $i=n$.
So, assume that $\beta\leq\beta_k\leq\gamma$.
Then, by (P$3'$), we can find an 
$x_i^1\in F_{s_i}^1$ extending $x_i^0\restriction\beta_k$
such that $x_i^1(\beta_k)\neq x_i^0(\beta_k)$.
Then (\ref{defXs}) holds as well. 

Finally, for $s\in 2^{A_{k}}$ and $j<2$ let
$s\hat{\ }j$ stand for 
$s\cup\{\la \la \beta_{k},n_{k}\ra,j\ra\}\in 2^{A_{k+1}}$
and for $i<2^k$ define 
\[
E_{s_i\hat{\ }j}=F_{s_i}^j\cap B_\alpha(x_i^j,2^{-k}).
\]
Let $\E_{k+1}=\{E_s\colon s\in 2^{A_{k+1}}\}$. 
To finish the proof it is enough to show that $\E_{k+1}$
satisfies (i)-(iv) from Lemma~\ref{MasterFusionLemma}.
Thus, (i) follows from the fact that 
$E_{s_i\hat{\ }j}\subset B_\alpha(x_i^j,2^{-k})$; 
(ii) is justified by 
$E_{s_i\hat{\ }j}\subset F_{s_i}^j\subset E_{s_i}'\subset E_{s_i}$; 
while 
(iii) and (iv) can be easily deduced from (P$3'$),
(\ref{defXs}), and (\ref{eq18x}).
\qed


\begin{thebibliography}{22}

\bibitem{ABLP} S.~Agronsky, A.~M.~Bruckner, M.~Laczkovich, D.~Preiss,   
{\it Convexity conditions and intersections
with smooth functions}, Trans. Amer. Math. Soc. {\bf 289} (1985), 659--677.

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

\bibitem{Br2} J.~B.~Brown, {\it Differentiable restrictions of real  
functions},
Proc. Amer. Math. Soc. {\bf 108} (1990), 391--398.

\bibitem{Br1} J.~B.~Brown, {\it Restriction theorems in real analysis},
Real Anal. Exchange {\bf 20}(1) (1994--95), 510--526.

\bibitem{Bruckner}  A.~M.~Bruckner, {\it Differentiation of Real Functions}, CMR
Series vol. 5, Amer. Math. Soc., 1994.



\bibitem{Burges} J.~P.~Burges, {\it A selector principle for 
$\Sigma^1_1$ equivalence relations},
Michigan Math. J. {\bf 24} (1977), 65--76.



\bibitem{cimopaso} J.~Cicho\'{n}, M.~Morayne, J.~Pawlikowski, S.~Solecki, {\it
Decomposing {B}aire functions}, J. Symbolic Logic {\bf 56}(4) (1991), 1273--1283.


\bibitem{KCsurv} K.~Ciesielski,
{\it Set theoretic real analysis}, J. Appl. Anal. {\bf 3}(2) (1997), 143--190.
(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{CiBook} K.~Ciesielski,
{\it Set Theory for the Working Mathematician}, 
London Math. Soc. Stud. Texts {\bf 39}, Cambridge Univ. Press 1997.

\bibitem{KCdecomp} K.~Ciesielski,
{\it Decomposing symmetrically continuous functions and Sierpi\'nski-Zygmund 
functions into continuous functions}, Proc. Amer. Math. Soc. 
{\bf 127} (1999), 3615--3622. (Preprint$^\star$ available.)



\bibitem{CN}  K.~Ciesielski, T. Natkaniec, {\it On Sierpi\'{n}ski-Zygmund
bijections  and their inverses}, Topology Proc. {\bf 22} (1997), 155--164.
(Preprint$^\star$ available.)

\bibitem{CP83} K.~Ciesielski, J.~Pawlikowski,
{\it Crowded and selective ultrafilters under the Covering Property Axiom}, 
J. Appl. Anal. {\bf 9(1)} (2003), 19--55.
(Preprint$^\star$ available.)


\bibitem{CPAbook} K.~Ciesielski, J.~Pawlikowski,
{\it Covering Property Axiom CPA. A combinatorial core of the iterated perfect set model}, 
version of October 2003, work in progress$^\star$.

\bibitem{CW}  K.~Ciesielski, J.~Wojciechowski, {\it Sums of connectivity
functions on $\R^n$}, Proc. London Math. Soc.
{\bf 76(2)} (1998), 406--426.
(Preprint$^\star$ available.)



\bibitem{Fed} H.~Federer, {\it Geometric measure theory}, 
Springer, New York 1969. 



\bibitem{Ga1} F.~Galvin, {\it Partition theorems for the real line}, 
Notices Amer. Math. Soc. {\bf 15} (1968), 660.

\bibitem{Ga2} F.~Galvin, {\it Errata to ``Partition theorems for the real line''}, 
Notices Amer. Math. Soc. {\bf 16} (1969), 1095.

\bibitem{Eng} R.~Engelking, {\it General Topology}, 
Polish Sci. Publ. PWN, Warszawa, 1977. 

\bibitem{Ka}  V.~Kanovei, {\it Non-Glimm--Effros equivalence relations 
at second projective level}, Fund. Math. {\bf 154} (1997), 1--35.



\bibitem{Ke}  A.~S.~Kechris, {\it Classical Descriptive Set Theory},
Springer-Verlag, Berlin 1995.



\bibitem{ScotB} R.~D.~Mauldin, {\it The Scottish Book}, 
Birkh\"auser, Boston 1981. 

\bibitem{Mi}  A.~W.~Miller, {\it Mapping a set of reals onto the reals}, 
J. Symbolic Logic {\bf 48} (1983), 575--584.



\bibitem{Mor}  M.~Morayne, {\it On continuity of symmetric restrictions 
of Borel functions}, 
Proc. Amer. Math. Soc. {\bf 98} (1985), 440--442.


\bibitem{Ol} A.~Olevski\v{\i},   
{\it Ulam Zahorski problem on free interpolation by smooth functions}, 
Trans. Amer. Math. Soc. {\bf 342} (1994), 713--727.

\bibitem{St}  J.~Stepr\={a}ns, {\it Sums of Darboux and  continuous functions},
Fund. Math. {\bf 146} (1995), 107--120.



\bibitem{St2} J.~Stepr\={a}ns, 
{\it Decomposing Euclidean space with
a small number of smooth sets},
Trans. Amer. Math. Soc. {\bf 351} (1999), 1461--1480.
(Preprint$^\star$ available.)

\bibitem{Ulam} S. Ulam, 
{\it A Collection of Mathematical Problems},
Interscience, New York, 1960. 

\bibitem{Wh} H. Whitney, 
{\it Analytic extensions of differentiable functions defined in closed sets},
Trans. Amer. Math. Soc. {\bf 36} (1934), 63--89.



\bibitem{Za} Z. Zahorski, 
{\it Sur l'ensamble des points singuli\'{e}re d'une fonction d'une variable
r\'{e}ele admettand des d\'{e}riv\'{e}es des tous orders},
Fund. Math. {\bf 34} (1947), 183--245.




\end{thebibliography}

\end{document}