קדם סדר

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

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

מקדם סדר נתון אפשר לקבל יחס סדר באופן הבא: מגדירים "\ a \equiv b אם ורק אם \ (a,b)\in R וגם \ (b,a)\in R", ומתקבל יחס שקילות. על מחלקות השקילות של יחס זה אפשר להגדיר את היחס \ [a]<[b] אם ורק אם \ (a,b)\in R, וזהו יחס סדר.

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