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 ${ℛ}_1$och ${ℛ}_2$både är totala ordningar.

Definition

• Antag att ${ℛ}_1$ respektive ${ℛ}_2$ är partiella ordningar på ${𝒮}_1$ respektive ${𝒮}_2$. Relationen $ℛ$ på produktmängden ${𝒮}_1$  ×  ${𝒮}_2$ definieras genom att låta $(x_1,x_2)ℛ(y_1,y_2)$ om och endast om

$\{\begin{array}{cc}{x}_1{ℛ}_1{y}_1,& \text{om }{x}_1\ne y_1\\ x_2{ℛ}_2{y}_2,& \text{om }{x}_1=y_1\end{array}$

Relationen $ℛ$ är den lexikografiska ordningen på produktmängden ${𝒮}_1$  ×  ${𝒮}_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)⟺a_j<b_j\text{ och }{a}_i=b_i\text{ för }\mathrm{\forall }i<j$ Mall:Källa behövs

Sats

Om ${ℛ}_1$ respektive ${ℛ}_2$ är partiella ordningar på ${𝒮}_1$ respektive ${𝒮}_2$ så är den lexikografiska ordningen en partiell ordning på produktmängden ${𝒮}_1$  ×  ${𝒮}_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\ne y_1$.

Exempel och tillämpningar

• Om mängderna ${𝒮}_1=\{1,2\}$ och ${𝒮}_2=\{1,2,3\}$ båda har relationen $\le$ ges den lexikografiska ordningen på produktmängden ${𝒮}_1\times {𝒮}_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.