סדר חלקי

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

• היחס רפלקסיבי, אנטי-סימטרי חלש, טרנזיטיבי – זהו יחס סדר חלש.
• היחס אי-רפלקסיבי, אנטי-סימטרי חזק, טרנזיטיבי – זהו יחס סדר חזק.

דיאגרמת הסה של איברי קבוצת החזקה של ${\displaystyle \{x,y,z\}}$ כאשר הסדר החלקי המוגדר עליהם הוא הכלה. איבר המינימום הוא ${\displaystyle \emptyset }$ ואיבר המקסימום ${\displaystyle \{x,y,z\}}$

הקבוצה ${\displaystyle X}$, יחד עם יחס הסדר, נקראת קבוצה סדורה.

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

סימון

מקובל לסמן יחסי סדר בווריאציות על סימן האי-שוויון ${\displaystyle <}$, והיפוכו ${\displaystyle >}$. הסימון ליחסי סדר חלשים כולל גם רמז לסימן השוויון, כגון ${\displaystyle \leq ,\preceq }$, בעוד שהסימון ליחסי סדר חזקים אינו כולל אותו: ${\displaystyle <,\prec }$).

יחסי סדר חלשים וחזקים

שני סוגי היחסים כרוכים זה בזה: אם ${\displaystyle \leq }$ יחס סדר חלש, אז היחס (${\displaystyle a\leq b}$ אבל ${\displaystyle a\neq b}$) הוא יחס סדר חזק. אם ${\displaystyle <}$ יחס סדר חזק, אז היחס (${\displaystyle a<b}$ או ${\displaystyle a=b}$) הוא יחס סדר חלש. יחס סדר לא יכול להיות גם חזק וגם חלש, למעט המקרה המנוון של היחס הריק על הקבוצה הריקה.

באופן כללי יכולים להיות שני איברים של ${\displaystyle X}$ שאינם ניתנים להשוואה מבחינת היחס, ולכן הוא נקרא גם יחס סדר חלקי. אם עבור כל ${\displaystyle a,b\in X}$ מתקיים ${\displaystyle a\leq b}$ או ${\displaystyle b\leq a}$ אז קוראים ליחס ${\displaystyle \leq }$ סדר ליניארי או סדר מלא, ולזוג ${\displaystyle (X,\leq )}$ קבוצה סדורה ליניארית, או שרשרת.

דוגמאות

• קבוצת כל המספרים הטבעיים המסומנת כך: ${\displaystyle (\mathbb {N} ,\leq )}$ עם הסדר הסטנדרטי עליהם, היא קבוצה סדורה ליניארית. כך גם הממשיים.
• יחס החלוקה של מספרים טבעיים המסומן כך: ${\displaystyle \mid }$ מוגדר כך: ${\displaystyle m\mid n}$ אם ורק אם ${\displaystyle m}$ מחלק את ${\displaystyle n}$ ללא שארית. הקבוצה המחולקת ${\displaystyle (\mathbb {N} ,\mid )}$ היא קבוצה סדורה חלקית שאינה סדורה ליניארית, שכן לא ניתן, למשל, להשוות בין 5 ו-2, שאינם מחלקים זה את זה ללא שארית. יחס החלוקה אינו יחס סדר על המספרים השלמים כי אינו אנטי-סימטרי: ${\displaystyle 1\mid -1}$ וגם ${\displaystyle -1\mid 1}$ אף כי ${\displaystyle -1\neq 1}$.

איברים מיוחדים

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

• איבר ${\displaystyle a\in X}$ נקרא איבר מינימלי או איבר מזערי אם לא קיים ${\displaystyle b\in X}$ השונה ממנו עבורו ${\displaystyle b\leq a}$.
• איבר ${\displaystyle a\in X}$ נקרא איבר מקסימלי או איבר מרבי אם לא קיים ${\displaystyle b\in X}$ השונה ממנו עבורו ${\displaystyle a\leq b}$.
• איבר ${\displaystyle a\in X}$ נקרא מינימום (גם: איבר קטן ביותר או איבר ראשון) אם לכל ${\displaystyle b\in X}$ מתקיים ${\displaystyle a\leq b}$.
• איבר ${\displaystyle a\in X}$ נקרא מקסימום (גם: איבר גדול ביותר או איבר אחרון) אם לכל ${\displaystyle b\in X}$ מתקיים ${\displaystyle b\leq a}$.

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

בקבוצה סדורה ליניארית ${\displaystyle (X,\leq )}$ שבה יש איבר ראשון לכל תת-קבוצה של ${\displaystyle X}$, נקראת קבוצה סדורה היטב.

כאשר מתקיים ${\displaystyle x>y}$, ואין ${\displaystyle z}$ עבורו ${\displaystyle x>z>y}$, אזי אומרים כי ${\displaystyle x}$ מכסה את ${\displaystyle y}$ (ומכאן שבסדר צפוף אין שני איברים שמכסים זה את זה).

ראו גם

• תורת הקבוצות - מונחים

קישורים חיצוניים

• סדר חלקי, באתר MathWorld (באנגלית)
• גדי אלכסנדרוביץ', תורת הקבוצות - יחסי סדר, באתר "לא מדויק", 10 בינואר 2020