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

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

הגדרות

הגדרה: יחס שקילות (Equivalence relation) יחס ${\mathcal {R}}$ על קבוצה $A$ יקרא יחס שקילות אם מתקיימים התנאים הבאים: היחס רפלקסיבי: לכל $a\in A$ מתקיים $a{\mathcal {R}}a$ (כלומר $(a,a)\in {\mathcal {R}}$). היחס סימטרי: לכל $a,b\in A$ אם $a{\mathcal {R}}b$ אז $b{\mathcal {R}}a$. היחס טרנזיטיבי: לכל $a,b,c\in A$ אם $a{\mathcal {R}}b$ וגם $b{\mathcal {R}}c$ אז $a{\mathcal {R}}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\}$ הוא קבוצת הזוגות ${\bigl \{}(1,1),(2,2),(3,3){\bigr \}}$.

ב. תהי $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={\bigl \{}\{1,2\},\{3\},\{4,5\}{\bigr \}}$ היא חלוקה של $A$(ודאו זאת).

ב. הקבוצה ${\bigl \{}(1,1),(2,2),(3,3){\bigr \}}$ מהווה חלוקה של $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}$.

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

הגדרה: קבוצת המנה יהי ${\mathcal {R}}$ יחס שקילות על קבוצה $A$. נגדיר קבוצה שתסומן $A/{\mathcal {R}}$ ותקרא קבוצת המנה באופן הבא: קבוצת המנה של $A$ היא קבוצת כל מחלקות השקילות של $A$. כלומר: $A/{\mathcal {R}}={\bigl \{}[a]:a\in A{\bigr \}}$

דוגמה:

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

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

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

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

הוכחה:

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

יהי $a\in A$.

אם $a\in X$ (כאשר $X$ תא בחלוקה) אז ברור כי $a\in X$ ולכן $a\approx a$.

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

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

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

היחס $\approx$ טרנזיטיבי:

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

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

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

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

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

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

משפט: קבוצת המנה היא חלוקה יהי ${\mathcal {R}}$ יחס שקילות על קבוצה לא־ריקה $A$. קבוצת המנה $A/{\mathcal {R}}$ מהווה חלוקה של $A$.

הוכחה:

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

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

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

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

$c{\mathcal {R}}a$ אם ורק אם $c{\mathcal {R}}b$ (טרנזיטיביות ומההנחה כי $a{\mathcal {R}}b$)

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

הראנו כי $c\in [a]\iff c\in [b]$ ולכן מצאנו כי $[a]=[b]$.

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

${\mathcal {R}}$ יחס שקילות, לכן $a{\mathcal {R}}a$ (רפלקסיביות) ולכן $a\in [a]$.

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

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

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

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

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

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

יהיו $[a],[b]\in A/{\mathcal {R}}$ המקיימים $[a]\neq [b]$, הדבר שקול לכך ש־$a{\bcancel {\mathcal {R}}}b$ (לפי (*)).

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

נובע כי קיים $c\in [a]\cap [b]$.

נובע כי $c\in [a]$ וגם $c\in [b]$.

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

מסימטריות נקבל כי $c{\mathcal {R}}a\,\Rightarrow \,a{\mathcal {R}}c$.

מטרנזיטיביות נקבל כי $a{\mathcal {R}}c\land c{\mathcal {R}}b\,\Rightarrow \,a{\mathcal {R}}b$ בסתירה להנחה כי $a{\bcancel {\mathcal {R}}}b$.

לכן $[a]\neq [b]\,\Rightarrow \,[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/{\mathcal {R}}$ (קבוצת המנה: ראה הגדרה) היא חלוקה של $A$.

משפט: יחידות החלוקה הי ${\mathcal {R}}$ יחס שקילות על קבוצה לא־ריקה $A$. קבוצת המנה $A/{\mathcal {R}}$ היא החלוקה היחידה של $A$ אשר היחס ${\mathcal {R}}$ מושרה על ידה.

הוכחה:

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

עתה נוכיח כי $A/{\mathcal {R}}$ היא החלוקה היחידה שמשרה את ${\mathcal {R}}$.

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

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

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

${\mathcal {R}}$ יחס שקילות, נקבל כי $b{\mathcal {R}}b$ (רפלקסיביות) ולכן $b\in [b]$.

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

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

מהגדרת מחלקת השקילות נקבל כי $a{\mathcal {R}}c$ וגם $b{\mathcal {R}}c$.

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

כלומר, בסה"כ $a,b\in [c]\iff a{\mathcal {R}}b$ (כאשר $[c]\in A/{\mathcal {R}}$)

בכך הראינו שהחלוקה $A/{\mathcal {R}}$ משרה את היחס ${\mathcal {R}}$.

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

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

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

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

כלומר $a{\mathcal {R}}b$ אם ורק אם $b\in [a]$ ($A/{\mathcal {R}}$ משרה את ${\mathcal {R}}$).

מצאנו כי $a,b\in X\iff a{\mathcal {R}}b\iff a,b\in [a]$. מכאן $X=[a]$.

הראינו שכל תא $X\in T$ הוא תא של $A/{\mathcal {R}}$ ולכן $T\subseteq A/{\mathcal {R}}$.

כיוון שני: יהי $[a]\in A/{\mathcal {R}}$ תא אשר $a\in A$ שייך אליו.

מתקיים $b\in [a]$ אם ורק אם $a{\mathcal {R}}b$ ($A/{\mathcal {R}}$ משרה את ${\mathcal {R}}$).

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

הראנו כי $a,b\in [a]\iff a{\mathcal {R}}b\iff a,b\in T$.

הראינו שכל תא $[a]\in A/{\mathcal {R}}$ הוא תא של $T$ ולכן $A/{\mathcal {R}}\subseteq T$.

משילוב הכיוונים מצאנו כי $T=A/{\mathcal {R}}$.

מ־(1) ומ־(2) הוכחנו כי $A/{\mathcal {R}}$ היא החלוקה היחידה שמשרה את היחס.

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

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

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

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

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

שימושים

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

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

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

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

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

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

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

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

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

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

יחסי שקילות

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