הרצאה 6

תזכורת

• קבוצה. נקרא יחס
• יחס שקילות אם רפלקסיבי, סימטרי וטרנזיטיבי
• אם יחס שקילות, אז: לכל מחלקת השקילות של .
• קבוצת המנה.

חלוקה

הגדרה

חלוקה של קבוצה היא אוסף של קבוצות לא ריקות, כך שלכל מתקיים:

• האוסף זר בזוגות ומכסה את (כלומר לכל )

דוגמה

משפט

תהי קבוצה ויהי יחס שקילות על , אזי היא חלוקה של .

הוכחה

צריך להראות שאין קבוצה ריקה באוסף, שכל איבר באוסף מוכל ב, שהאוסף זר בזוגות ושהאוסף מכסה את .

1. אין קבוצה ריקה באוסף: יהי . רפלקסיבי, לכן ולכן וזה גורר ש
2. כל איבר באוסף מוכל ב: יהי . לפי הגדרה מכיוון שהבסיס של הקבוצה היא איברים הלקוחים מ, הקבוצה מוכלת ב.
   הוכחה חלופית: יהי , אז לפי הגדרת מחלקת שקילות , אולם
3. האוסף זר בזוגות: יהיו . נראה כי ב.
   א. נראה את הנוגד הלוגי: אם אז ואכן. נניח ש, נראה הכלה דו כיוונית (ונגיע לסתירה):
   : יהי לכן , בנוסף ולכן מסימטריות ומטרנזיטיביות גם כלומר , אותו דבר תקף גם ל
   ב. לפי (א) . נניח בשלילה כי ולכן קיים . מזה נובע כי . בנוסף . מסימטריות גם ומטרנזיטיביות גם . סתירה. לכן
4. האוסף מכסה את : צ”ל כי ואכן, יהי אז:

הגדרה

תהא קבוצה , ותהי חלוקה של . היחס המושרה ע”י החלוקה הוא היחס שמוגדר ע”י אם ו שייכים לאותה קבוצה בחלוקה

דוגמאות

א. , חלוקה לזוגיים ואי זוגיים. היחס המושרה הוא

ב. . חלוקה ליחידונים, היחס המושרה (יחס הזהות):

ג. עבור ניקח את החלוקה שמכילה קבוצה 1, שהיא כל . היחס המושרה (היחס המלא)

תרגיל

עבור כל אחת מהדוגמאות:
א. מצאו חתך
ב. מצאו את מחלקות השקילות
ג. מצאו את קבוצת המנה

משפט

אם חלוקה כלשהי של קבוצה . אז היחס המושרה ע”י הוא יחס שקילות.

הוכחה

תהי קבוצה ותהי חלוקה של . נסמן ב את היחס המושרה
נשים לב: לכל , ולכן קיים . בנוסף לכן , ואם . ולכל , אם ורק אם (נובע מהגדרת יחס מושרה).
נוכיח ש יחס שקילות.
רפלקסיבי: יהי . חלוקה של , לכן קיים כך ש , ולכן גם וזה גורר
סימטרי: יהיו כך ש . מהגדרת יחס מושרה קיימת כך ש, ומכך נובע ש ולכן
טרנזיטיבי: יהיו כך ש .

בפרט קיבלנו ש

עוד קצת יחסי שקילות

, סימנו וגדרנו יחס שקילות

נרצה להבין מה היחס מייצג

כל מגדיר הפרש למעשה ניתן להגדיר: