Counting $Δ_0$ sets

DOI10.4064/fm-127-1-67-76zbMath0627.03018OpenAlexW802852870MaRDI QIDQ3030804

A. J. Wilkie, Jeffrey Bruce Paris

Publication date: 1987

Published in: Fundamenta Mathematicae (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/211630

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Models of arithmetic and set theory (03C62)

Related Items (8)

The complexity of the pigeonhole principle ⋮ Models of arithmetic and categories with finiteness conditions ⋮ \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\) ⋮ Iterated multiplication in \(VTC^0\) ⋮ End extensions of models of linearly bounded arithmetic ⋮ Rudimentary relations and primitive recursion: A toolbox ⋮ A note on proofs of falsehood ⋮ Nonerasing, counting, and majority over the linear time hierarchy

This page was built for publication: Counting $Δ_0$ sets