תרגול 10 תשעז

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

יחסי שקילות

הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא

1. רפלקסיבי
2. סימטרי
3. טרנזיטיבי

סימון מקובל:

אם R יחס שקילות מסמנים גם [math]\displaystyle{ x \sim y }[/math] עבור [math]\displaystyle{ (x,y)\in R }[/math]

וכן נסמן [math]\displaystyle{ (A,\sim) }[/math] את הקבוצה עם יחס השקילות

תרגיל

על [math]\displaystyle{ \mathbb{R} }[/math] נגדיר שני יחסים [math]\displaystyle{ S,T }[/math] באופן הבא: לכל [math]\displaystyle{ x,y\in \mathbb{R} }[/math]:

[math]\displaystyle{ xSy\iff x-y=17 }[/math].

[math]\displaystyle{ xTy\iff \exists a\in \mathbb{Z}:x-y=a }[/math].

האם [math]\displaystyle{ S }[/math] יחס שקילות? האם [math]\displaystyle{ T }[/math] יחס שקילות?

פתרון

[math]\displaystyle{ S }[/math] לא כיון שלא רפלקסיבי, שהרי לכל [math]\displaystyle{ x\in \mathbb{R} }[/math] (ובפרט קיים לפחות אחד) [math]\displaystyle{ x-x=0\neq 17 }[/math].

[math]\displaystyle{ T }[/math] כן:

רפלקסיביות: יהי [math]\displaystyle{ x\in \mathbb{R} }[/math], ניקח [math]\displaystyle{ a=0 }[/math] ואז [math]\displaystyle{ x-x=0=a }[/math].

סימטריות: [math]\displaystyle{ xTy\Rightarrow \exists a\in \mathbb{Z} :x-y=a \Rightarrow y-x=-a\in \mathbb{Z} \Rightarrow yTx }[/math].

טרנזיטיביות: [math]\displaystyle{ xTy\land yTz\Rightarrow \exists a\in \mathbb{Z}: x-y=a \land \exists b\in \mathbb{Z}: y-z=b \Rightarrow x-z=x-y+y-z=a+b\in \mathbb{Z} }[/math].

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

הגדרה: תהא 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]

משפט: יהא 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{ T\subseteq \mathbb{R}\times \mathbb{R} }[/math] והראינו שהוא שקילות. הוכיחו:

א. [math]\displaystyle{ x\in \mathbb{R}\smallsetminus \mathbb{Q}\Rightarrow [x]_T\subseteq \mathbb{R}\smallsetminus \mathbb{Q} }[/math].

ב. אם [math]\displaystyle{ x,y\in [0,1) }[/math] שונים אז [math]\displaystyle{ [x]_T\neq [y]_T }[/math].

ג. [math]\displaystyle{ \forall x\in \mathbb{R} \exists y\in [0,1): [x]_T=[y]_T }[/math].

פתרון

א. יהי [math]\displaystyle{ x\in \mathbb{R}\smallsetminus \mathbb{Q} }[/math] ונניח בשלילה שקיים [math]\displaystyle{ q\in \mathbb{Q}\cap [x]_T }[/math]. נקבל שקיים [math]\displaystyle{ a\in \mathbb{Z} }[/math] כך ש [math]\displaystyle{ x-q=a }[/math] ולכן [math]\displaystyle{ x=a+q\in \mathbb{Q} }[/math] בסתירה (סגירות הרציונאליים).

ב. בה"כ [math]\displaystyle{ x\gt y }[/math] ולכן [math]\displaystyle{ x-y\gt 0 }[/math] ומאידך, כיון ששניהם בין 0 ל-1 נקבל [math]\displaystyle{ x-y\lt 1 }[/math], ולכן ההפרש בהכרח לא שלם, לכן הם לא שקולים.

ג. כל מספר כשמחסרים ממנו את הערך השלם התחתון שלו מקבלים משהו בין 0 ל-1, והם שקולים כי ההפרש הוא הערך השלם התחתון, שהוא, מהגדרתו, מספר שלם.