any given c.e.set has number M whose power bounds the corresponding elements of S? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T00:09:38Z http://mathoverflow.net/feeds/question/79299 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79299/any-given-c-e-set-has-number-m-whose-power-bounds-the-corresponding-elements-of any given c.e.set has number M whose power bounds the corresponding elements of S? XL 2011-10-27T19:10:05Z 2011-12-25T21:07:44Z <p>For S ,any given c.e.set,does there exist a M (integer) and a partially computable function outputing every element of S the c.e.set ,such that $\forall x\in S,\exists n x=f(n)$ and $x=f(n)\leq M^n$?.</p> http://mathoverflow.net/questions/79299/any-given-c-e-set-has-number-m-whose-power-bounds-the-corresponding-elements-of/79303#79303 Answer by Andreas Blass for any given c.e.set has number M whose power bounds the corresponding elements of S? Andreas Blass 2011-10-27T20:02:42Z 2011-10-27T20:02:42Z <p>Yes, even with $M=2$. Start with any partial recursive function that enumerates $S$ and "slow it down" so that it won't produce output $x$ until after <code>$\log_2 x$</code> steps. With more delay, you can ensure, for example, that $f(n)\leq n$ for all $n$. </p> <p>More formally, if <code>$S=\{x:(\exists y)\ R(x,y)\}$</code>, and if $\langle,\rangle$ is a reasonable pairing function, then define $f(n)$ to be $x$ if, for some $y$, $n=\langle x,y\rangle$ and $R(x,y)$ (and $f(n)$ is undefined otherwise). </p>