Inmathematics,primitive recursive set functions orprimitive recursive ordinal functions are analogs ofprimitive recursive functions, defined forsets orordinals rather thannatural numbers. They were introduced byJensen & Karp (1971).

A primitive recursive set function is afunction 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}
• Testingmembership:C(x, y, u, v) =x ifu ∈ v, andC(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)

wherex andy 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 functionF(x, y) =x ∪ {y} is replaced byF(x) =x ∪ {x} (thesuccessor ofx). 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.^[1]: 26
• Givenhereditarily finite${\displaystyle c}$, the constant function${\displaystyle f(x)=c}$.^[1]: 28

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

The notion of a set function beingprimitive 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

• .
• The function assigning to${\displaystyle \alpha }$ the${\displaystyle \alpha }$th level${\displaystyle L_{\alpha }}$ ofGodel's constructible hierarchy.

Let${\displaystyle f_0:{\text{Ord}}^2\to \text{Ord}}$ be the function${\displaystyle f(\alpha ,\beta )=\alpha +\beta }$, and for all,${\displaystyle {\tilde{f}}_i(\alpha )=f_i(\alpha ,\alpha )}$ and${\displaystyle f_{i+1}(\alpha ,\beta )=({\tilde{f}}_i{)}^{\beta }(\alpha )}$. Let L_α denote the αth stage ofGodel's constructible universe. L_α is closed under primitive recursive set functions iff α is closed under each${\displaystyle f_i}$ for all.^[1]: 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

• Computability theory
• Theory of computation
• Functions and mappings
• Recursion
• Set theory
• Ordinal numbers

• CS1: long volume value