הצגת המקור של הדף "יחס סדר מילוני"

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

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

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

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

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

הסימון הפורמלי מתחיל ב[[קבוצה סופית]] {{נוסחה|''A''}}, הנקראת לרוב [[אלפבית (שפה פורמלית)|האלפבית]], שהיא [[סדר מלא|מסודרת מלא]]. כלומר, עבור כל שתי אותיות {{נוסחה|''a''}} ו- {{נוסחה|''b''}} ב- {{נוסחה|''A''}} שאינם אותה אות, או {{נוסחה|''a'' < ''b''}} או {{נוסחה|''b'' < ''a''}} .

''המילים'' של {{נוסחה|''A''}} הן הרצפים הסופיים של אותיות מ- {{נוסחה|''A''}}, כולל מילים באורך 1 המכילות אות בודדת, מילים באורך 2 עם שתי אותיות וכן הלאה, כולל הרצף הריק, <math>\varepsilon</math>, ללא סמלים כלל. הסדר המילוני בקבוצה של כל המילים הסופיות הללו מסדר את המילים באופן הבא:

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

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

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

תכונה חשובה של הסדר המילוני הוא שלכל {{נוסחה|''n''}}, קבוצת המילים באורך {{נוסחה|''n''}} [[סדר טוב|סדורה היטב]] לפי הסדר המילוני (בתנאי שהאלפבית סופי); כלומר, כל רצף יורד (ביחס הסדר המילוני) של מילים באורך {{נוסחה|''n''}} הוא סופי (או באופן שקול, לכל תת-קבוצה לא ריקה יש אלמנט מינימלי - קטן ביותר).<ref name="Harzheim">{{Cite book|last=Egbert Harzheim|title=Ordered Sets|publisher=Springer|year=2006|isbn=978-0-387-24222-4|pages=88–89}}</ref><ref name="BaaderNipkow1999">{{Cite book|last=Franz Baader|title=Term Rewriting and All That|last2=Tobias Nipkow|publisher=Cambridge University Press|year=1999|isbn=978-0-521-77920-3|pages=18–19}}</ref> אך, תכונה זו אינה נשמרת כאשר מדברים על הקבוצה של ''כל'' המילים הסופיות. היא אינה סדורה היטב; לדוגמה, לקבוצת המילים האינסופית {ב, בא, באא, באאא, ... } אין אלמנט קטן ביותר מבחינה מילונית. (כי הוא אמור להיות אאאא... עד אינסוף, ואין באפשרותינו להשתמש במילים אינסופיות).

== מכפלות קרטזיות ==
הסדר המילוני מגדיר סדר על [[מכפלה קרטזית]] של קבוצות סדורות, שהוא סדר מלא כאשר כל הקבוצות במכפלה הקרטזית הן סדורות באופן מלא בעצמן. איבר של מכפלה קרטזית <math>E_1 \times \cdots \times E_n</math> הוא רצף שהאיבר ה- <math>i</math> שלו שייך ל <math>E_i</math> לכל <math>i.</math> מכיוון שבמקרה זה, אנו משווים רצפים באורך n, כולם מאותו אורך, לכן הסדר המילוני ניתן להכללה למכפלה קרטזית של קבוצות סדורות. ניתן להכליל זאת למכפלה אינסופית של קבוצות סדורות באופן דומה.

באופן ספציפי, בהינתן שתי [[סדר חלקי|קבוצות סדורות חלקית]] <math>A</math> ו <math>B,</math> ה <math>A \times B</math> זה מוגדר כ:

(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),

התוצאה היא סדר חלקי. אם <math>A</math> ו <math>B</math> כל אחת [[סדר מלא|סדורה באופן מלא]], אז התוצאה היא גם סדר מלא. הסדר המילוני של שתי קבוצות סדורות באופן מלא הוא בעצם [[הרחבה ליניארית]] של [[הזמנת מוצר|סדר המכפלה]] שלהם.

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

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:מילונאות]]