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

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

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

יחס סדר חלקי

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

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

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

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

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

הקבוצה $\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{array}{ccc}4& & 5\\ \uparrow & & \uparrow \\ 2& & 3\\ & \nwarrow \nearrow & \\ & 1& \end{array}$(סרטוט 1)

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

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

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

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

${|}_2=\{(a,b)|\mathrm{\exists }m\in \mathbb{N}:m>1\wedge b=a\cdot m\}$

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

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

תכונה ידוע היא שלכל מספר טבעי $n$ שונה מ-0, מתקיים $\frac{n}{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, האם עדיין היה מדובר ביחס סדר חלקי?

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

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

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

כלומר $(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=\{a,b,c,d,e,f,g,x,y,z\}$.

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

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

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

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

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

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

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

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

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

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

יחס סדר מלא

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

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

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

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

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

היחס סדר החלקי הבא $\{(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{array}{cccccc}& 4& & 5& & \\ & & \nwarrow \nearrow \\ 2& \leftarrow & 1& \to & 3\end{array}\begin{array}{c}5\\ \uparrow \\ 4\\ \uparrow \\ 3\\ \uparrow \\ 2\\ \uparrow \\ 1\end{array}$

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

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

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

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

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

דוגמה המוכרת לכם היטב של קבוצה סדורה היא $(\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$ קבוצה לא ריקה. עבור אילו תנאים הזוג $(𝒫(A),\subset )$ (קבוצת החזקה) הוא קבוצה סדורה? ועבור אילו תנאים הוא קבוצה סדורה חלקית? (רמז: התחילו מלהתבונן בקבוצה הריקה).

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

יחס סדר חלש

כל היחסים שהובאו עד כה היו יחסי סדר המכונים יחסי סדר חזקים. נביא את ההגדרה ליחס סדר אחר: תבנית:מבנה תבנית דוגמאות ליחסי סדר חלשים הם היחס $\le$ על $ℝ$, היחס $\subseteq$ על $𝒫(A)$ לכל קבוצה $A$, והיחס $\Rightarrow$ על טענות בוליאניות.

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

יחס סדר טוב

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

תבנית:מבנה תבנית נראה שלכל איבר (מלבד האחרון, אם הוא קיים) יש עוקב מיידי: יהי $x\in A$ ונגדיר $S=\{y:x\prec y\}$. מכיוון שx אינו האחרון, S אינה ריקה, ויהי $x^{\prime }$ האיבר הראשון ב$S$. כל האיברים בS גדולים מx, לכן $x\prec x^{\prime }$. נראה שלא קיים $x\prec y\prec x^{\prime }$: בשביל זה חייב להתקיים $x\prec y$, לכן $y\in S$. מכיוון ש$x^{\prime }$ ראשון בS, נקבל $x^{\prime }\prec y$, ומכיוון ש$y=x^{\prime }$ נקבל $y\prec ̸x^{\prime }$. קיבלנו כי $x^{\prime }=S(x)$. תבנית:מבנה תבנית תבנית:משפט הוכחה: נניח שקיימת סדרה אינסופית $\{a_n{\}}_{n=0}^{\mathrm{\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}^{\mathrm{\infty }}$ היא סדרה יורדת אינסופית.

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