Lexikografisk ordning

Lexikografisk ordningsföljd är ett sätt att ordna mängder inom matematiken. Ett exempel på en lexikografiskt ordnad mängd är alfabetiskt ordnade uppslagsord i ett uppslagsverk. Metoden att ordna mängder i lexikografisk ordning beskrevs matematiskt av Julius König och Richard Jules år 1905 oberoende av varandra . Den lexikografiskt ordnade mängden tas fram genom att definiera en relation på produktmängden av två partiellt ordnade mängder. Observera att konstruktionen nedan definierar en total ordning i de fall ${\mathcal {R}}_{1}$och ${\mathcal {R}}_{2}$både är totala ordningar.

Definition

• Antag att ${\mathcal {R}}_{1}$ respektive ${\mathcal {R}}_{2}$ är partiella ordningar på ${\mathcal {S}}_{1}$ respektive ${\mathcal {S}}_{2}$. Relationen ${\mathcal {R}}$ på produktmängden ${\mathcal {S}}_{1}$  ×  ${\mathcal {S}}_{2}$ definieras genom att låta $(x_{1},\,x_{2}){\mathcal {R}}(y_{1},\,y_{2})$ om och endast om

$\left\{{\begin{matrix}x_{1}{\mathcal {R}}_{1}y_{1},&{\mbox{om }}x_{1}\neq y_{1}\\x_{2}{\mathcal {R}}_{2}y_{2},&{\mbox{om }}x_{1}=y_{1}\end{matrix}}\right.$

Relationen ${\mathcal {R}}$ är den lexikografiska ordningen på produktmängden ${\mathcal {S}}_{1}$  ×  ${\mathcal {S}}_{2}$.

• Den lexikografiska ordningen kan också uttryckas som en naturlig ordning av Cartesiska produkten av ett antal ordnade mängder, definierad genom att jämföra termerna i ordning, dvs:

$(a_{1},...a_{n})<(b_{1},...,b_{n})\iff a_{j}<b_{j}{\mbox{ och }}a_{i}=b_{i}{\mbox{ för }}\forall i<j$ ^{[källa behövs]}

Sats

Om ${\mathcal {R}}_{1}$ respektive ${\mathcal {R}}_{2}$ är partiella ordningar på ${\mathcal {S}}_{1}$ respektive ${\mathcal {S}}_{2}$ så är den lexikografiska ordningen en partiell ordning på produktmängden ${\mathcal {S}}_{1}$  ×  ${\mathcal {S}}_{2}$.

Bevisgång

Att den lexikografiska ordningen är partiellt ordnad visas genom att de tre kriterierna för partiellt ordnade mängder (reflexivitet, antisymmetri och transitivitet) uppfylls både för antagandet $x_{1}=y_{1}$ och för antagandet $x_{1}\neq y_{1}$.

Exempel och tillämpningar

• Om mängderna ${\mathcal {S}}_{1}=\left\{1,2\right\}$ och ${\mathcal {S}}_{2}=\left\{1,2,3\right\}$ båda har relationen $\leq$ ges den lexikografiska ordningen på produktmängden ${\mathcal {S}}_{1}\times {\mathcal {S}}_{2}$enligt (1,1), (1,2), (1,3), (2,1), (2,2), (2,3).
• I ett uppslagsverk används bokstävernas ordning i alfabetet för att bestämma ordningen mellan uppslagsorden, t.ex. kommer ab före ac, vilket är en lexikografisk ordning.