שינויים
/* תרגיל */
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
=יחסים=מכפלה קרטזית==
הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות 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>.
ניתן להגדיר זוגות סדורים באמצעות הגדרת הקבוצות בלבד, כפי שנראה בתרגיל הבא:
===תרגיל(בשיעורי הבית בד"כ)===
הוכח/הפרך:
לכן, ניתן להגדיר זוג סדור על ידי קבוצות בלבד (באופן דומה לכך שכל המתמטיקה פחות או יותר נבנת על קבוצות בלבד).
===תרגיל===
====פתרון====
א. הוכחה: <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>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>. מה מיוחד בזוגות אלה?
דוגמאות:
*יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי, טרנזיטיבי ואנטי-סימטרי.*יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי.*יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי.*יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי.*יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי.*יחס 'a מחלק את b' (על הטבעיים) הינו רפלקסיבי וטרנזיטיבי, טרנזיטיבי ואנטי-סימטרי.*יחס 'a מחלק את b' (על השלמים) הינו רפלקסיבי, טרנזיטיבי.*יחס 'אדם x שמע על אדם y' הינו רפלקסיבי.==== תרגיל (חשוב)====מצאו יחסים על הקבוצה <math>\{1,2,3\}</math> עם התכונות הבאות:* יחס רפלקסיבי*יחס סימטרי*יחס אנטי סימטרי*יחס טרנזיטיבי*יחס סימטרי ואנטי סימטרי*יחס טרנזיטיבי וסימטרי* יחס רפלקסיבי, סימטרי ולא טרנזיטיבי*עוד לבקשת הקהל
==== תרגיל ====לכל <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 יקרה יקרא יחס שקילות אם הוא
#רפלקסיבי
#סימטרי
====תרגיל====נגדיר יחס שקילות R על <math>\mathbb{ZR}</math> ע"י ארבעה יחסים <math>Q,R,S,T</math> באופן הבא: לכל <math>3|(x-,y) \Leftrightarrow xRyin \mathbb{R}</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>.
===מחלקות שקילות וקבוצת המנה===
הגדרה:
למשל, בדוגמא הראשונה <math>A_1,A_2,A_3</math> הן מחלקות השקילות. קבוצת המנה היא <math>A/R=\{A_1,A_2,A_3\}</math>
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
====תרגיל====כמה יחסי שקילות שונים יש על <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> 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> והיחס שהגדרנו לעיל. למעשה, מאחורי כל שבר עומדת הקבוצה האינסופית של כל השברים השקולים לו, ופשוט אנחנו בוחרים לייצג קבוצה זו על ידי אחד השברים שבה באופן שרירותי (או באופן מסוים - בחירת השבר המצומצם).
<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>
==== תרגיל ====
בכל אחד מהיחסים שהופיעו קודם, קבעו האם הוא יחס שקילות. במידה והוא יחס שקילות, מצאו את החלוקה שהוא משרה.
