Archive for Mathematical Logic 51 (5-6):651-660 (2012)

In (Fund Math 60:175–186 1967), Wolk proved that every well partial order (wpo) has a maximal chain; that is a chain of maximal order type. (Note that all chains in a wpo are well-ordered.) We prove that such maximal chain cannot be found computably, not even hyperarithmetically: No hyperarithmetic set can compute maximal chains in all computable wpos. However, we prove that almost every set, in the sense of category, can compute maximal chains in all computable wpos. Wolk’s original result actually shows that every wpo has a strongly maximal chain, which we define below. We show that a set computes strongly maximal chains in all computable wpo if and only if it computes all hyperarithmetic sets
Keywords Well-quasi-orderings  Well partial order  Maximal chain  Computable well partial order  Hyperarithmetic  Generic
Categories (categorize this paper)
DOI 10.1007/s00153-012-0289-4
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 62,496
Through your library

References found in this work BETA

Pairs of Recursive Structures.C. J. Ash & J. F. Knight - 1990 - Annals of Pure and Applied Logic 46 (3):211-234.
Subsystems of Second-Order Arithmetic.Stephen G. Simpson - 2004 - Studia Logica 77 (1):129-129.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Maximal Chains in the Turing Degrees.C. T. Chong & Liang Yu - 2007 - Journal of Symbolic Logic 72 (4):1219 - 1227.
Maximal Chains in the Fundamental Order.Steven Buechler - 1986 - Journal of Symbolic Logic 51 (2):323-326.
Syntax in Chains.Marcus Kracht - 2001 - Linguistics and Philosophy 24 (4):467-530.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
A Co-Analytic Maximal Set of Orthogonal Measures.Vera Fischer & Asger Törnquist - 2010 - Journal of Symbolic Logic 75 (4):1403-1414.
Maximal Wickedness Vs. Maximal Goodness.Sandra Menssen - 1997 - Proceedings of the American Catholic Philosophical Association 71:91-99.


Added to PP index

Total views
28 ( #388,444 of 2,446,328 )

Recent downloads (6 months)
1 ( #456,608 of 2,446,328 )

How can I increase my downloads?


My notes