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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏שאלה ממבחן)
 
(3 גרסאות ביניים של משתמש אחר אחד אינן מוצגות)
שורה 1: שורה 1:
 
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
 
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
  
−
==המשך יחסי שקילות==
+
==יחסי שקילות - תרגילים נוספים==
  
−
הגדרה: תהא A קבוצה. '''חלוקה''' של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות <math>\{A_i\}_{i\in I}</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>\forall i\in I: A_i \neq \emptyset </math>
+
−
* <math>\cup _{i\in I} A_i =A </math> כלומר האיחוד של כל תתי הקבוצות שווה לקבוצה כולה 
+
−
* הקבוצות <math>A_i</math> הן '''זרות''' זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק (<math>\forall i\not= j\in I : A_i\cap A_j = \phi </math>)
+
  
−
הגדרה:
+
א. זהו יחס שקילות.
  
−
יהא R יחס שקילות על A אזי
+
ב. לכל <math>X\subseteq A</math> קיימת <math>C\subseteq B</math> כך ש <math>[X]_R=[C]_R</math>.
  
−
# לכל <math>x\in A</math> מוגדרת '''מחלקת השקילות של x ''' להיות  <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} </math>
+
ג. אם <math>C,D\subseteq B</math> שונות, אז <math>[C]\neq [D]</math>.
−
# ''' קבוצת המנה ''' מוגדרת <math>A/R := \{ [x]_R | x\in A\} </math>
+
  
 +
====פיתרון====
 +
א. רפלקסיביות: כמובן ש- <math>\forall C\subseteq A:C\cap B=C\cap B</math>, ולכן <math>C\sim C</math>.
  
−
למשל בדוגמא משבוע שעבר על השלמים עם היחס <math>x~y\iff 3|x-y</math>, מחלקת השקילות של 0 היא <math>[0]_R=\{ 0 \pm 3 \pm 6 \dots \}</math> וקבוצת המנה היא
+
סימטריות: נניח <math>C\sim D</math> אזי <math>C\cap B=D\cap B\iff D\cap B=C\cap B</math>, ולכן <math>D\sim C</math>.
−
<math>\mathbb{Z}/R= \{[0]_R,[1]_R,[2]_R\}</math> (כלומר כל השאריות האפשריות בחלוקה ב-3).
+
  
 +
טרנזיטיביות: נניח <math>C\sim D\land D\sim E</math> אזי <math>C\cap B=D\cap B\land D\cap B=E\cap B</math> ומטרנזיטיביות יחס השיוויון נקבל הדרוש.
  
−
משפט: יהא R יחס שקילות על A אזי
+
ב. יהי <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>x,y\in A</math> מתקיים <math>[x]=[y]</math> או <math>[x]\cap [y] =\phi </math> (כלומר מחלקות השקילות זרות)
+
−
# <math>A=\bigcup_{[x]\in A/R}[x]</math> כלומר (איחוד מחלקות השקילות תתן את כל A)
+
−
הערה: זה בדיוק אומר שמיחס שקילות ניתן להגיע לחלוקה של A
+
  
 +
ג. תהיינה <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>.
  
−
מסקנה:
+
===שאלה ממבחן===
−
תהא A קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על A }
+
א. תהי <math>A</math> קבוצה לא ריקה ותהי <math>\{R_i\}_{i\in I}</math> משפחה של יחסי שקילות על <math>A</math>. הוכיחו כי החיתוך הכללי <math>R=\cap_{i\in I}R_i</math> הינו יחס שקילויות על <math>A</math>.
−
<math>\leftrightarrow</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>(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>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>(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>|P(A)/\sim |</math>
+
ב. <math>R_1</math> הינו אוסף כל הזוגות הסדורים מעל השלמים, שכן אחד מחלק כל מספר ולכן כל הפרש.
  
−
====פיתרון====
+
<math>R_2</math> הינו אוסף כל הזוגות בהם שני הצדדים זוגיים או שני הצדדים אי זוגיים, שכן ההפרש בינהם חייב להיות זוגי.
−
א. רפלקסיביות: כמובן ש- <math>\forall C\subseteq A:C\cap B=C\cap B</math>, ולכן <math>C\sim C</math>.
+
  
−
סימטריות: נניח <math>C\sim D</math> אזי <math>C\cap B=D\cap B\iff D\cap B=C\cap B</math>, ולכן <math>D\sim C</math>.
+
<math>R</math> הינו אוסף הזוגות שההפרש בינהם מתחלק בכל המספרים הטבעיים. רק הפרש אפס יכול להתחלק בכל מספר, ולכן <math>R</math> הינו אוסף הזוגות מהצורה <math>(q,q)</math> עבור <math>q</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>\mathbb{Z}/R_1</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>\mathbb{Z}/R_2</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>\mathbb{Z}/R</math> הינו אוסף כל הקבוצות המכילות איבר שלם בודד.
−
 
+
−
ובסה"כ קיבלנו שכל איבר ב- <math>P(A)/\sim</math> מוגדר ע"י תת קבוצה של <math>B</math> ושאין חזרה כי כל שתי תתי קבוצות שונות של <math>B</math> מגדירות מחלקת שקילות שונה. לכן מספר האיברים בקבוצת המנה הוא כמספר תתי הקבוצות של <math>B</math>.
+
−
 
+
−
===שאלה ממבחן===
+
−
תהי A קבוצה לא ריקה ותהי <math>\{R_i\}_{i\in I}</math> משפחה של יחסי שקילות על A. הוכיחו כי החיתוך הכללי  <math>R=\cap_{i\in I}R_i</math> הינו יחס שקילויות על A.
+
−
 
+
−
====פתרון====
+
−
רפלקסיביות: מאחר ו <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>
+

גרסה אחרונה מ־15:56, 29 בדצמבר 2017

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

יחסי שקילות - תרגילים נוספים

תרגיל

תהא 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 הינו אוסף כל הקבוצות המכילות איבר שלם בודד.

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