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

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

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

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

⊥ ⊑ f (⊥) ⊑ f (f (⊥)) ⊑ \dots ⊑ f^{n} (⊥) ⊑ \dots

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

სიმოკლისათვის:

lfp (f) = \sup ({f^{n} (⊥) ∣ n \in ℕ})

სადაც $lfp$ აღნიშნავს უმცირეს უძრავ წერტილს.

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

დამტკიცება

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

ლემა 1:თუ $L$ არის CPO, და $f : L \to L$ სკოტის აზრით უწყვეტია, მაშინ $f^{n} (⊥) ⊑ f^{n + 1} (⊥), n \in ℕ_{0}$

დავამტკიცოთ ინდუქციით $n$ -ის მიმართ:

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

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

ვთქვათ $𝕄$ არის ჯაჭვის ელემენტთა სიმრავლე: $𝕄 = {⊥, f (⊥), f (f (⊥)), \dots}$ . ლემა 1-დან გამომდინარეობს რომ ჯაჭვი არის მიმართული $ω$ -ჯაჭვი. CPO-ს გამნარტებიდან გამომდინარეობს რომ ამ სიმრავლეს აქვს სუპრემუმი, ავღნიშნოთ ის $m$ -ით. საჩვენებელი დარჩა მხოლოდ ის, რომ $m$ უმცირესი უძრავი წერტილია.

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

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

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

იხილეთ აგრეთვე

კნასტერ-ტარსკის თეორემა

ლიტერატურა

S.C. Kleene "Introduction to Metamathematics (Bibliotheca Mathematica)" 1952 ISBN-13: 978-0923891572