1.04.03 — Sıralama bağıntıları

Haritadaki yerimiz

Matematik haritasındaki konum

Dünya 1 — Matematiksel Dil ve Temeller
Bölüm 1.04 — Bağıntılar, Denklik ve Sıralama

Bu birimin zorunlu ön koşulu 1.04.01 — Bağıntı nedir? birimidir.

Orada bir bağıntının;

yansımalı,
simetrik,
antisimetrik,
geçişli

olabileceğini öğrenmiştik.

Şimdi bu özelliklerden üçünü bir araya getirerek matematikte son derece önemli yeni bir yapı kuracağız:

sıralama.

Bu fikir ileride özellikle;

sayıların sıralanmasında,
alt kümelerin karşılaştırılmasında,
bölünebilmede,
üst ve alt sınırlarda,
supremum ve infimum kavramlarında,
reel sayıların tamlık özelliğinde,
cebirsel yapıların alt yapılarında,
bilgisayar bilimindeki bağımlılık sistemlerinde

yeniden karşımıza çıkacak.

Temel soru

Matematiksel nesneleri genel anlamda nasıl sıralarız?

Daha önemlisi:

Bir sıralamada her iki nesneyi mutlaka karşılaştırabilmek zorunda mıyız?

1. Başlangıç problemi: Her şey tek sıraya dizilebilir mi?

Sıralama deyince ilk akla gelen şey genellikle sayılardır:

1<2<3<4<5.

Burada herhangi iki sayıyı seçtiğimizde hangisinin daha küçük olduğunu söyleyebiliriz.

Örneğin:

2<5.

Bu yüzden sayı doğrusu zihnimizde şu fikri oluşturur:

Bir şeyleri sıralıyorsak hepsini tek bir çizgi üzerinde soldan sağa dizmeliyiz.

Fakat şimdi sayılar yerine kümeleri düşünelim.

Bir küme seçelim:

S=\{a,b\}.

Bunun kuvvet kümesi:

\mathcal P(S) = \{\varnothing,\{a\},\{b\},\{a,b\}\}

olsun.

Bu kümeleri alt küme olma ilişkisine göre düzenlemeye çalışalım.

Şunları biliyoruz:

\varnothing\subseteq\{a\},

\varnothing\subseteq\{b\},

\{a\}\subseteq\{a,b\},

\{b\}\subseteq\{a,b\}.

Peki $\{a\}$ ile $\{b\}$ arasında ne söyleyeceğiz?

\{a\}\subseteq\{b\}

yanlış.

Ama

\{b\}\subseteq\{a\}

da yanlış.

Yani bu iki nesneden hiçbiri diğerinden önce veya aşağıda değildir.

Ortaya çıkan problem

Sayıları sıralarken kullandığımız doğrusal düşünce burada çalışmıyor.

$\{a\}$ ile $\{b\}$ arasında anlamlı bir düzen ilişkisi vardır ama bu iki nesne birbirleriyle karşılaştırılamaz.

Öyleyse matematiğin daha genel bir sıralama fikrine ihtiyacı var:

Bazı nesnelerin karşılaştırılabildiği, bazılarının ise karşılaştırılamadığı bir sıralama mümkün müdür?

İşte kısmi sıralama fikri tam olarak bu ihtiyaca cevap verir.

2. Eski araç neden yetmiyor?

Sayı doğrusu bize özel bir sıralama türü öğretir:

x\leq y \quad\text{veya}\quad y\leq x.

Her iki sayı mutlaka karşılaştırılabilir.

Fakat matematikte karşılaştığımız birçok doğal yapı böyle değildir.

Örneğin:

bir kümenin alt kümeleri,
bir sayının bölenleri,
bir projenin birbirine bağımlı görevleri,
bir yazılım sistemindeki modül bağımlılıkları,
bir organizasyondaki yetki kapsama ilişkileri

tek bir çizgi üzerinde doğal biçimde sıralanmak zorunda değildir.

Bir görev başka bir görevden önce yapılmak zorunda olabilir.

Ama iki bağımsız görev için:

Hangisi önce?

sorusunun matematiksel olarak zorunlu bir cevabı olmayabilir.

Yeni zihinsel model

Sıralamayı artık yalnızca

“soldan sağa dizmek”

olarak düşünmeyeceğiz.

Daha genel fikir şu:

Hangi nesnenin hangi nesnenin altında, öncesinde veya içinde bulunduğunu tutarlı biçimde belirleyen bir bağıntı kurmak.

Bu düzen bazen tek bir zincir oluşturur.

Bazen de dallanır.

3. Kısa tarihsel çerçeve

“Küçük”, “büyük”, “önce”, “sonra” gibi karşılaştırmalar matematiğin çok eski dönemlerinden beri vardır. Sayıların büyüklük bakımından karşılaştırılması için ayrıca bir “sıralama teorisi” icat etmek gerekmiyordu.

Daha soyut soru çok daha sonra belirginleşti:

Sayılar dışında kalan matematiksel nesnelerde de ortak bir “düzen” yapısı var mı?

Kümeler ve soyut bağıntılar matematiğin merkezine yerleştikçe sıralama, belirli nesnelerin özelliği olmaktan çıkarılıp bağıntıların taşıdığı genel bir yapı olarak ele alınmaya başladı.

Bu gelişimin tek bir mucidi yoktur.

yüzyılın başlarında sıralı kümeler artık küme teorisinin önemli araçlarından biriydi. Felix Hausdorff'un 1914'te ortaya koyduğu maksimal ilke de kısmi sıralı kümeler üzerindeki zincirler ve maksimal nesnelerle ilgili erken önemli sonuçlardan biridir.

Bugünkü order theory — sıralama teorisi, bu soyut bakışı sistematik biçimde inceler.

4. Sıralama da bir bağıntıdır

Önceki birimden hatırlayalım.

$A$ kümesi üzerinde bir bağıntı:

R\subseteq A\times A

biçiminde tanımlanabilir.

Eğer $(a,b)\in R$ ise bunu:

aRb

diye yazabiliriz.

Sıralama bağıntılarında ise çoğu zaman daha anlamlı bir sembol kullanacağız:

a\preceq b.

Buradaki $\preceq$ sembolünü şimdilik:

“ $a$ , sıralamamız bakımından $b$ 'den önce veya $b$ 'nin altında”

şeklinde okuyabiliriz.

Bu sembol mutlaka sayısal “küçük veya eşit” anlamına gelmez.

Örneğin $\preceq$ ;

$\leq$ olabilir,
$\subseteq$ olabilir,
“böler” ilişkisi olabilir,
“ön koşuludur” ilişkisi olabilir.

Asıl önemli olan kullandığımız sembol değil, bağıntının taşıdığı özelliklerdir.

5. Kısmi sıralamanın üç koşulu

Kısmi sıralama bağıntısı

$A$ kümesi üzerinde bir $\preceq$ bağıntısı aşağıdaki üç özelliği sağlıyorsa kısmi sıralama bağıntısı (partial order) denir.

1. Yansımalı

Her $a\in A$ için:

a\preceq a.

2. Antisimetrik

Her $a,b\in A$ için:

a\preceq b \quad\text{ve}\quad b\preceq a

ise:

a=b.

3. Geçişli

Her $a,b,c\in A$ için:

a\preceq b \quad\text{ve}\quad b\preceq c

ise:

a\preceq c.

Bir küme ve onun üzerindeki kısmi sıralama birlikte:

(A,\preceq)

biçiminde gösterilir.

Böyle bir yapıya kısmi sıralı küme, İngilizcede partially ordered set veya kısaca poset denir.

Bu üç koşulu yalnızca ezberlemeyelim. Her birinin neden gerekli olduğunu anlayalım.

6. Yansıma neden gerekli?

Bir nesne en azından kendisiyle aynı sıralama konumunda olmalıdır.

Alt küme ilişkisinde:

X\subseteq X.

Sayılarda:

x\leq x.

Bölünebilmede:

n\mid n.

Buradaki $n\mid n$ gösterimi:

“ $n$ , $n$ 'yi böler.”

demektir.

Yansıma, kullandığımız sıralamanın eşitliği de kapsayan biçimidir.

Daha sonra göreceğimiz gibi $\preceq$ yerine yalnızca “kesin olarak önce” anlamına gelen $\prec$ kullanılırsa yansıma beklemeyiz.

Örneğin:

x<x

hiçbir zaman doğru değildir.

Bu nedenle matematikte sıkı sıralama ile sıkı olmayan sıralama birbirinden ayrılır.

7. Antisimetri neden gerekli?

Bu özellik ilk karşılaşmada en çok karıştırılan özelliktir.

Antisimetri:

“ $a$ ile $b$ arasında iki yönlü ilişki asla olamaz.”

demek değildir.

Şunu söyler:

Eğer ilişki iki yönde birden geçerliyse, aslında iki farklı nesneyle karşı karşıya değilizdir.

Yani:

a\preceq b \land b\preceq a \Rightarrow a=b.

Alt kümelerde düşünelim.

Eğer:

X\subseteq Y

ve aynı zamanda:

Y\subseteq X

ise kümelerin eşitliği tanımından:

X=Y

olmak zorundadır.

Bu son derece doğal bir sıralama davranışıdır.

Simetrik ile antisimetrik aynı şey değildir

Simetrik:

aRb\Rightarrow bRa.

Antisimetrik:

aRb\land bRa\Rightarrow a=b.

Bunlar birbirinin değili değildir.

Örneğin eşitlik bağıntısı hem simetrik hem antisimetriktir.

8. Geçişlilik neden gerekli?

Bir düzenin tutarlı olmasını sağlayan temel özelliklerden biri geçişliliktir.

Eğer:

a\preceq b

ve:

b\preceq c

ise doğal olarak:

a\preceq c

bekleriz.

Alt kümelerde:

X\subseteq Y \quad\text{ve}\quad Y\subseteq Z

ise:

X\subseteq Z.

Bir görev bağımlılığı düşünelim:

A görevi tamamlanmadan B başlayamıyor.
B görevi tamamlanmadan C başlayamıyor.

O hâlde $C$ 'ye ulaşabilmek için $A$ da zorunlu olarak geride bırakılmış olmalıdır.

Geçişlilik bu tür dolaylı düzen bilgisini korur.

9. Temel örnek: Alt küme ilişkisi

Şimdi gerçekten bir kısmi sıralamayı baştan doğrulayalım.

Bir $S$ kümesinin kuvvet kümesi:

\mathcal P(S)

üzerinde $\subseteq$ bağıntısını ele alalım.

Alt küme bağıntısı neden kısmi sıralamadır?

Yansımalı

Her $X\in\mathcal P(S)$ için:

X\subseteq X.

Dolayısıyla bağıntı yansımalıdır.

Antisimetrik

Eğer:

X\subseteq Y

ve:

Y\subseteq X

ise küme eşitliği gereği:

X=Y.

Dolayısıyla bağıntı antisimetriktir.

Geçişli

Eğer:

X\subseteq Y

ve:

Y\subseteq Z

ise $X$ 'in her elemanı $Y$ 'dedir, $Y$ 'nin her elemanı da $Z$ 'dedir.

Bu nedenle $X$ 'in her elemanı $Z$ 'dedir:

X\subseteq Z.

Dolayısıyla bağıntı geçişlidir.

Üç özellik de sağlandığı için:

(\mathcal P(S),\subseteq)

bir kısmi sıralı kümedir.

Burada önemli bir ayrıntı var.

Kısmi sıralama olmak için her iki elemanın karşılaştırılabilmesi şartını kullanmadık.

İşte “kısmi” kelimesi tam burada önem kazanıyor.

10. Karşılaştırılabilirlik

Karşılaştırılabilir elemanlar

Bir kısmi sıralı kümede $a$ ve $b$ elemanlarından en az biri:

a\preceq b

veya:

b\preceq a

koşulunu sağlıyorsa $a$ ve $b$ karşılaştırılabilir (comparable) denir.

İkisi de doğru değilse elemanlar karşılaştırılamaz (incomparable).

Tekrar:

S=\{a,b\}

olsun.

$\mathcal P(S)$ içerisinde:

\{a\}\subseteq\{a,b\}

olduğu için $\{a\}$ ve $\{a,b\}$ karşılaştırılabilir.

Ama:

\{a\}\nsubseteq\{b\}

ve:

\{b\}\nsubseteq\{a\}

olduğu için $\{a\}$ ve $\{b\}$ karşılaştırılamaz.

Kısmi sıralamanın kilit fikri

Karşılaştırılamamak bir eksiklik veya hata değildir.

Bazen matematiksel yapı bize gerçekten:

“Bu iki nesneden hiçbiri diğerinin altında değildir.”

der.

Kısmi sıralama tam da bu durumu ifade edebilmemizi sağlar.

11. Tam sıralama

Şimdi sayı doğrusuna geri dönelim.

Reel sayılar üzerinde herhangi $x$ ve $y$ için mutlaka:

x\leq y

veya:

y\leq x

olur.

Yani burada karşılaştırılamayan iki eleman yoktur.

Tam sıralama

Bir $\preceq$ bağıntısı kısmi sıralama olmasının yanında her $a,b\in A$ için:

a\preceq b \quad\text{veya}\quad b\preceq a

koşulunu da sağlıyorsa tam sıralama (total order) denir.

Tam sıralamaya doğrusal sıralama (linear order) da denir.

Dolayısıyla:

\boxed{ \text{Tam sıralama} = \text{Kısmi sıralama} + \text{her çiftin karşılaştırılabilir olması} }

Buradaki “kısmi” ve “tam” kelimeleri bağıntının üç temel özelliğinin az veya çok sağlanmasını anlatmaz.

Her ikisi de:

yansımalı,
antisimetrik,
geçişlidir.

Fark yalnızca karşılaştırılabilirliktedir.

12. Kısmi ve tam sıralamayı karşılaştıralım

Özellik	Kısmi sıralama	Tam sıralama
Yansımalı	✓	✓
Antisimetrik	✓	✓
Geçişli	✓	✓
Her iki eleman karşılaştırılabilir	Gerekmez	✓

Tam sıralama

Tam sayılar üzerinde alışılmış:

\leq

bağıntısı tam sıralamadır.

Örneğin $-7$ ile $4$ karşılaştırılabilir:

-7\leq4.

Aynı şekilde hangi iki tam sayıyı seçersek seçelim biri diğerinden küçük veya eşittir.

Kısmi ama tam olmayan sıralama

$\mathcal P(\{a,b\})$ üzerinde:

\subseteq

bağıntısı kısmi sıralamadır.

Fakat $\{a\}$ ile $\{b\}$ karşılaştırılamadığı için tam sıralama değildir.

13. Bir başka güçlü örnek: Bölünebilme

Pozitif doğal sayılar üzerinde:

a\preceq b \iff a\mid b

şeklinde bir ilişki tanımlayabiliriz.

Burada:

a\mid b

ifadesi, $b$ 'nin $a$ 'nın bir tam sayı katı olduğunu söyler.

Örneğin:

2\mid6,

çünkü:

6=2\cdot3.

Şimdi $\{1,2,3,6\}$ kümesine bakalım.

Şunlar doğrudur:

1\mid2,

1\mid3,

2\mid6,

3\mid6.

Ama:

2\nmid3

ve:

3\nmid2.

Dolayısıyla $2$ ile $3$ karşılaştırılamaz.

Bu yine kısmi ama tam olmayan bir sıralamadır.

Bu örnek ileride sayı teorisinde çok daha önemli hâle gelecek.

Burada amaç bölünebilme teorisini öğrenmek değil; “sıralama” fikrinin yalnızca büyüklük anlamına gelmediğini görmek.

$2<3$ olmasına rağmen bölünebilme sıralamasında $2$ ile $3$ karşılaştırılamaz.

Demek ki:

Sıra, nesnelerin kendisinden değil, üzerinde seçtiğimiz bağıntıdan gelir.

14. Aynı kümenin farklı sıralamaları olabilir

Bu nokta çok önemlidir.

Bir kümenin doğal olarak yalnızca tek bir sıralaması olmak zorunda değildir.

Örneğin pozitif doğal sayılar üzerinde:

Büyüklüğe göre

1\leq2\leq3\leq4\leq\cdots

tam sıralaması vardır.

Ama aynı sayılar üzerinde:

Bölünebilmeye göre

a\preceq b \iff a\mid b

kısmi sıralaması da vardır.

Yani matematikte:

“Bu elemanlar hangi sıradadır?”

sorusundan önce:

“Hangi bağıntıya göre sıralıyoruz?”

sorusunu sormamız gerekir.

15. Sıkı ve sıkı olmayan sıralama

Sayılarla çalışırken hem:

x\leq y

hem de:

x<y

kullanırız.

Bunlar aynı fikrin iki farklı gösterimidir.

Bir kısmi sıralama $\preceq$ verildiğinde:

a\prec b

ifadesini:

a\preceq b \quad\text{ve}\quad a\neq b

olarak tanımlayabiliriz.

$\preceq$ eşitliğe izin verir.

$\prec$ ise yalnızca gerçekten farklı sıralama konumlarını gösterir.

Bu nedenle:

a\preceq a

doğruyken:

a\prec a

yanlıştır.

Öz alt küme örneği

$\subseteq$ sıkı olmayan sıralamadır:

A\subseteq A.

Fakat öz alt küme bağıntısı:

\subsetneq

yansımalı değildir:

A\nsubsetneq A.

Dolayısıyla $\subsetneq$ , burada kullandığımız yansımalı tanıma göre bir kısmi sıralama bağıntısı değildir.

Onun yerine sıkı kısmi sıralama olarak düşünülür.

16. Hasse diyagramı neden gerekli?

Küçük bir kısmi sıralı kümedeki bütün ilişkileri tek tek yazabiliriz.

Ama eleman sayısı büyüdükçe bu oldukça yorucu olur.

Üstelik yansıma ve geçişlilik yüzünden aynı bilgi tekrar tekrar görünür.

Örneğin:

\varnothing\subseteq\{a\}

ve:

\{a\}\subseteq\{a,b\}

olduğunu biliyorsak geçişlilik zaten:

\varnothing\subseteq\{a,b\}

sonucunu verir.

Bu son ilişkiyi ayrıca çizmek zorunda değiliz.

Bu gereksiz bilgileri kaldırarak kısmi sıralamanın yapısını daha temiz gösterebiliriz.

Bunun için Hasse diyagramı kullanılır.

17. Hasse diyagramının mantığı

Sonlu bir kısmi sıralı kümede Hasse diyagramı oluştururken genel olarak:

Her elemanı bir nokta olarak düşünürüz.
Daha büyük elemanları daha yukarı yerleştiririz.
Yansıma nedeniyle oluşan $a\preceq a$ bağlantılarını çizmeziz.
Geçişlilikten zaten çıkarılabilen bağlantıları çizmeziz.
Geriye yalnızca doğrudan komşu sıralama ilişkileri kalır.

Bu son ilişki için kullanılan fikir örtme (cover) ilişkisidir.

Örtme ilişkisi

$x\prec y$ olsun.

Eğer $x$ ile $y$ arasında:

x\prec z\prec y

sağlayan hiçbir $z$ yoksa, $y$ elemanının $x$ 'i örttüğü söylenir.

Hasse diyagramında esas olarak bu doğrudan örtme ilişkileri çizilir.

Şimdi:

\mathcal P(\{a,b\})

kümesini $\subseteq$ ile sıralayalım.

Kuvvet kümesinin Hasse diyagramı

        {a,b}
        /   \
      {a}   {b}
        \   /
          ∅

Boş küme en altta, a ve b tek elemanlı kümeleri ortada ve a-b kümesi en üsttedir. a ile b tek elemanlı kümeleri birbirleriyle karşılaştırılamaz.

Bu tek çizim bize birçok bilgi verir.

Örneğin:

\varnothing\subseteq\{a,b\}

bağlantısı doğrudan çizilmemiştir.

Çünkü zaten:

\varnothing\subseteq\{a\}\subseteq\{a,b\}

yolundan geçişlilik sayesinde bunu biliyoruz.

Ayrıca $\{a\}$ ile $\{b\}$ arasında çizgi yoktur.

Bu da onların karşılaştırılamadığını gösterir.

Hasse diyagramını bir “sayı doğrusu” gibi değil, bir hiyerarşi haritası gibi düşünmek daha yararlıdır.

Dikey yön sıralama bilgisini taşır.

Dallanma ise karşılaştırılamayan elemanların bulunabileceğini görünür hâle getirir.

18. Minimal ve maksimal elemanlar

Şimdi kısmi sıralamalarda çok önemli bir ayrımla karşılaşacağız.

Önce minimal eleman kavramına bakalım.

Minimal eleman

$(A,\preceq)$ bir kısmi sıralı küme olsun.

$m\in A$ elemanı için $m$ 'den kesin olarak daha küçük başka bir eleman yoksa $m$ 'ye minimal eleman denir.

Başka bir deyişle:

x\preceq m

olduğunda zorunlu olarak:

x=m

oluyorsa $m$ minimaldir.

Minimal demek:

“Bunun altında başka eleman yok.”

demektir.

Ama:

“Bu bütün elemanlardan küçüktür.”

demek değildir.

Bu ayrım birazdan çok önemli olacak.

Benzer biçimde:

Maksimal eleman

$(A,\preceq)$ içerisinde $m$ 'den kesin olarak daha büyük başka bir eleman yoksa $m$ 'ye maksimal eleman denir.

Yani:

m\preceq x

olduğunda zorunlu olarak:

x=m

olmalıdır.

19. En küçük ve en büyük eleman

Şimdi daha güçlü kavramlara geçelim.

En küçük eleman

$(A,\preceq)$ içerisinde $l\in A$ için her $x\in A$ elemanına karşı:

l\preceq x

oluyorsa $l$ 'ye en küçük eleman (least element) denir.

Yani en küçük eleman yalnızca altında başka eleman bulunmayan bir eleman değildir.

Kümedeki bütün elemanların altındadır.

Benzer biçimde:

En büyük eleman

$g\in A$ için her $x\in A$ elemanına karşı:

x\preceq g

oluyorsa $g$ 'ye en büyük eleman (greatest element) denir.

Şimdi temel farkı açıkça yazalım:

\boxed{ \text{minimal} \neq \text{en küçük} }

ve:

\boxed{ \text{maksimal} \neq \text{en büyük} }

genel olarak.

20. Neden aynı şey değiller?

Şu kümeyi düşünelim:

A= \big\{ \{a\}, \{b\}, \{a,b\} \big\}

ve yine $\subseteq$ bağıntısını kullanalım.

Birden fazla minimal eleman

        {a,b}
        /   \
      {a}   {b}

a-b kümesi üstte, a ve b tek elemanlı kümeleri altta bulunur. a ve b tek elemanlı kümeleri minimaldir ve birbirleriyle karşılaştırılamaz; a-b kümesi en büyük elemandır.

Burada $\{a\}$ 'nın altında başka eleman yoktur.

Dolayısıyla $\{a\}$ minimaldir.

Aynı şekilde $\{b\}$ de minimaldir.

Ama $\{a\}$ en küçük değildir.

Çünkü:

\{a\}\nsubseteq\{b\}.

$\{b\}$ de en küçük değildir:

\{b\}\nsubseteq\{a\}.

Sonuç:

Bu kısmi sıralı kümenin iki minimal elemanı vardır ama en küçük elemanı yoktur.

Buna karşılık $\{a,b\}$ bütün diğer elemanları kapsadığı için:

\{a\}\subseteq\{a,b\},

\{b\}\subseteq\{a,b\}.

Dolayısıyla $\{a,b\}$ hem maksimal hem de en büyük elemandır.

21. En küçük eleman varsa tektir

Bu fark bize güzel bir matematiksel sonuç verir.

En küçük elemanın tekliği

Bir kısmi sıralı kümede iki farklı en küçük eleman bulunduğunu varsayalım.

Bunlara $a$ ve $b$ diyelim.

$a$ en küçük olduğuna göre:

a\preceq b.

$b$ de en küçük olduğuna göre:

b\preceq a.

Ama sıralama antisimetriktir.

Dolayısıyla:

a=b.

Yani iki farklı en küçük eleman bulunamaz.

En küçük eleman varsa tektir.

Aynı argüman en büyük eleman için de geçerlidir.

Önemli sonuç

Bir kısmi sıralı kümede birden fazla minimal eleman olabilir.
Birden fazla maksimal eleman olabilir.
Fakat en küçük eleman varsa yalnızca bir tanedir.
En büyük eleman varsa yalnızca bir tanedir.

Ayrıca:

\text{en küçük}\Rightarrow\text{minimal},

ama genel olarak:

\text{minimal}\nRightarrow\text{en küçük}.

Benzer biçimde:

\text{en büyük}\Rightarrow\text{maksimal},

ama:

\text{maksimal}\nRightarrow\text{en büyük}.

22. Çok küçük ama öğretici bir örnek

Yalnızca:

A=\{\{a\},\{b\}\}

kümesini $\subseteq$ ile sıralayalım.

$\{a\}$ ile $\{b\}$ karşılaştırılamaz.

Dolayısıyla Hasse diyagramı:

İki karşılaştırılamayan eleman

{a}     {b}

a ve b tek elemanlı kümeleri aynı seviyede bulunur ve aralarında sıralama bağlantısı yoktur.

Her ikisinin de altında başka eleman yoktur.

Dolayısıyla ikisi de minimaldir.

Her ikisinin de üstünde başka eleman yoktur.

Dolayısıyla ikisi de maksimaldir.

Ama en küçük eleman yoktur.

Çünkü iki elemandan hiçbiri diğerinin altında değildir.

En büyük eleman da yoktur.

Bu örnek:

“minimal = en küçük”

yanılgısını tamamen ortadan kaldırmalıdır.

23. Denklik bağıntısıyla sıralama bağıntısı arasındaki fark

Bir önceki birimde denklik bağıntılarını görmüştük.

İki yapı birbirine çok benzer görünür:

Denklik bağıntısı

yansımalı,
simetrik,
geçişli.

Kısmi sıralama

yansımalı,
antisimetrik,
geçişli.

Aradaki tek kelimelik değişiklik yapının anlamını tamamen değiştirir.

Denklik	Sıralama
Nesneleri “aynı tür” kabul eder	Nesneleri bir düzen içinde karşılaştırır
Simetriktir	Antisimetriktir
Sınıflara ayırır	Hiyerarşik/düzen yapısı kurar
$a\sim b$ ise $b\sim a$	$a\preceq b$ ise genellikle $b\preceq a$ değildir

İki farklı soyutlama

Denklik bağıntısı şu soruyu soruyordu:

“Hangi farklı nesneleri aynı kabul edebilirim?”

Sıralama bağıntısı ise şunu soruyor:

“Hangi nesne hangisinin altında, öncesinde veya içinde?”

Biri aynılık türünü, diğeri düzen türünü soyutlar.

24. Sıralama olmayan bağıntılar

Bir bağıntının “bir tür karşılaştırma” gibi görünmesi onun mutlaka matematiksel sıralama olduğu anlamına gelmez.

Boy bakımından karşılaştırmak

Bir insan kümesinde:

aRb

ifadesini:

“ $a$ kişisinin boyu, $b$ kişisinin boyundan küçük veya eşittir.”

şeklinde tanımlayalım.

Bu ilişki ilk bakışta $\leq$ gibi görünüyor.

Ama iki farklı kişinin boyu aynı olabilir.

Bu durumda:

aRb

ve:

bRa

olduğu hâlde:

a\neq b.

Dolayısıyla bağıntı insanlar üzerinde antisimetrik değildir.

Bu nedenle kısmi sıralama değildir.

Fakat nesneler “insanlar” değil de “boy uzunlukları” olsaydı alışılmış $\leq$ sıralaması çalışırdı.

Bu bize yine aynı dersi verir:

Bir bağıntının özellikleri yalnızca kullandığımız kelimeye değil, hangi küme üzerinde tanımlandığına da bağlıdır.

Arkadaşlık

İnsanlar üzerinde:

“ $a$ , $b$ ile arkadaştır.”

bağıntısı genellikle simetriktir:

aRb\Rightarrow bRa.

Fakat geçişli değildir.

$a$ , $b$ ile; $b$ de $c$ ile arkadaş olabilirken $a$ ile $c$ birbirini hiç tanımayabilir.

Dolayısıyla arkadaşlık bir sıralama değildir.

25. Bir bağıntının sıralama olup olmadığını nasıl inceleriz?

Bundan sonra bir bağıntıyla karşılaştığımızda sistematik bir yöntem kullanabiliriz.

Kontrol yöntemi

Bir $R$ bağıntısının kısmi sıralama olup olmadığını belirlemek için:

Adım 1 — Yansıma

Sor:

\forall a\in A,\quad aRa

doğru mu?

Değilse dur.

Kısmi sıralama değildir.

Adım 2 — Antisimetri

Sor:

aRb\land bRa

olduğunda mutlaka:

a=b

mi?

Değilse kısmi sıralama değildir.

Adım 3 — Geçişlilik

Sor:

aRb\land bRc

olduğunda mutlaka:

aRc

mi?

Üçü de doğruysa $R$ bir kısmi sıralamadır.

Adım 4 — Tamlık kontrolü

Her $a,b\in A$ için:

aRb \quad\text{veya}\quad bRa

doğru mu?

Evetse sıralama tam sıralamadır.

Hayırsa yalnızca kısmi sıralamadır.

26. Uygulamalar: Bu fikir nerede gerçekten kullanılır?

Matematik içinde

Sıralama bağıntıları ileride birçok farklı matematiksel yapının içinde ortaya çıkar.

Örneğin:

Alt kümeler

A\subseteq B

ilişkisi kümeleri kapsama bakımından sıralar.

Bölenler

a\mid b

ilişkisi sayıları bölünebilme bakımından sıralayabilir.

Alt uzaylar

Lineer cebirde bir vektör uzayının alt uzayları, kapsama bağıntısıyla kısmi sıralanabilir.

Üst ve alt sınırlar

Bir sıralı kümede bir grubun bütün elemanlarının üstünde veya altında kalan elemanları incelemek mümkündür.

Bu fikir bizi daha sonra:

üst sınır,
alt sınır,
supremum,
infimum,
tamlık

kavramlarına götürecek.

Özellikle reel sayıların yapısını anlamada bu bağlantı çok önemli olacaktır.

Bilgisayar bilimi ve teknoloji

Bir yazılım projesindeki görevleri düşünelim.

Veritabanı şeması
        │
        ├──► API
        │      │
        │      └──► Mobil uygulama
        │
        └──► Raporlama

Burada bazı işler başka işlerin ön koşuludur.

Fakat örneğin API geliştirme ile raporlama birbirine bağlı değilse:

“Hangisi önce gelmelidir?”

sorusunun zorunlu bir cevabı yoktur.

İki iş paralel yürütülebilir.

Bu nedenle bağımlılık sistemlerinin doğal yapısı çoğu zaman tek bir doğrusal sıra değil, kısmi sıralamadır.

Benzer yapı;

paket bağımlılıklarında,
derleme sistemlerinde,
iş akışlarında,
proje planlamasında,
dağıtık sistemlerdeki bazı olay ilişkilerinde

ortaya çıkar.

Gündelik düşünme

Bir yemek hazırlarken:

fırının ısınması,
hamurun hazırlanması,
sosun hazırlanması

gibi görevler bulunabilir.

Bazı adımlar diğerlerinden önce gelmek zorundadır.

Ama birbirinden bağımsız iki hazırlık aynı anda yapılabilir.

Dolayısıyla günlük hayattaki “önce–sonra” ilişkileri bile çoğu zaman tam değil, kısmi bir sıra oluşturur.

27. Sınırlar ve yaygın hatalar

1. Kısmi demek eksik demek değildir

“Kısmi sıralama” ifadesindeki kısmi kelimesi, bağıntının bazı kuralları sağlamadığı anlamına gelmez.

Kısmi sıralama:

yansımalı,
antisimetrik,
geçişli

olmak zorundadır.

“Kısmi” yalnızca bazı farklı eleman çiftlerinin karşılaştırılamayabileceğini anlatır.

2. Antisimetrik, simetrik olmayan demek değildir

Bir bağıntının antisimetrik olması:

“Hiçbir zaman ters yön oluşmaz.”

demek değildir.

Ters yön aynı anda oluşursa elemanların aynı olması gerekir.

3. Minimal ile minimumu karıştırma

Minimal:

Altında başka eleman yok.

En küçük:

Bütün elemanların altında.

Birden fazla minimal eleman olabilir.

Birden fazla en küçük eleman olamaz.

4. Hasse diyagramında her ilişki çizilmez

Hasse diyagramı:

yansıma bağlantılarını,
geçişlilikten çıkan gereksiz bağlantıları

bilerek kaldırır.

Dolayısıyla çizgide doğrudan bağlantı olmaması her zaman iki elemanın karşılaştırılamadığı anlamına gelmez.

Aralarında yukarı doğru bir yol varsa karşılaştırılabilirler.

5. Sıralama mutlaka sayısal büyüklük değildir

a\preceq b

ifadesi her zaman:

“ $a$ sayısal olarak daha küçüktür.”

demek değildir.

Bağıntıya göre:

alt kümedir,
böler,
ön koşuludur,
içerilir

gibi çok farklı anlamlar taşıyabilir.

28. Birlikte analiz edelim

Örnek 1 — Tam mı, kısmi mi?

A=\{1,2,3,4\}

üzerinde alışılmış $\leq$ bağıntısını düşünelim.

Yansımalı:

a\leq a.

Antisimetrik:

a\leq b \land b\leq a \Rightarrow a=b.

Geçişli:

a\leq b \land b\leq c \Rightarrow a\leq c.

Ayrıca hangi iki elemanı seçersek seçelim karşılaştırabiliriz.

Dolayısıyla $\leq$ bir tam sıralamadır.

Örnek 2 — Kısmi ama tam değil

A=\{\{1\},\{2\},\{1,2\}\}

üzerinde $\subseteq$ bağıntısını düşünelim.

$\subseteq$ yansımalı, antisimetrik ve geçişlidir.

Dolayısıyla kısmi sıralamadır.

Ama:

\{1\}\nsubseteq\{2\}

ve:

\{2\}\nsubseteq\{1\}.

Bu iki eleman karşılaştırılamaz.

Dolayısıyla sıralama tam değildir.

Örnek 3 — Minimal ama en küçük değil

Bir önceki örnekte:

\{1\}

ve:

\{2\}

minimaldir.

Ama hiçbirisi en küçük değildir.

Çünkü birbirleriyle karşılaştırılamazlar.

Buna karşılık:

\{1,2\}

hem maksimal hem en büyüktür.

29. Düşünme durakları

Şimdi metne bakmadan cevaplamaya çalış.

Düşünme 1

Bir kısmi sıralı kümede iki farklı minimal eleman bulunabilir mi?

Eğer cevabın evetse, neden bu durum antisimetriyi bozmaz?

Düşünme 2

Bir kısmi sıralı kümenin en küçük elemanı varsa bu eleman minimal olmak zorunda mıdır?

Tersi doğru mudur?

Düşünme 3

Bir bağıntı yansımalı, antisimetrik ve geçişli fakat bazı eleman çiftleri karşılaştırılamıyorsa buna ne denir?

Düşünme 4

Bir Hasse diyagramında $a$ ile $c$ arasında doğrudan çizgi bulunmuyor fakat:

c
│
b
│
a

şeklinde bir yol varsa $a$ ve $c$ karşılaştırılabilir mi?

Neden?

30. Bu birimin açtığı yeni kapı

Sıralamadan supremum ve tamlığa

Şu ana kadar yalnızca:

“Kim kimin altında?”

sorusuyla ilgilendik.

Ama sıralama kurulduğu anda çok daha derin sorular ortaya çıkar.

Örneğin bir $B$ alt kümesi için:

Bütün elemanların üstünde bulunan bir eleman var mı?

Daha da önemlisi:

Bu üst elemanların en küçüğü var mı?

Bu soru bizi ileride:

\sup B

yani supremum kavramına götürecek.

Reel sayıların en önemli yapısal özelliklerinden biri olan tamlık da özünde bir sıralama problemidir.

Dolayısıyla bugün öğrendiğimiz şey yalnızca nesneleri düzenlemek değildir.

Sonsuz kümelerin sınır davranışını anlamak için gereken dilin ilk parçasını kurduk.

31. Alıştırmalar

A. Kavrama

Kısmi sıralamanın üç temel özelliğini kendi sözlerinle açıkla. Her özellik için neden gerekli olduğuna dair bir cümle yaz.
“Kısmi” kelimesinin neden “üç sıralama kuralından yalnızca bazıları sağlanıyor” anlamına gelmediğini açıkla.
Minimal eleman ile en küçük eleman arasındaki farkı formül kullanmadan anlat.
Kısmi sıralama ile denklik bağıntısının ortak özelliklerini ve temel farkını belirt.

B. Teknik

Aşağıdaki kümede:

A=\{1,2,3,6,12\}

$a\preceq b$ bağıntısını:

a\mid b

şeklinde tanımla.

Hangi eleman çiftlerinin karşılaştırılabilir olduğunu belirle ve Hasse diyagramını oluşturmaya çalış.

Aşağıdaki kümede:

A= \big\{ \{1\}, \{2\}, \{1,2\}, \{1,2,3\} \big\}

$\subseteq$ bağıntısına göre:

minimal elemanları,
maksimal elemanları,
varsa en küçük elemanı,
varsa en büyük elemanı

belirle.

C. Gerekçelendirme

Bir kısmi sıralı kümede en büyük elemanın, eğer varsa, neden tek olmak zorunda olduğunu antisimetriden yararlanarak göster.
Öz alt küme bağıntısının:

\subsetneq

neden bu derste kullandığımız tanıma göre kısmi sıralama olmadığını açıkla. Buna rağmen neden bir “sıkı sıralama” olarak anlamlı olduğunu belirt.

İnsanlar üzerinde:

“ $a$ 'nın yaşı $b$ 'nin yaşından küçük veya eşittir.”

bağıntısının neden antisimetrik olmak zorunda olmadığını bir karşı örnekle göster.

D. Transfer

Bir proje için şu bağımlılıklar verilsin:

A → C
B → C
C → D
B → E

Ok:

“soldaki görev sağdakinden önce tamamlanmalıdır”

anlamına gelsin.

Bu görevleri bir kısmi sıralama olarak yorumla.

Hangi görevler karşılaştırılamaz?
Minimal görevler hangileridir?
Maksimal görevler hangileridir?
En küçük görev var mıdır?
En büyük görev var mıdır?

Cevaplarını yalnızca listeleme; nedenlerini de açıkla.

32. Birimin tamamlanma ölçütü

Bu birim yalnızca tanımları okuyarak tamamlanmış sayılmaz.

Birimi gerçekten tamamlamış olmak için şunları yapabilmelisin:

Sıralama bağıntısına neden ihtiyaç duyulduğunu açıklayabilmek.
Bir bağıntının yansımalı, antisimetrik ve geçişli olup olmadığını inceleyebilmek.
Bir bağıntının kısmi sıralama veya tam sıralama olduğunu belirleyebilmek.
İki elemanın karşılaştırılabilir olup olmadığını söyleyebilmek.
Sonlu ve basit bir kısmi sıralamanın Hasse diyagramını okuyup oluşturabilmek.
Minimal ile en küçük elemanı birbirinden ayırabilmek.
Maksimal ile en büyük elemanı birbirinden ayırabilmek.
En küçük ve en büyük elemanların neden varsa tek olduğunu antisimetriden çıkarabilmek.
Sıralama kavramını yalnızca sayısal “küçük–büyük” ilişkisiyle sınırlamadan yeni bir örneğe aktarabilmek.

33. Kısa sentez

Neden vardı?

Çünkü matematikte birçok nesne doğal bir düzene sahip olmasına rağmen bu nesnelerin her çifti sayı doğrusundaki gibi karşılaştırılamaz.

Ne öğrendik?

Bir kısmi sıralama:

yansımalı,
antisimetrik,
geçişli

bir bağıntıdır.

Her eleman çifti ayrıca karşılaştırılabiliyorsa tam sıralama elde ederiz.

Ayrıca:

minimal ile en küçük,
maksimal ile en büyük

kavramlarının aynı olmadığını gördük.

Neyi artık yapabiliyoruz?

Bir bağıntının gerçekten bir sıralama oluşturup oluşturmadığını inceleyebilir, sonlu kısmi sıralamaları Hasse diyagramlarıyla görebilir ve düzen içindeki özel elemanları ayırt edebiliriz.

Sırada ne var?

Bağıntıların iki temel özel türünü gördük:

\text{denklik} \qquad\text{ve}\qquad \text{sıralama}.

Bundan sonra bağıntıların başka çok önemli bir özel türüne geçeceğiz:

fonksiyonlar.

Daha ileride ise sıralama fikri yeniden karşımıza çıkacak ve:

\text{sıralama} \rightarrow \text{üst/alt sınır} \rightarrow \text{supremum/infimum} \rightarrow \text{tamlık}

zincirini oluşturacak.