קדם סדר

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

בהתאמה מוגדר גם קדם-סדר מלא הוא קדם סדר חלקי שמקיים גם את עקרון ההשוואה (או טוטאליות, באנגלית: totality או completeness), כלומר לכל x,y \in A מתקיים x \le  y או y \le  x.

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


לדוגמה, יחס החילוק \ a|b בין מספרים שלמים הוא קדם-סדר, אבל אינו סדר (למשל, המספרים 2 ו- 2- מחלקים זה את זה). דוגמה זו ניתן להכליל לכל חוג, והיא שימושית בעיקר בתחומי שלמות.

מתוך קדם סדר אפשר לקבל יחס סדר באופן הבא: מגדירים "\ a \equiv b אם ורק אם \ a \le b וגם \ b \le a", ומתקבל יחס שקילות. על מחלקות השקילות של יחס זה אפשר להגדיר את היחס \ [a]<[b] אם ורק אם \ a \le b , וזהו יחס סדר. נראה שאכן ההגדרה לא תלויה בבחירת הנציגים של מחלקות השיקלות. אם  b' \in [b] ,  a' \in [a] ואם מתקיים  a \le  b אז מתקיים גם  a' \le  b'. לפי הגדרת  a' \in [a] פירושו a' \le a לפי הגדרת  b' \in [b] פירושו  b \le b' ולכן אם \ a < b " אז מטרנזיטיביות מתקיים a' \le a \le b \le b' כלומר  a' \le b' ולכן היחס מוגדר היטב.