Porządek leksykograficzny

Porządek leksykograficzny – porządek w zbiorze ciągów ${\displaystyle X^{*}}$ pewnego zbioru ${\displaystyle X}$ indukowany przez porządek ${\displaystyle \preccurlyeq }$ w zbiorze ${\displaystyle X.}$

${\displaystyle X}$ może być zbiorem liczb całkowitych, zbiorem symboli pewnego alfabetu, lub jakimkolwiek innym zbiorem, którego elementy potrafimy porównywać.

Definicja

Relację leksykograficzną ${\displaystyle \preccurlyeq }$ między ciągami ${\displaystyle \alpha ,\beta \in X^{*}}$ ustala się następująco:

• jeśli istnieje wskaźnik ${\displaystyle j}$ taki, że ${\displaystyle \alpha (j)\neq \beta (j),}$ to znajdujemy najmniejszy ${\displaystyle i}$ o tej własności^[a]. Wówczas
  • ${\displaystyle \alpha \preccurlyeq \beta }$ gdy ${\displaystyle \alpha (i)\preccurlyeq \beta (i)}$ lub ${\displaystyle \beta \preccurlyeq \alpha }$ gdy ${\displaystyle \beta (i)\preccurlyeq \alpha (i)}$ (tzn. relacja między ciągami jest zgodna z relacją między odpowiednimi elementami)
• jeśli taki ${\displaystyle j}$ nie istnieje, to
  • jeśli oba są skończone i tej samej długości, to ${\displaystyle \alpha =\beta }$
  • jeśli oba ciągi są nieskończone, to ${\displaystyle \alpha =\beta }$
  • jeśli są różnej długość np. ${\displaystyle \beta }$ jest dłuższy od ${\displaystyle \alpha }$ (w szczególności ${\displaystyle \beta }$ może być nieskończony), to ${\displaystyle \alpha \ \preccurlyeq \ \beta }$

Przykłady

• zakładając naturalny porządek na liczbach, ciąg (1, 0, 0, 0) jest leksykograficznie większy (późniejszy) od ciągu (0, 10, 100, 1000) – na pierwszej różniącej się pozycji liczba w pierwszym ciągu (1) jest większa niż w drugim (0).
• zakładając porządek alfabetyczny, słowo „krowa” jest większe od słowa „kot” – na pierwszej różniącej się pozycji „r” jest większe od „o”.

Nazwa porządku leksykograficznego pochodzi od sposobu w jaki słowa są uporządkowane w słowniku, najpierw według pierwszej litery, następnie według drugiej, i tak dalej.

W teorii ekonomii porządek leksykograficzny ma znaczenie głównie jako prosty przykład preferencji, których nie można przedstawić przy pomocy ciągłej funkcji użyteczności.

Uwagi

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Lexicographic Order, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).