رابطه هم‌ارزی

دسته‌های هم‌ارزی

وقتی یک رابطهٔ هم‌ارزی را روی مجموعه‌ای تعریف می‌کنیم، این رابطه مجموعه را به دسته(کلاس)های هم‌ارزی افراز می‌کند. به عنوان نمونه، همان مثال توازی خطوط را در نظر بگیرید. این رابطه، رابطه‌ای هم‌ارزی است و خطوط موجود در صفحه را به دسته‌های هم‌ارزی افراز می‌کند؛ به طوری که همهٔ خطوط موجود در هر دسته، با هم موازی‌اند.
یک مثال مفید دیگر برای درک بهتر دسته‌های هم‌ارزی، رابطهٔ هم‌باقی‌ماندگی اعداد طبیعی به پیمانه‌ای مشخص است. نشان دادن این‌که این رابطه هم‌ارزی‌ست، بسیار ساده‌است و لذا از اثبات آن می‌گذریم. به این ترتیب همان‌طور که گفته شد، این رابطه مجموعهٔ اعداد طبیعی را به دسته‌های هم‌ارزی افراز خواهد کرد. اعداد موجود در هریک از این دسته‌ها، به پیمانهٔ m باقی‌ماندهٔ یکسانی خواهند داشت.
معمولاً دسته‌های هم‌ارزی را به کمک یکی از اعضای آن مشخص می‌کنند؛ برای مثال [۲] نمایانگر دستهٔ هم‌ارزی‌ای است که عنصر ۲ در آن قرار دارد یا به عبارت دیگر تمام اعضای مجموعهٔ اصلی که با عنصر ۲ رابطه دارند در [۲] قرار می‌گیرند.

مجموعه‌های مرتب

ابتدا لازم است مفهوم سنجش‌پذیر (مقایسه‌پذیر) را تعریف کنیم. دو عضو (مثل a و b) از یک مجموعه را سنجش‌پذیر با یک رابطهٔ ترتیب گوییم هرگاه (a،b) یا (b،a) عضو آن رابطه باشد. برای مثال اگر رابطهٔ موردنظر رابطهٔ بخش‌پذیری (شمردن/عادکردن) باشد، آن‌گاه دو عدد ۲ و ۴ سنجش‌پذیرند (زیرا ۴|۲ یا به عبارت دیگر (۲٬۴) عضو رابطه‌است) در حالی که دو عدد ۲ و ۳ سنجش‌پذیر نیستند (زیرا هیچ‌یک از (۳٬۲) یا (۲٬۳) عضو رابطه نیست). واضح است که اگر a و b متمایز باشند، به علت پادتقارنی بودن رابطه، امکان ندارد هردوی این زوج‌مرتب‌ها عضو رابطه باشند.
حال به تعریف مجموعه‌های مرتب می‌پردازیم.
مجموعهٔ مرتب (یا تمام‌مرتب) در مورد یک رابطهٔ ترتیب تعریف می‌شود و به مفهوم آن است که هر دو عضو آن مجموعه، نسبت به آن رابطه، سنجش‌پذیرند. برای مثال رابطهٔ بزرگ‌تر یا مساوی بودن، روی مجموعهٔ اعداد طبیعی را در نظر می‌گیریم. با توجه به آن‌چه گفته شد، این رابطه ترتیب است و از طرفی در مورد هر دو عدد طبیعی a و b یا  یا . به این ترتیب مجموعهٔ اعداد طبیعی نسبت به این رابطه مرتب است. گاهی چنین مجموعه‌هایی را زنجیر نیز می‌خوانند.

نمایش رابطهٔ ترتیب

برای نمایش هریک از انواع رابطه‌ها راه‌های گوناگونی هست. به طور کلی یکی از بهترین شیوه‌های نمایش رابطه‌ها، استفاده از گراف جهت‌دار است.
با توجه به آن‌چه گفته شد، یکی از راه‌هایی که برای نمایش رابطهٔ ترتیب استفاده می‌شود به نمودار هسه موسوم است. شیوهٔ ترسیم این نمودار به این صورت است که ابتدا گراف جهت‌دار نمایش رابطه را مشخص می‌کنیم. حال از آن‌جا که می‌دانیم رابطهٔ ترتیب بازتابی است، نیازی نیست که طوقه‌ها را نیز در نمودار باقی بگذاریم. پس آن‌ها را حذف می‌کنیم. از طرفی می‌دانیم که رابطهٔ ترتیب ترایایی نیز هست؛ بنابراین محتاج به رسم یال‌هایی که این رابطه را نشان می‌دهند نیز نیستیم. پس می‌شود آن‌ها را هم حذف کرد. آن‌چه که پس از این روال به دست می‌آید، نمودار هسه خوانده می‌شود.
برای مثال فرض کنید می‌خواهیم رابطهٔ بخش‌پذیری را روی مجموعه {۱٬۳،۴٬۶،۱۲} نمایش دهیم. این کار چنان که می‌بینید به کمک یک گراف جهت‌دار امکان‌پذیر است. حال اگر روال گفته‌شده را روی این گراف اعمال کنیم، نمودار هسه به دست می‌آید.

کاربردها

مهم‌ترین کاربرد رابطه‌های ترتیب در مرتب‌سازی است. مرتب‌سازی لکزیکوگرافیک و توپولوژیک، یافتن عنصر بیشینه و کمینه، تعیین کران بالا و کران پایین، تعیین ترتیب اجرای مراحل مختلف یک برنامه، برنامه‌ریزی درسی و... که کمابیش مفهوم ترتیب را دارند، کاربردهای دیگر رابطه‌های ترتیب را آشکار می‌سازند.
رابطه‌های هم‌ارزی نیز برای دسته‌بندی اشیاء، اعداد و پدیده‌ها در زمانی که هویت تک‌تک آن‌ها به اندازهٔ رفتار مشترک‌شان با سایر اعضای مجموعه اهمیت ندارد، کاربرد خواهند یافت.