Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-22T17:42:40.929Z Has data issue: false hasContentIssue false

Sparse analytic systems

Published online by Cambridge University Press:  04 July 2023

Brent Cody
Affiliation:
Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, 1015 Floyd Avenue, Richmond, VA 23284, USA; E-mail: [email protected]
Sean Cox
Affiliation:
Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, 1015 Floyd Avenue, Richmond, VA 23284, USA; E-mail: [email protected]
Kayla Lee
Affiliation:
Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, 1015 Floyd Avenue, Richmond, VA 23284, USA; E-mail: [email protected]

Abstract

Erdős [7] proved that the Continuum Hypothesis (CH) is equivalent to the existence of an uncountable family $\mathcal {F}$ of (real or complex) analytic functions, such that $\big \{ f(x) \ : \ f \in \mathcal {F} \big \}$ is countable for every x. We strengthen Erdős’ result by proving that CH is equivalent to the existence of what we call sparse analytic systems of functions. We use such systems to construct, assuming CH, an equivalence relation $\sim $ on $\mathbb {R}$ such that any ‘analytic-anonymous’ attempt to predict the map $x \mapsto [x]_\sim $ must fail almost everywhere. This provides a consistently negative answer to a question of Bajpai-Velleman [2].

Type
Foundations
Creative Commons
Creative Common License - CCCreative Common License - BYCreative Common License - NCCreative Common License - ND
This is an Open Access article, distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives licence (https://creativecommons.org/licenses/by-nc-nd/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is unaltered and is properly cited. The written permission of Cambridge University Press must be obtained for commercial re-use or in order to create a derivative work.
Copyright
© The Author(s), 2023. Published by Cambridge University Press

1 Introduction

In the early 1960s, John Wetzel posed the following problem.

Wetzel’s Problem: If $\mathcal {F}$ is a family of analytic functions (on some common domain) such that $\{ f(x) \ : \ f \in \mathcal {F} \}$ is countable for every x, must $\mathcal {F}$ be a countable family?

A few years later, Erdős proved that an affirmative answer to Wetzel’s Problem is equivalent to the negation of Cantor’s Continuum Hypothesis (CH). Combined with Paul Cohen’s proof of the independence of CH, this showed that Wetzel’s Problem is independent of the standard axioms of mathematics (ZFC). Upon learning of Erdős’ theorem, Wetzel remarked to his dissertation advisor (Halsey Royden) that ‘…once again a natural analysis question has grown horns!’ This quote, and other interesting history surrounding Wetzel’s Problem, appears in Garcia-Shoemaker [Reference Garcia and Shoemaker10]. Erdős’ proof even made it into Aigner-Ziegler’s ‘Proofs from the Book’ ([Reference Aigner and Ziegler1]). It will be more convenient for us to state and refer to Erdős’ equivalence in the negated form.

Theorem 1 (Erdős [Reference Erdős7])

The following are equivalent:

  1. (1) CH;

  2. (2) There exists an uncountable family $\mathcal {F}$ of analytic functions on some fixed open domain D of either $\mathbb {R}$ or $\mathbb {C}$ , such that for every $x \in D$ ,

    $$\begin{align*}\big\{ f(x) \ : \ f \in \mathcal{F} \big\} \end{align*}$$
    is countable.

Motivated by connections to work of Hardin-Taylor ([Reference Hardin and Taylor11], [Reference Hardin and Taylor12]) and Bajpai-Velleman [Reference Bajpai and Velleman2] described below, we strengthen Theorem 1 as follows. If $P \in \mathbb {R}^2$ , we denote the first coordinate of P by $x_P$ and the second coordinate by $y_P$ . Define a sparse (real) analytic system to mean a collection

$$\begin{align*}\big\{ f_P \ : \ P \in \mathbb{R}^2 \big\} \end{align*}$$

such that:

  1. (1) for all $P \in \mathbb {R}^2$ , $f_P$ is an increasing, analytic bijection from $\mathbb {R} \to \mathbb {R}$ that passes through the point P; and

  2. (2) For all $z \in \mathbb {R}$ , the sets

    $$\begin{align*}\big\{ f_P(z) \ : \ P \in \mathbb{R}^2 \text{ and } z \ne x_P \big\} \end{align*}$$
    and
    $$\begin{align*}\big\{ f^{-1}_P(z) \ : \ P \in \mathbb{R}^2 \text{ and } z \ne y_P \big\} \end{align*}$$
    are both countable.

We prove the following strengthening of Erdős’ Theorem 1.

Theorem 2. The following are equivalent:

  1. (1) CH

  2. (2) There exists a sparse real analytic system.

We use Theorem 2 to answer a question of Bajpai and Velleman, assuming CH. Given a nonempty set S, let $\boldsymbol {{}^{\mathbb {R}} S}$ denote the collection of total functions from $\mathbb {R}$ to S, and let $\boldsymbol {{}^{\underset {\smile }{\mathbb {R}}} S}$ denote the collection of all S-valued functions f such that $\text {dom}(f)=(-\infty ,t_f)$ for some $t_f \in \mathbb {R}$ . An $\boldsymbol {S}$ -predictor will refer to any function $\mathcal {P}$ with domain and codomain as follows:

(1) $$ \begin{align} \mathcal{P}: {}^{\underset{\smile}{\mathbb{R}}} S \to S. \end{align} $$

An S-predictor $\mathcal {P}$ will be called good if for all $F \in {}^{\mathbb {R}} S$ , the set

$$\begin{align*}\Big\{ t \in \mathbb{R} \ : \ F(t) = \mathcal{P} \big( F \restriction (-\infty,t) \big) \Big\} \end{align*}$$

has full measure in $\mathbb {R}$ . So $\mathcal {P}$ is good if for any total $F:\mathbb {R} \to S$ , $\mathcal {P}$ ‘almost always’ correctly predicts $F(t)$ based only on $F \restriction (-\infty ,t)$ .Footnote 1 Hardin-Taylor [Reference Hardin and Taylor11] proved that for any set S, there exists a good S-predictor, and in [Reference Hardin and Taylor12], they raised the question of whether these good predictors could also be arranged to be ‘ $\Gamma $ -anonymous’ with respect to certain classes $\Gamma \subseteq \text {Homeo}^+(\mathbb {R})$ ;Footnote 2 an S-predictor $\mathcal {P}$ is $\Gamma $ -anonymous if for every $\varphi \in \Gamma $ and every $f \in {}^{\underset {\smile }{\mathbb {R}}} S$ ,

$$\begin{align*}\mathcal{P}\big( f \big) = \mathcal{P} \big( f \circ \varphi \big), \end{align*}$$

where $f \circ \varphi $ is the member of ${}^{\underset {\smile }{\mathbb {R}}} S$ whose domain is understood to be $\big (-\infty , \varphi ^{-1}(t_f) \big )$ . Bajpai and Velleman [Reference Bajpai and Velleman2] gave a positive and a negative result:

  • For every set S, there exists a good S-predictor that is anonymous with respect to the class of affine functions on the reals. This strengthened a previous theorem of Hardin-Taylor [Reference Hardin and Taylor12], who had gotten the same result for the smaller class of affine functions of slope 1 (i.e, shifts).

  • There is an equivalence relation $\sim $ on $\mathbb {R}$ such that, letting $S:=\mathbb {R}/\sim $ , there is no good S-predictor that is anonymous with respect to the class of increasing $C^\infty $ bijections on $\mathbb {R}$ .

They asked about classes intermediate between the affine functions and the $C^\infty $ functions.

Question 3 (Bajpai-Velleman [Reference Bajpai and Velleman2], page 788)

Does there exist (for every set S) a good S-predictor that is anonymous with respect to the analytic members of $\text {Homeo}^+(\mathbb {R})$ ?

We use Theorem 2, together with an argument from Bajpai-Velleman [Reference Bajpai and Velleman2], to prove:

Theorem 4. Assuming CH, the answer to Question 3 is negative.

Section 2 provides an interpolation theorem that will be used in the proof of Theorem 2, Section 3 proves Theorem 2, Section 4 proves Theorem 4, and Section 5 has concluding remarks and open questions.

2 An interpolation theorem

A key part of the proof of Theorem 2 is the (ZFC) Theorem 5 below. One of the referees pointed out that Theorem 5 follows from known results; in particular, it follows from the much more powerful Theorem 3.2 of Burke [Reference Burke4] or, with modifications in the proofs, either Theorem 2 of Barth-Schneider [Reference Barth and Schneider3] or Corollary 1.9 of Burke [Reference Burke5]. Since deriving Theorem 5 from those more powerful theorems is not trivial, we choose to present our original direct proof of Theorem 5.

Recall that Cantor proved that any two countable dense subsets of $\mathbb {R}$ are order-isomorphic and that this order-isomorphism easily extends uniquely to a homeomorphism of $\mathbb {R}$ . Franklin [Reference Franklin9] considered the question of how nice this homeomorphism could be arranged to be, and showed that if D and E are countable dense subsets of $\mathbb {R}$ , then there is an order-isomorphism of D with E that extends to a real analytic function. A series of papers improved this result, culminating in Barth-Schneider [Reference Barth and Schneider3], who proved that there is an order-isomorphism of D with E that extends to an entire function $f: \mathbb {C} \to \mathbb {C}$ , answering (one interpretation of) Question 24 of Erdős [Reference Erdős8].Footnote 3 Subsequent work of Burke, mentioned above, further strengthened those results. The variant we will need for the proof of Theorem 2 follows.

Theorem 5. Suppose $\mathcal {D}$ is a partition of $\mathbb {R}$ into dense subsets of $\mathbb {R}$ ; for each $z \in \mathbb {R}$ , let $D_z$ denote the unique $D \in \mathcal {D}$ such that $z \in D$ .

Then for any $P=(x_P,y_P) \in \mathbb {R}^2$ and any countable set W of reals, there is an entire function $f: \mathbb {C} \to \mathbb {C}$ such that:

  1. (1) $f \restriction \mathbb {R}$ is real-valued (hence analytic, since $f:\mathbb {C} \to \mathbb {C}$ is entire);

  2. (2) $f \restriction \mathbb {R}$ is a bijection with strictly positive derivative;

  3. (3) $f(x_P)=y_P$ ; and

  4. (4) for each $w \in W$ ,

    1. (a) if $w \ne x_P$ , then $f(w) \in D_w$ ;

    2. (b) if $w \ne y_P$ , then $f^{-1}(w) \in D_w$ .

Let us give a brief outline of the following proof of Theorem 5, which is inspired by the proof of Nienhuys-Thiemann [Reference Nienhuys and Thiemann14]. We will inductively define a sequence of functions $\langle f_n : n\in \mathbb {N}\rangle $ whose limit will be the desired function f. Each function $f_n$ will satisfy a version of Theorem 5(4) for finitely many points in W. When we define the next function $f_{n+1}$ , we will want it to be equal to $f_n$ on these finitely many points in W that have already been taken care of, and we will want $f_{n+1}$ to satisfy Theorem 5(4a) or Theorem 5(4b), depending on whether n is even or odd, for an additional point in W. We will write $A_n$ to denote the set of finitely many points of W that have already been taken care of at stage n with regard to Theorem 5(4a), and we will write $B_n$ to denote the set of finitely many points of W that have been taken care of in regard to Theorem 5(4b).

Suppose $\mathcal {D}$ is a partition of $\mathbb {R}$ into dense sets, W is a countable set of real numbers, and $P=(x_P,y_P)$ is a point in $\mathbb {R}^2$ . Fix a 1-1 enumeration $\{ w_n \ : \ n \in \mathbb {N} \}$ of W, and for each n, let $D_n$ be the unique member of $\mathcal {D}$ containing $w_n$ . Since $\mathcal {D}$ is a partition, we have

(*) $$ \begin{align} \forall k,n \in \mathbb{N} \ \ \big( w_k \in D_n \ \iff \ D_k=D_n \ \iff \ w_n \in D_k \big). \end{align} $$

Suppose $p:{\mathbb {R}}\to {\mathbb {R}}$ is a continuous positive function such that

(2) $$ \begin{align} \forall n \in \mathbb{N} \ \lim_{t\rightarrow\infty}\frac{p(t)}{t^n}=\infty. \end{align} $$

We will inductively define sequences $\langle f_n : n\in \mathbb {N}\rangle $ , $\langle A_n : n\in \mathbb {N}\rangle $ and $\langle B_n : n\in \mathbb {N}\rangle $ such that $A_0=\emptyset $ and $B_0=\emptyset $ and for all $n\in \mathbb {N}$ , we have

  1. (I) n $f_n:{\mathbb {C}}\to {\mathbb {C}}$ is entire and $f_n\upharpoonright {\mathbb {R}}$ is real-valued;

  2. (II) n $f_n(x_P)=y_P$ ;

  3. (III) n $\forall x\in {\mathbb {R}} \ f_n'(x)\geq \frac {1}{2}+\frac {1}{2^n}$ , and thus $f_n\upharpoonright {\mathbb {R}}$ is a bijection;

  4. (IV) n if $n>0$ , then $\forall z\in {\mathbb {C}}\ |f_n(z)-f_{n-1}(z)|<\frac {1}{2^n}p(|z|)$ ;

  5. (V) n if $n=2k+1$ is odd, then $A_n=A_{n-1}\cup \{w_k\}$ , $B_n=B_{n-1}$ and we have $w_k\neq x_P \ \implies \ f_n(w_k)\in D_k$ ;

  6. (VI) n if $n=2k+2$ is even, then $A_n=A_{n-1}$ , $B_n=B_{n-1}\cup \{w_k\}$ and we have $w_k\neq y_P \ \implies \ f_n^{-1}(w_k)\in D_k$ ; and

  7. (VII) n if $n>0$ , then $f_n\upharpoonright A_{n-1}=f_{n-1}\upharpoonright A_{n-1}$ and $f_n^{-1}\upharpoonright B_{n-1}=f_{n-1}^{-1}\upharpoonright B_{n-1}$ .

First, let us show that, assuming we have sequences $\langle f_n : n\in \mathbb {N}\rangle $ and $\langle A_n : n\in \mathbb {N}\rangle $ and $\langle B_n : n\in \mathbb {N}\rangle $ satisfying (I) $_n$ -(VII) $_n$ for all n, the pointwise limit defined by $f(z)=\lim _{n\to \infty }f_n(z)$ has all of the desired properties. Suppose D is any compact subset of ${\mathbb {C}}$ . Since $\sum _{n=1}^\infty \frac {1}{2^n}$ converges and since $p(|z|)$ is bounded on D, the fact that (IV) $_n$ holds for all n ensures that the sequence $\langle f_n : n\in \mathbb {N}\rangle $ is uniformly Cauchy on D. Hence, we can define a function $f:{\mathbb {C}}\to {\mathbb {C}}$ by letting $f(z)=\lim _{n\to \infty }f_n(z)$ . Since the sequence $\langle f_n : n\in \mathbb {N}\rangle $ is uniformly Cauchy on any compact set, it follows that the convergence of $\langle f_n : n\in \mathbb {N}\rangle $ to f is uniform on any compact set, and hence, f is an entire function.

Now let us verify that Theorem 5(1)–(4) hold for f. By (I) $_n$ and closure of ${\mathbb {R}}$ in ${\mathbb {C}}$ , we see that $f\upharpoonright {\mathbb {R}}$ is real valued, and since (III) $_n$ holds for all n, we have $f'(x)\geq \frac {1}{2}$ for all $x\in {\mathbb {R}}$ . Thus, Theorem 5(1) and Theorem 5(2) hold. Theorem 5(3) holds since the sequence $\langle f_n(x_P) : n\in \mathbb {N}\rangle $ is constantly equal to $y_P$ . To show that Theorem 5(4) holds, let us prove that for all $i\in \mathbb {N}$ , if $w_i\neq x_P$ , then $f(w_i)\in D_i$ , and if $w_i\neq y_P$ , then $f^{-1}(w_i)\in D_i$ . Fix $i\in \mathbb {N}$ . We have $w_i\in A_{2i+1}$ and $w_i\in B_{2i+2}$ , and furthermore, by (V) $_{2i+1}$ and (VI) $_{2i+2}$ , $w_i\neq x_P$ implies $f_{2i+1}(w_i)\in D_i$ and $w_i\neq y_P$ implies $f_{2i+2}^{-1}(w_i)\in D_i$ . Since (VII) $_n$ holds for all n, we see that both of the sequences $\langle f_n(w_i) : n\in \mathbb {N}\rangle $ and $\langle f_n^{-1}(w_i) : n\in \mathbb {N}\rangle $ are eventually constant, and indeed, for $n\geq 2i+2$ , we have $f_n(w_i)=f_{2i+1}(w_i)$ and $f_n^{-1}(w_i)=f_{2i+2}^{-1}(w_i)$ . Therefore, $f(w_i)=f_{2i+1}(w_i)$ and $f^{-1}(w_i)=f_{2i+2}^{-1}(w_i)$ , so (4) holds.

It remains to show that we can inductively define sequences $\langle f_n : n\in \mathbb {N}\rangle $ , $\langle A_n : n\in \mathbb {N}\rangle $ and $\langle B_n : n\in \mathbb {N}\rangle $ that satisfy (I) $_n$ –(VII) $_n$ for all $n\in \mathbb {N}$ .

Let $f_0:{\mathbb {C}}\to {\mathbb {C}}$ be $f_0(z)=\frac {3}{2}(z-x_P)+y_P$ , $A_0=\emptyset $ and $B_0=\emptyset $ . One may easily verify that (I) $_0$ –(VII) $_0$ hold. For $n> 0$ , Section 2.1 shows how $f_n$ is constructed when n is odd, and Section 2.2 shows how $f_n$ is constructed when n is even.

2.1 When n is odd

Suppose $n=2k+1>0$ is odd and that $f_i$ , $A_i$ and $B_i$ satisfying (I) $_i$ –(VII) $_i$ have already been defined for $i\leq 2k$ . If $k=0$ , we have $A_0=\emptyset $ and $B_0=\emptyset $ , whereas if $k>0$ , we have

$$\begin{align*}A_{n-1}=A_{2k}=A_{2(k-1)+2}=\{w_0,\ldots,w_{k-1}\}\end{align*}$$

and

$$\begin{align*}B_{n-1}=B_{2k}=\{w_0,\ldots,w_{k-1}\}.\end{align*}$$

In any case, we let $A_{n}=A_{n-1}\cup \{w_k\}$ and $B_{n}=B_{n-1}$ . We define $f_{n} = f_{2k+1}$ in two cases as follows.

Case 2.1. A: $\boldsymbol {w_k\notin \{x_P\}\cup A_{n-1}\cup f_{n-1}^{-1}(B_{n-1})}$ . Let us argue that there is an entire function $g_{n}$ such that

  1. (i) $(\forall z\in {\mathbb {C}}) \ g_{n}(z)=0 \ \iff \ z\in \{x_P\}\cup A_{n-1}\cup f_{n-1}^{-1}(B_{n-1})$ ,

  2. (ii) $(\forall z\in {\mathbb {C}}) \ |g_{n}(z)|\leq \frac {1}{2^{n}}p(|z|)$ and

  3. (iii) $(\forall x\in {\mathbb {R}}) \ g_{n}'(x)\geq -\frac {1}{2^{n}}$ .

Take

$$\begin{align*}h_n(z)=(z-x_P)^{\beta_n}(z-w_0)\cdots(z-w_{k-1})(z-f_{n-1}^{-1}(w_0))\cdots(z-f_{n-1}^{-1}(w_{k-1})),\end{align*}$$

where $\beta _n\in \{1,2\}$ is such that the degree of $h_n$ is odd. We will show that for small enough positive $\alpha _n\in {\mathbb {R}}$ , the function $g_n(z)=\alpha _nh_n(z)$ satisfies (i)–(iii). Clearly, $h_n$ satisfies (i), so any such function $g_n(z)$ satisfies (i). For (ii), choose $m\in \mathbb {N}$ and some positive $c\in {\mathbb {R}}$ such that $|h_n(z)|\leq |z|^m+c$ for all $z\in {\mathbb {C}}$ . By our assumption on p, we have $\lim _{|z|\rightarrow \infty }\frac {p(|z|)}{|z|^m+c}=\infty $ , and thus we can let $D\subseteq {\mathbb {C}}$ be a large enough closed disk centered at the origin such that $z\in {\mathbb {C}}\setminus D$ implies $1\leq \frac {p(|z|)}{|z|^m+c}$ . Since p is a continuous positive function, we can choose a positive $\alpha _n\in {\mathbb {R}}$ such that $\alpha _n\leq \frac {1}{2^n}$ and $\alpha _n\leq \frac {p(|z|)}{2^n(|z|^m+c)}$ for all $z\in D$ . Then it follows that for every $z\in {\mathbb {C}}$ , we have

$$\begin{align*}|\alpha_nh_n(z)|\leq\alpha_n(|z|^m+c)\leq\frac{1}{2^n}p(|z|).\end{align*}$$

Let us verify that (iii) holds for small enough $\alpha _n$ . Since $h_n$ is odd and has a positive leading coefficient, the derivative of $h_n\upharpoonright {\mathbb {R}}$ is bounded below. So we may let $d=\inf \{h_n'(x) : x\in {\mathbb {R}}\}\in {\mathbb {R}}$ . Thus, we may choose a small enough positive $\alpha _n\in {\mathbb {R}}$ such that $\alpha _nd\geq -\frac {1}{2^n}$ , and then it follows that for all $x\in {\mathbb {R}}$ , we have $\alpha _nh_n'(x)\geq \alpha _n d\geq -\frac {1}{2^n}$ .

Using the case assumption that $w_k\notin \{x_P\}\cup A_{n-1}\cup f_{n-1}^{-1}(B_{n-1})$ , we see that $g_n(w_k)\neq 0$ , and hence it follows that the set

$$\begin{align*}\{f_{n-1}(w_k)+Mg_{n}(w_k) : M\in[0,1]\}\end{align*}$$

is a nontrivial interval of real numbers. Thus, since $D_k$ is dense in ${\mathbb {R}}$ , it follows that there is some $M_{n}\in [0,1]$ such that $f_{n-1}(w_k)+M_{n}g_{n}(w_k)\in D_k$ . We define

$$\begin{align*}f_{n}(z)=f_{n-1}(z)+M_{n}g_{n}(z).\end{align*}$$

Let us show that (I) $_n$ –(VII) $_n$ hold. It is trivial to see that (I) $_n$ and (II) $_n$ are true. For (III) $_n$ , notice that because $M_n\in [0,1]$ , and since (iii) and (III) $_{n-1}$ both hold, we have for all $x\in {\mathbb {R}}$ ,

$$\begin{align*}f_n'(x)=f_{n-1}'(x)+M_{n}g^{\prime}_{n}(x)\geq\frac{1}{2}+\frac{1}{2^{n-1}}-\frac{1}{2^{n}}=\frac{1}{2}+\frac{1}{2^{n}},\end{align*}$$

and thus $f_n:{\mathbb {R}}\to {\mathbb {R}}$ is a bijection. For (IV) $_n$ , we have for all $z\in {\mathbb {C}}$ ,

$$\begin{align*}|f_n(z)-f_{n-1}(z)|=M_{n}|g_{n}(z)|\leq \frac{1}{2^{n}}p(|z|),\end{align*}$$

where the last inequality follows since $M_n\in [0,1]$ and (ii) holds. Let us verify that (V) $_n$ holds. From the definition of $f_n=f_{2k+1}$ and the way we chose $M_{n}$ , it follows that $f_n(w_k)\in D_k$ (notice that $w_k \neq x_P$ by our case assumption). Thus, (V) $_n$ holds. (VI) $_n$ holds trivially since n is odd. To see that (VII) $_n$ holds, note that since $g_{n}(z)=0$ if $z\in \{x_P\}\cup A_{n-1}\cup f_{n-1}^{-1}(B_{n-1})$ , it follows directly from the definition of $f_n$ that $f_n\upharpoonright A_{n-1}=f_n\upharpoonright A_{n-1}$ and $f_n^{-1}\upharpoonright B_n=f_{n-1}^{-1}\upharpoonright B_{n-1}$ .

Case 2.1. B: $\boldsymbol {w_k\in \{x_P\}\cup A_{n-1}\cup f_{n-1}^{-1}(B_{n-1})}$ . Then we let $f_n=f_{n-1}$ , $A_n=A_{n-1}\cup \{w_k\}$ and $B_n=B_{n-1}$ . Let us argue that this definition of $f_n$ satisfies (V) $_n$ ; the rest of (I) $_n$ –(VII) $_n$ are easily seen to hold by the inductive hypothesis. Suppose $w_k\neq x_P$ . Since the enumeration of W is one-to-one, we have $w_k\neq w_j$ for all $j\leq k-1$ . Thus, for some $j\leq k-1$ , we have $w_k=f_{n-1}^{-1}(w_j)$ , and because $f_{n-1}(x_P)=y_P$ , $f_{n-1}$ is injective and $w_k\neq x_P$ , it follows that $w_j\neq y_P$ . Since $2j+2\leq n-1$ and since it follows by our inductive assumptions (VII) $_{\ell }$ for $\ell \leq n-1$ , that $f_{n-1}\upharpoonright A_{2j+2}=f_{2j+2}\upharpoonright A_{2j+2}$ , we see that $w_k=f_{n-1}^{-1}(w_j)=f_{2j+2}^{-1}(w_j)\in D_j$ . Then $D_j = D_k$ by (*) from page 4. So, $f_n(w_k)=f_{n-1}(w_k)=w_j\in D_j=D_k$ , and hence, (V) $_n$ holds.

2.2 When n is even

Now suppose $n=2k+2$ is even, where $k>0$ , and that $f_i$ , $A_i$ and $B_i$ satisfying (I) $_i$ –(VI) $_i$ have already been defined for $i\leq 2k+1$ . We have

$$\begin{align*}A_{2k+1}=\{w_0,\ldots,w_k\}\end{align*}$$

and

$$\begin{align*}B_{2k+1}=\{w_0,\ldots,w_{k-1}\}.\end{align*}$$

We will define $f_n$ , $A_n$ and $B_n$ in two cases as follows.

Case 2.2. A: $\boldsymbol {f_{n-1}^{-1}(w_k)\notin \{x_P\}\cup A_{n-1}\cup f_{n-1}^{-1}(B_{n-1})}$ . Then we let $g_{n}$ be an entire function such that

  1. (i) $(\forall z\in {\mathbb {C}}) \ g_{n}(z)=0 \ \iff \ z\in \{x_P\}\cup A_{n-1}\cup f_{n-1}^{-1}(B_{n-1})$ ,

  2. (ii) $(\forall z\in {\mathbb {C}}) \ |g_{n}(z)|\leq \frac {1}{2^{n}}p(|z|)$ and

  3. (iii) $(\forall x\in {\mathbb {R}})\ g_{n}'(x)\geq -\frac {1}{2^{n}}$ .

For example, as in the case above where n was odd, we could take

$$\begin{align*}g_n(z)=\alpha_n(z-x_P)^{\beta_n}(z-w_0)\cdots(z-w_k)(z-f_{n-1}^{-1}(w_0))\cdots(z-f_{n-1}^{-1}(w_{k-1}))\end{align*}$$

satisfying (i)–(iii) by choosing $\alpha _n$ small enough and $\beta _n\in \{1,2\}$ so that the degree of $g_n$ is odd. By our inductive assumption about $f_{n-1}$ and by (iii), it follows that for any $M\in [0,1]$ and any $x\in {\mathbb {R}}$ , we have

$$\begin{align*}f_{n-1}'(x)+Mg_{n}'(x)\geq\frac{1}{2}+\frac{1}{2^{n-1}}-\frac{1}{2^{n}}=\frac{1}{2}+\frac{1}{2^{n}}>0.\end{align*}$$

Thus, the function $f_{n-1}+Mg_{n}:{\mathbb {R}}\to {\mathbb {R}}$ is a bijection. Let us argue that the set

$$\begin{align*}\{(f_{n-1}+Mg_{n})^{-1}(w_k) : M\in[0,1]\}\end{align*}$$

is a nontrivial interval of real numbers. It will suffice to show that $(f_{n-1}+g_n)^{-1}(w_k)\neq f^{-1}_{n-1}(w_k)$ . Suppose $(f_{n-1}+g_n)^{-1}(w_k)= f_{n-1}^{-1}(w_k)$ . Then $f_{n-1}(f_{n-1}^{-1}(w_k))=w_k$ and $(f_{n-1}+g_n)(f^{-1}_{n-1}(w_k))=w_k$ . This implies that the functions $f_{n-1}$ and $f_{n-1}+g_n$ are equal at the point $f_{n-1}^{-1}(w_k)$ , and hence, $g_n(f_{n-1}^{-1}(w_k))=0$ , which contradicts (i) by our case assumption that $f_{n-1}^{-1}(w_k) \notin \{x_P\}\cup A_{n-1}\cup f_{n-1}^{-1}(B_{n-1})$ .

Thus, since $D_k$ is dense in ${\mathbb {R}}$ , it follows that there is some $M_{n}\in [0,1]$ such that $(f_{n-1}+M_{n}g_{n})^{-1}(w_k)\in D_k$ . We fix such an $M_{n}$ and define

$$\begin{align*}f_{n}(z)=f_{n-1}(z)+M_{n}g_{n}(z).\end{align*}$$

We also let $A_n=A_{n-1}$ and $B_n=B_{n-1}\cup \{w_k\}$ . The verification that (I) $_n$ –(VII) $_n$ hold is straightforward and similar to the above; it is therefore left to the reader.

Case 2.2. B: $\boldsymbol {f_{n-1}^{-1}(w_k)\in \{x_P\}\cup A_{n-1}\cup f_{n-1}^{-1}(B_{n-1})}$ , or equivalently, $w_k\in \{y_P\}\cup f_{n-1}(A_{n-1})\cup B_{n-1}$ . Then we define $f_n=f_{n-1}$ . As in the odd case above, this definition of $f_n$ is easily seen to satisfy (I) $_n$ –(V) $_n$ and (VII) $_n$ . Let us check (VI) $_n$ . Suppose $w_k\neq y_P$ . Since the enumeration of W is one-to-one, we have $w_k\neq w_j$ for all $j\leq k-1$ , and hence, $w_k=f_{n-1}(w_j)$ for some $j\leq k$ , where $w_j\neq x_P$ . Since $2j+1\leq n-1$ , it follows by our inductive assumptions (V) $_{\ell }$ for $\ell \leq n-1$ that $f_{n-1}\upharpoonright A_{2j+1}=f_{2j+1}\upharpoonright A_{2j+1}$ and $w_k=f_{n-1}(w_j)=f_{2j+1}(w_j)\in D_j$ . Then by (*) from page 4, $D_j = D_k$ . So $f_n^{-1}(w_k) = f_{n-1}^{-1}(w_k) = w_j \in D_j = D_k$ .

This concludes the proof of Theorem 5.

3 Proof of Theorem 2

To prove the $\Leftarrow $ direction of Theorem 2, assume that $\big \{ f_P \ : \ P \in \mathbb {R}^2 \big \}$ is a sparse analytic system and consider the subcollection $\big \{ f_{(0,y)} \ : \ y \in \mathbb {R} \big \}$ . Since $f_{(0,y)}$ passes through the point $(0,y)$ and each $f_{(0,y)}$ is analytic, and hence continuous, it follows that for $y \ne y'$ , $f_{(0,y)} \restriction (-\infty ,0) \ne f_{(0,y')} \restriction (-\infty ,0)$ . So

$$\begin{align*}\mathcal{F}:= \Big\{ f_{(0,y)} \restriction (-\infty,0) \ : \ y \in \mathbb{R} \Big\} \end{align*}$$

is a continuum-sized collection of analytic functions on the common domain $D:=(-\infty ,0)$ . Furthermore, given any $z \in D$ , since $z \ne 0$ and the $f_P$ ’s formed a sparse analytic system, it follows that

$$\begin{align*}\{ f_{(0,y)} (z) \ : \ y \in \mathbb{R} \} \end{align*}$$

is countable. So $\mathcal {F}$ is a collection of analytic functions as in clause (2) of Erdős’ Theorem 1. So by that theorem, CH must hold.

To prove the $\Rightarrow $ direction of Theorem 2 – which is heavily inspired by Erdős’ proof of Theorem 1 – assume CH and fix an enumeration $\langle w_\alpha \ : \ \alpha < \omega _1 \rangle $ of $\mathbb {R}$ . Fix any partition $\mathcal {D}$ of the reals into countable dense subsets of $\mathbb {R}$ .Footnote 4 For each $\alpha < \omega _1$ , let $D_\alpha $ be the unique member of $\mathcal {D}$ containing $w_\alpha $ . Also fix an $\omega _1$ -enumeration $\langle P_\alpha =(a_\alpha ,b_\alpha ) \ : \ \alpha < \omega _1 \rangle $ of $\mathbb {R}^2$ .

Fix an $\alpha < \omega _1$ . By Theorem 5, there exists an entire $f_\alpha : \mathbb {C} \to \mathbb {C}$ such that:

  1. (1) $f_\alpha \restriction \mathbb {R}$ is a real analytic bijection with strictly positive derivative;

  2. (2) $f_\alpha (a_\alpha ) = b_\alpha $ (i.e., $f_\alpha \restriction \mathbb {R}$ passes through the point $P_\alpha $ );

  3. (3) For each $w_\xi $ in the countable set $W_\alpha :=\{ w_\xi \ : \ \xi < \alpha \}$ ,

    1. (a) if $w_\xi \ne a_\alpha $ , then $f_\alpha (w_\xi ) \in D_\xi $ ; and

    2. (b) if $w_\xi \ne b_\alpha $ , then $f_\alpha ^{-1}(w_\xi ) \in D_\xi $ .

We claim that $\{ f_\alpha \restriction \mathbb {R} \ : \ \alpha < \omega _1 \}$ is a sparse analytic system, and the only nontrivial requirement to verify is that if $w \in \mathbb {R}$ , then both

$$\begin{align*}A_w:=\big\{ f_\alpha(w) \ : \ \alpha < \omega_1 \text{ and } w \ne a_\alpha \big\} \end{align*}$$

and

$$\begin{align*}B_w:=\big\{ f_\alpha^{-1}(w) \ : \ \alpha < \omega_1 \text{ and } w \ne b_\alpha \big\} \end{align*}$$

are countable. Say $w = w_\xi $ ; then,

$$ \begin{align*} A_w = A_{w_\xi} & \subseteq \underbrace{\{ f_\alpha(w_\xi) \ : \ \xi < \alpha < \omega_1 \text{ and } w_\xi \ne a_\alpha \}}_{\subseteq D_\xi \text{, by 3a}} \cup \underbrace{\{ f_\alpha(w_\xi) \ : \ \alpha \le \xi \}}_{\text{countable because } \xi < \omega_1}, \end{align*} $$

and hence, $A_w$ is countable. Similarly,

$$ \begin{align*} B_w =B_{w_\xi} & \subseteq \underbrace{\{ f^{-1}_\alpha(w_\xi) \ : \ \xi < \alpha < \omega_1 \text{ and } w_\xi \ne b_\alpha \}}_{\subseteq D_\xi\text{, by 3b}} \cup \underbrace{\{ f^{-1}_\alpha(w_\xi) \ : \ \alpha \le \xi \}}_{\text{countable because } \xi < \omega_1}, \end{align*} $$

and hence, $B_w$ is countable.

4 Proof of Theorem 4

The next lemma is the key connection between sparse analytic systems and predictors.

Lemma 6. Suppose $\mathcal {F}=\langle f_P \ : \ P \in \mathbb {R}^2 \rangle $ is a sparse analytic system. Let $\sim $ be the equivalence relation on $\mathbb {R}$ generated by the set

$$\begin{align*}X:=\Big\{ (u,v) \in \mathbb{R}^2 \ : \ \exists P \in \mathbb{R}^2 \ \big( u \ne x_P \ \wedge \ v \ne y_P \ \wedge \ f_P(u)=v \big) \Big\}. \end{align*}$$

Then,

  1. (1) Each $\sim $ -equivalence class is countable.

  2. (2) For every $P=(x_P,y_P) \in \mathbb {R}^2$ and every $z \in \mathbb {R}$ : if $z \ne x_P$ , then $z \sim f_P(z)$ .

Before proving Lemma 6, we say how the proof of Theorem 4 is finished: assuming CH, Theorem 2 yields the existence of a sparse analytic system. Let $\sim $ be the equivalence relation on $\mathbb {R}$ induced by the sparse analytic system via Lemma 6. The properties of $\sim $ listed in the conclusion of Lemma 6 satisfy the assumptions of Lemma 20 of Cox-Elpers [Reference Cox and Elpers6], and that lemma tells us that if $S:=\mathbb {R}/\sim $ and

$$\begin{align*}\mathcal{P}: {}^{\underset{\smile}{\mathbb{R}}} S \to S \end{align*}$$

is any analytic-anonymous S-predictor,Footnote 5 then $\mathcal {P}$ fails to predict the function $x \mapsto [x]_\sim $ for almost every $x \in \mathbb {R}$ .Footnote 6 In particular, there is no good analytic-anonymous S-predictor.

(Proof of Lemma 6)

Part (2) holds because, by the definition of sparse analytic system, $f_P$ is injective and $f_P(x_P)=y_P$ . So if $z \ne x_P$ , then $f_P(z) \ne y_P$ ; so not only is $z \sim f_P(z)$ , but the pair $\big (z,f_P(z)\big )$ is an element of X.

To prove part (1), since X generates $\sim $ , it suffices to prove that for every $z \in \mathbb {R}$ , both

$$\begin{align*}z^\uparrow:=\{ v \in \mathbb{R} \ : \ (z,v) \in X \} = \{ v \in \mathbb{R} \ : \ \exists P \in \mathbb{R}^2 \ ( z \ne x_P \wedge v \ne y_P \wedge f_P(z)=v ) \} \end{align*}$$

and

$$\begin{align*}z_\downarrow:=\{ u \in \mathbb{R} \ : \ (u,z) \in X \} =\{ u \in \mathbb{R} \ : \ \exists P \in \mathbb{R}^2 \ ( u \ne x_P \wedge z \ne y_P \wedge f_P(u)=z ) \} \end{align*}$$

are countable. But

$$\begin{align*}z^\uparrow \subseteq \{ f_P(z) \ : \ z \ne x_P \} \end{align*}$$

and

$$\begin{align*}z_\downarrow \subseteq \{ f_P^{-1}(z) \ : \ z \ne y_P \}, \end{align*}$$

which are both countable by definition of sparse analytic system.

5 Concluding Remarks

The notion of a sparse analytic system obviously generalizes to a sparse $\Gamma $ -system for any $\Gamma \subseteq \text {Homeo}^+(\mathbb {R})$ , and Lemma 6 easily generalizes to such systems. In fact, Section 4 of Bajpai-Velleman [Reference Bajpai and Velleman2] and Section 5 of Cox-Elpers [Reference Cox and Elpers6] can both be viewed as constructions, in ZFC alone, of sparse $\Gamma $ -systems (with $\Gamma =$ ‘increasing $C^\infty $ bijections’ in [Reference Bajpai and Velleman2] and $\Gamma =$ ‘increasing smooth diffeomorphisms’ in [Reference Cox and Elpers6]).

We have shown that CH implies a negative answer to Bajpai-Velleman’s Question 3, but it is open whether ZFC alone implies a negative solution.

Footnotes

We gratefully acknowledge suggestions of the two referees. Partially funded by VCU SEED Grant and NSF grant DMS-2154141 of the second author.

1 Note that F is allowed to be highly discontinuous; otherwise, the problem trivializes since one could simply predict $F(t)$ by considering $\lim _{x \nearrow t} F(x)$ , which only depends on $F \restriction (-\infty ,t)$ .

2 $\text {Homeo}^+(\mathbb {R})$ denotes the set of increasing homeomorphisms from $\mathbb {R}$ to $\mathbb {R}$ .

3 See also Maurer [Reference Maurer13], Nienhuys-Thiemann [Reference Nienhuys and Thiemann14] and Sato-Rankin [Reference Sato and Rankin15] for related results. Burke [Reference Burke5] provides a nice historical overview of this literature on this topic.

4 For example, define an equivalence relation $\sim $ on $\mathbb {R}$ by: $x \sim y$ iff $y=rx$ for some nonzero $r \in \mathbb {Q}$ . Then the set of equivalence classes constitutes a partition of $\mathbb {R}$ into countable dense subsets of $\mathbb {R}$ . We thank Alex Misiats for pointing out this example (since our original draft used CH to get such a partition).

5 Recall these notions were defined in Section 1.

6 Strictly speaking, the statement of [Reference Cox and Elpers6, Lemma 20] only implies that an analytic-anonymous predictor fails to predict $x \mapsto [x]_\sim $ on a positive-measure set. This is good enough to answer Question 3, since such a predictor would not be good. But the proof of [Reference Cox and Elpers6, Lemma 20] – which was due essentially to Bajpai-Velleman [Reference Bajpai and Velleman2] – shows that an analytic-anonymous predictor can successfully predict $x \mapsto [x]_\sim $ only for those x lying in some fixed equivalence class, which, in the context of Lemma 6, is countable. So analytic-anonymous predictors fail to predict $x \mapsto [x]_\sim $ almost everywhere in this situation.

References

Aigner, M. and Ziegler, G. M., Proofs from The Book, sixth edn, (Springer, Berlin, 2018).CrossRefGoogle Scholar
Bajpai, D. and Velleman, D. J., ‘Anonymity in predicting the future’, Amer. Math. Monthly 123(8) (2016), 777788.CrossRefGoogle Scholar
Barth, K. F. and Schneider, W. J., ‘Entire functions mapping countable dense subsets of the reals onto each other monotonically’, J. Lond. Math. Soc. 2 (1970), 620626.CrossRefGoogle Scholar
Burke, M. R., ‘Approximation and interpolation by entire functions with restriction of the values of the derivatives’, Topology Appl. 213 (2016), 2449.CrossRefGoogle Scholar
Burke, M. R., ‘Entire functions mapping uncountable dense sets of reals onto each other monotonically’, Trans. Amer. Math. Soc. 361(6) (2009), 28712911.CrossRefGoogle Scholar
Cox, S. and Elpers, M., ‘How robustly can you predict the future?’, Canad. J. of Math ., To appear , available at https://arxiv.org/abs/2208.09722.Google Scholar
Erdős, P., ‘An interpolation problem associated with the continuum hypothesis’, Michigan Math. J. 11 (1964), 910.CrossRefGoogle Scholar
Erdős, P., ‘Some unsolved problems’, Michigan Math. J. 4 (1957), 291300.CrossRefGoogle Scholar
Franklin, P., ‘Analytic transformations of everywhere dense point sets’, Trans. Amer. Math. Soc. 27(1) (1925), 91100.CrossRefGoogle Scholar
Garcia, S. R. and Shoemaker, A. L., ‘Wetzel’s Problem, Paul Erdős, and the continuum hypothesis: A mathematical mystery’, Notices Amer. Math. Soc. 62(3) (2015), 243247.Google Scholar
Hardin, C. S. and Taylor, A. D., ‘A peculiar connection between the axiom of choice and predicting the future’, Amer. Math. Monthly 115(2) (2008), 9196.CrossRefGoogle Scholar
Hardin, C. S. and Taylor, A. D., The Mathematics of Coordinated Inference (Developments in Mathematics) vol. 33 (Springer, Cham, 2013).Google Scholar
Maurer, W. D., ‘Conformal equivalence of countable dense sets’, Proc. Amer. Math. Soc. 18 (1967), 269270.CrossRefGoogle Scholar
Nienhuys, J. W. and Thiemann, J. G. F., ‘On the existence of entire functions mapping countable dense sets onto each other’, Indag. Math. 79(4) (1976), 331334.CrossRefGoogle Scholar
Sato, D. and Rankin, S., ‘Entire functions mapping countable dense subsets of the reals onto each other monotonically’, Bull. Aust. Math. Soc. 10 (1974), 6770.CrossRefGoogle Scholar