דוגמאות ליחסי שקילות
עריכה
א. יחס השוויון (=) על כל קבוצה
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 \{(1,1),(2,2),(3,3)\}}
.
ב. תהי
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=\{\{1,2\},\{3\},\{4,5\}\}}
היא חלוקה של
A
{\displaystyle A}
(ודאו זאת).
ב. הקבוצה
{
(
1
,
1
)
,
(
2
,
2
)
,
(
3
,
3
)
}
{\displaystyle \{(1,1),(2,2),(3,3)\}}
מהווה חלוקה של
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} }
.
הגדרה: קבוצת המנה
יהי
D
{\displaystyle {\mathfrak {D}}}
יחס שקילות על קבוצה
A
{\displaystyle A}
. נגדיר קבוצה שתסומן
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
ותקרא קבוצת המנה באופן הבא:
קבוצת המנה של
A
{\displaystyle A}
, היא קבוצת כל מחלקות השקילות של
A
{\displaystyle A}
. כלומר:
A
╱
D
=
{
[
a
]
|
a
∈
A
}
{\displaystyle A\diagup {\mathfrak {D}}=\{[a]|a\in {}A\}}
הקבוצה
{
(
1
,
1
)
,
(
2
,
2
)
,
(
3
,
3
)
}
{\displaystyle \{(1,1),(2,2),(3,3)\}}
היא קבוצת המנה של
{
1
,
2
,
3
}
╱
=
{\displaystyle \{1,2,3\}\diagup {}=}
(ראה דוגמה א' בדוגמאות ליחסי שקילות ודוגמה ב' בדוגמאות לחלוקה).
הגדרנו הגדרות רבות, אך לא עולה מהן בהכרח קשר ליחס השקילות. ראשית, נביא משפט שיעזור לנו לחבר בין כל ההגדרות שמקודם:
הוכחה:
היחס
≈
{\displaystyle \thickapprox }
רפלקסיבי:
יהי
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\thickapprox {}a}
.
היחס
≈
{\displaystyle \thickapprox }
סימטרי:
יהיו
a
,
b
∈
A
{\displaystyle a,b\in {}A}
.
אם
a
≈
b
{\displaystyle a\thickapprox {}b}
, כלומר
a
,
b
∈
X
{\displaystyle a,b\in {}X}
(כאשר
X
{\displaystyle X}
תא בחלוקה) אז ברור ש-
b
,
a
∈
X
{\displaystyle b,a\in {}X}
ולכן
b
≈
a
{\displaystyle b\thickapprox {}a}
.
היחס
≈
{\displaystyle \thickapprox }
הוא טרנזיטיבי:
יהיו
a
,
b
,
c
∈
A
{\displaystyle a,b,c\in {}A}
.
אם
a
≈
b
{\displaystyle a\thickapprox {}b}
וגם
b
≈
c
{\displaystyle b\thickapprox {}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\to {}X=Y}
(ראה הגדרת החלוקה) לכן
a
,
c
∈
X
{\displaystyle a,c\in {}X}
ולכן
a
≈
c
{\displaystyle a\thickapprox {}c}
.
הוכחנו כי
≈
{\displaystyle \thickapprox }
הוא יחס רפלקסיבי, סימטרי וטרנזיטיבי ובכך הוכחנו כי הוא יחס שקילות.
כפי שמצביע שם המשפט: ליחס זה אנו קוראים היחס שמושרה על ידי החלוקה או שאנו אומרים החלוקה משרה את היחס .
עכשיו יש בידינו כלי, שדרכו נוכל לחבר בין כל ההגדרות שהובאו ולהראות מדוע יחסי השקילות כה חשובים:
משפט: קבוצת המנה היא חלוקה
יהי
D
{\displaystyle {\mathfrak {D}}}
יחס שקילות על קבוצה לא ריקה
A
{\displaystyle A}
.
קבוצת המנה
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
מהווה חלוקה של
A
{\displaystyle A}
הוכחה:
במהלך ההוכחה נסמן
[
a
]
{\displaystyle [a]}
מחלקת השקילות (ראו הגדרה) של
a
{\displaystyle a}
.
(*): נוכיח
a
D
b
{\displaystyle a{\mathfrak {D}}b}
אם ורק אם
[
a
]
=
[
b
]
{\displaystyle [a]=[b]}
.
כיוון ראשון נניח כי
a
D
b
{\displaystyle a{\mathfrak {D}}b}
. יהי
c
∈
A
{\displaystyle c\in {}A}
.
c
∈
[
a
]
{\displaystyle c\in {}[a]}
אם ורק אם
c
D
a
{\displaystyle c{\mathfrak {D}}a}
(מהגדרת מחלקת השקילות)
c
D
a
{\displaystyle c{\mathfrak {D}}a}
אם ורק אם
c
D
b
{\displaystyle c{\mathfrak {D}}b}
(טרנזיטיביות ומההנחה ש-
a
D
b
{\displaystyle a{\mathfrak {D}}b}
)
לבסוף,
c
D
b
{\displaystyle c{\mathfrak {D}}b}
אם ורק אם
c
∈
[
b
]
{\displaystyle c\in {}[b]}
(הגדרת מחלקת השקילות).
הראנו כי
c
∈
[
a
]
↔
c
∈
[
b
]
{\displaystyle c\in [a]\leftrightarrow {}c\in [b]}
ולכן, מצאנו כי
[
a
]
=
[
b
]
{\displaystyle [a]=[b]}
. כפי שרצינו.
כיוון שני: נניח כי
[
a
]
=
[
b
]
{\displaystyle [a]=[b]}
.
משום ש-
D
{\displaystyle {\mathfrak {D}}}
יחס שקילות, הרי ש-
a
D
a
{\displaystyle a{\mathfrak {D}}a}
(רפלקסיביות) ולכן
a
∈
[
a
]
{\displaystyle a\in [a]}
.
מההנחה ש-
[
a
]
=
[
b
]
{\displaystyle [a]=[b]}
נקבל כי
a
∈
[
b
]
{\displaystyle a\in [b]}
.
לכן, מהגדרת מחלקת השקילות, נקבל כי
a
D
b
{\displaystyle a{\mathfrak {D}}b}
. כפי שרצינו.
בכך הוכחנו את (*).
(1) נוכיח שלכל
a
∈
A
{\displaystyle a\in {}A}
מתקיים כי
[
a
]
≠
∅
{\displaystyle [a]\neq \varnothing }
:
לכל
a
∈
A
{\displaystyle a\in {}A}
מתקיים
a
D
a
{\displaystyle a{\mathfrak {D}}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
╱
D
{\displaystyle [a],[b]\in A\diagup {\mathfrak {D}}}
המקיימים
[
a
]
≠
[
b
]
{\displaystyle [a]\neq [b]}
, הדבר שקול לכך ש-
a
D
b
{\displaystyle a{\bcancel {\mathfrak {D}}}b}
(לפי (*)).
נניח בשלילה כי
[
a
]
∩
[
b
]
≠
∅
{\displaystyle [a]\cap {}[b]\neq \varnothing }
.
מהנחת השלילה, נובע כי קיים
c
∈
[
a
]
∩
[
b
]
{\displaystyle c\in {}[a]\cap {}[b]}
.
מכך ש-
c
∈
[
a
]
∩
[
b
]
{\displaystyle c\in {}[a]\cap {}[b]}
נובע ש-
c
∈
[
a
]
{\displaystyle c\in {}[a]}
וגם ש-
c
∈
[
b
]
{\displaystyle c\in {}[b]}
.
לכן, מהגדרת מחלקת השקילות, מצאנו כי
c
D
a
{\displaystyle c{\mathfrak {D}}a}
וגם
c
D
b
{\displaystyle c{\mathfrak {D}}b}
.
מסימטריות נקבל כי
c
D
a
→
a
D
c
{\displaystyle c{\mathfrak {D}}a\to a{\mathfrak {D}}c}
.
מטרנזיטיביות נקבל כי
a
D
c
∧
c
D
b
→
a
D
b
{\displaystyle a{\mathfrak {D}}c\land {}c{\mathfrak {D}}b\to {}a{\mathfrak {D}}b}
בסתירה להנחה כי
a
D
b
{\displaystyle a{\bcancel {\mathfrak {D}}}b}
.
הנחת השלילה הובילה לסתירה, ולכן
[
a
]
≠
[
b
]
→
[
a
]
∩
[
b
]
=
∅
{\displaystyle [a]\neq [b]\to [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
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
(קבוצת המנה : ראה הגדרה) היא חלוקה של
A
{\displaystyle A}
.
הוכחה:
במשפט: קבוצת המנה היא חלוקה, הוכחנו כי
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
היא חלוקה של
A
{\displaystyle A}
.
עתה נוכיח כי
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
היא החלוקה היחידה שמשרה את
D
{\displaystyle {\mathfrak {D}}}
.
(1) נוכיח ש-
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
היא אכן חלוקה שמשרה את
D
{\displaystyle {\mathfrak {D}}}
, כלומר, נראה כי
a
D
b
{\displaystyle a{\mathfrak {D}}b}
אם ורק אם
a
{\displaystyle a}
ו-
b
{\displaystyle b}
באותו התא של
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
:
כיוון ראשון: נניח כי
a
D
b
{\displaystyle a{\mathfrak {D}}b}
.
משום ש-
a
D
b
{\displaystyle a{\mathfrak {D}}b}
נובע כי
a
∈
[
b
]
{\displaystyle a\in {}[b]}
(הגדרת מחלקת השקילות).
משום ש-
D
{\displaystyle {\mathfrak {D}}}
הוא יחס שקילות, נקבל כי
b
D
b
{\displaystyle b{\mathfrak {D}}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
{\displaystyle a}
ו-
b
{\displaystyle b}
באותו התא של
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
, כלומר
a
,
b
∈
[
c
]
{\displaystyle a,b\in {}[c]}
.
מהגדרת מחלקת השקילות נקבל ש-
a
D
c
{\displaystyle a{\mathfrak {D}}c}
וגם
b
D
c
{\displaystyle b{\mathfrak {D}}c}
.
לכן נקבל
a
D
b
{\displaystyle a{\mathfrak {D}}b}
(סימטריה, וטרנזיטיביות של יחס השקילות
D
{\displaystyle {\mathfrak {D}}}
).
כלומר, בסה"כ
a
,
b
∈
[
c
]
↔
a
D
b
{\displaystyle a,b\in [c]\leftrightarrow a{\mathfrak {D}}b}
(כאשר
[
c
]
∈
A
╱
D
{\displaystyle [c]\in A\diagup {\mathfrak {D}}}
)
בכך הראנו שהחלוקה
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
משרה את היחס
D
{\displaystyle {\mathfrak {D}}}
. כפי שרצינו.
(2): נוכיח כי זו החלוקה היחידה שמשרה את
D
{\displaystyle {\mathfrak {D}}}
.
תהא
T
{\displaystyle T}
חלוקה שמשרה את
D
{\displaystyle {\mathfrak {D}}}
, כלומר
a
D
b
{\displaystyle a{\mathfrak {D}}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
D
b
{\displaystyle a{\mathfrak {D}}b}
(
T
{\displaystyle T}
משרה את
D
{\displaystyle {\mathfrak {D}}}
).
כלומר,
a
D
b
{\displaystyle a{\mathfrak {D}}b}
אם ורק אם
b
∈
[
a
]
{\displaystyle b\in [a]}
(
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
משרה את
D
{\displaystyle {\mathfrak {D}}}
).
מצאנו כי
a
,
b
∈
X
↔
a
D
b
↔
a
,
b
∈
[
a
]
{\displaystyle a,b\in X\leftrightarrow a{\mathfrak {D}}b\leftrightarrow a,b\in [a]}
מכאן ש-
X
=
[
a
]
{\displaystyle X=[a]}
.
הראנו שכל תא
X
∈
T
{\displaystyle X\in T}
הוא תא של
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
ולכן
T
⊆
A
╱
D
{\displaystyle T\subseteq {}A\diagup {\mathfrak {D}}}
.
כיוון שני: יהי
[
a
]
∈
A
╱
D
{\displaystyle [a]\in {}A\diagup {\mathfrak {D}}}
תא אשר
a
∈
A
{\displaystyle a\in A}
שייך אליו.
מתקיים
b
∈
[
a
]
{\displaystyle b\in [a]}
אם ורק אם
a
D
b
{\displaystyle a{\mathfrak {D}}b}
(
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
משרה את
D
{\displaystyle {\mathfrak {D}}}
).
כמו כן,
a
D
b
{\displaystyle a{\mathfrak {D}}b}
אם ורק אם
b
∈
X
{\displaystyle b\in {}X}
(
T
{\displaystyle T}
משרה את
D
{\displaystyle {\mathfrak {D}}}
).
הראנו כי
a
,
b
∈
[
a
]
↔
a
D
b
↔
a
,
b
∈
T
{\displaystyle a,b\in [a]\leftrightarrow a{\mathfrak {D}}b\leftrightarrow a,b\in T}
.
הראינו שכל תא
[
a
]
∈
A
╱
D
{\displaystyle [a]\in {}A\diagup {\mathfrak {D}}}
הוא תא של
T
{\displaystyle T}
ולכן
A
╱
D
⊆
T
{\displaystyle A\diagup {\mathfrak {D}}\subseteq {}T}
.
משילוב הכיוונים מצאנו כי
T
=
A
╱
D
{\displaystyle T=A\diagup {\mathfrak {D}}}
, כפי שרצינו.
מ-(1) ומ-(2) הוכחנו כי
A
╱
D
{\displaystyle A\diagup {\mathfrak {D}}}
היא החלוקה היחידה שמשרה את היחס
במשפטים אלו הוכחנו שני דברים חשובים:
הראשון, קבוצת המנה של קבוצה היא חלוקה .
השני, קבוצת המנה היא החלוקה היחידה שמשרה את יחס השקילות שמגדיר אותה.
משילוב המשפטים ניתן לראות, שאם נקבל חלוקה - אז נוכל להשרות דרכה יחס שקילות.
ואם נקבל יחס שקילות, נוכל למצוא את החלוקה שמשרה אותו; היא פשוט קבוצת המנה.
מכאן, נחזור לדוגמה ב' בדוגמאות ליחס שקילות :
אחת הדרכים (אם כי הפחות שימושית) בה מגדירים באופן פורמלי עוצמה של קבוצה, היא לקחת את מחלקת כל הקבוצות, ולהסתכל על מחלקת המנה שלה (הגדרה כמעט זהה לקבוצת המנה) ביחס ליחס
≅
{\displaystyle \cong }
שהוגדר בדוגמה.
כלומר, אנו יודעים שלשתי קבוצות יש את אותה עוצמה אם יש ביניהן בייקציה. לכן, בהנתן קבוצה
A
{\displaystyle A}
נוכל לומר שהעוצמה שלה היא פשוט מחלקת השקילות
[
A
]
{\displaystyle [A]}
ביחס ל-
≅
{\displaystyle \cong }
.
ואכן, אנו נאמר של
A
{\displaystyle A}
ול-
B
{\displaystyle B}
יש את אותה עוצמה אם
B
∈
[
A
]
{\displaystyle B\in {}[A]}
.
כמו כן, הגדרות רבות במתמטיקה (למשל של סודרים ) ניתנות על ידי מחלקות שקילות והקשר שביניהן לבין חלוקה.
דוגמאות לאובייקטים מתמטיים שנהוג להגדיר על ידי יחס שקילות ועל ידי קבוצת המנה הם המספרים השלמים והרציונליים.
כדוגמה נוספת למחלקת שקילות :
אפשר להסתכל על דמיון ועל חפיפת משולשים כיחסי שקילות.
נסו למצוא תאור מדוייק של מחלקות השקילות של יחס הדמיון בין משולשים.
חישבו גם מה משותף ביחס החפיפה בין משולשים, ליחס השוויון בין קבוצות (ראה דוגמה א' בדוגמות ליחס שקילות).