טיפוס סדר

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

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

את טיפוס הסדר של קבוצה סדורה $(A,\leq )$ מסמנים ב-${\overline {(A,\leq )}}$, ולעיתים כ-$\operatorname {type} (A)$.

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

המושג נהגה ונחקר לראשונה על ידי גאורג קנטור.

הגדרה

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

שתי קבוצות הן בעלות אותו טיפוס סדר אם ורק אם הן איזומורפיות, כלומר קיימת פונקציה חד-חד-ערכית ועל שומרת סדר ביניהן (כלומר מתקיים $\ a\leq b\Leftrightarrow f(a)\leq f(b)$). זאת בדומה לעוצמה שבה שתי קבוצות הן בעלות אותה עוצמה אם ורק אם קיימת פונקציה חח"ע ועל ביניהן. אם לשתי קבוצות יש אותו טיפוס סדר, אז גם יש להן אותה עוצמה (כי הפונקציה של האיזומורפיזם היא בפרט חח"ע ועל) אך ההפך אינו נכון.

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

בדומה לעוצמות, גם במקרה של טיפוסי סדר ניתן להגדיר את היחס $\leq$ מעל קבוצה כלשהי של טיפוסי סדר, כקיום פונקציה שיכון: פונקציה שומרת סדר וחד-חד-ערכית (שאינה דווקא על). יחס זה הוא קדם סדר (כלומר הוא רפלקסיבי וטרנזיטיבי) אך בניגוד ליחס מעל העוצמות, הוא איננו אנטי-סימטרי ואיננו משווה. כך לדוגמה, ${\overline {((0,1),\leq )}}\leq {\overline {([0,1],\leq )}}$ וכן ${\overline {((0,1),\leq )}}\geq {\overline {([0,1],\leq )}}$, אך ${\overline {((0,1),\leq )}}\neq {\overline {([0,1],\leq )}}$. כמו כן, לא כל שתי קבוצות ניתנות להשוואה, למשל $(\mathbb {N} ,\leq )$ ו-$(\mathbb {N} ,\geq )$. אם מדברים על סודרים, אזי שתי התכונות מתקיימות.

דוגמאות

• לכל שתי קבוצות סופיות סדורות בעלות אותו מספר איברים יש אותו טיפוס סדר. זאת מכיוון שהפונקציה שמתאימה איבר ראשון לאיבר ראשון, שני לשני וכו' היא איזומורפיזם.
• לכל שני קטעים פתוחים באותו אורך עם יחס ההשוואה יש אותו טיפוס סדר, כיוון שהפונקציה $f(x)=x+a$ (כאשר $a$ הוא המרחק בין הקצוות הימניים של הקטעים) היא איזומורפיזם. גם לשני קטעים שהקצה השמאלי שלהם ב-$0$ יש אותו טיפוס סדר, כיוון שהפונקציה $f(x)=ax$ (כאשר $a$ הוא היחס בין גודלי הקטעים) היא איזומורפיזם. מכך נובע שלכל שני קטעים יש אותו טיפוס סדר (ניתן "להזיז" ל-$0$, לשנות לגודל הנכון ואז "להזיז" למקום הנכון) כמו כן, לכל קטע אותו טיפוס סדר כמו הישר הממשי כולו; זאת כיוון שהפונקציה $f(x)=\tan x$ (טנגנס) היא איזומורפיזם בין הקטע $\left(-{\frac {\pi }{2}},{\frac {\pi }{2}}\right)$ (שכבר הוכח שאיזומורפי לכל קטע אחר) לישר הממשי.

תכונות של קבוצות

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

ניתן לאפיין טיפוסי סדר באמצעות תכונות שלהם. כך לדוגמה:

• טיפוס הסדר של המספרים הטבעיים, המסומן באות $\omega$, הוא טיפוס סדר של כל קבוצה לא ריקה שאין בה איבר אחרון וכל תת-קבוצה חסומה מלעיל היא סופית.
• טיפוס הסדר של המספרים הרציונליים, המסומן באות $\mu$, הוא טיפוס הסדר של כל קבוצה לא ריקה ובת מנייה בלי איבר ראשון ואחרון המסודרת בסדר צפוף.
• טיפוס הסדר של המספרים הממשיים, המסומן באות $\rho$, הוא טיפוס הסדר של כל קבוצה המכילה קבוצה עם טיפוס הסדר μ בלי איבר ראשון ואחרון ולכל קבוצה לא-ריקה וחסומה מלעיל יש חסם עליון.

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

ניתן להגדיר פעולות בין טיפוסי סדר:

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

החיבור והכפל אסוציאטיביים אך אינם קומוטטיביים. חוק הפילוג מתקיים מימין בלבד (היינו $A\cdot (B+C)\cong A\cdot B+A\cdot C$), ובמקרה של קבוצות סדורות היטב (או בשקילות סודרים), מתקיימות מונוטוניות ורציפות מימין בלבד (היינו $f(B)=A+B$, $f(B)=AB$ פונקציות מונוטוניות ורציפות, ולא להפך).

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

• טיפוס סדר, באתר MathWorld (באנגלית)