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.

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 \ne 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) \mbox{ om och endast om } a_j<b_j \mbox{ och } a_i=b_i \mbox{ för } i<j$ ^{[källa behövs]}

Teorem

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 \ne 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 $\le$ ges den lexikografiska ordningen på produktmängden $\mathcal{S}_1$  ×  $\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.