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