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

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