Lexikografisk ordning

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif
icon_anmal.gif
rp-wp-sv.gif

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

Innehåll

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

(a1,...an) < (b1,...,bn) om och endast om aj < bj och ai = bi fr i < j [4]

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 x1 = y1 och för antagandet x_1 \ne y_1 .[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).[5]
  • 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

  1. ↑ 1,0 1,1 1,2 1,3 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. ↑ Källa saknas
  5. ↑ Ekenberg, L: "Logikens grunder", sidor 152 och 264. Natur och Kultur, 2001


E-to-the-i-pi.svg Denna matematik-relaterade artikel är bara påbörjad. Du kan hjälpa till genom att utöka den.
Hämtad från "https://sv.rilpedia.org/wiki/Lexikografisk_ordning"
Personliga verktyg