An Equivalence between Second Order Bounded Domain Bounded Arithmetic and First Order Bounded Arithmetic
Alexander Alexandrovich Razborov · 1993
Abstract But Bounded Arithmetic also gives an opportunity to directly interpret second order objects in a first order language. The antagonism “second order vs. first order” translates via this interpretation to “arbitrary integers vs. those “small” integers x for which f(x) exists” where f is a rapidly growing function whose existence is not provable in Bounded Arithmetic.