Approximating a function via definable functions II

Question

In a previous post I asked about the definability of a function that can be "approximated" by a uniformly definable family of functions. Nevertheless, the notion of approximation I gave was too weak and a counterexample was given. Here is another try. Let $T$ be a first order theory, $M\prec N$ models of $T$ equipped with a topology with a uniform definable basis (i.e. every basic open is definable with parameters with the same formula). Suppose furthermore that $N$ is saturated enough. Let $F:M\rightarrow M$ be a partial function such that $dom(F)$ is $M$-definable and open (you can also suppose $rng(F)$ is $M$-definable). Let $(f_a)_{a\in N^k}$ be a uniformly definable family of functions (the only parameters in the formula $f_a$ are $a\in N^k$) such that for every positive integer $n$ and $b_1,...,b_n\in dom(F)$ there is $a\in M^k$ and a basic open $U \subsetneq dom(F)$ containing $b_1,...,b_n$ such that $F\upharpoonright U=f_a\upharpoonright U$. In addition, suppose there is $d\in N^k$ such that $F=f_d\upharpoonright M$. Can we conclude that $F$ is $M$-definable? The question is still interesting dropping the assumption $F=f_d\upharpoonright M$, but in case this question has a negative answer, I would still like to have an answer for the former question.

Answer 1

Let $M$ be the structure consisting of a countable universe with the following structure. There is a binary function $E$ such that, given any finitely many distinct elements $d_1,\dots,d_k\in M$ and any (not necessarily distinct) $a_1,\dots,a_k\in M$ there is some $q\in M$ with $E(q,d_i)=a_i$ for all $i=1,\dots,k$. (I'll abuse notation by letting $E$ serve as both a function symbol and its interpretation in any model, rather than writing $E^M$ here and $E^N$ below.) Let $N$ be a highly saturated elementary extension of $M$. What I need from saturation is that every function $F:M\to M$ is of the form $E(q,-)$ for some $q\in N$. Thus, all functions $F:M\to M$ are the restrictions to $M$ of functions parametrically definable in $N$. Furthermore, every such $F$ agrees on any finite subset of $M$ with $E(q,-)$ for some parameter $q\in M$. Since there are uncountably many such $F$'s and only countably many can be definable from parameters in $M$, we have a negative answer to your question. (You also wanted a topology on $M$ with a definable base, but this seems to be just a remnant of your earlier question, since the topology plays no real role here. If you really want a topology. take the discrete topology with the base consisting of singletons.)

Answer 2

Here is a comparatively concrete counter-example.

Let $N$ be the structure consisting of the binary tree $2^{\lt\omega}$ together with its branches $2^\omega$, with the initial-segment relation and the same-level relation. Let $M$ be any countable elementary substructure of $N$. (One could replace $N$ with a saturated elementary extension, if this feature was really desired.) Consider the function $f_a(x)=y$, if $y\lt a$ and $y$ is on the same level as $x$. That is, we map the part of the tree at levels below $a$ to the path of nodes below $a$. This function is uniformly definable, and the domain consists of the finite sequences shorter than $a$. We may place the discrete topology on the points, although other topologies will also work here.

Now select any branch $d$ in $N$ but not in $M$, and consider $f_d$. This function picks out the nodes below $d$, and is therefore not definable in the substructure $M$, but it is definable in $N$ from $d$. Meanwhile, given any finitely many finite nodes, there is a branch $b$ in $M$ that agrees with $d$ that far, and so $f_d$ is approximated by $f_b$ on that finite set.