תרגול 10 תשעז: הבדלים בין גרסאות בדף
אין תקציר עריכה |
|||
| שורה 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>. | |||
וכן נסמן <math>(A,\sim)</math> את הקבוצה עם יחס השקילות. | |||
וכן נסמן <math>(A,\sim)</math> את הקבוצה עם יחס השקילות | |||
====תרגיל==== | ====תרגיל==== | ||
| שורה 25: | שורה 24: | ||
<math>xTy\iff \exists a\in \mathbb{Z}:x-y=a</math>. | <math>xTy\iff \exists a\in \mathbb{Z}:x-y=a</math>. | ||
האם | בדקו עבור כל אחד מהם האם הוא יחס שקילות. | ||
=====פתרון===== | =====פתרון===== | ||
| שורה 33: | שורה 32: | ||
<math>R</math> אמנם רפלקסיבי, אך לא סימטרי. | <math>R</math> אמנם רפלקסיבי, אך לא סימטרי. | ||
<math>S</math> לא טרנזיטיבי: <math>2S6\land 6S3</math> אבל לא נכון ש <math>2S3</math>. | <math>S</math> לא טרנזיטיבי: <math>2S6\land 6S3</math> אבל לא נכון ש-<math>2S3</math>. | ||
<math>T</math> כן: | <math>T</math> כן יחס שקילות: | ||
רפלקסיביות: יהי <math>x\in \mathbb{R}</math>, ניקח <math>a=0</math> ואז <math>x-x=0=a</math>. | רפלקסיביות: יהי <math>x\in \mathbb{R}</math>, ניקח <math>a=0</math> ואז <math>x-x=0=a</math>. | ||
| שורה 41: | שורה 40: | ||
סימטריות: <math>xTy\Rightarrow \exists a\in \mathbb{Z} :x-y=a \Rightarrow y-x=-a\in \mathbb{Z} \Rightarrow yTx</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>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 היא | הגדרה: תהא <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 \ | * <math>\forall i\in I: A_i \neq \varnothing </math>. | ||
* <math>\ | * <math>\bigcup _{i\in I} A_i =A </math> כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה. | ||
* הקבוצות <math>A_i</math> הן '''זרות''' | * הקבוצות <math>A_i</math> הן '''זרות בזוגות'''. כלומר החיתוך בין כל שתי תת קבוצות הוא ריק (<math>\forall i\ne j\in I : A_i\cap A_j = \varnothing</math>). | ||
הגדרה: | הגדרה: | ||
יהא R יחס שקילות על A | יהא <math>R</math> יחס שקילות על <math>A</math> אזי | ||
# לכל <math>x\in A</math> מוגדרת '''מחלקת השקילות של x ''' להיות <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} </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>A/R := \{ [x]_R | x\in A\} </math>. | ||
משפט: יהא R יחס שקילות על A אזי | '''משפט''': יהא <math>R</math> יחס שקילות על <math>A</math> אזי | ||
# לכל <math>x,y\in A</math> מתקיים <math>[x]=[y]</math> או <math>[x]\cap [y] =\ | # לכל <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=\bigcup_{[x]\in A/R}[x]</math> (כלומר איחוד מחלקות השקילות הוא כל <math>A</math>). | ||
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A | הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של <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>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\in \mathbb{R}\smallsetminus \mathbb{Q}\Rightarrow [x]_T\subseteq \mathbb{R}\smallsetminus \mathbb{Q}</math>. | ||
| שורה 83: | שורה 82: | ||
א. יהי <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\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>x>y</math> ולכן <math>x-y>0</math> ומאידך, כיון ששניהם בין 0 ל-1 נקבל <math>x-y<1</math>, ולכן ההפרש בהכרח לא שלם, ולכן הם לא שקולים. | ||
ג. כל מספר כשמחסרים ממנו את הערך השלם התחתון שלו מקבלים משהו בין 0 ל-1, והם שקולים כי ההפרש הוא הערך השלם התחתון, שהוא, מהגדרתו, מספר שלם. | ג. כל מספר כשמחסרים ממנו את הערך השלם התחתון שלו מקבלים משהו בין 0 ל-1, והם שקולים כי ההפרש הוא הערך השלם התחתון, שהוא, מהגדרתו, מספר שלם. | ||
| שורה 89: | שורה 88: | ||
====תרגיל==== | ====תרגיל==== | ||
על <math>\mathbb{R}\times \mathbb{R}</math> נגדיר יחס <math> | על <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)~(x_2,y_2)\iff x_1^2+y_1^2=x_2^2+y_2^2</math>. | <math>(x_1,y_1)~(x_2,y_2)\iff x_1^2+y_1^2=x_2^2+y_2^2</math>. | ||
| שורה 97: | שורה 96: | ||
=====פתרון===== | =====פתרון===== | ||
מעגל עם רדיוס 1 מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית. | מעגל עם רדיוס <math>1</math> מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית. | ||
גרסה מ־23:53, 23 בדצמבר 2017
חזרה לדף מערכי התרגול.
יחסי שקילות
הגדרה: תהא [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 \exists a\in \mathbb{N}\cup \{0\}:x-y=a }[/math]
[math]\displaystyle{ xSy\iff \exists a\in 2\mathbb{Z}\cup 3\mathbb{Z}:x-y=a }[/math].
[math]\displaystyle{ xTy\iff \exists a\in \mathbb{Z}:x-y=a }[/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{ 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].
מחלקות שקילות וחלוקה
הגדרה: תהא [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)~(x_2,y_2)\iff x_1^2+y_1^2=x_2^2+y_2^2 }[/math].
קל לראות שזהו יחס שקילות. מהי, מבחינה גיאומטרית מחלקת השקילות של [math]\displaystyle{ (0,1) }[/math]? ומהי, מבחינה גיאומטרית, קבוצת המנה?
פתרון
מעגל עם רדיוס [math]\displaystyle{ 1 }[/math] מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית.