In
mathematics, primitive recursive set functions or primitive recursive ordinal functions are analogs of
primitive recursive function
In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
s, defined for
sets or
ordinals rather than
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
s. They were introduced by .
Definition
A primitive recursive set function is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
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'' ∪
*Testing
membership
Member may refer to:
* Military jury, referred to as "Members" in military jargon
* Element (mathematics), an object that belongs to a mathematical set
* In object-oriented programming, a member of a class
** Field (computer science), entries in ...
: ''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'' ∪ is replaced by ''F''(''x'') = ''x'' ∪ (the
successor
Successor may refer to:
* An entity that comes after another (see Succession (disambiguation))
Film and TV
* ''The Successor'' (film), a 1996 film including Laura Girling
* ''The Successor'' (TV program), a 2007 Israeli television program Musi ...
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.
[R. B. Jensen]
Manuscript on fine structure, inner model theory, and the core model below one Woodin cardinal
(pp. 22--31). Accessed 2022-12-07
*Given
hereditarily finite , the constant function
.
Extensions
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
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only s ...
) 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.
Primitive recursive closure
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
.
References
*
Inline
{{reflist
Computability theory
Theory of computation
Functions and mappings
Recursion
Set theory
Ordinal numbers