دالة المجموعة التكرارية الأولية

في الرياضيات ، تُعدّ الدوال التكرارية الأولية للمجموعات أو الدوال التكرارية الأولية للترتيب نظائر للدوال التكرارية الأولية ، وهي مُعرّفة للمجموعات أو الترتيبات بدلاً من الأعداد الطبيعية . وقد قدّمها جنسن وكارب (1971) .

دالة المجموعة التكرارية الأولية هي دالة من مجموعات إلى مجموعات يمكن الحصول عليها من الدوال الأساسية التالية عن طريق تطبيق قواعد الاستبدال والتكرار التالية بشكل متكرر:

الوظائف الأساسية هي:

• الإسقاط: P _{n , m} ( x ₁ , ..., x _n ) = x _m لـ 0 ≤ m ≤ n
• الصفر: F ( x ) = 0
• إلحاق عنصر بمجموعة : F ( x , y ) = x ∪ { y }
• اختبار العضوية : C ( x , y , u , v ) = x إذا كان u ∈ v ، و C ( x , y , u , v ) = y خلاف ذلك.

قواعد توليد الدوال الجديدة عن طريق الاستبدال هي

• F ( x , y ) = G ( x , H ( x ), y )
• F ( x , y ) = G ( H ( x ), y )

حيث x و y عبارة عن متواليات محدودة من المتغيرات.

قاعدة توليد الدوال الجديدة عن طريق الاستدعاء الذاتي هي

• F ( z , x ) = G (∪ _{u ∈ z} F ( u , x ), z , x )

تُعرَّف الدالة الترتيبية التكرارية الأولية بنفس الطريقة، باستثناء استبدال الدالة الأولية F ( x , y ) = x ∪ { y } بالدالة F ( x ) = x ∪ { x } (الدالة اللاحقة لـ x ). وتُعدّ الدوال الترتيبية التكرارية الأولية مماثلةً للدوال الترتيبية التكرارية الأولية التي تربط الأعداد الترتيبية ببعضها.

أمثلة على دوال المجموعات التكرارية الأولية:

• TC ، الدالة التي تُسند إلى مجموعة ما إغلاقها المتعدي. ^{[ 1 ] : 26}
• بالنظر إلى محدودية وراثية${\displaystyle c}$، الدالة الثابتة${\displaystyle f(x)=c}$[ ^{1 ] : 28​}

يمكن أيضًا إضافة المزيد من الدوال الأولية للحصول على فئة أكبر من الدوال. على سبيل المثال، الدالة الترتيبية${\displaystyle \alpha \mapsto \أوميغا ^{\alpha }}$ليست دالة تكرارية بدائية، لأن الدالة الثابتة ذات القيمة ω (أو أي مجموعة لانهائية أخرى ) ليست دالة تكرارية بدائية، لذلك قد يرغب المرء في إضافة هذه الدالة الثابتة إلى الدوال الأولية.

إن مفهوم كون دالة المجموعة بدائية تكرارية في ω له نفس تعريف التكرار البدائي، باستثناء أن ω كمعامل يتم تثبيته، ولا يتم تغييره بواسطة مخططات التكرار البدائي.

أمثلة على الدوال البدائية التكرارية في ω: ^{[ 1 ] ص 28-29}

• ${\displaystyle \mathbb {P} _{\omega }(x)=\bigcup _{n<\omega }x^{n}}$.
• الدالة التي تُسند إلى${\displaystyle \alpha }$ال${\displaystyle \alpha }$المستوى th${\displaystyle L_{\alpha }}$من التسلسل الهرمي القابل للبناء عند غودل .

يترك${\displaystyle f_{0}:{\textrm {Ord}}^{2}\to {\textrm {Ord}}}$كن الوظيفة${\displaystyle f(\alpha ,\beta )=\alpha +\beta }$ولجميع${\displaystyle i<\omega }$،${\displaystyle {\tilde {f}}_{i}(\alpha )=f_{i}(\alpha ,\alpha )}$و${\displaystyle f_{i+1}(\alpha ,\beta )=({\tilde {f}}_{i})^{\beta }(\alpha )}$لنفترض أن Lα _تُمثل المرحلة α من كون غودل القابل للبناء . تكون Lα _مغلقة تحت دوال المجموعات التكرارية الأولية إذا وفقط إذا كانت α مغلقة تحت كل منها.${\displaystyle f_{i}}$للجميع${\displaystyle i<\omega }$[ ^{1 ] : 31​}

• جنسن، رونالد ب .؛ كارب، كارول (1971)، "دوال المجموعات البدائية المتكررة"، نظرية المجموعات البديهية ، وقائع ندوة الرياضيات البحتة، المجلد  الثالث عشر، الجزء الأول، بروفيدنس، رود آيلاند: الجمعية الأمريكية للرياضيات، الصفحات 143-176 ، ISBN  9780821802458، MR 0281602