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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏תרגיל)
שורה 35: שורה 35:
  
 
===תרגיל===
 
===תרגיל===
−
תהא <math>B\subseteq A</math> קבוצה ותת קבוצה. נגדיר יחס <math>\sim \subseteq P(A)\times P(A)</math> ע"י <math>C\sim D\iff C\cap B=D\cap B</math>.
+
תהא <math>B\subseteq A</math> קבוצה ותת קבוצה. נגדיר יחס <math>\sim \subseteq P(A)\times P(A)</math> ע"י <math>C\sim D\iff C\cap B=D\cap B</math>. הוכיחו:
  
−
א. הוכח שזהו יחס שקילות.
+
א. זהו יחס שקילות.
  
−
ב. מצא את <math>|P(A)/\sim |</math>
+
ב. לכל <math>X\subseteq A</math> קיימת <math>C\subseteq B</math> כך ש <math>[X]_R=[C]_R</math>.
 +
 
 +
ג. אם <math>C,D\subseteq B</math> שונות, אז <math>[C]\neq [D]</math>.
  
 
====פיתרון====
 
====פיתרון====
שורה 48: שורה 50:
 
טרנזיטיביות: נניח <math>C\sim D\land D\sim E</math> אזי <math>C\cap B=D\cap B\land D\cap B=E\cap B</math> ומטרנזיטיביות יחס השיוויון נקבל הדרוש.
 
טרנזיטיביות: נניח <math>C\sim D\land D\sim E</math> אזי <math>C\cap B=D\cap B\land D\cap B=E\cap B</math> ומטרנזיטיביות יחס השיוויון נקבל הדרוש.
  
−
ב. פיתרון: <math>|P(A)/\sim |=|P(B)|=2^{|B|}</math>. הוכחה:
+
ב. יהי <math>X\subseteq A</math> נשים לב שמתקיים <math>(X\cap B)\cap B=X\cap B</math> ולכן <math>[X]_R=[X\cap B]_R</math>, ובנוסף מתקיים <math>X\cap B\subseteq B</math> ולכן נוכל לבחור <math>C=X\cap B</math>.
−
 
+
−
מחד, לכל מחלקת שקילות <math>[C]\in P(A)/\sim</math> נוכל לבחור תת קבוצה של <math>B</math> כנציג: כי <math>\forall C\in P(A):[C]=\{ D\subseteq A|C\cap B=D\cap B\}</math>, וכיון ש- <math>(C\cap B)\cap B=C\cap B</math> נקבל <math>[C]=[C\cap B]</math>, ו-<math>C\cap B\subseteq B</math> הוא הנציג שחיפשנו.
+
−
 
+
−
מצד שני, כל תת קבוצה של <math>B</math> מגדירה מחלקת שקילות שונה, כי אם <math>C\neq D\subseteq B</math> אז <math>C\cap B\neq D\cap B</math>, ולכן <math>[C]\neq [D]</math>.
+
  
−
ובסה"כ קיבלנו שכל איבר ב- <math>P(A)/\sim</math> מוגדר ע"י תת קבוצה של <math>B</math> ושאין חזרה כי כל שתי תתי קבוצות שונות של <math>B</math> מגדירות מחלקת שקילות שונה. לכן מספר האיברים בקבוצת המנה הוא כמספר תתי הקבוצות של <math>B</math>.
+
ג. תהיינה <math>C,D\subseteq B</math> שונות. לכן קיים (בה"כ) <math>x\in C\smallsetminus D</math> וכמובן <math>x\in B</math>, ולכן נקבל <math>x\in C\cap B\land x\notin D\cap B</math> כלומר <math>C\cap B\neq D\cap B</math> ולכן <math>[C]\neq [D]</math>.
  
 
===שאלה ממבחן===
 
===שאלה ממבחן===

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

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

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

הגדרה: תהא 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 אזי

  1. לכל x\in A מוגדרת מחלקת השקילות של x להיות \bar{x}=[x]_R:=\{y\in A | (x,y)\in R\}
  2. קבוצת המנה מוגדרת 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 אזי

  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}

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


תרגיל

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

פתרון

רפלקסיביות: מאחר ו \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

מקור: https://math-wiki.com/index.php?title=תרגול_11_תשעז&oldid=74044