Primitive recursive set function ================================ 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 . 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 . ==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: P n,m (x 1 , ..., 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 c , the constant function f(x)=c . ==Extensions== One can also add more initial functions to obtain a larger class of functions. For example, the ordinal function \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 \mathbb P_\omega(x)=\bigcup_{n . The function assigning to \alpha the \alpha th level L_\alpha of Godel's constructible hierarchy. ==Primitive recursive closure== Let f_0:\textrm{Ord}^2\to\textrm{Ord} be the function f(\alpha,\beta) =\alpha+\beta , and for all i , \tilde{f}_i(\alpha) = f_i(\alpha,\alpha) and 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 for all i . ==References== ===Inline=== REFERENCES ---------- BIBLIOGRAPHY (BibTeX) -------------------- @article{ref0, title = {Primitive recursive set function}, url = {https://encyclopegia.org/a/primitive-recursive-set-function} } BIBLIOGRAPHY (RIS) ------------------- TY - JOUR TI - Primitive recursive set function UR - https://encyclopegia.org/a/primitive-recursive-set-function ER - CITE THIS ARTICLE ---------------- Cite this article: Primitive recursive set function Derived from: https://en.wikipedia.org/w/index.php?oldid=1316116777 Licence: CC BY-SA 4.0 Snapshot: enwiki-001316116777 Permalink: /a/primitive-recursive-set-function