💻 computer science

Are Dependent Types in Set Theory Feasible?

تقدم هذه الورقة تضميناً آلياً للأنواع المعتمدة والأكوان في نظرية مجموعات "تارسكي-غروثينديك" ضمن مساعد الإثبات "ليسا" (Lisa)، مما يتيح تكتيك تحقق من الأنواع ينتج براهين ويستفيد من قواعد المساواة والتعويض المجموعاتية القياسية للاستنتاج الآلي.

المؤلفون الأصليون: Yunsong Yang, Simon Guilloud, Viktor Kunčak

نُشر 2026-03-16

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Yunsong Yang, Simon Guilloud, Viktor Kunčak

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

في العقود الأخيرة، أصبح هناك مخطط أكثر حداثة يسمى نظرية الأنواع المعتمدة (Dependent Type Theory) (المستخدمة في أدوات مثل Lean و Rocq) هو المفضل لدى العديد من علماء الرياضيات والمبرمجين. إنها تشبه المكتبة حيث لكل كتاب ملصق يتغير بناءً على ما بداخله، مما يسمح بتنظيم دقيق للغاية. ومع ذلك، فإن هذا المخطط الجديد معقد في البناء والتحقق؛ فإذا ارتكبت خطأً بسيطاً في الأساس، فقد تصبح المكتبة بأكملها غير آمنة.

السؤال الكبير: هل يمكننا بناء الميزات المتطورة ذاتية التنظيم الخاصة بـ "نظرية الأنواع" داخل أساس "نظرية المجموعات" المتين والتقليدي؟

تقول هذه الورقة البحثية نعم، وإليك كيف فعلوا ذلك، باستخدام بعض التشبيهات البسيطة:

1. المترجم (التضمين - The Embedding)

قام المؤلفون ببناء مترجم يتحدث اللغتين.

المشكلة: نظرية المجموعات لا تفهم بشكل طبيعي "الدوال التي تعتمد على مدخلاتها" (الأنواع المعتمدة). هي تفهم فقط المجموعات القياسية.
الحل: قاموا بإنشاء قاموس يترجم مفاهيم "نظرية الأنواع" إلى مفاهيم "نظرية المجموعات".
- تشبيه: تخيل أن لديك وصفة لكعكة تقول: "أضف الدقيق إذا كانت العجينة صفراء". نظرية المجموعات لا تعرف ماذا يعني "إذا" في سياق الوصفة. قام المؤلفون بترجمة هذا إلى قاعدة صارمة: "مجموعة جميع المكونات تتضمن الدقيق فقط إذا كانت العجينة صفراء".
- استخدموا امتداداً خاصاً للمنطق (يسمى $\lambda$ FOL) يسمح بكتابة هذه "الوصفات الشرطية" كمجموعات رياضية قياسية.

2. الأرفف اللانهائية (الأكوان - Universes)

في نظرية الأنواع، لديك "أكوان". فكر في هذه الأكوان كأرفف. الرف يحمل كتباً (أنواعاً)، ولكن الرف نفسه يجب أن يستقر على رف أكبر.

المشكلة: في نظرية المجموعات القياسية، لا يمكنك امتلاك "مجموعة كل المجموعات" (لأن ذلك يؤدي إلى تناقضات). لا يمكنك بسهولة بناء سلم لانهائي من الأرفف حيث يكون كل رف كبيراً بما يكفي لاحتواء الرف الذي تحته.
الحل: استخدموا قاعدة رياضية قوية تسمى بديهية تارسكي (Tarski's Axiom).
- تشبيه: تخيل أنك تحاول بناء برج من الصناديق. القواعد القياسية تقول: "لا يمكنك وضع صندوق داخل صندوق أكبر منه". بديهية تارسكي هي مثل قاعدة سحرية تقول: "لكل صندوق تملكه، يوجد صندوق فائق كبير بما يكفي لاحتوائه، ويوجد صندوق فائق الفوقية لاحتواء ذلك الصندوق، وهكذا إلى ما لا نهاية".
- هذا يسمح لهم بإنشاء تسلسل هرمي لانهائي من "الأكوان" (الأرفف) داخل نظرية المجموعات، تماماً كما تتطلب نظرية الأنواع.

3. المدقق الآلي (التكتيك المنتج للبرهان - Proof-Producing Tactic)

عادةً، عندما تكتب كوداً أو برهاناً في هذه الأنظمة، عليك إقناع الكمبيوتر يدوياً بأن منطقك سليم.

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

4. خدعة "النوع الفرعي" (Subtyping)

لقد أضافوا أيضاً ميزة تسمى النوع الفرعي (Subtyping).

المفهوم: في البرمجة، "الكلب" هو نوع من "الحيوان". إذا كانت الدالة تحتاج إلى "حيوان"، يمكنك إعطاؤها "كلباً".
التحدي: في نظرية المجموعات البحتة، هذا الأمر صعب لأن المجموعات لا تتوافق دائماً مع علاقات "هو نوع من" (is a kind of).
النتيجة: أثبتوا قاعدة محددة تسم تتيح لهذا الأمر أن يعمل بأمان داخل ترجمة نظرية المجموعات الخاصة بهم، ولكن مع وجود حواجز وقائية لمنع "مجموعة كل الدوال" من أن تصبح كبيرة جداً لدرجة تمنع وجودها.

لماذا يهم هذا؟

اعتبر Lean و Rocq كمكتبات عالية التقنية ومستقبلية، وهي رائعة في الاستخدام ولكن قواعدها الأساسية معقدة وهشة. واعتبر نظرية المجموعات كمكتبة مبنية على صخرة صلبة—مملة ولكنها لا تتزعزع.

هذه الورقة البحثية تشبه بناء جسر.

تسمح للأشخاص بكتابة أكوادهم الحديثة والمتطورة بأسلوب "نظرية الأنواع".
يقوم هذا الجسر تلقائياً بترجمتها إلى لغة "نظرية المجموعات".
يقوم أساس نظرية المجموعات بالتحقق من أنها صحيحة بنسبة 100%.

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

إليك ملخص تقني مفصل للورقة البحثية بعنوان "هل الأنواع المعتمدة في نظرية المجموعات مجدية؟" لـ يونسونغ يانغ، وسايمون غيولود، وفيكتور كونتشاك.

1. بيان المشكلة

تتناول الورقة التوتر القائم بين هيمنة نظرية الأنواع المعتمدة (DTT) في إثبات النظريات التفاعلي (مثل Lean 4 وRocq) وبين البساطة التأسيسية لـ نظرية مجموعات زيرميلو-فرانكل مع الاختيار (ZFC).

التحدي: بينما توفر نظرية الأنواع المعتمدة ميزات عملية مثل الحوسبة المدمجة والتحقق المتوقع من الأنواع، فإن نويات المنطق الخاصة بها معقدة، ويصعب التحقق من صحتها، وعرضة للأخطاء البرمجية في التنفيذ. وفي المقابل، تعد ZFC أساسًا ناضجًا ومفهومًا جيدًا، لكنها تفتقر إلى الدعم الأصيل للأنواع المعتمدة ونموذج "الأنواع كـ مجموعات" المطلوب لمساعدات الإثبات الحديثة.
الهدف: يسعى المؤلفون لتحديد ما إذا كان من الممكن تنفيذ نظام أنواع ناعم (soft type system) للأنواع المعتمدة فوق أساس قائم على نظرية المجموعات (وتحديدًا مساعد الإثبات Lisa). الهدف هو توفير بناء الجمل (syntax) والأتمتة الخاصة بنظرية الأنواع المعتمدة مع ضمان أن جميع عمليات الاستدلال مبررة رسميًا بواسطة بديهيات نظرية المجموعات وقواعد الاستنتاج للمنطق من الدرجة الأولى (FOL).

2. المنهجية

يقترح المؤلفون تضمينًا ميكانيكيًا (mechanized embedding) لأنواع الدوال المعتمدة مع تسلسل هرمي للأكوان داخل المنطق من الدرجة الأولى المخطط (schematic first-order logic) مع المساواة، باستخدام مساعد الإثبات Lisa.

أ. الأساس المنطقي: $\lambda$ FOL

للتعامل مع ربط المتغيرات (وهو أمر ضروري لـ $\lambda$ -abstractions في نظرية الأنواع) ضمن إطار من الدرجة الأولى، يستخدم المؤلفون $\lambda$ FOL، وهو امتداد للمنطق من الدرجة الأولى متاح في Lisa.

الميزات: يتضمن $\lambda$ FOL حدود $\lambda$ ( $\lambda$ -terms) وعامل هيلبرت $\epsilon$ .
البساطة: يعتمد النظام على اختزال $\beta$ ( $\beta$ -reduction) وتعيين الرموز المخطط (schematic symbol instantiation)، مما يسمح بفك الحدود من الرتب العليا إلى حدود نقية من الدرجة الأولى، مما يحافظ على "روح الدرجة الأولى" للنواة.

ب. تضمين الأنواع المعتمدة

يعرف المؤلفون دالة تضمين تربط حدود نظرية الأنواع بحدود $\lambda$ FOL:

التجريد ( $\lambda x:T. u$ ): يُرسم كطقم من الأزواج يمثل علاقة دالية: abs(T)(λx.u) := {⟨x, L(x)⟩ | x ∈ T}.
التطبيق ( $t u$ ): يُرسم باستخدام عامل $\epsilon$ لاختيار قيمة من طقم الدالة: app(t)(u) := εy. (u, y) ∈ t.
الضرب المعتمد ( $\Pi x:T_1. T_2$ ): يُرسم كطقم من العلاقات الدالية التي تستوفي قيود المجال والمجال المقابل:
$\Pi(T_1)(L) := \{ f \in \mathcal{P}(T_1 \times \bigcup_{x \in T_1} L(x)) \mid \text{isFunc}(f) \land \forall x \in T_1. \text{app}(f)(x) \in L(x) \}$
النظرية الرئيسية: يثبتون أن هذه التعريفات تستعيد قواعد الاستدلال القياسية لنظرية الأنواع المعتدة، بما في ذلك اختزال $\beta$ ، والتجريد (Tabs)، والتطبيق (Tapp)، وذلك استنادًا بحتًا إلى بديهيات نظرية المجموعات.

ج. إدارة الأكوان (Universe Management)

تفتقر ZFC القياسية إلى مفهوم داخلي للأكوان (المجموعات المغلقة تحت جميع عمليات الإنشاء). لنمذجة التسلسل الهرمي التراكمي ( $Type_i : Type_{i+1}$ ) المطلوب للتعددية (polymorphism):

بديهيات تارسكي-غروثنديك: يتبنى المؤلفون بديهية تارسكي، التي تؤكد وجود عدد لا نهائي من أكوان غروثنديك (Grothendieck universes).
التعريف: كون غروثنديك هو مجموعة مغلقة تحت عمليات الازدواج (pairing)، والاتحاد (union)، والمجموعات الجزئية (power sets)، والاستبدال (replacement).
التنفيذ: يعرفون محددًا isUniverse ودالة universeOf(x) (باستخدام عامل $\epsilon$ ) لاختيار كون يحتوي على مجموعة معينة. يسمح هذا ببناء تسلسل هرمي من الأكوان ($Typen$) الضروري لتشكيل الضرب المعتمد.

د. توليد الإثبات الآلي

لتجنب بناء الإثبات يدويًا لأحكام النوع (typing judgments)، قام المؤلفون بتنفيذ تكتيك التحقق من النوع ثنائي الاتجاه (Typecheck.prove) داخل Lisa.

الأنماط: يعمل التكتيك في نمط التحقق (Check) (التحقق من حد من نوع متوقع)، ونمط الاستنتاج (Infer) (حساب نوع حد ما)، ونمط المجموعة الجزئية (Subset) (التعامل مع النوع الفرعي).
النوع الفرعي (Subtyping): ينفذون شكلًا مقيدًا من النوع الفرعي. وبينما يعد التغاير العكسي (contravariance) الكامل مشكلة في نظرية المجموعات (بسبب مسائل الحجم)، فإنهم يثبتون قاعدة لـ المجالات الثابتة والمجالات المقابلة المتغيرة (covariant codomains) لمنتجات $\Pi$ (أي $\Pi$ -subtyping).
المخرجات: بدلًا من إرجاع قيمة منطقية (boolean)، يقوم التكتيك بتخليق كائن إثبات رسمي (إثبات نظري للمجموعات) يمكن التحقق منه بواسطة نواة Lisa.

3. المساهمات الرئيسية

التضمين في نظرية المجموعات لـ DTT: تحقيق رسمي لأنواع الدوال المعتمدة والتسلسلات الهرمية للأكوان داخل إطار نظري للمجموعات من الدرجة الأولى، مما يثبت إمكانية اختزال بنى DTT إلى الانتماء للمجموعات والمساواة.
مدقق نوع منتج للإثبات: تنفيذ تكتيك يولد تلقائيًا إثباتات يمكن للنواة التحقق منها لأحكام النوع، مما يجسد الفجوة بين نظرية الأنواع عالية المستوى ونظرية المجموعات منخفضة المستوى.
دعم النوع الفرعي: تنفيذ تجريبي للنوع الفرعي (تحديدًا أنواع الدوال المتغيرة/covariant) ضمن نموذج نظرية المجموعات، مما يوضح مرونة هذا النهج.
مسار التوافق التشغيلي: خطوة نحو ترجمة الإثباتات من الأنظمة القائمة على DTT (مثل Lean 4 وRocq) إلى مساعدات الإثبات القائمة على نظرية المجموعات، مما يسهل نقل الإثباتات والتوافق بين الأنظمة.

4. النتائج

التحقق: نجح المؤلفون في ميكنة التضمين في Lisa. وأظهروا أن أحكام النوع (مثل تركيب الدوال مع الهوية متعددة الأشكال) يمكن التحقق منها تلقائيًا.
حالة مثال: تحققوا من مثال تركيب متعدد الأشكال (Function.comp و id)، مما أظهر أن التكتيك يستنتج بشكل صحيح الانتماء للمجموعة للدالة المركبة بناءً على افتراضات المدخلات ومستويات الكون.
الصحة: يضمن النظام أن جميع قرارات التحقق من النوع مدعومة ببديهيات تارسكي-غروثنديك وقواعد الاستنتاج للمنطق من الدرجة الأولى، مما يلغي الحاجة إلى نواة معقدة وغير متحقق منها لنظرية الأنواع.

5. الأهمية

الرصانة التأسيسية: من خلال ترسيخ الأنواع المعتمدة في ZFC، يستفيد هذا النهج من قرن من الإجماع الرياضي ويبسط النواة المنطقية، مما قد يقلل من خطر الأخطاء البرمجية مقارنة بنويات DTT المعقدة.
الربط بين المجتمعات: يسهل هذا العمل نقل الإثباتات من بيئة DTT المهيمنة (Lean, Rocq) إلى أنظمة نظرية المجموعات (Mizar, Isabelle/ZF)، مما قد يوحد الرياضيات الرسمية.
الأتمتة العملية: يوضح هذا العمل أن نهج "نظام الأنواع الناعم" يمكن أن يوفر سهولة الاستخدام والأتمتة الخاصة بـ DTT دون التضحية بالبساطة التأسيسية لنظرية المجموعات.
الاتجاهات المستقبلية: يرى المؤلفون أن هذا خطوة أولى نحو طبقة ترجمة كاملة لـ Lean 4 وRocq، مما يشير إلى أن أسس نظرية المجموعات يمكن أن تدعم ميزات نظرية الأنواع المتقدمة مثل الأنواع المعتمدة والنوع الفرعي دون الحاجة إلى تغيير جذري في المنطق الأساسي.