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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

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

יחס סדר חלקי[עריכה]

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

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

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

הגדרה: יחס סדר חלקי (Partially ordered)

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

  • אי-רפלקסיבי: לכל מתקיים כי (כלומר ).
  • טרנזיטיבי: לכל אם וגם אז

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

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

הקבוצה היא יחס סדר חלקי.

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

ניתן גם לראות כי וגם .

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

(סרטוט 1)

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

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


טענה:

יהי יחס סדר חלקי על קבוצה .

היחס הוא יחס אסימטרי. כלומר, לכל אם אז


הוכחה: יהיו המקיימים .

נניח בשלילה כי .

מטרנזיטיביות נקבל כי בסתירה לכך שהיחס אי-רפלקסיבי.

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

מש"ל.PNG

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

נתבונן ביחס הבא על המספרים הטבעיים החיוביים :

(כלומר אם ורק אם מתחלק ב- ללא שארית ותוצאת החלוקה גדולה מ-1. למשל אבל וגם )

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

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

נניח כי ו- לכן קיימים טבעיים עבורם וגם .

מטרנזיטיביות השוויון (ראה יחסי שקילות) נקבל כי . כלומר .

כמו כן, ולכן .

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

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

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

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


הגדרה: קבוצה סדורה חלקית

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

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

כלומר אם ורק אם וגם .

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

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

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

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

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


הגדרה: איבר מינימלי/מקסימלי, איבר קטן/גדול ביותר

תהי קבוצה סדורה חלקית ויהי . איבר יקרא:

  1. איבר מינימלי: אם לא קיים איבר המקיים ,
  2. איבר מקסימלי: אם לא קיים איבר המקיים ,
  3. איבר קטן ביותר: אם לכל מתקיים ( או ).
  4. איבר גדול ביותר: אם לכל מתקיים ( או ).

תהי .

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

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

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

אם נקח את התת קבוצה ונצמצם את היחס אליה (בצמצום הכוונה ל-)

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

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

טענה:

תהי קבוצה סדורה חלקית . ויהי .

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

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


הוכחה: יהי איבר קטן ביותר. יהי .

הוא איבר קטן ביותר ולכן .

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

אם אז .

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

בכך הראנו שלא קיים המקיים .

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

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

יהי איבר מינימלי.

מכיוון ש- איבר מינימלי, אז לא קיים המקיים ובפרט .

נניח בשלילה כי .

מהנחת השלילה נובע כי וגם בסתירה לכך ש- איבר קטן ביותר.

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

מש"ל.PNG

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

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

יחס סדר מלא[עריכה]

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

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

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


הגדרה: יחס משווה

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

כלומר, אם לכל מתקיים או או .

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


הגדרה: יחס סדר מלא

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

  • הוא יחס סדר חלקי.
  • הוא יחס משווה.

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

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

אבל, היחס סדר החלקי הבא על אותה קבוצה הוא כן יחס סדר: (וודאו זאת!).

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

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

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

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


משפט:

יהי יחס סדר על קבוצה .

  1. אם יש ב- איבר מינימלי, אזי הוא האיבר הקטן ביותר.
  2. אם יש ב- איבר מקסימלי, אזי הוא האיבר הגדול ביותר.

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

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


הוכחה:

נניח כי קיים איבר מינימלי .

לכן, אין איבר המקיים .

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

ראינו כי ולכן או .

כלומר, הראנו שלכל מתקיים ולכן הוא איבר קטן ביותר


מש"ל.PNG

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

הגדרה:

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

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

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

נוכיח זאת:

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

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

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

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

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

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

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

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

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

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

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

לכל מתקיים אם ורק אם או וגם .

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

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

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

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

טענה:

תהי קבוצה סדורה. יהיו . מתקיים אחד ורק אחד מהמצבים הבאים: , , .

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

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

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

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

טענה:

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

כלומר, אם או אז אינו יחס סדר על הקבוצה .


הוכחה: יהי . לכן קיימים המקיימים וגם .

מתכונת ההשוואה נקבל כי וגם .

מכיוון ש- אז .

בסה"כ הראנו כי וגם וגם .

מכך נובע כי אינו יחס משווה ולכן אינו יחס סדר. כפי שרצינו להוכיח.

יהי . נניח בשלילה כי יחס סדר.

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

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


מש"ל.PNG


משפט:

תהי קבוצה סדורה.

אם קבוצה סופית אז יש בה איבר גדול ביותר ואיבר קטן ביותר.


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

נסמן ב- את כל איברי הקבוצה.

מהנחת השלילה לכל קיים כך שמתקיים .

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

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

מכאן שגם ל- קיים כלשהו המקיים כלומר:

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

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

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


מש"ל.PNG

יחס סדר חלש[עריכה]

יחס סדר טוב[עריכה]