\documentclass{article}\usepackage{amssymb} \font\script=eusm10 \let\Large\large \let\LARGE\large \let\Huge\large \def\eusm#1{\hbox{\script#1}} \textwidth 384pt %\textwidth 471pt \textheight = 48\baselineskip %\textheight = 50\baselineskip \title{{\bf Sets of range uniqueness for classes of continuous functions}} \author{ Maxim R.~Burke% \thanks{Research supported by NSERC. The author thanks the Department of Mathematics at the University of Wisconsin for its hospitality during the year 1996/97 while much of this research was carried out. } %\\ %{\footnotesize Dept of Math and Comp Sci.,} \\ %{\footnotesize Univ. of Prince Edward Island,} \\ %{\footnotesize Charlottetown, P.E.I., Canada C1A 4P3} \\ %{\footnotesize burke@upei.ca} %{\footnotesize Department of Mathematics and Computer Science,} \\ %{\footnotesize University of Prince Edward Island,} \\ %{\footnotesize Charlottetown, P.E.I., Canada C1A 4P3} \\ %{\footnotesize burke@upei.ca} \and Krzysztof Ciesielski% \thanks{This author was partially supported by NATO Collaborative Research Grant CRG~950347 and 1996/97 West Virginia University Senate Research Grant. \endgraf AMS classification numbers: Primary 26A15, 54C30; Secondary 04A30, 26A46, 30D20. \endgraf Key words and phrases: set of range uniqueness. \endgraf The authors would like to thank Lee Larson for his contributions to an early version of the paper. } %\\ %{\footnotesize Department of Mathematics,}\\ %{\footnotesize West Virginia University,} \\ %{\footnotesize Morgantown, WV 26506-6310} \\ %{\footnotesize KCies@wvnvms.wvnet.edu} %{\footnotesize %Department of Mathematics, West Virginia University,} \\ %{\footnotesize Morgantown, WV 26506-6310} \\ %{\footnotesize KCies@wvnvms.wvnet.edu} } \date{} \def\dom{{\rm dom}} \def\proof{\noindent {\sc Proof. }} \def\qed{\hfill$\Box$} \def\id{{\rm id}} \def\implies{\longrightarrow} \def\M{{\eusm M}} %% 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} \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{\map}{\mapsto} %arrow for functions \newcommand{\proves}{\vdash} %provability sign \newcommand{\A}{{\cal A}} %\newcommand{\M}{{\cal M}} \def\continuum{{\mathfrak c}} \def\c{{\mathfrak c}} \def\dd{{\mathfrak d}} \newcommand{\sq}{\subseteq} %\newcommand{\real}{{\bf R}} \newcommand{\complex}{{\mathbb C}} \newcommand{\real}{{\mathbb R}} \newcommand{\R}{{\real}} \newcommand{\rational}{{\mathbb Q}} \newcommand{\Q}{{\rational}} \newcommand{\integer}{{\mathbb Z}} \newcommand{\N}{{\mathbb N}} \newcommand{\cf}{{\rm cf}} \newcommand{\om}{\omega} \newcommand{\Z}{{\mathbb Z}} \newcommand{\NN}{{\eusm 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{\F}{{\eusm F}} \newcommand{\G}{{\cal G}} \newcommand{\C}{{\rm C}} \newcommand{\B}{{\eusm B}} \newcommand{\D}{{\cal D}} \newcommand{\E}{{\cal E}} \def\a{\alpha} \newcommand{\e}{{\emptyset}} \newcommand{\ep}{{\varepsilon}} \newcommand{\g}{{\gamma}} \renewcommand{\d}{{\delta}} \newcommand{\const}{{\rm Const}} \newcommand{\bor}{\mbox{${\cal B}or$}} \newcommand{\cm}{{{\rm C}_n}} \newcommand{\cc}{{{\rm C}_c}} \newcommand{\nd}{{\cal ND}} \def\poset{{\mathbb P}} \def\range{\mathop{\rm range}} \def\card{\mathop{\rm Card}} \def\cl{\mathop{\rm cl}} \def\inter{\mathop{\rm int}} \def\cof{\mathop{\rm cof}} \def\k{{\kappa}} \def\dom{{\rm dom}} \def\P{{\proof}} \def\qed{\hfill\vrule height6pt width6pt depth1pt%\medskip } \def\endproof{{\qed}} \def\AA{{\cal A}} \newcommand{\tr}{{\rm tr}} \newcommand{\sru}{{\rm sru}} \begin{document} \maketitle \begin{abstract} In \cite{DPR} it is proved that there are subsets $M$ of the complex plane such that for any two entire functions $f$ and $g$ if $f[M]=g[M]$ then $f=g$. In \cite{BD} it was shown that the continuum hypothesis (CH) implies the existence of a similar set $M\subset\R$ for the class $C_n(\real)$ of continuous nowhere constant functions from $\R$ to $\R$, while it follows from the results in \cite{BC} and \cite{CS} that the existence of such a set is not provable in ZFC. In this paper we will show that for several well-behaved subclasses of $C(\R)$, including the class $D^1$ of differentiable functions and the class $AC$ of absolutely continuous functions, a set $M$ with the above property can be constructed in ZFC. We will also prove the existence of a set $M\subset\real$ with the dual property that for any $f,g\in C_n(\R)$ if $f^{-1}[M]=g^{-1}[M]$ then $f=g$. \end{abstract} \section{Preliminaries} We use $\N$, $\R$, and $\complex$ to denote the set of natural numbers, the set of real numbers, and the set of complex numbers, respectively. We denote by $C(X)$ the set of all continuous real-valued functions on a topological space $X$ and by $C_n(X)$ the set of all nowhere constant members of $C(X)$, i.e., the functions which are not constant on any nonempty open set. ``Topological space'' means ``Tychonoff space''. $\const(X)$ will stand for the family of all constant functions from $X$ into~$\R$. We will write simply $\const$ if $X$ is clear from the context. The cardinality of a set $X$ will be denoted by $|X|$. The cardinality of $\R$, the continuum, will be denoted by~$\continuum$. For set-theoretic notation and terminology in general see \cite{BJ} or \cite{Ci}. The following basic concept was introduced in~\cite{BD}. \defi{defTrun}{If $X$ is a topological space then $g\in\C(X)$ is said to be a {\em truncation} of $f\in\C(X)$ if $g$ is constant on every connected component of $\{x\in X\colon f(x)\neq g(x)\}$.} Notice that every function is a truncation of every other function if $X$ is totally disconnected, making this concept trivial for such an $X$. We shall be interested in it only when $X$ is locally connected. (Mainly when $X=\R^n$.) Note also that when $X$ is locally connected, \begin{equation}\label{eq1} \mbox{if $f\in C(X)$, $g\in C_n(X)$, and $g$ is a truncation of $f$ then $f=g$.} \end{equation} Our interest in truncations derives from the following theorem which is a special case of Theorem~\ref{thm:main} below. \prop{prop:magic1}{{\rm (Berarducci, Dikranjan \cite[Thm.~8.1]{BD})} Let $X$ be a separable topological space. There exists a set $M \subseteq \real$ such that for every $g\in\C(X)$ and every countable-to-one $f\in\C(X)$ if $g[M]\subseteq f[M]$ then $g$ is a truncation of $f$. } % Note also that, by (\ref{eq1}), if $X$ is locally connected and $g\in\C_n(X)$ then the conclusion ``$g$ is a truncation of $f$'' in Proposition~\ref{prop:magic1} can be replaced by ``$f=g$.'' The main concepts studied in the first part of this paper are given by the following definition. \defi{SRU}{Let $X$ and $Y$ be sets, and let $\F$ be a family of functions from $X$ to $Y$. Let $M\sq X$. \begin{description} \item[(a)] $M$ is a {\em set of range uniqueness (SRU)} for $\F$ provided that for any $f,g\in\F$ if $f[M]=g[M]$ then $f=g$; \item[(b)] If $X$ is a topological space and $\F\sq\C(X)$, we will say $M$ is a {\em strong set of range uniqueness (strong SRU)} for $\F$ provided that for any open set $U\sq X$ and any $f,g\in\F$ if $f[M\cap U]\sq g[M]$ then $f\restr U$ is a truncation of $g\restr U$. \end{description} } We record for future reference the following results from \cite{DPR} and \cite{BD}. \prop{prop:DPR}{{\rm (Diamond, Pomerance, Rubel \cite{DPR})} \begin{description} \item[(a)] There are sequences $M=\{a_n\colon n\in\N\}$ of positive real numbers converging to zero (e.g., $a_n=1/n$ or $a_n=1/n!$) which are SRU's for the class $\cal A$ of analytic functions in the complex plane. \item[(b)] There exist sequences $M=\{a_n\colon n\in\N\}$ of positive real numbers converging to zero (e.g., $a_n=1/2^n$) which are not SRU's for $\cal A$. \end{description}} \prop{prop:BD}{{\rm (Berarducci, Dikranjan \cite[Thm.~8.5]{BD})} If the continuum hypothesis holds then for every separable Baire topological space $X$ there exists an SRU for $C_n(X)$.} The notion of a strong SRU was first considered in \cite{BC} in a more general setting. The definition from \cite{BC} differs slightly from the one given above, however they agree if $X$ is locally connected, Baire, and the functions in $\F$ are assumed to be nowhere constant. (The last two assumptions were imposed in~\cite{BC}.) In \cite{BC} the authors prove that under CH (and some weaker assumptions) the class of functions which have the property of Baire and are not constant on any nonmeager set (resp., the class of Lebesgue measurable functions which are not constant on any set of positive measure) has an SRU as long as we weaken the conclusion ``$f=g$'' in the definition of an SRU to ``$f=g$ except on a meager set'' (resp., ``$f=g$ a.e.''). It follows from the results in \cite{BC} and \cite{CS} that one cannot prove in ZFC the existence of a set with either of these two properties, nor can one prove in ZFC the existence of the set from Proposition~\ref{prop:BD} when $X=\R$. The terminology suggests that strong SRU's are SRU's and this is true when $X$ is both connected and locally connected. To see this note first that for any connected and locally connected space $X$ \begin{equation}\label{eq2}\!\!\!\!\!\!\! \mbox{if $f,g\in C(X)$ are truncations of each other and $f\neq g$ then $f,g$ are both constant.}\!\! \end{equation} Indeed, let $x_0\in W=\{x\in\R\colon f(x)\not=g(x)\}$ and let $U$ be the component of $x_0$ in $W$. Then $U$ is open in $X$ and $f$ and $g$ are both constant on $U$ (with different values). If $U=X$ we are done. But otherwise, by connectedness of $X$, there exists a boundary point $x\in X\setminus W$ of $U$ and so $f$ and $g$ assume different values at $x$, a contradiction. Note also that for any $\F\subseteq\const$ any nonempty $M\subset\R$ is simultaneously an SRU and a strong SRU for $\F$. Thus, we will concentrate on the case when $\F\not\subset\const$. \prop{StrongSRU}{Let $X$ be a connected locally connected topological space and let $\F\sq\C(X)$, $\F\not\subset\const$. Then any strong SRU for $\F$ is an SRU for $\F$.} \proof Let $M\subseteq X$ be a strong SRU for $\F$. We will show that $M$ is an SRU for $\F$. If $|\F|\leq 1$ then any set is an SRU for $\F$. So we can assume that $|\F|>1$. But then $M\neq\emptyset$ since otherwise for any $f,g\in\F$ we would have $f[M]=\emptyset=g[M]$ which, together with (\ref{eq2}), would imply that $\F\subseteq\const$. Next, take $f,g\in\F$ such that $f[M]=g[M]$. Then $f$ and $g$ are truncations of each other since $M$ is a strong SRU for $\F$. If $f=g$ we are done. But otherwise, by (\ref{eq2}), $f$ and $g$ are different constant functions, which is impossible, since $M\neq\emptyset$. \qed \section{Sets of range uniqueness for $C_n(X)$ when $X$ is Polish} We begin by analyzing the proof from \cite{CS} that in the model $\M$ constructed in that paper, there are no SRU's for $C_n(\R)$. The model $\M$ is constructed so that it satisfies the following statement for $X=2^\om$. \begin{description} \item{$\Phi(X)$:\quad} For every set $A\sq X$ of cardinality $\c$ there is a continuous function $f\colon X\to [0,1]$ %$\phantom{asdfa}$ such that $f[A]=[0,1]$. \end{description} It is then shown that $\Phi(2^\om)$ implies $\Phi(\R)$. This easily implies that there are no SRU's for $C_n(\R)$ of cardinality $\c$ (see \cite{BC}). That there are no SRU's of cardinality $<\c$ in $\M$ follows from the fact that sets of reals of cardinality $<\c$ are meager in $\M$ and from the theorem in \cite{BC} that an SRU for $C_n(\R)$ cannot be meager. Most of this argument will work with $\R$ replaced by an arbitrary perfect Polish space. Consider a perfect Polish space $X$. In $\cite{BC}$ it was shown that an SRU for $C_n(X)$ cannot be meager. Also, it is well known that if sets of size $<\c$ are meager in $\R$, then the same is true in $X$. Unfortunately, we do not know whether $\Phi(2^\om)$ implies $\Phi(X)$. We can however show that $\Phi(X)$ holds in $\M$ by using additional properties of $\M$ established in \cite{CS}, namely that in $\M$ we have $\c=\om_2$ and $\dd=\om_1$, where \[ \dd=\min\{|F|\colon F\sq\om^\om,\ \forall f\in\om^\om\,\exists g\in F\,\forall n<\om\,f(n)\leq g(n)\}. \] (The equation $\dd=\om_1$ is not stated explicitly in~\cite{CS}, but it follows from the fact that the forcing used to get $\M$ is $\om^\om$-bounding, and this follows easily from~\cite[Lemma 5.1]{CS}.) \prop{covering}{ Every Polish space can be covered by at most $\dd$ compact zero-dimensional sets.} \proof We first prove the statement for the Hilbert cube $[0,1]^\om$. Identify the irrational numbers in $[0,1]$ with $\om^\om$ and let $\{r_n\colon n<\om\}$ enumerate the rationals in $[0,1]$. For $f\in\om^\om$, write $K_f=\{g\in\om^\om\colon \textrm{ for all } n<\om$, $g(n)\leq f(n)\}\cup\{r_i\colon i\leq f(0)\}$. $K_f$ is a compact zero-dimensional subset of $[0,1]$. For $f\in\om^\om$, let $f_i$ ($i<\om$) be the functions defined by $f_i(n)=f(2^i(2n+1))$ and let $L_f$ be the compact zero-dimensional subset of $[0,1]^\om$ given by $L_f=\Pi_{i<\om}K_{f_i}$. Since $f\leq f'$ implies $L_{f}\sq L_{f'}$, it is clear that the sets $L_f$, as $f$ ranges over a dominating family, cover $[0,1]^\om$. For the general case, let $X$ be any Polish space. We may assume that $X$ is a subspace of the Hilbert cube. By considering the intersections of $X$ with each member of a family of $\dd$ compact zero-dimensional sets covering the Hilbert cube, we may assume that $X$ is zero-dimensional. By the Cantor-Bendixson theorem, we may assume that $X$ has no isolated points. Finally, by deleting a countable dense set, we may assume that $X$ has no nonvoid compact open sets. But now $X$ is homeomorphic to $\om^\om$ and the desired conclusion is standard (and easy). \endproof We now show that $\Phi(X)$ holds in $\M$ for any Polish space $X$. The following result is more than we need, but seems to be of independent interest. It applies not only to the model of \cite{CS}, but also to the models of \cite{Mi} and \cite{Co} as well. \cor{NoSRUPolish1} {Suppose $\dd<\cf(\c)$ and for every $A\sq 2^\omega$ of cardinality $\c$ there is a continuous function $f\colon 2^\om\to [0,1]$ such that $f[A]=[0,1]$. \begin{description} \item[(a)] Every separable metric space of cardinality $\c$ maps uniformly continuously onto $[0,1]$. \item[(b)] If $\c<\h_\om$, then every metric space of cardinality $\c$ maps uniformly continuously onto $[0,1]$. \end{description} } \rem{remA}{In \cite{Co} it is pointed out that part (a) holds for subspaces of the real line by results in \cite{Mi}. Also, if we drop the word ``uniformly,'' then both (a) and (b) are essentially shown in \cite{Mi}.} \proof If $\c<\h_\om$, the nonseparable case reduces to the separable case by reductions similar to those in \cite{Mi}. First, if $X$ has density $\geq\c$, then there is a set $D\sq X$ of cardinality $\geq\c$ such that the distances between distinct points of $D$ are bounded away from zero. Any map from $D$ onto $[0,1]$ is uniformly continuous and extends to a uniformly continuous map of $X$ onto $[0,1]$. Second, if $X$ has uncountable density $\k<\c$, then an argument in \cite[p.~575]{Mi} shows that $X$ has a subspace of cardinality $\c$ which has density $<\k$. (Note that since $\c<\h_\om$, $\k$ and $\c$ are regular.) Iterating this argument reduces us to the case where $X$ is separable. Hence (b) reduces to (a). For (a), note that the completion of $X$ is covered by at most $\dd$ compact zero-dimensional sets, and one of these, $K$ say, is such that $|K\cap X|=\c$. By removing countably many points from $K$, we may assume $K$ is homeomorphic to $2^\om$. The conclusion now follows easily from our assumption. \endproof \cor{NoSRUPolish2} {In the model constructed in \cite{CS}, there is no SRU for $C_n(X)$ for any perfect Polish space $X$. } Next consider the following easy proposition. \prop{propB}{Suppose $X$ and $Y$ are topological spaces and there is a continuous function $f\colon X\to Y$ with dense range such that $f^{-1}[N]$ is nowhere dense in $X$ for each nowhere dense $N\sq Y$. If $A$ is an SRU for $C_n(X)$, then $f[A]$ is an SRU for $C_n(Y)$.} \proof Let $g_1,g_2\colon Y\to\R$ be nowhere constant continuous functions such that $g_1[f[A]]=g_2[f[A]]$. Then $g_1\circ f$ and $g_2\circ f$ are nowhere constant and have the same image of $A$. Hence $g_1\circ f=g_2\circ f$. Since $f$ has dense range, $g_1=g_2$. \endproof Thus, in the model $\M$, for any space $X$ which can be mapped densely into $[0,1]$ so that the preimages of nowhere dense sets are nowhere dense, there is no SRU for $C_n(Y)$. We don't know precisely which spaces have this property. Here are a few simple observations. If the property is satisfied by one of the factors in a product $\Pi_\a X_\a$, then the product satisfies it as well. More generally, if there is a continuous open surjection from $X$ to $Y$, and $Y$ has the property, then so does $X$. In particular, if there is a continuous open surjection from $X$ to $[0,1]$, then $X$ has the property. Thus, for example, the Stone space of the regular open algebra of $[0,1]$ has the property. This idea gives a possible alternative proof of Corollary~\ref{NoSRUPolish2}. \pr{probC}{If $X$ is a perfect Polish space, is there a continuous function $f\colon X\to[0,1]$ with dense range and such that $f^{-1}[N]$ is nowhere dense for each nowhere dense $N\sq[0,1]$?} \noindent Added in proof: The answer is yes for any perfect metric space $X$. See M.R. Burke, {\it Continuous functions which take a somewhere dense set of values on every open set}, to appear in Topology Appl. We have very few results relating the existence of an SRU for $C_n(X)$ to the existence of an SRU for $C_n(Y)$ for different spaces $X$ and $Y$. For example we don't know the answer to the following question. \pr{probD}{If there is an SRU for $C_n([0,1])$, is there an SRU for $C_n(2^\om)$?} \section{Sets of range uniqueness for special classes of continuous functions} The following theorem is a technical tool used to prove some of the results in this section. \thm{thm:main}{Let $X$ be a separable topological space with a fixed base $\B$ of cardinality $\leq\continuum$ and let $\NN$ be an ideal of subsets of $\R$ such that $|V\setminus N|=\continuum$ for every $N\in\NN$ and nonempty open interval $V\subset \R$. Then there exists a set $M\subset X$ with the following property. If $f,g\in\C(X)$, \begin{description} \item{\rm (a)} $\{y\in\R\colon f^{-1}(y)$ is uncountable$\}\in\NN$, \item{\rm (b)} $N\in\NN$ is an analytic set, $U\in\B$, and \item{\rm (c)} $g[M\cap U]\setminus N\sq f[M]$ \end{description} then $g\restr U$ is a truncation of $f\restr U$. } \rem{remF}{If $X$ is locally connected, then the conclusion holds for all open sets $U$, regardless of whether they are in the fixed base $\B$. To see this, note that if $W$ is a component of $\{x\in U\colon f(x)\not=g(x)\}$, then $W$ is covered by the family $S$ of (open) components $W'$ of the sets $B\in\B$ such that $B\sq W$. If we fix $W'_0\in S$, then the union of the $W'\in S$ which are joined to $W'_0$ by a chain $W'_0,W'_1,\dots,W'_n=W'$ such that $W'_i\cap W'_{i+1}\not=\e$ for all $i=0,1,\dots,n-1$ is an open connected subset of $W$ and hence equals $W$. Since $g$ is constant on each $W'$, it is clear that $g$ is constant on $W$. } \proof Let $\{\la f_\alpha,g_\alpha,N_\a,U_\alpha\ra\colon \alpha<\continuum\}$ be an enumeration of all four-tuples $\la f,g,N,U\ra$ such that $f,g\in\C(X)$, the properties (a) and (b) hold, and $g\restr U$ is not a truncation of $f\restr U$. Let $W_\a\neq\emptyset$ be a fixed component of $\{x\in U_\a\colon f_\a(x)\not=g_\a(x)\}$ on which $g$ is not constant. We will construct, by induction on $\alpha<\continuum$, a set $M=\{m_\alpha\colon\alpha<\continuum\}$ such that $m_\alpha\in W_\alpha$ and $g_\alpha(m_\alpha)\not\in f_\alpha[M]\cup N_\a$ for every $\alpha<\continuum$. This will finish the proof. We choose $m_\alpha$ so that the following inductive assumptions are satisfied. \begin{description} \item{(I$_\alpha$)} $m_\alpha\in W_\alpha$, $g_\a(m_\a)\notin N_\a$. \end{description} Note that $m_\alpha\in W_\alpha\subseteq U_\alpha$ implies, in particular, that $g_\a(m_\a)\neq f_\a(m_\a)$. \begin{description} \item{(II$_\alpha$)} $g_\alpha(m_\alpha)\notin\{f_\alpha(m_\gamma)\colon\gamma<\alpha\}$. \end{description} Finally we need $g_\alpha(m_\alpha)\notin\{f_\alpha(m_\gamma)\colon\gamma>\alpha\}$, i.e., $f_\alpha(m_\gamma)\neq g_\alpha(m_\alpha)$ for every $\alpha<\gamma$. By interchanging $\alpha$ and $\gamma$ in the last condition we obtain $f_\gamma(m_\alpha)\neq g_\gamma(m_\gamma)$ for every $\gamma<\alpha$. So, it is enough to choose \begin{description} \item{(III$_\alpha$)} $g_\alpha(m_\alpha)\notin g_\alpha\left[\bigcup_{\gamma<\alpha} f^{-1}_\gamma(g_\gamma(m_\gamma))\right]$. \end{description} To make such a choice possible, we will also require that \begin{description} \item{($\star_\alpha$)} $f^{-1}_\alpha(g_\alpha(m_\alpha))$ is countable. \end{description} So, assume that for some $\alpha<\continuum$ the sequence $\la m_\beta\colon\beta<\alpha\ra$ satisfying the above conditions is already constructed. Note that $g_\alpha[W_\alpha]$ is a non-trivial interval since $g_\alpha$ is not constant on $W_\a$ and $W_\a$ is connected. Let $S_\a=\{y\in\R\colon f_\a^{-1}(y)$ is uncountable$\}$. By conditions (a), (b), and our assumption on $\NN$ we have that $g_\alpha[W_\alpha]\setminus (S_\alpha\cup N_\a)$ has cardinality continuum. But the set $g_\alpha\left[\bigcup_{\gamma<\alpha} f^{-1}_\gamma(g_\gamma(m_\gamma))\right]$ has cardinality less than $\continuum$ by the inductive assumption ($\star_\gamma$) for $\gamma<\alpha$. Therefore, we can pick \[ y_\alpha\in g_\alpha[W_\alpha]\setminus \left(S_\alpha\cup N_\a\cup\{f_\alpha(m_\gamma)\colon\gamma<\alpha\}\cup g_\alpha\left[\bigcup_{\gamma<\alpha} f^{-1}_\gamma(g_\gamma(m_\gamma))\right] \right). \] Choose \[ m_\alpha\in W_\a\cap g^{-1}_\alpha(y_\alpha). \] It is easy to see that it satisfies (I$_\alpha$), (II$_\alpha$), (III$_\alpha$) and ($\star_\alpha$). This finishes the proof. \qed \cor{diffSRU}{There is a meager strong SRU for the family \[ (N)= \{f\in\C(\R)\colon f[E] \mbox{ has Lebesgue measure zero for each set $E$ of Lebesgue measure zero}\}. \] } \proof Apply Theorem~\ref{thm:main} with $X=\R$, $\B$ being the family of all open sets in $\R$, and $\NN$ being the ideal of Lebesgue measure zero sets. Let $M$ be the set given by the theorem and let $H\sq\R$ be a meager Borel set whose complement $\real\setminus H$ has Lebesgue measure zero. Then $M\cap H$ is the desired strong SRU. Indeed suppose that $f,g\in\F$, $U\sq \R$ is open, and $g[M\cap H\cap U]\sq f[M\cap H]$. Assumption (a) of the theorem is satisfied \cite{B} (see also~\cite{F}) and in assumption (b) we take $N=g[\R\setminus H]$. It is easily seen that (c) now holds and the theorem gives the desired conclusion. \qed \cor{corMain}{There exists a meager strong SRU set $M$ for the class $D^1\cup AC$. } \proof This follows from Corollary~\ref{diffSRU} and the fact that $D^1\cup AC\subset(N)$. (See \cite{F} for information on the relationship of the family $(N)$ to $D^1$, $AC$ and other familiar families of functions.) \qed Corollary~\ref{corMain} implies in particular that that there exists a ZFC example of an SRU set for the family $C^1$ of continuously differentiable functions. This special case is due partly to Lee Larson. \rem{rem1}{In the spirit of \cite{BC}, Corollary~\ref{diffSRU} holds for the class of Lebesgue measurable functions which map sets of measure zero to sets of measure zero and map sets of positive measure to sets of positive measure. (See \cite{BC} for the definition of strong SRU in this context.) The proof is similar to the proofs of Theorem~\ref{thm:main} and Corollary~\ref{diffSRU} with \cite[Theorem 4.1]{FM} taking the place of the result of Banach used in the proof of Corollary~\ref{diffSRU}. } \pr{prob0}{Is there a Borel SRU for the differentiable (or $\C^\infty$) functions?} \pr{prob1}{Is there an SRU for the class of differentiable (or $\C^\infty$) functions on $\real^n$ when $n>1$?} \noindent Added in proof: The answer is yes. See M.R. Burke, {\it A note on sets of range uniqueness for differentiable functions}, unpublished note, Nov. 24, 1998. The following observation is essentially contained in~\cite{DPR}. We reproduce it here in a form suitable to our purposes. \prop{SRUnotCount}{Let $\F\subset\C(\R)$ be a family of functions that contains all functions from $\R$ onto $\R$ which are the restrictions of entire functions of a complex variable and which have a positive derivative at every point of $\R$. If $M$ is an SRU for $\F$ then $M$ cannot be countable and dense.} \proof Suppose $M$ were a countable dense SRU for such a family of functions. By the main result of \cite{NT} there is a function $f\in\F$ such that $f[M]=\Q$. Then $f[M]=(-f)[M]$ and hence $f$ is not an SRU, contradiction. \qed \cor{corCInf}{If $\F\subset\C(\R)$ contains the family $C^\infty$ of infinitely differentiable functions then an SRU for $\F$ cannot be countable.} \proof It is easy to see that an SRU for any family containing $C^\infty$ functions must be dense. (See e.g.~\cite{BC}.) \qed In Theorem~\ref{thm:main}, we could have taken $C(X)$ to be the continuous complex-valued functions on $X$. The theorem then provides us with various SRU's and strong SRU's for the class $\cal A$ of analytic functions in the complex plane. (The fibers of a nonconstant analytic function have finite intersection with any compact set, so the theorem easily applies.) For example, there is a Bernstein subset of $\complex$ (i.e., a set with the property that both it and its complement meet every uncountable compact set) which is a strong SRU for $\cal A$. And every uncountable compact subset of the plane contains an SRU for $\cal A$. We finish this section by strengthening the result from \cite{DPR} that $M=\{1/n!\colon n\in\N\}$ is an SRU for $\cal A$. $M$ cannot be a strong SRU for $\cal A$ since it isn't dense, but it has a similar property: $f[M]\sq g[M]$ implies either $f$ is constant or $f=g$ for entire functions $f$ and $g$. Not every SRU for $\cal A$ has this stronger property since, by Proposition~\ref{prop:DPR}, the set $M'=\{1/n\colon n\in\N\}$ is an SRU for $\cal A$, while the functions $f(z)=z^2$ and $g(z)=z$ show that it fails to have the stronger property. \prop{strSRUforA}{Let $M=\{1/n!\colon n\in\N\}$. Then for every $f,g\in\A$ if $f[M]\subseteq g[M]$, then either $f$ is constant or $f=g$.} \proof Assume f is not constant. As in the proof of \cite[theorem 2]{DPR}, we may assume $f(0)=g(0)=0$. (They use $f[M]=g[M]$ but in a context where $f[M]\sq g[M]$ is clearly enough.) We have $f(z) \sim c z^\ell$ and $g(z) \sim d z^m$ as $z\to 0$ for some $c\not=0\not=d$. Say $f(1/n!)=g(1/a(n)!)$ for all $n$. From \cite[Lemma 1]{DPR} it follows easily that $\{a(n)\}$ is eventually strictly increasing. In particular, $a(n)\to\infty$ as $n\to\infty$. We have, as $n\to\infty$, \[ \frac{c}{(n!)^\ell}\sim\frac{d}{(a(n)!)^m} \] or, $$ u(n)=\frac{(n!)^\ell }{(a(n)!)^m}\sim\frac{c}{d}\neq 0. \leqno{(*)} $$ We must have $v(n)=u(n+1)/u(n) \sim 1$ and hence $w(n)=v(n)/v(n-1)\sim 1$. Calculating gives \[ w(n)= \left(1+{1\over n}\right)^\ell \frac{[(a(n-1)+1)\cdots a(n)]^m}{[(a(n)+1)\cdots a(n+1)]^m} \sim\frac{[(a(n-1)+1)\cdots a(n)]^m}{[(a(n)+1)\cdots a(n+1)]^m} \sim 1 \] and hence $$ \frac{(a(n-1)+1)\cdots a(n)}{(a(n)+1)\cdots a(n+1)} \sim 1.\leqno{(**)} $$ Notice that the numbers $a(n+1)-a(n)$ eventually stabilize to say $k$. Indeed, otherwise there would exist infinitely many numbers $n$ for which the number of factors in the denominator is greater than the number of factors in the numerator. But since the numbers in the denominator are larger, we would obtain that for infinitely many $n$ \[ \frac{(a(n-1)+1)\cdots a(n)}{(a(n)+1)\cdots a(n+1)}\leq \frac{1}{a(n+1)} \] which contradicts ($**$). So we have $a(n_0+i)=a(n_0)+ki$ for some $n_0$ and all $i$. Thus \[ v(n_0+i-1)= \frac{(n_0+i)^\ell}{[(a(n_0)+k(i-1)+1)\cdots(a(n_0)+ki)]^m} \sim 1. \] The left-hand side is $\sim i^\ell / (ki)^{km}$, and this is $\sim 1$ if and only if $\ell=km$ and $k=1$. We now have $\ell=m$ and thus $a(n)=a(n_0+(n-n_0))=a(n_0)+n-n_0=n+k_0$ for all large enough $n$, where $k_0=a(n_0)-n_0$. It follows from $(*)$ that $\lim [n!/(n+k_0)!] = (c/d)^{1/m}$. Since the right-hand side is nonzero, we must have $k_0=0$ which gives $a(n)=n$ for all large enough $n$. Thus $f$ and $g$ agree on a tail of the sequence $\{1/n!\}$ and hence are equal. \endproof \section{Sets of preimage uniqueness} Now consider the following notion ``dual'' to that of SRU. \defi{defSPU}{A set $M\subseteq\real$ is a {\em set of preimage uniqueness (SPU)} for the family $\F$ of functions from $X$ into $\real$ if $f,g\in\F$ and $g^{-1}[M]=f^{-1}[M]$ then $f=g$.} The existence of an SPU for many classes follows from the next theorem. It gives a set with the stronger property obtained by replacing ``$g^{-1}[M]=f^{-1}[M]$'' in the definition of SPU by ``$g^{-1}[M]\sq f^{-1}[M]$''. \thm{anti}{There is a set $M\sq\R$ such that for any Polish space $X$ the following holds. For any Borel set $Z\sq \R$ and any $f,g\in C_n(X)$ if $g^{-1}(Z)$ is meager and $g^{-1}[M\setminus Z]\subseteq f^{-1}[M]$ then $f=g$. In particular, $M$ is an SPU for $C_n(X)$ for any Polish space $X$. } \proof Let $\{\la X_\a,f_\alpha,g_\alpha,Z_\a\ra\colon \alpha<\continuum\}$ be an enumeration of all quadruples $\la X,f,g,Z\ra$ such that $X$ is a Polish subspace of the Hilbert cube, $f,g\in C_n(X)$, $f\neq g$, and $Z$ is a Borel subset of $\R$ with $g^{-1}(Z)$ being meager. We will construct, by induction on $\alpha<\continuum$, a set $M=\{m_\alpha\colon\alpha<\continuum\}$ such that $m_\a\not\in Z_\a$ and $g^{-1}_\alpha(m_\alpha)\not\subset f^{-1}_\alpha[M]$ for every $\alpha<\continuum$. This will finish the proof. We will define $m_\alpha=g_\alpha(x_\alpha)$ for appropriately chosen $x_\alpha$, that is such that $x_\alpha\notin f^{-1}_\alpha(M)$. To obtain this we will choose $x_\alpha$ such that the following inductive conditions are satisfied. \medskip $x_\alpha\notin f^{-1}_\alpha(m_\alpha)= f^{-1}_\alpha(g_\alpha(x_\alpha))$, i.e., such that \begin{description} \item{(I$_\alpha$)} $x_\alpha\in U_\alpha$, where $U_\alpha=\{x\in\real\colon f_\alpha(x)\neq g_\alpha(x)\}$. \end{description} $x_\alpha\notin\bigcup\{f^{-1}_\alpha(m_\gamma)\colon\gamma<\alpha\}$, i.e., such that \begin{description} \item{(II$_\alpha$)} $f_\alpha(x_\alpha)\notin M_\alpha=\{m_\gamma\colon\gamma<\alpha\}$. \end{description} $x_\alpha\notin\bigcup\{f^{-1}_\alpha(m_\gamma)\colon\gamma>\alpha\}$, i.e., such that $f_\alpha(x_\alpha)\neq m_\gamma=g_\gamma(x_\gamma)$ for every $\alpha<\gamma$. By interchanging $\alpha$ and $\gamma$ in the last condition we obtain $g_\alpha(x_\alpha)\neq f_\gamma(x_\gamma)$ for every $\gamma<\alpha$. So, it is enough to choose $x_\alpha$ such that \begin{description} \item{(III$_\alpha$)} $g_\alpha(x_\alpha)\notin H_\alpha\cup Z_\a$ where $H_\a=\{f_\gamma(x_\gamma)\colon\gamma<\alpha\}$. \end{description} So assume that for some $\alpha<\continuum$ the sequence $\la x_\beta\colon\beta<\alpha\ra$ satisfying the above conditions is already constructed. Let $E=U_\a\setminus g_\a^{-1}(Z_\a)$ and let $F=\la f_\a,g_\a\ra\colon X\to\R^2$. Then $F$ is continuous and $P=F[E]$ is analytic. We will be done if we show that \[ S= P\setminus[(M_\alpha\times\real)\cup(\real\times H_\alpha)]\neq\emptyset \] since any $x_\alpha\in E\cap F^{-1}[S]$ will satisfy the inductive requirements. If $S$ were empty, then $P$ would be covered by less than $\continuum$ many horizontal and vertical lines, and hence would be covered by countably many such lines \cite{vEKM}. But then it follows from the definition of $P$ and the fact that $f_\alpha$ and $g_\alpha$ are nowhere constant that $E$, and hence $U_\a$, is covered by countably many nowhere dense sets, contradiction. \qed The following is an analog of Proposition~\ref{SRUnotCount}. \prop{SPUnotCount}{Let $\F\subset\C(\R)$ be a family of functions which contains all functions from $\R$ onto $\R$ which are the restrictions of the entire functions of a complex variable and which have a positive derivative at every point of $\R$. If $M$ is an SPU for $\F$ then $M$ cannot be countable and dense.} \proof Suppose $M$ were a countable dense SPU for such a family of functions. Then, by the main result of \cite{NT}, there is a strictly increasing function $f\in\F$ such that $f[\Q]=M$. Then, for $g(x)=f(x-1)$ we have $g\in\F$, $g[\Q]=M$, and $f\neq g$, contradiction. \qed \cor{corCInfSPU}{If $\F\subset\C(\R)$ contains the family $C^\infty$ then an SPU for $\F$ cannot be countable.} \proof It is easy to see that an SPU for any family containing $C^\infty$ functions must be dense. \qed \pr{prob3}{Can an SPU for $C^\infty$, or differentiable functions be meager?} We even do not know even whether an SPU for the analytic functions can be countable, though the answer is likely affirmative. \begin{thebibliography}{Ba}%{Baren} \bibitem%[Ba] {B} S.~Banach, {\em Sur une classe de fonctions continues}, Fund. Math. {\bf 8} (1926), 166--172. \bibitem%[BJ] {BJ} T.~Bartoszy\'nski, H.~Judah, {\it Set Theory}, A.K.~Peters, Wellesley MA, 1995. \bibitem%[BD] {BD} A.~Berarducci and D.~Dikranjan, {\it Uniformly approachable functions and $UA$ spaces}, Rend. Ist. Matematico Univ. di Trieste {\bf 25} (1993), 23--56. \bibitem%[Br] {Br} A.~M.~Bruckner, {\it Differentiation of real functions}, CMR Series vol. 5, Amer. Math. Soc., 1994. \bibitem%[BC] {BC} M.~Burke and K.~Ciesielski, {\it Sets on which measurable functions are determined by their range}, Canad. J. Math. {\bf 49} (1997), no/ 6, 1089--1116. (Preprint$^\star$ available.% \footnote{Preprints marked by $^\star$ are available in electronic form. They can be accessed from the {\it Set Theoretic Analysis Web Page:} http://www.math.wvu.edu/homepages/kcies/STA/STA.html}) \bibitem%[Ci] {Ci} K.~Ciesielski, {\sl Set Theory for the Working Mathematician}, London Math. Soc. Student Texts {\bf 39}, Cambridge Univ. Press 1997. \bibitem%[CS] {CS} K.~Ciesielski and S.~Shelah, {\it Model with no magic set}, %chKC preprint$^\star$. J. Symbolic Logic, to appear. (Preprint$^\star$ available.) \bibitem%[Co] {Co} P.~Corazza, {\em The generalized Borel conjecture and strongly proper orders}, Trans. Amer. Math. Soc. {\bf 316} (1989), 115--140. \bibitem%[DPR] {DPR} H.~G.~Diamond, C.~Pomerance, L.~Rubel, {\em Sets on which an entire function is determined by its range}, Math Z. {\bf 176} (1981), 383--398. \bibitem%[vEKM] {vEKM} F.~van~Engelen, K.~Kunen, and A.~W.~Miller, {\em Two remarks about analytic sets}, in Set theory and its applications, J.~Steprans and S.~Watson eds., Lecture Notes in Math.\ 1401, Springer-Verlag, 1989, 68--72. \bibitem%[FM] {FM} H.~Federer, A.~P.~Morse, {\em Some properties of measurable functions}, Bull.\ Amer.\ Math.\ Soc. {\bf 49} (1943), 270--277. \bibitem%[Fo] {F} J.~Foran, {\em Continuous functions: a survey}, Real Anal. Exchange {\bf 2} (1977), 85--103. \bibitem%[Mi] {Mi} A.W. Miller, {\em Mapping a set of reals onto the reals}, J. Symbolic Logic {\bf 48} (1983), 575--584. \bibitem%[NT] {NT} J.~W.~Nienhuys, J.~G.~F.~Thiemann, {\em On the existence of entire functions mapping countable dense sets onto each other}, Indag.\ Math. {\bf 38} (1976), 331--334. \bibitem%[S] {Saks} S.~Saks, {\it Theory of the Integral}, Warszawa-Lw\'ow 1937. \end{thebibliography} \noindent{\footnotesize Department of Mathematics and Computer Science, University of Prince Edward Island, Charlottetown, P.E.I., Canada C1A 4P3 (burke@upei.ca)} \noindent{\footnotesize Department of Mathematics, %Dept of Math, West Virginia Univ., Morgantown, WV 26506-6310 (KCies@wvnvms.wvnet.edu)} \end{document}