תורת הקבוצות/יחסי שקילות

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

הגדרות

הגדרה: יחס שקילות (Equivalence relation) יחס ${\mathfrak {D}}$ על קבוצה $A$ יקרא יחס שקילות אם מתקיימים התנאים הבאים: היחס רפלקסיבי: לכל $a\in {A}$ מתקיים $a{\mathfrak {D}}a$ (כלומר $(a,b)\in {\mathfrak {D}}$). היחס סימטרי: לכל $a,b\in {A}$ אם $a{\mathfrak {D}}b$ אז $b{\mathfrak {D}}a$. היחס טרנזיטיבי: לכל $a,b,c\in {A}$ אם $a{\mathfrak {D}}b$ וגם $b{\mathfrak {D}}c$ אז $a{\mathfrak {D}}c$.

דוגמאות ליחסי שקילות

א. יחס השוויון (=) על כל קבוצה $A$ הוא יחס שקילות:

• לכל $a\in (A)$ מתקיים $a=a$.
• לכל $a,b\in (A)$ אם $a=b$ אז $b=a$.
• לכל $a,b,c\in (A)$ אם $a=b$ וגם $b=c$ אז $a=c$.

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

ב. תהי $A$ קבוצה של קבוצות. יהי היחס $\cong$ על הקבוצה $A$ שמוגדר כך:

לכל $X,Y\in {A}$ מתקיים $X\cong {}Y$ אם ורק אם קיימת בייקציה (פונקציה חד-חד ערכית ועל) $f:A\to {}B$.

היחס $\cong {}$ הוא יחס שקילות:

• לכל קבוצה $X\in {A}$ פונקציית הזהות $f(a)=a$ מ-$A$ ל-$A$ היא בייקציה ולכן $X\cong {}X$.
• לכל $X,Y\in {A}$ אם $X\cong {}Y$, כלומר יש בייקציה $f:X\to {}Y$ אז גם $f^{-1}:Y\to {}X$ היא בייקציה ולכן $Y\cong {}X$.
• לכל לכל $X,Y,Z\in {A}$ אם $X\cong {}Y$ וגם $Y\cong {}Z$, כלומר יש בייקציה $f:X\to {}Y$ וגם יש בייקציה $g:Y\to {}Z$ אז גם ההרכבה $g\circ {}f:X\to {}Z$ היא בייקציה ולכן $X\cong {}Z$.

הדוגמה הראשונה היא טריוויאלית. בעוד הדוגמה השנייה קשה יותר (מומלץ לקרוא בעיון ולנסות להבין). עוד נחזור לדוגמאות אלו אחרי ההגדרה הבאה:

הגדרה: חלוקה של קבוצה (Partition) תהי קבוצה לא ריקה $A$. לקבוצה $S\subseteq {}{\mathcal {P}}(A)$ (מוכלת בקבוצת החזקה של $A$) נקרא חלוקה של $A$ אם מתקיימים התנאים הבאים: כל איבר $X\in {}S$ מקיים $X\neq \varnothing$. איברי הקבוצה $S$ זרים בזוגות. כלומר: לכל $X,Y\in {}S$ מתקיים $X\cap {}Y=\varnothing$. איחוד כל איברי $S$ היא הקבוצה $A$. כלומר: $\bigcup _{X\in {}S}X=A$.

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

דוגמאות לחלוקה:

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

ב. הקבוצה $\{(1,1),(2,2),(3,3)\}$ מהווה חלוקה של $A=\{1,2,3\}$ (ראה דוגמה א' בדוגמאות ליחסי שקילות).

ג. הקבוצה $\{3n|n\in \mathbb {N} \}\cup \{3n+1|n\in \mathbb {N} \}\cup \{3n+2|n\in \mathbb {N} \}$ היא חלוקה של $\mathbb {N}$.

הגדרה: מחלקת שקילות יהי ${\mathfrak {D}}$ יחס שקילות על קבוצה $A$ ויהי $a\in {}A$. נגדיר קבוצה שתסומן $[a]$ ותקרא בשם מחלקת השקילות של $a$באופן הבא: $[a]=\{b\in {}A|b{\mathfrak {D}}a\}$ כלומר, מחלקת השקילות של איבר $a\in A$, היא קבוצת כל האיברים של $A$ המתייחסים אל $a$ ביחס השקילות ${\mathfrak {D}}$.

הגדרה: קבוצת המנה יהי ${\mathfrak {D}}$ יחס שקילות על קבוצה $A$. נגדיר קבוצה שתסומן $A\diagup {\mathfrak {D}}$ ותקרא קבוצת המנה באופן הבא: קבוצת המנה של $A$, היא קבוצת כל מחלקות השקילות של $A$. כלומר: $A\diagup {\mathfrak {D}}=\{[a]|a\in {}A\}$

דוגמה:

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

תכונות של יחסי שקילות

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

משפט: חלוקה משרה יחס שקילות תהי קבוצה לא ריקה $A$ ותהי $S$ חלוקה של $A$. יהי $\thickapprox$ יחס על $A$ שיוגדר כדלהלן: לכל $a,b\in {}A$, $a\thickapprox {}b$ אם ורק אם $a,b\in {}X$ כאשר $X\in {}S$ (כלומר, $a,b$ נמצאים באותו התא בחלוקה) היחס $\thickapprox$ הוא יחס שקילות על $A$.

הוכחה:

היחס $\thickapprox$ רפלקסיבי:

יהי $a\in {}A$.

אם $a\in {}X$ (כאשר $X$ תא בחלוקה) אז ברור ש- $a\in {}X$ ולכן $a\thickapprox {}a$.

היחס $\thickapprox$ סימטרי:

יהיו $a,b\in {}A$.

אם $a\thickapprox {}b$, כלומר $a,b\in {}X$ (כאשר $X$ תא בחלוקה) אז ברור ש-$b,a\in {}X$ ולכן $b\thickapprox {}a$.

היחס $\thickapprox$ הוא טרנזיטיבי:

יהיו $a,b,c\in {}A$.

אם $a\thickapprox {}b$ וגם $b\thickapprox {}c$, כלומר $a,b\in {}X$ וגם $b,c\in {}Y$ (כאשר $X,Y$ תאים בחלוקה) אז:

$b\in {}X\land {}b\in {}Y\to {}X=Y$ (ראה הגדרת החלוקה) לכן $a,c\in {}X$ ולכן $a\thickapprox {}c$.

הוכחנו כי $\thickapprox$ הוא יחס רפלקסיבי, סימטרי וטרנזיטיבי ובכך הוכחנו כי הוא יחס שקילות.

כפי שמצביע שם המשפט: ליחס זה אנו קוראים היחס שמושרה על ידי החלוקה או שאנו אומרים החלוקה משרה את היחס.

עכשיו יש בידינו כלי, שדרכו נוכל לחבר בין כל ההגדרות שהובאו ולהראות מדוע יחסי השקילות כה חשובים:

משפט: קבוצת המנה היא חלוקה יהי ${\mathfrak {D}}$ יחס שקילות על קבוצה לא ריקה $A$. קבוצת המנה $A\diagup {\mathfrak {D}}$ מהווה חלוקה של $A$

הוכחה:

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

(*): נוכיח $a{\mathfrak {D}}b$ אם ורק אם $[a]=[b]$.

כיוון ראשון נניח כי $a{\mathfrak {D}}b$. יהי $c\in {}A$.

$c\in {}[a]$ אם ורק אם $c{\mathfrak {D}}a$ (מהגדרת מחלקת השקילות)

$c{\mathfrak {D}}a$ אם ורק אם $c{\mathfrak {D}}b$ (טרנזיטיביות ומההנחה ש-$a{\mathfrak {D}}b$)

לבסוף, $c{\mathfrak {D}}b$ אם ורק אם $c\in {}[b]$(הגדרת מחלקת השקילות).

הראנו כי $c\in [a]\leftrightarrow {}c\in [b]$ ולכן, מצאנו כי $[a]=[b]$. כפי שרצינו.

כיוון שני: נניח כי $[a]=[b]$.

משום ש-${\mathfrak {D}}$ יחס שקילות, הרי ש-$a{\mathfrak {D}}a$ (רפלקסיביות) ולכן $a\in [a]$.

מההנחה ש-$[a]=[b]$ נקבל כי $a\in [b]$.

לכן, מהגדרת מחלקת השקילות, נקבל כי $a{\mathfrak {D}}b$. כפי שרצינו.

בכך הוכחנו את (*).

(1) נוכיח שלכל $a\in {}A$ מתקיים כי $[a]\neq \varnothing$:

לכל $a\in {}A$ מתקיים $a{\mathfrak {D}}a$ (רפלקסיביות) מכך נובע כי $a\in [a]$ ולכן $[a]\neq {}\varnothing$. כפי שרצינו.

(2) נוכיח שאם $[a]\neq {}[b]$ (תאים שונים של החלוקה) אז $[a]\cap {}[b]\neq \varnothing$:

יהיו $[a],[b]\in A\diagup {\mathfrak {D}}$ המקיימים $[a]\neq [b]$, הדבר שקול לכך ש- $a{\bcancel {\mathfrak {D}}}b$ (לפי (*)).

נניח בשלילה כי $[a]\cap {}[b]\neq \varnothing$.

מהנחת השלילה, נובע כי קיים $c\in {}[a]\cap {}[b]$.

מכך ש-$c\in {}[a]\cap {}[b]$ נובע ש-$c\in {}[a]$ וגם ש-$c\in {}[b]$.

לכן, מהגדרת מחלקת השקילות, מצאנו כי $c{\mathfrak {D}}a$ וגם $c{\mathfrak {D}}b$.

מסימטריות נקבל כי $c{\mathfrak {D}}a\to a{\mathfrak {D}}c$.

מטרנזיטיביות נקבל כי $a{\mathfrak {D}}c\land {}c{\mathfrak {D}}b\to {}a{\mathfrak {D}}b$ בסתירה להנחה כי $a{\bcancel {\mathfrak {D}}}b$.

הנחת השלילה הובילה לסתירה, ולכן $[a]\neq [b]\to [a]\cap [b]=\varnothing$. כפי שרצינו.

(3): נראה כי $A=\bigcup _{a\in {}A}[a]$.

כיוון ראשון: יהי $a\in {}A$,

מהגדרת מחלקת השקילות, נקבל $[a]\subseteq {}A$ ולכן מתקיים ש- $\bigcup _{a\in {}A}[a]\subseteq {}A$.

כיוון שני: יהי $a\in {}A$.

נקבל $a\in [a]$ (כפי שהראנו ב-(2)) ולכן $a\in {}\bigcup _{a\in {}A}[a]$.

בכך הראנו כי $A\subseteq \bigcup _{a\in {}A}[a]$.

משילוב הכיוונים קיבלנו כי $A=\bigcup _{a\in {}A}[a]$.

לפי (1), (2) ו-(3) הראנו שכל מחלקת שקילות אינה ריקה, הראנו שכל שתי מחלקות שקילות שונות זרות והראנו שאיחוד כל מחלקות השקילות הוא $A$.

לכן, מהגדרת החלוקה, מצאנו כי $A\diagup {\mathfrak {D}}$ (קבוצת המנה: ראה הגדרה) היא חלוקה של $A$.

משפט: יחידות החלוקה הי ${\mathfrak {D}}$ יחס שקילות על קבוצה לא ריקה $A$. קבוצת המנה $A\diagup {\mathfrak {D}}$ היא החלוקה היחידה של $A$ אשר היחס ${\mathfrak {D}}$ מושרה על ידה.

הוכחה:

במשפט: קבוצת המנה היא חלוקה, הוכחנו כי $A\diagup {\mathfrak {D}}$ היא חלוקה של $A$.

עתה נוכיח כי $A\diagup {\mathfrak {D}}$ היא החלוקה היחידה שמשרה את ${\mathfrak {D}}$.

(1) נוכיח ש-$A\diagup {\mathfrak {D}}$ היא אכן חלוקה שמשרה את ${\mathfrak {D}}$, כלומר, נראה כי $a{\mathfrak {D}}b$ אם ורק אם $a$ ו-$b$ באותו התא של $A\diagup {\mathfrak {D}}$:

כיוון ראשון: נניח כי $a{\mathfrak {D}}b$.

משום ש-$a{\mathfrak {D}}b$ נובע כי $a\in {}[b]$ (הגדרת מחלקת השקילות).

משום ש-${\mathfrak {D}}$ הוא יחס שקילות, נקבל כי $b{\mathfrak {D}}b$ (רפלקסיביות) ולכן $b\in {}[b]$.

מצאנו ש-$a\in [b]$ וגם $b\in {}[b]$ ובכך הראנו כי $a,b$ באותו תא.

כיוון שני: נניח כי $a$ ו-$b$ באותו התא של $A\diagup {\mathfrak {D}}$, כלומר $a,b\in {}[c]$.

מהגדרת מחלקת השקילות נקבל ש-$a{\mathfrak {D}}c$ וגם $b{\mathfrak {D}}c$.

לכן נקבל $a{\mathfrak {D}}b$ (סימטריה, וטרנזיטיביות של יחס השקילות ${\mathfrak {D}}$).

כלומר, בסה"כ $a,b\in [c]\leftrightarrow a{\mathfrak {D}}b$ (כאשר $[c]\in A\diagup {\mathfrak {D}}$)

בכך הראנו שהחלוקה $A\diagup {\mathfrak {D}}$ משרה את היחס ${\mathfrak {D}}$. כפי שרצינו.

(2): נוכיח כי זו החלוקה היחידה שמשרה את ${\mathfrak {D}}$.

תהא $T$ חלוקה שמשרה את ${\mathfrak {D}}$, כלומר $a{\mathfrak {D}}b$ אם ורק אם $a,b$ באותו התא של $T$.

כייון ראשון: יהי $X$ תא בחלוקה $T$.

$X\neq \varnothing$ ולכן יש $a\in X$. לכל $b\in A$ מתקיים $b\in X$ אם ורק אם $a{\mathfrak {D}}b$ ($T$ משרה את ${\mathfrak {D}}$).

כלומר, $a{\mathfrak {D}}b$ אם ורק אם $b\in [a]$ ( $A\diagup {\mathfrak {D}}$ משרה את ${\mathfrak {D}}$).

מצאנו כי $a,b\in X\leftrightarrow a{\mathfrak {D}}b\leftrightarrow a,b\in [a]$מכאן ש-$X=[a]$.

הראנו שכל תא $X\in T$ הוא תא של $A\diagup {\mathfrak {D}}$ ולכן $T\subseteq {}A\diagup {\mathfrak {D}}$.

כיוון שני: יהי $[a]\in {}A\diagup {\mathfrak {D}}$ תא אשר $a\in A$ שייך אליו.

מתקיים $b\in [a]$ אם ורק אם $a{\mathfrak {D}}b$ ( $A\diagup {\mathfrak {D}}$ משרה את ${\mathfrak {D}}$).

כמו כן, $a{\mathfrak {D}}b$ אם ורק אם $b\in {}X$ ($T$ משרה את ${\mathfrak {D}}$).

הראנו כי $a,b\in [a]\leftrightarrow a{\mathfrak {D}}b\leftrightarrow a,b\in T$.

הראינו שכל תא $[a]\in {}A\diagup {\mathfrak {D}}$ הוא תא של $T$ ולכן $A\diagup {\mathfrak {D}}\subseteq {}T$.

משילוב הכיוונים מצאנו כי $T=A\diagup {\mathfrak {D}}$, כפי שרצינו.

מ-(1) ומ-(2) הוכחנו כי $A\diagup {\mathfrak {D}}$ היא החלוקה היחידה שמשרה את היחס

במשפטים אלו הוכחנו שני דברים חשובים:

הראשון, קבוצת המנה של קבוצה היא חלוקה.

השני, קבוצת המנה היא החלוקה היחידה שמשרה את יחס השקילות שמגדיר אותה.

משילוב המשפטים ניתן לראות, שאם נקבל חלוקה - אז נוכל להשרות דרכה יחס שקילות.

ואם נקבל יחס שקילות, נוכל למצוא את החלוקה שמשרה אותו; היא פשוט קבוצת המנה.

שימושים

מכאן, נחזור לדוגמה ב' בדוגמאות ליחס שקילות: אחת הדרכים (אם כי הפחות שימושית) בה מגדירים באופן פורמלי עוצמה של קבוצה, היא לקחת את מחלקת כל הקבוצות, ולהסתכל על מחלקת המנה שלה (הגדרה כמעט זהה לקבוצת המנה) ביחס ליחס $\cong$שהוגדר בדוגמה.

כלומר, אנו יודעים שלשתי קבוצות יש את אותה עוצמה אם יש ביניהן בייקציה. לכן, בהנתן קבוצה $A$נוכל לומר שהעוצמה שלה היא פשוט מחלקת השקילות $[A]$ ביחס ל-$\cong$.

ואכן, אנו נאמר של $A$ול-$B$יש את אותה עוצמה אם $B\in {}[A]$.

כמו כן, הגדרות רבות במתמטיקה (למשל של סודרים) ניתנות על ידי מחלקות שקילות והקשר שביניהן לבין חלוקה.

דוגמאות לאובייקטים מתמטיים שנהוג להגדיר על ידי יחס שקילות ועל ידי קבוצת המנה הם המספרים השלמים והרציונליים.

כדוגמה נוספת למחלקת שקילות:

אפשר להסתכל על דמיון ועל חפיפת משולשים כיחסי שקילות.

נסו למצוא תאור מדוייק של מחלקות השקילות של יחס הדמיון בין משולשים.

חישבו גם מה משותף ביחס החפיפה בין משולשים, ליחס השוויון בין קבוצות (ראה דוגמה א' בדוגמות ליחס שקילות).

הפרק הקודם: פונקציות

יחסי שקילות

הפרק הבא: יחסי סדר