Primitive recursive set function

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: P_n,m(x₁, ..., x_n) = x_m 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.
• Given hereditarily finite , the constant function .

One can also add more initial functions to obtain a larger class of functions. For example, the ordinal function 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

• .
• The function assigning to the th level of Godel's constructible hierarchy.

Let be the function , and for all , and . Let L_α denote the αth stage of Godel's constructible universe. L_α is closed under primitive recursive set functions iff α is closed under each for all .