תרגול 10 תשעז: הבדלים בין גרסאות בדף

גרסה אחרונה מ־14:35, 16 ביולי 2019

יחסי שקילות

הגדרה: תהא [math]\displaystyle{ A }[/math] קבוצה ו-[math]\displaystyle{ R }[/math] יחס עליה. [math]\displaystyle{ R }[/math] יקרא יחס שקילות (יח"ש) אם הוא

רפלקסיבי
סימטרי
טרנזיטיבי

סימון מקובל: אם [math]\displaystyle{ R }[/math] יחס שקילות מסמנים גם [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{ Q,R,S,T }[/math] באופן הבא: לכל [math]\displaystyle{ x,y\in \mathbb{R} }[/math]:

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

[math]\displaystyle{ xRy\iff x-y\in \mathbb{N}\cup \{0\} }[/math]

[math]\displaystyle{ xSy\iff x-y\in 2\mathbb{Z}\cup 3\mathbb{Z} }[/math].

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

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

פתרון

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

[math]\displaystyle{ R }[/math] אמנם רפלקסיבי, אך לא סימטרי.

[math]\displaystyle{ S }[/math] לא טרנזיטיבי: [math]\displaystyle{ 2S6\land 6S3 }[/math] אבל לא נכון ש-[math]\displaystyle{ 2S3 }[/math].

[math]\displaystyle{ T }[/math] כן יחס שקילות:

רפלקסיביות: יהי [math]\displaystyle{ x\in \mathbb{R} }[/math], אז [math]\displaystyle{ x-x=0\in \mathbb{Z} }[/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].

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

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

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

הגדרה:

יהא [math]\displaystyle{ R }[/math] יחס שקילות על [math]\displaystyle{ A }[/math] אזי

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

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

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

הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של [math]\displaystyle{ A }[/math].

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

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

תרגיל

ראינו לעיל יחס [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, והם שקולים כי ההפרש הוא הערך השלם התחתון, שהוא, מהגדרתו, מספר שלם.

תרגיל

על [math]\displaystyle{ \mathbb{R}\times \mathbb{R} }[/math] נגדיר יחס [math]\displaystyle{ \sim }[/math] לפי זה שלכל [math]\displaystyle{ (x_1,y_1),(x_2,y_2) }[/math]:

[math]\displaystyle{ (x_1,y_1)\sim (x_2,y_2)\iff x_1^2+y_1^2=x_2^2+y_2^2 }[/math].

קל לראות שזהו יחס שקילות. מהי, מבחינה גיאומטרית מחלקת השקילות של [math]\displaystyle{ (0,1) }[/math]? ומהי, מבחינה גיאומטרית, קבוצת המנה?

פתרון

מעגל עם רדיוס 1 מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית.

@@ שורה 1: / שורה 1: @@
-'''הערה:'''
+חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
-עבור <math>A</math> קבוצה ויחס סדר חלקי עליה. נסמן <math>(A,\leq )</math>  את הקבוצה עם היחס
+==יחסי שקילות==
+הגדרה: תהא <math>A</math> קבוצה ו-<math>R</math> יחס עליה. <math>R</math> יקרא '''יחס שקילות''' (יח"ש) אם הוא
+#רפלקסיבי
+#סימטרי
+#טרנזיטיבי
+'''סימון מקובל:'''
+אם <math>R</math> יחס שקילות מסמנים גם <math>x \sim y</math> עבור <math>(x,y)\in R</math>.
-'''הגדרות.''' יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:
+וכן נסמן <math>(A,\sim)</math> את הקבוצה עם יחס השקילות.
-*חסם מלעיל של B הוא איבר <math>x\in A</math> כך שמתקיים <math>\forall y\in B:(y,x)\in R </math>
-*חסם מלרע של B הוא איבר <math>x\in A</math> כך שמתקיים <math>\forall y\in B:(x,y)\in R </math>
-*החסם העליון (סופרמום) של B הינו המינימום של קבוצת חסמי המלעיל (אם קיים). מסומן <math>sup(B)</math>
-*החסם התחתון (אינפימום) של B הינו המקסימום של קבוצת חסמי המלרע (אם קיים). מסומן <math>inf(B)</math>
-=== דוגמאות ===
+====תרגיל====
-'''דוגמא'''
+על <math>\mathbb{R}</math> נגדיר ארבעה יחסים <math>Q,R,S,T</math> באופן הבא: לכל <math>x,y\in \mathbb{R}</math>:
-עבור <math>\{A_i\}_{i\in I}</math> אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא
-<math>\cup _{i\in I} A_i </math>
-'''דוגמא.'''
+<math>xQy\iff x-y=17</math>
-נביט בקבוצה <math>A=\{1,2,3,4,5\}</math> ונגדיר עליה יחס סדר חלקי:
+<math>xRy\iff x-y\in \mathbb{N}\cup \{0\}</math>
-<math>R=\{(1,1),(2,2),(3,3),(4,4),(5,5),(2,4),(1,2),(1,4),(3,2),(3,4),(5,2),(5,4)\}</math>
+<math>xSy\iff x-y\in 2\mathbb{Z}\cup 3\mathbb{Z}</math>.
-(הזוגיים 'גדולים' מכל אי הזוגיים ומהזוגיים הקטנים מהם)
+<math>xTy\iff x-y\in \mathbb{Z}</math>.
-נביט בתת הקבוצה המכילה את המספרים האי זוגיים בלבד <math>B=\{1,3,5\}</math>. קבוצת חסמי המלעיל של B הינה <math>\{2,4\}</math>. המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.
+בדקו עבור כל אחד מהם האם הוא יחס שקילות.
-'''הגדרה.''' יהי R יחס סדר חלקי על A. אם לכל שני איברים a,b בA מתקיים <math>[(a,b)\in R]\or[(b,a)\in R]</math> אזי R נקרא '''יחס סדר מלא'''.
+=====פתרון=====
-למשל: היחס 'קטן שווה' על השלמים/הממשיים הוא יחס סדר מלא.
+<math>Q</math> לא כיון שלא רפלקסיבי, שהרי לכל <math>x\in \mathbb{R}</math> (ובפרט קיים לפחות אחד) <math>x-x=0\neq 17</math>.
-שימו לב כי זו דוגמא ליחס סדר בלי איברים מינימליים או מקסימליים.
-===יחסי שקילות===
+<math>R</math> אמנם רפלקסיבי, אך לא סימטרי.
-הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא
-#רפלקסיבי
+<math>S</math> לא טרנזיטיבי: <math>2S6\land 6S3</math> אבל לא נכון ש-<math>2S3</math>.
-#סימטרי
-#טרנזיטיבי
+<math>T</math> כן יחס שקילות:
+רפלקסיביות: יהי <math>x\in \mathbb{R}</math>, אז <math>x-x=0\in \mathbb{Z}</math>.
+סימטריות: <math>xTy\Rightarrow \exists a\in \mathbb{Z} :x-y=a \Rightarrow y-x=-a\in \mathbb{Z} \Rightarrow yTx</math>.
+טרנזיטיביות: <math>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>.
+===מחלקות שקילות וחלוקה===
-'''סימון מקובל:'''
+הגדרה: תהא <math>A</math> קבוצה. '''חלוקה''' של <math>A</math> היא אוסף של תת קבוצות זרות של <math>A</math> המכסות את <math>A</math>. באופן פורמלי קיימות תת קבוצות <math>\{A_i\}_{i\in I}</math>
+כך שמתקיים:
+* <math>\forall i\in I: A_i \neq \varnothing </math>.
+* <math>\bigcup _{i\in I} A_i =A </math> כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה.
+* הקבוצות <math>A_i</math> הן '''זרות בזוגות'''. כלומר החיתוך בין כל שתי תת קבוצות הוא ריק (<math>\forall i\ne j\in I : A_i\cap A_j = \varnothing</math>).
-אם R יחס שקילות מסמנים גם <math>x \sim y</math> עבור <math>(x,y)\in R</math>
+הגדרה:
-וכן נסמן <math>(A,\sim)</math> את הקבוצה עם יחס השקילות
+יהא <math>R</math> יחס שקילות על <math>A</math> אזי
-דוגמא נוספת:
+# לכל <math>x\in A</math> מוגדרת '''מחלקת השקילות של <math>x</math>''' להיות  <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\}</math>.
+# ''' קבוצת המנה ''' מוגדרת <math>A/R := \{ [x]_R | x\in A\} </math>.
-נגדיר יחס שקילות R על <math>\mathbb{Z}</math> ע"י  <math>3|(x-y) \Leftrightarrow xRy</math>
-טענה: R אכן יחס שקילות
+'''משפט''': יהא <math>R</math> יחס שקילות על <math>A</math> אזי
+# לכל <math>x,y\in A</math> מתקיים <math>[x]=[y]</math> או <math>[x]\cap [y] =\varnothing </math> (כלומר מחלקות השקילות זרות).
+# <math>A=\bigcup_{[x]\in A/R}[x]</math> (כלומר איחוד מחלקות השקילות הוא כל <math>A</math>).
+הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של <math>A</math>.
-הוכחה:
-. רפלקסיביות - נניח <math>\forall x\in \mathbb{Z}:3|0=x-x</math> לכן <math>xRx</math>
+מסקנה:
+תהא <math>A</math> קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על <math>A</math>}
+<math>\leftrightarrow</math> {חלוקות של <math>A</math>}.
-. סימטריות - נניח <math>(x,y)\in R</math> אזי <math>3|(x-y)</math> ולכן גם <math>3|(y-x)=-(x-y)</math>
+חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
-. טרנזיטיביות - נניח <math>[(x,y)\in R] \and [(y,z)\in R]</math> אזי <math>3|(x-y)\and 3|(y-z) </math>
+====תרגיל====
-ולכן גם <math>3|(z-x)=(z-y)+(y-x)</math>
+ראינו לעיל יחס <math>T\subseteq \mathbb{R}\times \mathbb{R}</math> והראינו שהוא יחס שקילות. הוכיחו:
-הגדרה: תהא A קבוצה. '''חלוקה''' של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות <math>\{A_i\}_{i\in I}</math>
+א. <math>x\in \mathbb{R}\smallsetminus \mathbb{Q}\Rightarrow [x]_T\subseteq \mathbb{R}\smallsetminus \mathbb{Q}</math>.
-כך ש:
-* <math>\forall i\in I: A_i \neq \emptyset </math>
-* <math>\cup _{i\in I} A_i =A </math> כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
-* הקבוצות <math>A_i</math> הן '''זרות''' זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק (<math>\forall i\not= j\in I : A_i\cap A_j = \phi </math>)
-הגדרה:
+ב. אם <math>x,y\in [0,1)</math> שונים אז <math>[x]_T\neq [y]_T</math>.
-יהא R יחס שקילות על A  אזי
+ג. <math>\forall x\in \mathbb{R} \exists y\in [0,1): [x]_T=[y]_T</math>.
-# לכל <math>x\in A</math> מוגדרת '''מחלקת השקילות של x ''' להיות  <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} </math>
+=====פתרון=====
-# ''' קבוצת המנה ''' מוגדרת <math>A/R := \{ [x]_R | x\in A\} </math>
+א.נוכיח בשלילה: יהי <math>x\in \mathbb{R}\smallsetminus \mathbb{Q}</math> ונניח בשלילה שקיים <math>q\in \mathbb{Q}\cap [x]_T</math>. נקבל שקיים <math>a\in \mathbb{Z}</math> כך ש <math>x-q=a</math> ולכן <math>x=a+q\in \mathbb{Q}</math> בסתירה (סגירות הרציונאליים).
+ב. בהינתן כל <math>x>y</math> ולכן <math>x-y>0</math> ומאידך, כיון ששניהם בין 0 ל-1 נקבל <math>x-y<1</math>, ולכן ההפרש בהכרח לא שלם, ולכן הם לא שקולים.
-למשל, בדוגמא הראשונה <math>A_1,A_2,A_3</math> הן מחלקות השקילות. קבוצת המנה היא <math>A/R=\{A_1,A_2,A_3\}</math>
+ג. כל מספר כשמחסרים ממנו את הערך השלם התחתון שלו מקבלים משהו בין 0 ל-1, והם שקולים כי ההפרש הוא הערך השלם התחתון, שהוא, מהגדרתו, מספר שלם.
-בדוגמא השניה מחלקת השקילות של 0 היא <math>[0]_R=\{ 0 \pm 3 \pm 6 \dots \}</math> וקבוצת המנה היא
+====תרגיל====
-<math>\mathbb{Z}/R= \{[0]_R,[1]_R,[2]_R\}</math> (כלומר כל השאריות האפשריות בחלוקה ב-3).
+על <math>\mathbb{R}\times \mathbb{R}</math> נגדיר יחס <math>\sim</math> לפי זה שלכל <math>(x_1,y_1),(x_2,y_2)</math>:
-משפט: יהא R יחס שקילות על A אזי
+<math>(x_1,y_1)\sim (x_2,y_2)\iff x_1^2+y_1^2=x_2^2+y_2^2</math>.
-# לכל <math>x,y\in A</math> מתקיים <math>[x]=[y]</math> או <math>[x]\cap [y] =\phi </math> (כלומר מחלקות השקילות זרות)
-# <math>A=\bigcup_{[x]\in A/R}[x]</math> כלומר (איחוד מחלקות השקילות תתן את כל A)
-הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
+קל לראות שזהו יחס שקילות. מהי, מבחינה גיאומטרית מחלקת השקילות של <math>(0,1)</math>? ומהי, מבחינה גיאומטרית, קבוצת המנה?
-מסקנה:
+=====פתרון=====
-תהא A קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על A }
-<math>\leftrightarrow</math> {חלוקות של A}
-חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
+מעגל עם רדיוס 1 מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית.