Switch to: Citations

References in:

Notes on polynomially bounded arithmetic

Domenico Zambella

Journal of Symbolic Logic 61 (3):942-966 (1996)

Add references

You must login to add references.

Bounded arithmetic and the polynomial hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.details T i 2 = S i +1 2 implies ∑ p i +1 ⊆ Δ p i +1 ⧸poly. S 2 and IΔ 0 ƒ are not finitely axiomatizable. The main tool is a Herbrand-type witnessing theorem for ∃∀∃ П b i -formulas provable in T i 2 where the witnessing functions are □ p i +1. Download Export citation Bookmark 46 citations
¹1-formulae on finite structures.M. Ajtai - 1983 - Annals of Pure and Applied Logic 24 (1):1.details Download Export citation Bookmark 26 citations
Exponentiation and second-order bounded arithmetic.Jan Krajíček - 1990 - Annals of Pure and Applied Logic 48 (3):261-276.details V i 2 ⊢A iff for some term t :S i 2 ⊢ “2 i exists→ A”, a bounded first-order formula, i ≥1. V i 2 is not Π b 1 -conservative over S i 2 . Any model of V 2 not satisfying Exp satisfies the collection scheme BΣ 0 1 . V 1 3 is not Π b 1 -conservative over S 2. Download Export citation Bookmark 10 citations

1