{
  "id": "enwiki-001316116777",
  "slug": "primitive-recursive-set-function",
  "title": "Primitive recursive set function",
  "qid": "",
  "lead": "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 .",
  "body": "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 ,&thinsp;...,&thinsp;x n ) = x m for 0&thinsp;≤&thinsp;m&thinsp;≤&thinsp;n Zero: F(x) = 0 Adjoining an element to a set: F(x,&thinsp;y) = x&thinsp;∪&thinsp;{y} Testing membership: C(x,&thinsp;y,&thinsp;u,&thinsp;v) = x if u&thinsp;∈&thinsp;v, and C(x,&thinsp;y,&thinsp;u,&thinsp;v) = y otherwise. The rules for generating new functions by substitution are F(x,&thinsp;y) = G(x, H(x), y) F(x,&thinsp;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,&thinsp;x) = G(∪ u ∈ z &thinsp;F(u,&thinsp;x), z, x) A primitive recursive ordinal function is defined in the same way, except that the initial function F(x,&thinsp;y) = x&thinsp;∪&thinsp;{y} is replaced by F(x) = x&thinsp;∪&thinsp;{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===",
  "categories": [
    "20477108",
    "23054168",
    "24719580",
    "26159830",
    "26868936",
    "29176345",
    "48128016"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1316116777",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1760102779.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001316116777",
    "type": "webpage",
    "title": "Primitive recursive set function",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/primitive-recursive-set-function",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001316116777",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1316116777",
    "note": "Immutable snapshot enwiki-001316116777"
  }
}