{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T11:59:50Z","timestamp":1778673590519,"version":"3.51.4"},"reference-count":10,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":7954,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1992,6]]},"abstract":"<jats:p>In 1960 G. F. Rose [R] made the following definition: A function <jats:italic>f<\/jats:italic>: \u03c9 \u2192 \u03c9 is (<jats:italic>m, n<\/jats:italic>)-<jats:italic>computable<\/jats:italic>, where 1 \u2264 <jats:italic>m<\/jats:italic> \u2264 <jats:italic>n<\/jats:italic>, iff there exists a recursive function <jats:italic>R<\/jats:italic>: \u03c9<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> \u2192 \u03c9<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> such that, for all <jats:italic>n<\/jats:italic>-tuples (<jats:italic>x<\/jats:italic><jats:sub>1<\/jats:sub>,\u2026, <jats:italic>x<jats:sub>n<\/jats:sub><\/jats:italic>) of distinct natural numbers,<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200022933_eqnU1\"\/><\/jats:disp-formula><\/jats:p><jats:p>J. Myhill (see [McN, p. 393]) asked if <jats:italic>f<\/jats:italic> had to be recursive if <jats:italic>m<\/jats:italic> was close to <jats:italic>n<\/jats:italic>; B. A. Trakhtenbrot [T] responded by showing in 1963 that <jats:italic>f<\/jats:italic> is recursive whenever 2<jats:italic>m<\/jats:italic> &gt; <jats:italic>n<\/jats:italic>. This result is optimal, because, for example, the characteristic function of any semirecursive set is (1,2)-computable. Trakhtenbrot's work was extended by E. B. Kinber [Ki1], using similar techniques. In 1986 R. Beigel [B] made a powerful conjecture, much more general than the above results. Partial verification, falling short of a full proof, appeared in [O]. Using new techniques, M. Kummer has recently established the conjecture, which will henceforth be referred to as the cardinality theorem (CT). It is the goal of this paper to show the connections between these various theorems, to review the methods used by Trakhtenbrot, and to use them to prove a special case of CT strong enough to imply Kinber's theorem (see \u00a73). We thus have a hierarchy of results, with CT at the top. We will also include a discussion of Kummer's methods, but not a proof of CT.<\/jats:p>","DOI":"10.2307\/2275300","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:44:45Z","timestamp":1146955485000},"page":"682-687","source":"Crossref","is-referenced-by-count":22,"title":["Frequency computations and the cardinality theorem"],"prefix":"10.1017","volume":"57","author":[{"given":"Valentina","family":"Harizanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Kummer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jim","family":"Owings","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200022933_ref002","volume-title":"Information and Computation","author":"Beigel"},{"key":"S0022481200022933_ref006","first-page":"677","volume":"57","author":"Kummer","year":"1992","journal-title":"A proof of Beigel's cardinality conjecture"},{"key":"S0022481200022933_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60144-8"},{"key":"S0022481200022933_ref001","unstructured":"Beigel R. , Query-limited reducibilities, Ph.D. Dissertation, Stanford University, Stanford, California, 1987."},{"key":"S0022481200022933_ref008","first-page":"761","volume":"54","author":"Owings","year":"1989","journal-title":"A cardinality version of Beigel's nonspeedup theorem"},{"key":"S0022481200022933_ref009","first-page":"14","volume-title":"International Congress for Logic, Methodology and Philosophy of Science, Abstracts","author":"Rose","year":"1960"},{"key":"S0022481200022933_ref003","first-page":"873","article-title":"Frequency calculations of general recursive predicates and frequency enumeration of sets","volume":"13","author":"Kinber","year":"1972","journal-title":"Soviet Mathematics Doklady"},{"key":"S0022481200022933_ref010","first-page":"25","article-title":"On the frequency computation of functions","volume":"2","author":"Trakhtenbrot","year":"1963","journal-title":"Algebra i Logika"},{"key":"S0022481200022933_ref005","unstructured":"Kinber E. B. , Frequency-computable functions and frequency-enumerable sets, Ph.D. Dissertation, Riga, 1975, (Russian)"},{"key":"S0022481200022933_ref004","doi-asserted-by":"publisher","DOI":"10.1007\/BF01463139"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200022933","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T21:44:26Z","timestamp":1558043066000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200022933\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":10,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["S0022481200022933"],"URL":"https:\/\/doi.org\/10.2307\/2275300","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}