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. ^[1] Metoden att ordna mängder i lexikografisk ordning beskrevs matematiskt av Julius König och Richard Jules år 1905 ^[2] oberoende av varandra ^[3]. 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 ${\displaystyle {\mathcal {R}}_{1}}$och ${\displaystyle {\mathcal {R}}_{2}}$både är totala ordningar.

Definition

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

${\displaystyle \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 ${\displaystyle {\mathcal {R}}}$ är den lexikografiska ordningen på produktmängden ${\displaystyle {\mathcal {S}}_{1}}$  ×  ${\displaystyle {\mathcal {S}}_{2}}$. ^[1]

• 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:

${\displaystyle (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 ${\displaystyle {\mathcal {R}}_{1}}$ respektive ${\displaystyle {\mathcal {R}}_{2}}$ är partiella ordningar på ${\displaystyle {\mathcal {S}}_{1}}$ respektive ${\displaystyle {\mathcal {S}}_{2}}$ så är den lexikografiska ordningen en partiell ordning på produktmängden ${\displaystyle {\mathcal {S}}_{1}}$  ×  ${\displaystyle {\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 ${\displaystyle x_{1}=y_{1}}$ och för antagandet ${\displaystyle x_{1}\neq y_{1}}$.^[1]

Exempel och tillämpningar

• Om mängderna ${\displaystyle {\mathcal {S}}_{1}=\left\{1,2\right\}}$ och ${\displaystyle {\mathcal {S}}_{2}=\left\{1,2,3\right\}}$ båda har relationen ${\displaystyle \leq }$ ges den lexikografiska ordningen på produktmängden ${\displaystyle {\mathcal {S}}_{1}\times {\mathcal {S}}_{2}}$enligt (1,1), (1,2), (1,3), (2,1), (2,2), (2,3).^[4]
• 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.^[1]

Källor