לדלג לתוכן
שינוי מצב סרגל צד
Math-Wiki
חיפוש
יצירת חשבון
כלים אישיים
יצירת חשבון
כניסה לחשבון
דפים לעורכים שלא נכנסו לחשבון
מידע נוסף
שיחה
תרומות
ניווט
עמוד ראשי
שינויים אחרונים
העלאת קובץ
כלים
דפים המקושרים לכאן
שינויים בדפים המקושרים
דפים מיוחדים
מידע על הדף
עריכת הדף "
88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 2
" (פסקה)
דף
שיחה
עברית
קריאה
עריכה
גרסאות קודמות
עוד
קריאה
עריכה
גרסאות קודמות
אזהרה:
אינכם מחוברים לחשבון. כתובת ה־IP שלכם תוצג בפומבי אם תבצעו עריכות כלשהן. אם
תיכנסו לחשבון
או
תיצרו חשבון
, העריכות שלכם תיוחסנה לשם המשתמש שלכם ותקבלו גם יתרונות אחרים.
בדיקת אנטי־ספאם.
אין
למלא שדה זה!
==יחסי שקילות== הגדרה: תהא 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> נגדיר יחס R על A כך <math>\exist 1\leq i \leq 3 : x,y\in A_i \Leftrightarrow xRy</math> טענה R יחס שקילות הוכחה: 1. רפלקסיביות - נניח <math>x\in A</math> לכן x שייך ל <math>A_i</math> עבור i מסוים (שכן האיחוד שלהן שווה לA) ולכן <math>(x,x)\in R</math>. 2. סימטריות - נניח <math>(x,y)\in R</math> אזי <math>x,y\in A_i</math> עבור i מסוים, מכיוון שאין משמעות לסדר שייכות לקבוצה, נובע שגם <math>(y,x)\in R</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> כפי שרצינו. הגדרה: תהא 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>\forall i\not= j\in I : A_i\cap A_j = \phi </math>) כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן). '''הערה:''' אפשר להציג את היחס על <math>P(X)</math> שמוגדר ע"י <math>A\sim B\iff A\cap S=B\cap S </math> (כאשר S ת"ק קבועה), אם כי זה נעשה בשיעורי הבית. מוזמנים לקחת קבוצות S,X קונקרטיות ולתאר בצורה מדויקת איך היחס נראה ("איך היחס נראה" זה לא שאלה מוגדרת היטב - הכוונה שתוודאו שאתם יודעים להסביר לעצמכם מה הולך שמה). בנוסף, חשבו מה קורה ביחסים: # <math>A\sim B\iff A\cup S=B\cup S </math> # <math>A\sim B\iff A\triangle S=B\triangle S </math> ====תרגיל==== נגדיר על <math>\mathbb{R}</math> ארבעה יחסים <math>Q,R,S,T</math> באופן הבא: לכל <math>x,y\in \mathbb{R}</math>: <math>xQy\iff x-y=17</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>xTy\iff x-y\in \mathbb{Z}</math>. בדקו עבור כל אחד מהם האם הוא יחס שקילות. =====פתרון===== <math>Q</math> לא כיון שלא רפלקסיבי, שהרי לכל <math>x\in \mathbb{R}</math> (ובפרט קיים לפחות אחד) <math>x-x=0\neq 17</math>. <math>R</math> אמנם רפלקסיבי, אך לא סימטרי. <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>. ===מחלקות שקילות וקבוצת המנה=== הגדרה: יהא R יחס שקילות על A אזי # לכל <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>A_1,A_2,A_3</math> הן מחלקות השקילות. קבוצת המנה היא <math>A/R=\{A_1,A_2,A_3\}</math> משפט: יהא R יחס שקילות על A אזי # לכל <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 מסקנה: תהא A קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על A } <math>\leftrightarrow</math> {חלוקות של A} חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת. ====תרגיל==== כמה יחסי שקילות שונים יש על <math>A=\{1,2,3\}</math>? פתרון: נספור לפי חלוקות ונגלה כי התשובה היא 5. ====תרגיל==== תהי <math>A=\{1,2,3\}</math> קבוצה. השלם את היחסים הבאים מעליה על מנת שיקיימו את התכונות הנדרשות בשאלה (השלם - כלומר הוסף זוגות סדורים '''הכרחיים'''): *השלם את <math>R=\{(1,2)\}</math> להיות יחס סימטרי וטרנזיטיבי. האם אחרי ההשלמה קיבלת יחס שקילות? *השלם את הקבוצה הריקה ליחס שקילות. איך קוראים ליחס שקיבלת? מהן מחלקות השקילות? =====פתרון===== 1. <math>R=\{(1,2),(2,1),(1,1),(2,2)\}</math> זה אינו יחס שקילות מכיוון שאינו רפלקסיבי - (3,3) חסר. 2. <math>R=\{(1,1),(2,2),(3,3)\}</math>. זהו יחס השיוויון, מחלקות השקילות שלו הינן [1],[2],[3]. ====תרגיל==== ראינו לעיל יחס <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\neq y</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 מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית (כלומר: קבוצה של קבוצות של זוגות סדורים שהם הנק' על כל מעגל לפי הרדיוס שלו). ==== תרגיל ==== תהא <math>A</math> קבוצה ותהא <math>S\subseteq A</math> ת"ק שלה. נגדיר יחס <math>\sim</math> על <math>P(A)</math> ע"י הכלל <math>B_1\sim B_2 \iff B_1 \cup S=B_2\cup S</math> * הוכיחו כי זהו יחס שקילות. * עבור <math>S=\{1,7,9,10\},A=\{1,2,\dots 10\}</math> מצאו את מספר האיברים ב <math>P(A)/\sim</math> =====פתרון===== * יש לבדוק פשוט שהתכונות של יחס שקילות מתקיימות לפי הגדרת היחס הנתון. * נשים לב ששתי קבוצות ב-(P(A שקולות זו לזו אם ורק אם הן נבדלות זו מזו רק באיברים השייכים ל-S (אפשר להוכיח), כלומר: אם ההפרש הסימטרי שלהן מוכל ב-S. לכן, אם אנו רוצים לספור מחלקות שקילות (שונות), עלינו לספור כמה אפשרויות יש לחלק של ההפרש הסימטרי שאינו מוכל ב-S (החלק שמוכל אינו משפיע). כיוון שחלק זה יכול להיות כל תת קבוצה של המשלים של S (ביחס ל-A), וכיוון שבמשלים זה יש 6 איברים, נקבל שישנן 6^2 אפשרויות, ולכן זהו מספר מחלקות השקילות, כלומר: גודל קבוצת המנה. ===דוגמא חשובה - הגדרת הרציונאליים === נביט בקבוצת המכפלה הקרטזית של השלמים עם עצמם <math>\mathbb{Z}\times \mathbb{N} </math>. נסתכל על ההתאמה <math>(a,b)\leftrightarrow\frac{a}{b}</math> האם תחת ההתאמה הזו ניתן להגדיר את הרציונאליים באמצעות המכפלה הקרטזית לעיל בלבד? תשובה: לא. למשל, <math>\frac{2}{6}=\frac{1}{3}</math> ואילו <math>(2,6)\neq (1,3)</math>. כלומר, המכפלה הקרטזית מכילה חזרות מיותרות לעומת הרציונאליים. נרצה איפוא, להגדיר יחס שקילות על הזוגות הסדורים של מספרים שלמים כך שכל שני שברים שקולים יהיו ביחס. שימו לב שאנו מגדירים יחס על קבוצת זוגות סדורים, ולכן האיברים ביחס הינם זוגות סדורים של זוגות סדורים. נגדיר <math>R</math> על <math>\mathbb{Z}\times \mathbb{N} </math> ע"י <math>(x,y)R(z,w) \iff xw=zy</math> (כלומר אם מתקיים עבור השברים <math>\frac{x}{y}=\frac{z}{w}</math>) נוכיח רק טרנזיטיביות: נניח <math>(x,y)R(z,w), (z,w)R(a,b) </math> אזי <math> xw=zy, zb=aw </math> (צ"ל <math> xb=ay </math>) כייון ש <math> w \not=0 </math> נקבל כי <math>x=\frac{zy}{w}</math> ולכן <math>xb=\frac{zby}{w}=\frac{awy}{w}=ay</math> כנדרש. ומי שלא רוצה להשתמש בחילוק (אבל כן מתיר לצמצם משיוויון איבר שנמצא בשני הצדדים, כי ניתן להשתכנע בכך מהגדרת כפל על טבעיים): נשים לב שמתקיים: <math>xwb=zyb=yaw</math>, ולכן נקבל <math>xb=ay</math> כנדרש. מסקנה: הרציונאלים הם קבוצת המנה של <<math>\mathbb{Z}\times \mathbb{N} </math> והיחס שהגדרנו לעיל. למעשה, מאחורי כל שבר עומדת הקבוצה האינסופית של כל השברים השקולים לו, ופשוט אנחנו בוחרים לייצג קבוצה זו על ידי אחד השברים שבה באופן שרירותי (או באופן מסוים - בחירת השבר המצומצם). ===שאלה ממבחן=== א. תהי A קבוצה לא ריקה ותהי <math>\{R_i\}_{i\in I}</math> משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי <math>R=\cap_{i\in I}R_i</math> הינו יחס שקילויות על A. ב. נסמן <math>R_n=\{(x,y)\in\mathbb{Z}\times\mathbb{Z}:n|(x-y)\}</math>. מהם <math>R_1,R_2,R=\cap_{n\in\mathbb{N}}R_n</math>? מהן קבוצות המנה <math>\mathbb{Z}/R,\mathbb{Z}/R_1,\mathbb{Z}/R_2</math>? ====פתרון==== א. רפלקסיביות: מאחר ו <math>\forall a\in A\forall i\in I : (a,a)\in R_i</math> נובע ש <math>\forall a\in A: (a,a)\in R</math>. סימטריות: נניח <math>(x,y)\in R</math> לכן <math>\forall i\in I:(x,y)\in R_i</math> ולכן נובע מסמטריות היחסים ש <math>\forall i\in I:(y,x)\in R_i</math> ולכן <math>(y,x)\in R</math>. טרנזיטיביות: ממש אותו דבר... ב. <math>R_1</math> הינו אוסף כל הזוגות הסדורים מעל השלמים, שכן אחד מחלק כל מספר ולכן כל הפרש. <math>R_2</math> הינו אוסף כל הזוגות בהם שני הצדדים זוגיים או שני הצדדים אי זוגיים, שכן ההפרש בינהם חייב להיות זוגי. R הינו אוסף הזוגות שההפרש בינהם מתחלק בכל המספרים הטבעיים. רק הפרש אפס יכול להתחלק בכל מספר, ולכן R הינו אוסף הזוגות מהצורה (q,q) עבור q מספר שלם. (יחס השיוויון.) <math>\mathbb{Z}/R_1</math> הינו אוסף מחלקות השקילות של היחס המכיל את כל הזוגות. יש בו רק מחלקת שקילות אחת המכילה את כל המספרים השלמים. <math>\mathbb{Z}/R_2</math> מכיל שתי קבוצות, קבוצת הזוגיים וקבוצת האי זוגיים שכן בין כל הזוגיים יש את היחס, ובין כל האי זוגיים ולא בין לבין כמובן (הרי זה יחס שקילויות כפי שקל להוכיח). <math>\mathbb{Z}/R</math> הינו אוסף כל הקבוצות המכילות איבר שלם בודד.
תקציר:
לתשומת לבך: תורמים אחרים עשויים לערוך או אף להסיר את תרומתך ל־Math-Wiki. אם אינך רוצה שעבודתך תהיה זמינה לעריכה על־ידי אחרים, אין לפרסם אותה פה.
כמו־כן, שמירת העריכה משמעה הבטחה שכתבת את הטקסט הזה בעצמך, או העתקת אותו ממקור שאינו מוגן בזכויות יוצרים (אפשר לעיין בדף
Math-Wiki:זכויות יוצרים
לפרטים נוספים).
אין לעשות שימוש בחומר המוגן בזכויות יוצרים ללא רשות!
ביטול
עזרה בעריכה
(נפתח בחלון חדש)