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

დალაგების და მესრების თეორიაში, **კლინის უძრავი წერტილის თეორემა**, რომელიც ატარებს ამერიკელი მათემატიკოსის სტივენ კოულ კლინის, სახელს, შემდეგნაირია:
:*ვთქვათ (L, \leq) სრული ნაწილობრივი დალაგებაა (CPO), და  f:L\rightarrow L არის სკოტის აზრით უწყვეტი (და მაშასადამე მონოტონური) ფუნქცია. მაშინ f-ს გააჩნია უმცირესი უძრავი წერტილი, რომელიც არის f-ის შესაბამისი **კლინის აღმავალი ჯაჭვის** სუპრემუმი.

f-ის შესაბამისი **კლინის აღმავალი ჯაჭვი**  არის ჯაჭვი

:\bot \; \sqsubseteq \; f(\bot) \; \sqsubseteq \; f\left(f(\bot)\right) \; \sqsubseteq \; \dots \; \sqsubseteq \; f^n(\bot) \; \sqsubseteq \; \dots

შედგენილი f-ის იტერაციებით L-ის უმცირეს ელემენტზე \bot.

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

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

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

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

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

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

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

თავდაპირველად ვაჩვენოთ, რომ m უძრავი წერტილია, სხვა სიტყვებით f(m) = m. რადგან f არის სკოტის აზრით უწყვეტი , f(\sup(\mathbb{M})) = \sup(f(\mathbb{M})), რაც იგივეა რაც f(m) = \sup(f(\mathbb{M})). რადგანაც  f(\mathbb{M}) = \mathbb{M}\setminus\{\bot\} და ასევე რადგან \bot არ ღებულობს მონაწილეობას სუპრემუმის დადგენისას, გვაქვს \sup(f(\mathbb{M})) = \sup(\mathbb{M}). აქედან კი f(m) = m, რაც იმას ნიშნავს რომ m არის f-ის უძრავი წერტილი.

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

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

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

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

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