תרגול 11 תשעז: הבדלים בין גרסאות בדף
(←פיתרון) |
(←פיתרון) |
||
| שורה 48: | שורה 48: | ||
ב. פיתרון: <math>|P(A)/\sim |=|P(B)|=2^{|B|}</math>. הוכחה: | ב. פיתרון: <math>|P(A)/\sim |=|P(B)|=2^{|B|}</math>. הוכחה: | ||
מחד, לכל מחלקת שקילות <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>B</math> מגדירה מחלקת שקילות שונה, כי אם <math>C\neq D\subseteq B</math> אז <math>C\cap B\neq D\cap B</math>, ולכן <math>[C]\neq [D]</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>. | |||
===שאלה ממבחן=== | ===שאלה ממבחן=== | ||
גרסה מ־18:56, 24 בינואר 2017
המשך יחסי שקילות
הגדרה: תהא A קבוצה. חלוקה של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות [math]\displaystyle{ \{A_i\}_{i\in I} }[/math] כך ש:
- [math]\displaystyle{ \forall i\in I: A_i \neq \emptyset }[/math]
- [math]\displaystyle{ \cup _{i\in I} A_i =A }[/math] כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
- הקבוצות [math]\displaystyle{ A_i }[/math] הן זרות זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק ([math]\displaystyle{ \forall i\not= j\in I : A_i\cap A_j = \phi }[/math])
הגדרה:
יהא R יחס שקילות על A אזי
- לכל [math]\displaystyle{ x\in A }[/math] מוגדרת מחלקת השקילות של x להיות [math]\displaystyle{ \bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} }[/math]
- קבוצת המנה מוגדרת [math]\displaystyle{ A/R := \{ [x]_R | x\in A\} }[/math]
למשל בדוגמא משבוע שעבר על השלמים עם היחס [math]\displaystyle{ x~y\iff 3|x-y }[/math], מחלקת השקילות של 0 היא [math]\displaystyle{ [0]_R=\{ 0 \pm 3 \pm 6 \dots \} }[/math] וקבוצת המנה היא
[math]\displaystyle{ \mathbb{Z}/R= \{[0]_R,[1]_R,[2]_R\} }[/math] (כלומר כל השאריות האפשריות בחלוקה ב-3).
משפט: יהא R יחס שקילות על A אזי
- לכל [math]\displaystyle{ x,y\in A }[/math] מתקיים [math]\displaystyle{ [x]=[y] }[/math] או [math]\displaystyle{ [x]\cap [y] =\phi }[/math] (כלומר מחלקות השקילות זרות)
- [math]\displaystyle{ A=\bigcup_{[x]\in A/R}[x] }[/math] כלומר (איחוד מחלקות השקילות תתן את כל A)
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
מסקנה:
תהא A קבוצה אזי יש התאמה {[math]\displaystyle{ R }[/math] יחס שקילות על A }
[math]\displaystyle{ \leftrightarrow }[/math] {חלוקות של A}
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
תרגיל
תהא [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{ |P(A)/\sim | }[/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{ |P(A)/\sim |=|P(B)|=2^{|B|} }[/math]. הוכחה:
מחד, לכל מחלקת שקילות [math]\displaystyle{ [C]\in P(A)/\sim }[/math] נוכל לבחור תת קבוצה של [math]\displaystyle{ B }[/math] כנציג: כי [math]\displaystyle{ \forall C\in P(A):[C]=\{ D\subseteq A|C\cap B=D\cap B\} }[/math], וכיון ש- [math]\displaystyle{ (C\cap B)\cap B=C\cap B }[/math] נקבל [math]\displaystyle{ [C]=[C\cap B] }[/math], ו-[math]\displaystyle{ C\cap B\subseteq B }[/math] הוא הנציג שחיפשנו.
מצד שני, כל תת קבוצה של [math]\displaystyle{ B }[/math] מגדירה מחלקת שקילות שונה, כי אם [math]\displaystyle{ C\neq D\subseteq B }[/math] אז [math]\displaystyle{ C\cap B\neq D\cap B }[/math], ולכן [math]\displaystyle{ [C]\neq [D] }[/math].
ובסה"כ קיבלנו שכל איבר ב- [math]\displaystyle{ P(A)/\sim }[/math] מוגדר ע"י תת קבוצה של [math]\displaystyle{ B }[/math] ושאין חזרה כי כל שתי תתי קבוצות שונות של [math]\displaystyle{ B }[/math] מגדירות מחלקת שקילות שונה. לכן מספר האיברים בקבוצת המנה הוא כמספר תתי הקבוצות של [math]\displaystyle{ B }[/math].
שאלה ממבחן
תהי A קבוצה לא ריקה ותהי [math]\displaystyle{ \{R_i\}_{i\in I} }[/math] משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי [math]\displaystyle{ R=\cap_{i\in I}R_i }[/math] הינו יחס שקילויות על A.
פתרון
רפלקסיביות: מאחר ו [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]