תורת הקבוצות

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

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

תהי הקבוצה $plot:\[A = \left\{ {1,2,3,4,5} \right\}\]$ ותהי הרלציה $plot:\[R = \left\{ {\left\langle {1,2} \right\rangle ,\left\langle {2,3} \right\rangle ,\left\langle {2,4} \right\rangle ,\left\langle {4,5} \right\rangle ,\left\langle {5,1} \right\rangle } \right\}\]$ .

הסגור הטרנזיטיבי יהיה $plot:\[\left\{ {\left\langle {1,2} \right\rangle ,\left\langle {2,3} \right\rangle ,\left\langle {2,4} \right\rangle ,\left\langle {4,5} \right\rangle ,\left\langle {5,1} \right\rangle ,\left\langle {1,3} \right\rangle ,\left\langle {4,1} \right\rangle ,\left\langle {1,4} \right\rangle ,\left\langle {1,5} \right\rangle ,\left\langle {2,5} \right\rangle ,\left\langle {4,2} \right\rangle } \right\}\]$ .

נשים לב שאם אחרי שהוספנו איברים, ניתן לעשות חיבורים נוספים, יש לעשותם.

בהינתן רלציה R מעל A, נגדיר את הרלציה $plot:\[{R^*}\]$ באופן הבא:

$plot:\[{R^*} = R \cup {R^2} \cup {R^3} \cup ... = \cup {R^i},i = \mathbb{N} - \{ 0\} \]$

מתקיים כי $plot:\[\left\langle {x,y} \right\rangle \in {R^*}\]$ אמ"מ קיים $plot:\[i \geqslant 1\]$ כך ש $plot:\[\left\langle {x,y} \right\rangle \in {R^i}\]$ .

טענה

אם רלציה מקיימת את $plot:\[\alpha \]$ , אז היא עצמה הסגור שלה ביחס ל- $plot:\[\alpha \]$ . מכאן שהסגור הטרנזיטיבי של רלציה טרנזיטיבית R הוא R.

טענה

לכל רלציה $plot:\[R\]$ , $plot:\[{R^*}\]$ הוא הסגור הטרנזיטיבי שלה.

הוכחה:

כדי להוכיח ש- $plot:\[{R^*}\]$ היא הסגור הטרנזיטיבי של $plot:\[R\]$ צ"ל:

1. $plot:\[R \subseteq {R^*}\]$ .

2. $plot:\[{R^*}\]$ טרנזיטיבית.

3. לכל רלציה $plot:\[T\]$ , אם $plot:\[T\]$ היא טרנזיטיבית וגם $plot:\[R \subseteq T\]$ אזי $plot:\[{R^*} \subseteq T\]$ .

ברור שמתקיים, כי $plot:\[{R^*} = R \cup {R^2} \cup ... \supseteq R\]$ .

צריך להוכיח כי אם $plot:\[\left\langle {x,y} \right\rangle ,\left\langle {x,z} \right\rangle \in {R^*}\]$ אזי $plot:\[\left\langle {x,z} \right\rangle \in {R^*}\]$ .

$plot:\[\left\langle {x,y} \right\rangle ,\left\langle {x,z} \right\rangle \in {R^*}\]$ גורר כי קיים $plot:\[i \geqslant 1\]$ , $plot:\[\left\langle {x,y} \right\rangle \in {R^i}\]$ וקיים $plot:\[j \geqslant 1\]$ , $plot:\[\left\langle {y,z} \right\rangle \in {R^j}\]$ כך ש

$plot:\[\left\langle {y,z} \right\rangle \in {R^*} \Leftarrow \left\langle {y,z} \right\rangle \in {R^{i + j}} \Leftarrow \left\langle {y,z} \right\rangle \in {R^i} \cdot {R^j}\]$

נשתמש בטענה אם $plot:\[R \subseteq T\]$ אזי לכל $plot:\[i \in \mathbb{N}\]$ מתקים $plot:\[{R^i} \subseteq {T^i}\]$ .

תהי T טרנזיטיבית, $plot:\[R \subseteq T\]$ . צריך להוכיח כי $plot:\[{R^*} \subseteq T\]$

יהי $plot:\[\left\langle {x,y} \right\rangle \in {R^*}\]$ . מכאן קיים $plot:\[k\]$ כך ש- $plot:\[\left\langle {x,y} \right\rangle \in {R^k}\]$ . ולפי טענת העזר: $plot:\[R \subseteq T\]$ .

T טרנזיטיבית. מכאן קיים $plot:\[k\]$ כך ש- $plot:\[\left\langle {x,y} \right\rangle \in {T^k}\]$ ., ולכן $plot:\[\left\langle {x,y} \right\rangle \in T\]$ .

תכונה

אם $plot:\[A\]$ סופית אזי $plot:\[{R^*} = R \cup {R^2} \cup ... \cup {R^{\left| A \right|}}\]$ .

דוגמא

נגדיר את הקבוצה הבאה: $plot:\[B = \left\{ {A|A \subseteq \mathbb{N},A \ne \phi ,\left| A \right| \leqslant 10} \right\}\]$ ונגדיר יחס $plot:\[S\]$ מעל $plot:\[B\]$ בצורה הבאה:

$plot:\[S = \left\{ {\left\langle {{A_1},{A_2}} \right\rangle |{A_1} \cap {A_2} \ne \phi } \right\}\]$

האם $plot:\[S\]$ הינו יחס טרנזיטיבי?
מהו $plot:\[{S^*}\]$ ?

$plot:\[S\]$ איננו יחס טרנזיטיבי.

דוגמא נגדית: יהיו הקבוצות $plot:\[{A_1} = \left\{ {1,2} \right\},{A_2} = \left\{ {2,3} \right\},{A_3} = \left\{ {3,4} \right\}\]$ .

מתקיים: $plot:\[\left\langle {{A_1},{A_2}} \right\rangle \in S,\left\langle {{A_2},{A_3}} \right\rangle \in S\]$ אולם $plot:\[\left\langle {{A_1},{A_3}} \right\rangle \notin S\]$ .

כאשר אנו נתקלים בשאלה מסוג זה, השלב הראשון בפיתרון יהיה להבין מיהו $plot:\[{S^2}\]$ על מנת לקבל תחושה לגבי הפתרון.

$plot:\[{S^2} = \left\{ {\left. {\left\langle {{A_1},{A_3}} \right\rangle } \right|\exists {A_2}:\left\langle {{A_2},{A_3}} \right\rangle \in S,\left\langle {{A_1},{A_2}} \right\rangle \in S} \right\}\]$

נטען: $plot:\[{S^2} = B \times B\]$ .

ברור כי $plot:\[{S^2} \subseteq B \times B\]$ מכיוון ש- $plot:\[S\]$ הינו יחס מעל $plot:\[B\]$ .

צ"ל: $plot:\[B \times B \subseteq {S^2}\]$ .

תהינה $plot:\[{A_1},{A_3} \in B\]$ . צריך למצוא $plot:\[{A_2}\]$ כך שמתקיים $plot:\[\left\langle {{A_1},{A_2}} \right\rangle \in S,\left\langle {{A_2},{A_3}} \right\rangle \in S\]$ .

$plot:\[\exists {a_1} \in {A_1} \Leftarrow {A_1} \ne \phi \Leftarrow {A_1} \in B\]$ . כמו כן $plot:\[\exists {a_3} \in {A_3} \Leftarrow {A_3} \ne \phi \Leftarrow {A_3} \in B\]$ .

נבחר $plot:\[{A_2} = \left\{ {{a_1},{a_3}} \right\}\]$ . נוודא כי $plot:\[{A_2} \in B\]$ .

$plot:\[{a_1} \in {A_1} \cap {A_2} \ne \phi \]$ ומכאן $plot:\[\left\langle {{A_1},{A_2}} \right\rangle \in S\]$ . $plot:\[{a_2} \in {A_2} \cap {A_3} \ne \phi \]$ ומכאן $plot:\[\left\langle {{A_2},{A_3}} \right\rangle \in S\]$ .

מסקנה: $plot:\[\left\langle {{A_1},{A_3}} \right\rangle \in {S^2}\]$ .

דוגמא

נתון $plot:\[R \subseteq \mathbb{N} \times \mathbb{N}\]$ , $plot:\[R = \left\{ {\left. {\left\langle {a,b} \right\rangle } \right|a + b{\text{ is odd}}} \right\}\]$ , לדוגמא $plot:\[\left\langle {1,2} \right\rangle \in R\]$ .

א. מצא את $plot:\[{R^2}\]$ .

ב. מצא את הסגור הטרנזיטיבי.

א.

נסמן את הקבוצה הבאה ב- $plot:\[T\]$ : $plot:\[T = \left\{ {\left. {\left\langle {a,b} \right\rangle } \right|a + b{\text{ is even}}} \right\}\]$ .

נטען: $plot:\[{R^2} = T\]$ , כאשר $plot:\[{R^2} = \left\{ {\left. {\left\langle {x,y} \right\rangle } \right|\left\langle {x,z} \right\rangle ,\left\langle {z,y} \right\rangle \in R} \right\}\]$ .

יהיו $plot:\[\left\langle {z,y} \right\rangle ,\left\langle {x,z} \right\rangle \in R\]$ .

יתכנו שני מקרים:

1. $plot:\[z\]$ אי זוגי, $plot:\[x\]$ זוגי $plot:\[ \Leftarrow \]$ $plot:\[y\]$ זוגי.

2. $plot:\[z\]$ זוגי, $plot:\[x\]$ אי זוגי $plot:\[ \Leftarrow \]$ $plot:\[y\]$ אי זוגי.

בשני המקרים מתקיים $plot:\[x + y\]$ הוא זוגי, ולכן הראנו $plot:\[{R^2} \subseteq T\]$ .

כעת נראה את הכיוון השני: יהיה האיבר $plot:\[\left\langle {a,b} \right\rangle \in {R^2}\]$ .

אם $plot:\[a\]$ זוגי, נבחר $plot:\[c = 1\]$ ואז $plot:\[\left\langle {b,c} \right\rangle ,\left\langle {a,c} \right\rangle \in R\]$ . אם $plot:\[a\]$ אי זוגי, נבחר $plot:\[c = 2\]$ ואז $plot:\[\left\langle {b,c} \right\rangle ,\left\langle {a,c} \right\rangle \in R\]$ .

ומכאן $plot:\[T \subseteq {R^2}\]$ . הראנו הכלה דו כיוונית ולכן מתקיים השוויון.

ב.

ניתן לראות כי מתקיים $plot:\[{R^3} = R\]$ , וכך הלאה, ולכן:

$plot:\[{R^i} = \left\{ {\begin{array}{*{20}{c}} R \hfill & {i{\text{ is odd}}} \hfill \\ {{R^2}} \hfill & {i{\text{ is even}}} \hfill \\ \end{array} } \right.\]$

כלומר $plot:\[{R^*} = R \cup {R^2} = \mathbb{N} \times \mathbb{N}\]$ .

לפרק הקודם4.7.3. סגור א-רפלקסיבי

לפרק הבא4.8. רלצית שקילות

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

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

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

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

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

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

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