# What about the fastest-growing non-computable function ?

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 ?

-

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.