תרגול 11 תשעז
תוכן עניינים
המשך יחסי שקילות
הגדרה: תהא A קבוצה. חלוקה של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות כך ש:
- כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
- הקבוצות הן זרות זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק ()
הגדרה:
יהא R יחס שקילות על A אזי
- לכל מוגדרת מחלקת השקילות של x להיות
- קבוצת המנה מוגדרת
למשל בדוגמא משבוע שעבר על השלמים עם היחס , מחלקת השקילות של 0 היא וקבוצת המנה היא
(כלומר כל השאריות האפשריות בחלוקה ב-3).
משפט: יהא R יחס שקילות על A אזי
- לכל מתקיים או (כלומר מחלקות השקילות זרות)
- כלומר (איחוד מחלקות השקילות תתן את כל A)
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
מסקנה:
תהא A קבוצה אזי יש התאמה { יחס שקילות על A }
{חלוקות של A}
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
שאלה ממבחן
תהי A קבוצה לא ריקה ותהי משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי הינו יחס שקילויות על A.
פתרון
רפלקסיביות: מאחר ו נובע ש .
סימטריות: נניח לכן ולכן נובע מסמטריות היחסים ש ולכן .
טרנזיטיביות: נניח אזי , וכיון שהוא יחס שקילות אז נובע , ולפי הגדרת החיתוך הכללי נקבל
תרגיל
תהא קבוצה ותת קבוצה. נגדיר יחס ע"י .
א. הוכח שזהו יחס שקילות.
ב. מצא את
פיתרון
א. רפלקסיביות: כמובן ש- , ולכן .
סימטריות: נניח אזי , ולכן .
טרנזיטיביות: נניח אזי ומטרנזיטיביות יחס השיוויון נקבל הדרוש.
ב. פיתרון: . הוכחה:
מחד כל תת קבוצה של מגדירה מחלקת שקילות שונה, כי אם אז , ולכן .
מצד שני, מכל מחלקת שקילות נוכל לבחור תת קבוצה של כנציג: כי , וכיון ש- נקבל .