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

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

הגדרות

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

א. יחס השוויון (=) על כל קבוצה $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$.

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

הערה: קבוצה $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}$.

דוגמה:

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

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

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

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

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

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

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

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

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

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

שימושים

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

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

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

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

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

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

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

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

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