✖

ความสัมพันธ์สมมูล

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

ตัวอย่างนำ

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

เราคาดหวังอะไรจากความสัมพันธ์สมมูลแบบนี้ ลองดูอีกตัวอย่างหนึ่ง คำสองคำคล้ายกันหรือสมมูลกันเมื่อมีความยาวเท่ากัน (ในที่นี้ใช้คำภาษาอังกฤษ และความยาวคือจำนวนตัวอักษร)

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

ต่อมา ถ้าคำว่า “river” คล้ายหรือสมมูลกับคำว่า “apple” ย่อมคาดหวังว่าคำว่า “apple” ก็สมมูลกับคำว่า “river” ด้วย กล่าวอีกอย่างหนึ่งคือลำดับไม่สำคัญ ในภาษาของความสัมพันธ์ ความสัมพันธ์สมมูลต้องมีสมบัติสมมาตร

และสุดท้าย ถ้าคำว่า “tree” คล้ายหรือสมมูลกับคำว่า “bird” และคำว่า “bird” สมมูลกับคำว่า “foot” ย่อมคาดหวังว่าคำว่า “tree” และ “foot” ก็สมมูลกันด้วย ดังนั้นความสัมพันธ์สมมูลต้องมีสมบัติถ่ายทอดด้วย

นอกจากนี้ไม่ได้คาดหวังอะไรจากความสัมพันธ์สมมูลอีก

ตัวอย่าง

ตัวอย่างอื่นของความสัมพันธ์สมมูล

  • อาศัยอยู่ในเมืองเดียวกัน สมชายย่อมอาศัยอยู่ในเมืองเดียวกับสมชาย (สมบัติสะท้อน) ถ้าสมชายอาศัยอยู่ในเมืองเดียวกับสมศักดิ์ สมศักดิ์ก็อาศัยอยู่ในเมืองเดียวกับสมชาย (สมบัติสมมาตร) และถ้าสมศักดิ์อาศัยอยู่ในเมืองเดียวกับกฤษ สมชายก็อาศัยอยู่ในเมืองเดียวกับกฤษ (สมบัติถ่ายทอด)
  • เพลงที่มีผู้แต่งคนเดียวกัน (ชื่อเพลงต่อไปนี้แต่งขึ้นเป็นตัวอย่าง) เพลง “ฝนแรกที่ปลายนา” ย่อมมีผู้แต่งคนเดียวกับเพลง “ฝนแรกที่ปลายนา” (สมบัติสะท้อน) ถ้าเพลง “ฝนแรกที่ปลายนา” และ “ลมหนาวบนดอย” มีผู้แต่งคนเดียวกัน เพลง “ลมหนาวบนดอย” และ “ฝนแรกที่ปลายนา” ก็มีผู้แต่งคนเดียวกัน (สมบัติสมมาตร) และถ้า “ลมหนาวบนดอย” และ “ทะเลยามเย็น” มีผู้แต่งคนเดียวกัน เพลง “ฝนแรกที่ปลายนา” และ “ทะเลยามเย็น” ก็มีผู้แต่งคนเดียวกัน (สมบัติถ่ายทอด)
  • (a, b) ∈ R ก็ต่อเมื่อ a − b เป็นจำนวนคู่ เมื่อ a, b เป็นจำนวนเต็ม สมบัติสะท้อน a − a = 0 และศูนย์เป็นจำนวนคู่ สมบัติสมมาตร ให้ c = a − b จะได้ b − a = −(a − b) = −c ถ้า c เป็นจำนวนคู่ −c ก็ต้องเป็นจำนวนคู่ด้วย สมบัติถ่ายทอด ให้ p = a − b และ q = b − c เรารู้ว่า p และ q เป็นจำนวนคู่ ต้องพิสูจน์ว่า a − c เป็นจำนวนคู่ แทน c ด้วย c = b − q จะได้ a − (b − q) ซึ่งเท่ากับ a − b + q จากสมมติฐาน a − b เป็นจำนวนคู่ เมื่อบวกจำนวนคู่ด้วยจำนวนคู่ q ก็ได้จำนวนคู่อีก
  • ความสัมพันธ์เท่ากับ ความสัมพันธ์เท่ากับเป็นความสัมพันธ์สมมูล และยังเป็นความสัมพันธ์สมมูลที่เล็กที่สุดบนเซต M ใด ๆ ด้วย

ความสัมพันธ์สมมูลชัด

ให้ M เป็นเซตที่ไม่เป็นเซตว่าง ความสัมพันธ์สมมูลที่เล็กที่สุดที่เป็นไปได้ R บนเซต M คืออะไร สับเซตที่เล็กที่สุดที่เป็นไปได้ของผลคูณคาร์ทีเซียน M × M คือเซตว่าง ∅ เซตว่างสอดคล้องกับเงื่อนไขของความสัมพันธ์สมมูลหรือไม่

เซตว่างมีสมบัติสมมาตรแน่นอน เพราะความสัมพันธ์ R ไม่มีสมาชิกเลย เงื่อนไขของสมบัติสมมาตรจึงเป็นจริงโดยอัตโนมัติ สมบัติถ่ายทอดก็เช่นกัน ปัญหาอยู่ที่สมบัติสะท้อน นิยามบอกว่าสำหรับสมาชิก x ทุกตัวของเซต M จะได้ (x, x) ∈ R ข้อนี้เป็นจริงหรือไม่ เซต M ไม่เป็นเซตว่าง จึงมีสมาชิกอย่างน้อยหนึ่งตัว เช่น q คู่ (q, q) อยู่ในความสัมพันธ์ R หรือไม่ ไม่อยู่ ความสัมพันธ์ R จึงไม่มีสมบัติสะท้อน

ความสัมพันธ์ที่เล็กที่สุดที่มีสมบัติสะท้อนคืออะไร คือความสัมพันธ์เท่ากับ ความสัมพันธ์ R ต้องมีคู่ (x, x) สำหรับสมาชิกทุกตัวของ M เป็นอย่างน้อย ซึ่งก็คือความสัมพันธ์เอกลักษณ์ (identity relation) ความสัมพันธ์นี้มีสมบัติสมมาตรหรือไม่ เห็นได้ง่ายว่ามี และเห็นได้ง่ายเช่นกันว่ามีสมบัติถ่ายทอด ความสัมพันธ์สมมูลที่เล็กที่สุดบนเซต M จึงเป็นความสัมพันธ์เอกลักษณ์ เขียนแทนด้วย idM ซึ่งประกอบด้วยคู่ (x, x) สำหรับทุก x ∈ M

ความสัมพันธ์สมมูลที่ใหญ่ที่สุดที่เป็นไปได้บนเซต M คืออะไร สับเซตที่ใหญ่ที่สุดคือเซต M × M ทั้งหมด ซึ่งสอดคล้องกับเงื่อนไขของความสัมพันธ์สมมูลหรือไม่ เห็นได้ชัดว่าสอดคล้อง

ชั้นสมมูล

ความสัมพันธ์สมมูลทุกความสัมพันธ์แบ่งเซต M ออกเป็นวงศ์ของเซตที่ไม่มีสมาชิกร่วมกัน เรียกเซตเหล่านี้ว่าชั้นสมมูล (equivalence class)

ให้ M เป็นเซตของคำทั้งหมด (ภาษาอังกฤษ) และ R เป็นความสัมพันธ์สมมูล “เป็นคำที่ยาวเท่ากัน” นั่นคือ (a, b) ∈ R ก็ต่อเมื่อคำ a และ b มีความยาวเท่ากัน ความสัมพันธ์สมมูลนี้แบ่งเซตของคำออกเป็นเซตย่อยหลายเซต แต่ละเซตประกอบด้วยคำที่ยาวเท่ากัน แยกชั้นสมมูลแต่ละชั้นได้ด้วยตัวห้อย ซึ่งบอกความยาวของคำในเซตนั้นด้วย

  • M1 = {a, I, O, …}
  • M2 = {in, to, be, we, me, …}
  • M3 = {but, the, can, top, …}
  • M4 = {tree, park, bird, foot, …}
  • …

สังเกตสองข้อ 1) เซตแต่ละเซตไม่มีสมาชิกร่วมกันเลย 2) สมาชิกทุกตัวในเซตแต่ละเซตสมมูลกันทั้งหมด คำทุกคำในเซต M3 สมมูลกัน เพราะทุกคำมีความยาวสาม คือมีความยาวเท่ากัน ซึ่งเป็นเงื่อนไขของความสัมพันธ์สมมูล

นอกจากนี้ สมาชิกแต่ละตัวกำหนดชั้นสมมูลของตัวเองได้เพียงชั้นเดียว โดยทั่วไปเขียนด้วยสัญลักษณ์ M[x] เมื่อ x ∈ M ถ้าเขียน M[but] ก็เป็นการกำหนดชั้นสมมูลเพียงชั้นเดียว ซึ่งเราตั้งชื่อไว้แล้วว่า M3

ถ้ารู้ x ∈ M บางตัว จะหาชั้นสมมูลได้อย่างไร ไล่ดูสมาชิกทุกตัวใน M แล้วตรวจว่าสมาชิกใดสมมูลกับสมาชิก x สมาชิกเหล่านั้นทั้งหมดคือสมาชิกของชั้นสมมูล M[x]

สำหรับ M[but] ต้องไล่ดูคำทุกคำใน M แล้วเก็บคำที่มีความยาวสามไว้ใน M3

นิยามและสมบัติของชั้นสมมูล

นิยามชั้นสมมูลได้ดังนี้ ให้ M เป็นเซตและ R เป็นความสัมพันธ์สมมูลบนเซตนั้น ชั้นสมมูลที่มีสมาชิก x ∈ M คือ:

M[x]={y∈M;(x,y)∈R}

นิยามบอกว่าชั้นสมมูลคือ y ทั้งหมดที่สมมูลกับสมาชิก x ที่กำหนด เนื่องจากความสัมพันธ์สมมูลมีสมบัติสะท้อน สมาชิก x เองก็อยู่ในชั้นนี้ด้วย — เพราะ x สมมูลกับตัวเอง

ผลแบ่งกั้นที่สอดคล้องกับความสัมพันธ์สมมูล (partition) คือเซตของชั้นสมมูลทั้งหมด ผลแบ่งกั้นของเซตของคำทั้งหมดจึงเป็นเซต {M1, M2, M3, …}

สมบัติพื้นฐานของชั้นสมมูล

  • (a, b) ∈ R ก็ต่อเมื่อ M[a] = M[b] ถ้าสมาชิกสองตัว a, b สมมูลกัน ชั้นสมมูลของทั้งสองต้องเท่ากัน
  • ในทางกลับกัน ถ้า (a, b) ∈ R ไม่เป็นจริง จะได้ M[a] ≠ M[b] ด้วย หรือกล่าวให้ชัดคือ M[a] ∩ M[b] = ∅ ถ้าสมาชิกสองตัวไม่สมมูลกัน ชั้นสมมูลของทั้งสองไม่มีสมาชิกร่วมกัน
  • ยูเนียนของชั้นสมมูลทั้งหมดต้องเท่ากับเซต M เดิม: M1 ∪ M2 ∪ … ∪ Mn = M (การเขียนนี้ใช้กับชั้นสมมูลจำนวนจำกัดเท่านั้น แต่ในกรณีทั่วไปอาจมีชั้นสมมูลมากมายไม่จำกัด)

ตัวอย่างผลแบ่งกั้นตามความสัมพันธ์สมมูล

ตัวอย่างแรก จำนวนคี่และจำนวนคู่

ให้ R เป็นความสัมพันธ์สมมูลง่าย ๆ ที่นิยามบนจำนวนนับ N โดย (a, b) ∈ R ก็ต่อเมื่อ a และ b เป็นจำนวนคี่ทั้งคู่ หรือ a และ b เป็นจำนวนคู่ทั้งคู่ ตัวอย่างสมาชิก: (1, 7), (13, 9), (4, 6), (8, 136) ต่อไปจะหาผลแบ่งกั้นของความสัมพันธ์สมมูลนี้ออกเป็นชั้นสมมูล

เริ่มทีละขั้น ชั้น N[1] เท่ากับอะไร ต้องหาจำนวนทั้งหมดที่สมมูลกับหนึ่ง ตามเงื่อนไขของความสัมพันธ์สมมูลคือจำนวนคี่ทั้งหมด ดังนั้น N[1] = {1, 3, 5, 7, 9, …}

ชั้น N[2] เท่ากับอะไร หาจำนวนทั้งหมดที่สมมูลกับสอง คือจำนวนคู่ทั้งหมด: N[2] = {2, 4, 6, 8, 10, …}

ต่อไปคือ N[3] จำนวนใดสมมูลกับสาม คือจำนวนคี่ทั้งหมด แต่จะได้เซต N[1] ซึ่งหาไว้แล้วเมื่อสองย่อหน้าก่อน N[4] ก็ทำนองเดียวกัน ได้เซตของจำนวนคู่อีกครั้ง

จะเห็นว่าต่อจากนี้จะได้เซตเดิมซ้ำไปเรื่อย ๆ เห็นได้จากข้อที่ว่าไม่ว่าเลือกจำนวนนับ n ใด จะได้ n ∈ N[1] หรือ n ∈ N[2] ไม่มีจำนวนนับใดที่ไม่เป็นทั้งจำนวนคี่และจำนวนคู่ เซตสองเซตนี้จึงเป็นผลแบ่งกั้นตามความสัมพันธ์สมมูล

คล้ายกับนึกถึงความสัมพันธ์สมมูลบนเซตของคน “a และ b เป็นผู้ชายทั้งคู่ หรือ a และ b เป็นผู้หญิงทั้งคู่” ผลแบ่งกั้นที่ได้คือเซตของผู้หญิงและเซตของผู้ชาย

ตัวอย่างที่สอง ค่าสัมบูรณ์

ให้ R เป็นความสัมพันธ์สมมูลบนเซตของจำนวนเต็ม Z นิยามดังนี้ (a, b) ∈ R ก็ต่อเมื่อ |a| = |b| (เส้นตั้งสองเส้นคือค่าสัมบูรณ์) ทำทีละขั้นอีกครั้ง

  • Z[0] = {0} ศูนย์อยู่ในความสัมพันธ์กับศูนย์เท่านั้น
  • Z[1] = {−1, 1} หนึ่งอยู่ในความสัมพันธ์กับหนึ่งและลบหนึ่ง เพราะ |1| = |−1|
  • Z[2] = {−2, 2} สองอยู่ในความสัมพันธ์กับสองและลบสอง
  • Z[3] = {−3, 3}
  • …

คงเห็นแล้วว่าจะเป็นอย่างไรต่อไป ผลแบ่งกั้นทั้งหมดจึงเป็นเซตของชั้นต่อไปนี้:

{{a,−a};a∈Z0+}

(คือคู่ a, −a ทั้งหมด เมื่อ a เป็นจำนวนเต็มที่ไม่เป็นลบ) จะเห็นว่ามีชั้นสมมูลมากมายไม่จำกัด

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