Computing Maximal Chains

Details Computing Maximal Chains Computing Maximal Chains

2012-01-20

arxiv.org/abs/1201.4408v1

Mathematics

Logic

Scientific paper

In 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.

Affiliated with

Also associated with

No associations

Rating

Computing Maximal Chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing Maximal Chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Maximal Chains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-133663