שינויים

נביט בקבוצה <math>הגדרה: תהא A=\{1,2,3,4,5,6\}</math> ונביט באוסף תת הקבוצות <math>B=\{1,3\},C=\{2,4,5\},D=\{6\}</math> המקיימות שתי תכונות*הן '''זרות''' זו לו (כלומר החיתוך בין כל שתי תתי קבוצות קבוצה ו-R יחס עליה. R יקרה יחס שקילות אם הוא ריק)*האיחוד של כל תתי הקבוצות שווה לקבוצה כולה <math>A=B\cup C\cup D</math>#רפלקסיבי#סימטרי#טרנזיטיבי

(אמנם אנחנו עוסקים בדוגמא, אבל התרגיל יהיה נכון באופן כללי לקבוצות כאלה). נגדיר את היחס R על A באופן הבאדוגמא: תהא <math>(xA=\{1,2,3,4,5,y)6\in R}</math> אם"ם x,y שייכים שניהם לאחד מתתי . נגדיר תת הקבוצות B<math>A_1=\{1,C3\},D.A_2=\{2,4,5\},A_3=\{6\}</math>

הוכח שR מקיים רפלקסיביותנגדיר יחס R על A כך <math>\exist 1\leq i \leq 3 : x, סימטריות, וטרנזיטיביות.y\in A_i \Leftrightarrow xRy</math>

12. רפלקסיביות סימטריות - נניח <math>(x,y)\in AR</math> לכן אזי <math>x שייך לאחת מתתי הקבוצות (שכן האיחוד שלהן שווה לA) ולכן ,y\in A_i</math> עבור i מסוים, מכיוון שאין משמעות לסדר שייכות לקבוצה, נובע שגם <math>(xy,x)\in R</math>.

23. סימטריות טרנזיטיביות - נניח <math>[(x,y)\in R] \and [(y,z)\in R]</math> אזי קיימים i,j כך ש <math>x,y\in XAֹ_i</math> כאשר X אחת מתתי הקבוצותוגם <math>y, z\in A_j</math>. לכן <math>y\in A_i\cap A_j</math>. מכיוון שאין משמעות לסדר שייכות לקבוצה, נובע שגם שהחיתוך בין תתי הקבוצות הוא ריק מוכרח להיות ש<math>(A_i=A_j</math> ולכן <math>x,y,z\in A_i</math> ולכן <math>(x,z)\in R</math>כפי שרצינו.

3הגדרה: תהא A קבוצה. טרנזיטיביות - נניח '''חלוקה''' של A היא חלוקה של A לקבוצות זרות. באופן פורמלי קיימות תת קבוצות <math>[(x,y)\in R] {A_i\and [(y,z)}_{i\in R]I}</math> אזי אחת מתתי הקבוצות X מקיימת כך ש:* <math>x,y\cup _{i\in XI} A_i =A </math> ואחת מתתי כלומר האיחוד של כל תתי הקבוצות Y מקיימת שווה לקבוצה כולה * הן '''זרות''' זו לו = החיתוך בין כל שתי תתי קבוצות הוא ריק (<math>y,z\in Y</math>. לכן <math>yforall i\not= j\in XI : A_i\cap Y</math>. מכיוון שהחיתוך בין תתי הקבוצות הוא ריק מוכרח להיות שXA_j =Y ולכן <math>x,y,z\in Xphi </math> ולכן <math>(x,z)\in R</math> כפי שרצינו.

הגדרהדוגמא נוספת: יחס המקיים את שלושת התכונות רפלקסיביות, סימטריות וטרנזיטיביות נקרא '''יחס שקילויות'''. כפי שראינו בתרגיל הקודם, אם אנחנו מחלקים קבוצה לתתי קבוצות זרות, היחס שמקשר בין איברי אותה קבוצה הינו יחס שקילויות. האם הכיוון ההפוך גם נכון? כלומר, האם כל יחס שקילויות מחלק קבוצה לתתי קבוצות זרות שאיחודן נותן את הקבוצה כולה.

התשובה איפוא היא כן, נגדיר יחס שקילויות מחלק קבוצה לתתי קבוצות כאלה שקילות R על <math>\mathbb{Z}</math> ע"י <math>3|(תרגיל קל). זוהי מהותו העיקרית של יחס השקילויות x- לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויוןy) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.\Leftrightarrow xRy</math>

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

דוגמאהוכחה:  1. רפלקסיביות - נניח <math>\forall x\in \mathbb{Z}:3|0=x-x</math> לכן <math>xRx</math>  2. סימטריות - נניח <math>(x,y)\in R</math> אזי <math>3|(x-y)</math> ולכן גם <math>3|(y-x)=-(x-y)</math> 3. טרנזיטיביות - נניח <math>[(x,6y)\in R] \and [(y,9,... כולם ביחס השקילות "מודולו z)\in R]</math> אזי <math>3" באותה |(x-y)\and 3|(y-z) </math> ולכן גם <math>3|(z-x)=(z-y)+(y-x)</math>  הגדרה: יהא R יחס על A אזי # לכל <math>x\in A</math> מוגדרת '''מחלקת שקילותהשקילות של x ''' להיות <math>\bar{x}=[x]_R:=\{y\in A | (x,y)\in R\} </math># ''' קבוצת המנה ''' מוגדרת <math>A/R := \{ [x]_R | x\in A\} </math>  למשל, בדוגמא הראשונה <math>A_1,A_2,A_3</math> הן מחלקות השקילות. 1קבוצת המנה היא <math>R/A=\{A_1,4A_2,7A_3\}</math> בדוגמא השניה מחלקת השקילות של 0 היא <math>[0]_R=\{ 0 \pm 3 \pm 6 \dots \}</math> וקבוצת המנה היא<math>\mathbb{Z}/R= \{[0]_R,10.[1]_R [3]_R\}</math> (כלומר כל השאריות האפשריות בחלוקה ב-3).. נמצאים במחלקת  משפט: יהא R יחס שקילות אחרתעל A אזי# לכל <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 מסקנה:תהא A קבוצה אזי יש התאמה {<math>R</math> יחס שקילות על A } <math>\leftrightarrow</math> {חלוקות של A} חידוד: מהותו העיקרית של יחס שקילויות הוא לשים לב לשקילות מסוימת בין אברים שונים (כמו שיוויון) ולצמצם את החזרות המיותרות על ידי קיבוץ כל האיברים השקולים לקבוצה אחת.