Concept
Alpha recursion theory
Overview
In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals
α
{\displaystyle \alpha }
. An admissible set is closed under
Σ
1
(
L
α
)
{\displaystyle \Sigma _{1}(L_{\alpha })}
functions, where
L
ξ
{\displaystyle L_{\xi }}
denotes a rank of Godel's constructible hierarchy.
α
{\displaystyle \alpha }
is an admissible ordinal if
L
α
{\displaystyle L_{\alpha }}
is a model of Kripke–Platek set theory. In what follows
α
{\displaystyle \alpha }
is considered to be fixed.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
In respect to any complex eternal object, _S(D1, D2, ... Dn)_, the eternal objects _D1, ... Dn_, whose individual essences are constitutive of the individual essence of _S(D1, ... Dn)_, are called the components of _S(D1, ... Dn)_. It is obvious that the grade of complexity to be ascribed to _S(D1, ... Dn)_ is to be taken as one above the highest grade of complexity to be found among its components.
Alfred North Whitehead, Science and the modern world
States what Alpha recursion theory is.
There are nevertheless, in mathematics, some examples of so-called Induction, in which the conclusion does bear the appearance of a generalization grounded on some of the particular cases included in it. A mathematician, when he has calculated a sufficient number of the terms of an algebraical or arithmetical series to have ascertained what is called the _law_ of the series, does not hesitate to fill up any number…
John Stuart Mill, A System of Logic
States what Alpha recursion theory is.
More complicated, but analogous, questions involving propositional functions of two variables involve the notion of "correlation," just as functions of one argument involve classes. Similarly functions of three arguments yield three-cornered correlations, and so on. This logical section is one which Russell has made peculiarly his own by work which must always remain fundamental.
Alfred North Whitehead, The organisation of thought, educational and scientific
Close in meaning to Alpha recursion theory; the term itself is not named.
Related ideas
- First-order logic
- If and only if
- Turing machine
- Second-order arithmetic
- Empty set
- Kripke–Platek set theory
- Admissible ordinal
Place in the tradition
Part of Outline of logic.