On the strength of Fraïssé’s conjecture
Richard A. Shore · Birkhäuser Boston eBooks · 1993
We show that Fraïssé’s conjecture that the class of linear orderings is well-quasiordered under embedability is proof theoretically strong. Indeed, even special cases of its restriction to wellorderings implies ATR 0 : If the class of wellorderings has no infinite antichains or no infinite descending chains then ATR 0 . is provable in RCA 0 . These results answer questions of Clote, Friedman and Hirst. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.