טיפוס סדר

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

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

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

את טיפוס הסדר של קבוצה סדורה (A, \le) מסמנים ב-\overline {(A, \le)}

טיפוס סדר של קבוצה סדורה היטב נקרא סודר.

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

הגדרה[עריכת קוד מקור | עריכה]

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

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

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

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

דוגמאות[עריכת קוד מקור | עריכה]

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

תכונות של קבוצות[עריכת קוד מקור | עריכה]

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

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

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

פעולות בין טיפוסי סדר[עריכת קוד מקור | עריכה]

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

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

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

הערות שוליים[עריכת קוד מקור | עריכה]

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