תרגול 11 תשעז

המשך יחסי שקילות

הגדרה: תהא A קבוצה. חלוקה של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות $\{A_i\}_{i\in I}$ כך ש:

• $\forall i\in I: A_i \neq \emptyset$
• $\cup _{i\in I} A_i =A$ כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
• הקבוצות $A_i$ הן זרות זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק ($\forall i\not= j\in I : A_i\cap A_j = \phi$)

הגדרה:

יהא R יחס שקילות על A אזי

1. לכל $x\in A$ מוגדרת מחלקת השקילות של x להיות $\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\}$
2. קבוצת המנה מוגדרת $A/R := \{ [x]_R | x\in A\}$

למשל בדוגמא משבוע שעבר על השלמים עם היחס $x~y\iff 3|x-y$, מחלקת השקילות של 0 היא $[0]_R=\{ 0 \pm 3 \pm 6 \dots \}$ וקבוצת המנה היא $\mathbb{Z}/R= \{[0]_R,[1]_R,[2]_R\}$ (כלומר כל השאריות האפשריות בחלוקה ב-3).

משפט: יהא R יחס שקילות על A אזי

1. לכל $x,y\in A$ מתקיים $[x]=[y]$ או $[x]\cap [y] =\phi$ (כלומר מחלקות השקילות זרות)
2. $A=\bigcup_{[x]\in A/R}[x]$ כלומר (איחוד מחלקות השקילות תתן את כל A)

הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A

מסקנה: תהא A קבוצה אזי יש התאמה {$R$ יחס שקילות על A } $\leftrightarrow$ {חלוקות של A}

חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.

שאלה ממבחן

תהי A קבוצה לא ריקה ותהי $\{R_i\}_{i\in I}$ משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי $R=\cap_{i\in I}R_i$ הינו יחס שקילויות על A.

פתרון

רפלקסיביות: מאחר ו $\forall a\in A\forall i\in I : (a,a)\in R_i$ נובע ש $\forall a\in A: (a,a)\in R$.

סימטריות: נניח $(x,y)\in R$ לכן $\forall i\in I:(x,y)\in R_i$ ולכן נובע מסמטריות היחסים ש $\forall i\in I:(y,x)\in R_i$ ולכן $(y,x)\in R$.

טרנזיטיביות: נניח $(x,y),(y,z)\in \mathbb R$ אזי $\forall i\in I:(x,y),(y,z)\in R_i$, וכיון שהוא יחס שקילות אז נובע $\forall i\in I:(x,z)\in R_i$, ולפי הגדרת החיתוך הכללי נקבל $(x,z)\in R$

תרגיל

תהא $B\subseteq A$ קבוצה ותת קבוצה. נגדיר יחס $~subseteq P(A)\times P(A)$ ע"י $C~D\iff C\cup B=D\cup B$. הוכח שזהו יחס שקילות.

פיתרון

רפלקסיביות: כמובן ש-