My question is the following:

  • Given $x,y \in \omega^\omega$ such that $x\equiv_c y$ is there an $L$-definable continuous map $\varphi: \omega^\omega\rightarrow \omega^\omega$ such that $\varphi(x) = y$?

By $x\equiv_c y$ I mean that they are in the same constructibility degree, i.e. $L(x) = L(y)$ and by $\varphi$ being $L$-definable I mean that the map $\varphi$ is defined by a formula with constructible parameters. Also I can assume (if it is of any help) $V=L(x)$.

At first look I would say that it is unlikely, but I cannot say why.
Do you have any idea or suggestion?


  • 1
    $\begingroup$ Might be relevant: if you add a Sacks real $s$ over $L$, then in $L(s)$, for every real $x,y$, there is a continuous map coded in $L$ that maps $x$ to $y$. This shows up as Lemma 74 in On Sacks Forcing and the Sacks Property by Stefan Geschke and Sandra Quickert. $\endgroup$ Jun 18 at 7:13

1 Answer 1


By "formula" I will mean "formula of set theory with ordinal parameters." Note that "ordinal parameters" is equivalent to "constructible parameters" for our purposes, since $L$ carries a definable bijection with $\mathsf{Ord}$.

Also, since the answer to your question is trivially true if $V=L$, I'm interpreting your question as asking whether we always have the situation you describe. Under this interpretation we get a highly robust negative answer: every $M\models\mathsf{ZFC}$ has a forcing extension in which the principle you ask about fails. So your intuition is correct in a very strong way.

We start with two simple observations:

We always have $x\equiv_c x'$.

Proof: since $x'\ge_Tx$ we have $x'\ge_cx$, and conversely since $x'$ is $\Sigma^0_1(x)$ we have $x\ge_cx'$. $\quad\Box$

Given countably many continuous functions $f_i:\omega^\omega\rightarrow\omega^\omega$ ($i\in\omega$), there is a real $a$ such that whenever $x\ge_Ta$ we have $f_i(x)\le_Tx$ for each $i\in\omega$ - and consequently $f_i(x)\not=x'$ for any $i\in\omega$.

Proof: basically, have $a$ "code" all the $f_i$s in some appropriate way. $\quad\Box$

Now given a (transitive, for simplicity) model $M$ of $\mathsf{ZFC}$, let $\mathsf{ODC}(M)$ ("ordinal-definable continuous") be the set of continuous functions $f:\omega^\omega\rightarrow\omega^\omega$ which are definable over $M$ by a formula with ordinal parameters.

If $\mathsf{ODC}(M)$ is countable in $M$, then $M\models$ "There is a counterexample to your question."

Proof: apply the two simple observations above, with $y=x'$. $\quad\Box$

Of course, on the face of it $\mathsf{ODC}(M)$ could be quite large (e.g. size continuum$^M$). Fortunately, we can control it relatively easily:

If $\mathbb{P}\in M$ is a homogeneous forcing and $G$ is $\mathbb{P}$-generic over $M$, then "$\mathsf{ODC}(M)=\mathsf{ODC}(M[G])$" - or, more precisely, if $f\in\mathsf{ODC}(M[G])$ then $f\upharpoonright M\in\mathsf{ODC}(M)$.

Proof: this is the usual homogeneity argument: the formulas defining elements of $\mathsf{ODC}$ only involve parameters from the ground model, so their behavior on ground model inputs is independent of the choice of generic. Now use definability of forcing. $\quad\Box$

The point is that if $M,M[G]$ are as above, then $$M[G]\models\vert\mathsf{ODC}(M[G])\vert=\vert\mathsf{ODC}(M)\vert.$$ And now to wrap up we just note that $Col(\omega,\kappa)^M$ is homogeneous for any $\kappa$, including $\kappa=\vert\mathsf{ODC}(M)\vert^M$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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