11 September 2012, Logic Tea, Zhenhao Li

Countable ordinals can be represented by well orderings on subsets of natural numbers. Fixing a computable pairing function, each well ordering on a subset of natural numbers can be coded into a set of natural numbers which is called a "real code". We say that a (partial) function $f$ on the countable ordinals is computable if there is an oracle Turing machine such that given any real code $X$ of any ordinal $\alpha$ in the domain of $f$ as the oracle it will "output" a real code of $f(\alpha)$. In other words, $f$ is computable if real codes of $f(\alpha)$ are computable uniformly from real codes of $\alpha$ for any $\alpha$ in the domain of $f$. We show that the three basic operations of ordinal arithmetic are computable. We study other "natural" functions and show that some are computable and some are not.

We define that $\alpha$ is reducible to $\beta$ if the singleton function $(\beta, \alpha)$ is computable. This induces a degree structure on the countable ordinals, where the bottom degree is the set of computable ordinals. We show that the order type of the degree of $\omega_1^{ck}$ is at least $\omega$ which is a consequence of among others the statement that the singleton function $(\omega_1^{ck}+\omega, \omega_1^{ck})$ is computable.

The Logic Tea homepage can be found at http://www.illc.uva.nl/logic_tea/ For more information, please contact Johannes Marti (johannes.marti at gmail.com), Sebastian Speitel (sebastian.speitel at gmail.com), or Matthijs Westera (M.Westera at uva.nl).