Computing maximal chains

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


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.



    Upload a copy of this work     Papers currently archived: 91,219

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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

36 (#423,536)

6 months
6 (#448,852)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

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

Add more references