סדר מלא

בתורת הקבוצות, סדר מלא (או סדר לינארי) הוא סדר חלקי שמקיים גם את תכונות ההשוואה, כלומר, לכל $\ a$ ו-$\ b$ בקבוצה הסדורה חלקית $\ \left(A, \le \right)$ מתקיים $\ a \le b$ או $\ b \le a$. קבוצה הסדורה בסדר מלא נקראת קבוצה סדורה (או קבוצה סדורה לינארית או שרשרת).

דוגמאות:

• היחס קטן או שווה על קבוצת המספרים הטבעיים, שנסמנו $\!\, \left(\mathbb{N},\le\right)$, הוא סדר מלא.
• היחס קטן על קבוצת המספרים הטבעיים הוא סדר מלא חזק (כפי שיוגדר בהמשך הערך).
• על צבעי האור בקשת הצבעים ניתן להגדיר סדר מלא, לפי אורך הגל של כל צבע. לפי יחס סדר זה, סגול קטן מכחול שקטן מאדום וכו'.

הגדרה

קבוצה $\ A$ שעליה מוגדר יחס $\!\, \le$ תסומן $\ \left( A, \le \right)$ ותקרא סדורה בסדר מלא אם ורק אם לכל $\ b, a$ ו-$\ c$ ב-$\ A$ היחס מקיים:

• רפלקסיביות: לכל $\!\, a\isin A$ מתקיים $\!\,a\le a$.
• אנטי-סימטריות (antisymmetry) - אם $\ a \le b$ וגם $\ b \le a$ אז $\ a=b$;
• טרנזיטיביות (transitivity) - אם $\ a \le b$ וגם $\ b \le c$ אז $\ a \le c$;
• השוואתיות (או טוטאליות, באנגלית: totality או completeness) - לכל $\ a$ ו-$\ b$ מתקיים $\ a \le b$ או $\ b \le a$.

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

סדר מלא חזק

עבור כל סדר מלא $\ \le$ ניתן להגדיר סדר מלא חזק $\ <$ (באנגלית: Strict total order) באופן הבא: לכל $\ a$ ו-$\ b$ ב- $\ \left( A, \le \right)$ מתקיים $\ a < b$ אם ורק אם $\ a \le b$ וגם $\ a \ne b$. הגדרה נוספת ושקולה היא ש- $\ a < b$ אם ורק אם לא מתקיים $\ b \le a$. הסדר המתקבל דומה בתכונותיו לסדר הקודם ונבדל בכך שהוא טריכוטומי (כלומר לכל $\ a$ ו-$\ b$ ב- $\ \left( A, < \right)$ מתקיימת רק אחת מבין האפשרויות $\ a < b$, $\ b < a$ או $\ a=b$) ובפרט אי-רפלקסיבי.

פעולות בין סדרים

חיבור סדרים  : יהיו $( P,\le )$ $( Q,\le )$ סדרים אז נגדיר $\ Q + P$ באופן הבא : $\ P + Q = P \times \left\{0\right\}\cup Q \times \left\{1\right\}$

עם הסדר :

$x,y \in P , (x ,0) \le (y ,0) \iff x \le y$

, $a,b \in Q , (a ,1) \le (b ,1) \iff a \le b$

ולכל $a \in Q , x \in P$ מתקיים $x \le a$

כפל סדרים: יהיו $( P,\le )$ $( Q,\le )$ סדרים אז נגדיר $Q \times P$ עם הסדר המילוני הימני (העברי) כלומר :

$(x_1 , x_2 ) \le (y_1 , y_2)$ אם מתקיים :

$x_2 \le y_2$ או, $\ y_2 = x_2$ וגם $x_1 \le y_1$

הערות:

• אם $( P,\le )$ $( Q,\le )$ סדרים טובים אז $\ P + Q$ ו $P \times Q$ הם סדרים טובים

• מכיוון שפעולת החיבור ופעולת הכפל מוגדרות היטב ניתן גם לדבר על פילוג מימין : יהיו $( M,\le )$ $( P,\le )$ $( Q,\le )$ סדרים מלאים, אז מתקיים : $P \times (Q +M ) = P \times Q + P \times M$

• עבור סדרים סופיים פילוג משמאל מתקיים. אך עבור סדרים אינסופיים זה לא נכון.

ראו גם

• סדר טוב
• פונקציה שומרת סדר
• טיפוס סדר

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