• Images
• Videos
• Documents
• Books
• Articles

Definition

A primitive recursive set function is a function from sets to sets that can be obtained from the following basic functions by repeatedly applying the following rules of substitution and recursion:

The basic functions are:

• Projection: Pn,m (x1, ..., xn) = xm for 0 ≤ m ≤ n
• Zero: F(x) = 0
• Adjoining an element to a set: F(x, y) = x ∪ {y}
• Testing membership: C(x, y, u, v) = x if u ∈ v, and C(x, y, u, v) = y otherwise.

The rules for generating new functions by substitution are

• F(x, y) = G(x, H(x), y)
• F(x, y) = G(H(x), y)

where x and y are finite sequences of variables.

The rule for generating new functions by recursion is

• F(z, x) = G(∪u ∈ z F(u, x), z, x)

A primitive recursive ordinal function is defined in the same way, except that the initial function F(x, y) = x ∪ {y} is replaced by F(x) = x ∪ {x} (the successor of x). The primitive recursive ordinal functions are the same as the primitive recursive set functions that map ordinals to ordinals.

Examples of primitive recursive set functions:

• TC, the function assigning to a set its transitive closure.¹: 26 
• Given hereditarily finite c {\displaystyle c} , the constant function f ( x ) = c {\displaystyle f(x)=c} . ²: 28 

Extensions

One can also add more initial functions to obtain a larger class of functions. For example, the ordinal function α ↦ ω α {\displaystyle \alpha \mapsto \omega ^{\alpha }} is not primitive recursive, because the constant function with value ω (or any other infinite set) is not primitive recursive, so one might want to add this constant function to the initial functions.

The notion of a set function being primitive recursive in ω has the same definition as that of primitive recursion, except with ω as a parameter kept fixed, not altered by the primitive recursion schemata.

Examples of functions primitive recursive in ω:³ pp.28--29

• P ω ( x ) = ⋃ n < ω x n {\displaystyle \mathbb {P} _{\omega }(x)=\bigcup _{n<\omega }x^{n}} .
• The function assigning to α {\displaystyle \alpha } the α {\displaystyle \alpha } th level L α {\displaystyle L_{\alpha }} of Godel's constructible hierarchy.

Primitive recursive closure

Let f 0 : Ord 2 → Ord {\displaystyle f_{0}:{\textrm {Ord}}^{2}\to {\textrm {Ord}}} be the function f ( α , β ) = α + β {\displaystyle f(\alpha ,\beta )=\alpha +\beta } , and for all i < ω {\displaystyle i<\omega } , f ~ i ( α ) = f i ( α , α ) {\displaystyle {\tilde {f}}_{i}(\alpha )=f_{i}(\alpha ,\alpha )} and f i + 1 ( α , β ) = ( f ~ i ) β ( α ) {\displaystyle f_{i+1}(\alpha ,\beta )=({\tilde {f}}_{i})^{\beta }(\alpha )} . Let Lα denote the αth stage of Godel's constructible universe. Lα is closed under primitive recursive set functions iff α is closed under each f i {\displaystyle f_{i}} for all i < ω {\displaystyle i<\omega } . ⁴: 31 

• Jensen, Ronald B.; Karp, Carol (1971), "Primitive recursive set functions", Axiomatic Set Theory, Proc. Sympos. Pure Math., vol. XIII, Part I, Providence, R.I.: Amer. Math. Soc., pp. 143–176, ISBN 9780821802458, MR 0281602

Inline

References

1. R. B. Jensen, Manuscript on fine structure, inner model theory, and the core model below one Woodin cardinal (pp. 22--31). Accessed 2022-12-07 http://www-irm.mathematik.hu-berlin.de/~raesch/org/jensen/pdf/book_sec_1_2.pdf ↩

2. R. B. Jensen, Manuscript on fine structure, inner model theory, and the core model below one Woodin cardinal (pp. 22--31). Accessed 2022-12-07 http://www-irm.mathematik.hu-berlin.de/~raesch/org/jensen/pdf/book_sec_1_2.pdf ↩

3. R. B. Jensen, Manuscript on fine structure, inner model theory, and the core model below one Woodin cardinal (pp. 22--31). Accessed 2022-12-07 http://www-irm.mathematik.hu-berlin.de/~raesch/org/jensen/pdf/book_sec_1_2.pdf ↩

4. R. B. Jensen, Manuscript on fine structure, inner model theory, and the core model below one Woodin cardinal (pp. 22--31). Accessed 2022-12-07 http://www-irm.mathematik.hu-berlin.de/~raesch/org/jensen/pdf/book_sec_1_2.pdf ↩