Introduction to Logic

توجه:

عناصر نظریه مجموعه‌ها:  رابطه  آخرین ویرایش: ۱۳۹۵/۰۷/۰۱ 

عناصر نظریه مجموعه‌ها

۱۱.۱ دوتایی‌ مرتب

گاه نیازمندیم برای اعضای مجموعه‌ای‌ مانند A={a, b} به نحوی ترتیب قائل شویم و برای مثال a را عضو اول و b را عضو دوم بنامیم. در این مواقع این ترتیب را با یک الحاقی، به‌صورت <a, b>، منظور می‌کنیم و می‌گوییم بنا به این الحاقی، یعنی <a, b>، و فارغ از ترتیب حضور اعضا در a ،A عضو نخست و b عضو بعدی A است. به <a, b> یک دوتایی مرتب می‌گوییم. بنابراین وقتی a و b یکی نیستند <a, b> و  <b, a> دو ترتیب متمایز را در {a, b} برای a و b مشخص می‌کنند. 

به همین نحو می‌توان از سه‌تایی مرتب مانند <b, a, c>و به‌طورکلی از nتایی‌ مرتب مانند:

  <a۱, a۲, ...,an> صحبت کرد.

به‌جا است پرسیده شود سرشت ریاضی این "الحاقی ترتیبی" چیست؟ جواب این است که یک دوتایی و به‌طورکلی nتایی مرتب یک مجموعه است. در مورد دوتایی مرتب داریم؛

 <a, b>={{a}, {a, b}}

 بنابراین: دوتایی مرتب  <a, b> فارغ از مجموعه A (در بالا) خود بیان شدنی است.

دوتایی مرتب <x, y> را به‌صورت (x,  y) نیز می‌نویسند.

برای هر دوتایی مرتب  <x, y> داریم:

  x=a  و  y=b   اگر و قط اگر   <x, y>= <a, b>

و

  x=y    اگر و قط اگر   <x, y>= <y, x>

 

۱۲.۱ ضرب دکارتی مجموعه‌ها:

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

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

X×Y={(x,y)| xX & yY}.

 

 

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

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

   B×A                        A×B  
/\/ | \
 ۰   ۱ a b c
/|\/|\/\ /\ /\
abb abb۰ ۱ ۰ ۱ ۰ ۱
            

 

مثال:  خط، صفحه و فضای اقلیدسی نمایش هندسی(اقلیدسی) مجموعه‌های زیر هستند ( به ترتیب از چپ به راست):

R۱=RR۲ = R×R;   R۳=R×R×R.

 اگر مجموعه A دارای n عضو و مجموعه B دارای m عضو باشد، آنگاه A×B دارای n×m عضو خواهد بود.

ضرب دکارتی دو مجموعه، خلاف ضرب اعداد، خاصیت جابجایی ندارد. یعنی، چنین نیست که همیشه A×B مساوی B×A باشد.


 

۱۳.۱ رابطه:

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

 (x, y, z)R×R×Rبه قسمی که xبین y و z باشد،

 یک رابطه در R تعریف می‌کند.

ازآنجاکه یک رابطه یک مجموعه است همه اعمال روی مجموعه‌ها روی آن نیز جاری خواهد بود. اگر نام رابطه اخیر را  R بنامیم، آنگاه:

 R={(x, y, z)|x, y, z R & y<x<z} 

و می‌توان نوشت:

(۱۳, ۱۱, ۲۱)R ; (۱۳, ۱۱, ۱۱)R

مثال:

دو مجموعه A و B به فرض، {a ،b ،c} و {۱ ،۰} را در نظر بگیرید. هریک از دو مجموعه زیر:

 R۱ = {(۰, a), (۰, b), (۰, c)}A ×B 
  R۲ = {(۰, ۱), (۱,۰)} A ×A = A۲ 

دو رابطه متمایز را تعریف می‌کنند. اکنون می‌توان نوشت:

 (۱, b)∈R۱

و نیز گفت:

۱ در رابطه R۱ با b است.

 هم‌چنین می‌نویسند:

  (۱, b)R۲

و می‌گویند:

۱ در رابطه R۲با b نیست.

 

 

علاوه به نوشتن (x, y)R  برای نشان دادن در رابطه R بودن x با  y، آن را به‌صورت xRy نیز می‌نویسند.  بنابراین می‌توان نوشت:   ۱ b و  ۱ a.

 ۱.۱۳.۱ رابطه تهی:

مجموعه تهی زیرمجموعه هر مجموعه‌ای‌ است، بنابراین مجموعه تهی یک رابطه است و می‌توان از آن بدون ‌ابهام  همچون رابطه تهی نام ‌برد زیرا فقط یک رابطه تهی وجود دارد.


۲.۱۳.۱ رابطه یکتایی:

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

فرض کنید Q ویژگی (رابطه یکتایی) گویایی در مجموعه اعداد حقیقی باشد، در این صورت برای نشان دادن این ویژگی برای شیء مانند  a (در اینجا عددی حقیقی) نوشته:  Qa [یا  Q(a)] و می‌خوانیم a عدد گویا است. یا، فرض کنید P ویژگی (رابطه یکتایی) عدد اول بودن در R باشد، در این صورت برای نشان دادن این ویژگی برای شیئی مانند  a (در اینجا عددی طبیعی) نوشته:  Pa [یا  P(a)] و می‌خوانیم a عدد اول است.


۳.۱۳.۱ رابطه دوتایی:

 برای n = ۲ رابطه را یک رابطه دوتایی می‌گویند. اگر A و B مجموعه باشند، ضرب دکارتی آن‌ها،A×B ، و هر زیرمجموعه آن یک رابطه دوتایی از A در B را تعریف می‌کند. وقتی هر دو مجموعه (به‌طورکلی عوامل ضرب دکارتی) در یک رابطه دوتایی در یک مجموعه، به فرض A، باشند، معمولاً به‌جای "رابطه از A در A" می‌گویند "رابطه در A". برای مثال اگر A مجموعه انسان‌ها باشد آنگاه:

R = {(x, y)|x, y∈A & است y برادر x}

رابطه دوتایی (برادر بودن) را در A تعریف می‌کند. فرض کنید پرویز، a، برادر پروین، b، باشد؛ در این صورت می‌نویسیم:

  (a, b)R

 یا

aR b

  نیز

(b, a)R

یا

 bR a.


 

۱.۳.۱۳.۱ رابطه همانندی:

 برای مجموعه دلخواه به رابطه{(x, x)|xA}  یک رابطه همانندی ( یا رابطه تساوی با نماد =) در A می‌گوییم.


 

۴.۱۳.۱   دامنه  رابطه

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

Domain(R)={x|x∈A & aA, xRa}A

 برای مثال اگر R رابطه برادر بودن در  A را مجموعه انسان‌ها باشد آنگاه دامنه R مجموعه همه انسان‌هایی است که برادر حداقل یک نفر هستند. [هیچ مادری عضو دامنه این رابطه نیست.]


۵.۱۳.۱  قلمرو رابطه:

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

Range(R)={y|y∈A & a∈A, aRx}A

برای مثال اگر R را رابطه برادر بودن در  A مجموعه انسان‌ها باشد آنگاه قلمرو R مجموعه همه انسان‌هایی است که دارای حداقل یک برادر هستند. [یک مادر ممکن است عضو قلمرو این رابطه باشد.]


۶.۱۳.۱  میدان رابطه:

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

Field(R)=Domain(R) Range(R)

 برای مثال اگر R رابطه برادر بودن در A مجموعه انسان‌ها باشد آنگاه میدان R مجموعه همه انسان‌هایی است که خود برادر کسی هستند یا دارای برادر هستند. در این صورت: اگر پرویز برادر پروین باشد آنگاه هر دو عضو میدان R هستند.


۷.۱۳.۱ گونه‌های ساده روابط

۱.۷.۱۳.۱ رابطه بازتابی:

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

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

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


۲.۷.۱۳.۱ رابطه متقارن:

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

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

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


۳.۷.۱۳.۱ رابطه پادمتقارن:

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

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

به‌عبارت‌دیگر برای هر yx در میدان R چنین نیست که xR y و yR x.

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

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

و

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

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


۴.۷.۱۳.۱ رابطه ترایایی:

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

  xR y & yR z xR z.

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


۶.۷.۱۳.۱ مجموعه مرتب جزئی

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

 مرتب جزئی بودن مجموعه‌ای مانند A توسط رابطه‌ای به فرض Rرا به‌صورت (A, R) (یا <A, R>) نشان می‌دهند. بنابراین می‌توان گفت (Z,) مرتب جزئی است و همین‌طور است (Z,) و نیز .(Ƥ(A),) مجموعه (Z+,|) که در آن | رابطه شمردن (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، در مجموعه {۴، ۳، ۲، ۱}:

hasse diagram- نمودار هس
نمودار هس برای مثال ۱.  در این مثال اولین عنصر وجود دارد ولی آخرین عنصر وجود ندارد.

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

hasse diagram- نمودار هس
نمودار هس برای مثال ۲.  در این مثال اولین عنصر و هم آخرین عنصر وجود دارد.

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

hasse diagram- نمودار هس
نمودار هس برای مثال ۳.   در این مثال نه اولین عنصر و نه آخرین عنصر وجود ندارد.

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

hasse diagram- نمودار هس
نمودار هس برای مثال ۴.   در این مثال نه اولین عنصر و نه آخرین عنصر وجود ندارد.

۴.۶.۷.۱۳.۱ ترتیب واژه نویسی (الفبایی) :

فرض کنید (A, <) و (B, <) دو مجموعه مرتب جزئی باشند. مراد از ترتیب واژه نویسی) در A×B وجود رابطه ترتیبی > در A×B است، به قسمی که، برای  (a۱, b۱)∈A×B و (a۲, b۲)∈B داشته باشیم:

   (a۱, b۱) ∈A×B < (a۲, b۲) ∈B 

اگر و فقط اگر:

  a۱ < a۲ یا (a۱ = a۲ و  b۱ < b۲)


۷.۷.۱۳.۱ مقایسه پذیری:

فرض کنید که (A, R) یک مجموعه مرتب جزئی و a و b دو عضو آن باشند. می‌گوییم  a و b مقایسه پذیراند اگر aRb یا bRa؛ در غیر این صورت آن‌ها را مقایسه ناپذیر می‌گوییم.


۸.۷.۱۳.۱ مجموعه مرتب کامل:

فرض کنید که (A, ) یک مجموعه مرتب جزئی، اگر هر دو عضو A مقایسه پذیر باشند آنگاه A را مرتب کامل و نیز را یک رابطه ترتیبی کامل یا ترتیب خطی در A می‌نامند.


۹.۷.۱۳.۱ مجموعه خوش‌ترتیب

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


۱۰.۷.۱۳.۱ اصل خوش‌ترتیبی:

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


۸.۱۳.۱ رابطه هم‌ارزی:

رابطه دوتایی R را رابطه هم‌ارزی گویند اگر  R:
۱-بازتابی
، -۲متقارن و  -۳ترایایی باشد.

رابطه تساوی/همانندی(=) یک رابطه هم‌ارزی است. ولی رابطه‌های برادری در انسان‌ها، در Z و همشهری(آ و ب همشهری‌اند اگر تابعیت حداقل یک کشور را داشته باشند) هم‌ارزی نیستند.

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

هر رابطه هم‌ارزی، به فرض ، میدان خود را به زیرمجموعه‌های دوبه‌دو از هم جدا تقسیم (افراز) می‌کند، به قسمی که:

۱- هر دو عضو متعلق به هر یک از این زیرمجموعه‌ها باهم در رابطه هستند؛

۲- هیچ دو عضو متعلق به دو زیرمجموعه متمایز در رابطه نیستند؛

۳- اجتماع زیرمجموعه‌های افرازی مساوی میدان رابطه است.

این زیرمجموعه‌ها را کلاس‌های هم‌ارزی می‌گویند. ازآنچه گفته شد برمی‌آید، اگر C۱ و C۲ دو کلاس هم‌ارزی باشند و دارای حداقل یک عضو مشترک باشند لزوماً داریم C۱=C۲.

به‌عبارت‌دیگر، فرض کنید یک رابطه هم‌ارزی و DΦ میدان آن باشد. در این صورت به:

 CxD = {x D|x a, aD}

که یک زیرمجموعه D است کلاس هم‌ارزی در D به نمایندگی x می‌گوییم. می‌توان نشان داد برای هر x, yD داریم:

۱:   x y CxD CyD  

۲:   x=y CxD= CyD

و اگر تعداد کلاس‌های هم‌ارزی را  nR بگیریم:

۳: CDCD . . .CxnD=D


۱.۸.۱۳.۱  رابطه هم‌نهشتی در R∪{۰}:

 مثال: فرض کنید رابطه R۵ را در مجموعه R∪{۰} این‌گونه تعریف کنیم:  xR۵y اگر و فقط اگر باقی‌مانده‌های حاصل از تقسیم صحیح x و y به ۵ مساوی باشند (به‌عبارت‌دیگر، تفاضل آن‌ها به ۵ بخش‌پذیر باشد). بنابراین داریم:

۰،R۵۵

،۵R۵۱۰

،۱۰R۵۵

،۵R۵۵

،۰R۵۱۵

،۱R۵۶

،۶R۵۱۱

۱R۵۱۱

و مانند آن‌ها.

به‌آسانی می‌توان نشان ‌داد R۵ یک رابطه هم‌ارزی است و R∪{۰} را به پنج کلاس هم‌ارزی ۰ ,۱, ۲, ۳, ۴ به‌قرار زیر:

 ۰ = {x |به ۵ بخش‌پذیر باشد.  x-۰}= {۰, ۵, ۱۰, ۱۵, ۲۰, . . .}

 ۱ ={x |به ۵ بخش‌پذیر باشد.  x-۱}= {۱, ۶, ۱۱, ۱۶, ۲۱, . . .}

. . . . . . .

. . . . . . .

 

 ۴ ={x |به ۵ بخش‌پذیر باشد.  x-۴}= {۴, ۹, ۱۴, ۱۹, ۲۴, . . .}

افراز می‌کند. می‌توان دید که:

R∪{۰}= ۰۱۲۳۴

به R۵ رابطه هم‌نهشتی (به سنج/از سنجیدن ۵) گفته و می‌نویسند:

  ۱[۵ به سنج] به سنج]  

و نیز مانند آن برای بقیه.

رابطه هم‌نهشتی را می‌توان برای nR تعمیم داد. می‌گوییم k, lR∪{0} به سنج n هم‌نهشت هستند و می‌نویسیم:

   k [n به سنج] = l  

اگر و فقط اگر k-l ،n را بشمارد.


۹.۱۳.۱ مثال‌هایی از رابطه:

فرض کنید E مجموعه انسان‌ها و Rz و Rm به ترتیب ویژگی‌های(رابطه‌های یکتایی) زن بودن و مرد بودن در E باشند، آنگاه:

 

R۱={( x, y)|Rz(x) & Rm(y)}  : دوتایی‌هایی که اولی زن و بعدی مرد

R۲={(x, y)|xR1y & (است x همسر y)}  :رابطه زن‌و‌شوهری

R۳={(x, y)| x, y(RzRm) &  (است x فرزند y)}    :رابطه فرزندی

R۴={(x, y, z)|xR۲y & xR۳z & yR۳z & zRz}  :زن‌ و شوهر‌های با حداقل‌ ۱ فرزند دختر

R۵={(x, y, w, z)|(x, y, w)R۴  & (x, y, z)R۴  & w≠z} :زن و شوهرهای با حداقل‌ ۲ فرزند دختر


ادامه: . . . . .

 

© 1987 - 2017 KHcc Sc.