رابطه و ترتیب

■ مقدمه

کلید واژه این قسمت که در ادامه قسمت قبل، یعنی مجموعه و اعمال روی آن، می‌آید  «رابطه» است. بنابراین واکاوی دقیق مفهوم رابطه آماج این قسمت است. گونه‌ای هستی شناسی یک مجموعه مفهوم نگاری هندسه وارانه (اصل موضوعی) رابطه‌مندی بین عناصر آن مجموعه است. حاصل چنین مفهوم نگاری به ساختار آن مجموعه موسوم است. به چنین مجموعه‌ای عالم سخن نیز گفته می‌شود.  به دیگر سخن، مراد از یک ساختار، به فرض U، عبارت است از (۱): یک مجموعه، به فرض D، موسوم به عالم سخن و (۲): مجموعه دیگری، به فرض R، شامل روابط مفهوم نگاری شده در D. ساختار U را به صورت دوتایی مرتب:

U = <D, R >
R = {R_۱, R_۲, . . . }

 که در آن R_i یک رابطه در D است می‌نمایانند.

 اکنون، آنچه باقی می‌ماند اینکه رابطه چیست، انواع آن کدام است و اعمال روی آن چگونه است؟

■ دوتایی‌ مرتب

گاهی نیاز است برای دو عنصر به فرض  a و b به گونه‌ای ترتیب قائل شویم و برای مثال a را عضو اول و b را عضو دوم بنامیم. در این مواقع ترتیب مورد نظر را به‌صورت <a, b> بیان کرده و به آن دوتایی مرتب (یا زوج مرتب) گفته. بنابراین وقتی a و b مساوی نباشند <a, b> و  <b, a> نیز متمایزاند. به عبارت دیگر:

<a, b> = <b, a> ⇔ a = b.

 

به‌جا است پرسید سرشت <x, y> چیست؟ پاسخ آن است که یک دوتایی مرتب مجموعه‌ای است که به گونه زیر تعریف (ساخته) می‌شود:

 <x, y> = {{x}, {x, y}}

 <y, x> = {{y}, {x, y}}

■ ضرب دکارتی مجموعه‌ها

اگر X و Y مجموعه باشند آنگاه ضرب دکارتی X در Y مجموعه همه دوتایی‌های مرتب است، به قسمی که عنصر اول آن‌ها در X و عنصر دوم آن‌ها در Y باشد.

به‌عبارت‌دیگر، ضرب دکارتی دو مجموعه X و Y، که با X×Y نشان می‌دهیم، به‌قرار زیر تعریف می‌شود:

X×Y={(x,y)| x∈X ∧ y∈Y}.

مثال:  فرض کنید A و B به ترتیب {a ،b ،c} و {۱ ،۰} باشند، آنگاه

A×B={(a, ۰), ( b, ۰), (c, ۰), (a, ۱), (b, ۱), (c, ۱)};
B×A={(۰, a), (۰, b), (۰, c), (۱, a), (۱, b), (۱, c)}.

■ دامنه رابطه

فرض کنید R یک رابطه در A باشد. دامنه رابطه  R، که آن را با Dom(R) نشان می‌دهیم، مجموعه xهای متعلق به A است، به قسمی که برای حداقل یک y∈A داشته باشیم: (x, y)∈R .

Dom(R)={x ∈ A|∃a ∈A, x R a}

■ قلمرو رابطه

فرض کنید R یک رابطه در A باشد. قلمرو رابطه R، که آن را با Rng(R) نشان می‌دهیم، مجموعه yهای متعلق به A است، به قسمی که برای حداقل یک x∈A داشته باشیم: (x, y)∈R .

Rng(R)={y ∈ A|∃b ∈A, b R x}

■ میدان رابطه

فرض کنید R یک رابطه در A باشد. اجتماع دامنه و قلمرو  R را میدان رابطه  R می‌نامند.

Field(R)=Dom(R) ∪ Rng(R)

■ ترکیب رابطه‌ها

فرض کنید R یک رابطه از A در B و S یک رابطه از B در C باشد. ترکیب رابطه‌های  R با S که آن را به صورت S◦R می‌نویسند رابطه‌ای است که مطابق زیر تعریف می‌شود.

S ◦ R = {(a, c) ∈ A × C|∃b ∈ B; (a, b) ∈ R, (b, c) ∈ S}.

_______________

•مثال (تکرار برای یادآوری)⤺

فرض کنید S مجموعه همه دانشجویان، C مجموعه همه درس‌های ارایه شده، R مجموعه همه اتاق‌های خوابگاه و P مجموعه همه استادان دانشگاه آبان باشد. در این صورت از جمله روابط زیر در این عالم سخن قابل تمیز‌اند:

۱.  L = {(s, r) ∈ S × R | دانشجوی s در اتاق r ساکن است}.

۲.  E = {(s, c) ∈ S × C | دانشجوی s در درس c ثبت نام کرده}.

۳.  T = {(c, p) ∈ C × P | درس c توسط استاد p تدریس می‌شود}.

_______________

_______________

•مثال⤺

 اگر E و T رابطه‌های آمده در مثال بالا باشند، آنگاه ترکیب T◦E که رابطه‌ای از C به P است به قرار زیر خواهدبود:

T ◦ E = {(s, p) ∈ S × P: ∃c ∈ C; (s, c) ∈ E, (c, p) ∈ T}

مجموعه همه دوتایی های مرتب (دانشجو، استاد) به قسمی که، دانشجو در درسی که استاد تدریس میکند ثبت نام کرده.

_______________

•مثال⤺

E^-۱ = {(c, s) ∈ C × S: (s, c) ∈ E}

= {(c, s) ∈ C × S: دانشجوی s ثبت نام شده در درس c است}

مجموعه همه دوتایی های مرتب (درس، دانشجو) به قسمی که، دانشجو در آن درس ثبت نام کرده.

_______________

•مثال⤺

E ◦ L^-۱ = {(r, c) ∈ R × C: ∃s ∈ S; (r, s) ∈ L^-۱, (s, c) ∈ E}

= {(r, c) ∈ R × C: ∃s ∈ S; (s, r) ∈ L, (s, c) ∈ E}

= {(r, c) ∈ R × C: دانشجویی هست در اتاق r ساکن است و در درس c ثبت نام شده }

مجموعه همه دوتایی های مرتب (اتاق، درس) به قسمی که، دانشجو ساکن اتاق در آن درس ثبت نام کرده.

_______________

•مثال⤺

E^-۱ ◦ E = {(s, t) ∈ S × S: ∃c ∈ C; (s, c) ∈ E, (c, t) ∈ E^-۱}

= {(s, t) ∈ S × S| درسی هست که دانشجوی s و دانشجوی t هردو در آن ثبت نام کرده‌اند}

مجموعه همه دوتایی های مرتب (دانشجو۱، دانشجو۲) به قسمی که، درسی باشد که دانشجو۱ و دانشجو۲ در آن درس ثبت نام کرده.

_______________

•مثال⤺

E ◦ E^-۱ = {(c_۱, c_۲) ∈ C × C: ∃s ∈ S; (c_۱, s) ∈ E^-۱, (s, c_۲) ∈ E}

= {(c_۱, c_۲) ∈ C × C: دانشجویی هست که در هر دو درس c_۱ و  c_۲ ثبت نام شده‌ }

مجموعه همه دوتایی های مرتب (درس۱، درس۲) به قسمی که، دانشجویی باشد  که در درس۱ و درس۲ ثبت نام کرده.

 

______________

•⤺

همانطور که در مثال پیش دیده می‌شود، چنین نیست که همیشه:

 R_۱ ◦ R_۲ = R_۲ ◦ R_۱.

_______________

•مثال⤺

T ◦ (E ◦ L^-۱) =

= {(r, p) ∈ R × P: ∃c ∈ C; [(r, c)∈E ◦ L^-۱, (c, p)∈T]}

= {(r, p) ∈ R × P|∃s ∈ S; بعضی دانشجو که در اتاق r ساکن است در درس c ثبت نام شده و c تدریس شده توسط p است}

= {(s, t) ∈ S × S| دانشجویی هست که در اتاق r ساکن است و در بعض درس تدریس شده توسط p ثبت نام شده}

_______________

•مثال⤺

( T ◦ E) ◦ L^-۱ == {(r, p) ∈ R × P: ∃s ∈ S; [(r, s)∈L^-۱, (s, p)∈T ◦ R]}

= {(r, p) ∈ R × P: ∃s ∈ S; دانشجو s در اتاق r ساکن است و در بعضی درس تدریس شده توسط p ثبت نام شده}

= {(r, p) ∈ R × P: دانشجویی که در اتاق r ساکن است و در بعض درس تدریس شده توسط p ثبت نام شده}

_______________

■ چند ویژگی

■ تحدید رابطه

فرض کنید R یک رابطه در A و نیز B⊆A باشد؛ آنگاه به رابطه تعریف شده در زیر، که آن را با R|_B نشان داده، تحدید رابطه R به B گویند:

R|_B = R∩(B×B) = {(x, y)|(x‚ y)∈R ∧ x‚ y∈B}

■ رابطه بازتابی

رابطه دوتایی R را رابطه بازتابی گویند اگر:

 برای هر عضو میدان  R مانند x داشته باشیم: xR x.

رابطه ≤ (بزرگ‌تر یا مساوی) و نیز ≥ (کوچک‌تر یا مساوی) در  بازتابی‌اند ولی > (کوچک‌تر) و < (بزرگ‌تر) چنین نیستند.

■ رابطه متقارن

رابطه دوتایی  R را رابطه متقارن گویند اگر و فقط اگر:

برای هر دو عضو میدان R مانند x, y، اگر xR y آنگاه yR x.

رابطه برادری در انسان‌ها یک رابطه متقارن نیست؛ زیرا از این‌که a برادر b است لزوماً به دست نمی‌آید b برادر a است. همچنین رابطه ≥ در متقارن نیست. رابطه تساوی در هر میدان متقارن است.

■ رابطه پادمتقارن

رابطه دوتایی  R را  رابطه پادمتقارن گویند اگر و فقط اگر :

برای هر دو عضو میدان  R مانند x, y، اگر xR y و  yR x آنگاه  y = x.

به‌عبارت‌دیگر:

 برای هر x و y در میدان R به قسمی که y≠x چنین نیست که xR y و yR x.

 رابطه < در پادمتقارن است. رابطه‌های:

 {(۱,۲) ,(۲, ۳),(۴, ۱)}

و

  {(۱,۱), (۳, ۳)}

در{۱, ۲, ۳, ۴}  پادمتقارن هستند.

■ رابطه ترایایی

رابطه دوتایی R را رابطه ترایایی گویند اگر اگر و فقط اگر برای هر سه عضو میدان  R مانند x, y, z:

  xR y ∧ yR z ⇒ xR z.

 رابطه ≥  و  ≥ در ترایایی‌اند. رابطه برادری در انسان‌ها ترایایی نیست.

■ رابطه ترتیبی

به یک رابطه دوتایی که:

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

■ مجموعه مرتب جزئی

به مجموعه‌ای، به فرض A، که در آن، یک رابطه ترتیبی، به فرض R، تعریف شده، یک مجموعه مرتب جزئی  گفته. در این صورت می‌گوییم R مجموعه A را مرتب شده.

 مرتب جزئی بودن مجموعه‌ای مانند A توسط رابطه‌ای به فرض R را به‌صورت (A, R) یا <A, R> نشان می‌دهند. بنابراین می‌توان نوشت (, ≤)، (, ≥)، (Ƥ(A),⊆) و نیز نوشت (⁺,|) که در آن | رابطه شمردن است (x|y؛ اگر y ،x را بشمرد).

☚ به یک مجموعه مرتب جزئی یک Poset  (Partially ordered set) نیز گفته می‌شود.

☚   مجموعه {۴، ۳، ۲، ۱} با رابطه تقسیم‌پذیری، |، یک مجموعه مرتب جزئی است

■ کوچک‌ترین عنصر

فرض کنید (A, R) یک مجموعه مرتب جزئی باشد. در این صورت، اگر a در A وجود داشته به قسمی که برای هر عنصر مثل x در  A داشته باشیم  aRx، آنگاه به a کوچک‌ترین عنصر [نیز: اولین عنصر ] A گفته.

☚ به‌آسانی می‌توان نشان داد که اولین عنصر برای هر مجموعه، در صورت وجود، یکتا است (با بهره بردن از پادمتقارن بودن رابطه ترتیبی جزئی.)

■ بزرگ‌ترین عنصر

فرض کنید (A, R) یک مجموعه مرتب جزئی باشد. در این صورت، اگر  b در A وجود داشته به قسمی که برای هر عنصر مثل x در  A داشته باشیم  xRb، آنگاه به b بزرگ‌ترین عنصر [و نیز:  عنصر آخرین] A گفته.

☚ به‌آسانی می‌توان نشان داد که آخرین عنصر برای هر مجموعه، در صورت وجود، یکتا است (با بهره بردن از پادمتقارن بودن رابطه ترتیبی.)

■ نمایاندن رابطه (نمودار هس)

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

مثال ۱- رابطه  x|y، در مجموعه {۴، ۳، ۲، ۱}:

مثال ۲- رابطه کوچک‌تری، >، در مجموعه {۴، ۳، ۲، ۱}:

مثال ۳- رابطه R در مجموعه {۱۲، ۶، ۵، ۴، ۳} به قسمی که: xRy اگر و فقط اگر x مقسوم‌علیه y یا y مقسوم‌علیه x باشد (رابطه R یک رابطه ترتیبی جزئی نیست، زیرا پادمتقارن نیست.)

مثال ۴- رابطه Rدر مجموعه {۲۴، ۱۵، ۱۲، ۱۰، ۸، ۶، ۵، ۳، ۲} به قسمی که:  xRy اگر x  ،y را بشمرد.

مثال ۵- رابطه ⊆در مجموعه توانی مجموعه {a, b, c}.