Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Cited by 363

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 access
Kleene, S. C. · 1943 · Transactions of the American Mathematical Society

Abstract

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1090/s0002-9947-1943-0007371-8

Cites

18 of 18 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 18 references

Cited by

See all 363

Metadata

Authors
Kleene, S. C.
Venue
Transactions of the American Mathematical Society
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.