Sözlük düzeni
Gelen matematik bir lexicographic düzeni bir bir sipariş biz tanımlayan sonlu dizilerinin bir elemanlarının sıralı bir setin (eşdeğer bir şekilde ya da, kelime sıralı bir dizi üzerine inşa). Tanımı, sözlüğün sırasının bir genellemesidir: sıralı küme alfabedir, kelimeler aslında alfabenin harflerinin sonlu dizileridir. Sözlük düzeninin temel özelliği, ilk sıranın tamamını korumaktır. Benzer bir şekilde, elemanları dizilimlerden oluşan sıralı kümelerin Kartezyen çarpımları üzerinde, yani dilerseniz, sabit uzunlukta sonlu diziler olan bir sözlük düzenini tanımlayabiliriz.
Kartezyen bir üründe sözlük düzeni
Sözlük sıralaması ilkokuldan itibaren yapılsa da, resmileştirmeye Kartezyen ikili çarpım gibi basit bir durumla başlayacağız. Yani sözlüğümüzün kelimeleri başlangıçta sadece iki harften oluşacaktır.
( A , ≤) ve ( B , ≤) kümelerinin her ikisi de sıralıdır, sıra her iki takım için de aynı şekilde not edilir, kimseyi rahatsız etmemesi gereken bir özgürlük. Yine ≤ ile ifade ettiğimiz A × B üzerindeki sözlük sıralaması, ( a , b ) ve ( a ' , b' ) A × B'nin iki çifti için şu şekilde tanımlanır :
( a , b ) ≤ ( a ' , b' ) ancak ve ancak [ a < a ' veya ( a = a' ve b ≤ b ' )]ve katı sözlüksel düzen için benzer özelliği kolayca çıkarırız:
( a , b ) <( a ' , b' ) ancak ve ancak [ a < a ' veya ( a = a' ve b < b ' )].Bu aslında sözlüğün sırasıdır, örneğin:
lu <ne çünkü l <n (sadece ilk harfe bakarız) <lu çünkü e <u (ilk harfler aynı, ikinciye bakıyoruz).Karşılaştırmayı başlatmak için birinci bileşenin seçimi tamamen keyfidir, ancak önceki alfabetik örnekte gösterildiği gibi, karşılaştırma ikinci bileşenle başlatılırsa farklı bir sıra elde edilir.
Örnekler
- {0, 1} × {0, 1} üzerindeki sözlük düzeni genellikle sıralı olarak (0, 0) <(0, 1) <(1, 0) <(1, 1) verir.
- Genel olarak konuşursak, üzerinde lexicographic emri {0, 1, ..., n - 1} × {0, 1, ..., p - 1} genellikle talimatıyla yürütülen olduğunu izomorf düzen kesinlikle daha az tamsayılar üzerinde olağan düzene np .
- (Eğer bir , ≤) sıralı bir dizi üzerinde lexicographic sırası {0,1} x bir iki kopya “uçtan uca koyarak” tutarındadır A (ilk birinci bileşen 0, birinci bileşen ile ikinci ilişkili 1). Dolayısıyla, N , genellikle sıralı olan doğal sayılar kümesiyse - o zaman ω olarak adlandırılır - {0,1} × N sözlükbilimsel olarak sıralı, ω ile izomorfik değil, ω + ω = ω2 ordinali olan iyi bir sıradır . Sahip olacağız:
- Sözlüksel olarak sıralanan N × {0,1}, N'nin olağan sırası olan 2ω = ω'ye izomorfik iyi bir mertebedir .
- Sözlüksel olarak sıralanan N × N , sıralı ω 2'ye göre izomorfik iyi bir mertebedir .
Özellikleri
- İlk sıra ilişkilerinin her biri ( A ve B'de ) toplam bir sıraysa, A × B üzerindeki sözlüksel sıra ilişkisi bir toplam sıradır.
- Dahası, her bir ilk sıra ilişkisi iyi bir sıraysa, A × B üzerindeki sözlüksel sıra ilişkisi de iyi bir sıradır.
Sonlu Kartezyen ürünlere genelleme
Sonlu bir Kartezyen ürününün A 1 ×… × A k , ikili Kartezyen çarpımı kullanılarak şu şekilde tanımlandığını düşünürsek :
A 1 × A 2 ×… × A k = A 1 × ( A 2 × (… × A k )…)(ya da başka türlü tanımlanmışsa, bu iki küme arasında kanonik bir eşleştirme vardır), doğal olarak, tümevarım yoluyla, sözlüksel sırayı sıralı kümelerin sonlu çarpımlarına genelleştiririz.
K sıralı kümenin Kartezyen çarpımları için sözlük sırasını tanımladığımızı varsayalım . Daha sonra k +1 sıralı kümelerin çarpımı için sözlüksel sırayı tanımlamak için, A 1 , A 2 ,…, A k × A k + 1 , sözlükbilimsel olarak A 1'in ikili Kartezyen çarpımını ve k'nin Kartezyen çarpımını sıralayalım. A 2 ×… × A k × A k + 1'i ayarlar , ikincisinin kendisi sözlükbilimsel olarak sıralanmıştır. Bu, sıralı kümelerinin üründe lexicographic düzeni olup bir 1 x bir 2 x ... x bir k + 1 , böylece ilgili lexicographic düzeninden tanımlanan A 2 x ... x A + 1 k (biz gösterilir katı sırasını tanımlamak <oyundaki tüm setler için):
( bir 1 ,…, a k + 1 ) <( b 1 ,…, b k + 1 ) ancak ve ancak: bir 1 < b 1 veya [ a 1 = b 1 ve ( a 2 ,…, a k + 1 ) <( b 2 ,…, b k + 1 )]Kartezyen ürününü "sondan başlayarak" parçalara ayırarak, aynı sırayı elde ederiz, yani aynı notasyonları koruyarak:
( bir 1 ,…, a k + 1 ) <( b 1 ,…, b k + 1 ) ancak ve ancak: ( bir 1 ,…, bir k ) <( b 1 ,…, b k ) veya [( bir 1 ,…, bir k ) = ( b 1 ,…, b k ) ve bir k + 1 < b k + 1 ].A 1 × A 2 ×… × A k üzerinde sözlüksel sıranın tümevarımı ile tanımı "genişleterek", bu kümelerin her biri sıralanır, şunu elde ederiz:
( bir 1 ,…, bir k ) <( b 1 ,…, b k ) ancak ve ancak a 1 < b 1 veya ( a 1 = b 1 ve a 2 < b 2 ) veya ( a 1 = b 1 ve a 2 = b 2 ve a 3 < b 3 ) veya …… veya ( a 1 = b 1 ve a 2 = b 2 ve ... ve a k-1 = b k-1 ve a k < b k )Örnekler
Sözlüksel olarak N × N × N sıralarsak , her biri genellikle sıralanırsa, 3'e karşılık gelen iyi bir sayılabilir sıralama elde ederiz ki bu, ne ω'ye ne de ω 2'ye eşittir .
Özellikleri
İkili Kartezyen ürünler için belirtilen özellikler, tümevarımla hemen genelleşir: Tamamen sıralı kümelerin sonlu bir Kartezyen çarpımı üzerinde tanımlanan sözlük düzeni, toplam bir sıradır, iyi sıralı kümelerin sonlu Kartezyen çarpımı üzerinde tanımlanan sözlük düzeni iyi bir sıradır.
Sonlu diziler üzerinde sözlük düzeni
Sözlükler için kullanılan sıraya sahip olandır. Önceki durumlardan farklı olarak, keyfi uzunlukların sonlu dizilerini karşılaştırabilmek istiyoruz. Örneğin, sözlükte "ev" "annem" den önce gelir çünkü "benim" = "benim" ve "i" <"m". Bununla birlikte, "ev" 6 harf ve "anne" 5. Bu kelimeler, en yaygın kelimeyi keyfi olarak tamamladığımız alfabeye bir harf eklenmedikçe, aynı bitmiş Kartezyen ürünün unsurları olarak kabul edilemez. Bu sözlük için tamamen düşünülemez, çünkü bir dilin kelimelerinin pratikte maksimum bir uzunluğu vardır (en azından sözlükte görünenleri…), ancak çok yapay olacaktır. Bu nedenle, rasgele uzunluktaki sonlu diziler üzerinde sözlüksel sıralamayı tanımlamak doğaldır.
( E , ≤) bu nedenle sıralı bir küme olsun. Biz set E * = üzerine inşa tüm sonlu Kartezyen ürünlerin birliği E ( E 0 yalnızca boş diziyi içerir). E * üzerindeki sözlük sırasını aşağıdaki gibi tanımlıyoruz . Let bir = ( a 1 , ..., bir p ) ve b = ( b 1 , ..., B q ) herhangi iki eleman olabilir E * ve izin m iki tamsayı küçük p ve q . O zaman a < b ancak ve ancak:
( bir 1 ,…, bir m ) <( b 1 ,…, b m ) ( E m üzerindeki sözlük sıralaması için ) veya ( bir 1 ,…, bir m ) = ( b 1 ,…, b m ) ve m < q (yani p < q ).
Özellikleri
Kolayca başlangıç düzeni ise, bu gösterilen E toplamıdır hakkında lexicographic sipariş E *, elemanlarının sonlu dizilerin grubu E , aynı zamanda toplamıdır.
Öte yandan, iyi düzenin özelliği (eğer tabii dışında korunmadığını E bir olan tekil ). Örneğin, azalan sonsuz dizinin gösterdiği gibi {0, 1} iyi sıralanmıştır, ancak {0, 1} * değildir:
(1)> (0, 1)> (0, 0, 1)> (0, 0, 0, 1)>…Bu nedenle, iyi sıralı bir kümenin sonlu dizilerini doğru bir şekilde sıralamak için, örneğin önce dizilerin uzunluklarını karşılaştırmak için diğer yöntemleri göz önünde bulundurmalıyız.
Dizilerin uzunluklarını dikkate alan tanım
Baader ve Nipkow, sözlüksel sırayı aşağıdaki gibi tanımlar. (E,>) katı bir sıra ise, sözlükbilimsel sıra> * E * üzerinde lex şu şekilde tanımlanır:
u> * lex v if ve only if (| u |> | v | veya (| u | = | v | ve u> | u | lex v)
nerede | w | w kelimesinin uzunluğudur ve> | u | lex , E | u | .
> Katı bir emir ise,> * lex de kesin bir emirdir. > Biterse,> * lex biter.
Notlar ve referanslar
- Franz Baader ve Tobias Nipkow, Term Rewriting and All That , Cambridge University Press ,1999, 18–19 s. ( ISBN 978-0-521-77920-3 , çevrimiçi okuyun )
Ayrıca görün
- Lexicographic düzenin daha genel tanımı üzerinde, bir ailenin ürünü sıralı küme endeksli bir tarafından iyi sıralı kümesi
- Alfabetik sıra