חפיפה היא דוגמה ליחס שקילות. שני המשולשים השמאליים ביותר הם חופפים, בעוד המשולש השלישי והרביעי אינם תואמים לאף משולש אחר המוצג כאן. לפיכך, שני המשולשים הראשונים נמצאים באותה מחלקת שקילות, בעוד שהמשולש השלישי והרביעי נמצאים כל אחד במחלקת השקילות שלו.במתמטיקה , מחלקות שקילות היא דרך לחלק איברים של קבוצה כלשהי שקיים יחס שקילות המוגדר עליה. מחלקות שקילות אלו בנויות כך שאיברים שייכים לאותה מחלקת שקילות אם ורק אם הם מתייחסים זה לזה.
הגדרה
נתונה קבוצה
A
{\displaystyle A}
ויחס שקילות
R
{\displaystyle R}
על
A
{\displaystyle A}
. מחלקת שקילות של איבר
a
{\displaystyle a}
ב-
A
{\displaystyle A}
היא קבוצת כל האיברים השקולים ל-
a
{\displaystyle a}
, מסומנת
[
a
]
{\displaystyle [a]}
או
[
a
]
R
{\displaystyle [a]_{R}}
ומוגדרת כקבוצת כל האיברים המתייחסים ל-
a
{\displaystyle a}
ביחס
R
{\displaystyle R}
. כלומר[ 1] :
[
a
]
R
=
{
x
∈ ∈ -->
A
:
a
R
x
}
{\displaystyle [a]_{R}=\{x\in A:aRx\}}
מחלקות השקילות יוצרות חלוקה של
A
{\displaystyle A}
. חלוקה זו היא קבוצת מחלקות השקילות, הנקראת קבוצת המנה או מרחב המנה של
A
{\displaystyle A}
על ידי
R
{\displaystyle R}
ומסומנת
A
/
R
=
{
[
a
]
:
a
∈ ∈ -->
A
}
{\displaystyle A/R=\{[a]:a\in A\}}
. איחוד כל מחלקות השקילות הוא הקבוצה
A
{\displaystyle A}
עצמה, כלומר
⋃ ⋃ -->
A
/
R
=
A
{\displaystyle \bigcup A/R=A}
.
סימון
ייצוג בגרף של דוגמה של 7 מחלקות שקילות שונות.
הסימון
[
a
]
{\displaystyle [a]}
טוב כאשר נעשה שימוש רק ביחס שקילות אחד. אם יש יותר מיחס שקילות אחד, אז עלינו להבחין בין מחלקות השקילות לפי היחס. לעיתים קרובות נשתמש בסימונים:
R
[
a
]
{\displaystyle R[a]}
או
[
a
]
R
{\displaystyle [a]_{R}}
עבור מחלקת השקילות של
a
{\displaystyle a}
שנקבעת על ידי היחס
R
{\displaystyle R}
. בכל מקרה, תמיד כשעובדים עם יחס שקילות כלשהו על קבוצה
A
{\displaystyle A}
, אם
a
∈ ∈ -->
A
{\displaystyle a\in A}
אז מחלקת השקילות
[
a
]
{\displaystyle [a]}
היא תת-קבוצה של
A
{\displaystyle A}
.
משפט המבנה
כל 2 מחלקות שקילות הן שוות או זרות . אם 2 איברים בקבוצה כלשהי מתייחסים זה לזה, אז הם שייכים לאותה מחלקת שקילות. אם מחלקות השקילות שונות, אז אין להם שום איבר משותף. באופן פורמלי:
a
∈ ∈ -->
[
a
]
R
{\displaystyle a\in [a]_{R}}
a
R
b
⟺ ⟺ -->
[
a
]
R
=
[
b
]
R
{\displaystyle aRb\iff [a]_{R}=[b]_{R}}
[
a
]
R
∩ ∩ -->
[
b
]
R
=
∅ ∅ -->
⟺ ⟺ -->
[
a
]
R
≠ ≠ -->
[
b
]
R
{\displaystyle [a]_{R}\cap [b]_{R}=\emptyset \iff [a]_{R}\neq [b]_{R}}
ניתן להוכיח משפט זה באמצעות התכונות של יחס שקילות: רפלקסיביות , סימטריות וטרנזיטיביות [ 2] [ 3] .
הוכחה
תהי
A
{\displaystyle A}
קבוצה לא-ריקה ונניח
R
{\displaystyle R}
יחס שקילות על
A
{\displaystyle A}
.
יהי
a
∈ ∈ -->
A
{\displaystyle a\in A}
. מרפלקסיביות
a
R
a
{\displaystyle aRa}
. אז מהגדרת מחלקת שקילות
a
∈ ∈ -->
[
a
]
{\displaystyle a\in [a]}
.
הוכחה דו-כיוונית:
⇐ ⇐ -->
{\displaystyle \Leftarrow }
: יהיו
a
,
b
∈ ∈ -->
A
{\displaystyle a,b\in A}
, נניח
a
R
b
{\displaystyle aRb}
. נראה הכלה דו-כיוונית:
⇐ ⇐ -->
{\displaystyle \Leftarrow }
: יהי
x
∈ ∈ -->
[
a
]
{\displaystyle x\in [a]}
, לכן
a
R
x
{\displaystyle aRx}
. מסימטריות
b
R
a
{\displaystyle bRa}
, מטרנזיטיביות
b
R
x
{\displaystyle bRx}
ולכן
x
∈ ∈ -->
[
b
]
{\displaystyle x\in [b]}
. אז מהגדרת הכלה
[
a
]
⊆ ⊆ -->
[
b
]
{\displaystyle [a]\subseteq [b]}
.
⇒ ⇒ -->
{\displaystyle \Rightarrow }
: יהי
x
∈ ∈ -->
[
b
]
{\displaystyle x\in [b]}
, לכן
b
R
x
{\displaystyle bRx}
. מטרנזיטיביות
a
R
x
{\displaystyle aRx}
ולכן
x
∈ ∈ -->
[
a
]
{\displaystyle x\in [a]}
. אז מהגדרת הכלה
[
b
]
⊆ ⊆ -->
[
a
]
{\displaystyle [b]\subseteq [a]}
.
מהכלה דו-כיוונית
[
a
]
=
[
b
]
{\displaystyle [a]=[b]}
.
⇒ ⇒ -->
{\displaystyle \Rightarrow }
: יהיו
a
,
b
∈ ∈ -->
A
{\displaystyle a,b\in A}
ונניח
[
a
]
=
[
b
]
{\displaystyle [a]=[b]}
. מ-(1) נובע
a
∈ ∈ -->
[
a
]
{\displaystyle a\in [a]}
ומכיוון ששתי הקבוצות שוות נקבל כי
a
∈ ∈ -->
[
b
]
{\displaystyle a\in [b]}
, כלומר
b
R
a
{\displaystyle bRa}
ומסימטריות
a
R
b
{\displaystyle aRb}
.
הוכחה דו-כיוונית:
⇒ ⇒ -->
{\displaystyle \Rightarrow }
: יהיו
a
,
b
∈ ∈ -->
A
{\displaystyle a,b\in A}
ונניח
[
a
]
R
∩ ∩ -->
[
b
]
R
=
∅ ∅ -->
{\displaystyle [a]_{R}\cap [b]_{R}=\emptyset }
. מ-(1)
a
∈ ∈ -->
[
a
]
R
{\displaystyle a\in [a]_{R}}
ולכן
[
a
]
R
≠ ≠ -->
∅ ∅ -->
{\displaystyle [a]_{R}\neq \emptyset }
. מההנחה
[
a
]
R
∩ ∩ -->
[
b
]
R
=
∅ ∅ -->
{\displaystyle [a]_{R}\cap [b]_{R}=\emptyset }
ומכך ש-
a
∈ ∈ -->
[
a
]
R
{\displaystyle a\in [a]_{R}}
נובע
a
∉ ∉ -->
[
b
]
R
{\displaystyle a\notin [b]_{R}}
. אז לפי הגדרת השוויון
[
a
]
R
≠ ≠ -->
[
b
]
R
{\displaystyle [a]_{R}\neq [b]_{R}}
.
⇐ ⇐ -->
{\displaystyle \Leftarrow }
: יהיו
a
,
b
∈ ∈ -->
A
{\displaystyle a,b\in A}
ונניח
[
a
]
R
≠ ≠ -->
[
b
]
R
{\displaystyle [a]_{R}\neq [b]_{R}}
. נניח בשלילה
[
a
]
R
∩ ∩ -->
[
b
]
R
≠ ≠ -->
∅ ∅ -->
{\displaystyle [a]_{R}\cap [b]_{R}\neq \emptyset }
. אזי מהגדרת חיתוך קיים
x
{\displaystyle x}
כך ש
x
∈ ∈ -->
[
a
]
{\displaystyle x\in [a]}
וגם
x
∈ ∈ -->
[
b
]
{\displaystyle x\in [b]}
. מכך, ומסעיף 2 למשפט המבנה, נובע
[
x
]
R
=
[
b
]
R
{\displaystyle [x]_{R}=[b]_{R}}
וגם
[
x
]
R
=
[
a
]
R
{\displaystyle [x]_{R}=[a]_{R}}
. אז מטרניזטיביות השוויון
[
a
]
R
=
[
b
]
R
{\displaystyle [a]_{R}=[b]_{R}}
, וזאת סתירה להנחה. אזי
[
a
]
R
∩ ∩ -->
[
b
]
R
=
∅ ∅ -->
{\displaystyle [a]_{R}\cap [b]_{R}=\emptyset }
.
דוגמאות
יחס שקילות מודולו – ניתן לחלק את כל המספרים השלמים ל-
n
{\displaystyle n}
מחלקות שקילות באמצעות השארית מודולו
n
{\displaystyle n}
.
קישורים חיצוניים
הערות שוליים