Bqo is Pi^1_2-complete

Details Bqo is Pi^1_2-complete Bqo is Pi^1_2-complete

1994-05-24

arxiv.org/abs/math/9405207v1

Mathematical Logic Quarterly 41 (1995) 373-383

Mathematics

Logic

Scientific paper

In this paper we prove that the set of countable bqos (viewed as a subset of the Cantor space) is Pi^1_2-complete. The notion of bqo or better quasi-ordering arises from combinatorics and is a generalization of the canonical example of a Pi^1_1-complete notion, i.e. that of countable well-ordering. The Pi^1_2-completeness of bqo was conjectured by Clote and proved by the author in his Ph.d. thesis: in this paper we prove it using Simpson's definition of bqo and as little bqo theory as possible.

Affiliated with

Also associated with

No associations

Rating

Bqo is Pi^1_2-complete 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 Bqo is Pi^1_2-complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bqo is Pi^1_2-complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-494334