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

      0 references
      0 references
      1985
      0 references
      pigeon hole principle
      0 references
      survey
      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

      Identifiers