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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏יחסי שקילות)
(←‏תרגיל)
 
(65 גרסאות ביניים של 8 משתמשים אינן מוצגות)
שורה 1: שורה 1:
 
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
 
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
  
−
=יחסים=
+
==מכפלה קרטזית==
 
הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות A וB הינה אוסף כל ה'''זוגות הסדורים''' - <math>A\times B = \{(a,b)|a\in A \and b\in B\}</math>. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים <math>(1,2),(2,1)</math> והאיבר הבא הינו זוג חוקי <math>(1,1)</math>.
 
הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות A וB הינה אוסף כל ה'''זוגות הסדורים''' - <math>A\times B = \{(a,b)|a\in A \and b\in B\}</math>. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים <math>(1,2),(2,1)</math> והאיבר הבא הינו זוג חוקי <math>(1,1)</math>.
  
שורה 11: שורה 11:
 
ניתן להגדיר זוגות סדורים באמצעות הגדרת הקבוצות בלבד, כפי שנראה בתרגיל הבא:
 
ניתן להגדיר זוגות סדורים באמצעות הגדרת הקבוצות בלבד, כפי שנראה בתרגיל הבא:
  
−
===תרגיל===
+
===תרגיל (בשיעורי הבית בד"כ)===
 
הוכח/הפרך:
 
הוכח/הפרך:
  
שורה 31: שורה 31:
  
 
לכן, ניתן להגדיר זוג סדור על ידי קבוצות בלבד (באופן דומה לכך שכל המתמטיקה פחות או יותר נבנת על קבוצות בלבד).
 
לכן, ניתן להגדיר זוג סדור על ידי קבוצות בלבד (באופן דומה לכך שכל המתמטיקה פחות או יותר נבנת על קבוצות בלבד).
−
 
  
 
===תרגיל===
 
===תרגיל===
−
הוכח שלכל קבוצות A,B,C מתקיים <math>A\times(B\cap C)=(A\times B)\cap(A\times C)</math>
+
הוכיחו או הפריכו:
 +
 
 +
א. לכל קבוצות A,B,C מתקיים <math>A\times(B\cap C)=(A\times B)\cap(A\times C)</math>
 +
 
 +
ב. לכל קבוצות <math>A,B,C,D</math> מתקיים: <math>(A\times B)\cup (C\times D)=(A\cup C)\times (B\cup D)</math>
  
 
====פתרון====
 
====פתרון====
−
<math>(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)]</math>
+
א. הוכחה: <math>(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 C)] \iff (x,y)\in[(A\times B)\cap(A\times C)]</math>
  
 +
ב. הפרכה: אפשר פשוט לקחת <math>A=\{1\},B=\{2\},C=\{3\},D=\{4\}</math>. אפשר גם לקחת <math>A=B=[0,1],C=D=[1,2]</math>, ולהראות את המלבנים המתאימים שיוצאים בשני הצדדים - זה אולי יותר ממחיש את המכפלה.
  
 
==יחסים כתת קבוצה של הזוגות הסדורים==
 
==יחסים כתת קבוצה של הזוגות הסדורים==
−
הגדרה: יהיו A,B קבוצות, <math>R\subseteq A\times B</math> אזי R יקרא יחס (בין A ל -B)
+
הגדרה: יהיו A,B קבוצות, <math>R\subseteq A\times B</math> יקרא יחס (מ A ל -B).
−
הרעיון שעומד בבסיסו של יחס הוא האעשרות "להשוות" בין איברי A ל B
+
הרעיון שעומד בבסיסו של יחס הוא האפשרות "לקשר" בין איברי A ל B.
 
דוגמא:  <math>A=\{1,2,3\},B=\{0,2,6\}</math> ונביט בתת הקבוצה <math>R\subseteq A\times B</math> הבאה: <math>R=\{(1,2),(1,6),(2,2),(2,6),(3,6)\}</math>. מה מיוחד בזוגות אלה?
 
דוגמא:  <math>A=\{1,2,3\},B=\{0,2,6\}</math> ונביט בתת הקבוצה <math>R\subseteq A\times B</math> הבאה: <math>R=\{(1,2),(1,6),(2,2),(2,6),(3,6)\}</math>. מה מיוחד בזוגות אלה?
  
 
זוגות אלה הינן כל זוגות האיברים (a,b) כך ש <math>a\leq b</math>. (כלומר הגדרנו את היחס המייצג  "קטן שווה")  
 
זוגות אלה הינן כל זוגות האיברים (a,b) כך ש <math>a\leq b</math>. (כלומר הגדרנו את היחס המייצג  "קטן שווה")  
  
−
הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה <math>S=\{(1,2),(1,6),(2,0),(2,2))\}</math> היא יחס.
+
הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה <math>S=\{(1,2),(1,6),(2,0),(2,2)\}</math> היא יחס. גם <math>\emptyset</math> היא יחס. וגם <math>A\times B</math> הוא יחס.
  
−
סימון: אם זוג מסוים נמצא בקבוצת היחס R נהוג לסמן aRb. (אם יש משמעות ליחס כמו לעיל ניתן גם לסמן פשוט <math>a\leq b</math>.
+
סימון: אם זוג מסוים, (a,b), נמצא בקבוצת היחס R נהוג לסמן aRb. (אם יש משמעות ליחס כמו לעיל ניתן גם לסמן פשוט <math>a\leq b</math>.
  
  
שורה 65: שורה 69:
  
 
דוגמאות:
 
דוגמאות:
−
*יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
+
*יחס 'שיוויון' הינו רפלקסיבי, סימטרי, טרנזיטיבי ואנטי-סימטרי.
−
*יחס 'קטן שווה' הינו רפלקסיבי וטרנזיטיבי
+
*יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי.
−
*יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
+
*יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי.
−
*יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי
+
*יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי.
−
*יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
+
*יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי.
−
*יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי
+
*יחס 'a מחלק את b' (על הטבעיים) הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי.
−
*יחס 'אדם x שמע על אדם y' הינו רפלקסיבי
+
*יחס 'a מחלק את b' (על השלמים) הינו רפלקסיבי, טרנזיטיבי.
 +
*יחס 'אדם x שמע על אדם y' הינו רפלקסיבי.
 +
==== תרגיל (חשוב)====
 +
מצאו יחסים על הקבוצה <math>\{1,2,3\}</math> עם התכונות הבאות:
 +
* יחס רפלקסיבי
 +
*יחס סימטרי
 +
*יחס אנטי סימטרי
 +
*יחס טרנזיטיבי
 +
*יחס סימטרי ואנטי סימטרי
 +
*יחס טרנזיטיבי וסימטרי
 +
* יחס רפלקסיבי, סימטרי ולא טרנזיטיבי
 +
*עוד לבקשת הקהל
  
−
===יחסי שקילות===
+
==== תרגיל ====
−
הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא
+
לכל <math>x</math> ממשי, נגדיר את הערך התחתון שלו <math>\lfloor x\rfloor</math> להיות המספר השלם הגדול ביותר <math>z</math> המקיים <math>z\leq x</math>. למשל <math>\lfloor2.3\rfloor=2</math> למשל <math>\lfloor\pi\rfloor=3</math> למשל <math>\lfloor-2.3\rfloor=-3</math>.
 +
 
 +
נגדיר <math>R=\left\{ \left(x,\lfloor x\rfloor\right)\,\mid x\in\mathbb{R}\right\}</math>  שהוא יחס על <math>\mathbb{R}</math>. קבעו האם הוא רפלקסיבי/סימטרי/אנטי-סימטרי/טרנזיטיבי.
 +
 
 +
==יחסי שקילות==
 +
הגדרה: תהא A קבוצה ו-R יחס עליה. R יקרא יחס שקילות אם הוא
 
#רפלקסיבי
 
#רפלקסיבי
 
#סימטרי
 
#סימטרי
שורה 96: שורה 116:
 
הגדרה: תהא A קבוצה. '''חלוקה''' של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות <math>\{A_i\}_{i\in I}</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>\cup _{i\in I} A_i =A </math> כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה   
 
* הן '''זרות''' זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק (<math>\forall i\not= j\in I : A_i\cap A_j = \phi </math>)
 
* הן '''זרות''' זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק (<math>\forall i\not= j\in I : A_i\cap A_j = \phi </math>)
שורה 102: שורה 123:
  
  
−
דוגמא נוספת:
+
'''הערה:''' אפשר להציג את היחס על <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>
  
−
נגדיר יחס שקילות R על <math>\mathbb{Z}</math> ע"י  <math>3|(x-y) \Leftrightarrow xRy</math>
+
====תרגיל====
 +
נגדיר על <math>\mathbb{R}</math> ארבעה יחסים <math>Q,R,S,T</math> באופן הבא: לכל <math>x,y\in \mathbb{R}</math>:
  
−
טענה: R אכן יחס שקילות
+
<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>.
  
−
1. רפלקסיביות - נניח <math>\forall x\in \mathbb{Z}:3|0=x-x</math> לכן <math>xRx</math>  
+
<math>T</math> כן יחס שקילות:
  
−
2. סימטריות - נניח <math>(x,y)\in R</math> אזי <math>3|(x-y)</math> ולכן גם <math>3|(y-x)=-(x-y)</math>
+
רפלקסיביות: יהי <math>x\in \mathbb{R}</math>, אז <math>x-x=0\in \mathbb{Z}</math>.
  
−
3. טרנזיטיביות - נניח <math>[(x,y)\in R] \and [(y,z)\in R]</math> אזי <math>3|(x-y)\and 3|(y-z) </math> 
+
סימטריות: <math>xTy\Rightarrow \exists a\in \mathbb{Z} :x-y=a \Rightarrow y-x=-a\in \mathbb{Z} \Rightarrow yTx</math>.
−
ולכן גם <math>3|(z-x)=(z-y)+(y-x)</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  אזי
+
יהא R יחס שקילות על A  אזי
  
 
# לכל <math>x\in A</math> מוגדרת '''מחלקת השקילות של x ''' להיות  <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} </math>
 
# לכל <math>x\in A</math> מוגדרת '''מחלקת השקילות של x ''' להיות  <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} </math>
שורה 126: שורה 166:
  
  
−
למשל, בדוגמא הראשונה <math>A_1,A_2,A_3</math> הן מחלקות השקילות. קבוצת המנה היא <math>R/A=\{A_1,A_2,A_3\}</math>
+
למשל, בדוגמא הראשונה <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{Z}/R= \{[0]_R,[1]_R [3]_R\}</math> (כלומר כל השאריות האפשריות בחלוקה ב-3).
+
  
  
שורה 143: שורה 180:
  
 
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
 
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
−
 
+
====תרגיל====
−
===תרגיל===
+
כמה יחסי שקילות שונים יש על <math>A=\{1,2,3\}</math>? פתרון: נספור לפי חלוקות ונגלה כי התשובה היא 5.
 +
====תרגיל====
 
תהי <math>A=\{1,2,3\}</math> קבוצה. השלם את היחסים הבאים מעליה על מנת שיקיימו את התכונות הנדרשות בשאלה (השלם - כלומר הוסף זוגות סדורים '''הכרחיים'''):
 
תהי <math>A=\{1,2,3\}</math> קבוצה. השלם את היחסים הבאים מעליה על מנת שיקיימו את התכונות הנדרשות בשאלה (השלם - כלומר הוסף זוגות סדורים '''הכרחיים'''):
−
*השלם את <math>R=\{(1,2)\}</math> להיות יחס סימטרי וטרנזיטיבי. האם אחרי ההשלמה קיבלת יחס שקילויות?
+
*השלם את <math>R=\{(1,2)\}</math> להיות יחס סימטרי וטרנזיטיבי. האם אחרי ההשלמה קיבלת יחס שקילות?
−
*השלם את הקבוצה הריקה ליחס שקילויות. איך קוראים ליחס שקיבלת? מהן מחלקות השקילות?
+
*השלם את הקבוצה הריקה ליחס שקילות. איך קוראים ליחס שקיבלת? מהן מחלקות השקילות?
  
−
====פתרון====
+
=====פתרון=====
−
1. <math>R=\{(1,2),(2,1),(1,1),(2,2)\}</math> זה אינו יחס שקילויות מכיוון שאינו רפלקסיבי - (3,3) חסר.
+
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].
 
2. <math>R=\{(1,1),(2,2),(3,3)\}</math>. זהו יחס השיוויון, מחלקות השקילות שלו הינן [1],[2],[3].
  
−
===דוגמא חשובה - הגדרת הרציונאליים===
+
====תרגיל====
−
נביט בקבוצת המכפלה הקרטזית של השלמים עם עצמם <math>\mathbb{Z}\times\mathbb{Z}</math>. נסתכל על ההתאמה <math>(a,b)\leftrightarrow\frac{a}{b}</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\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>\frac{2}{6}=\frac{1}{3}</math> ואילו <math>(2,6)\neq (1,3)</math>. כלומר, המכפלה הקרטזית מכילה חזרות מיותרות לעומת הרציונאליים.
  
−
נרצה איפוא, להגדיר יחס שקילויות על הזוגות הסדורים של מספרים שלמים כך שכל שני שברים שקולים יהיו ביחס. שימו לב שאנו מגדירים יחס על קבוצת זוגות סדורים, ולכן האיברים ביחס הינם זוגות סדורים של זוגות סדורים. נגדיר <math>((x,y),(z,w))\in R \subseteq (\mathbb{Z}\times\mathbb{Z})\times(\mathbb{Z}\times\mathbb{Z})</math> אם מתקיים עבור השברים <math>\frac{x}{y}=\frac{z}{w}</math>. בקיצור נרשום ש <math>((x,y),(z,w))\in R \iff xw=zy</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>)
  
−
הגדרה: תהי A קבוצה ויהי R יחס שקילויות על A. אזי '''קבוצת המנה''' <math>A/R</math> מוגדרת להיות קבוצת מחלקות השקילות של A לפי R.  
+
כייון ש <math> w \not=0 </math> נקבל כי <math>x=\frac{zy}{w}</math> ולכן <math>xb=\frac{zby}{w}=\frac{awy}{w}=ay</math> כנדרש.
  
−
הערה חשובה- שימו לב שזהו סימן זהה להפרש, אך זה אינו הפרש. מידי פעם מתמטיקאים עושים את זה - מגדירים שני דברים סותרים, זה נקרא "התעללות בסמנטיקה" (abuse of notation). על אף שזה נראה שהמטרה היא להתעלל יותר בסטודנטים מאשר בסמנטיקה, לעיתים נוח יותר להשתמש בפחות סימונים, כאשר אנו מבדילים ביניהם על פי ההקשר.
+
ומי שלא רוצה להשתמש בחילוק (אבל כן מתיר לצמצם משיוויון איבר שנמצא בשני הצדדים, כי ניתן להשתכנע בכך מהגדרת כפל על טבעיים): נשים לב שמתקיים: <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. הוכיחו כי החיתוך הכללי על I הינו יחס שקילויות על A.
+
א. תהי 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>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>?
שורה 197: שורה 280:
  
 
<math>\mathbb{Z}/R</math> הינו אוסף כל הקבוצות המכילות איבר שלם בודד.
 
<math>\mathbb{Z}/R</math> הינו אוסף כל הקבוצות המכילות איבר שלם בודד.
 +
 +
==תירגול נוסף==
 +
=== תרגיל ===
 +
היחסים הבאים הם יחסים על קבוצת הממשיים. קבעו האם היחסים הבאים הם רפלקסיבים? האם הם סימטרים? האם הם אנטי-סימטריים? האם הם טרנזיטיבים?
 +
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=0\right\} </math>
 +
* <math>\left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=1\right\} </math>
 +
 +
==== תרגיל ====
 +
עבור כל אחד מהיחסים מתרגיל קודם. קבעו האם הוא יחס סדר? האם הוא יחס שקילות? האם הוא חלוקה של הממשיים?
 +
 +
עבור כל אחד מיחסי השקילות של סעיף קודם - מצאו את מחלקת השקילות של האיברים <math>0,\pi, 100</math>
 +
 +
עבור כל אחד מיחסי השקילות של סעיף קודם - תארו את קבוצת המנה.
 +
 +
=== תרגיל ===
 +
היחסים הבאים הם יחסים על קבוצת הטבעיים. קבעו האם היחסים הבאים הם רפלקסיבים? האם הם סימטרים? האם הם אנטי-סימטריים? האם הם רפלקסיבים?
 +
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=1\right\} </math>
 +
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=2\right\} </math>
 +
* <math>\left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=3\right\} </math>
 +
 +
=== תרגיל ===
 +
ראינו שניתן להגדיר את <math>\mathbb{Q}</math> כקבוצת מנה של יחס שקילות. הוכיחו כי ניתן להגדיר חיבור וכפל של מספר רציונאליים כמו שאנחנו רגילים.
 +
 +
=== תרגיל ===
 +
מצאו קבוצה ויחס שקילות כך שניתן לזהות את המספרים השלמים <math>\mathbb{Z}</math> עם קבוצת המנה המתקבלת (התבססו על קיומה של קבוצת הטבעיים בלבד).
 +
 +
הוכיחו כי ניתן להגדיר חיבור וכפל של מספר שלמים כמו שאנחנו רגילים.
 +
 +
=== תרגיל ===
 +
מצאו קבוצה ויחס שקילות כך שניתן לזהות את המספרים המשיים <math>\mathbb{R}</math> עם קבוצת המנה המתקבלת (התבססו על קיומה של קבוצת הרציונאליים בלבד).
 +
 +
הוכיחו כי ניתן להגדיר חיבור וכפל של מספר שלמים כמו שאנחנו רגילים.
 +
 +
 +
=== תרגיל ===
 +
עבור היחס מודלו <math>n</math> על קבוצת השלמים <math>\mathbb{Z}</math>, נסמן את קבוצת המנה ב <math>\mathbb{Z}_n</math>
 +
 +
הוכיחו כי ניתן להגדיר חיבור וכפל של איברים ב <math>\mathbb{Z}_n</math> ע"י <math>[a]+[b]=[a+b], [a][b]=[ab]</math>. חיבור זה נקרא חיבור מודלו n וכפל זה נקראה כפל מודלו n.
 +
 +
===תרגיל===
 +
 +
על <math>\mathbb{R}\times \mathbb{R}</math> נגדיר את היחסים הבאים: (היחסים יסומנו ב <math>\sim</math>)
 +
 +
*<math>(x_1,y_1)\sim (x_2,y_2)\iff x_1^2+y_1=x_2^2+y_2</math>.
 +
*<math>(x_1,y_1)\sim (x_2,y_2)\iff x_1=x_2</math>.
 +
*<math>(x_1,y_1)\sim (x_2,y_2)\iff y_1=y_2</math>.
 +
*<math>(x_1,y_1)\sim (x_2,y_2)\iff |x_1|=|x_2|</math>.
 +
*<math>(x_1,y_1)\sim (x_2,y_2)\iff |y_1|=|y_2|</math>.
 +
*<math>(x_1,y_1)\sim (x_2,y_2)\iff |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=x_2^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>(x_1,y_1)\sim (x_2,y_2)\iff 5x_1^2-y_1=5x_2^2-y_2</math>.
 +
 +
הוכיחו שאלו יחס שקילות. מהי, מבחינה גיאומטרית מחלקת השקילות של <math>(0,1)</math>? ומהי, מבחינה גיאומטרית, קבוצת המנה?
 +
 +
=== תרגיל ===
 +
תהא <math>X</math> קבוצה.  היחסים הבאים הם יחסים על קבוצת החזקה <math>P(X)</math>. קבעו האם היחסים הבאים הם רפלקסיבים? האם הם סימטרים? האם הם אנטי-סימטריים? האם הם טרנזיטיביים?
 +
 +
* <math>\left\{ \left(A,B\right)\,|\, A=B\right\} </math>
 +
* <math>\left\{ \left(A,B\right)\,|\, A\subseteq B\right\} </math>
 +
* <math>\left\{ \left(A,B\right)\,|\, A\cap B=B\right\} </math>
 +
* <math>\left\{ \left(A,B\right)\,|\, A\cap B=\emptyset\right\} </math>
 +
* <math>\left\{ \left(A,B\right)\,|\, A^c=B\right\} </math>
 +
 +
 +
 +
==== תרגיל ====
 +
בכל אחד מהיחסים שהופיעו קודם, קבעו האם הוא יחס שקילות. במידה והוא יחס שקילות, מצאו את החלוקה שהוא משרה.

גרסה אחרונה מ־12:29, 16 בספטמבר 2022

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

מכפלה קרטזית

הגדרה: המכפלה הקרטזית של שתי קבוצות 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)

ב. לכל קבוצות A,B,C,D מתקיים: (A\times B)\cup (C\times D)=(A\cup C)\times (B\cup D)

פתרון

א. הוכחה: (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 C)] \iff (x,y)\in[(A\times B)\cap(A\times C)]

ב. הפרכה: אפשר פשוט לקחת A=\{1\},B=\{2\},C=\{3\},D=\{4\}. אפשר גם לקחת A=B=[0,1],C=D=[1,2], ולהראות את המלבנים המתאימים שיוצאים בשני הצדדים - זה אולי יותר ממחיש את המכפלה.

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

הגדרה: יהיו A,B קבוצות, R\subseteq A\times B יקרא יחס (מ 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)\} היא יחס. גם \emptyset היא יחס. וגם A\times B הוא יחס.

סימון: אם זוג מסוים, (a,b), נמצא בקבוצת היחס 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' (על הטבעיים) הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי.
  • יחס 'a מחלק את b' (על השלמים) הינו רפלקסיבי, טרנזיטיבי.
  • יחס 'אדם x שמע על אדם y' הינו רפלקסיבי.

תרגיל (חשוב)

מצאו יחסים על הקבוצה \{1,2,3\} עם התכונות הבאות:

  • יחס רפלקסיבי
  • יחס סימטרי
  • יחס אנטי סימטרי
  • יחס טרנזיטיבי
  • יחס סימטרי ואנטי סימטרי
  • יחס טרנזיטיבי וסימטרי
  • יחס רפלקסיבי, סימטרי ולא טרנזיטיבי
  • עוד לבקשת הקהל

תרגיל

לכל x ממשי, נגדיר את הערך התחתון שלו \lfloor x\rfloor להיות המספר השלם הגדול ביותר z המקיים z\leq x. למשל \lfloor2.3\rfloor=2 למשל \lfloor\pi\rfloor=3 למשל \lfloor-2.3\rfloor=-3.

נגדיר R=\left\{ \left(x,\lfloor x\rfloor\right)\,\mid x\in\mathbb{R}\right\} שהוא יחס על \mathbb{R}. קבעו האם הוא רפלקסיבי/סימטרי/אנטי-סימטרי/טרנזיטיבי.

יחסי שקילות

הגדרה: תהא 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} כך ש:

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

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


הערה: אפשר להציג את היחס על P(X) שמוגדר ע"י A\sim B\iff A\cap S=B\cap S (כאשר S ת"ק קבועה), אם כי זה נעשה בשיעורי הבית. מוזמנים לקחת קבוצות S,X קונקרטיות ולתאר בצורה מדויקת איך היחס נראה ("איך היחס נראה" זה לא שאלה מוגדרת היטב - הכוונה שתוודאו שאתם יודעים להסביר לעצמכם מה הולך שמה). בנוסף, חשבו מה קורה ביחסים:

  1. A\sim B\iff A\cup S=B\cup S
  2. A\sim B\iff A\triangle S=B\triangle S

תרגיל

נגדיר על \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} .

מחלקות שקילות וקבוצת המנה

הגדרה:

יהא 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 הן מחלקות השקילות. קבוצת המנה היא A/R=\{A_1,A_2,A_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\}? פתרון: נספור לפי חלוקות ונגלה כי התשובה היא 5.

תרגיל

תהי 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].

תרגיל

ראינו לעיל יחס 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\neq y. בה"כ 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 מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית (כלומר: קבוצה של קבוצות של זוגות סדורים שהם הנק' על כל מעגל לפי הרדיוס שלו).

תרגיל

תהא A קבוצה ותהא S\subseteq A ת"ק שלה. נגדיר יחס \sim על P(A) ע"י הכלל B_1\sim B_2 \iff B_1 \cup S=B_2\cup S

  • הוכיחו כי זהו יחס שקילות.
  • עבור S=\{1,7,9,10\},A=\{1,2,\dots 10\} מצאו את מספר האיברים ב P(A)/\sim
פתרון
  • יש לבדוק פשוט שהתכונות של יחס שקילות מתקיימות לפי הגדרת היחס הנתון.
  • נשים לב ששתי קבוצות ב-(P(A שקולות זו לזו אם ורק אם הן נבדלות זו מזו רק באיברים השייכים ל-S (אפשר להוכיח), כלומר: אם ההפרש הסימטרי שלהן מוכל ב-S. לכן, אם אנו רוצים לספור מחלקות שקילות (שונות), עלינו לספור כמה אפשרויות יש לחלק של ההפרש הסימטרי שאינו מוכל ב-S (החלק שמוכל אינו משפיע). כיוון שחלק זה יכול להיות כל תת קבוצה של המשלים של S (ביחס ל-A), וכיוון שבמשלים זה יש 6 איברים, נקבל שישנן 6^2 אפשרויות, ולכן זהו מספר מחלקות השקילות, כלומר: גודל קבוצת המנה.

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

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

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

נרצה איפוא, להגדיר יחס שקילות על הזוגות הסדורים של מספרים שלמים כך שכל שני שברים שקולים יהיו ביחס. שימו לב שאנו מגדירים יחס על קבוצת זוגות סדורים, ולכן האיברים ביחס הינם זוגות סדורים של זוגות סדורים. נגדיר R על \mathbb{Z}\times \mathbb{N} ע"י

(x,y)R(z,w) \iff xw=zy (כלומר אם מתקיים עבור השברים \frac{x}{y}=\frac{z}{w})

נוכיח רק טרנזיטיביות: נניח (x,y)R(z,w), (z,w)R(a,b) אזי xw=zy, zb=aw (צ"ל xb=ay )

כייון ש w \not=0 נקבל כי x=\frac{zy}{w} ולכן xb=\frac{zby}{w}=\frac{awy}{w}=ay כנדרש.

ומי שלא רוצה להשתמש בחילוק (אבל כן מתיר לצמצם משיוויון איבר שנמצא בשני הצדדים, כי ניתן להשתכנע בכך מהגדרת כפל על טבעיים): נשים לב שמתקיים: xwb=zyb=yaw, ולכן נקבל xb=ay כנדרש.

מסקנה: הרציונאלים הם קבוצת המנה של <\mathbb{Z}\times \mathbb{N} והיחס שהגדרנו לעיל. למעשה, מאחורי כל שבר עומדת הקבוצה האינסופית של כל השברים השקולים לו, ופשוט אנחנו בוחרים לייצג קבוצה זו על ידי אחד השברים שבה באופן שרירותי (או באופן מסוים - בחירת השבר המצומצם).

שאלה ממבחן

א. תהי A קבוצה לא ריקה ותהי \{R_i\}_{i\in I} משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי R=\cap_{i\in I}R_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 הינו אוסף כל הקבוצות המכילות איבר שלם בודד.

תירגול נוסף

תרגיל

היחסים הבאים הם יחסים על קבוצת הממשיים. קבעו האם היחסים הבאים הם רפלקסיבים? האם הם סימטרים? האם הם אנטי-סימטריים? האם הם טרנזיטיבים?

  • \left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=0\right\}
  • \left\{ \left(x,y\right)\in\mathbb{R\times R}\,|\,x+y=1\right\}

תרגיל

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

עבור כל אחד מיחסי השקילות של סעיף קודם - מצאו את מחלקת השקילות של האיברים 0,\pi, 100

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

תרגיל

היחסים הבאים הם יחסים על קבוצת הטבעיים. קבעו האם היחסים הבאים הם רפלקסיבים? האם הם סימטרים? האם הם אנטי-סימטריים? האם הם רפלקסיבים?

  • \left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=1\right\}
  • \left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=2\right\}
  • \left\{ \left(x,y\right)\in\mathbb{N\times N}\,|\,x+y=3\right\}

תרגיל

ראינו שניתן להגדיר את \mathbb{Q} כקבוצת מנה של יחס שקילות. הוכיחו כי ניתן להגדיר חיבור וכפל של מספר רציונאליים כמו שאנחנו רגילים.

תרגיל

מצאו קבוצה ויחס שקילות כך שניתן לזהות את המספרים השלמים \mathbb{Z} עם קבוצת המנה המתקבלת (התבססו על קיומה של קבוצת הטבעיים בלבד).

הוכיחו כי ניתן להגדיר חיבור וכפל של מספר שלמים כמו שאנחנו רגילים.

תרגיל

מצאו קבוצה ויחס שקילות כך שניתן לזהות את המספרים המשיים \mathbb{R} עם קבוצת המנה המתקבלת (התבססו על קיומה של קבוצת הרציונאליים בלבד).

הוכיחו כי ניתן להגדיר חיבור וכפל של מספר שלמים כמו שאנחנו רגילים.


תרגיל

עבור היחס מודלו n על קבוצת השלמים \mathbb{Z}, נסמן את קבוצת המנה ב \mathbb{Z}_n

הוכיחו כי ניתן להגדיר חיבור וכפל של איברים ב \mathbb{Z}_n ע"י [a]+[b]=[a+b], [a][b]=[ab]. חיבור זה נקרא חיבור מודלו n וכפל זה נקראה כפל מודלו n.

תרגיל

על \mathbb{R}\times \mathbb{R} נגדיר את היחסים הבאים: (היחסים יסומנו ב \sim)

  • (x_1,y_1)\sim (x_2,y_2)\iff x_1^2+y_1=x_2^2+y_2.
  • (x_1,y_1)\sim (x_2,y_2)\iff x_1=x_2.
  • (x_1,y_1)\sim (x_2,y_2)\iff y_1=y_2.
  • (x_1,y_1)\sim (x_2,y_2)\iff |x_1|=|x_2|.
  • (x_1,y_1)\sim (x_2,y_2)\iff |y_1|=|y_2|.
  • (x_1,y_1)\sim (x_2,y_2)\iff |x_1|+|y_1|=|x_2|+|y_2|.
  • (x_1,y_1)\sim (x_2,y_2)\iff x_1^2-y_1=x_2^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.
  • (x_1,y_1)\sim (x_2,y_2)\iff 5x_1^2-y_1=5x_2^2-y_2.

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

תרגיל

תהא X קבוצה. היחסים הבאים הם יחסים על קבוצת החזקה P(X). קבעו האם היחסים הבאים הם רפלקסיבים? האם הם סימטרים? האם הם אנטי-סימטריים? האם הם טרנזיטיביים?

  • \left\{ \left(A,B\right)\,|\, A=B\right\}
  • \left\{ \left(A,B\right)\,|\, A\subseteq B\right\}
  • \left\{ \left(A,B\right)\,|\, A\cap B=B\right\}
  • \left\{ \left(A,B\right)\,|\, A\cap B=\emptyset\right\}
  • \left\{ \left(A,B\right)\,|\, A^c=B\right\}


תרגיל

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

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