הבדלים בין גרסאות בדף "תרגול 11 תשעז"
(←שאלה ממבחן) |
(←תרגיל) |
||
שורה 42: | שורה 42: | ||
===תרגיל=== | ===תרגיל=== | ||
− | תהא <math>B\subseteq A</math> קבוצה ותת קבוצה. נגדיר יחס <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>P(A)/\sim</math> | ||
====פיתרון==== | ====פיתרון==== | ||
− | רפלקסיביות: כמובן ש- <math></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>P(A)/\sim =P(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>\forall C\in P(A):[c]=\{ D\subseteq A|C\cap B=D\cap B\}</math>, וכיון ש- <math>C\cap B\subseteq B</math> נקבל <math>[C]=[C\cap B]</math>. |
גרסה מ־10:40, 22 בינואר 2017
תוכן עניינים
המשך יחסי שקילות
הגדרה: תהא A קבוצה. חלוקה של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות כך ש:
- כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
- הקבוצות הן זרות זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק ()
הגדרה:
יהא R יחס שקילות על A אזי
- לכל מוגדרת מחלקת השקילות של x להיות
- קבוצת המנה מוגדרת
למשל בדוגמא משבוע שעבר על השלמים עם היחס , מחלקת השקילות של 0 היא וקבוצת המנה היא
(כלומר כל השאריות האפשריות בחלוקה ב-3).
משפט: יהא R יחס שקילות על A אזי
- לכל מתקיים או (כלומר מחלקות השקילות זרות)
- כלומר (איחוד מחלקות השקילות תתן את כל A)
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
מסקנה:
תהא A קבוצה אזי יש התאמה { יחס שקילות על A }
{חלוקות של A}
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
שאלה ממבחן
תהי A קבוצה לא ריקה ותהי משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי הינו יחס שקילויות על A.
פתרון
רפלקסיביות: מאחר ו נובע ש .
סימטריות: נניח לכן ולכן נובע מסמטריות היחסים ש ולכן .
טרנזיטיביות: נניח אזי , וכיון שהוא יחס שקילות אז נובע , ולפי הגדרת החיתוך הכללי נקבל
תרגיל
תהא קבוצה ותת קבוצה. נגדיר יחס ע"י .
א. הוכח שזהו יחס שקילות.
ב. מצא את
פיתרון
א. רפלקסיביות: כמובן ש- , ולכן .
סימטריות: נניח אזי , ולכן .
טרנזיטיביות: נניח אזי ומטרנזיטיביות יחס השיוויון נקבל הדרוש.
ב. פיתרון: . הוכחה:
מחד כל תת קבוצה של מגדירה מחלקת שקילות שונה, כי אם אז , ולכן .
מצד שני, מכל מחלקת שקילות נוכל לבחור תת קבוצה של כנציג: כי , וכיון ש- נקבל .