Math-Wiki - תרומות המשתמש [he]

תרגול 10 תשעז

2018-02-07T11:00:46Z

תום: /* פתרון */

חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].

==יחסי שקילות==
הגדרה: תהא <math>A</math> קבוצה ו-<math>R</math> יחס עליה. <math>R</math> יקרא '''יחס שקילות''' (יח"ש) אם הוא
#רפלקסיבי
#סימטרי
#טרנזיטיבי

'''סימון מקובל:'''
אם <math>R</math> יחס שקילות מסמנים גם <math>x \sim y</math> עבור <math>(x,y)\in R</math>.

וכן נסמן <math>(A,\sim)</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 \exists a\in \mathbb{N}\cup \{0\}:x-y=a</math>

<math>xSy\iff \exists a\in 2\mathbb{Z}\cup 3\mathbb{Z}:x-y=a</math>.

<math>xTy\iff \exists a\in \mathbb{Z}:x-y=a</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>a=0</math> ואז <math>x-x=0=a</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</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>).

הגדרה:

יהא <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>.

'''משפט''': יהא <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>.

מסקנה:
תהא <math>A</math> קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על <math>A</math>}
<math>\leftrightarrow</math> {חלוקות של <math>A</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>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>? ומהי, מבחינה גיאומטרית, קבוצת המנה?

=====פתרון=====

מעגל עם רדיוס <math>1</math> מסביב לראשית. קבוצת המנה - אוסף המעגלים מסביב לראשית.

תרגול 8 תשעז

2017-12-05T17:04:44Z

תום: /* פתרון */

חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].

=יחסים=
==המכפלה הקרטזית==
הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות <math>A</math> ו-<math>B</math> הינה אוסף כל ה'''זוגות הסדורים''' - <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>n</math>-יה סדורה - כלומר <math>n</math> איברים מסודרים.

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

למתכנתים: זה מאוד דומה ללולאות for מקוננות.

===תרגיל===
הוכח שלכל קבוצות <math>A,B,C,D</math> מתקיים <math>(A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)</math>

====פתרון====
<math>(x,y)\in (A\times B)\cap (C\times D) \iff </math>

<math>(x,y)\in A\times B \land (x,y)\in C\times D \iff</math>

<math>(x\in A \and y\in B) \and (x\in C\and y\in D) \iff</math>

<math>(x\in A\and x\in C) \and (y\in B\and y\in D) \iff</math>

<math>(x,y)\in (A\cap C)\times (B\cap D)</math>

==יחסים כתת קבוצה של הזוגות הסדורים==
הגדרה: יהיו <math>A,B</math> קבוצות, <math>R\subseteq A\times B</math> אזי <math>R</math> יקרא יחס (בין <math>A</math> לבין <math>B</math>).
הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי <math>A</math> ל-<math>B</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>. מה מיוחד בזוגות אלה?

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

הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה <math>S=\{(1,2),(1,6),(2,0),(2,2)\}</math> היא יחס. גם <math>\varnothing</math> היא יחס, וגם <math>A\times B</math> הוא יחס.

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

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

הגדרה: בהינתן יחס <math>R\subseteq A\times B</math>, '''היחס ההפוך''' <math>R^{-1}\subseteq B\times A</math> הוא היחס המוגדר ע"י היפוך הזוגות הסדורים:
<math>R^{-1}=\{(b,a):aRb\}</math>

הגדרה: תהי קבוצה <math>A</math>. '''יחס הזהות''' על <math>A</math> הוא <math>R\subseteq A\times A</math> כך ש-<math>I_A=R=\{(a,a):a\in A\}</math>.

הגדרה: יהיו <math>A,B,C</math> קבוצות, ו-<math>R\subseteq A\times B, S\subseteq B\times C</math> '''יחס הכפל''' הוא היחס: <math>RS=\{(a,c)\in A\times C | \exists b\in B : (a,b)\in R \land (b,c)\in S\}</math>.

===תרגיל===
יהיו <math>A=\{1,2\}, B=\{3,4,5\}</math>. נגדיר את היחס: <math>R=\{(1,3),(2,4)\}</math>. בדוק האם:

א. <math>RR^{-1}=I_A</math>

ב. <math>R^{-1}R=I_B</math>

==תכונות של יחסים על קבוצה==
הגדרה: יחס <math>R</math> על קבוצה <math>A</math> פירושו <math>R\subseteq A\times A</math>.

תהי קבוצה <math>A</math> ויחס <math>R</math> עליה אזי:
#<math>R</math> נקרא '''רפלקסיבי''' אם כל איבר מקיים את היחס עם עצמו ( מתקיים <math>\forall a\in A:(a,a)\in R</math>).
#<math>R</math> נקרא '''סימטרי''' אם <math>aRb</math> גורר שגם <math>bRa</math> (מתקיים <math>\forall a,b\in A:[(a,b)\in R \rightarrow (b,a)\in R]</math>).
#<math>R</math> נקרא '''טרנזיטיבי''' אם יחס בין ראשון לשני (<math>aRb</math>), ויחס בין השני לשלישי (<math>bRc</math>) גורר יחס בין הראשון לשלישי (<math>aRc</math>). (מתקיים <math>\forall a,b,c\in A:[((a,b)\in R) \and ((b,c)\in R) \rightarrow ((a,c)\in R)]</math>).
#<math>R</math> נקרא '''אנטי סימטרי (חלש)''' אם <math>aRb</math> וגם <math>bRa</math> גורר כי <math>a=b</math> (מתקיים <math>\forall a,b\in A:[(a,b)\in R \and (b,a)\in R \rightarrow a=b]</math> ובאופן שקול: <math>\forall a\neq b\in A: \lnot (aRb\land bRa)</math>)

דוגמאות:
*יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
*יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
*יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
*יחס 'שיוויון מודולו <math>n</math>' הינו רפלקסיבי, סימטרי וטרנזיטיבי
*יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
*יחס '<math>a</math> מחלק את <math>b</math>' הינו רפלקסיבי וטרנזיטיבי
*יחס 'אדם <math>x</math> שמע על אדם <math>y</math>' הינו רפלקסיבי

'''הערה:''' יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמה: <math>A=\{ 1,2,3\} , R=\{ (1,1)\} , S=\{ (1,2),(2,1),(3,2)\}</math> ואז <math>R</math> גם וגם, ואילו <math>S</math> לא ולא.