הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 2"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏יחסי שקילות)
(←‏יחסי שקילות)
שורה 92: שורה 92:
  
 
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> כפי שרצינו.
 
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>
 
הגדרה: תהא A קבוצה. '''חלוקה''' של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות <math>\{A_i\}_{i\in I}</math>
שורה 99: שורה 100:
  
 
כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן).  
 
כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן).  
 +
  
 
דוגמא נוספת:
 
דוגמא נוספת:
שורה 104: שורה 106:
 
נגדיר יחס שקילות R על <math>\mathbb{Z}</math> ע"י  <math>3|(x-y) \Leftrightarrow xRy</math>
 
נגדיר יחס שקילות R על <math>\mathbb{Z}</math> ע"י  <math>3|(x-y) \Leftrightarrow xRy</math>
  
−
טענה R אכן יחס שקילות
+
טענה: R אכן יחס שקילות
  
 
הוכחה:
 
הוכחה:
שורה 128: שורה 130:
 
בדוגמא השניה מחלקת השקילות של 0 היא <math>[0]_R=\{ 0 \pm 3 \pm 6 \dots \}</math> וקבוצת המנה היא
 
בדוגמא השניה מחלקת השקילות של 0 היא <math>[0]_R=\{ 0 \pm 3 \pm 6 \dots \}</math> וקבוצת המנה היא
 
<math>\mathbb{Z}/R= \{[0]_R,[1]_R [3]_R\}</math> (כלומר כל השאריות האפשריות בחלוקה ב-3).
 
<math>\mathbb{Z}/R= \{[0]_R,[1]_R [3]_R\}</math> (כלומר כל השאריות האפשריות בחלוקה ב-3).
 +
  
 
משפט: יהא R יחס שקילות על A אזי
 
משפט: יהא R יחס שקילות על A אזי
שורה 133: שורה 136:
 
# <math>A=\bigcup_{[x]\in A/R}[x]</math> כלומר (איחוד מחלקות השקילות תתן את כל A)
 
# <math>A=\bigcup_{[x]\in A/R}[x]</math> כלומר (איחוד מחלקות השקילות תתן את כל A)
 
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
 
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
 +
  
 
מסקנה:
 
מסקנה:

גרסה מ־13:25, 16 ביולי 2013

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

יחסים

הגדרה: המכפלה הקרטזית של שתי קבוצות A וB הינה אוסף כל הזוגות הסדורים - A\times B = \{(a,b)|a\in A \and b\in B\}. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים (1,2),(2,1) והאיבר הבא הינו זוג חוקי (1,1).

ניתן להכליל את ההגדרה לעיל לn-יה סדורה - כלומר n איברים מסודרים.

דוגמא: A=\{1,2,3\} וB=\{a,b\} אזי מתקיים A\times B =\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\}


ניתן להגדיר זוגות סדורים באמצעות הגדרת הקבוצות בלבד, כפי שנראה בתרגיל הבא:

תרגיל

הוכח/הפרך:

1. [(a=c)\and(b=d)]\iff \{\{a\},b\}=\{\{c\},d\}

2. [(a=c)\and(b=d)]\iff \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}

פתרון

1. הפרכה ע"י הדוגמא הנגדית a=2,b=\{3\},c=3,d=\{2\}


2.

הוכחה: הכיוון משמאל לימין הוא ברור. מימין לשמאל, נניח והקבוצות שוות אזי \{a\}=\{c\} או ש \{a\}=\{c,d\}.

במקרה הראשון, נובע a=c ובמקרה השני נובע a=c=d, כך או כך a=c. כעת, \{a,b\}=\{c,b\}=\{c\} או \{c,b\}=\{c,d\} ונובע משניהם ש b=d.


לכן, ניתן להגדיר זוג סדור על ידי קבוצות בלבד (באופן דומה לכך שכל המתמטיקה פחות או יותר נבנת על קבוצות בלבד).


תרגיל

הוכח שלכל קבוצות A,B,C מתקיים A\times(B\cap C)=(A\times B)\cap(A\times C)

פתרון

(x,y)\in A\times(B\cap C) \iff (x\in A) \and [(y\in B)\and (y\in C)] \iff [(x\in A)\and(y\in B)] \and [(x\in A)\and(y\in B)] \iff x\in[(A\times B)\cap(A\times C)]


יחסים כתת קבוצה של הזוגות הסדורים

הגדרה: יהיו A,B קבוצות, R\subseteq A\times B אזי R יקרא יחס (בין A ל -B) הרעיון שעומד בבסיסו של יחס הוא האעשרות "להשוות" בין איברי A ל B דוגמא: A=\{1,2,3\},B=\{0,2,6\} ונביט בתת הקבוצה R\subseteq A\times B הבאה: R=\{(1,2),(1,6),(2,2),(2,6),(3,6)\}. מה מיוחד בזוגות אלה?

זוגות אלה הינן כל זוגות האיברים (a,b) כך ש a\leq b. (כלומר הגדרנו את היחס המייצג "קטן שווה")

הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה S=\{(1,2),(1,6),(2,0),(2,2))\} היא יחס.

סימון: אם זוג מסוים נמצא בקבוצת היחס R נהוג לסמן aRb. (אם יש משמעות ליחס כמו לעיל ניתן גם לסמן פשוט a\leq b.


דוגמא: נביט בקבוצת האנשים A. נגדיר את יחס "בן של" על ידי קבוצת הזוגות הסדורים R\subseteq A\times A כך ש (x,y)\in R אם"ם x הוא בן של y. שימו לב שיש משמעות לכיוון היחס, שכן יש הבדל בין העובדה שאני הבן של מישהו לבין העובדה שהוא הבן שלי.


תכונות של יחסים על קבוצה

הגדרה: יחס R על קבוצה A פירושו R\subseteq A\times A

תהי קבוצה A ויחס R עליה אזי

  1. R נקרא רפלקסיבי אם כל איבר מקיים את היחס עם עצמו ( מתקיים \forall a\in A:(a,a)\in R)
  2. R נקרא סימטרי אם aRb גורר שגם bRa (מתקיים \forall a,b\in A:[(a,b)\in R \rightarrow (b,a)\in R])
  3. R נקרא טרנזיטיבי אם יחס בין ראשון לשני, ויחס בין השני לשלישי גורר יחס בין הראשון לשלישי (מתקיים \forall a,b,c\in A:[((a,b)\in R) \and ((b,c)\in R) \rightarrow ((a,c)\in R)])
  4. R נקרא אנטי סימטרי (חלש) אם aRb וגם bRa גורר כי a=b (מתקיים \forall a,b\in A:[(a,b)\in R \and (b,a)\in R \rightarrow a=b])

דוגמאות:

  • יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
  • יחס 'קטן שווה' הינו רפלקסיבי וטרנזיטיבי
  • יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
  • יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי
  • יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
  • יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי
  • יחס 'אדם x שמע על אדם y' הינו רפלקסיבי

יחסי שקילות

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

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

דוגמא: תהא A=\{1,2,3,4,5,6\}. נגדיר תת הקבוצות A_1=\{1,3\},A_2=\{2,4,5\},A_3=\{6\}

נגדיר יחס R על A כך \exist 1\leq i \leq 3 : x,y\in A_i \Leftrightarrow xRy

טענה R יחס שקילות

הוכחה:

1. רפלקסיביות - נניח x\in A לכן x שייך ל A_i עבור i מסוים (שכן האיחוד שלהן שווה לA) ולכן (x,x)\in R.

2. סימטריות - נניח (x,y)\in R אזי x,y\in A_i עבור i מסוים, מכיוון שאין משמעות לסדר שייכות לקבוצה, נובע שגם (y,x)\in R.

3. טרנזיטיביות - נניח [(x,y)\in R] \and [(y,z)\in R] אזי קיימים i,j כך ש x,y\in Aֹ_i וגם y,z\in A_j. לכן y\in A_i\cap A_j. מכיוון שהחיתוך בין תתי הקבוצות הוא ריק מוכרח להיות שA_i=A_j ולכן x,y,z\in A_i ולכן (x,z)\in R כפי שרצינו.


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

  • \cup _{i\in I} A_i =A כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה
  • הן זרות זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק (\forall i\not= j\in I : A_i\cap A_j = \phi )

כפי שראינו בדוגמה הקודמת חלוקה של A מגדירה יחס שקילות (אמנם זה "רק" דוגמא אבל ניתן להוכיח את המקרה הכללי באותו אופן).


דוגמא נוספת:

נגדיר יחס שקילות R על \mathbb{Z} ע"י 3|(x-y) \Leftrightarrow xRy

טענה: R אכן יחס שקילות

הוכחה:

1. רפלקסיביות - נניח \forall x\in \mathbb{Z}:3|0=x-x לכן xRx

2. סימטריות - נניח (x,y)\in R אזי 3|(x-y) ולכן גם 3|(y-x)=-(x-y)

3. טרנזיטיביות - נניח [(x,y)\in R] \and [(y,z)\in R] אזי 3|(x-y)\and 3|(y-z) ולכן גם 3|(z-x)=(z-y)+(y-x)


הגדרה:

יהא 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\}


למשל, בדוגמא הראשונה A_1,A_2,A_3 הן מחלקות השקילות. קבוצת המנה היא R/A=\{A_1,A_2,A_3\}

בדוגמא השניה מחלקת השקילות של 0 היא [0]_R=\{ 0 \pm 3 \pm 6 \dots \} וקבוצת המנה היא \mathbb{Z}/R= \{[0]_R,[1]_R [3]_R\} (כלומר כל השאריות האפשריות בחלוקה ב-3).


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

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

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


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

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

תרגיל

תהי A=\{1,2,3\} קבוצה. השלם את היחסים הבאים מעליה על מנת שיקיימו את התכונות הנדרשות בשאלה (השלם - כלומר הוסף זוגות סדורים הכרחיים):

  • השלם את R=\{(1,2)\} להיות יחס סימטרי וטרנזיטיבי. האם אחרי ההשלמה קיבלת יחס שקילויות?
  • השלם את הקבוצה הריקה ליחס שקילויות. איך קוראים ליחס שקיבלת? מהן מחלקות השקילות?

פתרון

1. R=\{(1,2),(2,1),(1,1),(2,2)\} זה אינו יחס שקילויות מכיוון שאינו רפלקסיבי - (3,3) חסר.

2. R=\{(1,1),(2,2),(3,3)\}. זהו יחס השיוויון, מחלקות השקילות שלו הינן [1],[2],[3].

דוגמא חשובה - הגדרת הרציונאליים

נביט בקבוצת המכפלה הקרטזית של השלמים עם עצמם \mathbb{Z}\times\mathbb{Z}. נסתכל על ההתאמה (a,b)\leftrightarrow\frac{a}{b} האם תחת ההתאמה הזו ניתן להגדיר את הרציונאליים באמצעות המכפלה הקרטזית לעיל בלבד?

תשובה: לא. למשל, \frac{2}{6}=\frac{1}{3} ואילו (2,6)\neq (1,3). כלומר, המכפלה הקרטזית מכילה חזרות מיותרות לעומת הרציונאליים.

נרצה איפוא, להגדיר יחס שקילויות על הזוגות הסדורים של מספרים שלמים כך שכל שני שברים שקולים יהיו ביחס. שימו לב שאנו מגדירים יחס על קבוצת זוגות סדורים, ולכן האיברים ביחס הינם זוגות סדורים של זוגות סדורים. נגדיר ((x,y),(z,w))\in R \subseteq (\mathbb{Z}\times\mathbb{Z})\times(\mathbb{Z}\times\mathbb{Z}) אם מתקיים עבור השברים \frac{x}{y}=\frac{z}{w}. בקיצור נרשום ש ((x,y),(z,w))\in R \iff xw=zy.


הגדרה: תהי A קבוצה ויהי R יחס שקילויות על A. אזי קבוצת המנה A/R מוגדרת להיות קבוצת מחלקות השקילות של A לפי R.

הערה חשובה- שימו לב שזהו סימן זהה להפרש, אך זה אינו הפרש. מידי פעם מתמטיקאים עושים את זה - מגדירים שני דברים סותרים, זה נקרא "התעללות בסמנטיקה" (abuse of notation). על אף שזה נראה שהמטרה היא להתעלל יותר בסטודנטים מאשר בסמנטיקה, לעיתים נוח יותר להשתמש בפחות סימונים, כאשר אנו מבדילים ביניהם על פי ההקשר.

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

שאלה ממבחן

א. תהי A קבוצה לא ריקה ותהי \{R_i\}_{i\in I} משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי על I הינו יחס שקילויות על A.

ב. נסמן R_n=\{(x,y)\in\mathbb{Z}\times\mathbb{Z}:n|(x-y)\}. מהם R_1,R_2,R=\cap_{n\in\mathbb{N}}R_n? מהן קבוצות המנה \mathbb{Z}/R,\mathbb{Z}/R_1,\mathbb{Z}/R_2?

פתרון

א. רפלקסיביות: מאחר ו \forall a\in A\forall i\in I : (a,a)\in R_i נובע ש \forall a\in A: (a,a)\in R.


סימטריות: נניח (x,y)\in R לכן \forall i\in I:(x,y)\in R_i ולכן נובע מסמטריות היחסים ש \forall i\in I:(y,x)\in R_i ולכן (y,x)\in R.


טרנזיטיביות: ממש אותו דבר...



ב. R_1 הינו אוסף כל הזוגות הסדורים מעל השלמים, שכן אחד מחלק כל מספר ולכן כל הפרש.

R_2 הינו אוסף כל הזוגות בהם שני הצדדים זוגיים או שני הצדדים אי זוגיים, שכן ההפרש בינהם חייב להיות זוגי.

R הינו אוסף הזוגות שההפרש בינהם מתחלק בכל המספרים הטבעיים. רק הפרש אפס יכול להתחלק בכל מספר, ולכן R הינו אוסף הזוגות מהצורה (q,q) עבור q מספר שלם. (יחס השיוויון.)


\mathbb{Z}/R_1 הינו אוסף מחלקות השקילות של היחס המכיל את כל הזוגות. יש בו רק מחלקת שקילות אחת המכילה את כל המספרים השלמים.

\mathbb{Z}/R_2 מכיל שתי קבוצות, קבוצת הזוגיים וקבוצת האי זוגיים שכן בין כל הזוגיים יש את היחס, ובין כל האי זוגיים ולא בין לבין כמובן (הרי זה יחס שקילויות כפי שקל להוכיח).

\mathbb{Z}/R הינו אוסף כל הקבוצות המכילות איבר שלם בודד.

מקור: https://math-wiki.com/index.php?title=88-195_בדידה_לתיכוניסטים_תשעא/מערך_שיעור/שיעור_2&oldid=35991