Porządek leksykograficzny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Porządek leksykograficzny – porządek w zbiorze ciągów pewnego zbioru indukowany przez porządek w zbiorze .

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

Definicja[edytuj]

Relację leksykograficzną między ciągami ustala się następująco:

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

Przykłady[edytuj]

  • 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

  1. istnieje taki na mocy zasady minimum

Linki zewnętrzne[edytuj]