4
$\begingroup$

In short: Baire 2 functions are often assumed to be given by a double sequence of continuous functions, thought this is not the exact definition. Does one need the Axiom of Choice (or related) to connect these two definitions?

Longer version: we are working over the real numbers. As is well-known, Baire 0 functions are the continuous ones, while Baire $n+1$ functions are the pointwise limits of Baire $n$ functions.

I call a function $f$ from reals to reals effectively Baire 2 in case it is the double limit of a double sequence $(f_{n,m})_{n, m \in \mathbb{N}}$, i.e. for all reals $x$, we have $$ (\forall \epsilon>0)(\exists n'\in \mathbb{N})(\forall n> n')(\exists m'\in \mathbb{N})(\forall m>m')( |f_{m,n}(x)-f(x)|<\epsilon). \qquad (*) $$ As pointed out by Baire himself already, Baire 2 functions can be represented by effectively Baire 2 functions, though Baire did not use the latter terminology.

The notion (*) is essentially the definition of Baire 2 used in reverse mathematics/second-order arithmetic.

My question is then whether one needs the Axiom of Choice (or related) to show that for a general Baire 2 function, there is a double sequence satisfying (*).

$\endgroup$
6
  • $\begingroup$ I wouldn't be too surprised if the answer is positive, but then again, it might be that AC comes into play only for Baire 3, or Baire $\omega$. These things can be finicky. $\endgroup$
    – Asaf Karagila
    Commented Dec 19, 2022 at 18:25
  • 1
    $\begingroup$ @AsafKaragila It's easy to get a negative result for Baire 3. The indicator function of any countable union of countable sets is Baire 3, so if $\mathbb{R}$ is a countable union of countable sets, not all such functions will be codable by a real. $\endgroup$ Commented Dec 20, 2022 at 3:58
  • $\begingroup$ @ElliotGlazer that doesn't quite work. For example, if the countable union of countable sets is all of $\mathbb{R}$ then the indicator function is effectively Baire class 3 so there's no contradiction there. However, using the effective perfect set theorem you can get a contradiction if you have a countable union of countable sets whose cardinality is neither countable nor continuum. $\endgroup$ Commented Dec 20, 2022 at 4:52
  • $\begingroup$ @PatrickLutz: Related. $\endgroup$
    – Asaf Karagila
    Commented Dec 20, 2022 at 5:08
  • 2
    $\begingroup$ @PatrickLutz If $\mathbb{R}$ is a countable union of countable sets then every subset of $\mathbb{R}$ is also a countable union of countable sets. My point is that there is then $|\mathcal{P}(\mathbb{R})|$ many functions in Baire class 3 so they can't all be coded by a real. $\endgroup$ Commented Dec 20, 2022 at 5:15

1 Answer 1

5
$\begingroup$

It's provable in ZF that every Baire-2 function is effectively Baire-2. It suffices to prove the following:

(ZF) There is an explicit function which maps each Baire-1 function $f: \mathbb{R} \rightarrow \mathbb{R}$ to a sequence of rational polynomials that pointwise converge to it.

The first step is to construct a sequence of reals $\langle r_n \rangle$ such that each $r_n$ codes a rational-valued function $f_n$ such that $|f_n(x)-f(x)| \le \frac{1}{n}$ for all $x \in \mathbb{R}.$ We'll construct $r_1,$ which immediately generalizes to other $n.$

Let $U_k$ enumerate the basic open sets. We use transfinite recursion to define a descending sequence of closed sets $\langle C_{\alpha}: \alpha<\omega_1 \rangle$:

  1. $C_0=\mathbb{R},$
  2. $C_{\alpha+1}=C_{\alpha} \setminus \bigcup \{U_k: \forall x, y \in C_{\alpha} \cap U_k (|f(x)-f(y)|\le 1)\},$
  3. For limit $\alpha,$ $C_{\alpha}=\cap_{\xi<\alpha} C_{\xi}.$

If $C_{\alpha} \neq \emptyset,$ then $f \restriction_{C_{\alpha}}$ is continuous at some $x \in C_{\alpha}$ by Baire's Characterization Theorem. Then $x \not \in C_{\alpha+1},$ so $C_{\alpha+1} \subsetneq C_{\alpha}.$ Define a surjective partial map $g: \omega \rightharpoonup\beta = \{\alpha: C_{\alpha} \neq \emptyset\}$ by sending $k$ to the greatest $\alpha$ such that $U_k \cap C_{\alpha} \neq \emptyset,$ and a well-founded partial ordering $(\omega, \prec)$ by $i \prec j$ if $g(i) < g(j).$ Define $h: \text{dom}(g) \rightarrow \mathbb{Z}$ by $h(k)=\lfloor \sup_{U_k \cap C_{g(k)}} f \rfloor.$

Define $f_1: \mathbb{R} \rightarrow \mathbb{Z}$ as follows: for given $x,$ let $j=\min\{k<\omega: x \in U_k \wedge \forall \alpha (x \in C_{\alpha} \leftrightarrow U_k \cap C_{\alpha} \neq \emptyset)\}.$ Set $f_1(x) = h(j).$

Let $r_1$ be a real which encodes $(\omega, \prec)$ and $h.$ From $(\omega, \prec),$ one can determine the sequence $\langle C_{\alpha}\rangle$ and hence $g.$ Thus, $f_1$ can be determined from $r_1.$ This completes the construction of $r_1$ (and hence all $r_n$).

Let $r$ encode $\langle r_n \rangle$ (and thus $f$). By Shoenfield absoluteness relativized to $r,$ we have in $L[r]$ that $r$ encodes a Baire-1 function $\hat{f}.$ Enumerate the rational polynomials by $\langle q_n \rangle.$ A Stone-Weierstrass argument shows that there is $\langle n_k \rangle$ such that $\langle q_{n_k} \rangle$ converges pointwise to $\hat{f}$ in $L[r].$ Let $\langle n_k \rangle$ be the $L[r]$-least such sequence. Applying Shoenfield absoluteness upwards relative to a real encoding $(r, \langle n_k \rangle),$ we see in $V$ that $\langle q_{n_k} \rangle$ converges pointwise to the Baire-1 function coded by $r,$ namely $f.$ This completes the construction.

Some additional remarks: The above construction can be carried out in $Z_2.$ I don't know enough about subsystems of analysis to say more with confidence. By analyzing how much of $L[r]$ is really needed in the above, you can probably get this down to $\Pi^1_1-CA_0.$

As I showed in the comments, it is not provable in ZF that every Baire-3 function is effectively Baire-3, since if $\mathbb{R}$ is a countable union of countable sets, then every indicator function is Baire-3.

$\endgroup$
6
  • $\begingroup$ Thanks for the nice answer! You mention that your construction can be carried out in $Z_2$. How do you assume the Baire 1 function is given in the language of second-order arithmetic? $\endgroup$ Commented Dec 20, 2022 at 11:04
  • $\begingroup$ @SamSanders In the language of $Z_2,$ you can consider the equivalence relation of $r_1 \sim r_2$ if both reals code sequences of continuous functions which converge to the same output at each $x.$ Then the construction given provides canonical representatives of each equivalence class. $\endgroup$ Commented Dec 20, 2022 at 11:08
  • $\begingroup$ In Kleene's S1-S9 computability theory, the operation on input a function $f$ of bounded variation, output a sequence of continuous functions that pointwise converges to $f$ cannot be done with comprehension functionals less than Kleene's $\exists^3$, which implies full $Z_2$. This shows a big difference between computing with second-order codes and third-order objects. Hence, one should be careful with claims about $\Pi_1^1$-comprehension etc. See here for details: academic.oup.com/logcom/article-abstract/32/8/1747/6833330 $\endgroup$ Commented Dec 20, 2022 at 14:20
  • $\begingroup$ What I'm proposing might be doable in $\Pi^1_1-CA_0$ is showing that the formula defined in this construction sends each pointwise convergence sequence of continuous functions to the canonical sequence of rational polynomials with same pointwise limit. This is a single sentence, so it can only use a finite fragment of $Z_2.$ What would require full $Z_2$ is the theorem scheme which provides every formula which defines the graph of a Baire-1 function a formula defining its canonical rational polynomial sequence. $\endgroup$ Commented Dec 20, 2022 at 16:43
  • $\begingroup$ Certainly one would need full $Z_2$ to prove the scheme assigning every definable class coding a pointwise convergent sequence of graphs of Baire-1 functions to a formula defining a double sequence of polynomials which effectively represents the limit Baire-2 function. $\endgroup$ Commented Dec 20, 2022 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.