יחס סדר מילוני

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

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

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

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

מוטיבציה והגדרה

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

הסימון הפורמלי מתחיל בקבוצה סופית $A$ , הנקראת לרוב האלפבית, שהיא מסודרת מלא. כלומר, עבור כל שתי אותיות $a$ ו- $b$ ב- $A$ שאינם אותה אות, או $a < b$ או $b < a$ .

המילים של $A$ הן הרצפים הסופיים של אותיות מ- $A$ , כולל מילים באורך 1 המכילות אות בודדת, מילים באורך 2 עם שתי אותיות וכן הלאה, כולל הרצף הריק, $\varepsilon$ , ללא סמלים כלל. הסדר המילוני בקבוצה של כל המילים הסופיות הללו מסדר את המילים באופן הבא:

בהינתן שתי מילים שונות באורך זהה, נניח $a = a 1 a 2 ... a k$ ו- $b = b 1 b 2 ... b k$ , סדר שתי המילים תלוי בסדר האלפביתי של האותיות במקום הראשון $i$ שבו שתי המילים משתנות (בספירה מתחילת המילים): $a < b$ אם ורק אם $a i < b i$ בסדר הבסיסי של האלפבית $A$ .
אם שתי מילים בעלות אורכים שונים, הסדר הלקסיקוגרפי הרגיל "ממלא" את הקצרה עם "רווח" (סמל מיוחד שמתייחסים אליו כקטן מכל רכיב של $A$ ) בסוף עד שהמילים באורך זהה, ואז המילים הן בהשוואה למקרה הקודם. מבחינה אינטואיטיבית, משווים את שתי המילים כל עוד אפשר, ואם לא קיבלנו הכרעה, האות הארוכה יותר גדולה מהקצרה ביחס.

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

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

תכונה חשובה של הסדר המילוני הוא שלכל $n$ , קבוצת המילים באורך $n$ סדורה היטב לפי הסדר המילוני (בתנאי שהאלפבית סופי); כלומר, כל רצף יורד (ביחס הסדר המילוני) של מילים באורך $n$ הוא סופי (או באופן שקול, לכל תת-קבוצה לא ריקה יש אלמנט מינימלי - קטן ביותר).^[1]^[2] אך, תכונה זו אינה נשמרת כאשר מדברים על הקבוצה של כל המילים הסופיות. היא אינה סדורה היטב; לדוגמה, לקבוצת המילים האינסופית {ב, בא, באא, באאא, ... } אין אלמנט קטן ביותר מבחינה מילונית. (כי הוא אמור להיות אאאא... עד אינסוף, ואין באפשרותינו להשתמש במילים אינסופיות).

מכפלות קרטזיות

הסדר המילוני מגדיר סדר על מכפלה קרטזית של קבוצות סדורות, שהוא סדר מלא כאשר כל הקבוצות במכפלה הקרטזית הן סדורות באופן מלא בעצמן. איבר של מכפלה קרטזית $E_{1}\times \cdots \times E_{n}$ הוא רצף שהאיבר ה- $i$ שלו שייך ל $E_{i}$ לכל $i.$ מכיוון שבמקרה זה, אנו משווים רצפים באורך n, כולם מאותו אורך, לכן הסדר המילוני ניתן להכללה למכפלה קרטזית של קבוצות סדורות. ניתן להכליל זאת למכפלה אינסופית של קבוצות סדורות באופן דומה.

באופן ספציפי, בהינתן שתי קבוצות סדורות חלקית $A$ ו $B,$ ה $A\times B$ זה מוגדר כ:

(a, b) \leq \left(a^{\prime}, b^{\prime}\right) \text{ if and only if } a < a^{\prime} \text{ or } \left(a = a^{\prime} \text{ and } b \leq b^{\prime}\right),

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

בניגוד למקרה הסופי, מכפלה אינסופית של קבוצות סדורות היטב לא בהכרח סדורה היטב לפי הסדר המילוני. לדוגמה, קבוצת הרצפים הבינאריים האינסופיים בני המנייה (בהגדרה, קבוצת הפונקציות ממספרים שלמים אי-שליליים לקבוצה $\{0,1\}$ הידוע גם בתור מרחב קנטור $\{0,1\}^{\omega }$ , אינו מסודר היטב; תת-קבוצת הסדרות שבהן מופיעה בדיוק פעם אחת הספרה 1 (כלומר, {1000...,0100...,0010..., ... }) אין אלמנט מינימלי תחת הסדר המילוני המושרה על ידי $0<1$ , כי $100000... > 010000... > 001000... > ...$ היא שרשרת יורדת אינסופית .^[1] באופן דומה, גם המכפלה האינסופית עם יחס הסדר הנ"ל אינה נתרית, כי: $011111... < 101111... < 110111 ... < ...$ היא שרשרת עולה אינסופית.

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

יחס סדר מילוני, באתר MathWorld (באנגלית) המזהה לא מולא ולא נמצא בוויקינתונים, נא למלא את הפרמטר.

הערות שוליים

^ ^1.0 ^1.1 Egbert Harzheim (2006). Ordered Sets. Springer. pp. 88–89. ISBN 978-0-387-24222-4.
^ Franz Baader; Tobias Nipkow (1999). Term Rewriting and All That. Cambridge University Press. pp. 18–19. ISBN 978-0-521-77920-3.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

34794357יחס סדר מילוני

[Harzheim-1] 1.0 ^1.1 Egbert Harzheim (2006). Ordered Sets. Springer. pp. 88–89. ISBN 978-0-387-24222-4.

[BaaderNipkow1999-2] Franz Baader; Tobias Nipkow (1999). Term Rewriting and All That. Cambridge University Press. pp. 18–19. ISBN 978-0-521-77920-3.

[1]

[2]

יחס סדר מילוני

תוכן עניינים

מוטיבציה והגדרה

מכפלות קרטזיות

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

הערות שוליים

תפריט ניווט

יחס סדר מילוני

מוטיבציה והגדרה

מכפלות קרטזיות

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

הערות שוליים

תפריט ניווט

חיפוש