Lexikográfiai rend
A matematikában a lexikográfiai sorrend olyan rend , amelyet egy rendezett halmaz (vagy ezzel egyenértékű módon a rendezett halmazra épített szavak) véges szekvenciáin határozunk meg. Meghatározása a szótár sorrendjének általánosítása: a rendezett halmaz az ábécé, a szavak valóban az ábécé betűinek véges sorozata. A lexikográfiai rend legfőbb tulajdonsága, hogy a kezdeti rend egészét megtartsa. Hasonló módon definiálhatunk egy lexikográfiai sorrendet rendezett halmazok derékszögű termékein, amelyek elemei tehát többszörösek, vagyis ha akarják, rögzített hosszúságú véges szekvenciák.
Lexikográfiai sorrend egy derékszögű terméken
Noha a szótárrendelést már az általános iskolától kezdjük, a formalizálást egy egyszerű esettel kezdjük, a derékszögű bináris szorzattal. Vagyis szótárunk szavai kezdetben csak két betűből fognak állni.
Az ( A , ≤) és ( B , ≤) halmazok sorrendben vannak, a sorrendet mindkét halmazra azonos módon jegyezzük fel, ez a szabadság nem zavarhat senkit. Az A × B lexikográfiai sorrendjét , amelyet ismét ≤ -vel jelölünk, a következőképpen határozzuk meg ( a , b ) és ( a ' , b' ) két A × B pár esetén :
( a , b ) ≤ ( a ' , b' ) csak akkor, ha [ a < a ' vagy ( a = a' és b ≤ b ' )]és könnyen levezethetjük a szigorú lexikográfiai sorrend analóg tulajdonságát:
( a , b ) <( a ' , b' ) csak akkor, ha [ a < a ' vagy ( a = a' és b < b ' )].Ez valóban a szótár sorrendje, például:
lu <ne, mert l <n (csak az első betűt nézzük) a <lu, mert e <u (az első betűk azonosak, a másodikat nézzük).Az összehasonlítás megkezdéséhez az első komponens megválasztása teljesen önkényes, de amint azt az előző betűrendes példa szemlélteti, ha az összehasonlítást a második komponenssel kezdjük, akkor más sorrendet kapunk.
Példák
- A (z) {0, 1} × {0, 1} lexikográfiai sorrendje általában rendezett (0, 0) <(0, 1) <(1, 0) <(1, 1).
- Általánosságban elmondható, hogy a (z) {0, 1,…, n - 1} × {0, 1,…, p - 1} lexikográfiai sorrendje a szokásos sorrendben izomorf sorrend, szigorúan kisebb, mint np .
- Ha ( A , ≤) rendezett halmaza, a lexikografikus sorrendben a {0,1} × A összege „üzembe a végéig” két példányban A (az első összeköttetésben van az első komponens 0, a második az első komponens 1). Tehát, ha N a természetes számok halmaza, általában rendezve - akkor ω-nak hívják - a {0,1} × N lexikografikusan rendezett jó sorrend, amely nem izomorf az ω-val, hanem az ω + ω = ω2 sorszámmal . Lesz nekünk :
- A lexikográfia szerint rendezett N × {0,1} jó rendű izomorf 2ω = ω-ra, az N szokásos rendje .
- A lexikográfia szerint rendezett N × N az ω 2 sorszámra jó izomorf .
Tulajdonságok
- Ha az összes kezdeti sorrend-reláció ( A-n és B-n ) teljes sorrend , akkor az A × B-n lévő lexikográfiai sorrend-reláció teljes sorrend.
- Ha ráadásul minden kezdeti sorrend-reláció jó rend , akkor az A × B-n lévő lexikográfiai sorrend-reláció is jó sorrend.
Általánosítás véges derékszögű termékekre
Ha úgy vesszük, hogy az A 1 ×… × A k véges derékszögű szorzatot a bináris derékszögű szorzat segítségével határozzuk meg:
A 1 × A 2 ×… × A k = A 1 × ( A 2 × (… × A k )…)(vagy ha másként definiáltuk, hogy e két halmaz között kanonikus bijekció van), akkor természetesen a lexikográfiai rendet általánosítjuk indukcióval a rendezett halmazok véges szorzataira.
Tegyük fel, hogy meghatároztuk a k rendezett halmazok derékszögű termékeinek lexikográfiai sorrendjét . Ezután a k +1 rendezett halmazok szorzatának lexikográfiai sorrendjének meghatározásához hagyjuk, hogy A 1 , A 2 ,…, A k × A k + 1 , lexikografikusan rendezzük az A 1 bináris derékszögű szorzatát és a k derékszögű szorzatát. beállítja az A 2 ×… × A k × A k + 1 értéket , maga az utóbbi lexikográfiai sorrendben. Azaz, a lexikografikus sorrendben a termék megrendelt készletek A 1 × A 2 × ... × A k + 1 az így meghatározott a iexikografikus sorrendben a A 2 × ... × A k + 1 (definiáljuk a szigorú sorrendben, amely jelöli <az összes lejátszott szett esetében):
( a 1 ,…, a k + 1 ) <( b 1 ,…, b k + 1 ) csak akkor, ha: a 1 < b 1 vagy [ a 1 = b 1 és ( a 2 ,…, a k + 1 ) <( b 2 ,…, b k + 1 )]A derékszögű termék „végével kezdve” lebontásával ugyanazt a sorrendet kapjuk, vagyis ugyanazok a jelölések megtartásával rendelkezünk:
( a 1 ,…, a k + 1 ) <( b 1 ,…, b k + 1 ) csak akkor, ha: ( a 1 ,…, a k ) <( b 1 ,…, b k ) vagy [( a 1 ,…, a k ) = ( b 1 ,…, b k ) és a k + 1 < b k + 1 ].A lexikográfiai sorrend indukcióval történő „kibővítésével” az A 1 × A 2 ×… × A k kimeneten , e halmazok rendezésével, megkapjuk:
( a 1 ,…, a k ) <( b 1 ,…, b k ) akkor és csak akkor a 1 < b 1 vagy ( a 1 = b 1 és a 2 < b 2 ) vagy ( a 1 = b 1 és a 2 = b 2 és a 3 < b 3 ) vagy …… vagy ( a 1 = b 1 és egy 2 = b 2 , és ... és egy K-1 = b k-1 , és a k < b k )Példák
Ha lexikografikusan N × N × N sorrendet rendelünk, mindegyiket általában rendezve, akkor egy jó megszámlálható sorrendet kapunk, amely megfelel az ω 3 sorszámnak , amely nem egyenlő sem ω-val, sem pedig ω 2-vel .
Tulajdonságok
A bináris derékszögű termékekre megadott tulajdonságok indukcióval azonnal általánosítanak: a teljesen rendezett halmazok véges derékszögű szorzatán meghatározott lexikográfiai sorrend teljes sorrend, a jól rendezett halmazok véges derékszögű szorzatán meghatározott lexikográfiai sorrend jó.
Lexikográfiai sorrend véges szekvenciákon
Ez az, amelyik a szótárak sorrendjét használja. A korábbi esetekkel ellentétben szeretnénk tetszőleges hosszúságú véges szekvenciákat összehasonlítani. Például a szótárban a "ház" az "anya" előtt áll, mert a "my" = "my" és "i" <"m". A „háznak” azonban 6 betűje van, az „anyjának” pedig 5. Ezek a szavak nem tekinthetők ugyanannak a kész derékszögű terméknek az elemei, kivéve, ha az ábécébe betű kerül, amellyel önkényesen kiegészítjük a leggyakoribb szót. Ez nem teljesen elképzelhetetlen a szótár számára, mivel egy nyelv szavainak a gyakorlatban maximális hossza van (legalábbis azok, amelyek a szótárban szerepelnek ...), de nagyon mesterségesek lennének. Ezért természetes, hogy a lexikográfiai rendet tetszőleges hosszúságú véges szekvenciákon határozzuk meg.
Legyen ( E , ≤) tehát rendezett halmaz. Beállítottuk az E * = értéket , az E-re épített összes véges derékszögű termék egyesülését ( E 0 csak az üres szekvenciát tartalmazza). Az E * lexikográfiai sorrendjét a következőképpen definiáljuk . Legyen a = ( a 1 ,…, a p ) és b = ( b 1 ,…, b q ) az E * bármely két eleme , és m legyen a legkisebb a p és q egész szám közül . Akkor a < b akkor és csak akkor, ha:
( a 1 ,…, a m ) <( b 1 ,…, b m ) (az E m-es lexikográfiai sorrendhez ) vagy ( a 1 ,…, a m ) = ( b 1 ,…, b m ) és m < q (azaz p < q ).
Tulajdonságok
Könnyen látható, hogy, ha a kezdeti megbízást E jelentése teljes, a lexikografikus sorrendben a E *, a készlet véges szekvenciák elemeinek E , szintén teljes.
Másrészt, az ingatlan jó érdekében nem maradt fenn (kivéve persze, ha E egy szingli ). Például a {0, 1} rendezése rendben van, de a {0, 1} * nem, amint azt a csökkenő végtelen szekvencia mutatja:
(1)> (0, 1)> (0, 0, 1)> (0, 0, 0, 1)>…Ezért más módszereket is meg kell fontolnunk a jól rendezett halmaz véges szekvenciáinak megfelelő rendezéséhez, például a szekvenciák hosszának összehasonlításához.
Definíció a szekvenciák hosszának figyelembevételével
Baader és Nipkow a következőképpen határozza meg a lexikográfiai rendet. Ha (E,>) egy szigorú sorrendben, majd a lexikografikus sorrendben> * lex az E * határozza meg:
u> * lex v akkor és csak akkor, ha (| u |> | v | vagy (| u | = | v | és u> | u | lex v)
ahol | w | a w szó hossza, és> | u | lex az E | u | -on található lexikográfiai sorrend .
Ha a> szigorú sorrend, akkor a> * lex is szigorú sorrend. Ha> véget ér, akkor a * * lex véget ér.
Megjegyzések és hivatkozások
- Franz Baader és Tobias Nipkow, a terminus átírása és minden , Cambridge University Press ,1999, 18–19 p. ( ISBN 978-0-521-77920-3 , online olvasás )
Lásd is
- További általános meghatározása Iexikografikus érdekében , a termék egy család rendezett halmazok indexelt egy jól rendezett halmaz
- Ábécésorrend