نظرية كلين للنقطة الثابتة

في المجالات الرياضية لنظرية الترتيب والشبكة ، تنص نظرية النقطة الثابتة لكلين ، التي سميت على اسم عالم الرياضيات الأمريكي ستيفن كول كلين ، على ما يلي:

نظرية كلين للنقطة الثابتة. لنفترض${\displaystyle (L,\sqsubseteq )}$هي ترتيب جزئي موجه كامل (dcpo) مع عنصر أصغر، ولتكن${\displaystyle f:L\to L}$لتكن دالة متصلة من نوع سكوت (وبالتالي رتيبة ) . إذن${\displaystyle f}$لها نقطة ثابتة دنيا ، وهي القيمة العليا لسلسلة كلين الصاعدة لـ${\displaystyle f.}$

سلسلة كلين التصاعدية لـ f هي السلسلة

${\displaystyle \bot \sqsubseteq f(\bot )\sqsubseteq f(f(\bot ))\sqsubseteq \cdots \sqsubseteq f^{n}(\bot )\sqsubseteq \cdots }$

يتم الحصول عليها بتكرار الدالة f على أصغر عنصر ⊥ من L. وتنص النظرية، بصيغة رياضية، على ما يلي:

${\displaystyle {\textrm {lfp}}(f)=\sup \left(\left\{f^{n}(\bot )\mid n\in \mathbb {N} \right\}\right)}$

أين${\displaystyle {\textrm {lfp}}}$يشير إلى أصغر نقطة ثابتة.

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

المصدر: ^{[ 3 ]}

علينا أولاً أن نبين أن سلسلة كلين الصاعدة من${\displaystyle f}$موجود في${\displaystyle L}$ولإثبات ذلك، نبرهن على ما يلي:

اللمة. إذا${\displaystyle L}$هو خوارزمية DCPO ذات عنصر أصغر، و${\displaystyle f:L\to L}$إذا كانت متصلة من نوع سكوت، فإن${\displaystyle f^{n}(\bot )\sqsubseteq f^{n+1}(\bot ),n\in \mathbb {N} _{0}}$

البرهان. نستخدم الاستقراء:

• لنفترض أن n = 0. إذن${\displaystyle f^{0}(\bot )=\bot \sqsubseteq f^{1}(\bot ),}$منذ${\displaystyle \bot }$هو العنصر الأصغر.
• لنفترض أن n > 0. عندئذٍ علينا أن نثبت أن${\displaystyle f^{n}(\bot )\sqsubseteq f^{n+1}(\bot )}$بإعادة الترتيب نحصل على${\displaystyle f(f^{n-1}(\bot ))\sqsubseteq f(f^{n}(\bot ))}$بناءً على الافتراض الاستقرائي، نعلم أن${\displaystyle f^{n-1}(\bot )\sqsubseteq f^{n}(\bot )}$ويصدق هذا، ولأن f رتيبة (خاصية الدوال المتصلة سكوت)، فإن النتيجة صحيحة أيضاً.

وكنتيجة طبيعية للفرضية، لدينا سلسلة ω الموجهة التالية:

${\displaystyle \mathbb {M} =\{\bot ,f(\bot ),f(f(\bot )),\ldots \}.}$

يستنتج من تعريف أمر الحماية من العنف المنزلي ما يلي:${\displaystyle \mathbb {M} }$له قيمة عليا، فلنسميها كذلك${\displaystyle m.}$ما تبقى الآن هو إثبات ذلك${\displaystyle m}$هي أقل نقطة ثابتة.

أولاً، سنوضح أن${\displaystyle m}$هي نقطة ثابتة، أي أن${\displaystyle f(m)=m}$. لأن${\displaystyle f}$هل هي متصلة سكوت ،${\displaystyle f(\sup(\mathbb {M} ))=\sup(f(\mathbb {M} ))}$، إنه${\displaystyle f(m)=\sup(f(\mathbb {M} ))}$أيضًا، بما أن${\displaystyle \mathbb {M} =f(\mathbb {M} )\cup \{\bot \}}$ولأن${\displaystyle \bot }$ليس له أي تأثير في تحديد القيمة العليا التي لدينا:${\displaystyle \sup(f(\mathbb {M} ))=\sup(\mathbb {M} )}$ويترتب على ذلك أن${\displaystyle f(m)=m}$، تحضير${\displaystyle m}$نقطة ثابتة من${\displaystyle f}$.

الدليل على ذلك${\displaystyle m}$في الواقع، يمكن إيجاد أصغر نقطة ثابتة من خلال إثبات أن أي عنصر في${\displaystyle \mathbb {M} }$أصغر من أي نقطة ثابتة لـ${\displaystyle f}$(لأنه بحسب خاصية القيمة العليا ، إذا كانت جميع عناصر المجموعة${\displaystyle D\subseteq L}$أصغر من عنصر من${\displaystyle L}$ثم أيضًا${\displaystyle \sup(D)}$أصغر من نفس العنصر من${\displaystyle L}$يتم ذلك عن طريق الاستقراء: افترض${\displaystyle k}$هي نقطة ثابتة من${\displaystyle f}$نثبت الآن بالاستقراء على${\displaystyle i}$الذي - التي${\displaystyle \forall i\in \mathbb {N} :f^{i}(\bot )\sqsubseteq k}$أساس الاستقراء${\displaystyle (i=0)}$من الواضح أن هذا ينطبق على:${\displaystyle f^{0}(\bot )=\bot \sqsubseteq k,}$منذ${\displaystyle \bot }$هو العنصر الأقل من${\displaystyle L}$كفرضية استقراء، يمكننا أن نفترض أن${\displaystyle f^{i}(\bot )\sqsubseteq k}$ننتقل الآن إلى خطوة الاستقراء: انطلاقًا من فرضية الاستقراء ورتابة${\displaystyle f}$(مرة أخرى، يُستدل على ذلك من خلال استمرارية سكوت لـ${\displaystyle f}$)، يمكننا أن نستنتج ما يلي:${\displaystyle f^{i}(\bot )\sqsubseteq k~\implies ~f^{i+1}(\bot )\sqsubseteq f(k).}$الآن، بافتراض أن${\displaystyle k}$هي نقطة ثابتة لـ${\displaystyle f,}$نحن نعلم ذلك${\displaystyle f(k)=k,}$ومن ذلك نحصل على${\displaystyle f^{i+1}(\bot )\sqsubseteq k.}$

• نظريات أخرى حول النقطة الثابتة