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

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

ვთქვათ $(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