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.

DefinitionRedigera

  • 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]

SatsRedigera

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

BevisgångRedigera

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ämpningarRedigera

  • 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ällorRedigera

  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
  Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.