שיכון סדר

[טקסט=תצוגה חזותית של שיכון סדר|ממוזער|359x359 פיקסלים|[דיאגרמת הסה|דיאגרמות הסה של שני סריגים סופיים, כך שהסריג השמאלי משוכן בתוך הסריג הימני.]]
במתמטיקה, ובפרט בתורת הסדר, **שיכון סדר** הוא פונקציה מקבוצה סדורה אחת לאחרת שמשמר את היחס של קבוצת התחום בקבוצת הטווח, ומנגד לא מוסיף יחסים מקבוצת הטווח שאינם בקבוצת התחום. באמצעות שיכון סדר ניתן לבחון האם קבוצה סדורה מסוימת מהווה הרחבה של קבוצה סדורה אחרת, וכך לסדר גם את מחלקת הקבוצות הסדורות.

## הגדרה
יהי זוג קבוצות סדורות (P,\le_P) ו-(Q,\le_Q) ופונקציה f\colon P\to Q. אזי, f תקרא **שיכון סדר מ-**P **ל-**Q אם ורק אם:

# f מונוטונית: לכל x,y\in P, אם x\le_P y אז f(x)\le_Q f(y).
# f מחזירת סדר: לכל x,y\in P, אם f(x)\le_Q f(y) אז x\le_P y.
אם קיים שיכון סדר כלשהו מ-P ל-Q אומרים ש-**<math>P</math> משוכנת סדר ב-<math>Q</math>** ומסמנים P\hookrightarrow Q.

## תכונות
* כל שיכון סדר הוא בהכרח פונקציה חד-חד ערכית.
* יהי שלוש קבוצות סדורות (P,\le_P), (Q,\le_Q) ו-(R,\le_R) ושני שיכוני סדר f\colon P\to Q ו-g\colon Q\to R, אזי ההרכבה g\circ f היא שיכון סדר מ-P ל-R.
* לכל קבוצה סדורה, פונקציית הזהות מהקבוצה לעצמה היא שיכון סדר.

## איזומורפיזם סדר

יהי זוג קבוצות סדורות (P,\le_P) ו-(Q,\le_Q) ופונקציה f\colon P\to Q שיכון סדר שהיא גם פונקציה על. אזי, f תקרא **[[איזומורפיזם סדר]] מ-<math>P</math> ל-<math>Q</math>**. באופן דומה, P ו-Q תקראנה **קבוצות סדורות איזומורפיות**.

איזומורפיזמים של סדר מקיימים את התכונות הבאות:
*בעבור שלוש קבוצות סדורות (P,\le_P), (Q,\le_Q) ו-(R,\le_R) ושני איזומורפיזמי-סדר f\colon P\to Q ו-g\colon Q\to R, גם ההרכבה g\circ f היא איזומורפיזם סדר מ-P ל-R.
*בעבור שתי קבוצות סדורות (P,\le_P) ו-(Q,\le_Q), ואיזומורפיזם סדר f\colon P\to Q, הפונקציה ההפוכה f^{-1} היא איזומורפיזם סדר מ-Q ל-P.
* לכל קבוצה סדורה, פונקציית הזהות מהקבוצה לעצמה היא איזומורפיזם סדר.
משלוש התכונות הללו ניתן להסיק שהיחס "איזומורפי-סדר ל-" הוא יחס שקילות על מחלקת הקבוצות הסדורות. עובדה זו מאפשר להגדיר את טיפוס הסדר של קבוצה סדורה.

## היחס "משוכן ב-" כקדם סדר על מחלקה
טקסט=תצוגה חזותית של הקשר בין איזומורפיזם סדר לשיכון סדר|ממוזער|תצוגה חזותית של הקשר בין איזומורפיזם סדר לשיכון סדר
ניתן להראות שאם נתונות ארבע קבוצות סדורות P_1, P_2, Q_1 ו-Q_2 כך ש-P_1 איזומורפית ל-Q_1, P_2 איזומורפית ל-Q_2 ו-P_1 משוכנת סדר בתוך P_2, אז גם Q_1 משוכנת סדר ב-Q_2. הדבר מוביל למחשבה להגדיר את היחס "משוכן סדר ב-" כיחס סדר חלקי על מחלקת מחלקות השקילות של יחס השקילות "איזומורפי סדר ל-". עם זאת, הדבר איננו אפשרי.

ניתן להראות שייתכנו שתי קבוצות סדורות עם שיכוני סדר מהאחת לשנייה ולהפך, אך ששתי הקבוצות לא תהיינה איזומורפיות סדר. לדוגמה, מגדירים P=[0,1] הקטע הסגור בין 0 ל-1, ו-Q=(0,1) הקטע הפתוח בין 0 ל-1. מגדירים f\colon P\to Q ו-g\colon Q\to P כך ש:

f(x):=\frac{x+1}{3},\qquad g(x):=\frac{x+1}{3}

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

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

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

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

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

### משפט דושניק-מילר
כאמור לעיל, לכל קבוצה סדורה, פונקציית הזהות היא שיכון סדר. נשאלת השאלה האם ניתן לבנות שיכון סדר מקבוצה סדורה לעצמה ששונה מפונקציית הזהות.

עבור חבורות סדורות התשובה חיובית. עבור חבורה סדורה משמאל G בוחרים איבר h\in G ששונה מאיבר היחידה. ההתאמה x\to hx היא שיכון סדר שאינו פונקציית הזהות. בצורה זו ניתן להוכיח כי קבוצת המספרים הטבעיים \N, המספרים השלמים \Z, המספרים הרציונליים \Q והמספרים הממשיים \R, לכולן יש שיכון סדר עצמי ששונה מפונקציית היחידה.

משפט דושניק-מילר  קובע כי לכל קבוצה בת-מנייה שסדורה בסדר מלא, קיים שיכון סדר ממנה לעצמה ששונה מפונקציית הזהות. במאמר של דושניק ומילר משנת 1940 הם מוכיחים שטענה זו אינה נכונה באופן כללי עבור קבוצות סדורות שאינן ממידה בת-מנייה. לשם בניית דוגמה נגדית, ניתן להשתמש באקסיומת הבחירה כדי לבנות קבוצה A\subset \R שעבורה לא ניתן לבנות שיכון סדר עצמי שאינו פונקציית היחידה.

## דוגמאות
* המספרים הטבעיים משוכני-סדר בתוך המספרים השלמים, המספרים השלמים משוכני-סדר בתוך המספרים הרציונליים והמספרים הרציונליים משוכני-סדר בתוך המספרים הממשיים.
* לכל מספר טבעי n\in\N מגדירים f(n):=\{d\in\N\mid d|n\}. אזי, f היא שיכון סדור מ-\N הסדורה ביחס "מחלק את" לבין קבוצת החזקה \mathcal{P}(\N) הסדורה ביחס ההכלה.
* ניתן לשכן-סדר את המספרים הממשיים בתוך קבוצת הפונקציות הרציפות המסודרות לפי השוואה איבר-איבר, על-ידי התאמת כל r\in\R אל הפונקציה הקבועה x\to r. התאמה זו היא שיכון סדר.
* עבור קבוצה סדורה A מגדירים את L להיות קבוצת כל התת-קבוצות התחתונות של A. לכל x\in A מגדירים f(x):=\downarrow\! x כאשר \downarrow\! x הוא אוסף כל האיברים ב-A הקטנים מ-x. אזי, f היא שיכון סדר מ-A ל-L, כאשר L סדורה ביחס ההכלה. שיכון זה הוא איזומורפיזם סדר אם ורק אם A היא סריג-למחצה עליון שלם.

## הערות שוליים

קטגוריה:תורת הסדר