Shore, Richard A. 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]. Reviewer: R.Murawski (Poznań) Cited in 2 ReviewsCited in 7 Documents MSC: 03F35 Second- and higher-order arithmetic and fragments 03F15 Recursive ordinals and ordinal notations 03D80 Applications of computability and recursion theory Keywords:proof-theoretical strength; Fraissé’s conjecture; linear orderings; well-orderings; second-order arithmetic; reverse mathematics PDFBibTeX XMLCite \textit{R. A. Shore}, Prog. Comput. Sci. Appl. Log. 12, 782--813 (1993; Zbl 0820.03037)