In mathematics, primitive recursive set functions or primitive recursive ordinal functions are analogs of primitive recursive functions, defined for sets or ordinals rather than natural numbers.
They were introduced by Jensen & Karp (1971).
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: The rules for generating new functions by substitution are where x and y are finite sequences of variables.
The rule for generating new functions by recursion is 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: One can also add more initial functions to obtain a larger class of functions.
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 ω:[1] pp.28--29 Let
Let Lα denote the αth stage of Godel's constructible universe.
Lα is closed under primitive recursive set functions iff α is closed under each