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

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

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