Lexikografisk ordning

Från Wikipedia
Hoppa till: navigering, sök

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 relationproduktmängden av två partiellt ordnade mängder.

Definition[redigera | redigera wikitext]

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

 (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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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 .[1]

Exempel och tillämpningar[redigera | redigera wikitext]

  • 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).[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[redigera | redigera wikitext]

  1. ^ [a b c d] Ekenberg, L: "Logikens grunder", sidor 150-151. Natur och Kultur, 2001
  2. ^ Quine, W.: "Set theory and it's logic", sidor 208-211. Belknap press, 1963
  3. ^ van Heijenoort, J.: "From Frege to Gödel", sidor 142-149. Harvard University Press, 1967
  4. ^ Ekenberg, L: "Logikens grunder", sidor 152 och 264. Natur och Kultur, 2001
Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.