סדר חלקי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
דיאגרמת הסה של איברי קבוצת החזקה של {x, y, z} כאשר הסדר החלקי המוגדר עליהם הוא הכלה

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

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

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

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

הקבוצה X, יחד עם יחס הסדר, נקראת קבוצה סדורה.

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

דוגמאות:

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

איברים מיוחדים[עריכת קוד מקור | עריכה]

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

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

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

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

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

קבוצה סדורה לינארית שבה יש איבר ראשון לכל תת-קבוצה , נקראת קבוצה סדורה היטב.

כאשר מתקיים , ואין כך ש– , אז אומרים ש– מכסה את (ומכאן שבסדר צפוף אין שני איברים שמכסים זה את זה).

ראו גם[עריכת קוד מקור | עריכה]