מחלקת שקילות

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

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

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

ייצוג בגרף של דוגמה של 7 מחלקות שקילות שונות.

מחלקות השקילות יוצרות חלוקה של $A$. חלוקה זו היא קבוצת מחלקות השקילות, הנקראת קבוצת המנה או מרחב המנה של $A$ על ידי $R$ ומסומנת ב-$A/R$. כלומר, $A/R=\{[a]|a\in R\}$. איחוד כל מחלקות השקילות הוא הקבוצה $A$ עצמה, כלומר: $\bigcup A/R=A$.

הגדרה

בעבור האיבר $a$ ביחס $R$ מעל הקבוצה $A$, מחלקת השקילות של $a$ תהיה: $[a]=\{b\in A|aRb\}$.

סימון

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

משפט המבנה

כל 2 מחלקות שקילות הן שוות או זרות. אם 2 איברים בקבוצה כלשהי מתייחסים זה לזה, אז הם שייכים לאותה מחלקת שקילות. אם מחלקות השקילות שונות, אז אין להם שום איבר משותף. באופן פורמלי:

1. $a\in [a]_{R}$
2. $aRb\iff [a]_{R}=[b]_{R}$
3. $[a]_{R}\cap [b]_{R}=\emptyset \iff [a]_{R}\neq [b]_{R}$

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

הוכחה

פרק זה לוקה בחסר. אנא תרמו למכלול והשלימו אותו.

תהי $A$ קבוצה לא ריקה ונניח $R$ יחס שקילות על $A$.

1. יהי $a\in A$. מכיוון ש-$R$ הוא יחס שקילות מעל $A$, הוא רפלקסיבי. לפיכך, $aRa$ אז מהגדרת מחלקת שקילות: $a\in [a]$.
2. הוכחה דו כיוונית:

$\Leftarrow$: יהיו $a,b\in A$, נניח $aRb$. נראה הכלה דו-כיוונית:

$\Leftarrow$: יהיו $a,b\in A$, נניח $aRb$. יהי $x\in [a]$, אז לפי הגדרה $aRx$ ומסימטריה של $R$ מתקיים $xRa$. הנחנו $aRb$ אז מטרנזיטיביות של $R$ מתקיים $xRb$ אז מהגדרה $x\in [b]$. אז מהגדרת הכלה $[a]\subseteq [b]$.

$\Rightarrow$: $y\in [b]$, אז לפי הגדרה $bRy$. הנחנו $aRb$ אז מטרנזיטיביות של $R$ מתקיים $aRy$ ולכן $y\in [a]$ אז מהגדרת הכלה $[b]\subseteq [a]$.

אז מהכלה דו-כיוונית $[a]=[b]$.

$\Rightarrow$: יהיו $a,b\in A$ ונניח $[a]=[b]$. מ-(1) נובע $a\in [a]$ ומכיוון ששתי הקבוצות שוות, זה אומר לנו ש-$a\in [b]$ . אז לפי ההגדרה $aRb$ .

1. יהיו $a,b\in A$. נניח $[a]\cap [b]\neq \emptyset$, לכן קיים $x\in [a]$ וגם $x\in [b]$. אז מ-(1) מתקיים: $[x]=[a]$ וגם $[x]=[b]$ אז מטרנזיטיביות יחס השוויון מתקיים $[a]=[b]$. לכן $[a]=[b]$ או ${\displaystyle [a]\cap [b]=\emptyset }$.

דוגמאות

• יחס שקילות מודולו - ניתן לחלק את כל המספרים השלמים ל-$n$ מחלקות שקילות באמצעות השארית מודולו $n$.

קישורים חיצוניים

• פרופ' טד סאנדסטרום, Mathematical Reasoning: Writing and Proof, הוצאת אוניברסיטת גראנד ואלי סטייט, ‏5 בספטמבר 2021 (עדכון אחרון) (באנגלית)
• מחלקת שקילות, בביצוע ד"ר גדי אלכסנדרוביץ' ב"הטכניון מלמדים", סרטון באתר יוטיוב (אורך: 5:56)
• מחלקת שקילות, באתר MathWorld (באנגלית)

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

35120704מחלקת שקילות