ว่าด้วยเรื่อง complete lattice and fixpoint theory -- Logic Programming

โพสนี้อยู่ในหมวด เรียนรู้ logic programming + argumentation นะคะ
ก่อนอื่น เรามารู้จักคำว่า order กันก่อน  ซึ่ง order ก็คือการที่เราสามารถเปรียบเทียบสิ่งของสิ่งได้
เช่น 0 น้อยกว่า 1 หรือ ดาวอังคารอยู่ห่างจากดวงอาทิตย์ มากกว่าที่อยู่ห่างจากโลก

คิดว่าทุกคนคงทราบความหมายของ set กับ relation กันดีอยู่แล้ว ซึ่ง order เองก็คือ relation ประเภทหนึ่ง  

ทีนี้เรามาดูนิยามของคำว่า partial order ซึ่งคือ relation ที่จะต้องมีคุณสมบัติ
- reflexive (มีการเปรียบเทียบตัวเองกับตัวเอง)
- antisymmetric (ถ้าลำดับ X น้อยกว่า Y แล้วลำดับ Y ต้องไม่น้อยกว่า X  แต่ถ้าเกิดพบกว่าลำดับของ X น้อยกว่า Y และลำดับของ Y ก็น้อยกว่า X แสดงว่า Xและ Y นั้นคือค่าเดียวกัน)
-transitive (ถ้าลำดับของ X น้อยกว่า Y, ลำดับของ Y น้อยกว่า Z แล้วลำดับของ X ต้องน้อยกว่าลำดับของ Z)

ตัวอย่างของ partial order ก็อย่าง ความสัมพันธ์ของ subset  หรือการเปรียบเทียบ น้อยกว่าหรือเท่ากับของตัวเลขจำนวนเต็ม
เช่น {(1,1),(1,2),(2,2),(2,3)} ก็จะเห็นว่า  1 ≤ 1 , 1 ≤ 2,  2 ≤ 2 , 2 ≤ 3

ทีนี้เรามาทำความรู้จัก upper bound กันดีกว่านะคะ
ถ้าเรามี partial order สมมติชื่อว่า S เราดึงแค่ subset ของเซต S นี้ออกมา สมมติให้ชื่อ subset นี้ว่า X แล้วพบว่า สมาชิกทุกตัวใน X นี้มีค่าน้อยกว่าหรือเท่ากับ ค่าๆหนึ่งซึ่งเป็นสมาชิกของ S เช่นกัน เราจะเรียกค่านั้นว่า upper bound
ยกตัวอย่าง เช่นถ้าเรามีค่า A,B,C ซึ่ง  A  ≤ B ≤ C
แล้วเรามี {A , B, C} ถ้าถามว่า upper bound ของ { A } คือค่าอะไร ก็สามารถตอบได้ว่าคือ A, B , C
และในบรรดา upper bound ทั้งหมด upper bound ที่มีค่าน้อยที่สุด คือ  least upper bound
ดังนั้นจากตัวอย่างนี้ least upper bound คือ A

ถ้าเราต้องการหา lower bound ก็คล้ายๆกันเปลี่ยนแค่จากน้อยกว่าเป็นมากกว่า  จะได้ว่าถ้าพบว่า สมาชิกทุกตัวใน X นี้มีค่ามากกว่าหรือเท่ากับ ค่าๆหนึ่งซึ่งเป็นสมาชิกของ S เราจะเรียกค่านั้นว่า lower bound และในบรรดา lower bound ทั้งหมด lower bound ที่มีค่ามากที่สุด จะเรียกว่า greatest lower bound
จากตัวอย่างนี้ ถ้าถามว่าlower bound ของ{ A} คือค่าอะไร lower bound คือ A และ greatest lower bound ก็คือ A
ในขณะที่ lower bound ของ {B} = A, B และ greatest lower bound ก็คือ B

ทีนี้ถ้าเรามีเซต S ใดๆ แล้วเราหา power set of S  ( 2^S) ก็จะเห็นว่า 2^S  มีคุณสมบัติเป็น partial order 
ยกตัวอย่างเช่น S = {A,B} ดังนั้น = {∅, A, B, {A,B} } เป็น partial order เพราะ   ∅ ⊆ {A}⊆ {B}  ⊆ {A,B}

ก่อนจะไปหา lower bound, upper bound   ของ 2^S ขอยกตัวอย่างอีกสักตัวอย่าง
ถ้าเรามีเซต A , B สมมติว่า A ⊆C , B ⊆C
จะเห็นว่า C is upper bound of A , C is upper bound of B
ถ้าเราจับ A ∪ B   แล้ว จะพบว่า upper bound = A ∪ B , C  
และมี  least upper bound =  A ∪ B 

เช่นกันค่ะ เราจะได้ว่า ∅ is lower bound of A และ ∅ is lower bound of B

ถ้าเราจับ A ∩ B แล้ว lower bound of  = ∅, A ∩ B   
และมี greatest lower bound =  A ∩ B

จากแค่ทำกับสองเซต A,B ใช้หลักการเดียวกันไม่ว่าจะมีกี่เซต ซึ่งเราสามารถที่จะหาค่า least upper bound และ greatest lower bound ของทุกๆ subset of  2^S ได้ ซึ่งถ้าเรา หา intersection ของสมาชิกทุกตัวใน  2^S เราก็จะได้ greatest lower bound = ∅ และถ้าหา union ของสมาชิกทุกตัวใน  2^S  ก็จะได้ least upper bound = S นั่นเอง

ซึ่งถ้าเรามี partial order  L ใดๆ ที่สามารถหา least upper bound และ greatest lower bound ของทุกๆ subset ของ ของ order L นั้นได้ เราเรียกว่าคุณสมบัตินี้ว่า complete lattice

จากตัวอย่างข้างต้น เราก็เห็นกันแล้วนะคะว่า 2^S มีคุณสมบัติ complete lattice ทีนี้เราจะพูดถึง fix point theory กันบ้าง

fix point theory นิยามไว้ว่า ถ้าเรามี complete lattice ใดๆสมมติชื่อ L และมี mapping ให้ชื่อว่า T จากโดเมนคือ Lไปยังเรนจ์ คือ L  (T: L -> L) ณ จุดๆที่ เราใส่ค่า x ใดๆในโดเมนไปแล้ว map ได้ x เราจะเรียกค่า x นี้ว่า fix point of T พูดง่ายๆก็คือ ณ ตำแหน่งที่ T(x) = x นั่นเองค่ะ 

ทีนี้ fix point เนี่ย ก็มีได้หลายค่า เราก็จะเรียกค่า fix point ที่น้อยที่สุดในบรรดาค่า fix point ทั้งหมดว่า least fix point และเช่นกัน เราจะเรียกค่า fix point ที่มากที่สุดในบรรดาค่า fix point ทั้งหมดว่า greatest fix point

ทีนี้ เรากลับมาที่คำอธิบายเรื่อง complete lattice ของเรากันนะคะ เรารู้แล้วว่า 2^S มีคุณสมบัติ complete lattice แล้วถ้าเรามี mapping T: 2^S  -> 2^S ก็แสดงว่า ทั้ง input และ output (หรือโดเมนและเรนจ์) ของการ mapping นี้ จะมีคุณสมบัติ complete lattice แน่นอน เพราะว่ามันเป็น subset ของเซต ซึ่งก็จะทำให้เราสามารถหา greatest lower bound, least upper bound ได้เสมอ ซึ่งคุณสมบัติตรงนี้จะใช้อธิบายในหลายๆเรื่องของทฤษฎีในหนังสือ logic programming

ขอเล่าแถมอีกหน่อย เรื่อง fix point theory ว่าสำคัญไฉน
fix point เนี่ยมีความสำคัญในหลายๆแขนงของคณิตศาสตร์
เรารู้แล้วใช่ไหมคะว่า partial order คืออะไร และ complete lattice คืออะไรและเกี่ยวข้องกับ fix point ยังไง
ทีนี้เราลองมาดู fix point ในงานด้านอื่นบ้าง ถ้าเรามีจุด สองจุด บนแกน x,y อยากจะเทียบว่าจุดไหนใหญ่กว่า(ไม่แน่ใจว่าใช้คำว่าใหญ่กว่าจะดีไหม) วิธีการเทียบคือ ถ้า ค่าบนแกน x ของจุดแรกมากกว่าเท่ากับจุดสอง และ ค่าบนแกน y ของจุดแรกมากกว่าเท่ากับจุดสอง เราก็จะถือว่าจุดแรกใหญ่กว่า
อย่างเช่น จุด (2,2) ใหญ่กว่า จุด (1,1)

ทีนี้เราเทียบสองจุดได้แล้ว เราก็จะสามารถเทียบหลายๆจุดได้ใช่ไหมคะ เมื่อเราเทียบจุดหลายๆจุดได้ เราก็จัดลำดับเซตของจุดเหล่านี้ได้  และเราก็จะได้ partial order ใช่ไหมคะ เมื่อเราได้  partial order ของความสัมพันธ์ของจุดบนระนาบ x,y  (ซึ่ง ณ จุดนี้ก็คล้ายกับความสัมพันธ์ subset ของเซตแล้ว) ต่อไปเราก็จะพบว่ามันมีคุณสมบัติ complete lattice แล้วเราก็จะหา fix point ได้

คำถามคือเราจะหา fix point ของจุดไปทำไม ?

ถ้ายังจำได้ คณิตศาสตร์ที่เราเคยเรียนสมัยมัธยม เราจะหาจุดตัด (0,0) ซึ่งเราสามารถจะมองว่าคือ fix point ได้ นี่ก็คือ application นึงของ fix point ค่ะ และไม่ใช่แค่จุดบนระนาบ x,y เราสามารถจะเทียบบน สามมิติ x,y,z หรือ n-dimension ก็ได้

ซึ่งในระบบ dynamic ต่างๆ เราย่อมจะอยากหาเงื่อนไขที่ทำให้มัน stable เราก็นำเอา fix point theory เข้าไปใช้ ไม่ว่าจะเป็น งานด้าน machine vision , computer graphic ก็จะเห็นว่ามีทฤษฎี fix point ค่ะ

รวมถึง สมการ หรือ equation ที่เรารู้จักกันดี นั่นก็คือรูปแบบนึงของ fix point เช่นกัน
เช่น

 เรารู้จักกันในรูปแบบของสมการ ที่เราจะต้องการหาค่าตัวแปร X ว่ามีค่าเท่าไหร่
ซึ่งถ้าเรามองสมการเป็น    

ใช่ไหมคะ

ถ้าเรากำหนดให้   

เราจะพบว่า มันก็คือ fix point ที่เราจะหาจุดที่ f(X)=X นั่นเองค่ะ

หวังว่าคงจะเห็นความสำคัญและเข้าใจทฤษฎี fixpoint มากขึ้นและอ่านหนังสือ logic programming ได้เข้าใจยิ่งขึ้นนะคะ :)