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

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

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

תוכן עניינים

1 יחסי שקילות
- 1.1 תרגיל
  - 1.1.1 פתרון
- 1.2 מחלקות שקילות וחלוקה
  - 1.2.1 תרגיל
    - 1.2.1.1 פתרון
  - 1.2.2 תרגיל
    - 1.2.2.1 פתרון

יחסי שקילות

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

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

סימון מקובל: אם $R$ יחס שקילות מסמנים גם $x \sim y$ עבור $(x,y)\in R$ .

וכן נסמן $(A,\sim)$ את הקבוצה עם יחס השקילות.

תרגיל

על $\mathbb{R}$ נגדיר ארבעה יחסים $Q,R,S,T$ באופן הבא: לכל $x,y\in \mathbb{R}$ :

$xQy\iff x-y=17$

$xRy\iff x-y\in \mathbb{N}\cup \{0\}$

$xSy\iff x-y\in 2\mathbb{Z}\cup 3\mathbb{Z}$ .

$xTy\iff x-y\in \mathbb{Z}$ .

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

פתרון

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

$R$ אמנם רפלקסיבי, אך לא סימטרי.

$S$ לא טרנזיטיבי: $2S6\land 6S3$ אבל לא נכון ש- $2S3$ .

$T$ כן יחס שקילות:

רפלקסיביות: יהי $x\in \mathbb{R}$ , אז $x-x=0\in \mathbb{Z}$ .

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

טרנזיטיביות: עיבוד הנוסחה נכשל (שגיאת תחביר): 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} .

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

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

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

הגדרה:

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

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

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

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

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

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

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

תרגיל

ראינו לעיל יחס $T\subseteq \mathbb{R}\times \mathbb{R}$ והראינו שהוא יחס שקילות. הוכיחו:

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

ב. אם $x,y\in [0,1)$ שונים אז $[x]_T\neq [y]_T$ .

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

פתרון

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

ב. בהינתן כל $x>y$ ולכן $x-y>0$ ומאידך, כיון ששניהם בין 0 ל-1 נקבל $x-y<1$ , ולכן ההפרש בהכרח לא שלם, ולכן הם לא שקולים.

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

תרגיל

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

$(x_1,y_1)\sim (x_2,y_2)\iff x_1^2+y_1^2=x_2^2+y_2^2$ .

קל לראות שזהו יחס שקילות. מהי, מבחינה גיאומטרית מחלקת השקילות של $(0,1)$ ? ומהי, מבחינה גיאומטרית, קבוצת המנה?

פתרון

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

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

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

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

תוכן עניינים

יחסי שקילות

תרגיל

פתרון

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

תרגיל

פתרון

תרגיל

פתרון

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים