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

מתוך ויקיפדיה, האנציקלופדיה החופשית
תוכן שנמחק תוכן שנוסף
מ ←‏פתיח: תיקון קישור פנימי.
שדדשכ (שיחה | תרומות)
שורה 2: שורה 2:
ב[[תורת הקבוצות]], '''סדר חלקי''' (מכונה גם "'''סדר חלקי חלש'''" או "'''סדר חלש'''") על [[קבוצה (מתמטיקה)|קבוצה]] X הוא [[יחס]] <math>\!\, \le</math> המקיים שלוש תכונות:
ב[[תורת הקבוצות]], '''סדר חלקי''' (מכונה גם "'''סדר חלקי חלש'''" או "'''סדר חלש'''") על [[קבוצה (מתמטיקה)|קבוצה]] X הוא [[יחס]] <math>\!\, \le</math> המקיים שלוש תכונות:
*[[יחס רפלקסיבי|רפלקסיביות]]: לכל <math>\!\, a\isin X</math> מתקיים <math>\!\,a\le a </math>.
*[[יחס רפלקסיבי|רפלקסיביות]]: לכל <math>\!\, a\isin X</math> מתקיים <math>\!\,a\le a </math>.
*[[יחס אנטי-סימטרי|אנטיסימטריות]]: אם <math>\!\,a\le b </math> וגם <math>\!\, b\le a</math> אז <math>\!\,a=b </math>.
*[[יחס אנטי-סימטרי|אנטי-סימטריות]]: אם <math>\!\,a\le b </math> וגם <math>\!\, b\le a</math> אז <math>\!\,a=b </math>.
*[[יחס טרנזיטיבי|טרנזיטיביות]]: אם <math>\!\,a\le b</math> וגם <math>\!\, b\le c</math> אז <math>\!\, a\le c</math>.
*[[יחס טרנזיטיבי|טרנזיטיביות]]: אם <math>\!\,a\le b</math> וגם <math>\!\, b\le c</math> אז <math>\!\, a\le c</math>.
קבוצה שמוגדר עליה יחס סדר חלקי נקראת '''קבוצה סדורה''' (או '''קבוצה סדורה חלקית''').
קבוצה שמוגדר עליה יחס סדר חלקי נקראת '''קבוצה סדורה''' (או '''קבוצה סדורה חלקית''').


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

יחס אנטי-סימטרי חזק וטרנזיטיבי נקרא '''יחס סדר חזק''' ומסומן a>b. ניתן להגדיר באמצעותו יחס סדר חלש: a≥b אם a>b או a=b. לחילופין ניתן באמצעות הסדר החלש להגדיר סדר חזק: a>b אם a≥b וגם a≠b.


אם עבור כל שני איברים <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>\!\, a,b\isin X</math> מתקיים <math>\!\, a\le b</math> או <math>\!\, b\le a</math> אז קוראים ליחס <math>\!\, \le</math> '''סדר לינארי''' (או '''[[סדר מלא]]'''), ולזוג <math>\!\, \left(X, \le\right)</math> '''קבוצה סדורה לינארית''', או '''[[שרשרת_(מתמטיקה)|שרשרת]]'''.

גרסה מ־20:31, 30 בנובמבר 2013

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

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

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

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

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

יחס אנטי-סימטרי חזק וטרנזיטיבי נקרא יחס סדר חזק ומסומן a>b. ניתן להגדיר באמצעותו יחס סדר חלש: a≥b אם a>b או a=b. לחילופין ניתן באמצעות הסדר החלש להגדיר סדר חזק: a>b אם a≥b וגם a≠b.

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

דוגמאות:

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

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

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

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

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

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

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

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

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

ראו גם