مُحدد التفرع

في المنطق، المكمّم المتفرع ، ^{[ 1 ]} ويسمى أيضًا مكمّم هينكين ، أو المكمّم المرتب جزئيًا المحدود، أو حتى المكمّم غير الخطي ، هو ترتيب جزئي ^{[ 2 ].}

${\displaystyle \langle Qx_{1}\dots Qx_{n}\rangle }$

من المُكمِّمات لـ Q  ∈  {∀,∃}. وهي حالة خاصة من المُكمِّم المُعمَّم . في المنطق الكلاسيكي ، تُرتَّب بادئات المُكمِّمات ترتيبًا خطيًا بحيث تعتمد قيمة المتغير y_{_m} المُقيَّد بالمُكمِّم Q_{_m} على قيمة المتغيرات.

y ₁ , ..., y _{m −1}

مقيد بالمحددات الكمية

Qy ₁ ، ...، Qy _{m −1}

قبل Q _m . في منطق ذي تكميم جزئي مرتب (محدود)، لا يكون هذا هو الحال بشكل عام.

ظهر مفهوم التكميم المتفرع لأول مرة في ورقة بحثية قدمها ليون هينكين في مؤتمر عام 1959. ^{[ 3 ]} تُعتبر أنظمة التكميم المرتب جزئيًا متوسطة القوة بين منطق الرتبة الأولى ومنطق الرتبة الثانية . وهي تُستخدم كأساس لمنطق هينتيكا وغابرييل ساندو الداعم للاستقلالية .

أبسط مُحدد كمي لهينكين${\displaystyle Q_{H}}$يكون

${\displaystyle (Q_{H}x_{1},x_{2},y_{1},y_{2})\varphi (x_{1},x_{2},y_{1},y_{2})\equiv {\begin{pmatrix}\forall x_{1}\,\exists y_{1}\\\forall x_{2}\,\exists y_{2}\end{pmatrix}}\varphi (x_{1},x_{2},y_{1},y_{2}).}$

إنها (في الواقع كل صيغة تبدأ ببادئة هينكين، وليس فقط أبسطها) تعادل عملية سكولمية من الدرجة الثانية ، أي

${\displaystyle \exists f\,\exists g\,\forall x_{1}\forall x_{2}\,\varphi (x_{1},x_{2},f(x_{1}),g(x_{2})).}$

كما أنها قوية بما يكفي لتحديد الكمية${\displaystyle Q_{\geq \mathbb {N} }}$(أي "هناك عدد لا نهائي") مُعرَّف على النحو التالي

${\displaystyle (Q_{\geq \mathbb {N} }x)\varphi (x)\equiv (\exists a)(Q_{H}x_{1},x_{2},y_{1},y_{2})[\varphi (a)\land (x_{1}=x_{2}\leftrightarrow y_{1}=y_{2})\land (\varphi (x_{1})\rightarrow (\varphi (y_{1})\land y_{1}\neq a))].}$

يترتب على ذلك عدة أمور، بما في ذلك عدم إمكانية وضع بديهيات لمنطق الرتبة الأولى مع${\displaystyle Q_{H}}$(لاحظها إهرنفويشت لأول مرة )، ومكافئتها لـ${\displaystyle \سيجما _{1}^{1}}$- جزء من منطق الرتبة الثانية ( منطق الرتبة الثانية الوجودي ) - النتيجة الأخيرة التي نشرها بشكل مستقل في عام 1970 هربرت إندرتون ^{[ 4 ]} و دبليو. والكو. ^{[ 5 ]}

يمكن تعريف المحددات الكمية التالية أيضًا بواسطة${\displaystyle Q_{H}}$[ ^{2 ]​}

• ريشر: "عدد قيم φ أقل من أو يساوي عدد قيم ψ "

${\displaystyle (Q_{L}x)(\varphi x,\psi x)\equiv \operatorname {Card} (\{x\colon \varphi x\})\leq \operatorname {Card} (\{x\colon \psi x\})\equiv (Q_{H}x_{1}x_{2}y_{1}y_{2})[(x_{1}=x_{2}\leftrightarrow y_{1}=y_{2})\land (\varphi x_{1}\rightarrow \psi y_{1})]}$

• هارتيغ: " إن قيم φ متساوية في العدد مع قيم ψ "

${\displaystyle (Q_{I}x)(\varphi x,\psi x)\equiv (Q_{L}x)(\varphi x,\psi x)\land (Q_{L}x)(\psi x,\varphi x)}$

• تشانغ: "عدد φ يساوي عدد نطاق النموذج"

${\displaystyle (Q_{C}x)(\varphi x)\equiv (Q_{L}x)(x=x,\varphi x)}$

مُحدد كمية هينكين${\displaystyle Q_{H}}$يمكن التعبير عنها نفسها كنوع (4) من محدد كمية ليندستروم . ^{[ 2 ]}

طرح هينتيكا في ورقة بحثية عام 1973 ^{[ 6 ]} فرضية مفادها أن بعض الجمل في اللغات الطبيعية تُفهم على أفضل وجه من حيث الكميات المتفرعة، على سبيل المثال: "بعض أقارب كل قروي وبعض أقارب كل رجل مدينة يكرهون بعضهم البعض" من المفترض أن تُفسر، وفقًا لهينتيكا، على النحو التالي: ^{[ 7 ] [ 8 ]}

${\displaystyle {\begin{pmatrix}\forall x_{1}\,\exists y_{1}\\\forall x_{2}\,\exists y_{2}\end{pmatrix}}[(V(x_{1})\wedge T(x_{2}))\rightarrow (R(x_{1},y_{1})\wedge R(x_{2},y_{2})\wedge H(y_{1},y_{2})\wedge H(y_{2},y_{1}))].}$

وهو أمر معروف بأنه لا يوجد له مكافئ منطقي من الدرجة الأولى. ^{[ 7 ]}

لا تقتصر فكرة التفرع بالضرورة على استخدام المحددات الكمية الكلاسيكية كأوراق. ففي ورقة بحثية نُشرت عام 1979، ^{[ 9 ]} اقترح جون باروايز صيغًا مختلفة لجمل هينتيكا (كما تُسمى الجملة السابقة أحيانًا) حيث تكون المحددات الكمية الداخلية نفسها محددات كمية معممة ، على سبيل المثال: "معظم القرويين ومعظم سكان المدن يكرهون بعضهم بعضًا". ^{[ 7 ]} ملاحظًا أن${\displaystyle \Sigma _{1}^{1}}$بما أن الجملة غير مغلقة تحت النفي، فقد اقترح باروايز أيضًا اختبارًا عمليًا لتحديد ما إذا كانت جمل اللغة الطبيعية تتضمن بالفعل مُكمِّمات متفرعة، أي لاختبار ما إذا كان نفيها في اللغة الطبيعية يتضمن تحديدًا كميًا شاملًا على متغير مجموعة (أ).${\displaystyle \Pi _{1}^{1}}$^{[ 10 ]}​

قوبل اقتراح هينتيكا بالتشكيك من قبل عدد من علماء المنطق لأن بعض الجمل من الدرجة الأولى مثل الجملة أدناه تبدو وكأنها تلتقط بشكل جيد جملة هينتيكا في اللغة الطبيعية.

${\displaystyle [\forall x_{1}\,\exists y_{1}\,\forall x_{2}\,\exists y_{2}\,\varphi (x_{1},x_{2},y_{1},y_{2})]\wedge [\forall x_{2}\,\exists y_{2}\,\forall x_{1}\,\exists y_{1}\,\varphi (x_{1},x_{2},y_{1},y_{2})]}$

أين

${\displaystyle \varphi (x_{1},x_{2},y_{1},y_{2})}$

يشير

${\displaystyle (V(x_{1})\wedge T(x_{2}))\rightarrow (R(x_{1},y_{1})\wedge R(x_{2},y_{2})\wedge H(y_{1},y_{2})\wedge H(y_{2},y_{1}))}$

على الرغم من كثرة النقاشات النظرية التي تلت ذلك، لم يتضح إلا في عام ٢٠٠٩ أن بعض الاختبارات التجريبية التي أُجريت على طلاب مُدرَّبين على المنطق تُظهر ميلهم إلى إسناد نماذج تُطابق جملة الدرجة الأولى "ثنائية الاتجاه" بدلاً من جملة المُكمِّم المتفرع إلى العديد من تراكيب اللغة الطبيعية المُستمدة من جملة هينتيكا. فعلى سبيل المثال، عُرضت على الطلاب رسوم بيانية ثنائية الأجزاء غير مُوجَّهة - بمربعات ودوائر كرؤوس - وطُلب منهم تحديد ما إذا كانت جمل مثل "أكثر من ٣ دوائر وأكثر من ٣ مربعات متصلة بخطوط" تصف الرسوم البيانية بشكل صحيح. ^{[ ٧ ]}

• دلالات اللعبة
• منطق التبعية
• منطق داعم للاستقلالية (منطق الشرط)
• مُكمِّم موستوفسكي
• مُحدد كمية ليندستروم
• عدم قابلية الترتيب الأول

• مُكمِّم نظري للألعاب في PlanetMath.