Computable Linearizations of Well-partial-orderings |
| |
Authors: | Antonio Montalbán |
| |
Institution: | (1) Department of Mathematics, University of Chicago, Chicago, IL, USA |
| |
Abstract: | We analyze results on well-partial-orderings from the viewpoint of computability theory, and we answer a question posed by
Diana Schmidt. We obtain the following results. De Jongh and Parikh showed that every well-partial-order has a linearization
of maximal order type. We show that such a linearization can be found computably. We also show that the process of finding
such a linearization is not computably uniform, not even hyperarithmetically. |
| |
Keywords: | Maximal order type Well-partial-ordering |
本文献已被 SpringerLink 等数据库收录! |
|