იხილეთ წყარო გვერდისთვის კლინის თეორემა უძრავი წერტილის შესახებ

[[order theory|დალაგების]] და [[მესრებისთეორია|მესრების თეორიაში]], '''კლინის უძრავი წერტილის თეორემა''', რომელიც ატარებს ამერიკელი მათემატიკოსის [[სტივენ კოულ კლინი]]ს, სახელს, შემდეგნაირია:
:''ვთქვათ <math>(L, \leq)</math> [[სრული ნაწილობრივი დალაგება | სრული ნაწილობრივი დალაგებაა (CPO)]], და  <math>f:L\rightarrow L</math> არის სკოტის აზრით უწყვეტი (და მაშასადამე [[მონოტონური ფუნქცია|მონოტონური]]) [[ფუნქცია (მათემატიკა)|ფუნქცია]]. მაშინ <math>f</math>-ს გააჩნია [[უძრავი წერტილი | უმცირესი უძრავი წერტილი]], რომელიც არის <math>f</math>-ის შესაბამისი '''კლინის აღმავალი ჯაჭვის''' [[სუპრემუმი]].

<math>f</math>-ის შესაბამისი '''კლინის აღმავალი ჯაჭვი'''  არის [[ჯაჭვი (დალაგების თეორია) | ჯაჭვი]]

:<math>\bot \; \sqsubseteq \; f(\bot) \; \sqsubseteq \; f\left(f(\bot)\right) \; \sqsubseteq \; \dots \; \sqsubseteq \; f^n(\bot) \; \sqsubseteq \; \dots</math>

შედგენილი <math>f</math>-ის იტერაციებით <math>L</math>-ის [[უმცირეს ელემენტზე]] <math>\bot</math>.

სიმოკლისათვის:
:<math>\textrm{lfp}(f) = \sup \left(\left\{f^n(\bot) \mid n\in\mathbb{N}\right\}\right)</math>
სადაც <math>\textrm{lfp}</math> აღნიშნავს უმცირეს უძრავ წერტილს.

ამ შედეგს ხშირად [[ალფრედ ტარსკი]]ს მიაწერენ, მაგრამ [[ტარსკის უძრავი წერტილი თეორემა]] შეეხება [[მონოტონურ ფუნქცია |მონოტონურ ფუნქციებს]] სრულ მესრებზე.

== დამტკიცება ==

ჯერ ვაჩვენოთ <math>f</math>-ის შესბამისი კლინის ჯაჭვის არსებობა <math>L</math>-ში. ამისათვის დავამტკიცოთ შემდეგი ლემა:

:ლემა 1:''თუ <math>L</math> არის CPO, და <math>f:L\rightarrow L</math> სკოტის აზრით უწყვეტია, მაშინ <math>f^n(\bot) \sqsubseteq f^{n+1}(\bot), n \in \mathbb{N}_0</math>

დავამტკიცოთ ინდუქციით <math>n</math>-ის მიმართ: 
* დავუშვათ <math>n = 0 </math>. მაშინ <math>f^0(\bot) = \bot \sqsubseteq f^1(\bot)</math>, რადგან <math>\bot </math> უმცირესი ელემენტია.
* დავუშვათ <math>n > 0 </math>. საჩვენებელია რომ <math>f^n(\bot) \sqsubseteq f^{n+1}(\bot)</math>. ინდუქციის დაშვებით გვაქვს <math>f^{i-1}(\bot) \sqsubseteq f^i(\bot), i\leq n </math>. რადგან <math>f</math> მონოტონურია სამართლიანია <math>f(f^{n-1}(\bot)) \sqsubseteq f(f^n(\bot))</math> რისი ჩვენებაც გვინდოდა.

ლემიდან უშუალოდ გამომდინარეობს კლინის ჯაჭვის არსებობა.

ვთქვათ <math>\mathbb{M}</math> არის ჯაჭვის ელემენტთა სიმრავლე: <math>\mathbb{M} = \{ \bot, f(\bot), f(f(\bot)), \ldots\}</math>. '''ლემა 1'''-დან გამომდინარეობს რომ ჯაჭვი არის მიმართული <math>\omega</math> -ჯაჭვი. CPO-ს გამნარტებიდან გამომდინარეობს რომ ამ სიმრავლეს აქვს სუპრემუმი, ავღნიშნოთ ის  <math>m</math>-ით. საჩვენებელი დარჩა მხოლოდ ის, რომ <math>m</math> უმცირესი უძრავი წერტილია.

თავდაპირველად ვაჩვენოთ, რომ <math>m</math> უძრავი წერტილია, სხვა სიტყვებით <math>f(m) = m</math>. რადგან <math>f</math> არის [https://en.wikipedia.org/wiki/Scott_continuity  სკოტის აზრით უწყვეტი ], <math>f(\sup(\mathbb{M})) = \sup(f(\mathbb{M}))</math>, რაც იგივეა რაც <math>f(m) = \sup(f(\mathbb{M}))</math>. რადგანაც  <math>f(\mathbb{M}) = \mathbb{M}\setminus\{\bot\}</math> და ასევე რადგან <math>\bot</math> არ ღებულობს მონაწილეობას სუპრემუმის დადგენისას, გვაქვს <math>\sup(f(\mathbb{M})) = \sup(\mathbb{M})</math>. აქედან კი <math>f(m) = m</math>, რაც იმას ნიშნავს რომ <math>m</math> არის <math>f</math>-ის უძრავი წერტილი.

იმის საჩვენებლად რომ <math>m</math> სინამდვილეში '''უმცირესი უძრავი წერტილია''' საკმარისია ვაჩვენოთ რომ <math>\mathbb{M}</math> სიმრავლის ყველა ლემენტი ნაკლებია ვიდრე <math>f</math>-ის ნებისმიერი უძრავი წერტილი (რადგან სუპრემუმის (უმცირესი ზედა საზღვრის) განმარტებიდან, თუ ყველა ელემენტი სიმრავლიდან <math>D \subseteq L</math> ნაკლებია ვიდრე  <math>L</math> სიმრავლის რაიმე დაფიქსირებული ელემენტი <math>l</math>, მაშინ <math>\sup(D)</math> ასევე ნალებია ვიდრე <math>l</math>).

ვაჩვენოთ ეს ინდუქციის საშუალებით: დავუშვათ <math>k</math> არის <math>f</math>-ის რაიმე უძრავი წერტილი. დავამტკიცოთ ინდუქციით <math>i</math>-ს მიმართ რომ <math>\forall i \in \mathbb{N}\colon f^i(\bot) \sqsubseteq k</math>. ავიღოთ <math>i = 0</math>: <math>f^0(\bot) = \bot \sqsubseteq k</math> ცხადია სრულდება, რადგან <math>\bot</math> უმცირესი ელემენტია <math>L</math>-ში. ინდუქციის დაშვებად ავიღოთ <math>f^i(\bot) \sqsubseteq k</math>. ინდუქციის ბიჯი: ინდუქციის დაშვებიდან და <math>f</math>-ის მონოტონურობიდან, შეგვიძლია მივიღოთ შემდეგი: <math>f^i(\bot) \sqsubseteq k \implies f^{i+1}(\bot) \sqsubseteq f(k)</math>. რადგანაც <math>k</math> არის <math>f</math>-ის უძრავი წერტილი, გვაქვს <math>f(k) = k</math>, საიდანაც ვღებულობთ <math>f^{i+1}(\bot) \sqsubseteq k</math>.

==იხილეთ აგრეთვე==
* [[კნასტერ-ტარსკის თეორემა]]

==ლიტერატურა==
*S.C. Kleene "Introduction to Metamathematics (Bibliotheca Mathematica)" 1952 ISBN-13: 978-0923891572

[[კატეგორია:დალაგების თეორია]]
[[კატეგორია:თეორემები უძრავი წერტილის შესახებ]]