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

روابط دوتایی ترایا
متقارن پادمتقارن کانکس خوش-بنیان $\vee$ دارد $\wedge$ دارد بازتابی غیربازتابی نامتقارن رابطه هم‌ارزی ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ پیش‌ترتییب (شبه‌ترتیب) ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ ترتیب جزئی ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✗ ✗ پیش-ترتیب کلی ✗ ✗ ✓ ✗ ✗ ✗ ✓ ✗ ✗ ترتیب کلی ✗ ✓ ✓ ✗ ✗ ✗ ✓ ✗ ✗ پیش-خوش‌ترتیب ✗ ✗ ✓ ✓ ✗ ✗ ✓ ✗ ✗ خوش-شبه-ترتیب ✗ ✗ ✗ ✓ ✗ ✗ ✓ ✗ ✗ خوش‌ترتیب ✗ ✓ ✓ ✓ ✗ ✗ ✓ ✗ ✗ مشبکه ✗ ✓ ✗ ✗ ✓ ✓ ✓ ✗ ✗ جوین-نیم-مشبکه ✗ ✓ ✗ ✗ ✓ ✗ ✓ ✗ ✗ میت-نیم-مشبکه ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✗ ✗ جزئی‌مرتب قطعی ✗ ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✓ مجوعه ضعیف‌مرتب ✗ ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✓ ترتیب کلی قطعی ✗ ✓ ✓ ✗ ✗ ✗ ✗ ✓ ✓ تعاریف: برای تمام $a$ و $b$ ها و $S\neq \varnothing$ : ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
علامت "✓" نشان‌دهنده آن است که ویژگی ستونی در تعریف آن سطر لازم است. برای مثال تعریف رابطه هم‌ارزی لازم دارد تا متقارن باشد. به صورت ضمنی همه این تعاریف ترایا و بازتابی می‌باشند. علامت "✗" نشان‌دهنده آن است که ویژگی به طور کلی تضمین نمی‌شود (می‌تواند برقرار باشد، یا نباشد). تمام روابط بالا مستلزم آن است که رابطه همگون $R$ ترایا باشد: برای تمام $a$ و $b$ و $c$ ها، اگر $aRb$ و $bRc$ آنگاه $aRc$.

رابطه هم‌ارزی (به انگلیسی: Equivalence relation) در ریاضیات یک رابطه دوتایی است که بازتابی، متقارن، و ترایا است.

رابطه‌ها در ریاضیات به صورت زیرمجموعه‌هایی از ضرب دکارتی دو یا چند مجموعهٔ مشابه یا متمایز تعریف می‌شوند. این رابطه‌ها می‌توانند خواص و ویژگی‌های گوناگونی داشته باشند؛ اما ۴ ویژگی از سایر ویژگی‌ها مهم‌تر است. رابطه‌هایی که این خواص را دارند، به این شکل نامیده می‌شوند:

1. بازتابی
2. تقارنی
3. پادتقارنی
4. ترایایی

رابطه‌ای که بازتابی، تقارنی و ترایایی باشد، رابطهٔ هم‌ارزی و رابطه‌ای که بازتابی، پادتقارنی و ترایایی باشد، رابطهٔ ترتیب خوانده می‌شود.

مثال‌هایی از رابطه‌های هم‌ارزی و ترتیب

• رابطهٔ توازی خطوط در صفحه (||): مثالی از رابطهٔ هم‌ارزی

نشان می‌دهیم که رابطهٔ توازی خطوط در صفحه، یک رابطهٔ هم‌ارزی است:

نخست - هر خط با خودش موازی است؛ پس این رابطه بازتابی است.

دوم - اگر خطی با خط دیگری موازی باشد، آن خط نیز با این خط موازی است؛ پس این رابطه تقارنی است.

سوم - اگر خط d با خط 'd، و خط 'd با خط «d موازی باشند، آن‌گاه بنابر قضایای هندسهٔ اقلیدسی، خط d با خط»d موازی خواهد بود؛ پس این رابطه ترایایی نیز هست.

به این ترتیب مشخص شد که رابطهٔ توازی، یک رابطهٔ هم‌ارزی است.

• رابطهٔ بزرگ‌تر مساوی بودن ($\geq$): مثالی از رابطهٔ ترتیب

نشان می‌دهیم که رابطهٔ $\geq$ یک رابطهٔ ترتیب است:

نخست - هر عدد از خودش بزرگ‌تر یا با خودش مساوی است؛ پس این رابطه بازتابی است.

دوم - اگر $a\geq b$ و $b\geq a$ آن‌گاه نتیجه می‌شود که $a=b$؛ پس این رابطه پادتقارنی است.

سوم - اگر $a\geq b$ و $b\geq c$ آن‌گاه نتیجه می‌شود که $a\geq c$؛ پس این رابطه ترایایی است.

به این ترتیب مشخص شد که رابطهٔ $\geq$ یک رابطهٔ ترتیب است.

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

هر رنگ یك دستهٔ هم‌ارزی این خطوط را مشخص میكند

وقتی یک رابطهٔ هم‌ارزی را روی مجموعه‌ای تعریف می‌کنیم، این رابطه مجموعه را به دسته(کلاس)های هم‌ارزی افراز می‌کند. به عنوان نمونه، همان مثال توازی خطوط را در نظر بگیرید. این رابطه، رابطه‌ای هم‌ارزی است و خطوط موجود در صفحه را به دسته‌های هم‌ارزی افراز می‌کند؛ به طوری که همهٔ خطوط موجود در هر دسته، با هم موازی‌اند.

یک مثال مفید دیگر برای درک بهتر دسته‌های هم‌ارزی، رابطهٔ هم‌باقی‌ماندگی اعداد طبیعی به پیمانه‌ای مشخص است. نشان دادن این‌که این رابطه هم‌ارزی‌ست، بسیار ساده‌است و لذا از اثبات آن می‌گذریم. به این ترتیب همان‌طور که گفته شد، این رابطه مجموعهٔ اعداد طبیعی را به دسته‌های هم‌ارزی افراز خواهد کرد. اعداد موجود در هریک از این دسته‌ها، به پیمانهٔ m باقی‌ماندهٔ یکسانی خواهند داشت.

معمولاً دسته‌های هم‌ارزی را به کمک یکی از اعضای آن مشخص می‌کنند؛ برای مثال [۲] نمایانگر دستهٔ هم‌ارزی‌ای است که عنصر ۲ در آن قرار دارد یا به عبارت دیگر تمام اعضای مجموعهٔ اصلی که با عنصر ۲ رابطه دارند در [۲] قرار می‌گیرند.

چند مثال از افراز به دسته‌های هم‌ارزی

رابطهٔ هم‌رنگ بودن، پرچم را به سه دستهٔ هم‌ارزی سبز و سفید و قرمز افراز كرده‌است

• رابطهٔ هم‌استانی بودن: رابطه‌ای هم‌ارزی است و مجموعهٔ مردم یک کشور را به دسته‌های هم‌ارزی افراز می‌کند که هر دسته یک استان را مشخص خواهد کرد.
• رابطهٔ هم‌رنگ بودن: رابطه‌ای هم‌ارزی است و مجموعهٔ نقاط یک صفحه را به دسته‌های هم‌رنگ افراز خواهد کرد.
• رابطهٔ هم‌دما بودن: رابطه‌ای هم‌ارزی است و مجموعهٔ نقاط یک اتاق را به دسته‌های هم‌دما افراز خواهد کرد.
• رابطهٔ روز تولد یکسان داشتن: رابطه‌ای هم‌ارزی است و مجموعهٔ انسان‌ها را به ۳۶۵ (یا ۳۶۶) دستهٔ هم‌ارزی افراز خواهد کرد.
• رابطهٔ یکسانی تعداد یک‌ها در نمایش دودویی یک عدد: رابطه‌ای هم‌ارزی است و مجموعهٔ اعداد را به دسته‌های هم‌ارزی افراز می‌کند به طوری که در نمایش دودویی اعداد موجود در هر دسته، تعداد یکسانی یک وجود دارد.

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

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

حال به تعریف مجموعه‌های مرتب می‌پردازیم. مجموعهٔ مرتب (یا تمام‌مرتب) در مورد یک رابطهٔ ترتیب تعریف می‌شود و به مفهوم آن است که هر دو عضو آن مجموعه، نسبت به آن رابطه، سنجش‌پذیرند. برای مثال رابطهٔ بزرگ‌تر یا مساوی بودن، روی مجموعهٔ اعداد طبیعی را در نظر می‌گیریم. با توجه به آن‌چه گفته شد، این رابطه ترتیب است و از طرفی در مورد هر دو عدد طبیعی a و b یا $a\geq b$ یا $b\geq a$. به این ترتیب مجموعهٔ اعداد طبیعی نسبت به این رابطه مرتب است. گاهی چنین مجموعه‌هایی را زنجیر نیز می‌خوانند.

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

گراف جهت‌دار مربوط به رابطه

نمودار هسه مربوط به رابطه

برای نمایش هریک از انواع رابطه‌ها راه‌های گوناگونی هست. به طور کلی یکی از بهترین شیوه‌های نمایش رابطه‌ها، استفاده از گراف جهت‌دار است.

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

کاربردها

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

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

منابع

• ویکی‌پدیای انگلیسی

• Kenneth H. Rosen (۲۰۰۳)، Discrete Mathematics and Its Applications (ویراست ۵th Edition)، McGrowHill، شابک ۰-۰۷-۲۴۲۴۳۴-۶نگهداری یادکرد:متن اضافی (رده)