הועלה לאתר:  
מספר עמודים: 95
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת הקבוצות

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

3.2. הרכב רלציות

כזכור, רלציה מ-A ל-B היא תת קבוצה של plot:\[A \times B\]. בהינתן רלציה R מ-A ל-B (plot:\[R \subseteq A \times B\]) ורלציה S מ-B ל-C (plot:\[S \subseteq B \times C\]) ההרכב של R עם S, המסומן על ידי plot:\[R \circ S\], היא הרלציה:

plot:\[R \circ S = \left\{ {\left\langle {x,z} \right\rangle |\left\langle {x,y} \right\rangle  \in R,\left\langle {y,z} \right\rangle  \in S,\forall y \in B} \right\}\]

דוגמא

A={1,2,3,4}

B={a,b,c}

C={T,F}

plot:\[A \to B\]

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

plot:\[B \to C\]

plot:\[{\text{S = }}\left\{ {\left\langle {{\text{a,T}}} \right\rangle {\text{,}}\left\langle {{\text{b,T}}} \right\rangle {\text{,}}\left\langle {{\text{c,T}}} \right\rangle {\text{,}}\left\langle {{\text{c,F}}} \right\rangle } \right\}\]

plot:\[R \circ S = \left\{ {\left\langle {1,T} \right\rangle ,\left\langle {3,T} \right\rangle ,\left\langle {3,F} \right\rangle } \right\}\]

זוג נמצא ב-plot:\[R \circ S\] אם קיים מסלול באורך 2 בין איבריו.



תכונות של פעולת ההרכב

1. אסוציאטיביות: לכל plot:\[{R_1},{R_2},{R_3}\] המקיימות plot:\[{R_1} \subseteq A \times B,\,\,{R_2} \subseteq B \times C,\,\,{R_3} \subseteq C \times D\] מתקיים כי:

plot:\[({R_1} \circ {R_2}) \circ {R_3} = {R_1} \circ ({R_2} \circ {R_3})\]

2. לכל שתי רלציות, plot:\[{R_1} \subseteq A \times B,\,\,{R_2} \subseteq BxC\], מתקיים: plot:\[{({R_1} \circ {R_2})^{ - 1}} = {R_2}^{ - 1} \circ {R_1}^{ - 1}\]

הוכחה:

plot:\[\left\langle {x,z} \right\rangle  \in {\left( {{R_1} \circ {R_2}} \right)^{ - 1}} \Leftrightarrow \]הגדרת רלציה הופכית

plot:\[\left\langle {z,x} \right\rangle  \in {R_1} \circ {R_2} \Leftrightarrow \]הגדרת הרכב

plot:\[\exists y \in B,\left\langle {z,y} \right\rangle  \in {R_1},\left\langle {y,x} \right\rangle  \in {R_2} \Leftrightarrow \exists y \in B,\left\langle {y,z} \right\rangle  \in {R_1}^{ - 1},\left\langle {x,y} \right\rangle  \in {R_2}^{ - 1}\]

ומכאןplot:\[\left\langle {x,z} \right\rangle  \in {R_2}^{ - 1} \circ {R_1}^{ - 1}\]

תגיות המסמך:

לפרק הקודם3.1. הגדרות בסיסיות
לפרק הבא3.3. תכונות של יחסים
מאת: סטודנטית

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

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

תודה רבה!

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

תודה

מברוק! תודה
מאת: ברק

יש לכם טעות

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

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

מבלבל

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

מבלבל

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

קבוצה סופית

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

תודה רבה

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

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

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

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

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

כל הכבוד!!!!

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

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

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

המון תודה

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

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

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

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

והלוואי ויהיו רבים כמוך...
שיתוף:
| עוד