תרגול 10 תשעז
הגדרות. יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:
- חסם מלעיל של B הוא איבר כך שמתקיים
- חסם מלרע של B הוא איבר כך שמתקיים
- החסם העליון (סופרמום) של B הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן
- החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן
דוגמאות
דוגמא. נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה B. נביט ביחס "מחלק את". הסופרמום של B הוא המכפלה המשותפת המינימלית (lcm), והאינפימום הוא המחלק המשותף המקסימלי(gcd).
למשל
דוגמא עבור אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא
דוגמא.
נביט בקבוצה ונגדיר עליה יחס סדר חלקי:
(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)
נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד . קבוצת חסמי המלעיל של B הינה . המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.
הגדרה. יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים אזי R נקרא יחס סדר מלא.
למשל: היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא. שימו לב כי זו דוגמא ליחס סדר בלי איברים מינימליים או מקסימליים.
יחסי שקילות
הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא
- רפלקסיבי
- סימטרי
- טרנזיטיבי
סימון מקובל:
אם R יחס שקילות מסמנים גם עבור
דוגמא: תהא . נגדיר תת הקבוצות
נגדיר יחס R על A כך
טענה R יחס שקילות
הוכחה:
1. רפלקסיביות - נניח לכן x שייך ל עבור i מסוים (שכן האיחוד שלהן שווה לA) ולכן .
2. סימטריות - נניח אזי עבור i מסוים, מכיוון שאין משמעות לסדר שייכות לקבוצה, נובע שגם .
3. טרנזיטיביות - נניח אזי קיימים i,j כך ש וגם . לכן . מכיוון שהחיתוך בין תתי הקבוצות הוא ריק מוכרח להיות ש ולכן ולכן כפי שרצינו.
הגדרה: תהא A קבוצה. חלוקה של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות
כך ש:
- כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
- הקבוצות הן זרות זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק ()
כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן).
דוגמא נוספת:
נגדיר יחס שקילות R על ע"י
טענה: R אכן יחס שקילות
הוכחה:
1. רפלקסיביות - נניח לכן
2. סימטריות - נניח אזי ולכן גם
3. טרנזיטיביות - נניח אזי ולכן גם
הגדרה:
יהא R יחס שקילות על A אזי
- לכל מוגדרת מחלקת השקילות של x להיות
- קבוצת המנה מוגדרת
למשל, בדוגמא הראשונה הן מחלקות השקילות. קבוצת המנה היא
בדוגמא השניה מחלקת השקילות של 0 היא וקבוצת המנה היא (כלומר כל השאריות האפשריות בחלוקה ב-3).
משפט: יהא R יחס שקילות על A אזי
- לכל מתקיים או (כלומר מחלקות השקילות זרות)
- כלומר (איחוד מחלקות השקילות תתן את כל A)
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
מסקנה:
תהא A קבוצה אזי יש התאמה { יחס שקילות על A }
{חלוקות של A}
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.