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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏יחסי שקילות)
 
(20 גרסאות ביניים של 5 משתמשים אינן מוצגות)
שורה 1: שורה 1:
−
'''הגדרות.''' יהיו A קבוצה, B קבוצה המוכלת בה וR יחס סדר חלקי:
+
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
−
*חסם מלעיל של 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>A</math> קבוצה ו-<math>R</math> יחס עליה. <math>R</math> יקרא '''יחס שקילות''' (יח"ש) אם הוא
 +
#רפלקסיבי
 +
#סימטרי
 +
#טרנזיטיבי
  
−
'''דוגמא.'''
+
'''סימון מקובל:'''  
−
נביט בקבוצת הטבעיים, ובתת קבוצה סופית שלה B. נביט ביחס "מחלק את". הסופרמום של B הוא המכפלה המשותפת המינימלית (lcm), והאינפימום הוא המחלק המשותף המקסימלי(gcd).
+
אם <math>R</math> יחס שקילות מסמנים גם <math>x \sim y</math> עבור <math>(x,y)\in R</math>.
  
−
למשל <math>sup\{12,33,10\}=lcm(12,33,10)=3\cdot 4 \cdot 11 \cdot 5, inf\{12,33,10\}=gcd(12,33,10)=1</math>
+
וכן נסמן <math>(A,\sim)</math> את הקבוצה עם יחס השקילות.
  
−
'''דוגמא'''
+
====תרגיל====
−
עבור <math>\{A_i\}_{i\in I}</math> אוסף קבוצות. החסם העליון שלה הוא (ביחס להכלה) הוא
+
−
<math>\cup _{i\in I} A_i </math>
+
  
−
'''דוגמא.'''
+
על <math>\mathbb{R}</math> נגדיר ארבעה יחסים <math>Q,R,S,T</math> באופן הבא: לכל <math>x,y\in \mathbb{R}</math>:
  
−
נביט בקבוצה <math>A=\{1,2,3,4,5\}</math> ונגדיר עליה יחס סדר חלקי:
+
<math>xQy\iff x-y=17</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>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>B=\{1,3,5\}</math>. קבוצת חסמי המלעיל של B הינה <math>\{2,4\}</math>. המינימום של קבוצה זו הוא 2 ולכן הוא החסם העליון של B. אין חסם מלרע ל-B ולכן בוודאי אין לה חסם תחתון.
+
<math>xTy\iff x-y\in \mathbb{Z}</math>.
  
−
'''הגדרה.''' יהי 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>.
−
הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא
+
−
#רפלקסיבי
+
−
#סימטרי
+
−
#טרנזיטיבי
+
  
−
דוגמא: תהא <math>A=\{1,2,3,4,5,6\}</math>. נגדיר תת הקבוצות <math>A_1=\{1,3\},A_2=\{2,4,5\},A_3=\{6\}</math>
+
<math>R</math> אמנם רפלקסיבי, אך לא סימטרי.
  
−
נגדיר יחס R על A כך <math>\exist 1\leq i \leq 3 : x,y\in A_i \Leftrightarrow xRy</math>
+
<math>S</math> לא טרנזיטיבי: <math>2S6\land 6S3</math> אבל לא נכון ש-<math>2S3</math>.
  
−
טענה R יחס שקילות
+
<math>T</math> כן יחס שקילות:
  
−
הוכחה:
+
רפלקסיביות: יהי <math>x\in \mathbb{R}</math>, אז <math>x-x=0\in \mathbb{Z}</math>.
  
−
1. רפלקסיביות - נניח <math>x\in A</math> לכן x שייך ל <math>A_i</math> עבור i מסוים (שכן האיחוד שלהן שווה לA) ולכן <math>(x,x)\in R</math>.
+
סימטריות: <math>xTy\Rightarrow \exists a\in \mathbb{Z} :x-y=a \Rightarrow y-x=-a\in \mathbb{Z} \Rightarrow yTx</math>.
  
−
2. סימטריות - נניח <math>(x,y)\in R</math> אזי <math>x,y\in A_i</math> עבור i מסוים, מכיוון שאין משמעות לסדר שייכות לקבוצה, נובע שגם <math>(y,x)\in R</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>.
  
−
3. טרנזיטיביות - נניח <math>[(x,y)\in R] \and [(y,z)\in R]</math> אזי קיימים i,j כך ש <math>x,y\in Aֹ_i</math> וגם <math>y,z\in A_j</math>. לכן <math>y\in A_i\cap A_j</math>. מכיוון שהחיתוך בין תתי הקבוצות הוא ריק מוכרח להיות ש<math>A_i=A_j</math> ולכן <math>x,y,z\in A_i</math> ולכן <math>(x,z)\in R</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>).
  
−
הגדרה: תהא A קבוצה. '''חלוקה''' של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות <math>\{A_i\}_{i\in I}</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>)
+
  
−
כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן).
+
יהא <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>
+
'''משפט''': יהא <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>.
  
−
טענה: R אכן יחס שקילות
 
  
−
הוכחה:
+
מסקנה:
 +
תהא <math>A</math> קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על <math>A</math>}
 +
<math>\leftrightarrow</math> {חלוקות של <math>A</math>}.
  
−
1. רפלקסיביות - נניח <math>\forall x\in \mathbb{Z}:3|0=x-x</math> לכן <math>xRx</math>
+
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
  
−
2. סימטריות - נניח <math>(x,y)\in R</math> אזי <math>3|(x-y)</math> ולכן גם <math>3|(y-x)=-(x-y)</math>
+
====תרגיל====
 +
ראינו לעיל יחס <math>T\subseteq \mathbb{R}\times \mathbb{R}</math> והראינו שהוא יחס שקילות. הוכיחו:
  
−
3. טרנזיטיביות - נניח <math>[(x,y)\in R] \and [(y,z)\in R]</math> אזי <math>3|(x-y)\and 3|(y-z) </math> 
+
א. <math>x\in \mathbb{R}\smallsetminus \mathbb{Q}\Rightarrow [x]_T\subseteq \mathbb{R}\smallsetminus \mathbb{Q}</math>.
−
ולכן גם <math>3|(z-x)=(z-y)+(y-x)</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>.
  
−
יהא R יחס שקילות על A  אזי
+
=====פתרון=====
 +
א.נוכיח בשלילה: יהי <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 A</math> מוגדרת '''מחלקת השקילות של x ''' להיות  <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} </math>
+
ב. בהינתן כל <math>x>y</math> ולכן <math>x-y>0</math> ומאידך, כיון ששניהם בין 0 ל-1 נקבל <math>x-y<1</math>, ולכן ההפרש בהכרח לא שלם, ולכן הם לא שקולים.
−
# ''' קבוצת המנה ''' מוגדרת <math>A/R := \{ [x]_R | x\in A\} </math>
+
  
 +
ג. כל מספר כשמחסרים ממנו את הערך השלם התחתון שלו מקבלים משהו בין 0 ל-1, והם שקולים כי ההפרש הוא הערך השלם התחתון, שהוא, מהגדרתו, מספר שלם.
  
−
למשל, בדוגמא הראשונה <math>A_1,A_2,A_3</math> הן מחלקות השקילות. קבוצת המנה היא <math>A/R=\{A_1,A_2,A_3\}</math>
+
====תרגיל====
  
−
בדוגמא השניה מחלקת השקילות של 0 היא <math>[0]_R=\{ 0 \pm 3 \pm 6 \dots \}</math> וקבוצת המנה היא
+
על <math>\mathbb{R}\times \mathbb{R}</math> נגדיר יחס <math>\sim</math> לפי זה שלכל <math>(x_1,y_1),(x_2,y_2)</math>:
−
<math>\mathbb{Z}/R= \{[0]_R,[1]_R,[2]_R\}</math> (כלומר כל השאריות האפשריות בחלוקה ב-3).
+
  
 +
<math>(x_1,y_1)\sim (x_2,y_2)\iff x_1^2+y_1^2=x_2^2+y_2^2</math>.
  
−
משפט: יהא R יחס שקילות על A אזי
+
קל לראות שזהו יחס שקילות. מהי, מבחינה גיאומטרית מחלקת השקילות של <math>(0,1)</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
+
  
 +
=====פתרון=====
  
−
מסקנה:
+
מעגל עם רדיוס 1 מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית.
−
תהא A קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על A }
+
−
<math>\leftrightarrow</math> {חלוקות של A}
+
−
 
+
−
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
+

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

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

יחסי שקילות

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

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

סימון מקובל: אם 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 אזי

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


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

  1. לכל x,y\in A מתקיים [x]=[y] או [x]\cap [y] =\varnothing (כלומר מחלקות השקילות זרות).
  2. 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 מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית.

מקור: https://math-wiki.com/index.php?title=תרגול_10_תשעז&oldid=81807