Sıralama Bağıntısı

Sıralama bağıntısı, bir küme üzerinde tanımlı; yansıyan, ters simetrik ve geçişken olan ikili bağıntıdır.

Motivasyon

Sıralama, gündelik hayatta da kullandığımız yaygın bir kavramdır. Pek çok şeyi bir biçimde sıralayabiliriz — sözcükleri alfabe sırasına, öğrencileri okulda boya, malları fiyata göre. Bütün bunları, genellikle ≤ simgesiyle gösterdiğimiz sıralama bağıntısı anlatır. İlgili simgeler şunlardır: <, >, ≥. Anlamları açıktır.

Böyle bir bağıntıdan ne beklerdik? Simgeden bile anlaşılıyor ki sıralama bağıntısında aynı olan elemanlar da bulunacak — yani amacımız “küçük ya da eşit” bağıntısının özelliklerini tanımlamak. Böyle bir bağıntı yansıyan olmalıdır. a ≤ a geçerli olmalıdır.

Başka ne? Simetri kesinlikle geçerli olmaz — fiyata göre sıralıyorsak ve araba ekmekten ucuzsa, ekmek aynı zamanda arabadan ucuz olamaz. Peki a ≤ b ve aynı zamanda b ≤ a olsaydı genel olarak ne beklerdik? Bu bir yerde anlamlı olur muydu? Evet, a = b olsaydı. Bağıntıya konan elemanların sırasının önem taşımadığı tek durum, elemanların aynı olduğu durumdur — sıralama bu yüzden ters simetriktir.

Son olarak arabanın ekmekten pahalı olduğunu ve uçağın arabadan da pahalı olduğunu biliyorsak uçağın ekmekten kesinlikle pahalı olmasını bekleriz. Bunu geçişkenlik anlatır.

Kısmi Sıralama

Az önce tanımladığımız şey aslında yalnızca kısmi sıralamadır, tam değildir. Neden tam değil? Kümeler üzerinde bir sıralama tanımlamayı deneyelim. İki kümeyi nasıl karşılaştırabiliriz?

A kümesi, A ⊂ B ise, yani A kümesi B kümesinin alt kümesiyse, B kümesinden küçük ya da ona eşittir diyelim. Bu anlamlıdır, çünkü A = {1, 2} ve B = {1, 2, 3} ise A için küçüktür diyebiliriz — B kümesi A ile aynı elemanları içerir, üstüne bir de üç sayısını içerir. Dolayısıyla örneğin şunlar geçerli olur:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

Ama şu kümeleri karşılaştırmak istediğimizde sorun çıkar: A = {a, b} ve B = {a, c}. Hangisi daha küçük ya da daha büyük? Sorun şu: iki küme de a elemanını içeriyor, ama ikinci elemanları farklı. Hiçbiri diğerinin alt kümesi değil, dolayısıyla ne A ≤ B ne de B ≤ A geçerlidir. Böyle kümeler bizim sıralamamıza göre karşılaştırılamaz.

Bu yüzden her iki elemanı karşılaştırılabilen kümeye tam sıralı küme ya da zincir deriz. Böyle kümelere örnek, olağan sıralamalı sayı kümeleridir. Her iki a, b gerçek sayısı için a ≤ b mi yoksa b ≤ a mı olduğuna karar verebilirsin.

Gündelik Hayattan Örnekler

Karşılaştırmamanın işe yaradığı bir örnek, lezzete göre sıralama olabilir; < bağıntısı “daha az lezzetli olmak” anlamına gelsin. İki meyveyi birbiriyle karşılaştırmanın anlamı vardır, örneğin “elma” < “çilek”; çilek elmadan daha lezzetli demek bu. Ya da iki tatlıyı: “irmik helvası” < “baklava”; baklava irmik helvasından daha lezzetli.

Sorun şu: bir meyveyle bir tatlıyı karşılaştırmak herhalde çok zor. Çilek mi daha lezzetli, baklava mı? Dolayısıyla bu bağıntıda bazı yiyecek çiftleri karşılaştırılamaz.

Son örnekte yalnızca meyvelerle sınırlı kalırsak tam sıralı bir kümemiz olduğunu söyleyebiliriz, çünkü bütün meyvelerin lezzetini karşılaştırabiliriz.

Minimal ve Maksimal Eleman, En Küçük ve En Büyük Eleman

Sıralı bir M kümemiz varsa min ∈ M elemanına, x < min olacak biçimde bir x ∈ M yoksa minimal deriz. Yani min elemanından daha küçük bir eleman bulamıyoruz.

max ∈ M elemanına, x > max olacak biçimde bir x ∈ M yoksa maksimal deriz. Yani daha büyük bir eleman bulamıyoruz.

Bu iki kavram, en küçük ve en büyük kavramlarından farklıdır.

a ∈ M elemanına, her x ∈ M için a ≤ x geçerliyse en küçük deriz. Yani en küçük eleman a, M kümesinin bütün öteki elemanlarından küçük ya da onlara eşittir.

b ∈ M elemanına, her x ∈ M için b ≥ x geçerliyse en büyük deriz. En büyük eleman b, M kümesinin bütün öteki elemanlarından büyük ya da onlara eşittir.

En büyük eleman ile maksimal eleman arasındaki fark nedir? Maksimal eleman birden fazla olabilir, çünkü küme mutlaka tam sıralı olmak zorunda değildir. Meyveleri ve tatlıları karşılaştırdığımız örneğe dönersek çileğin en lezzetli meyve, baklavanın da en lezzetli tatlı olduğunu söyleyebiliriz. Ama bu ikisini kendi aralarında artık karşılaştıramıyoruz; çilek mi yoksa baklava mı daha lezzetli, bilmiyoruz.

Bu yüzden iki eleman da maksimaldir. Baklavadan daha lezzetli bir yiyecek bulamayız — baklava bütün öteki tatlılardan daha lezzetlidir ve onu meyvelerle karşılaştıramayız. Çilek için de aynısı geçerli — çilek bütün meyvelerden daha lezzetlidir ve onu tatlılarla karşılaştıramayız.

Ama ikisi de en büyük, yani bu anlamda en lezzetli değildir. Çünkü baklavanın en lezzetli/en büyük olması için bütün meyveler dahil her şeyden daha lezzetli olması gerekirdi. Oysa onu meyvelerle karşılaştıramayacağımızı söylemiştik; bu yüzden en lezzetli yiyecek olamaz, sıralama kuramının terimleriyle yalnızca maksimaldir.

Bir kümenin en büyük elemanı varsa bu elemanın aynı zamanda maksimal olduğu kolayca görülür. a elemanı kümenin bütün öteki elemanlarından büyükse (en büyük elemanın tanımı) bundan da büyük bir eleman kesinlikle bulamayız (maksimal elemanın tanımı).

En büyük ve en küçük elemanı olan bir kümeye örnek, kapalı [0, 1] aralığıdır. Aynı aralığı açık seçersek ne en büyük ne de en küçük elemanı olurdu: (0, 1).

Sonsuz sayıda minimal eleman istesek R sıralamasını şöyle tanımlayabilirdik. Önce M_x yardımcı kümelerini tanımlarız. Kümeler şu biçimde olacak: (0, 1) aralığındaki her x için M_x = {y ∣ y = x + n} kümesini tanımlarız; burada n negatif olmayan bir tam sayıdır. Böylece örneğin şu kümeleri elde ederiz:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Her M_x kümesi üzerinde R_x ile göstereceğimiz olağan sıralamayı tanımlarız. En sonunda bu sıralamaları birleştiririz: R = ∪ R_x. Bu sıralamada yalnızca başlangıçtaki zincirlerin içinde karşılaştırma yapabiliriz. Yani 0,5 ≤ 2,5 olup olmadığını öğrenebiliriz, ama 0,5 ≤ 2,7 olup olmadığını öğrenemeyiz; çünkü bu sayılar aynı M_x kümesinde değildi ve ilişkileri tanımlı değil.

Bu sıralama bağıntısında (0, 1) aralığındaki her eleman minimal elemandır.

Hasse Diyagramları

Sıralı kümeleri Hasse diyagramıyla çizebiliriz. Bu, köşelerin kümenin elemanlarını gösterdiği bir graftır; (a, b) köşeleri arasındaki bir kenar bize a < b olduğunu ve aynı zamanda a < c < b olacak biçimde bir c elemanının bulunmadığını söyler. Yani a ve b elemanlarının arasında başka bir eleman yoktur. Üstelik graftaki a köşesi b köşesinden daha aşağıda olmalıdır. Hasse diyagramı örneği:

Bu Hasse diyagramı {A, B, C, D, E, F} sıralı kümesini gösterir. Şunlar geçerlidir: A < B, B < E, ayrıca elbette A < E de geçerlidir, ama bu köşeler arasında kenar yoktur, çünkü A < B < E olacak biçimde bir B köşesi vardır. E ve D elemanları karşılaştırılamaz, çünkü hiçbiri ötekinin üstünde ya da altında değildir.

Hasse diyagramları genellikle böyle düzgün hizalanmış çizilse de bu kesinlikle şart değildir. Önceki Hasse diyagramı şöyle de görünebilir:

Başka bir örnek şu küme olabilir: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Bunlar 60 sayısının pozitif tam sayı bölenleridir. Bölünebilmeye göre sıralama şöyle gösterilebilir:

Bölünebilmeye göre sıralama, (a, b) ∈ R ancak ve ancak a sayısı b sayısını bölüyorsa demektir. Diyagramdan her sayının üstünde, kendisinin böldüğü sayıların bulunduğunu görebiliriz. Örneğin 6 sayısının üstünde 12, 30 ve 60 sayıları var. 4 sayısının üstünde 12, 20 ve 60 sayıları var. Vb. Buna karşılık 3 sayısının üstünde 10 sayısı yok, çünkü 3 sayısı 10 sayısını bölmez — dikkat et, 10 sayısı görsel olarak 3 sayısının üstünde, ama ona “aşağıdan yukarıya” giden bir çizgi yok. 3 sayısından yalnızca yukarı doğru ilerlersek 15 ve 6 sayılarına, onlardan da 30 sayısına gidebiliriz. 10 sayısına ancak aşağı inerek varabilirdik, buna ise izin yok.