عدد ترتيبي كبير قابل للعد

الأعداد الترتيبية القابلة للحساب (أو الأعداد الترتيبية الاسترجاعية) هي أعداد ترتيبية معينة قابلة للعد: بتعبير أدق، تلك التي تمثلها دالة قابلة للحساب . توجد عدة تعريفات مكافئة لهذا المفهوم: أبسطها هو القول بأن العدد الترتيبي القابل للحساب هو نوع ترتيب ترتيب استرجاعي (أي قابل للحساب) جيد للأعداد الطبيعية ؛ لذا، بشكل أساسي، يكون العدد الترتيبي استرجاعيًا عندما يمكننا عرض مجموعة الأعداد الترتيبية الأصغر بطريقة تمكن الحاسوب ( آلة تورينج ، على سبيل المثال) من معالجتها (وبشكل أساسي، مقارنتها).

يستخدم تعريف مختلف نظام كلين للترميز الترتيبي . باختصار، الترميز الترتيبي هو إما الاسم صفر (الذي يصف الترتيب 0)، أو العدد التالي لترميز ترتيبي (الذي يصف العدد التالي للترتيب الذي يصفه ذلك الترميز)، أو آلة تورينج (دالة قابلة للحساب) تُنتج سلسلة متزايدة من الترميزات الترتيبية (التي تصف الترتيب الذي يمثل نهاية السلسلة). وتُرتب الترميزات الترتيبية (جزئيًا) بحيث يكون العدد التالي لـ صفر أكبر من صفر، وتكون النهاية أكبر من أي حد في السلسلة (هذا الترتيب قابل للحساب؛ ومع ذلك، فإن مجموعة الترميزات الترتيبية O نفسها غير تكرارية إلى حد كبير، نظرًا لاستحالة تحديد ما إذا كانت آلة تورينج معينة تُنتج بالفعل سلسلة من الترميزات). الترتيب التكراري هو ترتيب موصوف بواسطة ترميز ترتيبي ما.

أي عدد ترتيبي أصغر من عدد ترتيبي متكرر هو نفسه متكرر، لذلك فإن مجموعة جميع الأعداد الترتيبية المتكررة تشكل عددًا ترتيبيًا معينًا (قابلًا للعد)، وهو عدد ترتيبي Church-Kleene (انظر أدناه).

قد يميل المرء إلى تجاهل رموز الأعداد الترتيبية، والاكتفاء بالحديث عن الأعداد الترتيبية التكرارية نفسها؛ وقد وردت بعض التصريحات حول الأعداد الترتيبية التكرارية التي تتعلق في الواقع برموز هذه الأعداد. إلا أن هذا الأمر يُفضي إلى صعوبات، إذ أن حتى أصغر عدد ترتيبي لانهائي، وهو ω، له رموز عديدة، بعضها لا يمكن إثبات تكافؤه مع الرمز الواضح (أبسط برنامج يُحصي جميع الأعداد الطبيعية).

هناك علاقة بين الأعداد الترتيبية القابلة للحساب وبعض الأنظمة الرسمية (التي تحتوي على الحساب ، أي جزء معقول على الأقل من حساب بيانو ).

بعض الأعداد الترتيبية القابلة للحساب كبيرة جدًا لدرجة أنه على الرغم من إمكانية إعطائها بواسطة رمز ترتيبي معين o ، إلا أن نظامًا رسميًا معينًا قد لا يكون قويًا بما يكفي لإظهار أن o هو في الواقع رمز ترتيبي: فالنظام لا يُظهر الاستقراء المتسامي لمثل هذه الأعداد الترتيبية الكبيرة.

على سبيل المثال، لا تُثبت بديهيات بيانو المعتادة من الرتبة الأولى الاستقراء المتسامي لـ ε₀ (أو ما بعدها ₎ : فبينما يُمكن وصف العدد الترتيبي _ε₀ حسابيًا بسهولة (فهو قابل للعد)، فإن بديهيات بيانو ليست قوية بما يكفي لإثبات أنه عدد ترتيبي بالفعل؛ في الواقع، يُثبت الاستقراء المتسامي على ε₀ _اتساق بديهيات بيانو (وهي نظرية لجينتزن )، لذا، وفقًا لنظرية عدم الاكتمال الثانية لغودل ، لا يُمكن لبديهيات بيانو صياغة هذا الاستدلال رسميًا. (هذا هو أساس نظرية كيربي-باريس حول متتاليات غودشتاين ). بما أن حساب بيانو يُمكنه إثبات أن أي عدد ترتيبي أقل من ε₀ _مُرتب ترتيبًا جيدًا، نقول إن ε₀ _يقيس قوة بديهيات بيانو من الناحية البرهانية.

لكن يمكننا فعل ذلك لأنظمة تتجاوز بكثير بديهيات بيانو. على سبيل المثال، تكمن قوة نظرية المجموعات لكريبك-بلاتيك من الناحية البرهانية في الترتيب الترتيبي لباخمان-هوارد ، وفي الواقع، يكفي إضافة البديهيات التي تنص على الترتيب الجيد لجميع الأعداد الترتيبية الأدنى من الترتيب الترتيبي لباخمان-هوارد إلى بديهيات بيانو للحصول على جميع النتائج الحسابية لنظرية المجموعات لكريبك-بلاتيك.

لقد ذكرنا سابقًا (انظر الشكل الطبيعي لكانتور ) الترتيب ε ₀ ، وهو أصغر قيمة تحقق المعادلة${\displaystyle \omega ^{\alpha }=\alpha }$إذن، فهي نهاية المتتالية 0، 1،${\displaystyle \omega }$،${\displaystyle \أوميغا ^{\أوميغا }}$،${\displaystyle \أوميغا ^{\أوميغا ^{\أوميغا }}}$... يُطلق على العدد الترتيبي التالي الذي يحقق هذه المعادلة اسم ε ₁ : وهو نهاية المتتالية

${\displaystyle \varepsilon _{0}+1,\qquad \omega ^{\varepsilon _{0}+1}=\varepsilon _{0}\cdot \omega ,\qquad \omega ^{\omega ^{\varepsilon _{0}+1}}=(\varepsilon _{0})^{\omega },\qquad {\text{إلخ.}}}$

وبشكل عام، فإن${\displaystyle \iota }$الترتيبية رقم - بحيث${\displaystyle \omega ^{\alpha }=\alpha }$يُطلق عليه اسم${\displaystyle \varepsilon _{\iota }}$يمكننا تعريف${\displaystyle \zeta _{0}}$باعتباره أصغر عدد ترتيبي بحيث${\displaystyle \varepsilon _{\alpha }=\alpha }$ولكن بما أن الأبجدية اليونانية لا تحتوي على عدد لا نهائي من الأحرف، فمن الأفضل استخدام تدوين أكثر قوة: تعريف الأعداد الترتيبية${\displaystyle \varphi _{\gamma }(\beta )}$بالاستقراء المتسامي كما يلي: ليكن${\displaystyle \varphi _{0}(\beta )=\أوميغا ^{\beta }}$ودع${\displaystyle \varphi _{\gamma +1}(\beta )}$كن${\displaystyle \beta }$النقطة الثابتة رقم -th من${\displaystyle \varphi _{\gamma }}$(أي،${\displaystyle \beta }$الترتيبية رقم - بحيث${\displaystyle \varphi _{\gamma }(\alpha )=\alpha }$فعلى سبيل المثال،${\displaystyle \varphi _{1}(\beta )=\varepsilon _{\beta }}$), ومتى${\displaystyle \delta }$هو عدد ترتيبي محدود، عرّفه${\displaystyle \varphi _{\delta }(\alpha )}$كما هو الحال${\displaystyle \alpha }$النقطة الثابتة المشتركة رقم -th لـ${\displaystyle \varphi _{\gamma }}$للجميع${\displaystyle \gamma <\delta }$تُعرف هذه المجموعة من الدوال باسم التسلسل الهرمي لفبلين (توجد اختلافات غير جوهرية في التعريف، مثل السماح بـ، لـ${\displaystyle \delta }$ترتيب حدي،${\displaystyle \varphi _{\delta }(\alpha )}$كن الحد الأقصى لـ${\displaystyle \varphi _{\gamma }(\alpha )}$ل${\displaystyle \gamma <\delta }$: هذا ببساطة يقوم فقط بتغيير المؤشرات بمقدار 1، وهو أمر غير ضار).${\displaystyle \varphi _{\gamma }}$يُطلق عليه اسم${\displaystyle \gamma ^{th}}$دالة فيبلن (إلى الأساس)${\displaystyle \omega }$).

الطلب:${\displaystyle \varphi _{\alpha }(\beta )<\varphi _{\gamma }(\delta )}$إذا وفقط إذا كان أحد (${\displaystyle \alpha =\gamma }$و${\displaystyle \beta <\delta }$) أو (${\displaystyle \alpha <\gamma }$و${\displaystyle \beta <\varphi _{\gamma }(\delta )}$) أو (${\displaystyle \alpha >\gamma }$و${\displaystyle \varphi _{\alpha }(\beta )<\delta }$).

أصغر عدد ترتيبي بحيث${\displaystyle \varphi _{\alpha }(0)=\alpha }$يُعرف باسم الترتيب فيفرمان-شوت ، ويكتب عمومًا${\displaystyle \Gamma _{0}}$يمكن وصفها بأنها مجموعة جميع الأعداد الترتيبية التي يمكن كتابتها كتعبيرات منتهية، بدءًا من الصفر، باستخدام التسلسل الهرمي لفبلين والجمع فقط. يكتسب عدد فيفرمان-شوت الترتيبي أهمية بالغة لأنه، بمعنى يصعب تحديده بدقة، هو أصغر عدد ترتيبي (غير منتهٍ) لا يمكن وصفه ( بشكل تنبؤي ) باستخدام أعداد ترتيبية أصغر. وهو يقيس قوة أنظمة مثل " الاستدعاء الذاتي الحسابي المتسامي ".

وبشكل أكثر عمومية، فإن Γ _α يعدد الأعداد الترتيبية التي لا يمكن الحصول عليها من الأعداد الترتيبية الأصغر باستخدام الجمع ووظائف فيبلن.

من الممكن، بالطبع، وصف الأعداد الترتيبية بما يتجاوز ترتيب فيفرمان-شوت. ويمكن للمرء أن يستمر في البحث عن النقاط الثابتة بطريقة أكثر تعقيدًا: حصر النقاط الثابتة لـ${\displaystyle \alpha \mapsto \Gamma _{\alpha }}$ثمّ نحصي النقاط الثابتة لذلك ، وهكذا، ثمّ نبحث عن الترتيب الأول α الذي يُحصل عليه في α خطوة من هذه العملية، ونستمر في التقطير بهذه الطريقة المخصصة . وهذا يؤدي إلى تعريف ترتيبات فيبلن " الصغيرة " و" الكبيرة ".

لتجاوز نظام فيفرمان-شوت الترتيبي، يلزم استحداث أساليب جديدة. لسوء الحظ، لا توجد حتى الآن طريقة موحدة للقيام بذلك: يبدو أن كل مؤلف في هذا المجال قد ابتكر نظامه الخاص في الترميز، ومن الصعب للغاية الترجمة بين الأنظمة المختلفة. قدّم باخمان أول نظام من هذا القبيل عام ١٩٥٠ (بطريقة غير رسمية )، ووصف كل من بوخهولز، وتاكيوتي (مخططات الترتيب)، وفيفرمان (أنظمة θ)، وأكسيل ، وبريدج، وشوت ، وبولرز امتدادات وتنوعات مختلفة له. مع ذلك، تستخدم معظم الأنظمة الفكرة الأساسية نفسها، وهي بناء ترتيبات جديدة قابلة للعد باستخدام وجود ترتيبات معينة غير قابلة للعد. إليكم مثال على هذا التعريف، الموصوف بتفصيل أكبر في مقالة دالة اختزال الترتيب :

• يتم تعريف ψ( α ) على أنه أصغر عدد ترتيبي لا يمكن إنشاؤه بالبدء من 0 و1 وω وΩ، وتطبيق الجمع والضرب والأس بشكل متكرر، وψ على الأعداد الترتيبية التي تم إنشاؤها مسبقًا (باستثناء أنه لا يمكن تطبيق ψ إلا على الوسائط الأقل من α ، لضمان تعريفها بشكل جيد).

هنا، Ω = ω₁ _هو أول عدد ترتيبي غير قابل للعد. أُدرج هذا العدد لأنه بدونه، ستتوقف الدالة ψ عند أصغر عدد ترتيبي σ بحيث يكون _εσ = σ : على وجه الخصوص، ψ( α ) = σ لأي عدد ترتيبي α يحقق σ ≤ α ≤ Ω. مع ذلك، فإن تضميننا لـ Ω يسمح لنا بتجاوز هذه النقطة: ψ(Ω+1) أكبر من σ . الخاصية الأساسية لـ Ω التي استخدمناها هي أنها أكبر من أي عدد ترتيبي تنتجه ψ.

لإنشاء أعداد ترتيبية أكبر، يمكننا توسيع تعريف ψ بإضافة المزيد من طرق إنشاء الأعداد الترتيبية غير القابلة للعد. توجد عدة طرق للقيام بذلك، وقد وُصفت إلى حد ما في مقالة دالة دمج الأعداد الترتيبية .

يُعدّ الترتيب الباخماني -هوارد (ويُسمى أحيانًا الترتيب الهواردي، ψ₀ ₍ εΩ ₊₁ ) وفقًا للرمز المذكور أعلاه) ترتيبًا مهمًا، لأنه يصف قوة نظرية المجموعات كريپكي-بلاتيك من الناحية البرهانية . في الواقع، تكمن الأهمية الرئيسية لهذه الترتيبات الكبيرة، والسبب وراء وصفها، في علاقتها ببعض الأنظمة الصورية كما هو موضح سابقًا. مع ذلك، تبدو أنظمة صورية قوية كحساب الرتبة الثانية الكامل ، فضلًا عن نظرية مجموعات زيرميلو-فرانكل ، بعيدة المنال في الوقت الراهن.

إلى جانب ذلك، توجد عدة أعداد ترتيبية متكررة ليست معروفة جيدًا مثل الأعداد السابقة. أولها هو عدد بوخهولز الترتيبي ، والذي يُعرَّف على النحو التالي:${\displaystyle \psi _{0}(\Omega _{\omega })}$، مختصرة إلى فقط${\displaystyle \psi (\Omega _{\omega })}$باستخدام الترميز السابق. وهو الترتيب البرهاني لـ${\displaystyle \Pi _{1}^{1}-CA_{0}}$[ ^{1 ]} نظرية حسابية من الدرجة الأولى تسمح بالتكميم على الأعداد الطبيعية وكذلك مجموعات الأعداد الطبيعية، ^و${\displaystyle ID_{<\omega }}$، "النظرية الرسمية للتعريفات الاستقرائية المتكررة بشكل محدود". ^{[ 2 ]}

بما أن الهيدرا من لعبة الهيدرا لبوخهولز متماثلة مع ترميز بوخهولز الترتيبي، فإنه يمكن التعبير عن الأعداد الترتيبية حتى هذه النقطة باستخدام الهيدرا من اللعبة. ^{[ 3 ] ص 136} على سبيل المثال${\displaystyle +(0(\omega ))}$يتوافق مع${\displaystyle \psi (\Omega _{\omega })}$.

يلي ذلك الترتيب الترتيبي لتاكيوتي-فيفيرمان-بوخهولز ، وهو الترتيب الترتيبي لنظرية البرهان لـ${\displaystyle \Pi _{1}^{1}-CA+BI}$; ^{[ 4 ]} ونظام فرعي آخر من الحساب من الدرجة الثانية:${\displaystyle \Pi _{1}^{1}}$- الفهم + الاستقراء المتسامي، و${\displaystyle ID_{\omega }}$، "النظرية الرسمية لـ${\displaystyle \omega }$^{[ 5 ]} في هذه الصيغة، يُعرَّف على النحو التالي: "تعريفات استقرائية متكررة مرات". [5]${\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})}$وهي القيمة العليا لمدى دوال بسي لبوخولز. ^{[ 6 ]} وقد أطلق عليها ديفيد مادور هذا الاسم لأول مرة.

يُذكر الترتيب التالي في جزء من التعليمات البرمجية التي تصف الترتيبات والأعداد الكبيرة القابلة للعد في لغة Agda ، وقد عرّفه "AndrasKovacs" على النحو التالي:${\displaystyle \psi _{0}(\Omega _{\omega +1}\cdot \varepsilon _{0})}$.

تم ذكر الترتيب التالي في نفس جزء الكود المذكور سابقًا، وتم تعريفه على النحو التالي:${\displaystyle \psi _{0}(\Omega _{\omega ^{\omega }})}$. إنه الترتيب البرهاني لـ${\displaystyle ID_{<\أوميغا ^{\أوميغا }}}$.

وقد ذُكر هذا الترتيب التالي مرة أخرى في نفس جزء الكود، وتم تعريفه على النحو التالي:${\displaystyle \psi _{0}(\Omega _{\varepsilon _{0}})}$، هو الترتيب البرهاني لـ${\displaystyle ID_{<\varepsilon _{0}}}$بشكل عام، الترتيب البرهاني لـ${\displaystyle ID_{<\nu }}$يساوي${\displaystyle \psi _{0}(\Omega _{\nu })}$— لاحظ أنه في هذه الحالة المحددة،${\displaystyle \Omega _{0}}$يمثل${\displaystyle 1}$، أول عدد ترتيبي غير صفري.

يلي ذلك عدد ترتيبي غير مسمى، أشار إليه ديفيد مادور باسم الانهيار "القابل للعد" لـ${\displaystyle \varepsilon _{I+1}}$، ^{[ 5 ]} حيث${\displaystyle I}$هو أول غير قابل للوصول (=${\displaystyle \Pi _{0}^{1}}$عدد أصلي (لا يوصف). هذا هو العدد الترتيبي لنظرية مجموعات كريپكي-بلاتيك المُعزز بعدم إمكانية الوصول التكراري لفئة الأعداد الترتيبية (KPi)، أو، من الناحية الحسابية، لـ${\displaystyle \Delta _{2}^{1}}$الفهم + الاستقراء المتسامي. قيمته تساوي${\displaystyle \psi (\varepsilon _{I+1})}$باستخدام دالة غير معروفة.

ثم يأتي ترتيب آخر لم يُسمَّ، أشار إليه ديفيد مادور باسم الانهيار "القابل للعد" لـ${\displaystyle \varepsilon _{M+1}}$، ^{[ 5 ]} حيث${\displaystyle M}$هو أول عدد أصلي من نوع ماهلو . وهو العدد الترتيبي لنظرية البرهان في KPM، وهو امتداد لنظرية مجموعات كريپكي-بلاتيك القائمة على عدد أصلي من نوع ماهلو. ^{[ 7 ]} وقيمته تساوي${\displaystyle \psi (\varepsilon _{M+1})}$باستخدام إحدى دوال بوخهولز المختلفة لـ psi. ^{[ 8 ]}

ثم يأتي ترتيب آخر لم يُسمَّ، أشار إليه ديفيد مادور باسم الانهيار "القابل للعد" لـ${\displaystyle \varepsilon _{K+1}}$، ^{[ 5 ]} حيث${\displaystyle K}$هي أول مجموعة ضعيفة التراص (=${\displaystyle \Pi _{1}^{1}}$عدد أصلي لا يوصف. هذا هو العدد الترتيبي لنظرية مجموعات كريپكي-بلاتيك + Π3 - مرجع. قيمته تساوي${\displaystyle \Psi (\varepsilon _{K+1})}$باستخدام دالة بسي لراثجين. ^{[ 9 ]}

ثم يأتي ترتيب آخر لم يُسمَّ، أشار إليه ديفيد مادور باسم الانهيار "القابل للعد" لـ${\displaystyle \varepsilon _{\Xi +1}}$، ^{[ 5 ]} حيث${\displaystyle \Xi }$هو الأول${\displaystyle \Pi _{0}^{2}}$عدد أصلي لا يوصف. هذا هو العدد الترتيبي لنظرية مجموعات كريپكي-بلاتيك + Πω-Ref. قيمته تساوي${\displaystyle \Psi _{X}^{\varepsilon _{\Xi +1}}}$باستخدام دالة بسي لستيجرت، حيث${\displaystyle X}$= (${\displaystyle \omega ^{+}}$؛${\displaystyle P_{0}}$؛${\displaystyle \epsilon }$،${\displaystyle \epsilon }$0, ). ^{[ 10 ]}

يلي ذلك العدد الترتيبي الأخير غير المسمى، والذي أشار إليه ديفيد مادور باسم العدد الترتيبي لنظرية البرهان للاستقرار. ^{[ 5 ]} هذا هو العدد الترتيبي لنظرية البرهان للاستقرار، وهو امتداد لنظرية مجموعات كريپكي-بلاتيك. قيمته تساوي${\displaystyle \Psi _{X}^{\varepsilon _{\Upsilon +1}}}$باستخدام دالة بسي لستيجرت، حيث${\displaystyle X}$= (${\displaystyle \omega ^{+}}$؛${\displaystyle P_{0}}$؛${\displaystyle \epsilon }$،${\displaystyle \epsilon }$0, ). ^{[ 10 ]}

يلي ذلك مجموعة من الأعداد الترتيبية التي لا يُعرف عنها الكثير، ولكنها لا تزال ذات أهمية كبيرة (بالترتيب التصاعدي):

• الترتيب البرهاني للحساب من الدرجة الثانية .
• حدٌّ محتملٌ لترميز تارانوفسكي الترتيبي C. (تخميني، بافتراض صحة نظام الترميز)
• الترتيب الإثباتي لـ ZFC .

بإسقاط شرط وجود وصف ملموس، يمكن الحصول على أعداد ترتيبية قابلة للعد بشكل متكرر أكبر، باعتبارها أعدادًا ترتيبية تقيس قوة النظريات القوية المختلفة؛ وبشكل عام، تُعد هذه الأعداد الترتيبية أصغر أنواع الترتيبات "الطبيعية" التي لا تستطيع النظريات إثبات أنها مرتبة ترتيبًا جيدًا. وبأخذ نظريات أقوى فأقوى، مثل الحساب من الرتبة الثانية ، ونظرية زيرميلو للمجموعات ، ونظرية زيرميلو-فرانكل للمجموعات ، أو نظرية زيرميلو-فرانكل للمجموعات مع بديهيات عددية كبيرة مختلفة ، نحصل على بعض الأعداد الترتيبية المتكررة الضخمة للغاية. (بالمعنى الدقيق، ليس من المؤكد أن جميع هذه الأعداد ترتيبية بالفعل: فبحسب التصميم، لا يمكن إثبات أن قوة نظرية ما ترتيبية إلا من خلال نظرية أقوى منها. لذا، يصبح الأمر غير واضح تمامًا بالنسبة للبديهيات العددية الكبيرة).

الحد الأعلى لمجموعة الأعداد الترتيبية المتكررة هو أصغر عدد ترتيبي لا يمكن وصفه بطريقة تكرارية. (وهو ليس نوع الترتيب لأي ترتيب جيد تكراري للأعداد الصحيحة). هذا العدد الترتيبي هو عدد ترتيبي قابل للعد يسمى عدد تشيرش-كلين الترتيبي .${\displaystyle \omega _{1}^{\mathrm {CK} }}$. هكذا،${\displaystyle \omega _{1}^{\mathrm {CK} }}$هو أصغر عدد ترتيبي غير متكرر، ولا أمل في "وصف" أي عدد ترتيبي بدقة من هذه النقطة فصاعدًا - لا يمكننا إلا تعريفها . ولكنه لا يزال أصغر بكثير من أول عدد ترتيبي غير معدود.${\displaystyle \omega _{1}}$ومع ذلك، وكما يوحي رمزها، فإنها تتصرف بطرق عديدة تشبه إلى حد كبير${\displaystyle \omega _{1}}$على سبيل المثال، يمكن تعريف دوال التجميع الترتيبي باستخدام${\displaystyle \omega _{1}^{\mathrm {CK} }}$بدلاً من${\displaystyle \omega _{1}}$.

يرتبط الترتيب التشرشي-كلين مرة أخرى بنظرية مجموعات كريپكي-بلاتيك ، ولكن بطريقة مختلفة: فبينما كان الترتيب الباخمان-هوارد (الموصوف أعلاه ) هو أصغر ترتيب لا تثبت نظرية كريپكي-بلاتيك الاستقراء المتسامي له، فإن الترتيب التشرشي-كلين هو أصغر قيمة α بحيث يؤدي بناء كون غودل ، L ، حتى المرحلة α ، إلى نموذج${\displaystyle L_{\alpha }}$من KP. تُسمى هذه الأعداد الترتيبية بالأعداد المقبولة ، وبالتالي${\displaystyle \omega _{1}^{\mathrm {CK} }}$هو أصغر عدد ترتيبي مقبول (بعد ω في حالة عدم تضمين بديهية اللانهاية في KP).

بحسب نظرية فريدمان ، وجينسن ، وساكس ، فإن الأعداد الترتيبية المقبولة القابلة للعد هي تحديدًا تلك التي تُبنى بطريقة مشابهة للعدد الترتيبي لتشرش-كلين، ولكن لآلات تورينج المزودة بأجهزة التنبؤ . ^{[ 11 ] [ 12 ]} يكتب المرء أحيانًا${\displaystyle \omega _{\alpha }^{\mathrm {CK} }}$لـ${\displaystyle \alpha }$-الترتيب الترتيبي الذي يكون إما مقبولاً أو حداً للمقبولات الأصغر.

${\displaystyle \omega _{\omega }^{\mathrm {CK} }}$هو أصغر حد للأعداد الترتيبية المقبولة (المذكورة لاحقًا)، ومع ذلك فإن العدد الترتيبي نفسه غير مقبول. وهو أيضًا أصغرها${\displaystyle \alpha }$بحيث${\displaystyle L_{\alpha }\cap P(\omega )}$هو نموذج لـ${\displaystyle \Pi _{1}^{1}}$-الفهم. ^{[ 5 ] [ 13 ]}

عدد ترتيبي يكون مقبولاً وحدوداً للمقبولات، أو ما يعادله بحيث${\displaystyle \alpha }$هو${\displaystyle \alpha }$يُطلق على العدد الترتيبي المسموح به رقم - اسم العدد غير القابل للوصول إليه بشكل متكرر ، ويمكن الإشارة إلى العدد الأقل عدم قابلية للوصول إليه بشكل متكرر بالرمز التالي:${\displaystyle \omega _{1}^{E_{1}}}$[ ^{14 ]} يُطلق على العدد الترتيبي الذي يكون غير قابل للوصول إليه بشكل متكرر، والذي يُمثل أيضًا حدًا للأعداد غير القابلة للوصول إليها بشكل متكرر، اسم ^العدد الترتيبي فائق عدم قابلية الوصول إليه بشكل متكرر . ^{[ 5 ]} توجد نظرية للأعداد الترتيبية الكبيرة بهذه الطريقة، وهي نظرية تُشابه إلى حد كبير نظرية الأعداد الأصلية الكبيرة (الصغيرة) . على سبيل المثال، يُمكننا تعريف الأعداد الترتيبية ماهلو بشكل متكرر : وهي...${\displaystyle \alpha }$بحيث يكون كل${\displaystyle \alpha }$مجموعة فرعية مغلقة غير محدودة ذات تكرار -${\displaystyle \alpha }$يحتوي على عدد ترتيبي مقبول (نظير تكراري لتعريف عدد ماهلو الأصلي ). القسم 1 من دالة هارينغتون${\displaystyle {}^{2}S^{\#}}$يساوي${\displaystyle L_{\rho }\cap {\mathcal {P}}(\omega )}$، أين${\displaystyle \rho }$هو أقل ترتيب ماهلو تكرارًا. ^{[ 15 ] ص 171}

لكن تجدر الإشارة إلى أننا ما زلنا نتحدث هنا عن الأعداد الترتيبية التي قد تكون قابلة للعد. (مع أن وجود الأعداد الأصلية غير القابلة للوصول أو أعداد ماهلو لا يمكن إثباته في نظرية زيرميلو-فرانكل للمجموعات ، فإن إثبات وجود الأعداد الترتيبية غير القابلة للوصول بشكل متكرر أو أعداد ماهلو المتكررة هو نظرية في زيرميلو-فرانكل: في الواقع، أي عدد أصلي منتظم هو عدد ماهلو متكرر وأكثر، ولكن حتى لو اقتصرنا على الأعداد الترتيبية القابلة للعد، فإن زيرميلو-فرانكل تثبت وجود أعداد ماهلو المتكررة. ومع ذلك، فهي خارج نطاق نظرية كريپكي-بلاتيك للمجموعات).

بالنسبة لمجموعة من الصيغ${\displaystyle \Gamma }$، حد ترتيبي${\displaystyle \alpha }$يُطلق عليه اسم${\displaystyle \Gamma }$- يعكس ما إذا كانت الرتبة${\displaystyle L_{\alpha }}$يحقق خاصية انعكاس معينة لكل${\displaystyle \Gamma }$-صيغة${\displaystyle \phi }$[ ^{16 ]} تظهر هذه الأعداد الترتيبية في التحليل الترتيبي لنظريات مثل KP+ Π ₃ -ref ، ^وهي نظرية تُعزز نظرية مجموعات كريپكي-بلاتيك بواسطة${\displaystyle \Pi _{3}}$مخطط الانعكاس. ويمكن اعتبارها أيضًا "نظائر تكرارية" لبعض الأعداد الأصلية غير القابلة للعد، مثل الأعداد الأصلية المدمجة بشكل ضعيف والأعداد الأصلية التي لا يمكن وصفها . ^{[ 17 ]} على سبيل المثال، عدد ترتيبي${\displaystyle \Pi _{3}}$يُطلق على المجموعة العاكسة اسم المجموعة الضعيفة المدمجة بشكل متكرر . ^{[ 18 ]} بالنسبة لـ${\displaystyle n}$الأقل${\displaystyle \Pi _{n}}$-الترتيبي العاكس هو أيضًا الحد الأعلى للترتيبيات المغلقة للتعريفات الاستقرائية الرتيبة التي تكون رسومها البيانية Π _m+1 ⁰ . ^{[ 18 ]}

بخاصة،${\displaystyle \Pi _{3}}$تتميز الأعداد الترتيبية العاكسة أيضًا بتوصيف باستخدام دوال من النوع الأعلى على الدوال الترتيبية، مما أكسبها اسم الأعداد الترتيبية المقبولة من الرتبة 2. ^{[ 18 ]} وتقدم ورقة بحثية غير منشورة لسولومون فيفرمان ، لكل مجموعة منتهية${\displaystyle n}$، خاصية مماثلة تتوافق مع${\displaystyle \Pi _{n}}$-انعكاس. ^{[ 19 ]}

ترتيب مقبول${\displaystyle \alpha }$يُطلق عليه اسم غير قابل للإسقاط إذا لم يكن هناك مجموع${\displaystyle \alpha }$- دالة حقنية متكررة${\displaystyle \alpha }$إلى عدد ترتيبي أصغر. (هذا صحيح بشكل بديهي بالنسبة للأعداد الأصلية المنتظمة؛ ومع ذلك، فإننا مهتمون بشكل أساسي بالأعداد الترتيبية القابلة للعد). يُعدّ كون العنصر غير قابل للإسقاط شرطًا أقوى بكثير من كونه مقبولًا، أو غير قابل للوصول إليه بشكل متكرر، أو حتى كونه من نوع ماهلو بشكل متكرر. ^{[ 13 ]} وفقًا لطريقة جينسن للإسقاطات، ^{[ 20 ]} فإن هذه العبارة تُكافئ العبارة القائلة بأن كون غودل ، L ، حتى المرحلة α، يُنتج نموذجًا${\displaystyle L_{\alpha }}$من KP +${\displaystyle \Sigma _{1}}$-الفصل. ومع ذلك،${\displaystyle \Sigma _{1}}$- الانفصال من تلقاء نفسه (ليس في وجود${\displaystyle V=L}$لا يُعدّ هذا مخططًا بديهيًا قويًا بما يكفي للاستدلال على عدم إمكانية الإسقاط، بل توجد في الواقع نماذج متعدية لـ${\displaystyle KP}$+${\displaystyle \Sigma _{1}}$- فصل أي ارتفاع مسموح به قابل للعد${\displaystyle >\omega }$[ ^{21 ]​}

ترتبط الأعداد الترتيبية غير القابلة للإسقاط بعمل جنسن على الإسقاطات. ^{[ 5 ] [ 22 ]} أما أصغر الأعداد الترتيبية غير القابلة للإسقاط بالنسبة لمجموعة معينة، فترتبط ببناء هارينغتون لأصغر فئة عاكسة من فئة سبيكتور 2. ^{[ 15 ] ص 174}

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

لو${\displaystyle T}$إذا كانت نظرية المجموعات قابلة للتعداد بشكل متكرر ومتوافقة مع V = L ، فإن أصغر${\displaystyle \alpha }$بحيث${\displaystyle (L_{\alpha },\in )\vDash T}$وهو أقل من الترتيب الأقل استقرارًا، وهو ما يتبعه. ^{[ 23 ]}

يمكن تعريف الأعداد الترتيبية القابلة للعد الأكبر حجمًا، والتي تسمى الأعداد الترتيبية المستقرة ، من خلال شروط عدم القابلية للوصف أو على أنها تلك${\displaystyle \alpha }$بحيث${\displaystyle L_{\alpha }}$هو نموذج فرعي أولي من النوع Σ ₁ لـ L ؛ ويمكن إثبات وجود هذه الأعداد الترتيبية في ZFC، ^{[ 24 ]} وهي ترتبط ارتباطًا وثيقًا بالأعداد الترتيبية غير القابلة للإسقاط من منظور نظرية النماذج. ^{[ 5 ] : 6} للأعداد القابلة للعد${\displaystyle \alpha }$استقرار${\displaystyle \alpha }$يعادل${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\omega _{1}}}$[ ^{5 ]​}

أقل مستوى استقرار لـ${\displaystyle L}$له بعض الخصائص المتعلقة بإمكانية التعريف. السماح${\displaystyle \sigma }$على الأقل بحيث${\displaystyle L_{\sigma }\prec _{1}L}$:

• تحتوي المجموعة على${\displaystyle \Sigma _{1}}$التعريف في${\displaystyle L}$إذا كان عضواً في${\displaystyle L_{\sigma }}$[ ^{5 ] ص. 6}
• مجموعة${\displaystyle x\subseteq \mathbb {N} }$يكون${\displaystyle \Delta _{2}^{1}}$إذا كان عضواً في${\displaystyle L_{\sigma }}$[ ^{5 ] ص. 6}
• مجموعة${\displaystyle x\subseteq \mathbb {N} }$يكون${\displaystyle \Sigma _{2}^{1}}$إذا كان${\displaystyle \sigma }$قابلة للتعداد بشكل متكرر، وفقًا لمصطلحات نظرية التكرار ألفا . ^{[ 5 ] ص 6}

• وولفرام بولرز ، نظرية البرهان ، سبرينغر 1989، رقم ISBN 0-387-51842-8(فيما يخص التسلسل الهرمي لفيبلين وبعض الأعداد الترتيبية غير التنبؤية). ربما يكون هذا الكتاب الأكثر سهولة في القراءة حول الأعداد الترتيبية المعدودة الكبيرة (وهذا لا يعني الكثير).
• غايسي تاكيوتي ، نظرية البرهان ، الطبعة الثانية 1987، رقم ISBN 0-444-10492-5(للمخططات الترتيبية)
• كورت شوتي ، نظرية الإثبات ، سبرينغر 1977 ISBN 0-387-07911-4(للتسلسل الهرمي لـ Veblen وبعض الأعداد الترتيبية غير التنبؤية)
• كريج سمورينسكي ، أنواع الخبرة الشجرية ، مجلة الرياضيات الذكية 4 (1982)، العدد 4، 182-189؛ يحتوي على وصف غير رسمي لتسلسل فيبلين الهرمي.
• هارتلي روجرز الابن ، نظرية الدوال التكرارية والحوسبة الفعالة، ماكجرو هيل (1967) ISBN 0-262-68052-1(يصف الترتيبات المتكررة وترتيب تشيرش-كلين)
• لاري دبليو ميلر ، الدوال العادية والرموز الترتيبية البنائية ، مجلة المنطق الرمزي ، المجلد 41، العدد 2، يونيو 1976، الصفحات من 439 إلى 459، JSTOR 2272243 ، 
• هيلبرت ليفيتز ، الأعداد الترتيبية المتسامية ورموزها: للمبتدئين ، مقال توضيحي (8 صفحات، بصيغة PostScript )
• هيرمان روج جيرفيل ، الحقيقة وإمكانية الإثبات ، مخطوطة قيد الإعداد.

• باروايز، جون (1976). المجموعات والهياكل المقبولة: مدخل إلى نظرية التعريف . منظورات في المنطق الرياضي. سبرينغر-فيرلاغ. ISBN 3-540-07451-1.
• هينمان، بيتر ج. (1978). التسلسلات الهرمية القائمة على نظرية الاستدعاء الذاتي . وجهات نظر في المنطق الرياضي. سبرينغر-فيرلاغ.

• مايكل راثجن ، "مجال التحليل الترتيبي". في إس بي كوبر وجيه تروس (محرران): المجموعات والبراهين . (مطبعة جامعة كامبريدج، 1999) 219-279. في ملف Postscript مؤرشف بتاريخ 22-02-2012 على Wayback Machine .