דוגמאות ליחסי שקילות
עריכה
א. יחס השוויון (=) על כל קבוצה
A
{\displaystyle A}
הוא יחס שקילות:
לכל
a
∈
A
{\displaystyle a\in A}
מתקיים
a
=
a
{\displaystyle a=a}
.
לכל
a
,
b
∈
A
{\displaystyle a,b\in A}
אם
a
=
b
{\displaystyle a=b}
אז
b
=
a
{\displaystyle b=a}
.
לכל
a
,
b
,
c
∈
A
{\displaystyle a,b,c\in A}
אם
a
=
b
{\displaystyle a=b}
וגם
b
=
c
{\displaystyle b=c}
אז
a
=
c
{\displaystyle a=c}
.
יחס השוויון על הקבוצה
A
=
{
1
,
2
,
3
}
{\displaystyle A=\{1,2,3\}}
הוא קבוצת הזוגות
{
(
1
,
1
)
,
(
2
,
2
)
,
(
3
,
3
)
}
{\displaystyle {\bigl \{}(1,1),(2,2),(3,3){\bigr \}}}
.
ב. תהי
A
{\displaystyle A}
קבוצה של קבוצות. יהי היחס
≅
{\displaystyle \cong }
על הקבוצה
A
{\displaystyle A}
שמוגדר כך:
לכל
X
,
Y
∈
A
{\displaystyle X,Y\in A}
מתקיים
X
≅
Y
{\displaystyle X\cong Y}
אם ורק אם קיימת בייקציה (פונקציה חד-חד ערכית ועל)
f
:
A
→
B
{\displaystyle f:A\to B}
.
היחס
≅
{\displaystyle \cong }
הוא יחס שקילות:
לכל קבוצה
X
∈
A
{\displaystyle X\in A}
פונקציית הזהות
f
(
a
)
=
a
{\displaystyle f(a)=a}
מ־
A
{\displaystyle A}
ל־
A
{\displaystyle A}
היא בייקציה ולכן
X
≅
X
{\displaystyle X\cong X}
.
לכל
X
,
Y
∈
A
{\displaystyle X,Y\in A}
אם
X
≅
Y
{\displaystyle X\cong {}Y}
, כלומר יש בייקציה
f
:
X
→
Y
{\displaystyle f:X\to Y}
אז גם
f
−
1
:
Y
→
X
{\displaystyle f^{-1}:Y\to X}
היא בייקציה ולכן
Y
≅
X
{\displaystyle Y\cong X}
.
לכל
X
,
Y
,
Z
∈
A
{\displaystyle X,Y,Z\in A}
אם
X
≅
Y
{\displaystyle X\cong Y}
וגם
Y
≅
Z
{\displaystyle Y\cong Z}
, כלומר יש בייקציה
f
:
X
→
Y
{\displaystyle f:X\to Y}
וגם יש בייקציה
g
:
Y
→
Z
{\displaystyle g:Y\to Z}
אז גם ההרכבה
g
∘
f
:
X
→
Z
{\displaystyle g\circ f:X\to Z}
היא בייקציה ולכן
X
≅
Z
{\displaystyle X\cong Z}
.
הדוגמה הראשונה היא טריוויאלית. בעוד הדוגמה השנייה קשה יותר (מומלץ לקרוא בעיון ולנסות להבין). עוד נחזור לדוגמאות אלו אחרי ההגדרה הבאה:
הערה: קבוצה
X
∈
S
{\displaystyle X\in S}
(השייכת לחלוקה) תקרא תא של החלוקה. כלומר, אם
x
∈
X
{\displaystyle x\in X}
נאמר שהאיבר
x
{\displaystyle x}
שייך לתא
X
{\displaystyle X}
של החלוקה
S
{\displaystyle S}
.
א. נתבונן בקבוצה
A
=
{
1
,
2
,
3
,
4
,
5
}
{\displaystyle A=\{1,2,3,4,5\}}
. הקבוצה
B
=
{
{
1
,
2
}
,
{
3
}
,
{
4
,
5
}
}
{\displaystyle B={\bigl \{}\{1,2\},\{3\},\{4,5\}{\bigr \}}}
היא חלוקה של
A
{\displaystyle A}
(ודאו זאת).
ב. הקבוצה
{
(
1
,
1
)
,
(
2
,
2
)
,
(
3
,
3
)
}
{\displaystyle {\bigl \{}(1,1),(2,2),(3,3){\bigr \}}}
מהווה חלוקה של
A
=
{
1
,
2
,
3
}
{\displaystyle A=\{1,2,3\}}
(ראה דוגמה א' בדוגמאות ליחסי שקילות).
ג. הקבוצה
{
3
n
:
n
∈
N
}
∪
{
3
n
+
1
:
n
∈
N
}
∪
{
3
n
+
2
:
n
∈
N
}
{\displaystyle \{3n:n\in \mathbb {N} \}\cup \{3n+1:n\in \mathbb {N} \}\cup \{3n+2:n\in \mathbb {N} \}}
היא חלוקה של
N
{\displaystyle \mathbb {N} }
.
הקבוצה
{
(
1
,
1
)
,
(
2
,
2
)
,
(
3
,
3
)
}
{\displaystyle {\bigl \{}(1,1),(2,2),(3,3){\bigr \}}}
היא קבוצת המנה של
{
1
,
2
,
3
}
/
=
{\displaystyle \{1,2,3\}/=}
(ראה דוגמה א' בדוגמאות ליחסי שקילות ודוגמה ב' בדוגמאות לחלוקה).
הגדרנו הגדרות רבות, אך לא עולה מהן בהכרח קשר ליחס השקילות. ראשית, נביא משפט שיעזור לנו לחבר בין כל ההגדרות שמקודם:
הוכחה:
היחס
≈
{\displaystyle \approx }
רפלקסיבי:
יהי
a
∈
A
{\displaystyle a\in A}
.
אם
a
∈
X
{\displaystyle a\in X}
(כאשר
X
{\displaystyle X}
תא בחלוקה) אז ברור כי
a
∈
X
{\displaystyle a\in X}
ולכן
a
≈
a
{\displaystyle a\approx a}
.
היחס
≈
{\displaystyle \approx }
סימטרי:
יהיו
a
,
b
∈
A
{\displaystyle a,b\in A}
.
אם
a
≈
b
{\displaystyle a\approx b}
, כלומר
a
,
b
∈
X
{\displaystyle a,b\in X}
(כאשר
X
{\displaystyle X}
תא בחלוקה) אז ברור כי
b
,
a
∈
X
{\displaystyle b,a\in X}
ולכן
b
≈
a
{\displaystyle b\approx a}
.
היחס
≈
{\displaystyle \approx }
טרנזיטיבי:
יהיו
a
,
b
,
c
∈
A
{\displaystyle a,b,c\in A}
.
אם
a
≈
b
{\displaystyle a\approx b}
וגם
b
≈
c
{\displaystyle b\approx c}
, כלומר
a
,
b
∈
X
{\displaystyle a,b\in X}
וגם
b
,
c
∈
Y
{\displaystyle b,c\in Y}
(כאשר
X
,
Y
{\displaystyle X,Y}
תאים בחלוקה) אז:
b
∈
X
∧
b
∈
Y
⇒
X
=
Y
{\displaystyle b\in X\land b\in Y\,\Rightarrow \,X=Y}
(ראה הגדרת החלוקה) לכן
a
,
c
∈
X
{\displaystyle a,c\in X}
ולכן
a
≈
c
{\displaystyle a\approx c}
.
הוכחנו כי
≈
{\displaystyle \approx }
הוא יחס רפלקסיבי, סימטרי וטרנזיטיבי ובכך הוכחנו כי הוא יחס שקילות.
כפי שמצביע שם המשפט: ליחס זה אנו קוראים היחס שמושרה על ידי החלוקה או שאנו אומרים החלוקה משרה את היחס .
עכשיו יש בידינו כלי, שדרכו נוכל לחבר בין כל ההגדרות שהובאו ולהראות מדוע יחסי השקילות כה חשובים:
משפט: קבוצת המנה היא חלוקה
יהי
R
{\displaystyle {\mathcal {R}}}
יחס שקילות על קבוצה לא־ריקה
A
{\displaystyle A}
.
קבוצת המנה
A
/
R
{\displaystyle A/{\mathcal {R}}}
מהווה חלוקה של
A
{\displaystyle A}
.
הוכחה:
במהלך ההוכחה נסמן
[
a
]
{\displaystyle [a]}
מחלקת השקילות (ראו הגדרה) של
a
{\displaystyle a}
.
(*): נוכיח
a
R
b
{\displaystyle a{\mathcal {R}}b}
אם ורק אם
[
a
]
=
[
b
]
{\displaystyle [a]=[b]}
.
כיוון ראשון נניח כי
a
R
b
{\displaystyle a{\mathcal {R}}b}
. יהי
c
∈
A
{\displaystyle c\in A}
.
c
∈
[
a
]
{\displaystyle c\in [a]}
אם ורק אם
c
R
a
{\displaystyle c{\mathcal {R}}a}
(מהגדרת מחלקת השקילות)
c
R
a
{\displaystyle c{\mathcal {R}}a}
אם ורק אם
c
R
b
{\displaystyle c{\mathcal {R}}b}
(טרנזיטיביות ומההנחה כי
a
R
b
{\displaystyle a{\mathcal {R}}b}
)
לבסוף,
c
R
b
{\displaystyle c{\mathcal {R}}b}
אם ורק אם
c
∈
[
b
]
{\displaystyle c\in [b]}
(הגדרת מחלקת השקילות).
הראנו כי
c
∈
[
a
]
⟺
c
∈
[
b
]
{\displaystyle c\in [a]\iff c\in [b]}
ולכן מצאנו כי
[
a
]
=
[
b
]
{\displaystyle [a]=[b]}
.
כיוון שני: נניח כי
[
a
]
=
[
b
]
{\displaystyle [a]=[b]}
.
R
{\displaystyle {\mathcal {R}}}
יחס שקילות, לכן
a
R
a
{\displaystyle a{\mathcal {R}}a}
(רפלקסיביות) ולכן
a
∈
[
a
]
{\displaystyle a\in [a]}
.
מההנחה כי
[
a
]
=
[
b
]
{\displaystyle [a]=[b]}
נקבל כי
a
∈
[
b
]
{\displaystyle a\in [b]}
.
לכן, מהגדרת מחלקת השקילות נקבל כי
a
R
b
{\displaystyle a{\mathcal {R}}b}
.
בכך הוכחנו את (*).
(1) נוכיח שלכל
a
∈
A
{\displaystyle a\in A}
מתקיים כי
[
a
]
≠
∅
{\displaystyle [a]\neq \varnothing }
:
לכל
a
∈
A
{\displaystyle a\in A}
מתקיים
a
R
a
{\displaystyle a{\mathcal {R}}a}
(רפלקסיביות) מכך נובע כי
a
∈
[
a
]
{\displaystyle a\in [a]}
ולכן
[
a
]
≠
∅
{\displaystyle [a]\neq \varnothing }
.
(2) נוכיח שאם
[
a
]
≠
[
b
]
{\displaystyle [a]\neq [b]}
(תאים שונים של החלוקה) אז
[
a
]
∩
[
b
]
≠
∅
{\displaystyle [a]\cap [b]\neq \varnothing }
:
יהיו
[
a
]
,
[
b
]
∈
A
/
R
{\displaystyle [a],[b]\in A/{\mathcal {R}}}
המקיימים
[
a
]
≠
[
b
]
{\displaystyle [a]\neq [b]}
, הדבר שקול לכך ש־
a
R
b
{\displaystyle a{\bcancel {\mathcal {R}}}b}
(לפי (*)).
נניח בשלילה כי
[
a
]
∩
[
b
]
≠
∅
{\displaystyle [a]\cap [b]\neq \varnothing }
.
נובע כי קיים
c
∈
[
a
]
∩
[
b
]
{\displaystyle c\in [a]\cap [b]}
.
נובע כי
c
∈
[
a
]
{\displaystyle c\in [a]}
וגם
c
∈
[
b
]
{\displaystyle c\in [b]}
.
לכן, מהגדרת מחלקת השקילות מצאנו כי
c
R
a
{\displaystyle c{\mathcal {R}}a}
וגם
c
R
b
{\displaystyle c{\mathcal {R}}b}
.
מסימטריות נקבל כי
c
R
a
⇒
a
R
c
{\displaystyle c{\mathcal {R}}a\,\Rightarrow \,a{\mathcal {R}}c}
.
מטרנזיטיביות נקבל כי
a
R
c
∧
c
R
b
⇒
a
R
b
{\displaystyle a{\mathcal {R}}c\land c{\mathcal {R}}b\,\Rightarrow \,a{\mathcal {R}}b}
בסתירה להנחה כי
a
R
b
{\displaystyle a{\bcancel {\mathcal {R}}}b}
.
לכן
[
a
]
≠
[
b
]
⇒
[
a
]
∩
[
b
]
=
∅
{\displaystyle [a]\neq [b]\,\Rightarrow \,[a]\cap [b]=\varnothing }
.
(3): נראה כי
A
=
⋃
a
∈
A
[
a
]
{\displaystyle A=\bigcup _{a\in A}[a]}
.
כיוון ראשון: יהי
a
∈
A
{\displaystyle a\in A}
.
מהגדרת מחלקת השקילות, נקבל
[
a
]
⊆
A
{\displaystyle [a]\subseteq A}
ולכן מתקיים כי
⋃
a
∈
A
[
a
]
⊆
A
{\displaystyle \bigcup _{a\in A}[a]\subseteq A}
.
כיוון שני: יהי
a
∈
A
{\displaystyle a\in A}
.
נקבל
a
∈
[
a
]
{\displaystyle a\in [a]}
(כפי שהראנו ב־(2)) ולכן
a
∈
⋃
a
∈
A
[
a
]
{\displaystyle a\in \bigcup _{a\in A}[a]}
.
בכך הראנו כי
A
⊆
⋃
a
∈
A
[
a
]
{\displaystyle A\subseteq \bigcup _{a\in A}[a]}
.
משילוב הכיוונים קיבלנו כי
A
=
⋃
a
∈
A
[
a
]
{\displaystyle A=\bigcup _{a\in A}[a]}
.
לפי (1), (2), (3) הראינו שכל מחלקת שקילות אינה ריקה, הראנו שכל שתי מחלקות שקילות שונות זרות והראנו שאיחוד כל מחלקות השקילות הוא
A
{\displaystyle A}
.
לכן, מהגדרת החלוקה, מצאנו כי
A
/
R
{\displaystyle A/{\mathcal {R}}}
(קבוצת המנה : ראה הגדרה) היא חלוקה של
A
{\displaystyle A}
.
הוכחה:
במשפט: קבוצת המנה היא חלוקה, הוכחנו כי
A
/
R
{\displaystyle A/{\mathcal {R}}}
היא חלוקה של
A
{\displaystyle A}
.
עתה נוכיח כי
A
/
R
{\displaystyle A/{\mathcal {R}}}
היא החלוקה היחידה שמשרה את
R
{\displaystyle {\mathcal {R}}}
.
(1) נוכיח כי
A
/
R
{\displaystyle A/{\mathcal {R}}}
היא אכן חלוקה שמשרה את
R
{\displaystyle {\mathcal {R}}}
, כלומר נראה כי
a
R
b
{\displaystyle a{\mathcal {R}}b}
אם ורק אם
a
,
b
{\displaystyle a,b}
באותו התא של
A
/
R
{\displaystyle A/{\mathcal {R}}}
:
כיוון ראשון: נניח כי
a
R
b
{\displaystyle a{\mathcal {R}}b}
.
נובע כי
a
∈
[
b
]
{\displaystyle a\in [b]}
(הגדרת מחלקת השקילות).
R
{\displaystyle {\mathcal {R}}}
יחס שקילות, נקבל כי
b
R
b
{\displaystyle b{\mathcal {R}}b}
(רפלקסיביות) ולכן
b
∈
[
b
]
{\displaystyle b\in [b]}
.
מצאנו כי
a
∈
[
b
]
{\displaystyle a\in [b]}
וגם
b
∈
[
b
]
{\displaystyle b\in [b]}
ובכך הראינו כי
a
,
b
{\displaystyle a,b}
באותו תא.
כיוון שני: נניח כי
a
,
b
{\displaystyle a,b}
באותו התא של
A
/
R
{\displaystyle A/{\mathcal {R}}}
, כלומר
a
,
b
∈
[
c
]
{\displaystyle a,b\in [c]}
.
מהגדרת מחלקת השקילות נקבל כי
a
R
c
{\displaystyle a{\mathcal {R}}c}
וגם
b
R
c
{\displaystyle b{\mathcal {R}}c}
.
לכן נקבל
a
R
b
{\displaystyle a{\mathcal {R}}b}
(סימטריה, וטרנזיטיביות של יחס השקילות
R
{\displaystyle {\mathcal {R}}}
).
כלומר, בסה"כ
a
,
b
∈
[
c
]
⟺
a
R
b
{\displaystyle a,b\in [c]\iff a{\mathcal {R}}b}
(כאשר
[
c
]
∈
A
/
R
{\displaystyle [c]\in A/{\mathcal {R}}}
)
בכך הראינו שהחלוקה
A
/
R
{\displaystyle A/{\mathcal {R}}}
משרה את היחס
R
{\displaystyle {\mathcal {R}}}
.
(2): נוכיח כי זו החלוקה היחידה שמשרה את
R
{\displaystyle {\mathcal {R}}}
.
תהי
T
{\displaystyle T}
חלוקה שמשרה את
R
{\displaystyle {\mathcal {R}}}
, כלומר
a
R
b
{\displaystyle a{\mathcal {R}}b}
אם ורק אם
a
,
b
{\displaystyle a,b}
באותו התא של
T
{\displaystyle T}
.
כייון ראשון: יהי
X
{\displaystyle X}
תא בחלוקה
T
{\displaystyle T}
.
X
≠
∅
{\displaystyle X\neq \varnothing }
ולכן קיים
a
∈
X
{\displaystyle a\in X}
. לכל
b
∈
A
{\displaystyle b\in A}
מתקיים
b
∈
X
{\displaystyle b\in X}
אם ורק אם
a
R
b
{\displaystyle a{\mathcal {R}}b}
(
T
{\displaystyle T}
משרה את
R
{\displaystyle {\mathcal {R}}}
).
כלומר
a
R
b
{\displaystyle a{\mathcal {R}}b}
אם ורק אם
b
∈
[
a
]
{\displaystyle b\in [a]}
(
A
/
R
{\displaystyle A/{\mathcal {R}}}
משרה את
R
{\displaystyle {\mathcal {R}}}
).
מצאנו כי
a
,
b
∈
X
⟺
a
R
b
⟺
a
,
b
∈
[
a
]
{\displaystyle a,b\in X\iff a{\mathcal {R}}b\iff a,b\in [a]}
. מכאן
X
=
[
a
]
{\displaystyle X=[a]}
.
הראינו שכל תא
X
∈
T
{\displaystyle X\in T}
הוא תא של
A
/
R
{\displaystyle A/{\mathcal {R}}}
ולכן
T
⊆
A
/
R
{\displaystyle T\subseteq A/{\mathcal {R}}}
.
כיוון שני: יהי
[
a
]
∈
A
/
R
{\displaystyle [a]\in A/{\mathcal {R}}}
תא אשר
a
∈
A
{\displaystyle a\in A}
שייך אליו.
מתקיים
b
∈
[
a
]
{\displaystyle b\in [a]}
אם ורק אם
a
R
b
{\displaystyle a{\mathcal {R}}b}
(
A
/
R
{\displaystyle A/{\mathcal {R}}}
משרה את
R
{\displaystyle {\mathcal {R}}}
).
כמו כן,
a
R
b
{\displaystyle a{\mathcal {R}}b}
אם ורק אם
b
∈
X
{\displaystyle b\in X}
(
T
{\displaystyle T}
משרה את
R
{\displaystyle {\mathcal {R}}}
).
הראנו כי
a
,
b
∈
[
a
]
⟺
a
R
b
⟺
a
,
b
∈
T
{\displaystyle a,b\in [a]\iff a{\mathcal {R}}b\iff a,b\in T}
.
הראינו שכל תא
[
a
]
∈
A
/
R
{\displaystyle [a]\in A/{\mathcal {R}}}
הוא תא של
T
{\displaystyle T}
ולכן
A
/
R
⊆
T
{\displaystyle A/{\mathcal {R}}\subseteq T}
.
משילוב הכיוונים מצאנו כי
T
=
A
/
R
{\displaystyle T=A/{\mathcal {R}}}
.
מ־(1) ומ־(2) הוכחנו כי
A
/
R
{\displaystyle A/{\mathcal {R}}}
היא החלוקה היחידה שמשרה את היחס.
במשפטים אלו הוכחנו שני דברים חשובים:
הראשון, קבוצת המנה של קבוצה היא חלוקה .
השני, קבוצת המנה היא החלוקה היחידה שמשרה את יחס השקילות שמגדיר אותה.
משילוב המשפטים ניתן לראות, שאם נקבל חלוקה - אז נוכל להשרות דרכה יחס שקילות.
ואם נקבל יחס שקילות, נוכל למצוא את החלוקה שמשרה אותו; היא פשוט קבוצת המנה.
מכאן, נשוב לדוגמה ב' בדוגמאות ליחס שקילות :
אחת הדרכים (אם כי הפחות שימושית) בה מגדירים באופן פורמלי עוצמה של קבוצה, היא לקחת את מחלקת כל הקבוצות, ולהסתכל על מחלקת המנה שלה (הגדרה כמעט זהה לקבוצת המנה) ביחס ליחס
≅
{\displaystyle \cong }
שהוגדר בדוגמה.
כלומר, אנו יודעים כי לשתי קבוצות יש אותה עוצמה אם יש ביניהן בייקציה. לכן, בהנתן קבוצה
A
{\displaystyle A}
נוכל לומר שהעוצמה שלה היא פשוט מחלקת השקילות
[
A
]
{\displaystyle [A]}
ביחס ל־
≅
{\displaystyle \cong }
.
ואכן, אנו נאמר כי ל־
A
,
B
{\displaystyle A,B}
יש אותה עוצמה אם
B
∈
[
A
]
{\displaystyle B\in [A]}
.
כמו כן, הגדרות רבות במתמטיקה (למשל של סודרים ) ניתנות על ידי מחלקות שקילות והקשר שביניהן לבין חלוקה.
דוגמאות לאובייקטים מתמטיים שנהוג להגדיר על ידי יחס שקילות ועל ידי קבוצת המנה הם המספרים השלמים והרציונליים.
כדוגמה נוספת למחלקת שקילות :
אפשר להסתכל על דמיון ועל חפיפת משולשים כיחסי שקילות.
נסו למצוא תאור מדוייק של מחלקות השקילות של יחס הדמיון בין משולשים.
חישבו גם מה משותף ביחס החפיפה בין משולשים, ליחס השוויון בין קבוצות (ראה דוגמה א' בדוגמות ליחס שקילות).