סדר מלא

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

דוגמאות:

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

המספרים הרציונליים והמספרים הממשיים הם קבוצות סדורות ליניארית צפופות.

סדרים מלאים אינסופיים

יחס סדר חלקי (חלש או חזק) ${\mathcal {R}}$ נקרא יחס סדר מלא (או "יחס סדר שלם", או "יחס סדר ליניארי") אם לכל $a\neq b$ מתקיים $a{\mathcal {R}}b$ או $b{\mathcal {R}}a$.

קבוצה סופית אפשר לסדר ליניארית באופן אחד ויחיד. בקבוצות אינסופיות מיון הסדרים הליניאריים הוא הרבה יותר מסובך. את הקבוצה $X$ עם הסדר המנוגד מסמנים ב-$X^{*}$. כל קבוצה סדורה אינסופית מכילה עותק של $\omega$ או של $\omega ^{*}$.

אוסף T של קבוצות סדורות ליניארית בעוצמה a הוא בסיס לכל הסדרים מעוצמה זו, אם אפשר לשכן בכל קבוצה סדורה מעוצמה a קבוצה סדורה מ-T. לקבוצות הסדורות שהן בנות מניה יש אם כך בסיס בגודל 2. בדומה לזה, עקבי שיש בסיס של חמישה סדרים לכל הסדרים מעוצמה $\aleph _{1}$; ולעומת זאת, בהנחת השערת הרצף, העוצמה של בסיס של הקבוצות הסדורות מעוצמת הרצף ${\mathfrak {c}}$ היא לפחות $2^{\mathfrak {c}}$.

שתי קבוצות סדורות ליניארית A,B מאותה עוצמה הן רחוקות אם אי אפשר לשכן בשתיהן סדר ליניארי כלשהו מאותה עוצמה; ורחוקות מונוטונית אם A ו-*A רחוקות גם מ-B וגם מ-*B.

סדר ליניארי על קבוצה A משרה טופולוגיה, שהקטעים הפתוחים הם בסיס שלה. קבוצה היא צפופה בטופולוגיית הסדר אם ורק אם היא צפופה בסדר עצמו. הטופולוגיה מציעה שני אינווריאנטים חשובים של הסדר: המשקל w(A), שהוא העוצמה של בסיס מינימלי; והצפיפות d(A) שהיא הגודל המינימלי של קבוצה צפופה. תמיד מתקיים $d(A)\leq w(A)$.

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

חיבור סדרים: החיבור של סדרים $(P,\leq ),(Q,\leq )$ מוגדר לפי "$P$ ואז $Q$", כלומר הקבוצה $P+Q=P\times \{0\}\cup Q\times \{1\}$ עם הסדר

${\begin{aligned}x,y\in P,(x,0)\leq (y,0)\iff x\leq y\\a,b\in Q,(a,1)\leq (b,1)\iff a\leq b\end{aligned}}$

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

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

$(x_{1},x_{2})\leq (y_{1},y_{2})$ אם מתקיים:

$x_{2}\leq y_{2}$ או $y_{2}=x_{2}$ וגם $x_{1}\leq y_{1}$

הערות:

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

ראו גם

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

קישורים חיצוניים

• גדי אלכסנדרוביץ', תורת הקבוצות - יחסי סדר, באתר "לא מדויק", 10 בינואר 2020
• סדר מלא, באתר MathWorld (באנגלית)

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.