Quantifier complexity of the definition of continuity of functions

Question

This was previously asked at MSE, but I was told to ask it on MO. Consider the structure $(\mathbb{R};+,-,*,0,1,<)$. We adjoin to it a unary function $f$ defined everywhere on the set of real numbers, 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 (specifically, the standard definition is $\forall\forall\exists\forall$). But what is the minimal quantifier complexity that would suffice to give a definition which is equivalent to the standard definition, along with the proof that it is indeed minimal?

Answer 1

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. Emil mentions in the comments, however, that 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.)

An idea for further progress. In the interest of making progress on this excellent question, let me mention a further idea I had realized. Suppose we aim to show that there can be no $\vec\forall\vec\exists$ characterization of "$f$ is continuous" in structures of the form $\langle\R,+,\cdot,0,1,<,f\rangle$. Suppose that $\forall\vec x\,\exists\vec y\ \varphi(\vec x,\vec y)$ is such a characterization, where $\varphi$ is quantifier-free. My idea begins with the observation that if $f$ is continuous, then for any particular $\vec x$, we can ensure that $\exists \vec y\ \varphi(\vec x,\vec y)$ with at most finitely much of the graph of $f$. Namely, the terms appearing in $\varphi$, when applied iteratively at $\vec x$ and the witnesses $\vec y$. If we consider a finite partial function $p:\R\dashrightarrow\R$, we can say that it fulfills a particular $\vec a$ if there is $\vec b$ such that $\varphi(\vec a,\vec b)^p$, using $p$ to interpret the function symbol.

The main idea now is that any finite partial function is part of a continuous function, and thus any finite partial function can be extended to a larger finite partial function that fulfills any given $\vec a$. In other words, in the forcing to add a function $g:\R\to\R$ with finite conditions, it is dense to fulfill any particular instance $\vec a$. It is also dense to agree more and more with highly discontinuous functions.

In particular, if we force over $V$ to add a generic function $g:\R\to\R$ by finite conditions, then the structure $\langle\R^V,+,\cdot,0,1,<,g\rangle$ will fulfill the property $\forall\vec x\,\exists \vec y\ \varphi(\vec x,\vec y)$, since every instance will be fulfilled. And the generic function will also be discontinuous at every point, since indeed the graph of $g$ will be dense in the plane, surjective from any interval.

Meanwhile, this argument doesn't quite show that the property fails in $V[g]$, however, since $g$ is defined only on the ground model reals $\R^V$, not on the reals of the extension $\R^{V[g]}$. What we would like to be doing instead is adding a generic function $g:\R^{V[g]}\to\R^{V[g]}$ by finite conditions, but this is a more delicate idea, which I haven't fully solved yet.

Alternatively, perhaps we can stay in the ground model and assemble a large compatible family of such finite partial functions to form a total function $f:\R\to\R$ with the $\vec\forall\vec\exists$ property, but discontinuous. We can extend any given finite function to fulfill any particular instance $\vec a$, and we can extend a finite partial function on further points so as to agree more and more with a fixed discontinuous function. Can we find an ultrafilter that somehow combines these ideas to find a sufficiently generic family of partial functions that fulfills the full $\vec\forall\vec\exists$ property while being discontinuous? I'm not sure.

Answer 2

The following should really be a comment rather than an answer, but it's too long:

Continuity is rarely $\exists^*$ or $\forall^*$ characterizable.

Specifically, consider the following two properties of a topological space $(X,\tau)$:

• (Finite flexibility) For every finite $A\subseteq X$ and every function $p:A\rightarrow X$, there is a $\tau$-continuous $f:X\rightarrow X$ and a $\tau$-discontinuous $g:X\rightarrow X$ with $f,g\supseteq p$.

The $f$-part is basically an interpolability condition, while the $g$-part says that $(X,\tau)$ is not "almost discrete." In particular, every non-discrete Polish space is finitely flexible.

If $\mathcal{X}$ is any finitely-flexible space, then there is no tuple $\overline{h}$ of $\tau$-continuous finite-arity functions on $X$ such that $\tau$-continuity is either $\exists^*$ or $\forall^*$ over $(X;\overline{h})$. This is because the truth of an $\exists^*$-sentence is forced by a finite configuration: if $(X;\overline{h},t)\models\varphi$ and $\varphi$ is $\exists^*$, then there is some finite $p\subseteq t$ such that all $s\supseteq p$ have $(X;\overline{h},s)\models\varphi$. This means that the $f$- and $g$-clauses of finite flexibility rule out $\forall^*$- and $\exists^*$-characterizations of continuity, respectively.

This raises the question of characterizing continuity over "close-to-discrete" Polish spaces such as $A=\mathbb{N}\cup\{\infty\}$. Here a function $f:A\rightarrow A$ is continuous iff $f$ is eventually constant or $f(\infty)=\infty$ and $f^{-1}(n)$ is finite for every $n\in\mathbb{N}$. I tentatively believe this can be made $\exists\forall$ over an appropriate continuous structure on $A$ and that this is optimal.