Fraisse's conjecture in Pi(1)(1)-comprehension

摘要

We prove Fraisse's conjecture within the system of Pi(1)(1)-comprehension. Furthermore, we prove that Fraisse's conjecture follows from the Delta(0)(2)-bqo-ness of 3 over the system of Arithmetic Transfinite Recursion, and that the Delta(0)(2)-bqo-ness of 3 is a Pi(1)(2)-statement strictly weaker than Pi(1)(1)-comprehension.