الترميز الترتيبي

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 48 صور
الموسوعة الحرة

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

  1. مجموعة الأعداد الطبيعية هي مجموعة متكررة
  2. الترتيب الجيد المستحث على مجموعة فرعية من الأعداد الطبيعية هو علاقة تكرارية

توجد العديد من أنظمة الترميز الترتيبي، بما في ذلك أنظمة ويلهلم أكرمان ، وهاينز باخمان ، وويلفريد بوخهولز، وجورج كانتور ، وسولومون فيفرمان ، وجيرهارد ياغر، وآيلز، وفايفر، وولفرام بولرز، وكورت شوت ، وجايسي تاكيوتي (المعروفة باسم المخططات الترتيبية )، وأوزوالد فيبلين . ولدى ستيفن كول كلين نظام ترميز يُسمى نظام كلين O ، والذي يتضمن الترميز الترتيبي، ولكنه ليس بنفس كفاءة الأنظمة الأخرى المذكورة هنا.

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

مثال مبسط باستخدام دالة الاقتران

وكالعادة، يجب أن نبدأ برمز ثابت للصفر، "0{\displaystyle 0}والتي يمكننا اعتبارها دالة للرتبة الصفرية. وهذا ضروري لأنه لا توجد أعداد ترتيبية أصغر يمكن وصف الصفر من خلالها.

الخطوة التالية الأكثر وضوحًا هي تعريف دالة أحادية، "S"، تأخذ عددًا ترتيبيًا إلى أصغر عدد ترتيبي أكبر منه؛ بعبارة أخرى، S هي دالة اللاحق. وبالاقتران مع الصفر، تُمكّن دالة اللاحق من تسمية أي عدد طبيعي.

يمكن تعريف الدالة الثالثة بأنها دالة تربط كل عدد ترتيبي بأصغر عدد ترتيبي لا يمكن وصفه بعد بالدالتين السابقتين والقيم السابقة لهذه الدالة. وهذا من شأنه أن يربطβ{\displaystyle \beta }لω⋅β{\displaystyle \أوميغا \cdot \beta }إلا عندماβ{\displaystyle \beta }هي نقطة ثابتة لتلك الدالة بالإضافة إلى عدد محدود، وفي هذه الحالة يتم تعيينβ{\displaystyle \beta }لω⋅(β+1){\displaystyle \omega \cdot (\beta +1)}.

الوظيفة الرابعة سترسم الخريطةα{\displaystyle \alpha }لωω⋅α{\displaystyle \omega ^{\omega }\cdot \alpha }إلا عندماα{\displaystyle \alpha }هي نقطة ثابتة لتلك الدالة بالإضافة إلى عدد محدود، وفي هذه الحالة يتم تعيينα{\displaystyle \alpha }لωω⋅(α+1){\displaystyle \omega ^{\omega }\cdot (\alpha +1)}.

رمز ξ

يمكن الاستمرار بهذه الطريقة، لكنها ستؤدي إلى عدد لا نهائي من الدوال. لذا، دعونا ندمج الدوال الأحادية في دالة ثنائية. وذلك عن طريق الاستدعاء الذاتي المتسامي علىα{\displaystyle \alpha }يمكننا استخدام الاستدعاء الذاتي المتجاوز للحدود علىβ{\displaystyle \beta }لتحديدξ(α،β){\displaystyle \xi (\alpha ,\beta )}أن يكون أصغر عدد ترتيبيγ{\displaystyle \gamma }بحيثα<γ{\displaystyle \alpha <\gamma }وβ<γ{\displaystyle \beta <\gamma }وγ{\displaystyle \gamma }ليست قيمةξ{\displaystyle \xi }لأي أصغرα{\displaystyle \alpha }أو لنفس الغرضα{\displaystyle \alpha }مع حجم أصغرβ{\displaystyle \beta }.

وبالتالي، حددξ{\displaystyle \xi }-الرموز كما يلي:

  • "0{\displaystyle 0}"هوξ{\displaystyle \xi }رمز الصفر (-).
  • إذا تم استبدال "أ" و "ب" بـξ{\displaystyle \xi }-رموز لـα{\displaystyle \alpha }وβ{\displaystyle \beta }في "ξAB"، تكون النتيجة aξ{\displaystyle \xi }-تدوين لـξ(α،β){\displaystyle \xi (\alpha ,\beta )}.
  • لا يوجد غيرهاξ{\displaystyle \xi }-الرموز.

الوظيفةξ{\displaystyle \xi }تُعرَّف هذه الدالة لجميع أزواج الأعداد الترتيبية، وهي دالة أحادية. تُعطي دائمًا قيمًا أكبر من مُدخلاتها، ونطاقها يشمل جميع الأعداد الترتيبية باستثناء الصفر وأعداد إبسيلون .

يمتلك المرءξ(α،β)<ξ(γ،دلتا){\displaystyle \xi (\alpha ,\beta )<\xi (\gamma ,\delta )}عندما

  • α=γ{\displaystyle \alpha =\gamma }وβ<دلتا{\displaystyle \beta <\delta }، أو
  • α<γ{\displaystyle \alpha <\gamma }وβ<ξ(γ،دلتا){\displaystyle \beta <\xi (\gamma ,\delta )}، أو
  • α>γ{\displaystyle \alpha >\gamma }وξ(α،β)≤دلتا{\displaystyle \xi (\alpha ,\beta )\leq \delta }.

وبناءً على هذا التعريف، فإنّ الرموز القليلة الأولى لـ ξ هي:

"0" لـ 0. "ξ00" لـ 1. "ξ0ξ00" لـ ξ(0,1)=2. "ξξ000" لـ ξ(1,0)=ω. "ξ0ξ0ξ00" لـ 3. "ξ0ξξ000" لـ ω+1. "ξξ00ξ00" لـ ω·2. "ξξ0ξ000" لـ ω ω . "ξξξ0000" لωωω.{\displaystyle \أوميغا ^{\أوميغا ^{\أوميغا }}.}

على العموم،ξ(0،β)=β+1{\displaystyle \xi (0,\beta )=\beta +1}. بينما ξ(1+α,β) = ω ω α ·(β+k) لـ k = 0 أو 1 أو 2 حسب المواقف الخاصة: k = 2 إذا كان α رقم إبسيلون و β محدود. بخلاف ذلك، k = 1 إذا كانت β مضاعفًا لـ ω ω α+1 بالإضافة إلى عدد محدود. خلاف ذلك، ك = 0.

إنه:

α+1=ξ(0،α).{\displaystyle \alpha +1=\xi (0,\alpha ).}
1≤γ<ωωβ+1∧ن<ω⟹ωωβ+1⋅α+ωωβ⋅(ω⋅γ+ن)=ξ(1+β،ωωβ+1⋅α+(ω⋅γ+ن)).{\displaystyle 1\leq \gamma <\omega ^{\omega ^{\beta +1}}\land n<\omega \implies \omega ^{\omega ^{\beta +1}}\cdot \alpha +\omega ^{\omega ^{\beta }}\cdot (\omega \cdot \gamma +n)=\xi (1+\beta ,\omega ^{\omega ^{\beta +1}}\cdot \alpha +(\omega \cdot \gamma +n)).}
(0<α∨β<ωβ)∧ن<ω⟹ωωβ+1⋅α+ωωβ⋅(ن+1)=ξ(1+β،ωωβ+1⋅α+ن).{\displaystyle (0<\alpha \lor \beta <\omega ^{\beta })\land n<\omega \implies \omega ^{\omega ^{\beta +1}}\cdot \alpha +\omega ^{\omega ^{\beta }}\cdot (n+1)=\xi (1+\beta ,\omega ^{\omega ^{\beta +1}}\cdot \alpha +n).}
β=ωβ∧ن<ω⟹ωωβ⋅(ن+2)=ξ(β،ن).{\displaystyle \beta =\omega ^{\beta }\land n<\omega \implies \omega ^{\omega ^{\beta }}\cdot (n+2)=\xi (\beta ,n).}

يمكن استخدام رموز ξ لتسمية أي عدد ترتيبي أقل من ε ≤ 0 باستخدام أبجدية مكونة من رمزين فقط ("0" و"ξ"). إذا تم توسيع هذه الرموز بإضافة دوال تُحصي أعداد إبسيلون، فستتمكن من تسمية أي عدد ترتيبي أقل من أول عدد إبسيلون لا يمكن تسميته بالدوال المضافة. تُسمى هذه الخاصية الأخيرة، وهي إضافة رموز ضمن جزء أولي من الأعداد الترتيبية تُعطي أسماءً ضمن ذلك الجزء، بالاكتمال (نسبةً إلى سولومون فيفرمان ).

قائمة

توجد أنظمة عديدة ومختلفة للتدوين الترتيبي، قدمها مؤلفون مختلفون. وغالبًا ما يكون التحويل بين هذه الأنظمة المختلفة أمرًا صعبًا للغاية.

كانتور

تُعطي "الكثيرات الحدودية الأسية" في 0 و ω نظامًا للترميز الترتيبي للأعداد الترتيبية الأقل من ε 0. وهناك العديد من الطرق المكافئة لكتابة هذه الكميات؛ فبدلاً من استخدام كثيرات الحدود الأسية، يمكن استخدام الأشجار الجذرية، أو الأقواس المتداخلة، أو النظام الموصوف أعلاه.

فيبلين

يمكن استخدام دوال فيبلن ذات المتغيرين ( فيبلن، 1908 ) لإنشاء نظام ترميز ترتيبي للأعداد الترتيبية الأقل من عدد فيفرمان-شوت الترتيبي . كما تُعطي دوال فيبلن، سواءً كانت ذات عدد محدود أو غير محدود من المتغيرات، أنظمة ترميز ترتيبي للأعداد الترتيبية الأقل من عدد فيبلن الترتيبي الصغير والكبير .

أكرمان

وصف أكرمان (1951) نظامًا للتدوين الترتيبي أقل قوة من النظام الذي وصفه فيبلين سابقًا. ويُطلق على حد نظامه أحيانًا اسم الترتيب الأكرماني .

باخمان

قدّم باخمان (1950) الفكرة الأساسية المتمثلة في استخدام الأعداد الترتيبية غير القابلة للعد لإنتاج أعداد ترتيبية جديدة قابلة للعد. كان نظامه الأصلي معقدًا نوعًا ما في الاستخدام لأنه كان يتطلب اختيار متتالية خاصة تتقارب إلى كل عدد ترتيبي. وقد تجنّبت أنظمة الترميز اللاحقة التي قدمها فيفرمان وآخرون هذا التعقيد.

مخططات تاكيوتي (الترتيبية)

وصف تاكيوتي (1987) نظامًا للتدوين الترتيبي يُعرف باسم "المخططات الترتيبية"، وحدته هي الترتيب الترتيبي لتاكيوتي-فيفيرمان-بوخهولز . [ 1 ] وقد تم تبسيط النظام لاحقًا بواسطة فيفيرمان.

دوال فيفرمان θ

قدّم فيفرمان دوال ثيتا، الموصوفة في بوخهولز (1986) على النحو التالي: بالنسبة للعدد الترتيبي α ، فإن θα دالة تربط الأعداد الترتيبية ببعضها. غالبًا ما تُكتب θα ( β ) على الصورة θαβ . تُعرَّف المجموعة C ( α , β ) بالاستقراء على α بأنها مجموعة الأعداد الترتيبية التي يمكن توليدها من 0، ω₁ ، ω₂ ، ...، ωₙ ، بالإضافة إلى الأعداد الترتيبية الأقل من β، وذلك من خلال عمليات جمع الأعداد الترتيبية والدوال θξ حيث ξ < α . وتُعرَّف الدالة θγ بأنها الدالة التي تُحصي الأعداد الترتيبية δ حيث δ ∉ C ( γ , δ ). تكمن مشكلة هذا النظام في أن الترميز الترتيبي ووظائف الدمج ليسا متطابقين، وبالتالي لا تُعتبر هذه الوظيفة ترميزًا ترتيبيًا. ولا يُعرف ترميز ترتيبي مرتبط بها.

بوخهولز

وصف بوخهولز (1986) نظام الترميز الترتيبي التالي بأنه تبسيط لدوال ثيتا لفيفرمان. عرّف:

  • Ω ξ = ω ξ إذا ξ > 0، Ω 0 = 1

يتم تعريف الوظائف ψ v ( α ) لـ α ترتيبي، v ترتيبي على الأكثر ω ، عن طريق الحث على α كما يلي:

  • ψ v ( α ) هو أصغر عدد ترتيبي غير موجود في C v ( α )

حيث C v ( α ) هي أصغر مجموعة بحيث

  • تحتوي المجموعة C v ( α ) على جميع الأعداد الترتيبية الأقل من Ω v
  • C v ( α ) مغلقة تحت الجمع الترتيبي
  • C v ( α ) مغلقة تحت الدوال ψ u (لـ u ≤ ω ) المطبقة على الوسائط الأقل من α .

يتمتع هذا النظام بنفس قوة نظام فيفرمان تقريبًا، كماθεΩv+10=ψ0(εΩv+1){\displaystyle \theta \varepsilon _{\Omega _{v}+1}0=\psi _{0}(\varepsilon _{\Omega _{v}+1})}بالنسبة لـ v ≤ ω . ومع ذلك، فرغم قوة هذا النظام، إلا أنه لا يُعدّ ترميزًا ترتيبيًا. صحيح أن بوخهولز ابتكر ترميزًا ترتيبيًا مرتبطًا به، إلا أنه معقد: تجدون تعريفه في المقال الرئيسي.

كلين أو

وصف كلين (1938) نظامًا للترميز لجميع الأعداد الترتيبية المتكررة (الأعداد الأقل من العدد الترتيبي لتشرش-كلين ). لسوء الحظ، على عكس الأنظمة الأخرى المذكورة أعلاه، لا توجد عمومًا طريقة فعالة لتحديد ما إذا كان عدد طبيعي ما يمثل عددًا ترتيبيًا، أو ما إذا كان عددان يمثلان العدد الترتيبي نفسه. مع ذلك، يمكن إيجاد رموز فعالة تمثل مجموع الأعداد الترتيبية، وحاصل ضربها، وأسها (انظر الحساب الترتيبي ) لأي رمزين معطيين في نظام كلين.يا{\displaystyle {\mathcal {O}}}وبإعطاء أي رمز لعدد ترتيبي، توجد مجموعة رموز قابلة للتعداد بشكل متكرر تحتوي على عنصر واحد لكل عدد ترتيبي أصغر، وهي مرتبة فعليًا. (كلين)يا{\displaystyle {\mathcal {O}}}يشير إلى مجموعة قياسية (وغير قابلة للحساب بشكل كبير) من الرموز. يستخدم مجموعة فرعية من الأعداد الطبيعية بدلاً من سلاسل محدودة من الرموز، وهو غير تكراري، وبالتالي، مرة أخرى، لا يُصنف كرمز ترتيبي تكراري.

قائمة بحدود مختلف الترميزات الترتيبية ووظائف الدمج

جدول حدود مختلف الرموز والدوال
الترميزأعلى مجموعة من الأعداد الترتيبية القابلة للعد
الشكل الطبيعي لكانتورإبسيلون صفرε0{\displaystyle \varepsilon _{0}}
دالة فيبلن الثنائيةترتيب فيفرمان-شوتΓ0{\displaystyle \Gamma _{0}}
دالة فيبلن المحدودةترتيب فيبلين الصغير
بيردزθ{\displaystyle \theta }وظيفةترتيب فيبلين الصغيرθ(Ωω){\displaystyle \theta (\Omega ^{\omega })}
وظيفة فيبلين الموسعةترتيب فيبلين الكبير
باخمانψ{\displaystyle \psi }وظيفةترتيب باخمان-هواردψΩ(εΩ+1){\displaystyle \psi _{\Omega }(\varepsilon _{\Omega +1})}
مادورψ{\displaystyle \psi }وظيفةترتيب باخمان-هواردψ(εΩ+1){\displaystyle \psi (\varepsilon _{\Omega +1})}
وايرمانزϑ{\displaystyle \vartheta }وظيفةترتيب باخمان-هواردϑ(εΩ+1){\displaystyle \vartheta (\varepsilon _{\Omega +1})}
فيفرمانθ{\displaystyle \theta }وظيفةترتيب تاكيوتي-فيفيرمان-بوخهولزθεΩω+1(0){\displaystyle \theta _{\varepsilon _{\Omega _{\omega }+1}}(0)}
بوخهولزψ{\displaystyle \psi }وظيفةترتيب تاكيوتي-فيفيرمان-بوخهولزψ0(εΩω+1){\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})}
راثجينψ{\displaystyle \psi }وظيفةψΩ(χεم+1(0)){\displaystyle \psi _{\Omega }(\chi _{\varepsilon _{M}+1}(0))}
راثجينΨ{\displaystyle \Psi }وظيفة>Ψ(εك+1){\displaystyle \Psi (\varepsilon _{K+1})}
أول تجربة لستيجرتΨ{\displaystyle \Psi }وظيفة>Ψ(ω+؛P0؛ϵ؛ϵ؛0)εΞ+1{\displaystyle \Psi _{(\omega ^{+};{\mathsf {P}}_{0};\epsilon ;\epsilon ;0)}^{\varepsilon _{\Xi }+1}} [ 2 ]
ستيجرت الثانيΨ{\displaystyle \Psi }وظيفة> ترتيب ستيجرت الكبيرΨ(ω+؛P0؛ϵ؛ϵ؛0)εY+1{\displaystyle \Psi _{(\omega ^{+};{\mathsf {P}}_{0};\epsilon ;\epsilon ;0)}^{\varepsilon _{Y}+1}} [ 2 ]
تارانوفسكيج{\displaystyle C}وظيفةالوجود غير معروف، ولكنه متكرر وكبير جدًا
كلينزيا{\displaystyle {\mathcal {O}}}وظيفةترتيب الكنيسة-كلينω1جك{\displaystyle \omega _{1}^{\mathsf {CK}}}
كليفيا+{\displaystyle {\mathcal {O}}^{+}}وظيفةأعلى الترتيبات القابلة للكتابةλ{\displaystyle \lambda }
كليفيا++{\displaystyle {\mathcal {O}}^{++}}وظيفةأعلى الأعداد الترتيبية القابلة للكتابة في نهاية المطافζ{\displaystyle \zeta }

انظر أيضاً

مراجع

  1. ↑ راثجن، مايكل (1 أغسطس 2023). "فن قياس قوة النظريات" . إشعارات الجمعية الرياضية الأمريكية . 70 ( 7): 1071-1079 – عبر وايت روز.
  2. 1 2 د. مادور، حديقة الحيوانات الترتيبية (ص.2). تم الوصول إليه في 25 أكتوبر 2021.