Lexikografisk ordning

Från Wikipedia
Hoppa till navigering Hoppa till 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. Observera att konstruktionen nedan definierar en total ordning i de fall och både är totala ordningar.

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]

Sats[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.