Bağıntılar: özellikler, denklik bağıntıları ve kısmi sıralamalar

Bağıntılar (relations) fonksiyonların genelleştirilmiş hali. Fonksiyonda her girdinin tam bir çıktısı vardı; bağıntıda bir eleman hiçbir şeyle ya da birçok şeyle ilişkili olabilir. Bu hafta final konusu. Sınavda beklenen soru tipleri: verilen bir bağıntının dört özelliğini kontrol etmek, “Prove that $R$ is an equivalence relation”, denklik sınıflarını yazmak, Hasse diyagramı çizmek ve bağıntı saymak.

Altın kurallar:

1. “Her” özelliklerini (reflexive) tek bir eksik çift bozar, “eğer … ise” özelliklerini (symmetric, transitive) tek bir karşı örnek bozar.
2. Antisymmetric, “symmetric değil” demek değildir. İkisi aynı anda doğru ya da aynı anda yanlış olabilir.
3. Denklik = reflexive + symmetric + transitive. Kısmi sıralama = reflexive + antisymmetric + transitive.
4. Bileşke $S\circ R$: önce $R$, sonra $S$.

Tanımlar

$A$‘dan $B$‘ye bir ikili bağıntı (binary relation), $A\times B$‘nin herhangi bir alt kümesidir. $(a,b)\in R$ yerine $a\,R\,b$ yazılır. $A$‘dan $A$‘ya bağıntıya ”$A$ üzerinde bağıntı” (relation on $A$) denir.

Sezgi: $A$ öğrenciler, $B$ dersler olsun. ”$a$, $b$ dersini alıyor” bir bağıntıdır. Bir öğrenci hiç ders almayabilir ya da beş ders alabilir. Her fonksiyon bir bağıntıdır; tersi doğru değil.

$|A| = n$ ise $|A\times A| = n^2$ çift var ve her biri ya bağıntıda ya değil. Yani $A$ üzerinde $2^{n^2}$ bağıntı var.

Dört özellik

$R$, $A$ üzerinde bir bağıntı olsun.

Örnek 1. $\{1,2,3,4\}$ üzerinde $\le$: her $a\le a$ (reflexive). $1\le 2$ ama $2\not\le 1$ (symmetric değil). $a\le b$ ve $b \le a$ ise $a = b$ (antisymmetric). $a\le b\le c$ ise $a \le c$ (transitive).

Örnek 2. $\{1,2,3\}$ üzerinde $R = \{(1,1),(1,2),(2,1)\}$:

reflexive?      (2,2) yok              -> HAYIR
symmetric?      (1,2) ve (2,1) ikisi de var  -> EVET
antisymmetric?  (1,2),(2,1) var ama 1 != 2  -> HAYIR
transitive?     (2,1),(1,2) var, (2,2) yok   -> HAYIR

TUZAK · transitive kontrolünde $a = c$ durumunu atlamak. Örnek 2’de $(2,1)$ ve $(1,2)$‘den $(2,2)$ gerekir. Çoğu öğrenci sadece “üç farklı eleman” zincirlerine bakar ve bunu kaçırır.

İPUCU · boş koşul. “Eğer … ise” özelliklerinde öncül hiç sağlanmıyorsa özellik otomatik doğrudur. Boş bağıntı symmetric, antisymmetric ve transitive’dir (ama $A$ boş değilse reflexive değildir).

Bağıntı saymak

$|A| = n$. Köşegende $n$ çift, köşegen dışında $n^2 - n$ çift var; köşegen dışı çiftler $\{a,b\}$ eşleşmelerinde gruplanır, $\frac{n(n-1)}{2}$ eşleşme.

Mantık: symmetric’te köşegen çiftleri serbest ($2^n$) ve her eşleşme “ikisi birden ya da hiçbiri” ($2$ seçenek). Antisymmetric’te her eşleşme için 3 seçenek: sadece $(a,b)$, sadece $(b,a)$, hiçbiri.

Bağıntıların bileşkesi ve kuvvetleri

$R$: $A\to B$, $S$: $B \to C$ ise

$S\circ R = \{(a,c) : \exists b\ \big((a,b)\in R \wedge (b,c)\in S\big)\}.$

Fonksiyon bileşkesi gibi: önce $R$ ile git, sonra $S$ ile devam et. Kuvvetler: $R^1 = R$, $R^{n+1} = R^n \circ R$. Önemli teorem: $R$ geçişken $\iff$ her $n\ge 1$ için $R^n \subseteq R$.

Geçişken kapanış (transitive closure) $R^*$: $R$‘yi içeren en küçük geçişken bağıntı. Yönlü graf olarak düşün: $a$‘dan $b$‘ye bir yol varsa $(a,b)\in R^*$. Matrisle $M_{R^*} = M_R \vee M_R^{[2]} \vee \dots \vee M_R^{[n]}$; pratikte Warshall algoritması kullanılır.

Denklik bağıntıları

Reflexive, symmetric ve transitive bir bağıntıya denklik bağıntısı (equivalence relation) denir. Sezgi: “aynı takımda oynuyor”, “aynı kalanı veriyor”, “aynı doğum yılında” gibi bir “aynılık” ilişkisi.

$a$‘nın denklik sınıfı (equivalence class): $[a]_R = \{s : (a,s)\in R\}$.

Temel teorem: denklik sınıfları ya aynıdır ya da ayrıktır, birleşimleri $A$‘dır. Yani bir bölüntü (partition) oluştururlar. Tersine her bölüntü bir denklik bağıntısı tanımlar (“aynı blokta olmak”). Bu yüzden $n$ elemanlı kümedeki denklik bağıntısı sayısı, bölüntü sayısına (Bell sayısı) eşittir: $n = 3$ için 5, $n = 4$ için 15.

En klasik örnek: $m$ modülünde denklik. $a \equiv b \pmod m$ ancak ve ancak $m \mid a - b$. $m$ tane sınıf var: $[0], [1], \dots, [m-1]$.

Tam yazılmış ispat

Claim. Let $m > 1$ be an integer. The relation $R = \{(a,b) : a \equiv b \pmod m\}$ on $\mathbb{Z}$ is an equivalence relation.

Proof. Reflexive. For every integer $a$, $a - a = 0 = m\cdot 0$, so $m \mid a - a$ and $a\,R\,a$. Symmetric. Suppose $a\,R\,b$. Then $a - b = mk$ for some integer $k$. Hence $b - a = m(-k)$, and $-k$ is an integer, so $b\,R\,a$. Transitive. Suppose $a\,R\,b$ and $b\,R\,c$. Then $a - b = mk$ and $b - c = ml$ for some integers $k, l$. Adding, $a - c = m(k + l)$, so $m \mid a - c$ and $a\,R\,c$. Since $R$ is reflexive, symmetric and transitive, it is an equivalence relation. $\blacksquare$

Türkçesi: her özelliği ayrı başlıkla yaz, tanımı ($a - b = mk$) açık yaz, sonunda üçünü birden andığın bitiş cümlesini koy. Hocalar puanı özellik başına verir.

Kısmi sıralamalar

Reflexive, antisymmetric ve transitive bağıntıya kısmi sıralama (partial order) denir; $(S, \preccurlyeq)$ çiftine poset denir. Örnekler: sayılarda $\le$, pozitif tam sayılarda $\mid$, kümelerde $\subseteq$.

“Kısmi” çünkü her iki eleman karşılaştırılabilir (comparable) olmak zorunda değil: $2 \nmid 3$ ve $3\nmid 2$. Her ikili karşılaştırılabiliyorsa total order (tam sıralama) denir.

Hasse diyagramı

Poset’i çizmenin kısa yolu. Yönlü grafından üç şeyi sil:

1. köşegen döngülerini (reflexive’den zaten biliniyor),
2. geçişkenlikten gelen kenarları ($a \preccurlyeq b \preccurlyeq c$ varsa $a$-$c$ kenarı),
3. ok yönlerini (küçük olan aşağıda çizilir).

Geriye sadece örtme (cover) çiftleri kalır: $a \prec b$ ve arada eleman yok.

Örnek. 18’in bölenleri $\{1,2,3,6,9,18\}$, bölünebilme ile:

seviye 3:            18
                    /  \
seviye 2:          6    9
                  / \  /
seviye 1:        2   3
                  \ /
seviye 0:          1
kenarlar: 1-2, 1-3, 2-6, 3-6, 3-9, 6-18, 9-18   (7 kenar)

Terimler: maximal (üstünde kimse yok), minimal (altında kimse yok), greatest/least element (herkesten büyük/küçük, tek olmalı), upper bound (bir alt kümenin hepsinden büyük eşit), least upper bound (üst sınırların en küçüğü). Bölünebilmede lub = ekok (lcm), glb = ebob (gcd).

n-li bağıntılar (kısaca)

$A_1\times A_2\times\dots\times A_n$‘nin alt kümesine n-ary relation denir. Veritabanı tablosu tam olarak budur: her satır bir $n$-li (n-tuple), her sütun bir alan. Seçme (selection) satır süzer, izdüşüm (projection) sütun siler, birleştirme (join) iki tabloyu ortak alanlarda eşler. Finalde en fazla bir tanım sorusu olarak gelir.

Sık yapılan hatalar