Institute for Logic, Language and Computation

11 September 2012, Logic Tea, Zhenhao Li

Speaker: Zhenhao Li
Title: Computable Functionals on the Countable Ordinals
Date: Tuesday 11 September 2012
Time: 17:00-18:00
Location: Room A1.04, Science Park 904, Amsterdam

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 For more information, please contact Johannes Marti (), Sebastian Speitel (), or Matthijs Westera ().

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X