תרגול 11 תשעז: הבדלים בין גרסאות בדף

גרסה אחרונה מ־15:56, 29 בדצמבר 2017

יחסי שקילות - תרגילים נוספים

תרגיל

תהא [math]\displaystyle{ B\subseteq A }[/math] קבוצה ותת קבוצה. נגדיר יחס [math]\displaystyle{ \sim \subseteq P(A)\times P(A) }[/math] ע"י [math]\displaystyle{ C\sim D\iff C\cap B=D\cap B }[/math]. הוכיחו:

א. זהו יחס שקילות.

ב. לכל [math]\displaystyle{ X\subseteq A }[/math] קיימת [math]\displaystyle{ C\subseteq B }[/math] כך ש [math]\displaystyle{ [X]_R=[C]_R }[/math].

ג. אם [math]\displaystyle{ C,D\subseteq B }[/math] שונות, אז [math]\displaystyle{ [C]\neq [D] }[/math].

פיתרון

א. רפלקסיביות: כמובן ש- [math]\displaystyle{ \forall C\subseteq A:C\cap B=C\cap B }[/math], ולכן [math]\displaystyle{ C\sim C }[/math].

סימטריות: נניח [math]\displaystyle{ C\sim D }[/math] אזי [math]\displaystyle{ C\cap B=D\cap B\iff D\cap B=C\cap B }[/math], ולכן [math]\displaystyle{ D\sim C }[/math].

טרנזיטיביות: נניח [math]\displaystyle{ C\sim D\land D\sim E }[/math] אזי [math]\displaystyle{ C\cap B=D\cap B\land D\cap B=E\cap B }[/math] ומטרנזיטיביות יחס השיוויון נקבל הדרוש.

ב. יהי [math]\displaystyle{ X\subseteq A }[/math] נשים לב שמתקיים [math]\displaystyle{ (X\cap B)\cap B=X\cap B }[/math] ולכן [math]\displaystyle{ [X]_R=[X\cap B]_R }[/math], ובנוסף מתקיים [math]\displaystyle{ X\cap B\subseteq B }[/math] ולכן נוכל לבחור [math]\displaystyle{ C=X\cap B }[/math].

ג. תהיינה [math]\displaystyle{ C,D\subseteq B }[/math] שונות. לכן קיים (בה"כ) [math]\displaystyle{ x\in C\smallsetminus D }[/math] וכמובן [math]\displaystyle{ x\in B }[/math], ולכן נקבל [math]\displaystyle{ x\in C\cap B\land x\notin D\cap B }[/math] כלומר [math]\displaystyle{ C\cap B\neq D\cap B }[/math] ולכן [math]\displaystyle{ [C]\neq [D] }[/math].

שאלה ממבחן

א. תהי [math]\displaystyle{ A }[/math] קבוצה לא ריקה ותהי [math]\displaystyle{ \{R_i\}_{i\in I} }[/math] משפחה של יחסי שקילות על [math]\displaystyle{ A }[/math]. הוכיחו כי החיתוך הכללי [math]\displaystyle{ R=\cap_{i\in I}R_i }[/math] הינו יחס שקילויות על [math]\displaystyle{ A }[/math].

ב. נסמן [math]\displaystyle{ R_n=\{(x,y)\in\mathbb{Z}\times\mathbb{Z}:n|(x-y)\} }[/math]. מהם [math]\displaystyle{ R_1,R_2,R=\cap_{n\in\mathbb{N}}R_n }[/math]? מהן קבוצות המנה [math]\displaystyle{ \mathbb{Z}/R,\mathbb{Z}/R_1,\mathbb{Z}/R_2 }[/math]?

פתרון

א. רפלקסיביות: מאחר ו-[math]\displaystyle{ \forall a\in A\forall i\in I : (a,a)\in R_i }[/math] נובע ש-[math]\displaystyle{ \forall a\in A: (a,a)\in R }[/math].

סימטריות: נניח [math]\displaystyle{ (x,y)\in R }[/math] לכן [math]\displaystyle{ \forall i\in I:(x,y)\in R_i }[/math] ולכן נובע מסמטריות היחסים ש [math]\displaystyle{ \forall i\in I:(y,x)\in R_i }[/math] ולכן [math]\displaystyle{ (y,x)\in R }[/math].

טרנזיטיביות: נניח [math]\displaystyle{ (x,y),(y,z)\in \mathbb R }[/math] אזי [math]\displaystyle{ \forall i\in I:(x,y),(y,z)\in R_i }[/math], וכיון שהוא יחס שקילות אז נובע [math]\displaystyle{ \forall i\in I:(x,z)\in R_i }[/math], ולפי הגדרת החיתוך הכללי נקבל [math]\displaystyle{ (x,z)\in R }[/math]

ב. [math]\displaystyle{ R_1 }[/math] הינו אוסף כל הזוגות הסדורים מעל השלמים, שכן אחד מחלק כל מספר ולכן כל הפרש.

[math]\displaystyle{ R_2 }[/math] הינו אוסף כל הזוגות בהם שני הצדדים זוגיים או שני הצדדים אי זוגיים, שכן ההפרש בינהם חייב להיות זוגי.

[math]\displaystyle{ R }[/math] הינו אוסף הזוגות שההפרש בינהם מתחלק בכל המספרים הטבעיים. רק הפרש אפס יכול להתחלק בכל מספר, ולכן [math]\displaystyle{ R }[/math] הינו אוסף הזוגות מהצורה [math]\displaystyle{ (q,q) }[/math] עבור [math]\displaystyle{ q }[/math] מספר שלם. (יחס השיוויון).

[math]\displaystyle{ \mathbb{Z}/R_1 }[/math] הינו אוסף מחלקות השקילות של היחס המכיל את כל הזוגות. יש בו רק מחלקת שקילות אחת המכילה את כל המספרים השלמים.

[math]\displaystyle{ \mathbb{Z}/R_2 }[/math] מכיל שתי קבוצות, קבוצת הזוגיים וקבוצת האי זוגיים שכן בין כל הזוגיים יש את היחס, ובין כל האי זוגיים ולא בין לבין כמובן (הרי זה יחס שקילויות כפי שקל להוכיח).

[math]\displaystyle{ \mathbb{Z}/R }[/math] הינו אוסף כל הקבוצות המכילות איבר שלם בודד.

@@ שורה 1: / שורה 1: @@
-==המשך יחסי שקילות==
+חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
-הגדרה: תהא A קבוצה. '''חלוקה''' של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות <math>\{A_i\}_{i\in I}</math>
+==יחסי שקילות - תרגילים נוספים==
-כך ש:
-* <math>\forall i\in I: A_i \neq \emptyset </math>
-* <math>\cup _{i\in I} A_i =A </math> כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
-* הקבוצות <math>A_i</math> הן '''זרות''' זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק (<math>\forall i\not= j\in I : A_i\cap A_j = \phi </math>)
-הגדרה:
+===תרגיל===
+תהא <math>B\subseteq A</math> קבוצה ותת קבוצה. נגדיר יחס <math>\sim \subseteq P(A)\times P(A)</math> ע"י <math>C\sim D\iff C\cap B=D\cap B</math>. הוכיחו:
-יהא R יחס שקילות על A  אזי
+א. זהו יחס שקילות.
-# לכל <math>x\in A</math> מוגדרת '''מחלקת השקילות של x ''' להיות  <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} </math>
+ב. לכל <math>X\subseteq A</math> קיימת <math>C\subseteq B</math> כך ש <math>[X]_R=[C]_R</math>.
-# ''' קבוצת המנה ''' מוגדרת <math>A/R := \{ [x]_R | x\in A\} </math>
+ג. אם <math>C,D\subseteq B</math> שונות, אז <math>[C]\neq [D]</math>.
-למשל בדוגמא משבוע שעבר על השלמים עם היחס <math>x~y\iff 3|x-y</math>, מחלקת השקילות של 0 היא <math>[0]_R=\{ 0 \pm 3 \pm 6 \dots \}</math> וקבוצת המנה היא
+====פיתרון====
-<math>\mathbb{Z}/R= \{[0]_R,[1]_R,[2]_R\}</math> (כלומר כל השאריות האפשריות בחלוקה ב-3).
+א. רפלקסיביות: כמובן ש- <math>\forall C\subseteq A:C\cap B=C\cap B</math>, ולכן <math>C\sim C</math>.
+סימטריות: נניח <math>C\sim D</math> אזי <math>C\cap B=D\cap B\iff D\cap B=C\cap B</math>, ולכן <math>D\sim C</math>.
-משפט: יהא R יחס שקילות על A אזי
+טרנזיטיביות: נניח <math>C\sim D\land D\sim E</math> אזי <math>C\cap B=D\cap B\land D\cap B=E\cap B</math> ומטרנזיטיביות יחס השיוויון נקבל הדרוש.
-# לכל <math>x,y\in A</math> מתקיים <math>[x]=[y]</math> או <math>[x]\cap [y] =\phi </math> (כלומר מחלקות השקילות זרות)
-# <math>A=\bigcup_{[x]\in A/R}[x]</math> כלומר (איחוד מחלקות השקילות תתן את כל A)
-הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
+ב. יהי <math>X\subseteq A</math> נשים לב שמתקיים <math>(X\cap B)\cap B=X\cap B</math> ולכן <math>[X]_R=[X\cap B]_R</math>, ובנוסף מתקיים <math>X\cap B\subseteq B</math> ולכן נוכל לבחור <math>C=X\cap B</math>.
-מסקנה:
+ג. תהיינה <math>C,D\subseteq B</math> שונות. לכן קיים (בה"כ) <math>x\in C\smallsetminus D</math> וכמובן <math>x\in B</math>, ולכן נקבל <math>x\in C\cap B\land x\notin D\cap B</math> כלומר <math>C\cap B\neq D\cap B</math> ולכן <math>[C]\neq [D]</math>.
-תהא A קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על A }
-<math>\leftrightarrow</math> {חלוקות של A}
-חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
+===שאלה ממבחן===
+א. תהי <math>A</math> קבוצה לא ריקה ותהי <math>\{R_i\}_{i\in I}</math> משפחה של יחסי שקילות על <math>A</math>. הוכיחו כי החיתוך הכללי <math>R=\cap_{i\in I}R_i</math> הינו יחס שקילויות על <math>A</math>.
+ב. נסמן <math>R_n=\{(x,y)\in\mathbb{Z}\times\mathbb{Z}:n|(x-y)\}</math>. מהם <math>R_1,R_2,R=\cap_{n\in\mathbb{N}}R_n</math>? מהן קבוצות המנה <math>\mathbb{Z}/R,\mathbb{Z}/R_1,\mathbb{Z}/R_2</math>?
-===תרגיל===
+====פתרון====
-תהא <math>B\subseteq A</math> קבוצה ותת קבוצה. נגדיר יחס <math>\sim \subseteq P(A)\times P(A)</math> ע"י <math>C\sim D\iff C\cap B=D\cap B</math>.
+א. רפלקסיביות: מאחר ו-<math>\forall a\in A\forall i\in I : (a,a)\in R_i</math> נובע ש-<math>\forall a\in A: (a,a)\in R</math>.
-א. הוכח שזהו יחס שקילות.
+סימטריות: נניח <math>(x,y)\in R</math> לכן <math>\forall i\in I:(x,y)\in R_i</math> ולכן נובע מסמטריות היחסים ש <math>\forall i\in I:(y,x)\in R_i</math> ולכן <math>(y,x)\in R</math>.
-ב. מצא את <math>|P(A)/\sim |</math>
+טרנזיטיביות: נניח <math>(x,y),(y,z)\in \mathbb R</math> אזי <math>\forall i\in I:(x,y),(y,z)\in R_i</math>, וכיון שהוא יחס שקילות אז נובע <math>\forall i\in I:(x,z)\in R_i</math>, ולפי הגדרת החיתוך הכללי נקבל <math>(x,z)\in R</math>
-====פיתרון====
-א. רפלקסיביות: כמובן ש- <math>\forall C\subseteq A:C\cap B=C\cap B</math>, ולכן <math>C\sim C</math>.
-סימטריות: נניח <math>C\sim D</math> אזי <math>C\cap B=D\cap B\iff D\cap B=C\cap B</math>, ולכן <math>D\sim C</math>.
-טרנזיטיביות: נניח <math>C\sim D\land D\sim E</math> אזי <math>C\cap B=D\cap B\land D\cap B=E\cap B</math> ומטרנזיטיביות יחס השיוויון נקבל הדרוש.
+ב. <math>R_1</math> הינו אוסף כל הזוגות הסדורים מעל השלמים, שכן אחד מחלק כל מספר ולכן כל הפרש.
-ב. פיתרון: <math>|P(A)/\sim |=|P(B)|=2^{|B|}</math>. הוכחה:
+<math>R_2</math> הינו אוסף כל הזוגות בהם שני הצדדים זוגיים או שני הצדדים אי זוגיים, שכן ההפרש בינהם חייב להיות זוגי.
-מחד, לכל מחלקת שקילות <math>[C]\in P(A)/\sim</math> נוכל לבחור תת קבוצה של <math>B</math> כנציג: כי <math>\forall C\in P(A):[C]=\{ D\subseteq A|C\cap B=D\cap B\}</math>, וכיון ש- <math>(C\cap B)\cap B=C\cap B</math> נקבל <math>[C]=[C\cap B]</math>, ו-<math>C\cap B\subseteq B</math> הוא הנציג שחיפשנו.
+<math>R</math> הינו אוסף הזוגות שההפרש בינהם מתחלק בכל המספרים הטבעיים. רק הפרש אפס יכול להתחלק בכל מספר, ולכן <math>R</math> הינו אוסף הזוגות מהצורה <math>(q,q)</math> עבור <math>q</math> מספר שלם. (יחס השיוויון).
-מצד שני, כל תת קבוצה של <math>B</math> מגדירה מחלקת שקילות שונה, כי אם <math>C\neq D\subseteq B</math> אז <math>C\cap B\neq D\cap B</math>, ולכן <math>[C]\neq [D]</math>.
-ובסה"כ קיבלנו שכל איבר ב- <math>P(A)/\sim</math> מוגדר ע"י תת קבוצה של <math>B</math> ושאין חזרה כי כל שתי תתי קבוצות שונות של <math>B</math> מגדירות מחלקת שקילות שונה. לכן מספר האיברים בקבוצת המנה הוא כמספר תתי הקבוצות של <math>B</math>.
+<math>\mathbb{Z}/R_1</math> הינו אוסף מחלקות השקילות של היחס המכיל את כל הזוגות. יש בו רק מחלקת שקילות אחת המכילה את כל המספרים השלמים.
-===שאלה ממבחן===
+<math>\mathbb{Z}/R_2</math> מכיל שתי קבוצות, קבוצת הזוגיים וקבוצת האי זוגיים שכן בין כל הזוגיים יש את היחס, ובין כל האי זוגיים ולא בין לבין כמובן (הרי זה יחס שקילויות כפי שקל להוכיח).
-תהי A קבוצה לא ריקה ותהי <math>\{R_i\}_{i\in I}</math> משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי  <math>R=\cap_{i\in I}R_i</math> הינו יחס שקילויות על A.
-====פתרון====
+<math>\mathbb{Z}/R</math> הינו אוסף כל הקבוצות המכילות איבר שלם בודד.
-רפלקסיביות: מאחר ו <math>\forall a\in A\forall i\in I : (a,a)\in R_i</math> נובע ש <math>\forall a\in A: (a,a)\in R</math>.
-סימטריות: נניח <math>(x,y)\in R</math> לכן <math>\forall i\in I:(x,y)\in R_i</math> ולכן נובע מסמטריות היחסים ש <math>\forall i\in I:(y,x)\in R_i</math> ולכן <math>(y,x)\in R</math>.
-טרנזיטיביות: נניח <math>(x,y),(y,z)\in \mathbb R</math> אזי <math>\forall i\in I:(x,y),(y,z)\in R_i</math>, וכיון שהוא יחס שקילות אז נובע <math>\forall i\in I:(x,z)\in R_i</math>, ולפי הגדרת החיתוך הכללי נקבל <math>(x,z)\in R</math>