✖

ความสัมพันธ์อันดับ

ความสัมพันธ์อันดับ (order relation) คือความสัมพันธ์ทวิภาคบนเซตที่มีสมบัติสะท้อน ปฏิสมมาตร และถ่ายทอด

ตัวอย่างนำ

การเรียงอันดับเป็นแนวคิดที่ใช้ในชีวิตประจำวันด้วย หลายสิ่งนำมาเรียงอันดับได้ เช่น เรียงคำตามตัวอักษร เรียงนักเรียนตามความสูง เรียงสินค้าตามราคา ทั้งหมดนี้อธิบายด้วยความสัมพันธ์อันดับ ซึ่งมักเขียนแทนด้วยสัญลักษณ์ ≤ สัญลักษณ์ที่เกี่ยวข้องคือ < > และ ≥ ซึ่งความหมายชัดเจนอยู่แล้ว

เราคาดหวังอะไรจากความสัมพันธ์แบบนี้ จากสัญลักษณ์ก็เห็นได้ว่าในความสัมพันธ์อันดับจะมีสมาชิกที่เท่ากันด้วย นั่นคือต้องการนิยามสมบัติของความสัมพันธ์น้อยกว่าหรือเท่ากับ ความสัมพันธ์นี้จึงควรมีสมบัติสะท้อน ต้องได้ว่า a ≤ a

ต่อไปเป็นอย่างไร สมบัติสมมาตรย่อมไม่เป็นจริง ถ้าเรียงตามราคา เมื่อรถยนต์ถูกกว่าขนมปัง ขนมปังย่อมไม่ถูกกว่ารถยนต์ด้วย ในกรณีทั่วไป ถ้าเกิดกรณีที่ a ≤ b และ b ≤ a เราจะคาดหวังอะไร มีกรณีใดที่สมเหตุสมผลหรือไม่ มี ถ้า a = b กรณีเดียวที่ลำดับของสมาชิกในความสัมพันธ์ไม่สำคัญ คือเมื่อสมาชิกเหล่านั้นเท่ากัน ความสัมพันธ์อันดับจึงมีสมบัติปฏิสมมาตร

สุดท้าย ถ้ารู้ว่ารถยนต์แพงกว่าขนมปัง และเครื่องบินแพงกว่ารถยนต์อีก ย่อมคาดหวังว่าเครื่องบินแพงกว่าขนมปังแน่นอน ข้อนี้อธิบายด้วยสมบัติถ่ายทอด

อันดับบางส่วน

สิ่งที่นิยามไปเมื่อสักครู่เป็นเพียงอันดับบางส่วน (partial order) ไม่ใช่อันดับทุกส่วน ทำไมจึงไม่ใช่อันดับทุกส่วน ลองนิยามอันดับบนเซตดู จะเปรียบเทียบเซตสองเซตได้อย่างไร

กล่าวว่าเซต A น้อยกว่าหรือเท่ากับเซต B ถ้า A ⊆ B นั่นคือ A เป็นสับเซตของ B ซึ่งสมเหตุสมผล เพราะถ้า A = {1, 2} และ B = {1, 2, 3} ก็กล่าวได้ว่า A น้อยกว่า — B มีสมาชิกเหมือนกับ A และยังมีจำนวนสามเพิ่มมาอีก ดังนั้นจะได้ เช่น

  • {a, c} ≤ {a, b, c, d}
  • ∅ ≤ {5, n, x}
  • {x, e, s} ≤ {x, e, s}

แต่ปัญหาเกิดขึ้นเมื่อต้องการเปรียบเทียบเซตต่อไปนี้ A = {a, b} และ B = {a, c} เซตใดน้อยกว่าหรือมากกว่า ปัญหาคือแม้ทั้งสองเซตมีสมาชิก a แต่สมาชิกตัวที่สองต่างกัน ไม่มีเซตใดเป็นสับเซตของอีกเซตหนึ่ง จึงไม่ได้ทั้ง A ≤ B และ B ≤ A เซตเหล่านี้เปรียบเทียบกันไม่ได้ด้วยอันดับของเรา

ดังนั้นจึงนิยามเซตอันดับทุกส่วน (totally ordered set) หรือโซ่ (chain) ว่าเป็นเซตที่สมาชิกทุกสองตัวเปรียบเทียบกันได้ เช่น เซตของจำนวนที่มีอันดับตามปกติ สำหรับจำนวนจริง a และ b ใด ๆ ตัดสินได้เสมอว่า a ≤ b หรือ b ≤ a

ตัวอย่างจากชีวิตประจำวัน

ตัวอย่างที่ไม่ควรเปรียบเทียบคือการเรียงอันดับตามความสวยงาม ความสัมพันธ์ < จะหมายถึง “หน้าตาด้อยกว่า” หรืออาจควรนิยามกลับกัน ให้ > หมายถึง “หน้าตาดีกว่า” จะได้สุภาพกว่า :-) การเปรียบเทียบผู้หญิงสองคนอาจสมเหตุสมผล เช่น “นภา” < “ดารินทร์” ในความหมายว่าดารินทร์หน้าตาดีกว่านภา หรือผู้ชายสองคน “ภูผา” < “ธีรภัทร” ในความหมายว่าธีรภัทรหน้าตาดีกว่าภูผา (ทั้งสี่คนเป็นดาราสมมติ)

ปัญหาคือการเปรียบเทียบความหล่อของผู้ชายกับความสวยของผู้หญิงทำได้ยาก ดารินทร์หรือธีรภัทรหน้าตาดีกว่ากัน นภาหรือภูผาหน้าตาด้อยกว่ากัน ไม่ถามดีกว่า…

ถ้าในตัวอย่างสุดท้ายจำกัดไว้เฉพาะผู้หญิง ก็กล่าวได้ว่าได้เซตอันดับทุกส่วน เพราะเปรียบเทียบความสวยของผู้หญิงทุกคนได้

สมาชิกเล็กสุดเฉพาะกลุ่มและใหญ่สุดเฉพาะกลุ่ม สมาชิกน้อยที่สุดและมากที่สุด

ถ้า M เป็นเซตอันดับ สมาชิก min ∈ M เรียกว่าสมาชิกเล็กสุดเฉพาะกลุ่ม (minimal element) ถ้าไม่มี x ∈ M ที่ x < min นั่นคือหาสมาชิกที่น้อยกว่าสมาชิก min ไม่ได้

สมาชิก max ∈ M เรียกว่าสมาชิกใหญ่สุดเฉพาะกลุ่ม (maximal element) ถ้าไม่มี x ∈ M ที่ x > max นั่นคือหาสมาชิกที่มากกว่าไม่ได้

แนวคิดสองข้อข้างต้นต่างจากแนวคิดสมาชิกน้อยที่สุดและสมาชิกมากที่สุด

สมาชิก a ∈ M เรียกว่าสมาชิกน้อยที่สุด (least element) ถ้าสำหรับทุก x ∈ M จะได้ว่า a ≤ x นั่นคือสมาชิกน้อยที่สุด a น้อยกว่าหรือเท่ากับสมาชิกอื่นทุกตัวในเซต M

สมาชิก b ∈ M เรียกว่าสมาชิกมากที่สุด (greatest element) ถ้าสำหรับทุก x ∈ M จะได้ว่า b ≥ x สมาชิกมากที่สุด b มากกว่าหรือเท่ากับสมาชิกอื่นทุกตัวในเซต M

สมาชิกมากที่สุดกับสมาชิกใหญ่สุดเฉพาะกลุ่มต่างกันอย่างไร สมาชิกใหญ่สุดเฉพาะกลุ่มอาจมีหลายตัว เพราะเซตไม่จำเป็นต้องเป็นเซตอันดับทุกส่วน ถ้ากลับไปที่ตัวอย่างการเปรียบเทียบคนตามหน้าตา อาจกล่าวได้ว่าดาราสาวสมมติชื่อแพรวาสวยที่สุดในบรรดาผู้หญิง และดาราหนุ่มสมมติชื่อกันต์หล่อที่สุดในบรรดาผู้ชาย แต่สองคนนี้เปรียบเทียบกันไม่ได้ เราไม่รู้ว่าแพรวาหรือกันต์หน้าตาดีกว่ากัน

ทั้งสองคนจึงเป็นสมาชิกใหญ่สุดเฉพาะกลุ่ม หาคนที่หน้าตาดีกว่ากันต์ไม่ได้ — กันต์หล่อกว่าผู้ชายคนอื่นทุกคน และเปรียบเทียบกับผู้หญิงไม่ได้ แพรวาก็ทำนองเดียวกัน — เธอสวยกว่าผู้หญิงทุกคน และเปรียบเทียบกับผู้ชายไม่ได้

แต่ไม่มีใครเป็นสมาชิกมากที่สุด ในความหมายว่าหน้าตาดีที่สุด เพราะถ้ากันต์จะหน้าตาดีที่สุดหรือเป็นสมาชิกมากที่สุด เขาต้องหน้าตาดีกว่าทุกคน รวมทั้งผู้หญิงทุกคนด้วย แต่เราบอกแล้วว่าเปรียบเทียบเขากับผู้หญิงไม่ได้ เขาจึงเป็นคนที่หน้าตาดีที่สุดไม่ได้ เป็นได้เพียงสมาชิกใหญ่สุดเฉพาะกลุ่มตามศัพท์ของทฤษฎีอันดับ

เห็นได้ไม่ยากว่าถ้าเซตมีสมาชิกมากที่สุด สมาชิกนั้นก็เป็นสมาชิกใหญ่สุดเฉพาะกลุ่มด้วย ถ้าสมาชิก a มากกว่าสมาชิกอื่นทุกตัวในเซต (นิยามของสมาชิกมากที่สุด) ย่อมหาสมาชิกที่มากกว่านั้นไม่ได้ (นิยามของสมาชิกใหญ่สุดเฉพาะกลุ่ม)

ตัวอย่างเซตที่มีทั้งสมาชิกมากที่สุดและน้อยที่สุด เช่น ช่วงปิด [0, 1] ถ้าเลือกช่วงเดียวกันแต่เป็นช่วงเปิด จะไม่มีทั้งสมาชิกมากที่สุดและน้อยที่สุด: (0, 1)

ถ้าต้องการสมาชิกเล็กสุดเฉพาะกลุ่มมากมายไม่จำกัด อาจนิยามอันดับ R ดังนี้ ขั้นแรกนิยามเซตช่วย Mx ในรูปต่อไปนี้ สำหรับทุก x ในช่วง (0, 1) นิยามเซต Mx = {y | y = x + n} เมื่อ n เป็นจำนวนเต็มที่ไม่เป็นลบ จะได้เซต เช่น:

M0.5={0.5,1.5,2.5,3.5,…}M0.7={0.7,1.7,2.7,3.7,…}M0.8={0.8,1.8,2.8,3.8,…}

บนเซต Mx แต่ละเซตนิยามอันดับตามปกติ เขียนแทนด้วย Rx สุดท้ายนำอันดับเหล่านี้มายูเนียนกัน R = ∪ Rx ในอันดับนี้เปรียบเทียบได้เฉพาะภายในโซ่เดิมเท่านั้น ตรวจได้ว่า 0.5 ≤ 2.5 หรือไม่ แต่ตรวจไม่ได้ว่า 0.5 ≤ 2.7 หรือไม่ เพราะจำนวนทั้งสองไม่ได้อยู่ในเซต Mx เดียวกัน จึงไม่ได้นิยามความสัมพันธ์ระหว่างกันไว้

ในความสัมพันธ์อันดับนี้ สมาชิกทุกตัวในช่วง (0, 1) เป็นสมาชิกเล็กสุดเฉพาะกลุ่ม

แผนภาพฮาสเซอ

เซตอันดับวาดได้ด้วยแผนภาพฮาสเซอ (Hasse diagram) ซึ่งเป็นกราฟที่จุดยอดแทนสมาชิกของเซต และเส้นเชื่อมระหว่างจุดยอด (a, b) บอกว่า a < b และไม่มี c ที่ a < c < b นั่นคือไม่มีสมาชิกอื่นอยู่ระหว่างสมาชิก a และ b นอกจากนี้ในกราฟจุดยอด a ต้องอยู่ต่ำกว่าจุดยอด b ตัวอย่างแผนภาพฮาสเซอ:

แผนภาพฮาสเซอ

แผนภาพฮาสเซอนี้แสดงเซตอันดับ {A, B, C, D, E, F} ซึ่ง A < B B < E และย่อมได้ A < E ด้วย แต่ระหว่างจุดยอดสองจุดนี้ไม่มีเส้นเชื่อม เพราะมีจุดยอด B ที่ A < B < E สมาชิก E และ D เปรียบเทียบกันไม่ได้ เพราะไม่มีตัวใดอยู่เหนือหรือใต้อีกตัวหนึ่ง

แม้แผนภาพฮาสเซอมักวาดให้เป็นระเบียบสวยงามแบบนี้ แต่ก็ไม่ใช่ข้อบังคับ แผนภาพฮาสเซอข้างต้นอาจวาดได้แบบนี้ด้วย:

แผนภาพฮาสเซอที่ไม่สวย

อีกตัวอย่างหนึ่งคือเซต A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} ซึ่งเป็นตัวประกอบที่เป็นบวกของ 60 อันดับตามการหารลงตัวแสดงได้ดังนี้:

เซตที่เรียงอันดับตามการหารลงตัว

อันดับตามการหารลงตัวหมายความว่า (a, b) ∈ R ก็ต่อเมื่อ a หาร b ลงตัว จากแผนภาพจะเห็นว่าเหนือจำนวนแต่ละจำนวนมีจำนวนที่จำนวนนั้นหารลงตัว เช่น เหนือ 6 มี 12 30 และ 60 เหนือ 4 มี 12 20 และ 60 เป็นต้น ในทางกลับกัน เหนือ 3 ไม่มี 10 เพราะ 3 หาร 10 ไม่ลงตัว — ระวัง ในภาพ 10 อยู่สูงกว่า 3 แต่ไม่มีเส้น “จากล่างขึ้นบน” ไปถึง ถ้าเริ่มจาก 3 และเคลื่อนที่ขึ้นเท่านั้น จะไปที่ 15 และ 6 ได้ แล้วจากสองจำนวนนั้นไปที่ 30 จะไปถึง 10 ได้ก็ต่อเมื่อเดินลง ซึ่งทำไม่ได้

สารบัญ: ความสัมพันธ์, การดำเนินการของความสัมพันธ์, ความสัมพันธ์ทวิภาค, ความสัมพันธ์ทวิภาคบนเซต, ความสัมพันธ์สมมูล, ความสัมพันธ์อันดับ, แลตทิซ