סדר חלקי – הבדלי גרסאות

עיון אינטראקטיבי בהיסטוריה

→ העריכה הקודמת העריכה הבאה ←

תוכן שנמחק תוכן שנוסף

חזותיקוד ויקי

בשורה

גרסה מ־02:33, 2 בינואר 2018

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

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

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

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

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

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

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

דוגמאות:

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

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

איבר $\!\,a\in X$ נקרא איבר מינימלי (איבר מזערי) אם לא קיים $\!\,b\in X$ השונה ממנו כך ש $\!\,b\leq a$ .

איבר $\!\,a\in X$ נקרא איבר מקסימלי (איבר מרבי) אם לא קיים $\!\,b\in X$ השונה ממנו כך ש $\!\,a\leq b$ .

איבר $\!\,a\in X$ נקרא מינימום (או לחלופין איבר קטן ביותר או איבר ראשון) אם לכל $\!\,b\in X$ מתקיים $\!\,a\leq b$ .

איבר $\!\,a\in X$ נקרא מקסימום (או לחלופין איבר גדול ביותר או איבר אחרון) אם לכל $\!\,b\in X$ מתקיים $\!\,b\leq a$ .

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

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

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

ראו גם

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

@@ שורה 12: / שורה 12: @@
 הקבוצה X, יחד עם יחס הסדר, נקראת [[קבוצה סדורה]].
-באופן כללי יכולים להיות שני איברים של X שאינם ניתנים להשוואה מבחינת היחס, ולכן הוא נקרא גם '''יחס סדר חלקי'''. אם עבור כל <math>\!\, a,b\isin X</math> מתקיים <math>\!\, a\le b</math> או <math>\!\, b\le a</math> אז קוראים ליחס <math>\!\, \le</math> '''סדר לינארי''' (או '''[[סדר מלא]]'''), ולזוג <math>\!\, \left(X, \le\right)</math> '''קבוצה סדורה לינארית''', או '''[[שרשרת (מתמטיקה)|שרשרת]]'''.
+באופן כללי יכולים להיות שני איברים של X שאינם ניתנים להשוואה מבחינת היחס, ולכן הוא נקרא גם '''יחס סדר חלקי'''. אם עבור כל <math>\!\, a,b\isin X</math> מתקיים <math>\!\, a\le b</math> או <math>\!\, b\le a</math> אז קוראים ליחס <math>\!\, \le</math> '''סדר ליניארי''' (או '''[[סדר מלא]]'''), ולזוג <math>\!\, \left(X, \le\right)</math> '''קבוצה סדורה ליניארית''', או '''[[שרשרת (מתמטיקה)|שרשרת]]'''.
 דוגמאות:
-* קבוצת כל [[מספר טבעי|המספרים הטבעיים]] <math>\!\, \left(\mathbb{N},\le\right)</math> עם הסדר הסטנדרטי עליהם, היא קבוצה סדורה לינארית. כך גם ה[[ממשיים]].
+* קבוצת כל [[מספר טבעי|המספרים הטבעיים]] <math>\!\, \left(\mathbb{N},\le\right)</math> עם הסדר הסטנדרטי עליהם, היא קבוצה סדורה ליניארית. כך גם ה[[ממשיים]].
-*יחס החלוקה של [[מספר טבעי|מספרים טבעיים]] <math>|</math> מוגדר כך ש-<math>m|n</math> אם ורק אם <math>m</math> [[מחלק]] את <math>n</math>. הקבוצה <math>\left(\mathbb{N},|\right)</math> היא קבוצה סדורה חלקית שאינה סדורה לינארית, שכן לא ניתן, למשל, להשוות בין 5 ו-2, שאינם מחלקים אחד את השני.
+*יחס החלוקה של [[מספר טבעי|מספרים טבעיים]] <math>|</math> מוגדר כך ש-<math>m|n</math> אם ורק אם <math>m</math> [[מחלק]] את <math>n</math>. הקבוצה <math>\left(\mathbb{N},|\right)</math> היא קבוצה סדורה חלקית שאינה סדורה ליניארית, שכן לא ניתן, למשל, להשוות בין 5 ו-2, שאינם מחלקים אחד את השני.
 *יחס החלוקה אינו יחס סדר על ה[[מספר שלם|מספרים השלמים]] כי אינו אנטי-סימטרי: <math>1|-1</math> וגם <math>-1|1</math> אף על פי ש-<math>-1\ne 1</math>.
@@ שורה 31: / שורה 31: @@
 ההבדל בין איבר מקסימלי למקסימום הוא שבקבוצה סדורה חלקית לא תמיד ניתן להשוות איבר לשאר האיברים, ואילו מקסימום חייב להיות בר השוואה לכל שאר האיברים.
-קבוצה סדורה לינארית <math>\!\,\left(X,\le\right)</math> שבה יש איבר ראשון לכל תת-קבוצה <math>\!\,X </math>, נקראת '''[[סדר טוב|קבוצה סדורה היטב]]'''.
+קבוצה סדורה ליניארית <math>\!\,\left(X,\le\right)</math> שבה יש איבר ראשון לכל תת-קבוצה <math>\!\,X </math>, נקראת '''[[סדר טוב|קבוצה סדורה היטב]]'''.
 כאשר מתקיים

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