תורת הקבוצות/יחסי סדר

במתמטיקה אנו רגילים להתעסק עם עצמים שיש ביניהם סדר. בין אם מדובר במספרים ובין אם מדובר בסדרות ואף בין אם מדובר בקבוצות. בתורת הקבוצות, יש מוטיבציה להגדיר כל דבר כקבוצה. אם כך, אין זה מפתיע שיחסים בכלל יוגדרו כקבוצות, כפי שעלה מהפרקים הקודמים, ובפרט שיחסי הסדר.

נזכור כי יחס מתאר קשר בין איברים בקבוצה, יחס סדר אם כן, מתאר סדר.

יחס סדר חלקי

נתחיל עם סדרים חלקיים. למשל, נוכל להסתכל על מפת התחנות של רכבת, מדרום לצפון, כמסודרות באופן חלקי. יכול להיות שאחרי תחנה מסויימת יהיו תחנות רבות שאין אף מסילה שמחברת ביניהן (ראו איור של סדר חלקי משמאל).

יחסי סדר בכלל, ויחס סדר חלקי בפרט, נוהגים לסמן בסימונים בסגנון הזה: $\prec ,\quad \leq ,\quad \gg ,\quad <$.

דוגמה ויזואלית ליחס סדר חלקי

הגדרה: יחס סדר חלקי (Partially ordered) יהי יחס $\prec$ על קבוצה $A$. נאמר כי $\prec$ יחס סדר חלקי אם הוא: אי-רפלקסיבי: לכל $a\in A$ מתקיים כי $a{\cancel {\prec }}a$ (כלומר $(a,a)\notin \prec$). טרנזיטיבי: לכל $a,b,c\in A$ אם $a\prec b$ וגם $b\prec c$ אז $a\prec c$

הגדרה זו מהווה תאור פורמלי של יחסים המתפצלים לכמה "מסלולים". ובאופן כזה, שאם שני איברים נמצאים במסלול של איבר שלישי, אז הם באותו המסלול (טרנזיטיביות).

אבל היחס מגדיר יותר מאשר להיות על אותו מסלול, הוא מתאר את הסדר על המסלול, כפי שהאינטואיציה מצפה, איבר אינו גדול מעצמו.

הקבוצה $\prec =\{(1,2),(1,3),(1,4),(1,5),(2,4),(3,5)\}$ היא יחס סדר חלקי.

למשל, $1\prec 2$ (נקרא זאת: 1 קטן מ-2, או 1 לפני 2) וגם $2\prec 4$ ואכן מתקיים ש- $1\prec 4$.

ניתן גם לראות כי $3{\cancel {\prec }}4$ וגם $4{\cancel {\prec }}3$.

יחס זה ניתן לתיאור גם באופן גרפי:

${\begin{matrix}4&&5\\\uparrow &&\uparrow \\2&&3\\&\nwarrow \nearrow &\\&1&\end{matrix}}$(סרטוט 1)

אנו רואים כי 1 הוא האיבר הכי קטן ביחס, בעוד אין איבר שהוא הכי גדול.

אנו גם רואים כי אין איברים הגדולים מ-4 ומ-5. לתכונות אלו ניתן שם בהמשך. כרגע, נביא טענה, שיתכן והבחנתם או חשדתם בנכונותה:

טענה: יהי $\prec$ יחס סדר חלקי על קבוצה $A$. היחס $\prec$ הוא יחס אסימטרי. כלומר, לכל $a,b\in A$ אם $a\prec b$ אז $b{\cancel {\prec }}a$

הוכחה: יהיו $a,b\in A$ המקיימים $a\prec b$.

נניח בשלילה כי $b\prec a$.

מטרנזיטיביות נקבל כי $a\prec b\land b\prec a\to a\prec a$ בסתירה לכך שהיחס אי-רפלקסיבי.

הנחת השלילה הובילה לסתירה, ולכן $b{\cancel {\prec }}a$.

הראנו אם כן, שיחס סדר חלקי הוא גם אסימטרי.

נתבונן ביחס הבא על המספרים הטבעיים החיוביים $\mathbb {N} \setminus \{0\}$:

$|_{2}=\{(a,b)|\exists m\in \mathbb {N} :m>1\land b=a\cdot m\}$

(כלומר $a|_{2}b$ אם ורק אם $b$ מתחלק ב-$a$ ללא שארית ותוצאת החלוקה גדולה מ-1. למשל $5|_{2}15$ אבל $15{\cancel {|_{2}}}5$ וגם $5{\cancel {|_{2}}}5$)

נראה כי מדובר ביחס סדר חלקי.

תכונה ידוע היא שלכל מספר טבעי $n$ שונה מ-0, מתקיים ${n \over n}=1$ ולכן $n{\cancel {|_{2}}}n$. כלומר, היחס אי-רפלקסיבי.

נניח כי $n|_{2}m$ ו-$m|_{2}k$ לכן קיימים $x,y>1$ טבעיים עבורם $k=x\cdot m$ וגם $m=y\cdot n$.

מטרנזיטיביות השוויון (ראה יחסי שקילות) נקבל כי $k=x\cdot m=x\cdot y\cdot n$. כלומר $k=xy\cdot n$.

כמו כן, $x,y>1\to x\cdot y>1$ ולכן $n|_{2}k$.

בכך הראנו כי אכן מדובר ביחס סדר חלקי.

לו היינו מוותרים על הדרישה שהחלוקה תהיה גדולה מ-1, האם עדיין היה מדובר ביחס סדר חלקי?

לו היינו מוותרים על הדרישה שהחלוקה תהיה ללא שארית?

לקבוצה עם יחס סדר חלקי אנו קוראים קבוצה סדורה חלקית. נגדיר:

הגדרה: קבוצה סדורה חלקית יהי $\prec$ יחס סדר חלקי על קבוצה $A$. לזוג הסדור $(A,\prec )$ אנו קוראים קבוצה סדורה חלקית.

הערה: מהגדרה זו נובע ששוויון של קבוצות סדורות חלקית מתבצע לפי שוויון של זוגות סדורים.

כלומר $(A,\prec _{1})=(B,\prec _{2})$ אם ורק אם $A=B$ וגם $\prec _{1}=\prec _{2}$.

מבחינה זו מדובר בהגדרה קולעת. נביא לכם תרגיל שימחיש את המשמעות של שוויון זה:

נסו למצוא קבוצות $A,B$ שונות ויחס סדר חלקי $\prec$ כך שמתקיים $\{(a,b)\in A\times A|a\prec b\}=\{(a,b)\in B\times B|a\prec b\}$.

כלומר, בעוד היחס בפני עצמו הוא אותה קבוצה (יחס הוא הרי פשוט קבוצה של זוגות) אם הקבוצות שונות, מדובר בקבוצות סדורות שונות.

כמובן שאם זו אותה קבוצה אבל הסידור שונה אז מדובר בקבוצות סדורות שונות.

אם נחזור לסרטוט 1 נוכל לראות, כפי שאמרנו, שיש כמה סוגים של איברים. כאלו שגדולים/קטנים מכולם וכאלו שאף אחד אינו גדול/קטן מהם. נביא הגדרות:

הגדרה: איבר מינימלי/מקסימלי, איבר ראשון/אחרון תהי קבוצה סדורה חלקית $(A,\prec )$ ויהי $a\in A$. איבר $a$ יקרא: איבר מינימלי: אם לא קיים איבר $b\in A$ המקיים $b\prec a$, איבר מקסימלי: אם לא קיים איבר $b\in A$ המקיים $a\prec b$, איבר ראשון: אם לכל $b\in A$ מתקיים $a\preceq b$ ($a\prec b$ או $a=b$). איבר אחרון: אם לכל $b\in A$ מתקיים $b\preceq a$ ($b\prec a$ או $a=b$).

תהי $A=\{a,b,c,d,e,f,g,x,y,z\}$.

התבוננו בתרשים של היחס סדר החלקי $\lessdot$ המוגדר עליה :

${\begin{matrix}g\\\uparrow \\d&&e&&f\\&\nwarrow \nearrow &&\nwarrow \nearrow \\&b&&c\\&&\nwarrow \nearrow \\&&a\end{matrix}}\quad \quad {\begin{matrix}z\\\uparrow \\y\\\uparrow \\x\end{matrix}}$

מהתרשים ניתן לראות שביחס יש ארבעה איברים מקסימליים ($g,e,f,z$, למה?)

ושני איברים מינימליים (מי הם?). נסו לרשום את קבוצת הזוגות שמגדירה את היחס.

אם נקח את התת קבוצה $B=\{a,b,c,d,e,f,g\}$ונצמצם את היחס אליה (בצמצום הכוונה ל-$\lessdot \cap (B\times B)$)

אז ביחס החדש יש 3 איברים מקסימליים, ואיבר קטן ביותר ($a$) [הכוונה, אם נתעלם מהחלק הימני ונסתכל רק ב"גוש" השמאלי שבסרטוט).

התבוננות בתרשים מביאה אותנו לחשוד בטענה הבאה:

טענה: תהי קבוצה סדורה חלקית $(A,\prec )$. ויהי $a\in A$. אם $a$ הוא איבר ראשון אז $a$ הוא האיבר המינימלי היחיד. אם $a$ הוא איבר אחרון אז $a$ הוא האיבר המקסימלי היחיד.

נוכיח את 1. ההוכחה ל-2 דומה ותושאר כתרגיל לקורא.

הוכחה: יהי $a$ איבר ראשון. יהי $b\in A$.

$a$ הוא איבר ראשון ולכן $a\preceq b$.

אם $a=b$ אז סיימנו (המקרה טריוויאלי).

אם $a\neq b$ אז $a\prec b$.

מכיוון שהוכחנו כי יחס סדר חלקי הוא אסימטרי נקבל כי $b{\cancel {\prec }}a$.

בכך הראנו שלא קיים $b\in A$ המקיים $b\prec a$.

כלומר, הראנו כי $a$ איבר מינימלי.

עתה נוכיח כי $a$ הוא האיבר המינימלי היחיד:

יהי $m\in A$ איבר מינימלי.

מכיוון ש-$m$ איבר מינימלי, אז לא קיים $x\in A$ המקיים $x\prec m$ ובפרט $a{\cancel {\prec }}m$.

נניח בשלילה כי $m\neq a$.

מהנחת השלילה נובע כי $a\neq m$ וגם $a{\cancel {\prec }}m$ בסתירה לכך ש-$a$ איבר קטן ביותר.

ההנחה הובילה לסתירה ולכן $a=m$ובכך הראנו כי $a$ הוא האיבר המינימלי היחיד. כפי שרצינו.

שימו לב, הוכחנו כי אם ביחס סדר חלקי יש איבר ראשון/אחרון אז הוא האיבר המינימלי/מקסימלי היחיד. הכיוון השני אינו נכון (חשבו על דוגמה נגדית).

מסקנה מהשפט: אם יש יותר מאיבר מינימלי/מקסימלי אחד אז אין איבר ראשון/אחרון.

משפט: אם $(A,\prec )$ קבוצה סדורה חלקית ו-$B\subseteq A$, אז $(B,\prec )$ סדורה חלקית.

הוכחה:

1. אנטי רפלקסיביות: $x\in B\Rightarrow x\in A\Rightarrow x\not \prec x$.
2. טרנזיטיביות: $x,y,z\in B\land x\prec y\prec z\Rightarrow x,y,z\in A\land x\prec y\prec z\Rightarrow x\prec z$.

יחס סדר מלא

עד כה דיברנו על יחס סדר חלקי. כפי שעלה מההגדרות, לא כל איבר של קבוצה חייב להשתתף ביחס החלקי עליה.

למשל, אם הקבוצה היא $A=\{1,2,3,4\}$ אז היחס $\prec =\{(1,2),(2,3),(1,3)\}$ הוא יחס סדר חלקי על הקבוצה $A$ וכפי שניתן בקלות לראות, 4 בכלל לא נמצא ביחס. הוא לא מתייחס לאף איבר, ואף איבר לא מתייחס אליו.

מה יקרה אם נדרוש מיחס סדר חלקי, שכל איברי הקבוצה ישתתפו בו? לפני שנגדיר יחס סדר מלא ונברר, הנה הגדרה:

הגדרה: יחס משווה יחס $E$ על קבוצה $A$ יקרא משווה או יחס משווה אם כל איברי $A$ ניתנים להשוואה. כלומר, אם לכל $a,b\in A$ מתקיים $aEb$ או $bEa$ או $a=b$.

משנתנו הגדרה זו, נוכל לומר שהיחס בדוגמה שבדיון מקודם אינו יחס משווה היות ו-$4{\cancel {\prec }}3\quad \land \quad 3{\cancel {\prec }}4\quad \land \quad 4\neq 3$.

הגדרה: יחס סדר מלא יחס $\prec$ על קבוצה $A$ יקרא יחס סדר מלא או בקיצור יחס סדר אם הוא מקיים את התנאים הבאים: $\prec$הוא יחס סדר חלקי. $\prec$ הוא יחס משווה.

מכאן אנו מסיקים שכל יחס סדר מלא הוא יחס סדר חלקי, אבל לא כל יחס סדר חלקי הוא יחס סדר מלא (מכאן והלאה, לא נאמר עוד יחס סדר מלא, אלא פשוט יחס סדר).

היחס סדר החלקי הבא $\{(1,2),(1,3),(1,4),(1,5)\}$ על הקבוצה $\{1,2,3,4,5\}$ אינו יחס סדר, שכן 4 ו-3 לא ניתנים להשוואה (מי עוד לא?).

אבל, היחס סדר החלקי הבא על אותה קבוצה הוא כן יחס סדר: $\{(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)\}$ (וודאו זאת!).

נצייר תרשימים של היחסים הללו זה לצד זה (השוו כל תרשים לאוסף הזוגות):

${\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}}$

התרשים הימני הוא התרשים של יחס הסדר (היחס השני) והתרשים משמאל הוא תרשים של יחס הסדר החלקי.

כפי שניתן לראות, יחס סדר אינו מתפצל למסלולים שונים. מסתבר, שהוספת הדרישה לכך שהיחס יהיה משווה, הופכת אותו לסוג של מסלול יחיד.

כדי לנסח הבחנה זו בצורה מדוייקת, הנה המשפט הבא:

משפט: יהי $\prec$ יחס סדר על קבוצה $A$. אם יש ב-$A$ איבר מינימלי, אזי הוא האיבר הראשון. אם יש ב-$A$ איבר מקסימלי, אזי הוא האיבר האחרון.

(ראו הגדרת האיבר האחרון/ראשון אל מול המקסימלי/מינימלי).

אנו נוכיח את 1. ההוכחה ל-2 דומה ותושאר כתרגיל.

הוכחה:

נניח כי קיים איבר מינימלי $m\in A$.

לכן, אין איבר $b\in A$ המקיים $b\prec m$.

לכל $b\in A$ מתקיים $b\prec m$ או $m\prec b$ או $m=b$ (יחס סדר הוא יחס משווה).

ראינו כי $b{\cancel {\prec }}m$ ולכן $m\prec b$ או $m=b$.

כלומר, הראנו שלכל $b\in A$ מתקיים $m\preceq b$ ולכן $m$ הוא איבר קטן ביותר

נביא הגדרה המקבילה להגדרה של קבוצה סדורה חלקית.

הגדרה: יהי $\prec$ יחס סדר מלא על קבוצה $A$. לזוג הסדור $(A,\prec )$ אנו קוראים קבוצה סדורה מלא או בקיצור קבוצה סדורה.

כפי שציינו קודם, קבוצות סדורות שוות זו לזו אם הן אותה קבוצה ויש בהן את אותו הסדר.

דוגמה המוכרת לכם היטב של קבוצה סדורה היא $(\mathbb {N} ,<)$ (יחס הסדר הרגיל).

נוכיח זאת:

ראשית נראה כי מדובר בקבוצה סדורה חלקית.

אין מספר טבעי $n\in \mathbb {N}$ המקיים $n<n$ (כלומר, אין מספר טבעי שקטן מעצמו) ולכן היחס הוא אי-רפלקסיבי.

יהיו $a,b,c\in \mathbb {N}$ המקיימים $a<b$ וגם $b<c$, אנו יודעים שניתן לכתוב זאת גם כך $a<b<c$ ובכתיבה זו, אנו רואים שמדובר ביחס טרנזיטיבי (ניתן לראות דרך ההגדרה של המספרים הטבעיים שנתנה בפרק קודם, ש-$a<b$זה בעצם $a\in b$ ולכן $a\in b\in c$, נדבר על כך בהרחבה בפרק על סודרים).

הראנו כי היחס הוא יחס סדר חלקי. עתה, נראה שהוא גם משווה.

אנו יודעים שלכל שני מספרים טבעיים: אם הם שונים, אז אחד גדול מהשני, ואם אם שווים אף אחד אינו גדול מהשני.

אכן מדובר ביחס סדר.

הראו שגם הממשיים והרציונליים עם הסדר הרגיל הן קבוצות סדורות.

נגדיר יחס $\prec$ על המספרים הטבעיים: לכל $m,n\in \mathbb {N}$ מתקיים $n\prec m$ אם ורק אם $n<m$ ושניהם זוגיים או $n<m$ושנייהם אי זוגיים או $n$ זוגי ו-$m$ אי-זוגי.

תרשים של יחס זה יראה כך: $0,2,4,6,8,10,...,1,3,5,7,9,11,...$ (קודם כך הזוגיים בסדר הרגיל ואז כל האי זוגיים). הסבירו לעצמכם מדוע מדובר ביחס סדר.

דוגמה אחרונה ומוכרת ליחס סדר היא הדוגמה הבאה:

יהיו הקבוצות הסדורות $(A,\prec _{1})$ ו-$(B,\prec _{2})$. נגדיר יחס $\prec$ על הקבוצה $A\times B$ באופן הבא:

לכל $(a_{1},b_{1}),(a_{2},b_{2})\in A\times B$ מתקיים $(a_{1},b_{1})\prec (a_{2},b_{2})$ אם ורק אם $a_{1}\prec _{1}a_{2}$ או $a_{1}=a_{2}$ וגם $b_{1}\prec _{2}b_{2}$.

קראו טוב את ההגדרה וודאו שאכן מדובר ביחס סדר.

יחס סדר זה מכונה בשם "הסדר המילוני השמאלי" כי הוא מסדר את הזוגות כמו במילון (מילון משמאל לימין) אם האותיות השמאליות קטנות יותר, אז הן יהיו משמאל, אם הן שוות אז האותיות השניות קובעות.

איך יוגד הסדר המילוני הימני?

אולי הדוגמאות עד כה עוררו את חשדכם בטענה הבאה:

טענה: תהי $(A,\prec )$ קבוצה סדורה. יהיו $a,b\in A$. מתקיים אחד ורק אחד מהמצבים הבאים: $a\prec b$, $b\prec a$, $a=b$.

הוכחת הטענה תושאר כתרגיל לקורא (הניחו בשלילה כי מתקיימים שניים מן המצבים במקביל, ראו הוכחת האסימטריות של יחס סדר חלקי).

מטענה זו אנו מקבלים בין היתר כי גם יחסי סדר, בדומה ליחסי סדר חלקיים, הם אסימטרים.

תהי $A$ קבוצה לא ריקה. עבור אילו תנאים הזוג $({\mathcal {P}}(A),\subset )$ (קבוצת החזקה) הוא קבוצה סדורה? ועבור אילו תנאים הוא קבוצה סדורה חלקית? (רמז: התחילו מלהתבונן בקבוצה הריקה).

לסיום סעיף זה, נביא עוד טענה ומשפט:

טענה: יהי $\prec$ יחס סדר על קבוצה $A$. כל הרחבה או צמצום (ממש) של יחס זה אינו מהווה יחס סדר על הקבוצה $A$. כלומר, אם $\prec _{*}\subset \prec$ או $\prec \subset \prec _{*}$ אז $\prec _{*}$ אינו יחס סדר על הקבוצה $A$.

הוכחה: יהי $\prec _{*}\subset \prec$. לכן קיימים $a,b\in A$ המקיימים $a\prec b$ וגם $a{\cancel {\prec _{*}}}b$.

מתכונת ההשוואה נקבל כי $b{\cancel {\prec }}a$ וגם $a\neq b$.

מכיוון ש- $\prec _{*}\subset \prec$ אז $b{\cancel {\prec }}a\to b{\cancel {\prec _{*}}}a$.

בסה"כ הראנו כי $a\neq b$ וגם $a{\cancel {\prec _{*}}}b$ וגם $b{\cancel {\prec _{*}}}a$.

מכך נובע כי $\prec _{*}$ אינו יחס משווה ולכן אינו יחס סדר. כפי שרצינו להוכיח.

יהי $\prec \subset \prec _{*}$. נניח בשלילה כי $\prec _{*}$ יחס סדר.

מהתוצה של החצי הקודם של ההוכחה נקבל כי $\prec$ אינו יחס סדר. בסתירה לנתוני הטענה.

ההנחה הובילה לסתירה, ולכן $\prec _{*}$ אינו יחס סדר.

משפט: תהי $(A,\prec )$ קבוצה סדורה. אם $A$ קבוצה סופית אז יש בה איבר גדול ביותר ואיבר קטן ביותר.

הוכחה: נניח בשלילה שאין בה איבר גדול ביותר.

נסמן ב-$a_{1},a_{2},a_{3},...,a_{n}$ את כל איברי הקבוצה.

מהנחת השלילה לכל $a_{i}\in A$ קיים $a_{j}\in A$ כך שמתקיים $a_{i}\prec a_{j}$.

תהי $i_{1},i_{2},i_{3},...,i_{n}$ סדרת אינדקסים שמקיימת את מה שנאמר בשורה מעל (לכל איברי הקבוצה).

כלומר, $a_{i_{1}}\prec a_{i_{2}}\prec a_{i_{3}}\prec ...\prec a_{i_{n}}$ (כפי שראינו בדיונים קודמים, מהגדרת יחס הסדר מתחייב שנקבל שרשרת כזאת).

מכאן שגם ל-$a_{i_{n}}$ קיים $a_{i_{j}}$ כלשהו המקיים $a_{i_{n}}\prec a_{i_{j}}$ כלומר:

$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}}$

ומצאנו ש-$a_{i_{n}}\prec a_{i_{j}}$ וגם $a_{i_{j}}\prec a_{i_{n}}$ בסתירה לטענה שהוכחנו קודם.

הנחת השלילה הובילה לסתירה, לכן יש איבר גדול ביותר.

ההוכחה עבור איבר קטן ביותר אנלוגית.

משפט: אם $(A,\prec )$ קבוצה סדורה ו-$B\subseteq A$, אז $(B,\prec )$ סדורה.

הוכחה: $(A,\prec )$ סדורה חלקית לכן $(B,\prec )$ סדורה חלקית. כלומר עלינו להראות רק את ההשוואה: $x,y\in B\Rightarrow x,y\in A\Rightarrow x\prec y\lor y\prec x\lor x=y$.

יחס סדר חלש

כל היחסים שהובאו עד כה היו יחסי סדר המכונים יחסי סדר חזקים. נביא את ההגדרה ליחס סדר אחר:

הגדרה: יחס סדר חלש יחס סדר חלקי חלש הוא יחס $\preceq$ המקיים: רפלקסיביות: לכל x מתקיים $x\preceq x$. אנטי-סימטריה: $x\preceq y\land y\preceq x\Rightarrow x=y$. טרנזיטיביות: $x\preceq y\land y\preceq z\Rightarrow x\preceq z$. היחס יקרא מלא אם בנוסף הוא מקיים: $\forall x,y:x\preceq y\lor y\preceq x$.

דוגמאות ליחסי סדר חלשים הם היחס $\leq$ על $\mathbb {R}$, היחס $\subseteq$ על ${\mathcal {P}}(A)$ לכל קבוצה $A$, והיחס $\Rightarrow$ על טענות בוליאניות.

כל ההגדרות של מינימום, מקסימום, ראשון ואחרון זהות ביחסי סדר חלשים כביחסי סדר חזקים.

משפט: אם $(A,\preceq )$ סדורה בסדר חלש (חלקי או מלא), ו-$B\subseteq A$, אז $(B,\preceq )$ סדורה בסדר חלש (חלקי או מלא).

הוכחה: נראה קודם כל את המקרה שבו הסדר הוא חלקי:

1. רפלקסיביות: $x\in B\Rightarrow x\in A\Rightarrow x\preceq x$.
2. טרנזיטיביות: $x,y,z\in B\land x\preceq y\preceq z\Rightarrow x,y,z\in A\land x\preceq y\preceq z\Rightarrow x\preceq z$.

כעת נוכיח במקרה שבו הסדר הוא מלא, כלומר נוכיח את תכונת ההשוואה: $x,y\in B\Rightarrow x,y\in A\Rightarrow x\preceq y\lor y\preceq x$.

יחס סדר טוב

הגדרה: יחס סדר טוב נאמר כי יחס סדר מלא $\prec$ על קבוצה $A$ הוא יחס סדר טוב, אם לכל תת קבוצה $S\subseteq A$ שאינה ריקה, יש איבר ראשון בקבוצה הסדורה $(S,\prec )$. נאמר גם כי $(A,\prec )$ היא קבוצה סדורה היטב.

הדוגמה הפשוטה ביותר ליחס סדר טוב הוא היחס $<$ על הקבוצה $\mathbb {N}$.

הגדרה: עוקב מיידי תהי $(A,\prec )$ קבוצה סדורה היטב. נגדיר את העוקב המיידי (בקצרה: עוקב) של $x\in A$, כאיבר $S(x)\in A$ המקיים $x\prec S(x)$, שעבורו לא קיים $y\in A$ השונה מ $x,S(x)$ כך ש $x\prec y\prec S(x)$.

נראה שלכל איבר (מלבד האחרון, אם הוא קיים) יש עוקב מיידי: יהי $x\in A$ ונגדיר $S=\{y:x\prec y\}$. מכיוון שx אינו האחרון, S אינה ריקה, ויהי $x'$ האיבר הראשון ב$S$. כל האיברים בS גדולים מx, לכן $x\prec x'$. נראה שלא קיים $x\prec y\prec x'$: בשביל זה חייב להתקיים $x\prec y$, לכן $y\in S$. מכיוון ש$x'$ ראשון בS, נקבל $x'\prec y$, ומכיוון ש$y\not =x'$ נקבל $y\not \prec x'$. קיבלנו כי $x'=S(x)$.

הגדרה: תהי $(A,\prec )$ קבוצה סדורה היטב, ויהי $a\in A$. נאמר כי $a$ הוא איבר עוקב אם ורק אם קיים $x\in A$ כך ש$a=S(x)$. אם $a$ אינו איבר עוקב, וגם $a\neq 0$, נאמר כי $a$ הוא איבר גבולי.

משפט: $(A,\prec )$ סדורה היטב, אם ורק אם לא קיימת סדרה יורדת אינסופית (מהצורה $a_{0}\succ a_{1}\succ a_{2}...$) ב$(A,\prec )$.

הוכחה: נניח שקיימת סדרה אינסופית $\{a_{n}\}_{n=0}^{\infty }$ המקיימת $a_{n+1}\prec a_{n}$. אז הקבוצה $S=\{a_{n}:n\in \mathbb {N} \}$ היא תת קבוצה של $A$, ולכל איבר בה יש איבר קטן ממנו, לכן אין בה ראשון, לכן $(A,\prec )$ לא סדורה היטב.

נניח ש$(A,\prec )$ לא סדורה היטב, אז תהי $S\subseteq A$ לא ריקה שאין בה איבר ראשון. נבחר $a_{0}\in S$ (קיים כי S לא ריקה). כעת נפעל ברקורסיה ולכל n טבעי, נגדיר את $a_{n}$ כאיבר בS שקטן מ$a_{n-1}$. (קיים כי אין ראשון). הסדרה $\{a_{n}\}_{n=0}^{\infty }$ היא סדרה יורדת אינסופית.

משפט: אם $(A,\prec )$ סדורה היטב ו-$B\subseteq A$, אז $(B,\prec )$ סדורה היטב.

הוכחה: $(B,\prec )$ סדורה מלא, לכן יש להראות רק את תכונת הסדר הטוב. אם היתה ב$(B,\prec )$ סדרה יורדת אינסופית, אז סדרה זו היתה גם ב$(A,\prec )$, בסתירה לסדר הטוב. לכן אין סדרה אינסופית יורדת ב$(B,\prec )$, ומהמשפט הקודם נקבל ש$(B,\prec )$ סדורה היטב.

נרחיב על סדרים טובים במסגרת משפט הסדר הטוב, הקובע כי על כל קבוצה ניתן להגדיר סדר טוב, וכן במסגרת אינדוקציה טרנספיניטית, שהיא שיטה להוכחת תכונות בקבוצה סדורה היטב, המכלילה את הרעיון של אינדוקציה מתמטית.

הפרק הקודם: יחסי שקילות

יחסי סדר

הפרק הבא: עוצמות