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

תורת הקבוצות

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

3.1. הגדרות בסיסיות

יהיו plot:\[A,B\] קבוצות.

תת קבוצה (כלשהי) של plot:\[A \times B\] נקראת רלציה בינארית מ-A ל-B.

תת קבוצה של plot:\[A \times B \times C\] נקראת רלציה טרנרית.

תת קבוצה של plot:\[{A_1} \times {A_2} \times ... \times {A_n}\] נקראת רלציה n-ארית.

דוגמא

תהי plot:\[A\] הקבוצה plot:\[A = \left\{ {1,2,3,4} \right\}\] ותהי plot:\[B\] הקבוצה plot:\[B = \left\{ {a,b,c} \right\}\]. דוגמא לרלציה מ-B ל-A:

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

נציג את הרלציה על ידי גרף (דו צדדי):

במקרה הכללי - יתכנו צמתים שאין מהם חצים יוצאים או אין חצים נכנסים אליהם. כמו כן יתכנו צמתים שיש להם יותר מחץ אחד נכנס או יוצא מהם.



ייצוג על ידי מטריצה בינרית

B/A

1

2

3

4

a

0

0

0

0

b

1

0

0

1

c

1

0

0

0

סימון: אם plot:\[\left\langle {a,b} \right\rangle  \in R\] נסמן plot:\[aRb\]. אם plot:\[\left\langle {a,b} \right\rangle  \notin R\] נסמן .

שאלה

כמה רלציות קיימות מ-A ל-B כאשר A ו-B הינן קבוצות סופיות?

כמספר תתי הקבוצות שלplot:\[A \times B\], שכן כל תת קבוצה שלplot:\[A \times B\] היא רלציה מ-A ל-B. plot:\[\left| {AxB} \right| = \left| A \right| \cdot \left| B \right|\]

מספר תתי הקבוצות הוא plot:\[{2^{\left| A \right| \cdot \left| B \right|}}\].

הגדרות

תחום של רלציה - תחום של רלציה plot:\[R \subseteq A \times B\] היא הקבוצה

domain(R) ={xplot:\[ \in \]A|קיים plot:\[y \in B\]כך שמתקיים xRy}

כלומר תחום של רלציה הינו קבוצת הצמתים שיש מהן חצים יוצאים.

לדוגמא: עבור R המוצג בצורה הבאה:

מתקיים כי domain(R)={a, b}.

טווח של רלציה - טווח של רלציה plot:\[R \subseteq A \times B\] היא הקבוצה

range(R) ={Yplot:\[ \in \]b|קיים plot:\[x \in A\]כך שמתקיים xRy}

טווח של רלציה הינה קבוצת האיברים ב-B שיש אליהם חצים נכנסים.

רלציה הופכית - רלציה הופכית של רלציה plot:\[R \subseteq A \times B\] היא הרלציה מ-B ל-A הבאה:

plot:\[{R^{ - 1}} = \left\{ {\left\langle {b,a} \right\rangle |\left\langle {a,b} \right\rangle  \in R} \right\}\]

כלומר: plot:\[b{R^{ - 1}}A \Leftrightarrow aRb\].

רלציה משלימה - רלציה משלימה לרלציה plot:\[R \subseteq A \times B\] היא הרלציה plot:\[{R^c} = A \times B - R\]

לכל plot:\[\left\langle {a,b} \right\rangle  \in A \times B\] מתקיים: plot:\[a{R^c}b \Leftrightarrow a{\text{\not R}}b\].



תגיות המסמך:

לפרק הקודם3. רלציות
לפרק הבא3.2. הרכב רלציות
מאת: סטודנטית

הוכחות להגדרה 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 אז צריך לתקן את זה.
מאת: אני

כל הכבוד!!!!

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

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

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

המון תודה

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

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

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

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

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