תורת הקבוצות

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

4.6. חזקות של רלציה

תהיי רלציה R מעל קבוצה A, נסמן ב- $plot:\[{R^2}\]$ את $plot:\[R \circ R\]$ .

הזוג $plot:\[\left\langle {x,z} \right\rangle \]$ שייך ל- $plot:\[{R^2}\]$ אם קיים y כך ש $plot:\[\left\langle {x,y} \right\rangle \in R,\left\langle {y,z} \right\rangle \in R\]$ . כלומר אם קיימת קשת מ-x ל-y כלשהו, ומאותו y אל z. במילים אחרות - אם קיימת מסלול באורך 2 בין x ל-z.

באופן דומה, מסמנים ב $plot:\[{R^i}\]$ את ההרכב הבא: $plot:\[R \circ R \circ ... \circ R\]$ . (i פעמים).

בגלל תכונת האסוציאטיביות של ההרכב נקבל את המסקנה: $plot:\[{R^i} \circ {R^j} = {R^{i + j}}\]$ .

איבר $plot:\[\left\langle {x,z} \right\rangle \]$ נמצא בגרף של $plot:\[{R^i}\]$ אם קיים מסלול באורך i שבין x ל-z בגרף של R.

טענה

R טרנזיטיבית אמ"מ $plot:\[{R^2} \subseteq R\]$ .

הוכחה:

$plot:\[R\]$ טרנזיטיבית $plot:\[ \Leftrightarrow \]$ לכל $plot:\[x,y,z \in A\]$ מתקיים כי $plot:\[\left\langle {x,z} \right\rangle \in R \Leftarrow \left\langle {x,y} \right\rangle \in R,\left\langle {y,z} \right\rangle \in R\]$ .

$plot:\[ \Leftrightarrow \]$ לכל $plot:\[\left\langle {x,z} \right\rangle \in A\]$ מתקיים כי $plot:\[{R^2} \subseteq R \Leftrightarrow \left\langle {x,z} \right\rangle \in R \Leftarrow \left\langle {x,z} \right\rangle \in {R^2}\]$

טענה (ללא הוכחה)

לכל 3 רלציות $plot:\[{s_1},{s_2},{s_3}\]$ מתקיים $plot:\[{S_1} \subseteq {S_2} \Rightarrow {S_1} \circ {S_3} \subseteq {S_2} \circ {S_3}\]$ .

טענה

תהיינה הרלציות $plot:\[f \subseteq A \times B,g \subseteq B \times C\]$ .

פעולת ההרכבה מוגדרת כרגיל: $plot:\[\left\langle {a,c} \right\rangle \in f \circ g\]$ אמ"מ קיים $plot:\[b \in B\]$ כך ש- $plot:\[\left\langle {a,b} \right\rangle \in f,\left\langle {b,c} \right\rangle \in g\]$ .

ניתן לראות כי $plot:\[f \circ g \subseteq A \times C\]$ . נטען: אם $plot:\[f,g\]$ הינן פונקציות אזי ההרכב $plot:\[f \circ g\]$ הינו פונקציה.

הוכחה:

על מנת להראות שרלציה היא פונקציה עלינו להראות:

קיום – לכל $plot:\[a \in A\]$ קים $plot:\[c \in C\]$ כך ש- $plot:\[\left\langle {a,c} \right\rangle \in f \circ g\]$ .
יחידות – אם $plot:\[\left\langle {a,{x_1}} \right\rangle \in f \circ g,\left\langle {a,{x_2}} \right\rangle \in f \circ g\]$ אזי בהכרח $plot:\[{x_1} = {x_2}\]$ .

יהי $plot:\[a \in A\]$ .

$plot:\[f\]$ היא פונקציה $plot:\[ \Leftarrow \]$ קיים $plot:\[b \in B\]$ כך ש- $plot:\[\left\langle {a,b} \right\rangle \in f\]$ .

$plot:\[g\]$ היא פונקציה $plot:\[ \Leftarrow \]$ קיים $plot:\[c \in C\]$ כך ש- $plot:\[\left\langle {b,c} \right\rangle \in g\]$ .

$plot:\[ \Leftarrow \]$ על פי הגדרת ההרכב מתקיים $plot:\[\left\langle {a,c} \right\rangle \in f \circ g\]$ .

$plot:\[ \Leftarrow \]$ לכל $plot:\[a \in A\]$ קיים $plot:\[c \in C\]$ כך ש- $plot:\[\left\langle {a,c} \right\rangle \in f \circ g\]$ .

יהיו $plot:\[{x_1},{x_2}\]$ כך ש- $plot:\[\left\langle {a,{x_1}} \right\rangle \in f \circ g,\left\langle {a,{x_2}} \right\rangle \in f \circ g\]$ .

$plot:\[f\]$ היא פונקציה ולכן:

קיים $plot:\[{b_1}\]$ כך ש- $plot:\[\left\langle {a,{b_1}} \right\rangle \in f\]$ וגם $plot:\[\left\langle {{b_1},{x_1}} \right\rangle \in g\]$ .
קיים $plot:\[{b_2}\]$ כך ש- $plot:\[\left\langle {a,{b_2}} \right\rangle \in f\]$ וגם $plot:\[\left\langle {{b_2},{x_2}} \right\rangle \in g\]$ .

$plot:\[f\]$ היא פונקציה ולכן $plot:\[{b_1} = {b_2}\]$ (יחידות עבור $plot:\[f\]$ ).

$plot:\[g\]$ היא פונקציה ולכן מכיוון ש- $plot:\[\left\langle {b,{x_2}} \right\rangle \in g,\left\langle {b,{x_1}} \right\rangle \in g\]$ נקבל $plot:\[{x_1} = {x_2}\]$ .

תרגיל

תהי $plot:\[f:{\mathbb{R}^2} \to {\mathbb{R}^2}\]$ המוגדרת כך: $plot:\[f\left( {x,y} \right) = \left\langle {x + y,x - y} \right\rangle \]$ .

יש לענות האם $plot:\[f\]$ היא על והאם היא חח"ע.

פתרון

יהי $plot:\[\left\langle {a,b} \right\rangle \in {\mathbb{R}^2}\]$ .

אם $plot:\[\left\langle {x,y} \right\rangle \to \left\langle {a,b} \right\rangle \]$ אזי נוכל לכתוב: $plot:\[a = x + y,b = x - y\]$ .

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

$plot:\[\left\langle {x,y} \right\rangle = \left\langle {\frac{{a + b}}{2},\frac{{a - b}}{2}} \right\rangle \in {\mathbb{R}^2}\]$

מכיוון שניתן להגיע לכל $plot:\[a,b\]$ כרצוננו בתחום $plot:\[{\mathbb{R}^2}\]$ הרי שהפונקציה הינה על.

מכיוון שפתרון מערכת המשוואות הינו יחיד הפונקציה הינה חד חד ערכית.

תרגיל

נתונות פונקציות $plot:\[f:X \to Y,g:Y \to Z\]$ .

צ"ל: אם $plot:\[f \circ g\]$ על וגם $plot:\[g\]$ הינה חח"ע אזי $plot:\[f\]$ היא על.

הוכחה:

כדי להוכיח כי $plot:\[f\]$ היא על עלינו להראות כי לכל איבר $plot:\[y \in Y\]$ קיים $plot:\[x \in X\]$ כך שמתקיים $plot:\[f(x) = y\]$ .

יהי $plot:\[y \in Y\]$ .

$plot:\[g\]$ היא פונקציה ולכן קיים $plot:\[z \in Z\]$ כך ש- $plot:\[g(y) = z\]$ .

$plot:\[f \circ g\]$ על ולכן קיים $plot:\[x \in X\]$ כך שמתקיים $plot:\[g \circ f(x) = z\]$ (כלומר $plot:\[g\left( {f(x)} \right) = z\]$ ).

כלומר בינתיים הגענו לכך ש: $plot:\[g\left( y \right) = z,g\left( {f(x)} \right) = z\]$ .

$plot:\[g\]$ הינה חח"ע ולכן $plot:\[y = f(x)\]$ . הראנו בעצם כי קיים איבר $plot:\[y \in Y\]$ כך ש- $plot:\[f(x) = y\]$ ובכך סיימנו.

טענה

R טרנזיטיבית אמ"מ לכל i $plot:\[ \leqslant \]$ 1, $plot:\[{R^i} \subseteq {R^{i - 1}} \subseteq {R^{i - 2}} \subseteq ... \subseteq {R^2} \subseteq R\]$ .

הוכחה: (באינדוקציה על i)

בסיס: $plot:\[i = 2\]$ ראינו בטענה הקודמת ( $plot:\[{R^2} \subseteq R\]$ ).

נניח את נכונות הטענה לכל $plot:\[i \leqslant n\]$ ונוכיח עבור $plot:\[i = n + 1\]$ .

על פי ההנחה מתקיים כי $plot:\[{R^n} \subseteq {R^{n - 1}} \subseteq {R^{n - 2}} \subseteq ... \subseteq {R^2} \subseteq R\]$ .

יש להוסיף: $plot:\[{R^{n + 1}} \subseteq {R^n}\]$ .

על פי ההנחה $plot:\[{R^n} \subseteq {R^{n - 1}}\]$ ולכן על פי טענה העזר $plot:\[{R^n} \circ R \subseteq {R^{n - 1}} \circ R\]$ , כלומר $plot:\[{R^{n + 1}} \subseteq {R^n}\]$ .

לפרק הקודם4.5.3. דוגמאות

לפרק הבא4.7. הסגור של רלציה ביחס לתכונה

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

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

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

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

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

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

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