Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Busy-Beaver trick provides a nice example of non-computable functions (let say from $\mathbb{N}$ to $\mathbb{N}$) which grows faster than any computable functions. But what can we say when we do not restrict ourselves to computable functions. My question could be, given a countable sets of functions, can we always find a function which grows faster than any function in this set ?

More generally, do we have a sort of a fast-growing hierarchy for non-computable functions ?

Thanks in advance for answers/paper ref. on the subject

share|improve this question
add comment

1 Answer 1

up vote 11 down vote accepted

An easy diagonalization shows that for every countable family of functions $g_n:\mathbb{N}\to\mathbb{N}$, there is a function $f$ eventually exceeding any one of them. Just let $f(n)=\sup_{k\leq n}g_k(n)+1$.

Although it may seem difficult to extend this idea to uncountable families of functions, the fact is that it is consistent with the ZFC axioms of set theory that one may do so. Specifically, the bounding number $\frak{b}$ is the size of the smallest family of functions $f:\mathbb{N}\to\mathbb{N}$ which are not (eventually) bounded by any single function. The observation above shows that the bounding number is uncountable, and it is clearly at most continuum, so under the continuum hypothesis the bounding number is precisely $\aleph_1$. The interesting thing, however, is that the bounding number can be strictly larger than $\aleph_1$, and indeed, by the method of forcing, it can be made as large as you like.

There are numerous interesting set-theoretic issues arising in connection with the bounding number and the other cardinal characteristics of the continuum, some of which I explain in my answer to the MO question Is there a topology on growth rates of functions?. Perhaps the most related to this question are the bounding and dominating numbers, which provide two distinct concepts of measuring the height of the order.

These concepts are also mentioned in several other MO answers, such as here.

share|improve this answer
    
well, I wasn't expected it to be so easy ;) –  Archimondain Jan 3 '12 at 18:49
    
Thanks a lot, your answer about the topology on groth rates of functions looks very interesting –  Archimondain Jan 3 '12 at 18:58
add comment

Your Answer

 
discard

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.