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