Primitive recursive set function - Revision history

Hellacioussatyr: /* Primitive recursive closure */

2022-12-24T06:34:06Z

Primitive recursive closure

← Previous revision		Revision as of 06:34, 24 December 2022
Line 35:		Line 35:

	==Primitive recursive closure==		==Primitive recursive closure==
	Let <math>f_0:\textrm{Ord}^2\to\textrm{Ord}</math> be the function <math>f(\alpha,\beta)=\alpha+\beta</math>, and for all <math>i<\omega</math>, <math>\tilde{f}_i(\alpha)=f_i(\alpha,\alpha)</math> and <math>f_{i+1}(\alpha,\beta)=(\tilde{f}_i)^\beta(\alpha)</math>. Let L<sub>α</sub> denote the αth stage of [[Constructible universe\|Godel's constructible universe]]. L<sub>α</sub> is closed under primitive recursive set functions iff α is closed under each <math>f_i</math> for all <math>i<\omega</math>. <ref name="JensenManuscript" />~~<sup>~~p.31~~</sup>~~		Let <math>f_0:\textrm{Ord}^2\to\textrm{Ord}</math> be the function <math>f(\alpha,\beta) =\alpha+\beta</math>, and for all <math>i<\omega</math>, <math>\tilde{f}_i(\alpha) = f_i(\alpha,\alpha)</math> and <math>f_{i+1}(\alpha,\beta) = (\tilde{f}_i)^\beta(\alpha)</math>. Let L<sub>α</sub> denote the αth stage of [[Constructible universe\|Godel's constructible universe]]. L<sub>α</sub> is closed under primitive recursive set functions iff α is closed under each <math>f_i</math> for all <math>i<\omega</math>. <ref name="JensenManuscript" />{{rp\|p=31}}

	==References==		==References==

Hellacioussatyr: /* Definition */

2022-12-24T06:30:29Z

Definition

← Previous revision		Revision as of 06:30, 24 December 2022
Line 22:		Line 22:

	Examples of primitive recursive set functions:		Examples of primitive recursive set functions:
	*[[~~Transitive_set~~#~~Transitive_closure~~\|TC]], the function assigning to a set its transitive closure.<ref name="JensenManuscript">R. B. Jensen, [http://www-irm.mathematik.hu-berlin.de/~raesch/org/jensen/pdf/book_sec_1_2.pdf Manuscript on fine structure, inner model theory, and the core model below one Woodin cardinal] (pp. 22--31). Accessed 2022-12-07</ref>~~<sup>~~p.26~~</sup>~~		*[[Transitive set#Transitive closure\|TC]], the function assigning to a set its transitive closure.<ref name="JensenManuscript">R. B. Jensen, [http://www-irm.mathematik.hu-berlin.de/~raesch/org/jensen/pdf/book_sec_1_2.pdf Manuscript on fine structure, inner model theory, and the core model below one Woodin cardinal] (pp. 22--31). Accessed 2022-12-07</ref>{{rp\|p=26}}
	*Given [[hereditarily finite set\|hereditarily finite]] <math>c</math>, the constant function <math>f(x)=c</math>. <ref name="JensenManuscript" />~~<sup>~~p.28~~</sup>~~		*Given [[hereditarily finite set\|hereditarily finite]] <math>c</math>, the constant function <math>f(x)=c</math>. <ref name="JensenManuscript" />{{rp\|p=28}}

	==Extensions==		==Extensions==
	One can also add more initial functions to obtain a larger [[Class (set theory)\|class]] of functions. For example, the ordinal function <math>\alpha\mapsto\omega^\alpha</math> 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.		One can also add more initial functions to obtain a larger [[Class (set theory)\|class]] of functions. For example, the ordinal function <math>\alpha\mapsto\omega^\alpha</math> 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.

C7XWiki: /* Extensions */

2022-12-13T07:03:52Z

Extensions

← Previous revision		Revision as of 07:03, 13 December 2022
Line 29:		Line 29:
	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.		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 ω:<ref name="JensenManuscript" /><sup>pp.28--29</sup>		Examples of functions primitive recursive in ω:<ref name="JensenManuscript" /> <sup>pp.28--29</sup>
	*<math>\mathbb P_\omega(x)=\bigcup_{n<\omega}x^n</math>.		*<math>\mathbb P_\omega(x)=\bigcup_{n<\omega}x^n</math>.
	*The function assigning to <math>\alpha</math> the <math>\alpha</math>th level <math>L_\alpha</math> of [[Constructible universe\|Godel's constructible hierarchy]]		*The function assigning to <math>\alpha</math> the <math>\alpha</math>th level <math>L_\alpha</math> of [[Constructible universe\|Godel's constructible hierarchy]].

	==Primitive recursive closure==		==Primitive recursive closure==
	Let <math>f_0:\textrm{Ord}^2\to\textrm{Ord}</math> be the function <math>f(\alpha,\beta)=\alpha+\beta</math>, and for all <math>i<\omega</math>, <math>\tilde{f}_i(\alpha)=f_i(\alpha,\alpha)</math> and <math>f_{i+1}(\alpha,\beta)=(\tilde{f}_i)^\beta(\alpha)</math>. Let L<sub>α</sub> denote the αth stage of [[Constructible universe\|Godel's constructible universe]]. L<sub>α</sub> is closed under primitive recursive set functions iff α is closed under each <math>f_i</math> for all <math>i<\omega</math>. <ref name="JensenManuscript" /><sup>p.31</sup>		Let <math>f_0:\textrm{Ord}^2\to\textrm{Ord}</math> be the function <math>f(\alpha,\beta)=\alpha+\beta</math>, and for all <math>i<\omega</math>, <math>\tilde{f}_i(\alpha)=f_i(\alpha,\alpha)</math> and <math>f_{i+1}(\alpha,\beta)=(\tilde{f}_i)^\beta(\alpha)</math>. Let L<sub>α</sub> denote the αth stage of [[Constructible universe\|Godel's constructible universe]]. L<sub>α</sub> is closed under primitive recursive set functions iff α is closed under each <math>f_i</math> for all <math>i<\omega</math>. <ref name="JensenManuscript" /><sup>p.31</sup>

C7XWiki at 07:03, 13 December 2022

2022-12-13T07:03:23Z

@@ Line 21: / Line 21: @@
 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 ordinal|successor]] of ''x''). The primitive recursive ordinal functions are the same as the primitive recursive set functions that map ordinals to ordinals.
 ==References==
@@ Line 28: / Line 39: @@
 |last=Jensen|first= Ronald B.|last2= Karp|first2= Carol
 |chapter=Primitive recursive set functions|year= 1971 |title=Axiomatic Set Theory |series=Proc. Sympos. Pure Math.|volume= XIII, Part I|pages= 143–176 |publisher=Amer. Math. Soc.|place= Providence, R.I.|isbn=9780821802458}}
 [[Category:Computability theory]]
 [[Category:Theory of computation]]

Joel Brennan: added wikilinks and removed the "underlinked" tag

2020-08-14T19:27:39Z

added wikilinks and removed the "underlinked" tag

← Previous revision		Revision as of 19:27, 14 August 2020
Line 1:		Line 1:
		⚫	In [[mathematics]], '''primitive recursive set functions''' or '''primitive recursive ordinal functions''' are analogs of [[primitive recursive function]]s, defined for [[Set (mathematics)\|sets]] or [[Ordinal number\|ordinals]] rather than [[natural number]]s. They were introduced by {{harvtxt\|Jensen\|Karp\|1971}}.
	{{Underlinked\|date=January 2019}}

⚫	In mathematics, '''primitive recursive set functions''' or '''primitive recursive ordinal functions''' are analogs of [[primitive recursive function]]s, defined for sets or ordinals rather than natural ~~numbers~~. They were introduced by {{harvtxt\|Jensen\|Karp\|1971}}.

	==Definition==		==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:		A primitive recursive set function is a [[Function (mathematics)\|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:		The basic functions are:
	*Projection: ''P''<sub>''n'',''m''</sub>(''x''<sub>1</sub>,...,''x''<sub>''n''</sub>) = ''x''<sub>''m''</sub>		*Projection: ''P''<sub>''n'',''m''{{space\|hair}}</sub>(''x''<sub>1</sub>, ..., ''x''<sub>''n''</sub>) = ''x''<sub>''m''</sub> for 0 ≤ ''m'' ≤ ''n''
	*Zero: ''F''(''x'') = 0		*Zero: ''F''(''x'') = 0
	*[[Axiom of adjunction\|Adjoining an element to a set]]: ''F''(''x'',''y'') = ''x'' ∪ {''y''}		*[[Axiom of adjunction\|Adjoining an element to a set]]: ''F''(''x'', ''y'') = ''x'' ∪ {''y''}
	*Testing membership: ''C''(''x'',''y'',''u'',''v'') = ''x'' if ''u'' ∈ ''v'', ''y'' otherwise.		*Testing [[Element (mathematics)\|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		The rules for generating new functions by substitution are
	*''F''('''x''','''y''') = ''G''('''x''',''H''('''x'''),'''y''')		*''F''('''x''', '''y''') = ''G''('''x''', ''H''('''x'''), '''y''')
	*''F''('''x''','''y''') = ''G''(''H''('''x'''),'''y''')		*''F''('''x''', '''y''') = ''G''(''H''('''x'''), '''y''')
	where '''x''' and '''y''' are finite sequences of variables.		where '''x''' and '''y''' are finite sequences of variables.

	The rule for generating new functions by recursion is		The rule for generating new functions by recursion is
	*''F''(''z'','''x''') = ''G''(∪<sub>''u''∈''z''</sub>''F''(''u'','''x'''),''z'','''x''')		*''F''(''z'', '''x''') = ''G''(∪<sub>''u''{{space\|hair}}∈{{space\|hair}}''z''</sub> ''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.		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 ordinal\|successor]] of ''x''). The primitive recursive ordinal functions are the same as the primitive recursive set functions that map ordinals to ordinals.

	One can also add more initial functions to obtain a larger class of functions. For example, the ordinal function ω<sup>α</sup> 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.		One can also add more initial functions to obtain a larger [[Class (set theory)\|class]] of functions. For example, the ordinal function ω<sup>α</sup> 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.

	==References==		==References==

CitationCleanerBot: stray comma cleanup + WP:GENFIXES, replaced: publisher=Amer. Math. Soc.,| → publisher=Amer. Math. Soc.|, added underlinked tag

2019-01-11T03:03:58Z

stray comma cleanup + WP:GENFIXES, replaced: publisher=Amer. Math. Soc.,| → publisher=Amer. Math. Soc.|, added underlinked tag

← Previous revision		Revision as of 03:03, 11 January 2019
Line 1:		Line 1:
			{{Underlinked\|date=January 2019}}

	In mathematics, '''primitive recursive set functions''' or '''primitive recursive ordinal functions''' are analogs of [[primitive recursive function]]s, defined for sets or ordinals rather than natural numbers. They were introduced by {{harvtxt\|Jensen\|Karp\|1971}}.		In mathematics, '''primitive recursive set functions''' or '''primitive recursive ordinal functions''' are analogs of [[primitive recursive function]]s, defined for sets or ordinals rather than natural numbers. They were introduced by {{harvtxt\|Jensen\|Karp\|1971}}.

Line 27:		Line 29:
	*{{citation\|mr=0281602		*{{citation\|mr=0281602
	\|last=Jensen\|first= Ronald B.\|last2= Karp\|first2= Carol		\|last=Jensen\|first= Ronald B.\|last2= Karp\|first2= Carol
	\|chapter=Primitive recursive set functions\|year= 1971 \|title=Axiomatic Set Theory \|series=Proc. Sympos. Pure Math.\|volume= XIII, Part I\|pages= 143–176 \|publisher=Amer. Math. Soc.,\|place= Providence, R.I.\|isbn=9780821802458}}		\|chapter=Primitive recursive set functions\|year= 1971 \|title=Axiomatic Set Theory \|series=Proc. Sympos. Pure Math.\|volume= XIII, Part I\|pages= 143–176 \|publisher=Amer. Math. Soc.\|place= Providence, R.I.\|isbn=9780821802458}}

	[[Category:Computability theory]]		[[Category:Computability theory]]

R.e.b.: Adding/removing wikilink(s)

2014-08-13T16:29:25Z

Adding/removing wikilink(s)

← Previous revision		Revision as of 16:29, 13 August 2014
Line 1:		Line 1:
	{{Underlinked\|date=July 2014}}

	In mathematics, '''primitive recursive set functions''' or '''primitive recursive ordinal functions''' are analogs of [[primitive recursive function]]s, defined for sets or ordinals rather than natural numbers. They were introduced by {{harvtxt\|Jensen\|Karp\|1971}}.		In mathematics, '''primitive recursive set functions''' or '''primitive recursive ordinal functions''' are analogs of [[primitive recursive function]]s, defined for sets or ordinals rather than natural numbers. They were introduced by {{harvtxt\|Jensen\|Karp\|1971}}.

Line 10:		Line 8:
	*Projection: ''P''<sub>''n'',''m''</sub>(''x''<sub>1</sub>,...,''x''<sub>''n''</sub>) = ''x''<sub>''m''</sub>		*Projection: ''P''<sub>''n'',''m''</sub>(''x''<sub>1</sub>,...,''x''<sub>''n''</sub>) = ''x''<sub>''m''</sub>
	*Zero: ''F''(''x'') = 0		*Zero: ''F''(''x'') = 0
	*~~Adding~~ an element to a set: ''F''(''x'',''y'') = ''x'' ∪ {''y''}		*[[Axiom of adjunction\|Adjoining an element to a set]]: ''F''(''x'',''y'') = ''x'' ∪ {''y''}
	*Testing membership: ''C''(''x'',''y'',''u'',''v'') = ''x'' if ''u'' ∈ ''v'', ''y'' otherwise.		*Testing membership: ''C''(''x'',''y'',''u'',''v'') = ''x'' if ''u'' ∈ ''v'', ''y'' otherwise.

Michael Hardy: /* Definition */

2014-07-21T12:24:36Z

Definition

← Previous revision		Revision as of 12:24, 21 July 2014
Line 9:		Line 9:
	The basic functions are:		The basic functions are:
	*Projection: ''P''<sub>''n'',''m''</sub>(''x''<sub>1</sub>,...,''x''<sub>''n''</sub>) = ''x''<sub>''m''</sub>		*Projection: ''P''<sub>''n'',''m''</sub>(''x''<sub>1</sub>,...,''x''<sub>''n''</sub>) = ''x''<sub>''m''</sub>
	*Zero: ''F''(''x'')=0		*Zero: ''F''(''x'') = 0
	*Adding an element to a set: ''F''(''x'',''y'') = ''x''∪{''y''}		*Adding an element to a set: ''F''(''x'',''y'') = ''x'' ∪ {''y''}
	*Testing membership: ''C''(''x'',''y'',''u'',''v'') = ''x'' if ''u''∈''v'', ''y'' otherwise.		*Testing membership: ''C''(''x'',''y'',''u'',''v'') = ''x'' if ''u'' ∈ ''v'', ''y'' otherwise.

	The rules for generating new functions by substitution are		The rules for generating new functions by substitution are

JRSpriggs: /* Definition */ change italic to bold for a sequence of variables

2014-07-19T06:31:49Z

Definition: change italic to bold for a sequence of variables

← Previous revision		Revision as of 06:31, 19 July 2014
Line 14:		Line 14:

	The rules for generating new functions by substitution are		The rules for generating new functions by substitution are
	*''F''('''x''','''y''') = ''G''(''x'',''H''('''x'''),'''y''')		*''F''('''x''','''y''') = ''G''('''x''',''H''('''x'''),'''y''')
	*''F''('''x''','''y''') = ''G''(''H''('''x'''),'''y''')		*''F''('''x''','''y''') = ''G''(''H''('''x'''),'''y''')
	where '''x''' and '''y''' are finite sequences of variables.		where '''x''' and '''y''' are finite sequences of variables.

Solarra: various clean up and reference fixes, added underlinked tag using AWB

2014-07-19T04:28:19Z

various clean up and reference fixes, added underlinked tag using AWB

← Previous revision		Revision as of 04:28, 19 July 2014
Line 1:		Line 1:
			{{Underlinked\|date=July 2014}}

	In mathematics, '''primitive recursive set functions''' or '''primitive recursive ordinal functions''' are analogs of [[primitive recursive function]]s, defined for sets or ordinals rather than natural numbers. They were introduced by {{harvtxt\|Jensen\|Karp\|1971}}.		In mathematics, '''primitive recursive set functions''' or '''primitive recursive ordinal functions''' are analogs of [[primitive recursive function]]s, defined for sets or ordinals rather than natural numbers. They were introduced by {{harvtxt\|Jensen\|Karp\|1971}}.

Line 19:		Line 21:
	*''F''(''z'','''x''') = ''G''(∪<sub>''u''∈''z''</sub>''F''(''u'','''x'''),''z'','''x''')		*''F''(''z'','''x''') = ''G''(∪<sub>''u''∈''z''</sub>''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.		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.

	One can also add more initial functions to obtain a larger class of functions. For example, the ordinal function ω<sup>α</sup> 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.		One can also add more initial functions to obtain a larger class of functions. For example, the ordinal function ω<sup>α</sup> 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.
Line 28:		Line 30:
	\|last=Jensen\|first= Ronald B.\|last2= Karp\|first2= Carol		\|last=Jensen\|first= Ronald B.\|last2= Karp\|first2= Carol
	\|chapter=Primitive recursive set functions\|year= 1971 \|title=Axiomatic Set Theory \|series=Proc. Sympos. Pure Math.\|volume= XIII, Part I\|pages= 143–176 \|publisher=Amer. Math. Soc.,\|place= Providence, R.I.\|isbn=9780821802458}}		\|chapter=Primitive recursive set functions\|year= 1971 \|title=Axiomatic Set Theory \|series=Proc. Sympos. Pure Math.\|volume= XIII, Part I\|pages= 143–176 \|publisher=Amer. Math. Soc.,\|place= Providence, R.I.\|isbn=9780821802458}}


	[[Category:Computability theory]]		[[Category:Computability theory]]
	[[Category:Theory of computation]]		[[Category:Theory of computation]]