11
$\begingroup$

Now at MO.

Consider the structure $(\mathbb{R};+,-,*,0,1,<)$. We adjoin to it a unary function $f$ defined everywhere on the real line, to form the expanded structure $(\mathbb{R};+,-,*,0,1,<,f)$ I can define that $f$ is everywhere continuous by a complicated definition involving several quantifiers. What is the minimum quantifier complexity that would suffice to give an equivalent definition, along with the proof that it is minimal? I apologize if my question is insufficiently rigorous or precise.

$\endgroup$
6
  • 1
    $\begingroup$ @AtticusStonestrom Yes, I mean the arithmetical hierarchy. $\endgroup$
    – user107952
    Aug 6, 2021 at 20:02
  • 3
    $\begingroup$ It's not properly speaking "the arithmetical hierarchy" here. There is a quantifier hierarchy but it's more subtle; for example, since $\mathcal{R}=(\mathbb{R};+,-,*,0,1,<)$ doesn't have a definable pairing operation (being o-minimal) we can't generally collapse like quantifiers (e.g. "$\forall\forall\leadsto\forall$"). So the naive complexity bound in this case is $\forall\forall\exists\forall$. $\endgroup$ Aug 6, 2021 at 22:35
  • $\begingroup$ @NoahSchweber But is it optimal, or can we have an equivalent definition of continuity with less quantifiers? $\endgroup$
    – user107952
    Aug 6, 2021 at 23:24
  • 2
    $\begingroup$ I'm not sure (although I strongly suspect it's optimal) - I was just commenting in response to your comment, re: terminology in this context. $\endgroup$ Aug 6, 2021 at 23:27
  • $\begingroup$ I think you should ask this at MO. $\endgroup$ Aug 20, 2023 at 2:10

2 Answers 2

8
$\begingroup$

This is surprisingly subtle! "Obviously" we shouldn't be able to do better than $\forall^*\exists^*\forall^*$ (in particular, the usual expression$^0$ is $\forall\forall\exists\forall$), but proving this is tricky. In fact, I don't currently see how to prove this! This "answer" is really just a series of comments indicating that the question may be difficult.


Tweaking the question

The original question is in my opinion a bit overly-specific - both to the particular space $\mathbb{R}$ and the particular set of functions/constants/relations $+,\cdot,-,0,1,<$. I think it's natural to look at arbitrary$^1$ topological space $\mathcal{X}$ and allow arbitrary particular constants and continuous finite-arity functions $\mathcal{X}^n\rightarrow\mathcal{X}$; note that for $\mathbb{R}$, the relation $<$ can be recovered via the continuous function $l(a,b)=\min\{b-a, 0\}.$ This lets us see that the problem is "fragile" in a couple ways. Most obviously, via the ($x$- and $y$-coordinate projection functions of the) Peano curve we can turn the $\forall\forall\exists\forall$-expression of continuity into a $\forall\exists\forall$-expression. That's not a huge deal since we're usually more interested in quantifier alternations than sizes of homogeneous quantifier blocks, but it does indicate that the original question will take care if we want to show that $\forall\forall\exists\forall$ is optimal.$^2$

But there's worse to come. Suppose we replace $\mathbb{R}$ with Baire space $\mathbb{N}^\mathbb{N}$. Then there is a continuous binary function $\Phi$ such that each continuous unary $f$ is equal to $\lambda x.\Phi(x,y)$ for some $y$. This means that continuity over $\mathbb{N}^\mathbb{N}$ is $\exists\forall$-expressible over $(\mathbb{N}^\mathbb{N};\Phi)$ via the formula $$\exists y\forall x[f(x)=\Phi(x,y)].$$ Note that $\mathbb{N}^\mathbb{N}$ is a very nice topological space; in particular, it's Polish (= separable and completely metrizable). So maybe this should worry us! Personally I still think the obvious expression of continuity is optimal - in particular, $\mathbb{R}$ is locally compact and connected but $\mathbb{N}^\mathbb{N}$ is not, and these are each significant differences - but it's certainly worth noting.


What can we express?

OK, let's look back at the OP for a moment. At this point it's a good idea to identify some things we can say with low-complexity formulas which might be relevant to expressing continuity. There are two that leap out to me:

  • Every continuous fucntion $f:\mathbb{R}\rightarrow\mathbb{R}$ satisfies $$\forall x,y,z\exists w[f(x)<y<f(z)\implies f(w)=y]$$ (and various strengthenings of same). This is $\forall^*\exists$, so well within the range that we're looking at. It also suggests the Conway base-13 function as an example of a discontinuous function satisfying every $\forall^*\exists^*$-property of continuous functions, buuut ...

  • ... we also need to talk about gaps. Every continuous function $f$ satisfies $$\exists u<v<w[f(u)=f(w)\not=f(v)]\implies\exists a<b\forall c[f(a)=f(b)\wedge a<c<b\implies f(c)\not=f(a)].$$ When "prenexified" this becomes an $\exists^*\forall^*$-sentence, and in particular not one satisfied by Conway's function! So even if the guess at the end of the paragraph above is correct, that still won't be a good way to show optimality of the obvious expression of continuity; we'll need a more complicated method of building "$\exists^*\forall^*\exists^*$-seemingly-continuous" functions.

  • Another thing we can say "cheaply" (that is, better than $\forall^*\exists^*\forall^*$) is "If $0$ is a limit point of $f^{-1}(1)$ then $f(0)=1$;" specifically, this is $\forall^*\exists^*$. Allowing parameters, we can do this for any fixed $r, s\in\mathbb{R}$ in place of $0, 1$ respectively, but saying "Every preimage of a singleton is closed" (which falls short of continuity) seems to require $\forall^*\exists^*\forall^*$.

Ultimately, my takeaway is the following

While none of the observations above really shake my confidence that $\forall^*\exists^*\forall^*$ is optimal, they do indicate that proving this will likely be hard.


Footnotes

$^0$I don't want to say "definition"/"definable"/etc. here since that's not really appropriate: the term "definable" is reserved, generally, for referring to elements of/functions on/relations on the structure in question, whereas we're talking about a class of functions on the structure in question. This isn't a huge deal, but I don't want to create more jargon-friction than necessary.

$^1$Well, maybe not arbitrary. We probably want at least $T_1$, and it's not unreasonable to go further and demand Hausdorffness or even metrizability. But the point stands.

$^2$The wildness of the Peano curve also suggests another way to generalize the problem; only allow "tame" continuous functions, e.g. differentiable. Of course this takes more work to set up, but may ultimately be the way to go.

$\endgroup$
5
+400
$\begingroup$

I have copied this from my answer over at MO.

It is truly a very nice question, one of those questions with an answer one feels must be right, but it is not so clear at first how to prove it.

Nevertheless, aiming at partial progress, I claim that there can be no $\vec\forall\vec\exists$ definition of continuity that works in all real-closed fields, meaning a definition with quantifier complexity $\forall x_0\forall x_1\cdots\forall x_n\exists y_0\exists y_1\cdots \exists y_k\varphi(\vec x,\vec y)$.

The basic reason that there can be no $\vec\forall\vec\exists$ characterization of continuity is that continuity is not preserved to limits of chains of models. To see this, let us start with the real field $\langle\newcommand\R{\mathbb{R}}\R,+,\cdot,-,0,1,<\rangle$, and build an elementary tower of hyperreal models over it, each with more infinitesimals with respect to the previous. $$\R\prec\R^*_1\prec \R^*_2\prec\cdots$$ Each of these is a real-closed field with the same theory as the real field, and also for the union of the elementary chain $\R^*_\omega$.

Now, begin with the constant zero function $f_0(x)=0$ in the bottom field (the reals). In each hyperreal field $\R^*_n$, let $f_n$ extend the previous function, still mostly zero, except that we add a new continuous narrow spiking bump from $0$ up to $1$ and back down to $0$ in the new infinitesimal region of $\R_n$ with respect to the previous model.

Thus, each $f_n$ adds one more flashing bump up to $1$ and back down in the new infinitesimal region of $\R_n$, and $f_n$ has $n$ such bumps. All the functions have $f_n(0)=0$.

When we expand the language to include these functions, we get a chain of models. $$\langle \R,+,\cdot,-,0,1,<,f_0\rangle\subseteq \langle \R^*_1,+,\cdot,-,0,1,<,f_1\rangle\subseteq\cdots$$ Let $\R^*_\omega$ be the union of the fields, with the limit function $f$.

Notice that although each $f_n$ was continuous in the $n$th model, nevertheless the limit model does not think the limit function $f$ is continuous, since it has $f(0)=0$ but there are bumps up to $1$ arbitrarily close to $0$. The limit model function is discontinuous.

In short, you can always add one more big bump near zero while staying continuous, but the limit model will not think the limit $f$ is continuous, since it has those jumps up to 1 arbitrarily close to 0.

It follows that the property of continuity is not preserved by unions of chains, and so it cannot be characterized by a $\vec\forall\vec\exists$ property, since such kind of properties always are preserved to limits of chains.

Remark on the underlying theory. The argument shows that there is no $\vec\forall\vec\exists$ definition that works in all real-closed fields. As Emil Jeřábek mentioned in comments on MO, however, we should be using a stronger theory, namely, the theory $T$ that is true in all structures of the form $\langle\R,+,\cdot,-,0,1,<,f\rangle$ for any choice of function $f:\R\to\R$. That is, what we naturally want is a characterization that works in all these structures. The argument I have given does not quite show that there is no $\vec\forall\vec\exists$ definition of continuity in these structures, since perhaps such a definition works in all these models, but not in all real-closed fields. Since my functions $f_n$ can be taken as definable, each of the models in the tower I build can be taken to satisfy the common theory, and although the limit model is a real-closed field, there seems little reason to suppose it satisfies the common theory. (Indeed, one can arrange that it does not, by coding some forbidden information into the limit function, a little at a time.)

$\endgroup$
3
  • $\begingroup$ I think this still leaves open the $\exists^*\forall^*\exists^*$ case, as well as the $\forall\exists\forall$ case. Still, definitely bounty-worthy! $\endgroup$ Aug 21, 2023 at 0:56
  • $\begingroup$ Regarding the bounty, thanks very much! Yes, I agree those other cases remain open. I wonder whether a similar model-theoretic method can work... $\endgroup$
    – JDH
    Aug 21, 2023 at 0:59
  • $\begingroup$ Certainly not alone since there is an $\exists\forall$-definition of continuity over Baire space. Something particular to the topology of $\mathbb{R}$ needs to be invoked. That's really what excites me the most about this question, it feels very similar to some "versions-of-the-reals" stuff I've thought about in the past but ultimately quite different (and much more compelling TBH). $\endgroup$ Aug 21, 2023 at 1:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .