תורת הקבוצות/יחסי סדר: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
YoavPinhasMath (שיחה | תרומות) |
YoavPinhasMath (שיחה | תרומות) |
||
שורה 125:
מהתרשים ניתן לראות שביחס יש אבעה איברים מקסימליים (<math>g,e,f,z</math>, למה?)
ושני איברים מינימליים (מי הם?). נסו לרשום את קבוצת הזוגות שמגדירה את היחס.
אם נקח את התת קבוצה <math>B=\{a,b,c,d,e,f,g\}</math>ונצמצם את היחס אליה (בצמצום הכוונה ל-<math>\lessdot \cap (B \times B)</math>)
שורה 172:
למשל, אם הקבוצה היא <math>A=\{1,2,3,4\}</math> אז היחס <math>\prec = \{(1,2),(2,3),(1,3)\}</math> הוא יחס סדר חלקי על הקבוצה <math>A</math> וכפי שניתן בקלות לראות, 4 בכלל לא נמצא ביחס. הוא לא מתייחס לאף איבר, ואף איבר לא מתייחס אליו.
מה יקרה אם נדרוש מיחס סדר חלקי, שכל איברי הקבוצה ישתתפו בו? לפני שנגדיר יחס סדר מלא ונברר, הנה הגדרה:
{{הגדרה|שם=יחס משווה|תוכן=
שורה 189:
}}
מכאן אנו מסיקים שכל יחס סדר מלא הוא יחס סדר חלקי, אבל לא כל יחס סדר חלקי הוא יחס סדר מלא (
היחס סדר החלקי הבא <math>\{(1,2),(1,3),(1,4),(1,5)\}</math> על הקבוצה <math>\{1,2,3,4,5\}</math> '''אינו''' יחס סדר, שכן 4 ו-3 לא ניתנים להשוואה (מי עוד לא?).
אבל, היחס סדר החלקי הבא על אותה קבוצה הוא כן יחס סדר: <math>\{(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)\}</math> (וודאו זאת!).
נצייר תרשימים של היחסים הללו זה לצד זה (השוו כל תרשים לאוסף הזוגות):
שורה 247:
כלומר, הראנו שלכל <math>b\in A</math> מתקיים <math>m\preceq b</math> ולכן <math>m</math> הוא איבר קטן ביותר
}}נביא הגדרה המקבילה להגדרה של קבוצה סדורה חלקית.
{{הגדרה|תוכן=יהי <math> \prec </math> יחס סדר מלא על קבוצה <math> A </math>. לזוג הסדור <math> (A, \prec ) </math> אנו קוראים '''קבוצה סדורה מלא''' או בקיצור '''קבוצה סדורה'''.}}
כפי שציינו קודם, קבוצות סדורות שוות זו לזו אם ורק אם יש להן גם אם הן אותה קבוצה ויש בהן את אותו הסדר.
דוגמה המוכרת לכם היטב של קבוצה סדורה היא <math>(\mathbb{N},<)</math> (יחס הסדר הרגיל).
נוכיח זאת:
ראשית נראה כי מדובר בקבוצה סדורה חלקית.
אין מספר טבעי <math>n\in \mathbb{N}</math> המקיים <math>n<n</math> (כלומר, אין מספר טבעי שקטן מעצמו) ולכן היחס הוא אי-רפלקסיבי.
יהיו <math>a,b,c\in\mathbb{N}</math> המקיימים <math>a<b</math> וגם <math>b<c</math>, אנו יודעים שניתן לכתוב זאת גם כך <math>a<b<c</math> ובכתיבה זו, אנו רואים שמדובר ביחס טרנזיטיבי (ניתן לראות דרך ההגדרה של המספרים הטבעיים שנתנה בפרק קודם, ש-<math>a<b</math>זה בעצם <math>a\in b</math> ולכן <math>a\in b \in c</math>, נדבר על כך בהרחבה בפרק על סודרים).
הראנו כי היחס הוא יחס סדר חלקי. עתה, נראה שהוא גם משווה.
אנו יודעים שלכל שני מספרים טבעיים: אם הם שונים, אז אחד גדול מהשני, ואם אם שווים אף אחד אינו גדול מהשני.
אכן מדובר ביחס סדר.
הראו שגם הממשיים והרציונליים עם הסדר הרגיל הן קבוצות סדורות.
נגדיר יחס <math>\prec</math> על המספרים הטבעיים: לכל <math>m,n\in \mathbb{N}</math> מתקיים <math>n\prec m</math> אם ורק אם <math>n<m</math> ושניהם זוגיים '''או''' <math>n<m</math>ושנייהם אי זוגיים '''או''' <math>n</math> זוגי ו-<math>m</math> אי-זוגי.
תרשים של יחס זה יראה כך: <math>0,2,4,6,8,10,...,1,3,5,7,9,11,...</math> (קודם כך הזוגיים בסדר הרגיל ואז כל האי זוגיים). הסבירו לעצמכם מדוע מדובר ביחס סדר.
דוגמה אחרונה ומוכרת ליחס סדר היא הדוגמה הבאה:
יהיו הקבוצות הסדורות <math>(A,\prec_1)</math> ו-<math>(B,\prec_2)</math>. נגדיר יחס <math>\prec</math> על הקבוצה <math>A\times B</math> באופן הבא:
לכל <math>(a_1,b_1),(a_2,b_2)\in A\times B</math> מתקיים <math>(a_1,b_1)\prec (a_2,b_2)</math> אם ורק אם <math>a_1\prec_1a_2</math> או <math>a_1=a_2</math> וגם <math>b_1\prec_2 b_2</math>.
קראו טוב את ההגדרה וודאו שאכן מדובר ביחס סדר.
יחס סדר זה מכונה בשם "הסדר המילוני השמאלי" כי הוא מסדר את הזוגות כמו במילון (מילון משמאל לימין) אם האותיות השמאליות קטנות יותר, אז הן יהיו משמאל, אם הן שוות אז האותיות השניות קובעות.
איך יוגד הסדר המילוני הימני?
אולי הדוגמאות עד כה עוררו את חשדכם בטענה הבאה:
{{טענה|תוכן=תהי <math> (A, \prec ) </math> קבוצה סדורה. יהיו <math>a,b\in A</math>.
מתקיים אחד ורק אחד מהמצבים הבאים:
<math>a\prec b</math>, <math>b\prec a</math>, <math>a = b</math>.}}
הוכחת הטענה תושאר כתרגיל לקורא (הניחו בשלילה כי מתקיימים שניים מן המצבים במקביל, ראו הוכחת האסימטריות של יחס סדר חלקי).
מטענה זו אנו מקבלים בין היתר כי גם יחסי סדר, בדומה ליחסי סדר חלקיים, הם אסימטרים.
תהי <math>A</math> קבוצה לא ריקה. עבור אילו תנאים הזוג <math>(\mathcal{P}(A),\subset )</math> (קבוצת החזקה) הוא קבוצה סדורה? ועבור אילו תנאים הוא קבוצה סדורה חלקית? (רמז: התחילו מלהתבונן בקבוצה הריקה).
לסיום סעיף זה, נביא עוד טענה ומשפט:
{{טענה|תוכן=יהי <math> \prec </math> יחס סדר על קבוצה <math>A</math>. כל הרחבה או צמצום (ממש) של יחס זה אינו מהווה יחס סדר על הקבוצה <math>A</math>.
כלומר, אם <math>\prec_* \subset \prec</math> או <math>\prec\subset \prec_*</math> אז <math>\prec_*</math> אינו יחס סדר על הקבוצה <math>A</math>.}}
{{הוכחה|
יהי <math>\prec_*\subset \prec</math>. לכן קיימים <math>a,b\in A</math> המקיימים <math>a\prec b</math> וגם <math>a\cancel{\prec_*}b</math>.
מתכונת ההשוואה נקבל כי <math>b\cancel{\prec}a</math> וגם <math>a\ne b</math>.
מכיוון ש- <math>\prec_*\subset \prec</math> אז <math>b\cancel{\prec}a \to b\cancel{\prec_*}a</math>.
בסה"כ הראנו כי <math>a\ne b</math> וגם <math>a\cancel{\prec_*}b</math> וגם <math>b \cancel{\prec_*} a</math>.
מכך נובע כי <math>\prec_*</math> אינו יחס משווה ולכן אינו יחס סדר. כפי שרצינו להוכיח.
יהי <math>\prec \subset \prec_*</math>. נניח בשלילה כי <math>\prec_*</math> יחס סדר.
מהתוצה של החצי הקודם של ההוכחה נקבל כי <math>\prec</math> אינו יחס סדר. בסתירה לנתוני הטענה.
ההנחה הובילה לסתירה, ולכן <math>\prec_*</math> אינו יחס סדר.
}}{{משפט|תוכן=תהי <math>(A,\prec)</math> קבוצה סדורה.
אם <math>A</math> קבוצה סופית אז יש בה איבר גדול ביותר ואיבר קטן ביותר.}}
{{הוכחה|
נניח בשלילה שאין בה איבר גדול ביותר.
נסמן ב-<math>a_1,a_2,a_3,...,a_n</math> את כל איברי הקבוצה.
מהנחת השלילה לכל <math>a_i\in A</math> קיים <math>a_j\in A</math> כך שמתקיים <math>a_i \prec a_j</math>.
תהי <math>i_1,i_2,i_3,...,i_n</math> סדרת אינדקסים שמקיימת את מה שנאמר בשורה מעל (לכל איברי הקבוצה).
כלומר, <math>a_{i_1}\prec a_{i_2} \prec a_{i_3} \prec ... \prec a_{i_n}</math> (כפי שראינו בדיונים קודמים, מהגדרת יחס הסדר מתחייב שנקבל שרשרת כזאת).
מכאן שגם ל-<math>a_{i_n}</math> קיים <math>a_{i_j}</math> כלשהו המקיים <math>a_{i_n} \prec a_{i_j}</math> כלומר:
<math>a_{i_1}\prec a_{i_2} \prec a_{i_3} \prec ... \prec ...\prec a_{i_j}\prec...\prec a_{i_n}\prec a_{i_j}</math>
ומצאנו ש-<math>a_{i_n}\prec a_{i_j}</math> וגם <math>a_{i_j} \prec a_{i_n}</math> בסתירה לטענה שהוכחנו קודם.
הנחת השלילה הובילה לסתירה, לכן יש איבר גדול ביותר.
ההוכחה עבור איבר קטן ביותר אנלוגית.
}}
| |||