תורת הקבוצות/יחסי סדר: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
YoavPinhasMath (שיחה | תרומות) שיניתי כמה דברים קטנים. עדיין חסרים רוב סוגי הסדרים |
YoavPinhasMath (שיחה | תרומות) |
||
שורה 69:
{{הגדרה|שם=קבוצה סדורה חלקית|תוכן=יהי <math>\prec</math> יחס סדר חלקי על קבוצה <math>A</math>. לזוג הסדור <math>(A,\prec)</math> אנו קוראים '''קבוצה סדורה חלקית'''.}}
הערה: מהגדרה זו נובע ששוויון של קבוצות סדורות חלקית מתבצע לפי שוויון של [[תורת הקבוצות/מכפלה קרטזית|זוגות סדורים]].
שורה 174 ⟵ 172:
== יחס סדר מלא ==
עד כה דיברנו על יחס סדר חלקי. כפי שעלה מההגדרות, לא כל איבר של קבוצה חייב להשתתף ביחס החלקי עליה.
למשל, אם הקבוצה היא <math>A=\{1,2,3,4\}</math> אז היחס <math>\prec = \{(1,2),(2,3),(1,3)\}</math> הוא יחס סדר חלקי על הקבוצה <math>A</math> וכפי שניתן בקלות לראות, 4 בכלל לא נמצא ביחס. הוא לא מתייחס לאף איבר, ואף איבר לא מתייחס אליו.
מה יקרה אם נדרוש מיחס סדר, שכל איברי הקבוצה ישתתפו בו? לפני שנגדיר יחס סדר מלא ונברר, הנה הגדרה:
{{הגדרה|שם=יחס משווה|תוכן=
יחס <math>E</math> על קבוצה <math>A</math> יקרא '''משווה''' או '''יחס משווה''' אם '''כל''' איברי <math>A</math> ניתנים להשוואה.
כלומר, אם '''לכל''' <math>a,b\in A</math> מתקיים <math>aEb</math> או <math>bEa</math> או <math>a=b</math>.
}}
משנתנו הגדרה זו, נוכל לומר שהיחס בדוגמה שבדיון מקודם אינו יחס משווה היות ו-<math>4 \cancel{\prec} 3\quad \land\quad 3 \cancel{\prec} 4\quad \land\quad 4\ne 3</math>.
{{הגדרה|שם=יחס סדר מלא|תוכן=
יחס <math>\prec</math> על קבוצה <math>A</math> יקרא '''יחס סדר מלא''' או בקיצור '''יחס סדר''' אם הוא מקיים את התנאים הבאים:
* <math>\prec</math>הוא יחס סדר חלקי.
* <math>\prec</math> הוא יחס משווה.
}}
מכאן אנו מסיקים שכל יחס סדר הוא יחס סדר חלקי, אבל לא כל יחס סדר חלקי הוא יחס סדר (מכאאן והלאה, לא נאמר יחס סדר מלא, אלא פשוט יחס סדר).
היחס סדר הבא <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> (וודאו זאת!).
נצייר תרשימים של היחסים הללו זה לצד זה (השוו כל תרשים לאוסף הזוגות):
<math>\begin{matrix}
&4&&5&&
\\
&& \nwarrow \nearrow
\\
2&\leftarrow&1&\rightarrow&3
\end{matrix}
\quad \quad \quad \quad
\begin{matrix}
5\\
\uparrow
\\
4\\
\uparrow
\\
3\\
\uparrow
\\
2\\
\uparrow
\\
1
\end{matrix}</math>
התרשים הימני הוא התרשים של יחס הסדר (היחס השני) והתרשים משמאל הוא תרשים של יחס הסדר החלקי.
כפי שניתן לראות, יחס סדר אינו מתפצל למסלולים שונים. מסתבר, שהוספת הדרישה לכך שהיחס יהיה משווה, הופכת אותו לסוג של מסלול יחיד.
כדי לנסח הבחנה זו בצורה מדוייקת, הנה המשפט הבא:
{{משפט|תוכן=
יהי <math>\prec</math> יחס סדר על קבוצה <math>A</math>.
# אם יש ב-<math>A</math> איבר מינימלי, אזי הוא האיבר הקטן ביותר.
# אם יש ב-<math>A</math> איבר מקסימלי, אזי הוא האיבר הגדול ביותר.
}}
(ראו הגדרת האיבר הגדול/קטן ביותר אל מול המקסימלי/מינימלי).
אנו נוכיח את 1. ההוכחה ל-2 דומה ותושאר כתרגיל.
{{הוכחה|
נניח כי קיים איבר מינימלי <math>m\in A</math>.
לכן, אין איבר <math>b\in A</math> המקיים <math>b\prec m</math>.
לכל <math>b\in A</math> מתקיים <math>b\prec m</math> או <math>m\prec b</math> או <math>m=b</math> (יחס סדר הוא יחס משווה).
ראינו כי <math>b\cancel{\prec}m</math> ולכן <math>m\prec b</math> או <math>m=b</math>.
כלומר, הראנו שלכל <math>b\in A</math> מתקיים <math>m\preceq b</math> ולכן <math>m</math> הוא איבר קטן ביותר
}}
== יחס סדר חלש ==
| |||