MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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.)

share|cite|improve this answer
Thanks. Indeed the topology is not playing any role. I guess, the situation I was having in mind is much more specific than the question I asked. Maybe there will be an Approximating functions part III... – Cubikova Apr 23 '13 at 11:39

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.

share|cite|improve this answer
This is very illustrative, thanks. Worth noticing that it is almost the same idea, since it also makes use tacitly of the same cardinality argument when we pick $M$ to be a countable substructure of $N$. – Cubikova Apr 23 '13 at 12:01
It is also possible to do it with two countable models, as long as $N$ has a branch that is not in $M$. – Joel David Hamkins Apr 23 '13 at 12:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.