Skip to main content
added 3626 characters in body
Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209

The answer is positive if you don’t require $g$ to be continuous. Indeed, continuous functions $[0,1]^n\to[0,1]$ can be approximated by piecewise constant functions whose pieces are boxes with rational endpoints. Any such function is definable in the structure $$M=([0,1],\{I_q:0<q<1,q\in\mathbb Q\}),$$ where $I_q$ is the unary predicate defining the interval $[0,q]$. This structure is easily seen to be superstable.


Concerning Q2, there are several suggestions in the comments to use continuous piecewise affine unary functions, so I can as well explain in detail why it doesn’t work.

First, a general observation. If $X$ is any set, and $G$ a group of permutations of $X$, let $M_G$ be the structure with domain $X$ endowed with unary functions corresponding to all elements of $G$. Then it is easy to show that $M_G$ has quantifier elimination. On the one hand, this implies that $M_G$ is superstable; on the other hand, it easily implies that for any function $f\colon X^n\to X$ definable in $M_G$, there is a finite partition $X^n=\bigcup_{i<k}Y_i$ where each $Y_i$ is definable, and $f\restriction Y_i$ is either constant, or $(f\restriction Y_i)(x_1,\dots,x_n)=g(x_j)$ for some $g\in G$ and $j<n$.

Now, let us take $X=[0,1]$, and $G$ the group of (not necessarily continuous) piecewise affine bijections $[0,1]\to[0,1]$ (with the pieces being intervals). Then all piecewise affine functions (bijective or otherwise) $[0,1]\to[0,1]$ are definable in $M_G$, and by the above, $M_G$ is superstable.

However, $M_G$ cannot continuously approximate all continuous functions $[0,1]^n\to[0,1]$. In fact, I claim that every continuous function $f\colon[0,1]^2\to[0,1]$ definable in $M_G$ depends on at most one variable. We can find a decomposition $[0,1]^2=\bigcup_{i<k}Y_i$ as above. By quantifier elimination, each $Y_i$ is a Boolean combination of rectangles $I\times J$, where $I,J\subseteq[0,1]$ are intervals, and of line segments. Since the complement of a union of finitely many lines is dense in any rectangle, and $f$ is continuous, we may assume all $Y_i$ to be rectangles. That is, there are $0=x_0<x_1<\dots<x_r=1$ and $0=y_0<y_1<\dots<y_s=1$ such that the restriction of $f$ to each $[x_i,x_{i+1}]\times[y_j,y_{j+1}]$ is an affine function of one variable.

Assume for instance that $(f\restriction[x_i,x_{i+1}]\times[y_j,y_{j+1}])(x,y)=L(x)$, where $L$ is a nonconstant affine function. Then $f$ restricted to the neighbouring rectangle $[x_i,x_{i+1}]\times[y_{j+1},y_{j+2}]$ depends on $x$, hence it also has to be an affine function of $x$, and in fact, since an affine function is determined by its value at two points, it has to coincide with $L(x)$. By continuing in this fashion, we see that $f$ coincides with $L(x)$ on the whole strip $[x_i,x_{i+1}]\times[0,1]$. If we assume for contradiction that $f$ restricted to another rectangle $[x_{i'},x_{i'+1}]\times[y_{j'},y_{j'+1}]$ is a nonconstant function of $y$, then the same argument shows that $f$ is an affine function of $y$ on $[0,1]\times[y_{j'},y_{j'+1}]$. But then $f\restriction[x_i,x_{i+1}]\times[y_{j'},y_{j'+1}]$ is simultaneously a function of $x$, and a function of $y$, a contradiction. Thus, $f$ depends only on $x$ on all the rectangles, and we obtain $f(x,y)=g(x)$ for some continuous piecewise affine function $g$.

Thus, for example, $M_G$ cannot continously $\epsilon$-approximate the function $f(x,y)=\min\{x,y\}$ for $\epsilon<1/2$.

Can we do better? In view of the discussion above, we can push this idea to its limits by simply taking for $G$ the group of all bijections $[0,1]\to[0,1]$. The resulting structure is still superstable. The argument above that continuous definable functions depend only on one variable no longer applies, as it relied on topological properties of definable sets that no longer hold (all subsets of $[0,1]$ are definable in the structure). However, I still do not see how one could continuously approximate, say, $\min\colon[0,1]^2\to[0,1]$ to arbitrary precision in this structure.

The answer is positive if you don’t require $g$ to be continuous. Indeed, continuous functions $[0,1]^n\to[0,1]$ can be approximated by piecewise constant functions whose pieces are boxes with rational endpoints. Any such function is definable in the structure $$M=([0,1],\{I_q:0<q<1,q\in\mathbb Q\}),$$ where $I_q$ is the unary predicate defining the interval $[0,q]$. This structure is easily seen to be superstable.

The answer is positive if you don’t require $g$ to be continuous. Indeed, continuous functions $[0,1]^n\to[0,1]$ can be approximated by piecewise constant functions whose pieces are boxes with rational endpoints. Any such function is definable in the structure $$M=([0,1],\{I_q:0<q<1,q\in\mathbb Q\}),$$ where $I_q$ is the unary predicate defining the interval $[0,q]$. This structure is easily seen to be superstable.


Concerning Q2, there are several suggestions in the comments to use continuous piecewise affine unary functions, so I can as well explain in detail why it doesn’t work.

First, a general observation. If $X$ is any set, and $G$ a group of permutations of $X$, let $M_G$ be the structure with domain $X$ endowed with unary functions corresponding to all elements of $G$. Then it is easy to show that $M_G$ has quantifier elimination. On the one hand, this implies that $M_G$ is superstable; on the other hand, it easily implies that for any function $f\colon X^n\to X$ definable in $M_G$, there is a finite partition $X^n=\bigcup_{i<k}Y_i$ where each $Y_i$ is definable, and $f\restriction Y_i$ is either constant, or $(f\restriction Y_i)(x_1,\dots,x_n)=g(x_j)$ for some $g\in G$ and $j<n$.

Now, let us take $X=[0,1]$, and $G$ the group of (not necessarily continuous) piecewise affine bijections $[0,1]\to[0,1]$ (with the pieces being intervals). Then all piecewise affine functions (bijective or otherwise) $[0,1]\to[0,1]$ are definable in $M_G$, and by the above, $M_G$ is superstable.

However, $M_G$ cannot continuously approximate all continuous functions $[0,1]^n\to[0,1]$. In fact, I claim that every continuous function $f\colon[0,1]^2\to[0,1]$ definable in $M_G$ depends on at most one variable. We can find a decomposition $[0,1]^2=\bigcup_{i<k}Y_i$ as above. By quantifier elimination, each $Y_i$ is a Boolean combination of rectangles $I\times J$, where $I,J\subseteq[0,1]$ are intervals, and of line segments. Since the complement of a union of finitely many lines is dense in any rectangle, and $f$ is continuous, we may assume all $Y_i$ to be rectangles. That is, there are $0=x_0<x_1<\dots<x_r=1$ and $0=y_0<y_1<\dots<y_s=1$ such that the restriction of $f$ to each $[x_i,x_{i+1}]\times[y_j,y_{j+1}]$ is an affine function of one variable.

Assume for instance that $(f\restriction[x_i,x_{i+1}]\times[y_j,y_{j+1}])(x,y)=L(x)$, where $L$ is a nonconstant affine function. Then $f$ restricted to the neighbouring rectangle $[x_i,x_{i+1}]\times[y_{j+1},y_{j+2}]$ depends on $x$, hence it also has to be an affine function of $x$, and in fact, since an affine function is determined by its value at two points, it has to coincide with $L(x)$. By continuing in this fashion, we see that $f$ coincides with $L(x)$ on the whole strip $[x_i,x_{i+1}]\times[0,1]$. If we assume for contradiction that $f$ restricted to another rectangle $[x_{i'},x_{i'+1}]\times[y_{j'},y_{j'+1}]$ is a nonconstant function of $y$, then the same argument shows that $f$ is an affine function of $y$ on $[0,1]\times[y_{j'},y_{j'+1}]$. But then $f\restriction[x_i,x_{i+1}]\times[y_{j'},y_{j'+1}]$ is simultaneously a function of $x$, and a function of $y$, a contradiction. Thus, $f$ depends only on $x$ on all the rectangles, and we obtain $f(x,y)=g(x)$ for some continuous piecewise affine function $g$.

Thus, for example, $M_G$ cannot continously $\epsilon$-approximate the function $f(x,y)=\min\{x,y\}$ for $\epsilon<1/2$.

Can we do better? In view of the discussion above, we can push this idea to its limits by simply taking for $G$ the group of all bijections $[0,1]\to[0,1]$. The resulting structure is still superstable. The argument above that continuous definable functions depend only on one variable no longer applies, as it relied on topological properties of definable sets that no longer hold (all subsets of $[0,1]$ are definable in the structure). However, I still do not see how one could continuously approximate, say, $\min\colon[0,1]^2\to[0,1]$ to arbitrary precision in this structure.

Source Link
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209

The answer is positive if you don’t require $g$ to be continuous. Indeed, continuous functions $[0,1]^n\to[0,1]$ can be approximated by piecewise constant functions whose pieces are boxes with rational endpoints. Any such function is definable in the structure $$M=([0,1],\{I_q:0<q<1,q\in\mathbb Q\}),$$ where $I_q$ is the unary predicate defining the interval $[0,q]$. This structure is easily seen to be superstable.