תורת הקבוצות/יחסי שקילות: הבדלים בין גרסאות בדף

[[תורת הקבוצות/יחסים|יחס]] <math>\mathfrak{D}</math> על קבוצה <math>A</math> יקרא '''יחס שקילות''' אם מתקיימים התנאים הבאים:

* '''היחס רפלקסיבי:''' לכל <math>a\in{A}</math> מתקיים <math>a\mathfrak{D}a</math> (כלומר <math>(a,b)\in{\mathfrak{D}}</math>).

יחס השוויון על הקבוצה <math>A=\{1,2,3\}</math> הוא קבוצת הזוגות <math>\{(1,1),(2,2),(3,3)\}</math>.

ב. אםתהי <math>A</math> קבוצה של קבוצות,. אזיהי היחס <math>\cong</math> על הקבוצה <math>A</math> שמוגדר כך:

היחס <math>\cong{}</math> הוא יחס שקילות:

* לכל קבוצה <math>X\in{A}</math> פונקציית הזהות <math>f(a)=a</math> מ-<math>A</math> ל-<math>A</math> היא בייקציה ולכן <math>X\cong{}X</math>.

* לכל <math>X,Y\in{A}</math> אם <math>X\cong{}Y</math>, כלומר יש בייקציה <math>f:X\to{}Y</math> אז גם <math>f^{-1}:Y\to{}X</math> היא בייקציה ולכן <math>Y\cong{}X</math>.

* לכל לכל <math>X,Y,Z\in{A}</math> אם <math>X\cong{}Y</math> וגם <math>Y\cong{}Z</math>, כלומר יש בייקציה <math>f:X\to{}Y</math> וגם יש בייקציה <math>g:Y\to{}Z</math> אז גם ההרכבה <math>g\circ{}f:X\to{}Z</math> היא בייקציה ולכן <math>X\cong{}Z</math>.

תהי קבוצה לא ריקה <math>A</math>. לקבוצה <math>S\subseteq{}\mathcal{P}(A)</math> (מוכלת בקבוצת החזקה של <math>A</math>) נקרא '''חלוקה''' של <math>A</math> אם מתקיימים התנאים הבאים:

* איברי הקבוצה <math>S</math> זרים בזוגות. כלומר: לכל <math>X,Y\in{}S</math> מתקיים <math>X\cap{}Y=\varnothing</math>.

* איחוד כל איברי <math>S</math> היא הקבוצה <math>A</math>. כלומר: <math>\bigcup_{X\in{}S}X=A</math>

הערה: קבוצה <math>X\in{}S</math> (השייכת לחלוקה) תקרא '''תא''' של החלוקה. כלומר, אם <math>x\in{}X</math> נאמר שהאיבר <math>x</math> שייך לתא <math>X</math> של החלוקה <math>S</math>.

א. נתבונן בקבוצה <math>A=\{1,2,3,4,5\}</math>. הקבוצה <math>B=\{\{1,2\},\{3\},\{4,5\}\}</math> היא חלוקה של <math>A</math>(ודאו זאת).

תהיא קבוצה <math>A</math>ויהייהי <math>\mathfrak{D}</math> יחס שקילות על קבוצה <math>A</math> ויהי <math>a\in{}A</math>. נגדיר קבוצה שתסומן <math>[a]</math> ותקרא בשם '''מחלקת השקילות''' של <math>a</math>באופן הבא:

כלומר, מחלקת השקילות של איבר <math>a\in A</math>, היא קבוצת כל האיברים של <math>A</math> המתייחסים אל <math>a</math> ביחס השקילות <math>\mathfrak{D}</math>.

תהיא קבוצה <math>A</math>ויהייהי <math>\mathfrak{D}</math> יחס שקילות על קבוצה <math>A</math>. נגדיר קבוצה שתסומן <math>A\setminusdiagup\mathfrak{D}</math> תקראותקרא '''קבוצת המנה''' ותוגדרבאופן כךהבא:

קבוצת המנה של <math>A</math>, היא קבוצת כל מחלקות השקילות של <math>A</math>. כלומר:

<math>A\setminusdiagup\mathfrak{D}=\{[a]|a\in{}A\}</math>

ב. הקבוצה <math>\{(1,1),(2,2),(3,3)\}</math> היא קבוצת המנה של <math>\{1,2,3\}\setminusdiagup{}=</math> (ראה דוגמה א' בדוגמאות ליחסי שקילות ודוגמה ב' בדוגמאות לחלוקה).

תהי קבוצה לא ריקה <math>A</math> ותהי <math>S</math> חלוקה של <math>A</math>.

לכל <math>a,b\in{}A</math>, <math>a\thickapprox{}b</math> אם ורק אם <math>a,b\in{}X</math> כאשר <math>X\in{}S</math> (כלומר, <math>a,b</math> נמצאים באותו התא בחלוקה)

* '''היחס <math>\thickapprox</math> רפלקסיבי:''' יהי <math>a\in{}A</math>. אם <math>a\in{}X</math> (כאשר <math>X</math> תא בחלוקה) אז ברור ש- <math>a\in{}X</math> ולכן <math>a\thickapprox{}a</math>.

* '''היחס <math>\thickapprox</math> סימטרי:''' יהיו <math>a,b\in{}A</math>. אם <math>a\thickapprox{}b</math>, כלומר <math>a,b\in{}X</math> (כאשר <math>X</math> תא בחלוקה) אז ברור ש- <math>b,a\in{}X</math> ולכן <math>b\thickapprox{}a</math>.

* '''היחס הוא טרנזיטיבי:''' יהיו <math>a,b,c\in{}A</math>. אם <math>a\thickapprox{}b</math> וגם <math>b\thickapprox{}c</math>, כלומר <math>a,b\in{}X</math> וגם <math>b,c\in{}Y</math> (כאשר <math>X,Y</math>תאho תאים בחלוקה) אז: <math>b\in{}X\land{}x\in{}Y\to{}X=Y</math> (ראה הגדרת החלוקה) לכן <math>a,c\in{}X</math> ולכן <math>a\thickapprox{}c</math>.

תהיאתהי קבוצה <math>A</math> ויהי <math>\mathfrak{D}</math> יחס שקילות על <math>A</math>. '''קיימת''' חלוקה '''יחידה''' <math>S</math> של <math>A</math> אשר היחס <math>\mathfrak{D}</math> '''מושרה על ידה'''.

במהלך ההוכחה נסמן <math>[a]</math> מחלקת השקילות (ראו הגדרה) של <math>a</math>.

<u>שלב ראשון:</u> נוכיח כי קבוצת המנה <math>A\setminusdiagup\mathfrak{D}</math> היא חלוקה של <math>A</math> (ראה הגדרה).

לכן, מהגדרת החלוקה, מצאנו כי <math>S=A\setminusdiagup\mathfrak{D}</math> ('''קבוצת המנה''': ראה הגדרה) היא '''חלוקה''' של <math>A</math>.

מ-(5) ומ-(6) הוכחנו כי <math>A\setminusdiagup\mathfrak{D}</math> היא החלוקה היחידה שמשרה את היחס <math>\Box</math>.