תרגול 11 תשעז

חזרה לדף מערכי התרגול.

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

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

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

הגדרה:

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

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

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

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

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

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

מסקנה: תהא A קבוצה אזי יש התאמה {[math]\displaystyle{ R }[/math] יחס שקילות על A } [math]\displaystyle{ \leftrightarrow }[/math] {חלוקות של A}

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

תרגיל

תהא [math]\displaystyle{ B\subseteq A }[/math] קבוצה ותת קבוצה. נגדיר יחס [math]\displaystyle{ \sim \subseteq P(A)\times P(A) }[/math] ע"י [math]\displaystyle{ C\sim D\iff C\cap B=D\cap B }[/math]. הוכיחו:

א. זהו יחס שקילות.

ב. לכל [math]\displaystyle{ X\subseteq A }[/math] קיימת [math]\displaystyle{ C\subseteq B }[/math] כך ש [math]\displaystyle{ [X]_R=[C]_R }[/math].

ג. אם [math]\displaystyle{ C,D\subseteq B }[/math] שונות, אז [math]\displaystyle{ [C]\neq [D] }[/math].

פיתרון

א. רפלקסיביות: כמובן ש- [math]\displaystyle{ \forall C\subseteq A:C\cap B=C\cap B }[/math], ולכן [math]\displaystyle{ C\sim C }[/math].

סימטריות: נניח [math]\displaystyle{ C\sim D }[/math] אזי [math]\displaystyle{ C\cap B=D\cap B\iff D\cap B=C\cap B }[/math], ולכן [math]\displaystyle{ D\sim C }[/math].

טרנזיטיביות: נניח [math]\displaystyle{ C\sim D\land D\sim E }[/math] אזי [math]\displaystyle{ C\cap B=D\cap B\land D\cap B=E\cap B }[/math] ומטרנזיטיביות יחס השיוויון נקבל הדרוש.

ב. יהי [math]\displaystyle{ X\subseteq A }[/math] נשים לב שמתקיים [math]\displaystyle{ (X\cap B)\cap B=X\cap B }[/math] ולכן [math]\displaystyle{ [X]_R=[X\cap B]_R }[/math], ובנוסף מתקיים [math]\displaystyle{ X\cap B\subseteq B }[/math] ולכן נוכל לבחור [math]\displaystyle{ C=X\cap B }[/math].

ג. תהיינה [math]\displaystyle{ C,D\subseteq B }[/math] שונות. לכן קיים (בה"כ) [math]\displaystyle{ x\in C\smallsetminus D }[/math] וכמובן [math]\displaystyle{ x\in B }[/math], ולכן נקבל [math]\displaystyle{ x\in C\cap B\land x\notin D\cap B }[/math] כלומר [math]\displaystyle{ C\cap B\neq D\cap B }[/math] ולכן [math]\displaystyle{ [C]\neq [D] }[/math].

שאלה ממבחן

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

ב. נסמן [math]\displaystyle{ R_n=\{(x,y)\in\mathbb{Z}\times\mathbb{Z}:n|(x-y)\} }[/math]. מהם [math]\displaystyle{ R_1,R_2,R=\cap_{n\in\mathbb{N}}R_n }[/math]? מהן קבוצות המנה [math]\displaystyle{ \mathbb{Z}/R,\mathbb{Z}/R_1,\mathbb{Z}/R_2 }[/math]?

פתרון

א. רפלקסיביות: מאחר ו [math]\displaystyle{ \forall a\in A\forall i\in I : (a,a)\in R_i }[/math] נובע ש [math]\displaystyle{ \forall a\in A: (a,a)\in R }[/math].

סימטריות: נניח [math]\displaystyle{ (x,y)\in R }[/math] לכן [math]\displaystyle{ \forall i\in I:(x,y)\in R_i }[/math] ולכן נובע מסמטריות היחסים ש [math]\displaystyle{ \forall i\in I:(y,x)\in R_i }[/math] ולכן [math]\displaystyle{ (y,x)\in R }[/math].

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

ב. [math]\displaystyle{ R_1 }[/math] הינו אוסף כל הזוגות הסדורים מעל השלמים, שכן אחד מחלק כל מספר ולכן כל הפרש.

[math]\displaystyle{ R_2 }[/math] הינו אוסף כל הזוגות בהם שני הצדדים זוגיים או שני הצדדים אי זוגיים, שכן ההפרש בינהם חייב להיות זוגי.

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

[math]\displaystyle{ \mathbb{Z}/R_1 }[/math] הינו אוסף מחלקות השקילות של היחס המכיל את כל הזוגות. יש בו רק מחלקת שקילות אחת המכילה את כל המספרים השלמים.

[math]\displaystyle{ \mathbb{Z}/R_2 }[/math] מכיל שתי קבוצות, קבוצת הזוגיים וקבוצת האי זוגיים שכן בין כל הזוגיים יש את היחס, ובין כל האי זוגיים ולא בין לבין כמובן (הרי זה יחס שקילויות כפי שקל להוכיח).

[math]\displaystyle{ \mathbb{Z}/R }[/math] הינו אוסף כל הקבוצות המכילות איבר שלם בודד.