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 respektive är partiella ordningar på respektive . Relationen på produktmängden  ×  definieras genom att låta om och endast om

Relationen är den lexikografiska ordningen på produktmängden  ×  . [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:

[källa behövs]

Teorem[redigera | redigera wikitext]

Om respektive är partiella ordningar på respektive så är den lexikografiska ordningen en partiell ordning på produktmängden  ×  .

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 och för antagandet .[1]

Exempel och tillämpningar[redigera | redigera wikitext]

  • Om mängderna och båda har relationen ges den lexikografiska ordningen på produktmängden  ×  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.