رابطه دوتایی

روابط دوتایی ترایا
متقارن پادمتقارن کانکس خوش-بنیان $\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$.

رابطه دوتایی

رابطهٔ دوتایی در ریاضیات روی مجموعهٔ A است که با A2 نمایش داده می‌شود. مفهوم کلی‌تر: رابطهٔ دوتایی بین دو مجموعهٔ A و B می‌شود زیرمجموعه‌ای از A*B.

یک مثال می‌شود رابطهٔ تقسیم بین مجموعه اعداد اول R و اعداد صحیح z که در آن هر عدد اول به چند عدد صحیح که مضارب آن عدد اول هستند مربوط می‌شود (و با بقیهٔ اعداد که مضرب همان عدد اول نیستند رابطه ندارد). در این رابطه برای نمونه عدد اول ۲ به همهٔ اعداد زوج که بر ۲ بخش‌پذیرند رابطه دارد مثلاً ۱۰ و ۶ ولی با ۵ و ۹ رابطه ندارد. از طرفی عدد اول ۳ نیز با ۶ رابطه دارد ولی با ۱۰ رابطه ندارد.

رابطهٔ دوتایی برای بیش‌تر شاخه‌ها در ریاضیات کاربرد دارد برای مثال برای مدل‌سازی مفاهیمی چون: "بزرگتر" و"تساوی" و "تقسیم" در حساب و تجانس در علم هندسه و... می‌توان از آن استفاده کرد.

مفهوم تابع به عنوان یکی از انواع خاص رابطه دوتایی تعریف می‌شود. رابطه دوتایی در علم کامپیوتر نیز کاربرد زیادی دارد.

یک مجموعه هنگامی رابطه دوتایی نامیده می‌شود که (An ... * A2 * A1 ) شامل R باشد وعنصر j ام از هر کدام از مجموعه‌های A1 تا An از عناصر مجموعه Aj ترکیب شده باشد.

تعریف

یک رابطه دوتایی معمولاً به شکل یک سه تایی (X,Y,G ) تعریف می‌شود که X,Y دو مجموعه دلخواه هستند و G یک زیر مجموعه از ضرب دکارتی X*Y دو مجموعه X,Y به ترتیب دامنه و هم‌دامنه نامیده می‌شوند و G گراف.

حالتی که X,Y هر دو شامل G هستند به شکل "X با Y رابطه R را دارد" خوانده می‌شود که به شکل XRY خلاصه می‌شود. نمادگذاری آخر برای نشان دادن مشخصه‌های تابع روی X,Y برای مجموعه جفت‌های (X,Y ) است.

مرتب‌سازی عناصر در هر جفت از گراف G مهم است. اگر a مساوی b نباشد یا aRb یا bRa می‌تواند درست باشد یا غلط، بستگی به هر دوی آن‌ها دارد. یادآوری مثال بالا ۳ از عوامل ۹ است ولی ۹ عامل ۳ نیست.

یک رابطه به شکل یک سه‌تایی (X,Y,G) تعریف می‌شود که معمولاً به جای مفهوم تناظر به کار می‌رود. در این مثال X با Y رابطه دارد باید معلوم شود که زمینه (رابطه) آن چیست.

آیا یک رابطه بیش‌تر از یک گراف آن است؟

بر اساس تعریف بالا دو رابطه با یک گراف یکسان و دامنه و برد متفاوت دو رابطهٔ متفاوت در نظر گرفته می‌شوند. مخصوصاً در نظریه مجموعه‌ها رابطه دوتایی معمولاً بر پایه جفت‌های داده شده یا گراف مورد نظر شناخته می‌شود.

دامنهٔ یک رابطه دوتایی R بر پایه تمامی Xهایی تعریف می‌شود که حداقل یک عضو با این عدد رابطه داشته باشد. برد نیز تمامی Yهایی تعریف می‌شود که حداقل با یک عدد در دامنه جفت شود.

حالت خاص این تفاوت را می‌توان در مفهوم تابع دید. خیلی از نویسنده‌ها بین هم‌دامنه و برد ابهام دارند. بنابراین یک قانون واحد مانند جفت کردن اعداد حقیقی می‌تواند این ایهام را برطرف کند. بستگی به این دارد که آیا تصور رابطه بین دو عدد واقعی است یا نه (واقعاً وجود ندارد) ولی بقیه مجموعه‌ها می‌توانند دامنه‌ای با اعضای مشخص داشته باشند. این تفاوت باعث شده که مثال‌های متناقضی منتشر شود. برای مثال ریاضی‌دانان قدیمی فرض کردند که پوشا بودن یک تابع یک ویژگی تابع شمرده می‌شود در حالی که این دستاورد به اندازه‌ای استفاده می‌شود که موجب بسیاری از تغییرات در علوم مختلف شده‌است. انتخاب بین دو تعریف ارائه شده معمولاً در زمینه‌های پایه مانند دسته‌بندی نظریه‌ها اهمیت پیدا می‌کند.

مثال ها: فرض کنید ۴ شیء دارید (توپ و ماشین و عروسک و تفنگ) و ۴ تا آدم (احسان و حسن و حسین و مریم) فرض کنید احسان صاحب توپ است و مریم صاحب عروسک و حسن صاحب ماشین. همان طور که می‌بینید هیچ کسی صاحب تفنگ نیست. بنابراین رابطه دوتایی می‌شود:

R=({توپ و ماشین و عروسک و تفنگ},{احسان و حسن و حسین و مریم}{(توپ و احسان)(مریم و عروسک)(حسن و ماشین)}
پس قسمت اول مجموعه‌ای از تمام اشیا است و قسمت دوم زوج مرتب‌های بین این اشیا.
عبارت (احسان و توپ) به شکل احسانRتوپ قابل نمایش است.
دو تعریف می‌توانند گراف یکسانی داشته باشند.
R=({توپ و ماشین و عروسک و تفنگ}{احسان و مریم و حسن}{(احسان و توپ)(مریم و عروسک)(حسن و ماشین)})
این دو رابطه مربوط به دو تعریف هستند که گراف یکسان دارند ولی با دو ارتباط متفاوت هستند.

رابطهٔ $n\!$-تایی

به‌همان‌گونه که روابط دوتایی، با تعریف فوق، ارتباط مابین عناصر دو مجموعه را نمایش می‌دهد، روابط $n\!$-تایی را به منظور نمایش ارتباط میان المان‌های موجود در بیش از دو مجموعه تعریف می‌نماییم.

حالات خاص روابط دوتایی

چند تا از حالات مهم رابطه‌ها بین X,Y در زیر نمایش داده شده است:

تراگذری: برای تمام اعداد در دامنه که XRY و تمام Yها در برد که YRZ باید بتوان نتیجه گرفت که XRZ .

برای مثال رابطه بزرگ تر: 2 با 5 رابطه دارد یعنی از آن کوچک‌تر است و یک نیز با 2 رابطه دارد و می‌توان گفت که 5 از یک بزرگ تر است و یک با 5 نیز رابطه دارد پس این رابطه خاصیت تراگذری را دارد.

خاصیت تابعی: برای تمام Xها در دامنه و تمام Yها و Zها در برد اگر XRY و XRZ باید Y=Z . به عنوان رابطه دوتایی آن را توابع جزئی می‌نامند.

برای مثال تابعی نبودن می‌توان به جذر گرفتن اشاره کرد. طبق این رابطه 4 با 2 رابطه دارد و همچنین 4 با -2 نیز رابطه دارد ولی 2 و -2 برابر نیست.

یک به یک: تابعی که هم پوشا باشد و هم خاصیتی تابعی را داسته باشد می‌شود یک به یک.

تمام دامنه:به ازای هر X ای در دامنه yای در برد وجود دارد که رابطه R برای آن‌ها وجود دارد. به‌طور مثال رابطه جذر گرفتن را می‌توان به دو قسمت تقسیم کرد. دامنه‌ای که برد برای آن وجود دارد و دامنه‌ای که برد برای آن نیست یعنی اعداد منفی پس این رابطه تمام دامنه نیست.

پوشا: به ازای هر Y ای در برد می‌توان Xای در دامنه پیدا کرد که رابطه R را داشته باشد.

تابع: به رابطه‌ای می‌گویند که خاصیت تابعی بودن را داشته باشد.

وارون پذیری: تابعی که هم یک به یک باشد و هم پوشا به‌طوری‌که اگر جای X و Y را برای آن جابجا کنیم باز هم خاصیت تابعی را داشته باشد.

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

اگر X=Y می‌گوییم یک رابطه روی X تعریف شده‌است. چند تا از رابطه‌ها در گراف‌ها به‌طور کلی بحث شد.مجموعه ی رابطه‌ها در روابط دو تایی که روی 2X*x تعریف شده اند جبر بولی نامیده می‌شوند با واروپذیری گسترش یافتند. بعضی از ویژگی‌ها ی روابط دوتایی:

بازتابی:برای هر X ای در دامنه باید XRX وجود داشته باشد مثلاً رابطه تساوی.

غیر بازتابی: برای هیچ X ای در دامنه XRX وجود نداشته باشد.

تک بازتابی: به ازای هر X,Y ای اگر XRY وجود داشت باید X=Y نیز وجود داشته باشد.مانند رابطه تساوی.

متقارن: برای هر X,Y که رابطه R باری آن‌ها تعریف شده باشد مثلاً XRY باید YRX نیز وجود داشته باشد.

پاد متقارن: برای هر X,Y اگر XRY و YRX باید X=Y باشد.

نامتقارن: برای هر X,Y ای اگر XRY وجود داشته باشد YRX وجود نداشته باشد.

تراگذری: برای هر X,Y,Z ای اگر XRY در دامنه دقیقاً یکی از XRY وجود داشته باشد و YRZ وجود داشته باشد باید XRZ نیز پیدا کرد.

سه بخشی: برای هر X,Y در دامنه دقیقاً یکی از XRY یا YRX یا X=Y وجود داشته باشد. برای مثال رابطه بزرگتر که هر عدد با عدد دیگری فقط می‌تواند یکی از دو حالت بالا را داشته باشد.

اقلیدسی: برای هر X,Y,Z ای اگر XRZ,XRY وجود داشته باشد YRZ سپس ZRY وجود داشته باشد. تساوی یک رابطه اقلیدسی است زیرا اگر X=Z,X=Y می‌توان نتیجه گرفت که Y=Z نیز هست.

سریالی: رابطه‌ای که به ازای هر X عضو دامنه Yای وجود داشته باشد که این رابطه برای آن صدق کند مثلاً رابطه بزرگ تر بودن برای اعداد طبیعی سریالی نیست زیرا عددی که یک از آن بزرگ تر باشد در اعداد طبیعی وجود ندارد ولی در اعداد صحیح می‌توان پیدا کرد پس این رابطه در اعداد طبیعی سریالی نیست ولی در اعداد صحیح سریالی است.

هم ارزی: یک مجموعه از اعداد را کلاس همارزی یک عدد می‌نامیم هنگامی که آن عدد و اعداد در آند مجموعه با یکدیگر هم رابطه بازتابی دارند و هم رابطه تقارن و هم رابطه تراگذری داشته باشند.به عبارت دیگر مجموعه تمام اعداد ی که با عدد مورد نظر رابطه دارند را کلاس هم ارزی آن عدد می‌نامیم.

رابطه‌ای را که خواص بازتابی و تراگذری و پادتقارن داشته باشد ترتیب جزئی می‌نامیم.

عملگرها روی مجمو عه ها:

اگر R و S را رابطه بنامیم و X,Y را نیز دو عدد از این مجموعه می‌توانیم عملیات‌های مجازی روی مجموعه‌ها را به صورت زیر بنویسیم:

اجتماع: یعنی تمام زوج مرتب‌هایی که یا در R یا S یا در هردوی آن‌ها تعریف می‌شوند.

اشتراک:تمام روج مرتب‌هایی که هم در R و هم در S هستند می‌شوند.

ترکیب: ترکیب SOR یعنی تمام روج مرتب‌های (X,Z) ای که (X,Y) در S وجود دارند و (Y,Z)در Rمثلاً اگر رابطه S,R به شکل زیر باشند می‌توانیم بگوییم: S={(1,2)(2,3)} R={(1,5)(2,7)} SOR={(1,7)}

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

مثلاً اگر R روی X,Y و همینطور S نیز روی X,Y تعریف بشوند و R زیرمجموعه‌ای از S باشد می‌توانیم به جای XRY XSY, قرار دهیم.

وارون: یعنی جابجایی Xها و Yها در تمام زوج مرتب‌های (X,Y) تا به شکل (Y,X) در بیایند.مثلاً اگر مجموعه R به شکل زیر باشد می‌توان دید:

R={(1,2)(2,3)(4,5)} R-1={(2,1)(3,2)(5,4)}

افزودن بازتابی بسته R: می‌شود اضافه کردن زوج مرتب‌هایی که اگر به R اضافه شوند R یک رابطه بازتابی می‌شود.

کاستن بازتابی بسته R: کم کردن تمام زوج مرتب‌هایی که به شکل (X,X) هستنداز R.

افزودن تراگذری: افزودن تمام زوج مرتب‌ها یی که با افزودن آن‌ها R تراگذری می‌شود.

کاستن تراگذری: کاستن تمام(X,Z)هایی که (Y,Z) و (X,Y) در R وجود دارند.

مکمل R: یعنی مجموعه تمام زوج مرتب‌هایی که در توان 2 مجموعه مرجع قرار دارند ولی در R قرار ندارند.مانند:

S={1,2} S2={(1,1)(1,2)(2,1)(2,2)} R={(1,1)} S-R={(2,1)(1,2)(2,2)}

محدوده: محدوده X یعنی مجموعه همه زوج مرتب‌هایی که می‌توان در بک مجموعه ساخت.

محدوده افزودن تراگذری یعنی تمام زوج مرتب‌هایی که باید به یک مجموعه اضافه کرد تا آن رابطه تراگذر شود.

مثلاً محدوده رابطه پدر بودن برای مرد هاست و رابطه مادر بودن به زن‌ها محدود می‌شود.

برای گسترش مفهوم کامل بودن در یک محدوده می‌توان شامل تمام اعداد حقیقی بین X,Y را زد که از X کوچک‌تر و از Y بزرگتراند.این اعداد به بازه بین X,Y محدودند اما بزرگترین عددی که شامل این مجموعه باشد را نمی‌توان یافت پس اصطلاحاً می‌گوییم X سوپریمم این رابطه است یعنی همه اعداد از X کوچک ترند ولی X خودش عضو این مجموعه نیست.

مچموعه‌ها در مقابل کلاس ها:

روابط دوتایی مانند تساوی زیر مجموعه و... در تعریف بالا نمی‌گنجد یعنی در نظریهٔ مجموعه‌ها نمی‌توان آن‌ها را مدل‌سازی کرد مثلاً رابطه تساوی را باید با دامنه و هم دامنه تعریف کرد ولی اندازه این مجموعه‌ها معلوم نیست پس اصطلاح دیگری مانند کلاس را معرفی می کنیم که شامل یک یا چند مجموعه است.

اگر یخواهیم اعداد ی که با عددی مانند X رابطه دارند را در یک یا چند مجموعه بگنجانیم همه مجموعه‌ها را در یک کلاس میریزیم و می نویسیم کلاس هم ارزی X.

برای مثال کلاس زیرمجموعه‌های یک مجموعه را مجموعه ی توانی آن مجموعه توانی آن مجموعه می نامیم و با نماد P(A) نشان می دهیم که این مجموعه می‌شود کلاس هم ارزی برای رابطه زیر مجموعه بودن در مجموعه A.

اهمیت و کاربردها

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

منابع

• Derek J.S. Robinson.(2003) An Introduction to Abstract Algebra. Germany. Walter de Gruyter.
• ریاضیات گسسته و کاربردهای آن (انگلیسی)