10,891 Pages

$$\omega$$ (pronounced "omega") is the first transfinite ordinal, the smallest ordinal greater than all the positive integers. In the von Neumann definition of ordinals, it is equal to the set of nonnegative integers $$\mathbb{N}$$.

In the Wainer hierarchy, the fundamental sequence of $$\omega$$ is $$0,1,2,\ldots$$. Using this hierarchy, the following holds:

However, if we are not working in the Wainer hierarchy, $$f_\omega$$ may be arbitrarily fast-growing. For example, letting $$\omega[n] = \Sigma(n)$$ (where $$\Sigma(n)$$ is a busy beaver function) makes $$f_\omega$$ uncomputable.

In fact, there are as many fundamental sequences for $$\omega$$ (and for any other countable ordinal), as the number of monotonically increasing $$\mathbb{N} \to \mathbb{N}$$ functions, i.e. continuum $$\mathfrak c$$ of them.

$$\omega$$ is the first admissible ordinal. It is also the first transfinite regular ordinal.

Community content is available under CC-BY-SA unless otherwise noted.