ויקיספר

תורת הקבוצות/יחסי שקילות: הבדלים בין גרסאות בדף

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
אין תקציר עריכה
פיצלתי משפט לשניים כדי להקל על הקריאה. כמו כן, התאמתי (ואמשיך להתאים תכף) את הסגנון של הפרק, כך שיתאים יותר לפרקים שהיו לפניו.
שורה 86:
==== הוכחה: ====
 
* '''היחס <math>\thickapprox</math> רפלקסיבי:''' יהי <math>a\in{}A</math>. אם <math>a\in{}X</math> (כאשר <math>X</math> תא בחלוקה) אז ברור ש- <math>a\in{}X</math> ולכן <math>a\thickapprox{}a</math>.
* '''היחס <math>\thickapprox</math> סימטרי:''' יהיו <math>a,b\in{}A</math>. אם <math>a\thickapprox{}b</math>, כלומר <math>a,b\in{}X</math> (כאשר <math>X</math> תא בחלוקה) אז ברור ש-<math>b,a\in{}X</math> ולכן <math>b\thickapprox{}a</math>.
* '''היחס הוא טרנזיטיבי:''' יהיו <math>a,b,c\in{}A</math>. אם <math>a\thickapprox{}b</math> וגם <math>b\thickapprox{}c</math>, כלומר <math>a,b\in{}X</math> וגם <math>b,c\in{}Y</math> (כאשר <math>X,Y</math> תאים בחלוקה) אז: <math>b\in{}X\land{}x\in{}Y\to{}X=Y</math> (ראה הגדרת החלוקה) לכן <math>a,c\in{}X</math> ולכן <math>a\thickapprox{}c</math>.
 
הוכחנו כי <math>\thickapprox</math> הוא יחס רפלקסיבי, סימטרי וטרנזיטיבי ובכך הוכחנו כי הוא יחס שקילות <math>\Box</math>.
שורה 105:
==== הוכחה: ====
 
 
{{משפט|
שם=יחידות החלוקה |▼
תוכן=▼
הי <math>\mathfrak{D}</math> יחס שקילות על קבוצה לא ריקה <math>A</math>.▼
 
קבוצת המנה <math>A\diagup\mathfrak{D}</math> היא החלוקה '''היחידה''' של <math>A</math> אשר היחס <math>\mathfrak{D}</math> '''מושרה על ידה'''.}}▼
 
==== הוכחה: ====▼
במהלך ההוכחה נסמן <math>[a]</math> מחלקת השקילות (ראו הגדרה) של <math>a</math>.
 
<u>שלב ראשון:</u> נוכיח כי קבוצת המנה <math>A\diagup\mathfrak{D}</math> היא חלוקה של <math>A</math> (ראה הגדרה).▼
 
(*): נוכיח <math>a\mathfrak{D}b</math> אם ורק אם <math>[a]=[b]</math>.
שורה 140 ⟵ 129:
בכך הוכחנו את (*).
 
<u>(1): נוכיח שאם שלכל <math>a\bcancel{\mathfrak{D}}b</math> (כלומר <math>(a,b)\not\in{}\mathfrak{D}A</math>) אזמתקיים כי <math>[a]\cap{}[b]\neq \varnothing</math>.</u>:
 
נניחלכל כי<math>a\in{}A</math> מתקיים ש- <math>a\bcancel{\mathfrak{D}}ba</math>. נניח(רפלקסיביות) בשלילהמכך נובע כי <math>a\in[a]\cap{}</math> ולכן <math>[ba]\neq{}\varnothing</math>. כפי שרצינו.
 
<u>(2) נוכיח שאם <math>[a]\neq{}[b]</math> (תאים שונים של החלוקה) אז <math>[a]\cap{}[b]\neq\varnothing</math></u>:
 
יהיו <math>[a],[b]\in A\diagup\mathfrak{D}</math> המקיימים <math>[a]\neq [b]</math>, הדבר שקול לכך ש- <math>a\bcancel{\mathfrak{D}}b</math> (לפי (*)).
 
נניח בשלילה כי <math>[a]\cap{}[b]\neq\varnothing</math>.
 
מהנחת השלילה, נובע כי קיים <math>c\in{}[a]\cap{}[b]</math>.
שורה 152 ⟵ 147:
מסימטריות נקבל כי <math>c\mathfrak{D}a\to a\mathfrak{D}c</math>.
 
מטרנזיטיביות נקבל כי <math>a\mathfrak{D}c\land{}c\mathfrak{D}b\to{}a\mathfrak{D}b</math> בסתירה להנחה כי <math>a\bcancel{\mathfrak{D}}b</math>.
 
הנחת השלילה הובילה לסתירה, ולכן <math>[a]\bcancel{\mathfrak{D}}neq[b]\to[a]\cap[b]=\varnothing</math>. כפי שרצינו.
 
(2): לכל <math>a\in{}A</math> מתקיים כי <math>[a]\neq \varnothing</math>.
 
לכל <math>a\in{}A</math> מתקיים <math>a\mathfrak{D}a</math> (רפלקסיביות) מכך נובע כי <math>a\in[a]</math> ולכן <math>[a]\neq{}\varnothing</math>. כפי שרצינו.
 
(3): נראה כי <math>A=\bigcup_{a\in{}A}[a]</math>.
שורה 174 ⟵ 165:
משילוב הכיוונים קיבלנו כי <math>A=\bigcup_{a\in{}A}[a]</math>.
 
לפי (1), (2) ו-(3) הראנו שכל שתי מחלקותמחלקת שקילות שונותאינה זרותריקה, הראנו שכל מחלקתשתי מחלקות שקילות היאשונות לא ריקהזרות והראנו שאיחוד כל מחלקות השקילות הוא <math>A</math>.
 
לכן, מהגדרת החלוקה, מצאנו כי <math>S=A\diagup\mathfrak{D}</math> ('''קבוצת המנה''': ראה הגדרה) היא '''חלוקה''' של <math>A</math>.{{משפט|
▲שם=יחידות החלוקה |
▲תוכן=
▲הי <math>\mathfrak{D}</math> יחס שקילות על קבוצה לא ריקה <math>A</math>.
 
▲קבוצת המנה <math>A\diagup\mathfrak{D}</math> היא החלוקה '''היחידה''' של <math>A</math> אשר היחס <math>\mathfrak{D}</math> '''מושרה על ידה'''.}}
 
▲==== הוכחה: ====
▲<u>שלב ראשוןבמשפט:</u> נוכיח כי קבוצת המנה היא חלוקה, הוכחנו כי <math>A\diagup\mathfrak{D}</math> היא חלוקה של <math>A</math> (ראה הגדרה).
 
עתה נוכיח כי <math>SA\diagup\mathfrak{D}</math> היא החלוקה '''היחידה''' שמשרה את <math>\mathfrak{D}</math>.
 
<u>(51), נוכיח ש-<math>SA\diagup\mathfrak{D}</math> היא אכן חלוקה שמשרה את <math>\mathfrak{D}</math>, כלומר, נראה כי <math>a\mathfrak{D}b</math> אם ורק אם <math>a</math> ו-<math>b</math> באותו התא של <math>SA\diagup\mathfrak{D}</math>.:</u>
 
<u>כיוון ראשון:</u> נניח כי <math>a\mathfrak{D}b</math>.
 
משום ש-<math>a\mathfrak{D}b</math> נובע כי <math>a\in{}[b]</math> (הגדרת מחלקת השקילות).
 
משום ש-<math>\mathfrak{D}</math> הוא יחס שקילות, נקבל כי <math>b\mathfrak{D}b</math> (רפלקסיביות) ולכן <math>b\in{}[b]</math>.
 
מצאנו ש-<math>a\in[b]</math> וגם <math>b\in{}[b]</math> ובכך הראנו כי <math>a,b</math> באותו תא.
 
<u>כיוון שני:</u> נניח כי <math>a</math> ו-<math>b</math> באותו התא של <math>SA\diagup\mathfrak{D}</math>, כלומר <math>a,b\in{}[c]</math>.
 
מהגדרת מחלקת השקילות נקבל ש-<math>a\mathfrak{D}c</math> וגם <math>b\mathfrak{D}c</math>.
שורה 196 ⟵ 195:
לכן נקבל <math>a\mathfrak{D}b</math> (סימטריה, וטרנזיטיביות של יחס השקילות <math>\mathfrak{D}</math>).
 
בכךכלומר, הראנו שהחלוקהבסה"כ <math>Sa,b\in[c]\leftrightarrow a\mathfrak{D}b</math> משרה את היחס(כאשר <math>[c]\in A\diagup\mathfrak{D}</math>. כפי שרצינו.)
 
בכך הראנו שהחלוקה <math>A\diagup\mathfrak{D}</math> משרה את היחס <math>\mathfrak{D}</math>. כפי שרצינו.
 
(62): נוכיח כי זו החלוקה היחידה שמשרה את <math>\mathfrak{D}</math>.
 
תהא <math>T</math> חלוקה שמשרה את <math>\mathfrak{D}</math>, כלומר <math>a\mathfrak{D}b</math> אם ורק אם <math>a,b</math> באותו התא של <math>T</math>.
 
יהי <mathu>X\in(T)כייון ראשון:</mathu> תא אשר האיבריהי <math>aX</math> שייךתא אליו. יהיבחלוקה <math>b\in{}XT</math>.
 
מההנחה<math>X\neq כי\varnothing </math>T ולכן יש <math>a\in X</math>. משרה אתלכל <math>b\mathfrak{D}in A</math> נובכעמתקיים כי <math>a,b\in TX</math> אם ורק אם <math>a\mathfrak{D}b</math> (שניהם<math>T</math> באותומשרה התאאת <math>\mathfrak{D}</math>).
 
מ-(*) נקבלכלומר, כי <math>a\mathfrak{D}b</math> אם ורק אם <math>[b]=\in [a]</math>, כלומר( <math>a,bA\in[a]diagup\mathfrak{D}</math> (אותומשרה את התא ב-<math>S\mathfrak{D}</math>).
 
מצאנו כי <math>a,b\in X \leftrightarrow a\mathfrak{D}b \leftrightarrow a,b\in[a]</math>מכאן ש-<math>X=[a]</math>.
 
הראנו שלכלשכל תא <math>X\in T</math> הוא המכיל אתתא איברשל <math>a</math> מתקיים ש-<math>X=[a]A\in S</math> לכן <math>Xdiagup\inmathfrak{D}S</math> ולכן <math>T\subseteq{}S A\diagup\mathfrak{D}</math>.
 
<u>כיוון שני:</u> יהי <math>[a]\in{}S</math> ויהי <math>XA\indiagup\mathfrak{D}T</math> תא ש-אשר <math>a\in A</math> שייך אליו.
 
מהגדרתמתקיים מחלקת השקילות, <math>b\in[a]</math> אם ורק אם <math>a\mathfrak{D}b</math> ( <math>A\diagup\mathfrak{D}</math> משרה את <math>\mathfrak{D}</math>).
 
כמו כן, <math>a\mathfrak{D}b</math> אם ורק אם <math>b\in{}X</math> (<math>T</math> משרה את <math>\mathfrak{D}</math>).
שורה 220 ⟵ 221:
הראנו כי <math>a,b\in [a] \leftrightarrow a\mathfrak{D}b \leftrightarrow a,b\in T</math>.
 
הראינו שלכלשכל תא <math>[a]\in{}S</math> קיים <math>XA\indiagup\mathfrak{D}T</math> כךהוא ש-<math>X=[a]</math>תא לכןשל <math>[a]\in{}T</math> ולכן <math>SA\diagup\mathfrak{D}\subseteq{}T</math>.
 
משילוב הכיוונים מצאנו כי <math>S=T=A\diagup\mathfrak{D}</math>, כפי שרצינו.
 
מ-(51) ומ-(62) הוכחנו כי <math>A\diagup\mathfrak{D}</math> היא החלוקה היחידה שמשרה את היחס <math>\Box</math>.
 
במשפטים אלו הוכחנו שני דברים חשובים:
בהוכחת המשפט הראנו שני דברים, שאף גורמים לו להיות יותר חזק ממה שהנוסח שלו מרמז.
 
הראשון, '''קבוצת המנה''' של קבוצה היא '''חלוקה'''.
שורה 234 ⟵ 235:
משילוב המשפטים ניתן לראות, שאם נקבל חלוקה - אז נוכל להשרות דרכה יחס שקילות.
 
ואפואם נקבל יחס שקילות, נוכל למצוא את החלוקה שמשרה אותו.; היא פשוט קבוצת המנה.
 
==== שימושים ====
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_הקבוצות/יחסי_שקילות"