scientific article; zbMATH DE number 3912375

From MaRDI portal
Publication:3689182





[For the entire collection see Zbl 0556.00007.] The paper is devoted to the counting problem in bounded arithmetic, namely to the following three still open problems: (1) Let A be a \(\Delta_ 0\) subset of N, then does the set \(\{<n,m>:\) \(m=| A\cap n| \}\) have a \(\Delta_ 0\) definition? (2) Let A be a \(\Delta_ 0\) subset of N, then for \(k\in N\) does \(\{<n,i>:\) \(i<k\) \& \(| A\cap n| =i mod k\}\) have a \(\Delta_ 0\) definition? (3) Does \(I\Delta_ 0\) \((=\) a fragment of Peano arithmetic with \(\Delta_ 0\) induction only) prove \(\Delta_ 0\) pigeon hole principle? The paper is a survey of results obtained in connection with these problems and contains a number of new results of the authors.




Cited in
(46)








This page was built for publication:

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