×

On the strength of Fraïssé’s conjecture. (English) Zbl 0820.03037

Crossley, John N. (ed.) et al., Logical methods. In honor of Anil Nerode’s 60th birthday. Basel: Birkhäuser. Prog. Comput. Sci. Appl. Log. 12, 782-813 (1993).
The paper is devoted to the study of proof-theoretical strength of Fraissé’s conjecture (stating that the class of linear orderings is well-quasiordered under embeddability). In particular it is shown that if the class of well-orderings has no infinite antichains or no infinite descending chains, then \(\text{ATR}_ 0\) is provable in \(\text{RCA}_ 0\), where \(\text{RCA}_ 0\) and \(\text{ATR}_ 0\) are fragments of the second-order arithmetic studied by reverse mathematics \((\text{RCA}_ 0 =\) Peano arithmetic \(+\) \(\Delta^ 0_ 1\)-comprehension \(+\) \(\Sigma^ 0_ 1\) induction, \(\text{ATR}_ 0 =\) Peano arithmetic + the assertion that arithmetic comprehension can be iterated along any countable well- ordering). The results answer problems of Clote, Friedman and Hirst.
For the entire collection see [Zbl 0810.00003].

MSC:

03F35 Second- and higher-order arithmetic and fragments
03F15 Recursive ordinals and ordinal notations
03D80 Applications of computability and recursion theory
PDFBibTeX XMLCite