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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏תרגיל)
(←‏המשך יחסי שקילות)
שורה 31: שורה 31:
 
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
 
חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.
  
−
===שאלה ממבחן===
 
−
תהי 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>
 
  
 
===תרגיל===
 
===תרגיל===
שורה 60: שורה 51:
  
 
מצד שני, מכל מחלקת שקילות נוכל לבחור תת קבוצה של <math>B</math> כנציג: כי <math>\forall C\in P(A):[c]=\{ D\subseteq A|C\cap B=D\cap B\}</math>, וכיון ש- <math>C\cap B\subseteq B</math> נקבל <math>[C]=[C\cap B]</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\subseteq B</math> נקבל <math>[C]=[C\cap 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>

גרסה מ־10: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.

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

ב. מצא את P(A)/\sim

פיתרון

א. רפלקסיביות: כמובן ש- \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 ומטרנזיטיביות יחס השיוויון נקבל הדרוש.

ב. פיתרון: P(A)/\sim =P(B). הוכחה:

מחד כל תת קבוצה של B מגדירה מחלקת שקילות שונה, כי אם C\neq D\subseteq B אז C\cap B\neq D\cap B, ולכן [C]\neq [D].

מצד שני, מכל מחלקת שקילות נוכל לבחור תת קבוצה של B כנציג: כי \forall C\in P(A):[c]=\{ D\subseteq A|C\cap B=D\cap B\}, וכיון ש- C\cap B\subseteq B נקבל [C]=[C\cap B].

שאלה ממבחן

תהי 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=69940