No label defined (Q3689182)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3912375
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3912375 |
Statements
1985
0 references
pigeon hole principle
0 references
survey
0 references
0.8337201476097107
0 references
0.8337201476097107
0 references
0.7966935038566589
0 references
0.7952979803085327
0 references
0.7939791083335876
0 references
[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.
0 references