Genel sipariş toplamı - Total order
Gelen matematik bir toplam ya da doğrusal sıra a, kısmi sıralama her iki eleman karşılaştırılabilir olduğu. Bu bir toplam sipariş bir dur, ikili ilişki bazı seti tatmin herkes için takip ve içinde :
- ( refleksif ).
- Eğer ve sonra ( geçişli )
- Eğer ve sonra ( antisimetrik )
- veya ( önceden toplam olarak adlandırılan güçlü bağlantılı ).
Toplam siparişler bazen basit , bağlantılı veya tam siparişler olarak da adlandırılır .
Toplam sipariş ile donatılmış bir set, tamamen sıralı bir settir ; terimler basitçe bir set sipariş , doğrusal olarak sipariş seti ve loset da kullanılmaktadır. Terimi, zincir bazen bir eş anlamlı olarak tanımlanır tamamen sıralı bir setin , ancak belirli bir kısmen sıralı bir setin tamamen sıralı alt-tür karşılık gelir.
Belirli bir kısmi düzenin toplam düzene uzantısına , bu kısmi düzenin doğrusal uzantısı denir .
Kesin ve katı olmayan toplam siparişler
Bir katı toplam sipariş kümesi a, katı kısmi sıralama üzerinde her hangi bir iki eleman karşılaştırılabilir. Bu bir toplam sipariş bir dur, ikili ilişki bazı seti tatmin herkes için takip ve içinde :
Her bir (non-sıkı) toplam sipariş için ilişkili bir ilişki vardır denir, katı toplam sipariş ile ilişkili iki eşdeğer şekilde tanımlanabilir:
- if ve ( dönüşlü azalma ).
- değilse (yani olan tamamlayıcı bir converse arasında ).
Tersine, katı bir toplam düzenin dönüşlü kapanışı (katı olmayan) bir toplam düzendir.
Örnekler
- Herhangi alt küme tamamen sıralı küme ait X tamamen üzerinde düzenin kısıtlama sipariş edildiği X .
- Boş kümedeki benzersiz düzen, ∅ , toplam bir düzendir.
- Herhangi bir temel sayı veya sıra numarası kümesi (daha güçlüsü, bunlar iyi sıralardır ).
- Eğer X herhangi seti ve bir fX'ten tam sıralı bir kümeye bir injektif fonksiyon , o zaman f , ancak ve ancak f ( x 1 ) ≤ f ( x 2 ) ise x 1 ≤ x 2 ayarlayarak X üzerinde bir toplam sıralamaya neden olur .
- Lexicographical sipariş üzerine Kartezyen ürünün tamamen sipariş setleri ailesinin endeksli bir tarafından iyi sipariş seti , kendisi tam bir düzendir.
- Kümesi reel sayılar "daha az veya hiç eşit" olağan tarafından sipariş (≤) veya "büyüktür veya eşit" (≥) ilişkileri tamamen sıralanır ve dolayısıyla böylece alt kümeleri olan doğal sayılar , tamsayılar ve rasyonel sayılar . Bunların her biri, (bir kadar özgü olduğu gösterilebilir sipariş izomorfik ) burada belli bir özelliği, (ile tamamen sıralı bir setin "ilk örnek" terimi, bir toplam sipariş bir olduğu ilk zaman, eğer bir özellik için oda vardır özelliği, A'dan B'nin bir alt kümesine bir sıra izomorfizmi vardır ):
- Doğal sayılar, üst sınırı olmayan, boş olmayan, tam sıralı bir başlangıç kümesi oluşturur .
- Tamsayılar, ne bir üst ne de bir alt sınırı olmayan, boş olmayan, tam sıralı bir başlangıç kümesi oluşturur .
- Rasyonel sayılar , gerçek sayılarda yoğun olan, tam sıralı bir başlangıç kümesi oluşturur . Ayrıca, yansımalı indirgeme < rasyonel sayılar üzerinde yoğun bir düzendir .
- Gerçek sayılar , sıra topolojisinde (aşağıda tanımlanmıştır) bağlı olan bir başlangıç sınırsız tam sıralı küme oluşturur .
- Sıralı alanlar tamamen tanım gereği sıralanmıştır. Rasyonel sayıları ve gerçek sayıları içerirler. Her sıralı alan, rasyonel sayılarla izomorf olan sıralı bir alt alan içerir. Herhangi bir Dedekind-tamamlanmış sıralı alan, gerçek sayılara eşbiçimlidir.
- Standart sözlük sırasına göre sıralanan alfabenin harfleri , örneğin, A < B < C vb., kesin bir toplam düzendir.
Zincirler
Terimi, zincir bazen tamamen sıralı bir setin ile eşanlamlı olarak tanımlanır, fakat genel olarak bir atıfta için kullanılan alt- a kısmen sıralı bir setin tamamen neden olduğu sipariş için sipariş edilir. Tipik olarak, kısmen sıralı küme, belirli bir kümenin dahil edilerek sıralanan bir alt kümeleri kümesidir ve terim, zincir kümesinin özelliklerini belirtmek için kullanılır. Bu yüksek sayıda iç içe küme düzeyi, terimin kullanışlılığını açıklar.
Kullanımının genel bir örneği zinciri tamamen sıralı alt-gruba atıfta için Zorn'un lemması kısmen sıralı küme, her zincir ise, bu iddia X bir üst bağlanmış olan , X , ardından X, en az bir maksimum elemanı içerir. Zorn lemması, X'in bir alt kümeler kümesi olmasıyla yaygın olarak kullanılır ; Bu durumda, upperbound bir zincir elemanları birliği ispat ile elde edilen X olan X . Bu, bir vektör uzayının Hamel tabanlarına sahip olduğunu ve bir halkanın maksimal ideallere sahip olduğunu kanıtlamak için genellikle kullanılan yoldur .
Bazı bağlamlarda, kabul edilen zincirler, olağan sıraları veya ters sıraları ile doğal sayılarla eşbiçimli sıralıdır . Bu durumda, bir zincir monoton bir dizi ile tanımlanabilir ve dizinin artan veya azalan olmasına bağlı olarak artan zincir veya azalan zincir olarak adlandırılır .
Kısmen sıralı bir küme, azalan her zincir sonunda stabilize olursa , azalan zincir koşuluna sahiptir . Örneğin , azalan zincir koşuluna sahipse , bir sipariş iyi kurulmuştur . Benzer şekilde, yükselen zincir koşulu , her yükselen zincirin sonunda stabilize olduğu anlamına gelir. Örneğin, bir Noether halkası , idealleri artan zincir koşulunu karşılayan bir halkadır .
Diğer bağlamlarda, yalnızca sonlu kümeler olan zincirler dikkate alınır. Bu durumda, genellikle bir zincir olarak kısaltılan sonlu zincirlerden söz edilir . Bu durumda, bir zincirin uzunluğu , zincirin ardışık elemanları arasındaki eşitsizliklerin (veya küme inklüzyonlarının) sayısıdır; yani, zincirdeki elemanlardan bir eksi sayı. Böylece bir tekli küme , sıfır uzunlukta bir zincirdir ve sıralı bir çift , bir uzunlukta bir zincirdir. Boyuta bir boşluk genellikle tanımlanmıştır ya da bölme odasının zincirlerinin maksimal uzunluk olarak karakterize edilir. Örneğin, bir vektör alan boyutu zincirlerinin maksimal uzunluğu doğrusal bölme odasının ve Krull boyutu a değişmeli halka zincirlerinin maksimal uzunluğu asal idealin .
"Zincir", kısmen sıralı kümeler olmayan yapıların bazı tamamen sıralı alt kümeleri için de kullanılabilir . Düzenli polinom zincirleri ile bir örnek verilmiştir . Başka bir örnek, "zincir" in bir grafikte yürüyüşle eşanlamlı olarak kullanılmasıdır .
Diğer kavramlar
kafes teorisi
Tamamen sıralı bir küme, belirli bir kafes türü olarak tanımlanabilir , yani içinde sahip olduğumuz bir küme.
- hepsi için a , b .
Daha sonra a ≤ b ancak ve ancak . Bu nedenle, tam sıralı bir küme, bir dağıtım örgüsüdür .
Sonlu toplam siparişler
Basit bir sayma argümanı, herhangi bir boş olmayan sonlu tamamen sıralı kümenin (ve dolayısıyla boş olmayan herhangi bir alt kümesinin) bir en küçük öğeye sahip olduğunu doğrulayacaktır. Böylece her sonlu toplam mertebe aslında bir kuyu mertebesidir . Doğrudan bir kanıt veya her sıra düzeni olduğunu gözlemleyerek ya izomorfik düzeni bir üzere sıra her sonlu toplam sipariş olduğunu gösterebilir bir izomorfik düzeni bir üzere ilk parçanın <tarafından sipariş edilen doğal sayılar. Başka bir deyişle, k elemanlı bir kümedeki toplam sıralama , ilk k doğal sayı ile bir önermeye neden olur . Bu nedenle, sonlu toplam siparişleri veya sipariş tipi ω olan kuyu sıralarını , sıralamaya (sıfır veya bir ile başlayarak) uygun bir şekilde doğal sayılarla endekslemek yaygındır .
kategori teorisi
Tamamen setleri oluşturmak sipariş tam alt kategori bir kategori ve kısmen sıralı küme ile morfizma emir saygı haritaları olarak, örneğin, haritalar f olduğu takdirde, örneğin , bir ≤ b sonra f ( a ) ≤ f ( b ).
Bir bijective haritası iki sipariş saygı iki tamamen sıralı küme arasında bir olduğunu izomorfizm Bu kategoride.
Sipariş topolojisi
Herhangi bir tam sıralı X kümesi için ( a , b ) = { x : a < x ve x < b }, (−∞, b ) = { x : x < b }, ( a , ∞) açık aralıklarını tanımlayabiliriz. = { x : a < x } ve (−∞, ∞) = X . Bu açık aralıkları , herhangi bir sıralı kümede, sıra topolojisinde bir topoloji tanımlamak için kullanabiliriz .
Bir kümede birden fazla düzen kullanıldığında, belirli bir düzen tarafından indüklenen düzen topolojisi hakkında konuşulur. Örneğin eğer N <az ve bir> Doğal sayılar biz siparişi topoloji atıfta bulunuyor olabilir büyüktür N tarafından uyarılan <ve siparişi topoloji N onlar özdeş olmak olur ama bu durumda neden olduğu> (olmaz Genel olarak).
Toplam düzen tarafından indüklenen düzen topolojisinin kalıtsal olarak normal olduğu gösterilebilir .
eksiksizlik
Bir üst sınırı olan her boş olmayan alt kümenin bir en küçük üst sınırı varsa , tam sıralı bir kümenin tamamlanmış olduğu söylenir . Örneğin, R reel sayılar kümesi tamdır, ancak Q rasyonel sayılar kümesi tam değildir. Başka bir deyişle, çeşitli tamlık kavramları ("toplam" olmakla karıştırılmamalıdır) kısıtlamalara taşınmaz . Örneğin, fazla gerçek sayılar ilgili ≤ bir özelliği, her olmasıdır boş olmayan bir alt kümesi S ve R , bir ile üst sınırı olarak R bir en üst sınırı olarak (ayrıca sup) R . Bununla birlikte, rasyonel sayılar için bu üstünlük mutlaka rasyonel değildir, bu nedenle aynı özellik, ≤ ilişkisinin rasyonel sayılarla sınırlandırılmasında geçerli değildir.
X'in eksiksizliği ile düzen topolojisinin özelliklerini ilişkilendiren bir dizi sonuç vardır:
- X üzerindeki sipariş topolojisi bağlıysa, X tamamlanmıştır.
- X, sırası topolojisi altında bağlıysa ve tamamlanmıştır ve yoktur, sadece boşluk içinde X (bir boşluk iki puan bir ve b olarak X ile bir < b , öyle ki herhangi bir C tatmin bir < c < b .)
- X , ancak ve ancak düzen topolojisinde kapalı olan her sınırlı küme kompakt olduğunda tamamlanır.
Bir (onun emri topoloji ile) Tamamen sıralı küme komple kafes olduğunu kompakt . Örnekler, reel sayıların kapalı aralıklarıdır, örneğin [0,1] birim aralığı ve afinite olarak genişletilmiş gerçek sayı sistemi (genişletilmiş gerçek sayı doğrusu). Bu örnekler arasında düzeni koruyan homeomorfizmalar vardır .
siparişlerin toplamları
Herhangi iki ayrık toplam mertebe ve için, sette iki mertebenin toplamı veya bazen sadece olarak adlandırılan doğal bir düzen vardır :
- için , ancak ve ancak aşağıdakilerden biri geçerliyse geçerlidir:
- ve
- ve
- ve
Sezgisel olarak bu, ikinci kümenin öğelerinin, birinci kümenin öğelerinin üstüne eklendiği anlamına gelir.
Daha genel olarak, eğer tamamen sıralı bir indeks kümesi ise ve yapı , kümelerin ikili olarak ayrık olduğu lineer bir sıra ise, o zaman doğal toplam mertebe şu şekilde tanımlanır:
- için , şu durumlarda geçerlidir:
- Ya bazılarıyla var
- ya da içinde olanlar var ,
Tamamen sıralı kümelerin Kartezyen çarpımı üzerindeki siparişler
Artan kuvvet sırasına göre, yani azalan çift kümelerine göre , iki tam sıralı kümenin Kartezyen çarpımı üzerindeki olası sıralardan üçü şöyledir:
- Sözlüksel sıra : ( a , b ) ≤ ( c , d ) ancak ve ancak a < c veya ( a = c ve b ≤ d ) ise. Bu tam bir sipariş.
- ( a , b ) ≤ ( c , d ) ancak ve ancak a ≤ c ve b ≤ d ( ürün siparişi ) ise. Bu kısmi bir sipariştir.
- ( a , b ) ≤ ( c , d ) ancak ve ancak ( a < c ve b < d ) veya ( a = c ve b = d ) ( karşılık gelen katı toplam siparişlerin doğrudan çarpımının yansımalı kapanışı ). Bu aynı zamanda kısmi bir emirdir.
Üçü de benzer şekilde ikiden fazla kümenin Kartezyen çarpımı için tanımlanabilir.
Uygulanan vektör uzayı R , n , bu marka bir her bir sıralı vektör alanı .
Kısmen sıralı küme örneklerine de bakın .
R n'nin bir alt kümesinde tanımlanan n gerçek değişkenin gerçek bir işlevi, katı bir zayıf sırayı ve bu alt kümede karşılık gelen bir toplam ön siparişi tanımlar .
İlgili yapılar
Antisimetrik, geçişli ve dönüşlü (ancak tam olması gerekmeyen) ikili bir ilişki kısmi bir düzendir .
Bir grup uyumlu bir toplam sipariş ile bir olup tamamen sipariş grup .
Toplam düzenin (olarak tanımlanabilen) redüksiyonu olan yalnızca birkaç önemsiz yapı vardır. Yönelimi unutmak bir aradalık ilişkisine yol açar . Uçların yerinin unutulması döngüsel bir sıra ile sonuçlanır . Her iki verinin de unutulması bir ayırma ilişkisine neden olur .
Geçişli İkili İlişkiler | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Tüm tanımlar zımnen gerektiren homojen bir ilişki olduğu geçişli : Bir " ✓ " sütunu, özelliği satır tanımı gerekli olduğunu gösterir. Örneğin, bir denklik ilişkisinin tanımı simetrik olmasını gerektirir. Burada , homojen bir ilişkinin karşılayabileceği ek özellikler listelenmiştir .
|
Ayrıca bakınız
- Artinian yüzüğü
- sipariş teorisi
- iyi düzenlenmiş
- Suslin'in sorunu
- taşralı hattı
- permütasyon
- Ön ek sırası - aşağı doğru toplam kısmi sipariş
Notlar
Referanslar
- Garrett Birkhoff (1967). Kafes Teorisi . Kolokyum Yayınları. 25 . Providence: Am. Matematik. Soc.
- Brian A. Davey; Hilary Ann Priestley (1990). Kafeslere Giriş ve Düzen . Cambridge Matematik Ders Kitapları. Cambridge Üniversitesi Yayınları. ISBN'si 0-521-36766-2. LCCN 89009753 .
- Fuchs, L (1963). Kısmi Sıralı Cebirsel Sistemler . Bergama Basın.
- George Gratzer (1971). Kafes teorisi: ilk kavramlar ve dağıtımlı kafesler. WH Freeman and Co. ISBN 0-7167-0442-0
- John G. Hocking ve Gail S. Young (1961). Topoloji. Düzeltilmiş yeniden baskı, Dover, 1988. ISBN 0-486-65676-4
- Rosenstein, Joseph G. (1982). Doğrusal sıralamalar . New York: Akademik Basın.
- Schmidt, Günther ; Ströhlein, Thomas (1993). İlişkiler ve Grafikler: Bilgisayar Bilimcileri için Ayrık Matematik . Berlin: Springer-Verlag. ISBN'si 978-3-642-77970-1.
Dış bağlantılar
- "Tamamen sıralanmış set" , Matematik Ansiklopedisi , EMS Press , 2001 [1994]