תורת הקבוצות

ספר אלקטרוני מאת: ניר אדר

3.3. תכונות של יחסים

רפלקסיביות: לכל $plot:\[a \in A\]$ , מתקיים $plot:\[\left\langle {a,a} \right\rangle \in R\]$ .
סימטריות: אם $plot:\[\left( {a,b} \right) \in R\]$ , מתקיים $plot:\[\left( {b,a} \right) \in R\]$ .
אנטי סימטריות: אם $plot:\[\left\langle {a,b} \right\rangle ,\left\langle {b,a} \right\rangle \in R\]$ אזי בהכרח $plot:\[a = b\]$ .
א-סימטריה: אם $plot:\[\left\langle {a,b} \right\rangle \in R\]$ , מתקיים $plot:\[\left\langle {b,a} \right\rangle \notin R\]$ .
טרנזיטיביות: אם $plot:\[\left\langle {a,b} \right\rangle ,\left\langle {b,c} \right\rangle \in R\]$ אזי $plot:\[\left\langle {a,c} \right\rangle \in R\]$ .

דוגמא

תהי הקבוצה $plot:\[A = \left\{ {a,b,c} \right\}\]$ . נגדיר יחס $plot:\[R\]$ מעל $plot:\[A\]$ $plot:\[\left( {R \subseteq A \times A} \right)\]$ :

$plot:\[R = \left\{ {\left\langle {a,b} \right\rangle ,\left\langle {b,b} \right\rangle ,\left\langle {c,c} \right\rangle ,\left\langle {b,c} \right\rangle ,\left\langle {a,c} \right\rangle } \right\}\]$

האם היחס רפלקסיבי? לא, כי $plot:\[\left\langle {a,a} \right\rangle \notin R\]$ אבל $plot:\[a \in A\]$ .

האם היחס סימטרי? לא, כי $plot:\[\left\langle {a,b} \right\rangle \in R\]$ אבל $plot:\[\left\langle {b,a} \right\rangle \notin R\]$

האם היחס הוא אנטי סימטרי? כן. הזוגות היחידים שמקיימים $plot:\[\left\langle {a,b} \right\rangle ,\left\langle {b,a} \right\rangle \in R\]$ הם $plot:\[\left\langle {b,b} \right\rangle \]$ ו- $plot:\[\left\langle {c,c} \right\rangle \]$ לכן היחס הוא אנטי סימטרי.

האם היחס הוא א-סימטרי? לא, כי $plot:\[\left\langle {b,b} \right\rangle \]$ ו- $plot:\[\left\langle {c,c} \right\rangle \]$ נמצאים ביחס.

האם היחס טרנזיטיבי? כן.

רפלקסיביות באופן ריק

אם $plot:\[A \ne \varphi \]$ ו-R רפלקסיבי, אזי בהכרח $plot:\[R \ne \varphi \]$ . רפלקסיביות נכונה באופן ריק רק כאשר R ריקה.

טרנזיטיביות באופן ריק

דוגמא: $plot:\[R = \left\{ {\left\langle {a,b} \right\rangle ,\left\langle {a,c} \right\rangle } \right\}\]$ . רלציה זו טרנזיטיבית באופן ריק.

דוגמא

נתונות הקבוצות $plot:\[A,B,C\]$ כך שמתקיים $plot:\[A \cap B = \phi ,A \ne \phi ,B \ne \phi \]$ וגם $plot:\[A \subseteq C,B \subseteq C\]$ .

נגדיר יחס R מעל C:

$plot:\[R = A \times B \subseteq C \times C\]$

האם היחס רפלקסיבי?

לא. $plot:\[A \ne \varphi \]$ , ומכאן קיים $plot:\[a \in A\]$ . $plot:\[B \ne \varphi \]$ , ומכאן קיים $plot:\[b \in B\]$ . מכאן $plot:\[\left\langle {a,b} \right\rangle \in R\]$

אם b=a אזי $plot:\[b \in A\]$ בסתירה לכך שהחיתוך בין A ל-B הוא קבוצה ריקה.

האם היחס סימטרי?

לא. יהי $plot:\[\left\langle {a,b} \right\rangle \in R\]$ (קיים כזה). אם $plot:\[\left\langle {b,a} \right\rangle \in R\]$ אזי $plot:\[b \in A \cap B\]$ בסתירה לנתון.

האם היחס אנטי סימטרי?

כן, באופן ריק.

אם $plot:\[\left\langle {a,b} \right\rangle \in R\]$ וגם $plot:\[\left\langle {b,a} \right\rangle \in R\]$ אזי $plot:\[b \in A \cap B\]$ בסתירה לנתון.

לכן אין זוג איברים $plot:\[\left\langle {a,b} \right\rangle \]$ ו- $plot:\[\left\langle {b,a} \right\rangle \]$ הנמצאים שניהם ביחס.

האם היחס א-סימטרי?

כן. אם $plot:\[\left\langle {a,b} \right\rangle \in R\]$ , נניח בשלילה שגם $plot:\[\left\langle {b,a} \right\rangle \in R\]$ אזי $plot:\[b \in A \cap B\]$ בסתירה לנתון.

האם היחס טרנזיטיבי?

כן, באופן ריק.

טענה

יהי $plot:\[R\]$ יחס, אזי מתקיים כי $plot:\[R\]$ סימטרי אמ"מ $plot:\[R = {R^{ - 1}}\]$ .

הוכחה:

$plot:\[ \Leftarrow \]$ נניח כי $plot:\[R\]$ סימטרי.

ואז: $plot:\[\left\langle {a,b} \right\rangle \in R\mathop \Leftrightarrow \limits_{{\text{simetric}}} \left\langle {b,a} \right\rangle \in R \Leftrightarrow \left\langle {a,b} \right\rangle \in {R^{ - 1}}\]$

$plot:\[ \Rightarrow \]$ נניח כי $plot:\[R = {R^{ - 1}}\]$ .

יהי $plot:\[\left\langle {a,b} \right\rangle \in R\]$ . על פי הגדרת $plot:\[{R^{ - 1}}\]$ נובע: $plot:\[\left\langle {b,a} \right\rangle \in {R^{ - 1}}\]$ . לפי הנתון $plot:\[R = {R^{ - 1}}\]$ ולכן $plot:\[\left\langle {b,a} \right\rangle \in R\]$ .

לפרק הקודם3.2. הרכב רלציות

לפרק הבא4. פונקציות

מאת: סטודנטית

15/12/2020 19:15

הוכחות להגדרה 2

אשמח להגדרות פורמליות מפורטות עבור המשפט. תודה רבה

מאת: ילדה

17/4/2018 19:45

תודה רבה!

תודה על ההסבר המצוין

מאת: אני

24/12/2017 13:48

תודה

מברוק! תודה

מאת: ברק

22/12/2017 18:24

יש לכם טעות

בסגור הטרנזיטיבי שהתקבל אצלכם, קיימים הזוגות <4,1> ו-<1,4>, אבל מתוקף היותו טרנזיטיבי הוא חייב גם להכיל את <1,1> ו-<4,4>. ההגדרה של טרנזיטיביות לא מחייבית a,b,c שונים.

כנ"ל לגבי <2,3> ו-<4,2> - חייב להימצא הזוג הסדור <4,3>.
מצאתי עוד 3 דוגמאות כאלה..

מאת: יואב

10/12/2017 22:33

מבלבל

היית צריך לתת דוגמאות גם ליחסים לא סימטריים.... התבלבלתי ממש בין X לY בגלל זה...

מאת: יואב

10/12/2017 22:32

מבלבל

היית צריך לתת דוגמאות גם ליחסים לא סימטריים.... התבלבלתי ממש בין X לY בגלל זה...

מאת: אמיר

11/1/2017 13:15

קבוצה סופית

מישו יכול להעלות את ההוכחה לכך שכל תת קבוצה של קבוצה סופית היא סופית ? זה ברור אבל אני צריך את ההגדרה הפורמלית לזה ..

מאת: רעות

26/11/2016 22:48

תודה רבה

תודה רבה ספר מעולה מסביר מצויין שתצליח תמיד :-)

מאת: עומר

1/6/2013 21:30

סגור טרנזיטיבי

ניר אתה בטוח ש- (4,2) הוא חלק מהסגור הטרנזיטיבי (משפט 3 מלמעלה)?
אני לא סגור על החומר, אבל אני לא חושב שזה נכון...

מאת: אחד שלומד

8/3/2013 11:34

יפה מאוד אך ישנן כמה טעויות

ישנן כמה טעויות (קריטיות להוכחה) כשעברתי על החומר,
למשל בהוכחה ש R* טרנזיטיבית (סעיף 2) יש בלבול שלם בין x,y,z אז צריך לתקן את זה.

מאת: אני

26/11/2011 12:01

כל הכבוד!!!!

כל הכבוד על העבודה שעשית כאן!!!
נורא עוזר!!!!

מאת: אני

20/11/2011 20:01

תודה רבה רבה רבה רבה!

כל הכבוד על העלאת הסיכום המעולה הזה לטובת כולם!

מאת: אלעד

8/7/2011 20:08

המון תודה

וואו, חומר כל כך ברור ומסודר!
עברתי על עשרות ספרים ואף אחד לא ברור וענייני כמו זה - פשוט כל הכבוד!
תודה, תודה תודה!

מאת: אולג

6/4/2010 21:54

תודה רבה!!!!!!!!

אף פעם לא ברור לי מה האינטרס של אנשים כמוך, להעלות חומר ממש מועיל לאינטרנט בחינם...

בכל אופן, רציתי לומר: כל הכבוד ותודה רבה, הסיכומים שלך מאוד עזרו לי ואני מאוד מעריך את הזמן והמאמץ שהושקע בהם.

והלוואי ויהיו רבים כמוך...

דיווח על הפרת זכויות יוצרים