Bqo is Pi^1_2-complete

Abstract

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.