مُكمِّم محدود

في دراسة النظريات الصورية في المنطق الرياضي ، تُضاف المُكمِّمات المحدودة (المعروفة أيضًا بالمُكمِّمات المُقيدة ) غالبًا إلى اللغة الصورية، إلى جانب المُكمِّمات القياسية "∀" و"∃". وتختلف المُكمِّمات المحدودة عن "∀" و"∃" في أنها تُقيِّد نطاق المتغير المُكمَّم. ويستند البحث في دراسة المُكمِّمات المحدودة إلى حقيقة أن تحديد صحة جملة تحتوي على مُكمِّمات محدودة فقط غالبًا ما يكون أسهل من تحديد صحة جملة أخرى.

تتضمن أمثلة المحددات الكمية المحدودة في سياق التحليل الحقيقي ما يلي:

• ${\displaystyle \forall x>0}$- لكل قيمة x حيث x أكبر من 0
• ${\displaystyle \exists y<0}$- يوجد قيمة لـ y حيث تكون y أقل من 0
• ${\displaystyle \forall x\in \mathbb {R} }$- لكل x حيث x عدد حقيقي
• ${\displaystyle \forall x>0\quad \exists y<0\quad (x=y^{2})}$- كل عدد موجب هو مربع عدد سالب

لنفترض أن L هي لغة حساب بيانو (لغة الحساب من الرتبة الثانية أو الحساب في جميع الأنواع المنتهية تصلح أيضًا). يوجد نوعان من الكميات المحدودة:${\displaystyle \forall n<t}$و${\displaystyle \exists n<t}$تربط هذه المحددات الكمية المتغير العددي n باستخدام حد عددي t لا يحتوي على n ولكنه قد يحتوي على متغيرات حرة أخرى. (يُقصد بالحدود العددية هنا حدود مثل "1 + 1"، "2"، "2 × 3"، " m + 3"، إلخ.)

تُحدد هذه الكميات وفقًا للقواعد التالية (${\displaystyle \phi }$(تشير إلى الصيغ):

${\displaystyle \exists n<t\,\phi \Leftrightarrow \exists n(n<t\land \phi )}$

${\displaystyle \forall n<t\,\phi \Leftrightarrow \forall n(n<t\rightarrow \phi )}$

هناك عدة دوافع لاستخدام هذه المحددات الكمية.

• في تطبيقات اللغة على نظرية الحوسبة ، مثل التسلسل الهرمي الحسابي ، لا تضيف المحددات الكمية المحدودة أي تعقيد. إذا${\displaystyle \phi }$إذا كان محمولاً قابلاً للتقرير${\displaystyle \exists n<t\,\phi }$و${\displaystyle \forall n<t\,\phi }$وهي قابلة للحسم أيضاً.
• في تطبيقات دراسة حساب بيانو ، قد يكون لحقيقة إمكانية تعريف مجموعة معينة باستخدام مُكمِّمات محدودة فقط آثارٌ على قابلية حساب تلك المجموعة. على سبيل المثال، يوجد تعريف للأعداد الأولية باستخدام مُكمِّمات محدودة فقط: العدد n أولي إذا وفقط إذا لم يكن هناك عددان أصغر منه تمامًا حاصل ضربهما يساوي n . لا يوجد تعريف للأعداد الأولية في هذه اللغة خالٍ من المُكمِّمات .${\displaystyle \langle 0,1,+,\times ,<,=\rangle }$ومع ذلك، فإن حقيقة وجود صيغة كمية محدودة تحدد أولية العدد تُظهر أنه يمكن تحديد أولية كل عدد حسابيًا.

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

في التسلسل الهرمي الحسابي ، تُسمى الصيغة الحسابية التي تحتوي فقط على مُكمِّمات محدودة${\displaystyle \Sigma _{0}^{0}}$،${\displaystyle \Delta _{0}^{0}}$، و${\displaystyle \Pi _{0}^{0}}$. يتم حذف الرقم 0 العلوي أحيانًا.

لنفترض أن L هي اللغة${\displaystyle \langle \in ,\ldots ,=\rangle }$في نظرية زيرميلو-فرانكل للمجموعات ، حيث يمكن استبدال علامة الحذف بعمليات تكوين المصطلحات مثل رمز عملية مجموعة القوى . يوجد مُكمِّمان محدودان:${\displaystyle \forall x\in t}$و${\displaystyle \exists x\in t}$. هذه المحددات الكمية تربط متغير المجموعة x وتحتوي على مصطلح t الذي قد لا يذكر x ولكنه قد يحتوي على متغيرات حرة أخرى.

يتم تحديد دلالات هذه المحددات الكمية وفقًا للقواعد التالية:

${\displaystyle \exists x\in t\ (\phi )\Leftrightarrow \exists x(x\in t\land \phi )}$

${\displaystyle \forall x\in t\ (\phi )\Leftrightarrow \forall x(x\in t\rightarrow \phi )}$

تُسمى صيغة ZF التي تحتوي فقط على مُكمِّمات محدودة${\displaystyle \Sigma _{0}}$،${\displaystyle \Delta _{0}}$، و${\displaystyle \Pi _{0}}$يشكل هذا أساس التسلسل الهرمي لليفي ، والذي يتم تعريفه بشكل مماثل للتسلسل الهرمي الحسابي.

تُعدّ المُكمِّمات المحدودة مهمة في نظرية مجموعات كريپكي-بلاتيك ونظرية المجموعات البنائية ، حيث يُقتصر الفصل على Δ _0. أي أنه يشمل الفصل للصيغ التي تحتوي على مُكمِّمات محدودة فقط، دون غيرها. في نظرية كريپكي-بلاتيك، يكمن الدافع في أن استيفاء مجموعة x لصيغة مُكمِّم محدود يعتمد فقط على مجموعة المجموعات القريبة منها في الرتبة ( إذ لا يمكن تطبيق عملية مجموعة القوى إلا عددًا محدودًا من المرات لتكوين حد). أما في نظرية المجموعات البنائية، فيستند هذا إلى أسس تنبؤية .

• التصنيف الفرعي - التحديد الكمي المحدود في نظرية الأنواع
• النظام F _<: — حساب لامدا متعدد الأشكال ذو نمط محدد مع تحديد كمي محدود

• هينمان، ب. (2005). أساسيات المنطق الرياضي . إيه كيه بيترز. ISBN 1-56881-262-0.
• كونين، ك. (1980). نظرية المجموعات: مقدمة في براهين الاستقلال . إلسيفير. ISBN 0-444-86839-9.