ইকুইভ্যালেন্স রিলেশন ও পার্টিশন

১ · ইকুইভ্যালেন্স রিলেশন ও ইকুইভ্যালেন্স ক্লাস

একটি সেট $A$-এর উপর রিলেশন $R$-কে ইকুইভ্যালেন্স রিলেশন (Equivalence Relation)Equivalence Relationএকটি রিলেশন যা একসাথে reflexive, symmetric ও transitive — L08-এর তিনটি নির্দিষ্ট বৈশিষ্ট্যের সমাহার। বলা হয় যদি এটি একসাথে reflexive, symmetric, ও transitive হয় (L08 দেখুন)। এই তিনটি বৈশিষ্ট্য মিলে "$a$ ও $b$ একই শ্রেণীর" — এই স্বজ্ঞাত ধারণাটিকে আনুষ্ঠানিক রূপ দেয়।

একটি উপাদান $a \in A$-এর ইকুইভ্যালেন্স ক্লাস (Equivalence Class)Equivalence Class$[a] = \{x \in A \mid (x,a) \in R\}$ — $a$-এর সাথে $R$-এর মাধ্যমে সম্পর্কিত সব উপাদানের সেট। সংজ্ঞায়িত হয় $[a] = \{x \in A \mid (x,a) \in R\}$ — অর্থাৎ $a$-এর সাথে সম্পর্কিত সব উপাদানের সেট।

২ · মূল উপপাদ্য — ইকুইভ্যালেন্স ক্লাস পার্টিশন তৈরি করে

একটি ইকুইভ্যালেন্স রিলেশনের সব ইকুইভ্যালেন্স ক্লাস মিলে $A$-এর একটি পার্টিশন (Partition)Partitionএকটি সেটকে কিছু নন-এম্পটি, পরস্পর ডিসজয়েন্ট উপসেটে ভাগ করা, যাদের ইউনিয়ন পুরো সেট। তৈরি করে — অর্থাৎ (১) প্রতিটি উপাদান ঠিক একটি ক্লাসে পড়ে, (২) কোনো দুটি ক্লাস হয় সম্পূর্ণ একই অথবা সম্পূর্ণ ডিসজয়েন্ট (কখনো আংশিক ওভারল্যাপ করে না), এবং (৩) সব ক্লাসের ইউনিয়ন পুরো $A$।

কেন এটি সত্য — সংক্ষিপ্ত স্বজ্ঞা: ধরুন $[a] \cap [b] \neq \emptyset$, অর্থাৎ কোনো $x$ আছে যা $[a]$ ও $[b]$ দুটোতেই আছে। তাহলে $x \mathrel{R} a$ ও $x \mathrel{R} b$। Symmetric-এর কারণে $a \mathrel{R} x$, এবং transitive-এর কারণে $a \mathrel{R} x$ ও $x \mathrel{R} b$ থেকে $a \mathrel{R} b$ পাওয়া যায়। এখন $[a]$-এর যেকোনো উপাদান $y$-এর জন্য $y \mathrel{R} a$ ও $a \mathrel{R} b$ থেকে transitivity দিয়ে $y \mathrel{R} b$, অর্থাৎ $y \in [b]$ — তাই $[a] \subseteq [b]$, একইভাবে $[b] \subseteq [a]$, তাই $[a] = [b]$। সুতরাং দুটি ক্লাস আংশিক ওভারল্যাপ করতে পারে না — হয় সম্পূর্ণ সমান, নাহলে সম্পূর্ণ আলাদা।

৩ · Worked উদাহরণ — mod 3 রিমাইন্ডার

পূর্ণসংখ্যার সেট $\mathbb{Z}$-এর উপর রিলেশন সংজ্ঞায়িত করুন: $a \mathrel{R} b$ যদি $a$ ও $b$-কে ৩ দিয়ে ভাগ করলে একই ভাগশেষ থাকে। এটি reflexive, symmetric ও transitive — একটি ইকুইভ্যালেন্স রিলেশন। এর ঠিক তিনটি ইকুইভ্যালেন্স ক্লাস আছে —

এই তিনটি ক্লাস পরস্পর ডিসজয়েন্ট এবং তাদের ইউনিয়ন পুরো $\mathbb{Z}$ — অর্থাৎ তারা $\mathbb{Z}$-কে সম্পূর্ণভাবে পার্টিশন করে। ঠিক এই ধারণাটিই M5-তে "মডুলার এরিথমেটিক" নামে গভীরভাবে ফিরে আসবে।

from collections import defaultdict

classes = defaultdict(list)
for n in range(15):
    classes[n % 3].append(n)

for r in sorted(classes):
    print(f"[{r}] (mod 3 = {r}):", classes[r])

# ভেরিফাই: ক্লাসগুলো ডিসজয়েন্ট ও তাদের ইউনিয়ন পুরো রেঞ্জ কভার করে
all_elements = sum(classes.values(), [])
print("\nমোট উপাদান:", len(all_elements))
print("রেঞ্জ(0..14)-এর সাথে মেলে কি না:", set(all_elements) == set(range(15)))