הבדלים בין גרסאות בדף "תרגול 11 תשעז"

גרסה מ־07:43, 22 בדצמבר 2017

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

תוכן עניינים

1 המשך יחסי שקילות
- 1.1 תרגיל
  - 1.1.1 פיתרון
- 1.2 שאלה ממבחן
  - 1.2.1 פתרון

המשך יחסי שקילות

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

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

הגדרה:

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

לכל $x\in A$ מוגדרת מחלקת השקילות של x להיות $\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\}$
קבוצת המנה מוגדרת $A/R := \{ [x]_R | x\in A\}$

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

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

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

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

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

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

תרגיל

תהא $B\subseteq A$ קבוצה ותת קבוצה. נגדיר יחס $\sim \subseteq P(A)\times P(A)$ ע"י $C\sim D\iff C\cap B=D\cap B$ . הוכיחו:

א. זהו יחס שקילות.

ב. לכל $X\subseteq A$ קיימת $C\subseteq B$ כך ש $[X]_R=[C]_R$ .

ג. אם $C,D\subseteq B$ שונות, אז $[C]\neq [D]$ .

פיתרון

א. רפלקסיביות: כמובן ש- $\forall C\subseteq A:C\cap B=C\cap B$ , ולכן $C\sim C$ .

סימטריות: נניח $C\sim D$ אזי $C\cap B=D\cap B\iff D\cap B=C\cap B$ , ולכן $D\sim C$ .

טרנזיטיביות: נניח $C\sim D\land D\sim E$ אזי $C\cap B=D\cap B\land D\cap B=E\cap B$ ומטרנזיטיביות יחס השיוויון נקבל הדרוש.

ב. יהי $X\subseteq A$ נשים לב שמתקיים $(X\cap B)\cap B=X\cap B$ ולכן $[X]_R=[X\cap B]_R$ , ובנוסף מתקיים $X\cap B\subseteq B$ ולכן נוכל לבחור $C=X\cap B$ .

ג. תהיינה $C,D\subseteq B$ שונות. לכן קיים (בה"כ) $x\in C\smallsetminus D$ וכמובן $x\in B$ , ולכן נקבל $x\in C\cap B\land x\notin D\cap B$ כלומר $C\cap B\neq D\cap B$ ולכן $[C]\neq [D]$ .

שאלה ממבחן

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

טרנזיטיביות: נניח $(x,y),(y,z)\in \mathbb R$ אזי $\forall i\in I:(x,y),(y,z)\in R_i$ , וכיון שהוא יחס שקילות אז נובע $\forall i\in I:(x,z)\in R_i$ , ולפי הגדרת החיתוך הכללי נקבל $(x,z)\in R$

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

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

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

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

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

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

@@ שורה 55: / שורה 55: @@
 ===שאלה ממבחן===
-תהי A קבוצה לא ריקה ותהי <math>\{R_i\}_{i\in I}</math> משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי  <math>R=\cap_{i\in I}R_i</math> הינו יחס שקילויות על 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>\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>\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>(x,y),(y,z)\in \mathbb R</math> אזי <math>\forall i\in I:(x,y),(y,z)\in R_i</math>, וכיון שהוא יחס שקילות אז נובע <math>\forall i\in I:(x,z)\in R_i</math>, ולפי הגדרת החיתוך הכללי נקבל <math>(x,z)\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> הינו אוסף כל הקבוצות המכילות איבר שלם בודד.

הבדלים בין גרסאות בדף "תרגול 11 תשעז"

גרסה מ־07:43, 22 בדצמבר 2017

תוכן עניינים

המשך יחסי שקילות

תרגיל

פיתרון

שאלה ממבחן

פתרון

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים