نظرية النموذج المحدود

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

بما أن العديد من النظريات المركزية لنظرية النماذج لا تصح عند تقييدها بالبنى المحدودة، فإن نظرية النماذج المحدودة تختلف اختلافًا كبيرًا عن نظرية النماذج في أساليب إثباتها. تشمل النتائج المركزية لنظرية النماذج الكلاسيكية التي لا تصح في حالة البنى المحدودة في نظرية النماذج المحدودة: نظرية التراص ، ونظرية غودل للاكتمال ، وطريقة الضرب الفائق لمنطق الرتبة الأولى . وتنتج جميع هذه النتائج غير الصحيحة من نظرية تراختنبروت . ^{[ 1 ]}

على الرغم من أن نظرية النماذج لها تطبيقات عديدة في الجبر الرياضي ، فقد أصبحت نظرية النماذج المحدودة أداةً "فعّالة بشكلٍ استثنائي" ^{[ 2 ]} في علوم الحاسوب. بعبارة أخرى: "في تاريخ المنطق الرياضي، انصبّ معظم الاهتمام على البنى اللانهائية. [...] ومع ذلك، فإن الكائنات التي تمتلكها الحواسيب وتحتفظ بها محدودة دائمًا. لدراسة الحوسبة، نحتاج إلى نظرية للبنى المحدودة." ^{[ 3 ]} وبالتالي، فإن مجالات التطبيق الرئيسية لنظرية النماذج المحدودة هي: نظرية التعقيد الوصفي ، ونظرية قواعد البيانات ، ونظرية اللغات الرسمية .

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

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

توصيف بنية واحدة

هل اللغة L معبرة بما يكفي لوضع بديهيات لبنية محدودة واحدة S ؟

مشكلة

يمكن وصف بنية مثل (1) في الشكل بواسطة جمل FO في منطق الرسوم البيانية مثل

1. كل عقدة لها حافة إلى عقدة أخرى:${\displaystyle \forall _{x}\exists _{y}G(x,y).}$
2. لا توجد عقدة لها حافة خاصة بها:${\displaystyle \forall _{x,y}(G(x,y)\Rightarrow x\neq y).}$
3. يوجد على الأقل عقدة واحدة متصلة بجميع العقد الأخرى :${\displaystyle \exists _{x}\forall _{y}(x\neq y\Rightarrow G(x,y)).}$

ومع ذلك، فإن هذه الخصائص لا تحدد البنية، لأنه بالنسبة للبنية (1') تنطبق الخصائص المذكورة أعلاه أيضًا، ومع ذلك فإن البنيتين (1) و (1') ليستا متماثلتين.

بشكل غير رسمي، السؤال هو ما إذا كان بإضافة عدد كافٍ من الخصائص، فإن هذه الخصائص معًا تصف بالضبط (1) وتكون صالحة (معًا) لأي بنية أخرى (حتى التماثل).

يقترب

بالنسبة لبنية محدودة واحدة، من الممكن دائمًا وصف البنية بدقة باستخدام جملة واحدة من نوع FO. ويوضح هذا المبدأ هنا لبنية ذات علاقة ثنائية واحدة.${\displaystyle R}$وبدون ثوابت. ولتحقيق هذه الغاية، نقدم متغيرات من الدرجة الأولى${\displaystyle x_{1},\dots ,x_{n}}$والتي تُفسر على أنها${\displaystyle n}$عناصر البنية. ثم نقدم الصيغ الأربع التالية:

1. ${\displaystyle \varphi _{1}=\bigwedge _{i\neq j}\neg (x_{i}=x_{j})}$يقول أن هناك على الأقل${\displaystyle n}$عناصر؛
2. ${\displaystyle \varphi _{2}=\forall _{y}\bigvee _{i}(x_{i}=y)}$ويقول إن هناك على الأكثر${\displaystyle n}$عناصر؛
3. ${\displaystyle \varphi _{3}=\bigwedge _{(a_{i},a_{j})\in R}R(x_{i},x_{j})}$يوضح كل جانب من جوانب العلاقة${\displaystyle R}$؛
4. ${\displaystyle \varphi _{4}=\bigwedge _{(a_{i},a_{j})\notin R}\neg R(x_{i},x_{j})}$يحدد كل حافة غير موجودة في العلاقة${\displaystyle R}$.

وأخيرًا، يتم وصف البنية بواسطة جملة FO${\displaystyle \exists _{x_{1}}\dots \exists _{x_{n}}(\varphi _{1}\land \varphi _{2}\land \varphi _{3}\land \varphi _{4})}$.

التمديد إلى عدد ثابت من الهياكل

يمكن بسهولة توسيع طريقة وصف بنية محدودة واحدة باستخدام جملة من الدرجة الأولى لتشمل أي عدد ثابت من البنى. ويمكن الحصول على وصف فريد من خلال فصل أوصاف كل بنية. على سبيل المثال، بالنسبة لبنيتين محدودتين${\displaystyle A}$و${\displaystyle B}$مع جمل تعريفية${\displaystyle \varphi _{A}}$و${\displaystyle \varphi _{B}}$سيكون هذا

${\displaystyle \varphi _{A}\lor \varphi _{B}.}$

امتداد إلى بنية لا نهائية

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

ولعل أشهر مثال على ذلك هو نظرية سكوليم ، التي تنص على وجود نموذج حسابي غير قياسي قابل للعد.

توصيف فئة من الهياكل

هل اللغة L معبرة بما يكفي لوصف تلك البنى المحدودة التي لها خاصية معينة P بدقة (حتى التماثل) ؟

مشكلة

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

يقترب

بدلاً من بيان عام، فيما يلي رسم تخطيطي لمنهجية التمييز بين الهياكل التي يمكن التمييز بينها والتي لا يمكن التمييز بينها.

1. الفكرة الأساسية هي أنه عندما يرغب المرء في معرفة ما إذا كان بالإمكان التعبير عن خاصية ما (P) باستخدام FO، فإنه يختار البنيتين A و B ، حيث تحتوي البنية A على الخاصية P بينما لا تحتوي البنية B عليها. إذا كانت جمل FO نفسها صحيحة بالنسبة للبنيتين A و B ، فلا يمكن التعبير عن الخاصية P باستخدام FO. باختصار:

   ${\displaystyle A\in P,B\not \in P}$و${\displaystyle A\equiv B,}$

   أين${\displaystyle A\equiv B}$هو اختصار لـ${\displaystyle A\models \alpha \Leftrightarrow B\models \alpha }$بالنسبة لجميع الجمل من النوع FO ، فإن α و P يمثلان فئة الهياكل ذات الخاصية P.
2. تعتمد هذه المنهجية على عدد لا نهائي من المجموعات الفرعية للغة، والتي يشكل اتحادها اللغة نفسها. على سبيل المثال، بالنسبة للغة FO، نعتبر الأصناف FO[ m ] لكل m . لكل m، يجب إثبات الفكرة الأساسية المذكورة أعلاه. أي:

   ${\displaystyle A\in P,B\not \in P}$و${\displaystyle A\equiv _{m}B}$

   مع زوج${\displaystyle A,B}$لكل${\displaystyle m}$و α (في ≡) من FO[ m ]. قد يكون من المناسب اختيار الفئات FO[ m ] لتشكيل تقسيم للغة.
3. إحدى الطرق الشائعة لتعريف FO[ m ] هي باستخدام رتبة المُكمِّم qr( α ) لصيغة FO α ، والتي تُعبِّر عن عمق تداخل المُكمِّمات . على سبيل المثال، بالنسبة لصيغة في الشكل الطبيعي prenex ، فإن qr هو ببساطة العدد الإجمالي لمُكمِّماتها. عندئذٍ، يُمكن تعريف FO[ m ] على أنها جميع صيغ FO α التي يكون فيها qr( α ) ≤ m (أو، إذا رُغِبَ في التقسيم، على أنها صيغ FO التي تكون فيها رتبة المُكمِّم مساوية لـ m ).
4. وهكذا، فإن الأمر كله يتلخص في العرض.${\displaystyle A\models \alpha \Leftrightarrow B\models \alpha }$على المجموعات الجزئية FO[ m ]. يتمثل النهج الرئيسي هنا في استخدام التوصيف الجبري الذي توفره ألعاب إهرنفويشت-فرايسيه . بشكل غير رسمي، تأخذ هذه الألعاب تماثلًا جزئيًا واحدًا على A و B وتمدده m مرة، إما لإثبات أو دحض${\displaystyle A\equiv _{m}B}$، وذلك يعتمد على من يفوز بالمباراة.

مثال

نريد أن نبين أن الخاصية التي مفادها أن حجم البنية المرتبة A = (A, ≤) زوجي، لا يمكن التعبير عنها في FO.

1. الفكرة هي اختيار A ∈ EVEN و B ∉ EVEN ، حيث EVEN هي فئة جميع الهياكل ذات الحجم الزوجي.
2. نبدأ ببنيتين مرتبتين A ₂ و B ₂ مع كونين A ₂ = {1، 2، 3، 4} و B ₂ = {1، 2، 3}. من الواضح أن A ₂ ∈ EVEN و B ₂ ∉ EVEN .
3. عندما يكون m = 2، في لعبة إهرنفويشت-فرايسيه ذات حركتين على A ₂ و B _2، يفوز اللاعب المكرر دائمًا، وبالتالي لا يمكن التمييز بين A ₂ و B _{2 في FO[2]، أي}${\displaystyle \mathbf {A} _{2}\models \alpha \iff \mathbf {B} _{2}\models \alpha }$لكل α ∈ FO[2] .
4. بعد ذلك، علينا تكبير الهياكل بزيادة قيمة m . على سبيل المثال، عندما m = 3، يجب أن نجد A _{= 3} و B = ₃ بحيث يفوز المُستنسخ دائمًا في لعبة الثلاث حركات. يمكن تحقيق ذلك باختيار A ₌ {1, ..., 8} و B ₌ {1, ..., 7}. وبشكل أعم، يمكننا اختيار A ₌ {1, ..., 2m ^} و B ₌ {1, ..., 2m ^- 1 }؛ فمع أي قيمة لـ m، يفوز المُستنسخ دائمًا في لعبة m حركة لهذا الزوج من الهياكل*.
5. وبالتالي، حتى على الهياكل المرتبة المحدودة، لا يمكن التعبير عنها في FO.

أثبت كلٌّ من غليبسكي وآخرون (1969) ، وفاجين (1976) بشكلٍ مستقل، قانونًا ثنائيًا (صفر-واحد) للجمل من الدرجة الأولى في النماذج المحدودة؛ وقد استخدم فاجين في برهانه نظرية التراص . ووفقًا لهذه النتيجة، فإن كل جملة من الدرجة الأولى في التوقيع العلائقي${\displaystyle \sigma }$إما أن يكون صحيحًا دائمًا تقريبًا أو خاطئًا دائمًا تقريبًا في حالة محدودة${\displaystyle \sigma }$-البنى. أي، ليكن S جملة ثابتة من الدرجة الأولى، واختر جملة عشوائية${\displaystyle \sigma }$-بناء${\displaystyle G_{n}}$مع النطاق${\displaystyle \{1,\dots ,n\}}$، بالتساوي بين الجميع${\displaystyle \sigma }$-هياكل ذات نطاق${\displaystyle \{1,\dots ,n\}}$ثم في النهاية عندما يؤول n إلى اللانهاية، فإن احتمال أن تقوم نماذج G _n بنمذجة S سيؤول إما إلى الصفر أو إلى الواحد:

${\displaystyle \lim _{n\to \infty }\operatorname {Pr} [G_{n}\models S]\in \{0,1\}.}$

تُعتبر مشكلة تحديد ما إذا كانت احتمالية جملة معينة تقترب من الصفر أو من الواحد مشكلة كاملة من نوع PSPACE . ^{[ 4 ]}

أُجري تحليل مماثل لمنطق أكثر تعبيرًا من منطق الرتبة الأولى. وقد ثبت أن قانون 0-1 ينطبق على الجمل في منطق الرتبة الأولى المُعزز بمعامل النقطة الثابتة الصغرى ، وبشكل أعم على الجمل في المنطق اللانهائي.${\displaystyle L_{\infty \أوميغا }^{\أوميغا }}$وهذا يسمح بوجود روابط وفصلات طويلة بشكل تعسفي. وهناك صيغة أخرى مهمة هي قانون 0-1 غير المصنف، حيث يتم بدلاً من ذلك النظر في نسبة البنى ذات المجال${\displaystyle \{1,\dots ,n\}}$عند النظر في نسبة فئات التشاكل للهياكل التي تحتوي على n عنصرًا، نجد أن هذه النسبة محددة جيدًا، حيث أن أي هيكلين متماثلين يحققان نفس الجمل. وينطبق قانون 0-1 غير المصنف أيضًا على${\displaystyle L_{\infty \أوميغا }^{\أوميغا }}$وبالتالي، على وجه الخصوص بالنسبة لمنطق الرتبة الأولى (LOFP) ومنطق الرتبة الأولى. ^{[ 5 ]}

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

وبشكلٍ أدق، ينتج كل نظام منطقي مجموعة من الاستعلامات التي يمكن التعبير عنها فيه. وتتوافق هذه الاستعلامات - عند تقييدها بهياكل محدودة - مع المشكلات الحسابية لنظرية التعقيد التقليدية.

تُجسد اللغات المنطقية بعض فئات التعقيد المعروفة على النحو التالي:

• في وجود ترتيب خطي، فإن منطق الرتبة الأولى مع إضافة عامل إغلاق تبادلي ومتعدي ينتج عنه L ، وهي مشاكل قابلة للحل في الفضاء اللوغاريتمي.
• في وجود ترتيب خطي، ينتج عن منطق الرتبة الأولى مع عامل إغلاق متعدٍ NL ، وهي المشكلات القابلة للحل في الفضاء اللوغاريتمي غير الحتمي.
• في وجود ترتيب خطي، فإن منطق الرتبة الأولى مع عامل النقطة الثابتة الصغرى يعطي P ، وهي المشكلات القابلة للحل في وقت متعدد الحدود حتمي.
• في جميع البنى المحدودة (بغض النظر عما إذا كانت مرتبة أم لا)، فإن منطق الرتبة الثانية الوجودي يعطي NP ( نظرية فاجين ). ^{[ 6 ]}

• تراختنبروت 1950 : فشل نظرية الاكتمال في منطق الرتبة الأولى
• شولز 1952: توصيف الأطياف في منطق الرتبة الأولى
• فاجين 1974 : مجموعة جميع الخصائص التي يمكن التعبير عنها في منطق الرتبة الثانية الوجودي هي بالضبط فئة التعقيد NP
• شاندرا، هاريل 1979/80: امتداد منطق الرتبة الأولى ذو النقطة الثابتة للغات استعلام قواعد البيانات القادرة على التعبير عن الإغلاق المتعدي -> الاستعلامات ككائنات مركزية في FMT
• Immerman و Vardi 1982: منطق النقطة الثابتة على الهياكل المرتبة يلتقط PTIME -> التعقيد الوصفي ( نظرية Immerman–Szelepcsényi )
• إيبينغهاوس ، فلوم 1995: أول كتاب شامل بعنوان "نظرية النموذج المحدود"
• أبيتبول ، هال، فيانو 1995: كتاب "أسس قواعد البيانات"
• إيمرمان 1999: كتاب " التعقيد الوصفي "
• كوبر، ليبكين، باريداينز 2000: كتاب "قواعد البيانات المقيدة"
• دارمشتات 2005 / آخن 2006: ورش العمل الدولية الأولى حول "نظرية النموذج الخوارزمي"

• Ebbinghaus, هاينز-ديتر ; فلوم، يورغ (1995). نظرية النموذج المحدود . سبرينغر . رقم ISBN 978-3-540-60149-4.

• فاجين، رونالد (1976). "الاحتمالات على النماذج المحدودة". مجلة المنطق الرمزي . 41 (1): 50-58 . doi : 10.2307/2272945 . JSTOR 2272945 . 
• جليبسكي، يو ف. كوجان، دي. ليوغونكي، ميشيغن؛ تالانوف، فيرجينيا (1969). "صيغة حجم ونسبة استيفاء صيغ حساب التفاضل والتكامل المسند من الدرجة الأولى" [ حجم وكسر مدى استيفاء الصيغ لحساب التفاضل والتكامل المسند من الدرجة الأولى ] . كيبرنتيكا . 5 (2): 17-27 .متوفر أيضاً بعنوان: "نطاق ودرجة إمكانية تحقيق الصيغ في حساب المسند المقيد". علم التحكم الآلي . 5 (2): 142-154 . 1972. doi : 10.1007/BF01071084 .
• ليبكين، ليونيد (2004). عناصر نظرية النموذج المحدود . سبرينغر . ISBN 3-540-21202-7.

• أبيتبول، سيرج ؛ هول، ريتشارد؛ فيانو، فيكتور (1995). أسس قواعد البيانات . أديسون-ويسلي . ISBN 0-201-53771-0.

• إيمرمان، نيل (1999). التعقيد الوصفي . نيويورك: سبرينغر . ISBN 0-387-98600-6.

• غرادل، إريك؛ كولايتيس، فوكيون ج.؛ ليبكين، ليونيد ؛ مارتن، ماركس؛ سبنسر، جويل ؛ فاردي، موشيه ي.؛ فينيما، يدي؛ وينشتاين، سكوت (2007). نظرية النموذج المحدود وتطبيقاتها . نصوص في علوم الحاسوب النظرية. سلسلة EATCS. ​​برلين: سبرينغر-فيرلاغ . ISBN 978-3-540-00428-8. Zbl 1133.03001 . 

• ليبكين، ليونيد (2009). "مجموعة أدوات نظرية النموذج المحدود لعالم قواعد البيانات". وقائع ندوة ACM SIGACT–SIGMOD الثامنة والعشرين حول مبادئ أنظمة قواعد البيانات (PODS 2009) . الصفحات 65-76 . doi : 10.1145/1559795.1559807 .  كما أنها مناسبة كمقدمة عامة ونظرة عامة.
• ليونيد ليبكين. الفصل التمهيدي من كتاب "عناصر نظرية النموذج المحدود" مؤرشف بتاريخ 24-09-2015 على موقع Wayback Machine . يحفز هذا الفصل ثلاثة مجالات تطبيق رئيسية: قواعد البيانات، والتعقيد، واللغات الرسمية.
• جوكو فانانين. دورة قصيرة حول نظرية النموذج المحدود . قسم الرياضيات، جامعة هلسنكي. بناءً على محاضرات من عام 1993 إلى عام 1994.
• أنوج داوار. نظرية النموذج اللانهائي والمحدود ، شرائح، جامعة كامبريدج، 2002.
• "نظرية النموذج الخوارزمي" . جامعة آخن التقنية. مؤرشف من الأصل بتاريخ 17 يوليو 2012. تم الاطلاع عليه بتاريخ 7 نوفمبر 2013 .يتضمن قائمة بمشاكل FMT المفتوحة.