Counting Δ_0 sets

DOI10.4064/FM-127-1-67-76MaRDI QIDQ3030804zbMATH OpenOpenAlexFDO

Authors Jeff Paris, A. J. Wilkie

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)

Recommendations

• scientific article; zbMATH DE number 3912375
• \(\Delta_0\)-definability of the denumerant with one plus three variables
• scientific article; zbMATH DE number 4033719
• scientific article; zbMATH DE number 3963824
• Some problems in logic and number theory, and their connections

Cited in

(13)

• Counting set classes with Burnside's lemma
• The complexity of the pigeonhole principle
• \(\Delta_0\)-definability of Dedekind sums
• \(\Delta_0\)-definability of the denumerant with one plus three variables
• Iterated multiplication in \(VTC^0\)
• Counting CTL
• Rudimentary relations and primitive recursion: A toolbox
• A note on proofs of falsehood
• Models of arithmetic and categories with finiteness conditions
• \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\)
• Nonerasing, counting, and majority over the linear time hierarchy
• scientific article; zbMATH DE number 4033719 (Why is no real title available?)
• End extensions of models of linearly bounded arithmetic

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3030804)