The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Recursive predicates and quantifiers
Open accessAbstract
This paper contains a general theorem on the quantification of recursive predicates, with applications to the foundations of mathematics.The theorem (Theorem II) is a slight extension of previous results on Herbrand-Gödel general recursive functions(2), while the applications include theorems of Church (Theorem VII)(3) and Gödel (Theorem VIII)(4) and other incompleteness theorems.It is thought that in this treatment the relationship of the results stands out more clearly than before.The general theorem asserts that to each of an enumeration of predicate forms, there is a predicate not expressible in that form.The predicates considered belong to elementary number theory.The possibility that this theorem may apply appears whenever it is proposed to find a necessary and sufficient condition of a certain kind for some given property of natural numbers; in other words, to find a predicate of a given kind equivalent to a given predicate.If the specifications on the predicate which is being sought amount to its having one of the forms listed in the theorem, then for some selection of the given property a necessary and sufficient condition of the desired kind cannot exist.In particular, it is recognized that to find a complete algorithmic theory for a predicate P(a) amounts to expressing the predicate as a recursive predicate.By one of the cases of the theorem, this is impossible for a certain P(a), which gives us Church's theorem.Again, when we recognize that to give a complete formal deductive theory (symbolic logic) for a predicate P{a) amounts to finding an equivalent predicate of the form (Ex)R(a, x) where R(a, x) is recursive, we have immediately Gödel's theorem, as another case of the general theorem.Still another application is made, when we consider the nature of a constructive existence proof.It appears that there is a proposition provable classically for which no constructive proof is possible (Theorem X).The endeavor has been made to include a fairly complete exposition of definitions and results, including relevant portions of previous theory, so that Presented to the Society,
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
On computable numbers, with an application to the entscheidungsproblem
Turing, A. M. (1937) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-42.1.230 · Cited by 8,283
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Gödel, K. (1931) · Monatshefte für Mathematik und Physik · doi:10.1007/bf01700692 · Cited by 2,395
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Gödel, K. (2006) · Monatshefte für Mathematik · doi:10.1007/s00605-006-0423-7 · Cited by 2,077
An Unsolvable Problem of Elementary Number Theory
Church, A. (1936) · American Journal of Mathematics · doi:10.2307/2371045 · Cited by 1,763
On Notation for Ordinal Numbers
Kleene, S. C. (1938) · Journal of Symbolic Logic · doi:10.2307/2267778 · Cited by 758
Self-citationDer Wahrheitsbegriff in den formalisierten Sprachen
Tarski, A. (1986) · De Gruyter eBooks · doi:10.1515/9783112645826-016 · Cited by 741
General recursive functions of natural numbers
Kleene, S. C. (1936) · Mathematische Annalen · doi:10.1007/bf01565439 · Cited by 593
Self-citationFinite combinatory processes—formulation
Post, E. L. (1936) · Journal of Symbolic Logic · doi:10.2307/2269031 · Cited by 516
Systems of Logic Based on Ordinals†
Turing, A. M. (1939) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-45.1.161 · Cited by 504
Extensions of some theorems of Gödel and Church
Rosser, B. (1936) · Journal of Symbolic Logic · doi:10.2307/2269028 · Cited by 359
Cited by
Recursively enumerable sets of positive integers and their decision problems
Post, E. L. (1944) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1944-08111-1 · Cited by 872
Classes of recursively enumerable sets and their decision problems
Rice, H. G. (1953) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1953-0053041-6 · Cited by 869
A Basis for a Mathematical Theory of Computation )
(1963) · Studies in Logic and the Foundations of Mathematics · doi:10.1016/s0049-237x(08)72018-4 · Cited by 692
On the interpretation of intuitionistic number theory
Kleene, S. C. (1945) · Journal of Symbolic Logic · doi:10.2307/2269016 · Cited by 538
Self-citationA Basis for a Mathematical Theory of Computation
(1959) · Studies in Logic and the Foundations of Mathematics · doi:10.1016/s0049-237x(09)70099-0 · Cited by 321
Metadata
- Authors
- Kleene, S. C.
- Venue
- Transactions of the American Mathematical Society
- Publisher
- American Mathematical Society (AMS)
- Published
- 1943
- Volume
- 53
- Issue
- 1
- Pages
- 41-73
- ISSN
- 0002-9947 (ISSN-L)
- 1088-6850
- OpenAlex
- W2087443598
- Cited by
- 363
- References
- 18
- FWCI
- 4.52
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Recursive predicates and quantifiers. https://app.cochat.ai/papers/10.1090/s0002-9947-1943-0007371-8
- The paper
- Kleene, S. C. (1943). Recursive predicates and quantifiers. Transactions of the American Mathematical Society. https://doi.org/10.1090/s0002-9947-1943-0007371-8
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.