32
$\begingroup$

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?

$\endgroup$
4
  • 4
    $\begingroup$ Note that I posted at the MSE-question a really long comment which goes into some of the possible subtleties here. In particular, if we shift from $\mathbb{R}$ to $\mathbb{N}^\mathbb{N}$ and allow arbitrary continuous functions in our language we get an $\exists\forall$-definition of continuity, and even in $\mathbb{R}$ if we allow arbitrary continuous functions in our language as opposed to just $+,-,*,0,1,$ and $<$ we can turn the standard $\forall\forall\exists\forall$-definition to a $\forall\exists\forall$-definition. So even though this question has an "obvious" answer, it may be tricky. $\endgroup$ Aug 20, 2023 at 22:01
  • 7
    $\begingroup$ Apart from $\forall\forall\exists\forall$, there is also a $\forall\exists\forall\forall$ definition: $\forall r\,\exists d>0\,\forall x,y\,(-r<x<y<x+d<r\to|f(x)-f(y)|<r^{-1})$ (i.e., “$f$ is locally uniformly continuous”). $\endgroup$ Aug 21, 2023 at 10:13
  • 1
    $\begingroup$ Continuity is the conjunction of continuity from the left and right. If $f$ is non decreasing then continuity from the left is $\forall \exists$, since it says $\forall a \forall b((\forall x < a f(x) \leq b) \Rightarrow f(a)\leq b)$. Ie $f$ preserves sups. Similarly for the right, so continuity for monotonic functions is $\forall \exists$ $\endgroup$
    – Tim Campion
    Aug 22, 2023 at 21:32
  • 2
    $\begingroup$ @TimCampion More simply, for monotone functions, continuity is equivalent to attaining intermediate values: $\forall x,y,v\,(f(x)<v<f(y)\to\exists z\,f(z)=v)$. $\endgroup$ Aug 25, 2023 at 5:39

2 Answers 2

26
+200
$\begingroup$

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.

$\endgroup$
27
  • 2
    $\begingroup$ @AkivaWeinberger Yes, the over-vector notation is the same in this context as the star notation in this context. My understanding is that the former is more common these days and the latter is more "old-school," I just use the latter since it's what I learned. $\endgroup$ Aug 20, 2023 at 23:35
  • 4
    $\begingroup$ I don’t understand how the argument is supposed to work. In order to prove that the usual sentence expressing continuity is not equivalent to a $\forall^*\exists^*$ sentence in all structures of the form $(\mathbb R,+,\cdot,f)$ as the question asks for, you need the structures $(\mathbb R_n^*,+,\cdot,f_n)$ to be models of the theory $T=\bigcap_{f\colon\mathbb R\to\mathbb R}\mathrm{Th}(\mathbb R,+,\cdot,f)$. Why should that be the case when you construct $f_n$ by seemingly arbitrarily tinkering with its values on infinitesimal elements? $\endgroup$ Aug 21, 2023 at 9:59
  • 3
    $\begingroup$ Note that $T$ really is strictly stronger than the theory of real-closed fields in the expanded language: e.g., $T$ includes the sentence $\forall x\,\exists y,z\,(y<x<z\land\forall x'\,(y<x'<z\to f(x)=f(x')))\to\forall x,x'\,f(x)=f(x')$ (i.e., “if $f$ is locally constant, it is constant”), which fails in all real-closed fields other than $\mathbb R$ expanded with suitable $f$. $\endgroup$ Aug 21, 2023 at 10:04
  • 2
    $\begingroup$ For more fun: if $\Phi=\forall X\,\phi(X)$ is any $\Pi^1_1$ sentence with $\phi$ arithmetical, then $\mathbb N\models\Phi$ iff $T$ includes $f(0)=0\land\forall x\,(0<x<1\to f(x)\ne0)\land\forall x\ge0\,(f(x)=0\leftrightarrow f(x+1)=0)\to\phi^*$, where $\phi^*$ is obtained from $\phi$ by relativizing all quantifiers to $x\ge0\land f(x)=0$ and replacing $x\in X$ with $f(-x-1)=0$. That is, $T$ is at least $\Pi^1_1$-hard. $\endgroup$ Aug 21, 2023 at 10:38
  • 3
    $\begingroup$ I think the wording is fine after the second edit (which I didn’t see when I wrote the previous comment), but in these situations it is customary on this site to start the answer with a prominent disclaimer that it does not address the question as written, as a courtesy to the reader, rather than to leave it till the end. $\endgroup$ Aug 21, 2023 at 12:41
3
$\begingroup$

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.

$\endgroup$

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.