4  Bağıntılar

“\(x\), \(y\)’nin annesidir”, “\(x < y\)”, “\(A \subseteq B\)”, “\(3\) sayısı \(12\)’yi böler” — bunların hepsi iki nesne arasındaki bir ilişkiyi söyler. Matematik bu fikri şaşırtıcı derecede basit bir yolla kesinleştirir: bir bağıntı, ilişkili olan çiftlerin kümesinden başka bir şey değildir. Önceki bölümde tanımladığımız kartezyen çarpım (Tanım 3.7) tam da bu yüzden gerekliydi.

Bu bölümde bağıntı kavramını ve temel özelliklerini (yansımalı, simetrik, ters simetrik, geçişli) öğreneceğiz; sonra iki özel bağıntı türünü inceleyeceğiz: bir kümeyi “aynı türden” parçalara bölen denklik bağıntıları ve elemanları “küçükten büyüğe” dizen sıralama bağıntıları. İkisi de kitabın geri kalanında sürekli karşımıza çıkacak; fonksiyon kavramı da bir sonraki bölümde özel bir bağıntı olarak tanımlanacak.

4.1 Bağıntı Kavramı

Bir \(X\) kümesindeki bazı elemanları bir \(Y\) kümesindeki bazı elemanlarla “eşlemek” istiyoruz. Hangi \(x\)’in hangi \(y\) ile eşlendiğini söylemenin en ekonomik yolu, eşlenen \((x, y)\) çiftlerini listelemektir.

Tanım 4.1 (Bağıntı) \(X\) ve \(Y\) boş olmayan kümeler olsun. \(X \times Y\) kartezyen çarpımının her \(R\) alt kümesine \(X\)’ten \(Y\)’ye bir bağıntı (relation) denir.

• \((x, y) \in R\) ise \(x\) ile \(y\)’nin \(R\) bağıntısıyla ilişkili olduğu söylenir ve \(x \mathrel{R} y\) yazılır. \((x, y) \notin R\) ise \(x\) ile \(y\) ilişkili değildir.
• \(X = Y\) ise \(R \subseteq X \times X\) bağıntısına \(X\) üzerinde bir bağıntı denir.

Tanımın gücü genelliğindedir: \(X \times Y\)’nin her alt kümesi bir bağıntıdır; bir “kural” ya da “formül” olması gerekmez. Boş küme \(\varnothing\) da \(X \times Y\)’nin kendisi de bağıntıdır (birincisinde hiçbir çift ilişkili değildir, ikincisinde hepsi ilişkilidir). Bilinen örnekler:

• \(\mathbb{R}\) üzerinde “küçüktür” bağıntısı: \(R_{<} = \{(x, y) \in \mathbb{R} \times \mathbb{R} : x < y\}\). \(2 \mathrel{R_{<}} 5\) doğrudur, \(5 \mathrel{R_{<}} 2\) yanlıştır.

• \(\mathcal{P}(X)\) üzerinde alt küme bağıntısı: \(\{(A, B) \in \mathcal{P}(X) \times \mathcal{P}(X) : A \subseteq B\}\) (bkz. Tanım 3.3).

• \(\mathbb{N}\) üzerinde bölünebilirlik. \(a \mid b\) yazılan bu bağıntı şu kümedir:

  \[\{(a, b) \in \mathbb{N} \times \mathbb{N} : b = ak \text{ olacak biçimde bir } k \in \mathbb{N} \text{ vardır}\}\]

Bir bağıntıyı iki biçimde çizebiliriz: \(X\) ve \(Y\)’nin elemanlarını iki sütuna yazıp ilişkili çiftler arasına ok koyarak (ok şeması) ya da \(X\) ve \(Y\) sayı kümeleriyse \((x, y)\) noktalarını koordinat düzlemine işaretleyerek (grafik). \(R_{<}\) bağıntısının grafiği, \(y = x\) doğrusunun üst tarafındaki açık yarı düzlemdir.

Bir ilişkinin yönünü çevirmek (“annesidir” yerine “çocuğudur” demek) yeni bir ilişki verir; bunu da bir bağıntı olarak yazalım.

Tanım 4.2 (Ters Bağıntı) \(R \subseteq X \times Y\) bir bağıntı olsun. \(R\)’nin bütün ikililerinin bileşenleri yer değiştirilerek elde edilen

\[R^{-1} = \{(y, x) : (x, y) \in R\} \subseteq Y \times X\]

bağıntısına \(R\)’nin ters bağıntısı (inverse relation) denir.

Yani \(y \mathrel{R^{-1}} x \Leftrightarrow x \mathrel{R} y\). Örneğin \(R_{<}\)’nin tersi “büyüktür” bağıntısıdır: \((y, x) \in R_{<}^{-1} \Leftrightarrow x < y \Leftrightarrow y > x\).

Bir bağıntıda \(X\)’in her elemanının bir eşi olmak zorunda değildir; gerçekten “kullanılan” elemanları ayırmak yararlıdır.

Tanım 4.3 (Bağıntının Tanım Kümesi ve Görüntü Kümesi) \(R \subseteq X \times Y\) bir bağıntı olsun.

• \(R\)’de ilk bileşen olarak geçen elemanların kümesine \(R\)’nin tanım kümesi (domain) denir:

  \[T_R = \{x \in X : \exists y \in Y,\ (x, y) \in R\}.\]

• \(R\)’de ikinci bileşen olarak geçen elemanların kümesine \(R\)’nin görüntü kümesi (range) denir:

  \[G_R = \{y \in Y : \exists x \in X,\ (x, y) \in R\}.\]

Tanım gereği \(T_R \subseteq X\) ve \(G_R \subseteq Y\)’dir; ama eşitlik gerekmez. Tersi alındığında tanım kümesiyle görüntü kümesi yer değiştirir.

Önerme 4.1 (Ters Bağıntının Özellikleri) \(R \subseteq X \times Y\) bir bağıntı olsun. O zaman

1. \((R^{-1})^{-1} = R\),
2. \(T_{R^{-1}} = G_R\) ve \(G_{R^{-1}} = T_R\).

İspat

(1) \((x, y) \in (R^{-1})^{-1} \Leftrightarrow (y, x) \in R^{-1} \Leftrightarrow (x, y) \in R\); her iki adım ters bağıntının tanımıdır. Aynı elemanlara sahip olduklarından kümeler eşittir.

(2) \(y \in T_{R^{-1}}\) olması, \((y, x) \in R^{-1}\) olacak biçimde bir \(x \in X\) bulunması demektir; bu da \((x, y) \in R\) olacak biçimde bir \(x\) bulunmasına, yani \(y \in G_R\)’ye denktir. İkinci eşitlik, bu sonucun \(R\) yerine \(R^{-1}\)’e uygulanıp (1)’in kullanılmasıyla çıkar: \(G_{R^{-1}} = T_{(R^{-1})^{-1}} = T_R\).

\(\blacksquare\)

Örnek 4.1 (Sonlu Bir Bağıntı) \(X = \{1, 2, 3\}\) ve \(Y = \{a, b\}\) olsun. \(R = \{(1, a), (2, b), (3, a)\}\) bağıntısının tersini, tanım kümesini ve görüntü kümesini bulunuz.

Çözüm

\(R \subseteq X \times Y\) olduğundan gerçekten \(X\)’ten \(Y\)’ye bir bağıntıdır. Her ikilinin bileşenlerini yer değiştirerek

\[R^{-1} = \{(a, 1), (b, 2), (a, 3)\} \subseteq Y \times X\]

buluruz. İlk bileşenler \(1, 2, 3\) olduğundan \(T_R = \{1, 2, 3\} = X\); ikinci bileşenler \(a\) ve \(b\) olduğundan \(G_R = \{a, b\} = Y\). Önerme 4.1 ile uyumlu olarak \(T_{R^{-1}} = \{a, b\} = G_R\)’dir.

\(\blacksquare\)

Örnek 4.2 (Toplamı Beş Olan Çiftler) \(\mathbb{N}\) üzerinde \(R = \{(x, y) \in \mathbb{N} \times \mathbb{N} : x + y = 5\}\) bağıntısını liste yöntemiyle yazınız; tersini, tanım ve görüntü kümesini bulunuz.

Çözüm

\(x, y \ge 1\) ve \(x + y = 5\) olduğundan \(x \in \{1, 2, 3, 4\}\) ve \(y = 5 - x\)’tir:

\[R = \{(1, 4), (2, 3), (3, 2), (4, 1)\}.\]

Bileşenleri yer değiştirince \(R^{-1} = \{(4, 1), (3, 2), (2, 3), (1, 4)\} = R\) çıkar; yani bu bağıntı kendi tersine eşittir. Bunun nedeni \(x + y = 5\) koşulunun \(x\) ile \(y\)’de simetrik olmasıdır. \(T_R = G_R = \{1, 2, 3, 4\}\); ikisi de \(\mathbb{N}\)’nin öz alt kümesidir.

\(\blacksquare\)

4.2 Bağıntıların Özellikleri

Bir küme üzerindeki bağıntıların en sık sorulan dört özelliği vardır. Her biri, kümenin bütün elemanları için geçerli olması gereken bir koşul söyler; bu yüzden hepsi tümel niceleyiciyle yazılır.

Tanım 4.4 (Yansımalı, Simetrik, Ters Simetrik ve Geçişli Bağıntılar) \(R\), bir \(X\) kümesi üzerinde bir bağıntı olsun.

1. Her \(x \in X\) için \((x, x) \in R\) ise \(R\) yansımalıdır (reflexive): her eleman kendisiyle ilişkilidir.

   \[\forall x \in X,\ x \mathrel{R} x.\]

2. \((x, y) \in R\) olduğunda \((y, x) \in R\) de oluyorsa \(R\) simetriktir (symmetric): ilişki yön seçmez.

   \[\forall x, y \in X,\ x \mathrel{R} y \Rightarrow y \mathrel{R} x.\]

3. \((x, y) \in R\) ve \((y, x) \in R\) olduğunda \(x = y\) olmak zorundaysa \(R\) ters simetriktir (anti-symmetric): farklı iki eleman arasında çift yönlü ilişki olamaz.

   \[\forall x, y \in X,\ (x \mathrel{R} y \ \text{ ve } \ y \mathrel{R} x) \Rightarrow x = y.\]

4. \((x, y) \in R\) ve \((y, z) \in R\) olduğunda \((x, z) \in R\) de oluyorsa \(R\) geçişlidir (transitive): ilişki zincirleme aktarılır.

   \[\forall x, y, z \in X,\ (x \mathrel{R} y \ \text{ ve } \ y \mathrel{R} z) \Rightarrow x \mathrel{R} z.\]

Bir bağıntının bu özelliklerden birine sahip olmadığını göstermek için Teorem 2.1’yı uygularız: tümel niceleyicinin olumsuzu bir karşıt örnektir.

• Yansımalı değil: \((x, x) \notin R\) olan bir \(x\) vardır.
• Simetrik değil: \((x, y) \in R\) ama \((y, x) \notin R\) olan bir çift vardır.
• Ters simetrik değil: \(x \neq y\) olduğu hâlde hem \((x, y)\) hem \((y, x)\) \(R\)’de olan bir çift vardır.
• Geçişli değil: \((x, y), (y, z) \in R\) ama \((x, z) \notin R\) olan bir üçlü vardır.

UyarıSimetrik ile ters simetrik birbirinin zıddı değildir

İki özellik birbirini dışlamaz, birinin yokluğu ötekinin varlığı anlamına gelmez. \(X\) üzerindeki eşitlik bağıntısı \(\{(x, x) : x \in X\}\) hem simetrik hem ters simetriktir. \(\{1, 2, 3\}\) üzerinde \(\{(1, 2), (2, 1), (1, 3)\}\) ise ne simetriktir (\((1, 3) \in R\) ama \((3, 1) \notin R\)) ne ters simetriktir (\((1, 2), (2, 1) \in R\) ama \(1 \neq 2\)).

Örnek 4.3 (Sonlu Bir Bağıntının Özellikleri) \(X = \{1, 2, 3\}\) üzerinde \(R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}\) bağıntısının yansımalı, simetrik, ters simetrik ve geçişli olup olmadığını belirleyiniz.

Çözüm

Yansımalı: \((1, 1), (2, 2), (3, 3)\) üçü de \(R\)’dedir; evet.

Simetrik: \(R\)’deki her \((x, y)\) için \((y, x)\)’i arayalım. \((x, x)\) biçimindeki çiftler kendi tersleridir; \((1, 2)\)’nin tersi \((2, 1) \in R\) ve \((2, 1)\)’in tersi \((1, 2) \in R\). Evet.

Ters simetrik: \((1, 2) \in R\) ve \((2, 1) \in R\) olduğu hâlde \(1 \neq 2\). Bu bir karşıt örnektir; hayır.

Geçişli: \((x, y), (y, z) \in R\) olan her üçlüyü denetlemeliyiz. İçinde \((x, x)\) geçen zincirler otomatik sağlanır (örneğin \((1, 1), (1, 2) \to (1, 2)\)). Geriye \((1, 2), (2, 1) \to (1, 1) \in R\) ve \((2, 1), (1, 2) \to (2, 2) \in R\) kalır. Evet.

Sonuç: \(R\) yansımalı, simetrik ve geçişlidir, ters simetrik değildir. Birazdan göreceğimiz dille \(R\) bir denklik bağıntısıdır; \(1\) ile \(2\)’yi “aynı”, \(3\)’ü ayrı bir sınıfa koyar.

\(\blacksquare\)

Örnek 4.4 (Reel Sayılar Üzerinde Üç Bağıntı) \(\mathbb{R}\) üzerinde \(\le\), \(<\) ve “yakınlık” bağıntısı \(x \mathrel{Y} y \Leftrightarrow |x - y| < 1\) için dört özelliği inceleyiniz.

Çözüm

\(\le\) bağıntısı. Yansımalı: her \(x\) için \(x \le x\). Simetrik değil: \(1 \le 2\) ama \(2 \le 1\) değil. Ters simetrik: \(x \le y\) ve \(y \le x\) ise \(x = y\). Geçişli: \(x \le y\) ve \(y \le z\) ise \(x \le z\). (Bu gerçekler Bölüm 7.1’ndaki sıralama aksiyomlarından çıkar; şimdilik bilinen özellikler olarak kullanıyoruz.)

\(<\) bağıntısı. Yansımalı değil: \(1 < 1\) yanlıştır. Simetrik değil: \(1 < 2\) ama \(2 < 1\) değil. Geçişli: \(x < y\) ve \(y < z\) ise \(x < z\). Ters simetrik: burada ince bir nokta var. “\(x < y\) ve \(y < x\)” önermesi hiçbir \(x, y\) çifti için doğru değildir; hipotezi yanlış olan gerektirme doğru olduğundan ters simetriklik koşulu (boşluktan) sağlanır. Evet, \(<\) ters simetriktir.

\(Y\) bağıntısı. Yansımalı: \(|x - x| = 0 < 1\). Simetrik: \(|x - y| = |y - x|\). Ters simetrik değil: \(|0 - 0{,}5| < 1\) ve \(|0{,}5 - 0| < 1\) ama \(0 \neq 0{,}5\). Geçişli değil: \(0 \mathrel{Y} 0{,}7\) ve \(0{,}7 \mathrel{Y} 1{,}4\) (\(|0 - 0{,}7| = 0{,}7 < 1\), \(|0{,}7 - 1{,}4| = 0{,}7 < 1\)) ama \(|0 - 1{,}4| = 1{,}4 \ge 1\), yani \(0 \mathrel{Y} 1{,}4\) değil.

Bağıntı	Yansımalı	Simetrik	Ters simetrik	Geçişli
\(\le\)	evet	hayır	evet	evet
\(<\)	hayır	hayır	evet	evet
\(Y\)	evet	evet	hayır	hayır

\(\blacksquare\)

Yakınlık örneği öğreticidir: “yakın olmak” günlük dilde geçişli gibi görünür ama küçük adımlar birikerek büyük fark yaratır. Analizde \(\varepsilon\)–\(\delta\) argümanlarının dikkat gerektirmesinin bir nedeni de budur.

4.3 Denklik Bağıntıları

“Aynı yaşta olmak”, “aynı takımda oynamak”, “\(3\)’e bölündüğünde aynı kalanı vermek”: bu ilişkilerin ortak yanı, bir kümeyi birbirine karışmayan “aynı türden” gruplara ayırmalarıdır. Bunu sağlayan tam olarak üç özelliktir.

Tanım 4.5 (Denklik Bağıntısı ve Denklik Sınıfı) \(X\) üzerinde bir \(R\) bağıntısı yansımalı, simetrik ve geçişliyse \(R\)’ye bir denklik bağıntısı (equivalence relation) denir. Denklik bağıntıları çoğu zaman \(\sim\) ile gösterilir: \(x \sim y\).

\(R\) bir denklik bağıntısı ve \(x \in X\) olsun. \(x\) ile ilişkili bütün elemanların kümesine \(x\)’in denklik sınıfı (equivalence class) denir:

\[[x] = \{y \in X : x \mathrel{R} y\}.\]

Bütün denklik sınıflarının kümesine \(X\)’in \(R\)’ye göre bölüm kümesi (quotient set) denir ve \(X / R = \{[x] : x \in X\}\) ile gösterilir.

Simetri sayesinde \([x] = \{y \in X : y \mathrel{R} x\}\) de yazılabilir; “\(x\)’in ilişkili olduğu” ile “\(x\) ile ilişkili olan” elemanlar aynıdır. En basit denklik bağıntısı eşitliktir: \(x \sim y \Leftrightarrow x = y\); her sınıf tek elemanlıdır, \([x] = \{x\}\). En kaba denklik bağıntısı \(X \times X\)’tir: herkes herkese denktir ve tek bir sınıf vardır, \([x] = X\). İlginç olanlar bu iki uç arasındadır.

Örnek 4.5 (Üçe Bölümden Kalan) \(\mathbb{Z}\) üzerinde \(x \mathrel{R} y \Leftrightarrow\) “\(x - y\) sayısı \(3\)’e bölünür” bağıntısını tanımlayalım; yani \(x \mathrel{R} y\) demek, \(x - y = 3k\) olacak biçimde bir \(k \in \mathbb{Z}\) bulunması demektir (bölünebilme kavramı Tanım 11.3’de kesin olarak ele alınacak). \(R\)’nin bir denklik bağıntısı olduğunu gösteriniz ve denklik sınıflarını bulunuz.

Çözüm

Yansımalı: her \(x \in \mathbb{Z}\) için \(x - x = 0 = 3 \cdot 0\), yani \(x \mathrel{R} x\).

Simetrik: \(x \mathrel{R} y\) olsun; \(x - y = 3k\) olan bir \(k \in \mathbb{Z}\) vardır. O zaman \(y - x = 3(-k)\) ve \(-k \in \mathbb{Z}\); yani \(y \mathrel{R} x\).

Geçişli: \(x \mathrel{R} y\) ve \(y \mathrel{R} z\) olsun; \(x - y = 3k\) ve \(y - z = 3m\) olan \(k, m \in \mathbb{Z}\) vardır. Taraf tarafa toplayınca \(x - z = 3k + 3m = 3(k + m)\) ve \(k + m \in \mathbb{Z}\); yani \(x \mathrel{R} z\).

Üç özellik sağlandığından \(R\) bir denklik bağıntısıdır.

Sınıflar: \([0] = \{y \in \mathbb{Z} : y = 3k,\ k \in \mathbb{Z}\} = \{\dots, -6, -3, 0, 3, 6, \dots\}\), yani \(3\)’ün katları. \([1] = \{y : y - 1 = 3k\} = \{\dots, -5, -2, 1, 4, 7, \dots\}\), yani \(3\)’e bölündüğünde \(1\) kalanını verenler. \([2] = \{\dots, -4, -1, 2, 5, 8, \dots\}\), yani \(2\) kalanını verenler.

Başka sınıf var mı? Her \(y \in \mathbb{Z}\), \(r \in \{0, 1, 2\}\) olmak üzere \(y = 3q + r\) biçiminde yazılabilir (bölme algoritması, Teorem 12.4). O zaman \(y - r = 3q\), yani \(y \mathrel{R} r\) ve dolayısıyla \(y \in [r]\). Demek ki her tam sayı bu üç sınıftan birindedir. Üç sınıf ikişer ikişer ayrıktır: \(r, s \in \{0, 1, 2\}\) ve \(y \in [r] \cap [s]\) olsa \(y - r = 3k\) ve \(y - s = 3m\) olurdu; çıkarınca \(r - s = 3(m - k)\), yani \(r - s\) sayısı \(3\)’ün bir katı olurdu. Oysa \(|r - s| \le 2\); \(3\)’ün bu aralıktaki tek katı \(0\)’dır, dolayısıyla \(r = s\). Örneğin \([4] = [1]\) ve \([-3] = [0]\)’dır; bir sınıf, elemanlarından herhangi biriyle adlandırılabilir.

Mod 3 denkliği ℤ'yi üç sınıfa böler: 3'e bölündüğünde 0, 1 ve 2 kalanını verenler. Her tam sayı tam olarak bir sınıfa düşer; sınıflar ayrıktır ve birleşimleri ℤ'dir.

Sonuç: \(\mathbb{Z} / R = \{[0], [1], [2]\}\) ve \(\mathbb{Z} = [0] \cup [1] \cup [2]\), birleşim ayrıktır. Bu bağıntıya “mod \(3\) denkliği” denir ve \(x \equiv y \pmod{3}\) yazılır.

\(\blacksquare\)

Örnekte gördüğümüz olgu (sınıfların bütün kümeyi ayrık parçalara bölmesi) rastlantı değildir; her denklik bağıntısı için geçerlidir.

Teorem 4.1 (Denklik Sınıflarının Özellikleri) \(R\), \(X\) üzerinde bir denklik bağıntısı olsun. Her \(x, y \in X\) için

1. \(x \in [x]\); özellikle hiçbir denklik sınıfı boş değildir.
2. \(x \mathrel{R} y \Leftrightarrow [x] = [y]\).
3. Ya \([x] = [y]\) ya da \([x] \cap [y] = \varnothing\); iki denklik sınıfı ya aynıdır ya ayrıktır.
4. \(\displaystyle\bigcup_{x \in X} [x] = X\).

İspat

(1) \(R\) yansımalı olduğundan \(x \mathrel{R} x\), yani tanım gereği \(x \in [x]\).

(2) (\(\Rightarrow\)) \(x \mathrel{R} y\) olsun. Önce \([y] \subseteq [x]\): \(z \in [y]\) alalım, yani \(y \mathrel{R} z\). \(x \mathrel{R} y\) ve \(y \mathrel{R} z\) olduğundan geçişlilikle \(x \mathrel{R} z\), yani \(z \in [x]\). Şimdi \([x] \subseteq [y]\): simetri ile \(y \mathrel{R} x\)’tir; az önceki akıl yürütmeyi \(x\) ile \(y\)’nin rolleri değişmiş olarak tekrarlarsak \([x] \subseteq [y]\) çıkar. İki kapsama \([x] = [y]\) verir.

(\(\Leftarrow\)) \([x] = [y]\) olsun. (1) ile \(y \in [y] = [x]\); tanım gereği \(x \mathrel{R} y\).

(3) \([x] \cap [y] \neq \varnothing\) olsun; ortak bir \(z\) alalım: \(x \mathrel{R} z\) ve \(y \mathrel{R} z\). Simetri ile \(z \mathrel{R} y\); \(x \mathrel{R} z\) ve \(z \mathrel{R} y\)’den geçişlilikle \(x \mathrel{R} y\). (2) gereği \([x] = [y]\). Demek ki kesişim boş değilse sınıflar eşittir; bu da istenen ikilemdir.

(4) Her \([x] \subseteq X\) olduğundan Teorem 3.2 (2) ile birleşim \(X\)’in içindedir. Tersine \(x \in X\) ise (1) ile \(x \in [x]\) ve dolayısıyla \(x\) birleşimdedir.

\(\blacksquare\)

Bu teoremin söylediği şeyin bir adı vardır.

Tanım 4.6 (Bölüntü) \(X\) boş olmayan bir küme olsun. \(X\)’in boş olmayan alt kümelerinden oluşan bir \(\mathcal{B}\) topluluğu,

1. \(\mathcal{B}\)’deki farklı iki küme ayrıksa ve
2. \(\mathcal{B}\)’deki kümelerin birleşimi \(X\) ise

\(X\)’in bir bölüntüsü (partition) diye adlandırılır. \(\mathcal{B}\)’nin elemanlarına bölüntünün parçaları denir.

Sonuç 4.1 (Denklik Bağıntısı Bölüntü Verir) \(R\), \(X\) üzerinde bir denklik bağıntısıysa bölüm kümesi \(X / R\), \(X\)’in bir bölüntüsüdür.

İspat

Teorem 4.1’nın (1) maddesi sınıfların boş olmadığını, (3) maddesi farklı sınıfların ayrık olduğunu, (4) maddesi birleşimlerinin \(X\) olduğunu söyler; bunlar tam olarak bölüntü tanımındaki koşullardır.

\(\blacksquare\)

Karşıt yön de doğrudur: her bölüntü bir denklik bağıntısından gelir.

Önerme 4.2 (Bölüntü Denklik Bağıntısı Verir) \(\mathcal{B}\), \(X\)’in bir bölüntüsü olsun. \(x \mathrel{R} y \Leftrightarrow\) “\(x\) ile \(y\) aynı parçadadır” biçiminde tanımlanan \(R\), \(X\) üzerinde bir denklik bağıntısıdır ve denklik sınıfları tam olarak \(\mathcal{B}\)’nin parçalarıdır.

İspat

Her \(x \in X\) bir parçadadır (birleşim \(X\)’tir) ve yalnız bir parçadadır (parçalar ayrıktır); \(x\)’i içeren parçaya \(P_x\) diyelim. O zaman \(x \mathrel{R} y \Leftrightarrow P_x = P_y\)’dir.

Yansımalı: \(P_x = P_x\). Simetrik: \(P_x = P_y\) ise \(P_y = P_x\). Geçişli: \(P_x = P_y\) ve \(P_y = P_z\) ise \(P_x = P_z\). Demek ki \(R\) bir denklik bağıntısıdır; eşitliğin özelliklerini devralmıştır.

\(x\)’in sınıfı \([x] = \{y : P_y = P_x\}\)’tir. \(y \in P_x\) ise \(y\)’nin bulunduğu tek parça \(P_x\) olduğundan \(P_y = P_x\), yani \(y \in [x]\); tersine \(y \in [x]\) ise \(y \in P_y = P_x\). Böylece \([x] = P_x\).

\(\blacksquare\)

Denklik bağıntısı ile bölüntü, aynı şeyin iki dilidir: “hangi elemanlar birbirine denk” demekle “küme hangi parçalara ayrılıyor” demek aynı bilgiyi taşır.

Örnek 4.6 (Kareleri Eşit Sayılar) \(\mathbb{R}\) üzerinde \(x \sim y \Leftrightarrow x^2 = y^2\) bağıntısının bir denklik bağıntısı olduğunu gösteriniz ve sınıflarını bulunuz.

Çözüm

Yansımalı: \(x^2 = x^2\). Simetrik: \(x^2 = y^2\) ise \(y^2 = x^2\). Geçişli: \(x^2 = y^2\) ve \(y^2 = z^2\) ise \(x^2 = z^2\). Üç özellik de sayıların eşitliğinden devralınır; \(\sim\) bir denklik bağıntısıdır.

\(x \in \mathbb{R}\) için \([x] = \{y \in \mathbb{R} : y^2 = x^2\}\). \(y^2 = x^2\) eşitliği \(y^2 - x^2 = (y - x)(y + x) = 0\)’a denktir; bir çarpım sıfırsa çarpanlardan biri sıfırdır (Önerme 6.13), dolayısıyla \(y = x\) ya da \(y = -x\). Böylece

\[[x] = \{x, -x\}, \qquad \text{özel olarak} \qquad [0] = \{0\}.\]

Sınıflar: \(\{0\}\) ve her \(a > 0\) için \(\{a, -a\}\) çiftleri. Bölüm kümesi \(\mathbb{R} / {\sim}\), negatif olmayan reel sayılarla birebir eşleşir: her sınıf, negatif olmayan tek temsilcisi \(|x|\) ile adlandırılabilir.

\(\blacksquare\)

4.4 Sıralama Bağıntıları

Denklik bağıntısı “aynı” olmayı yakalar; sıralama bağıntısı ise “önce gelmeyi”. Sayılardaki \(\le\)’yi örnek alırsak, yansımalıdır, ters simetriktir (iki yönlü \(\le\) eşitlik demektir) ve geçişlidir. Bu üç özelliği soyutlarız.

Tanım 4.7 (Kısmi Sıralama ve Tam Sıralama) \(X\) üzerinde bir \(R\) bağıntısı yansımalı, ters simetrik ve geçişliyse \(R\)’ye \(X\) üzerinde bir kısmi sıralama bağıntısı (partial order) denir; \((X, R)\) ikilisine kısmen sıralı küme denir. Kısmi sıralamalar çoğu zaman \(\preceq\) ile gösterilir.

\(x \preceq y\) ya da \(y \preceq x\) oluyorsa \(x\) ile \(y\)’ye karşılaştırılabilir (comparable) denir. Bir kısmi sıralama, \(X\)’in her \(x, y\) çifti karşılaştırılabilir oluyorsa, yani

\[\forall x, y \in X,\ x \preceq y \ \text{ veya } \ y \preceq x\]

sağlanıyorsa, tam sıralama (total order, linear order) diye adlandırılır; \((X, \preceq)\) o zaman tam sıralı kümedir.

“Kısmi” sözü, bazı çiftlerin karşılaştırılamayabileceğini vurgular; tam sıralamada herkes herkesle karşılaştırılır.

• \(\mathbb{Z}\), \(\mathbb{Q}\) ve \(\mathbb{R}\) üzerindeki \(\le\) bağıntısı tam sıralamanın temel örneğidir: Örnek 4.4’nde üç özelliği gördük; karşılaştırılabilirlik ise her \(a, b\) için \(a \le b\) ya da \(b \le a\) olmasıdır (üçlem yasası, Bölüm 7.1).
• Sözlük sıralaması (alfabetik sıra) sözcükler kümesi üzerinde bir tam sıralamadır: farklı iki sözcükten biri sözlükte ötekinden önce gelir.

NotKesin sıralama

\(<\) bağıntısı yansımalı olmadığından tanımımıza göre kısmi sıralama değildir; ona kesin sıralama (strict order) denir. İkisi birbirinden türetilir: \(x < y \Leftrightarrow (x \preceq y \text{ ve } x \neq y)\) ve \(x \preceq y \Leftrightarrow (x < y \text{ veya } x = y)\). Hangisiyle çalışıldığı bağlamdan anlaşılır.

Örnek 4.7 (Alt Küme Bağıntısı Kısmi Sıralamadır) \(X\) bir küme olsun. \(\mathcal{P}(X)\) üzerinde alt küme bağıntısı \(\subseteq\)’nin bir kısmi sıralama olduğunu, \(X\)’in en az iki elemanı varsa tam sıralama olmadığını gösteriniz.

Çözüm

Yansımalı: her \(A \subseteq X\) için \(A \subseteq A\) (Önerme 3.1). Ters simetrik: \(A \subseteq B\) ve \(B \subseteq A\) ise Tanım 3.1’deki eşitlik tanımı gereği \(A = B\). Geçişli: \(A \subseteq B\) ve \(B \subseteq C\) ise \(A \subseteq C\) (Önerme 3.1). Demek ki \((\mathcal{P}(X), \subseteq)\) kısmen sıralı bir kümedir.

\(X\)’te \(a \neq b\) iki eleman olsun. \(\{a\} \subseteq \{b\}\) yanlıştır (\(a \notin \{b\}\)) ve \(\{b\} \subseteq \{a\}\) yanlıştır (\(b \notin \{a\}\)). \(\{a\}\) ile \(\{b\}\) karşılaştırılamaz; sıralama tam değildir.

\(\blacksquare\)

Örnek 4.8 (Bölünebilirlik Kısmi Sıralamadır) \(\mathbb{N}\) üzerinde \(a \mid b \Leftrightarrow\) “\(b = ak\) olacak biçimde bir \(k \in \mathbb{N}\) vardır” bağıntısının bir kısmi sıralama olduğunu, ama tam sıralama olmadığını gösteriniz.

Çözüm

Yansımalı: \(a = a \cdot 1\) olduğundan \(a \mid a\).

Ters simetrik: \(a \mid b\) ve \(b \mid a\) olsun; \(b = ak\) ve \(a = bm\) olan \(k, m \in \mathbb{N}\) vardır. Birincisini ikincisine koyunca \(a = akm\), \(a \neq 0\) ile sadeleştirince \(km = 1\) çıkar. \(k, m \ge 1\) doğal sayılardır; \(k \ge 2\) olsaydı \(km \ge 2m \ge 2\) olurdu. Demek ki \(k = 1\) ve benzer biçimde \(m = 1\); dolayısıyla \(b = a\).

Geçişli: \(a \mid b\) ve \(b \mid c\) olsun; \(b = ak\) ve \(c = bm\). O zaman \(c = (ak)m = a(km)\) ve \(km \in \mathbb{N}\); yani \(a \mid c\).

Tam değil: \(3\) ile \(5\)’i ele alalım. \(3 \mid 5\) olsaydı \(5 = 3k\) olan bir \(k \in \mathbb{N}\) olurdu; \(k = 1\) için \(3\), \(k \ge 2\) için \(3k \ge 6\) elde edilir, hiçbiri \(5\) değildir. Aynı biçimde \(5 \mid 3\) de yanlıştır (\(5k \ge 5 > 3\)). Demek ki \(3\) ile \(5\) karşılaştırılamaz.

\(\blacksquare\)

Bölünebilirlik, “sıralama” sözcüğünün sayı doğrusundaki resimden ne kadar uzaklaşabileceğini gösterir: \(1\) herkesin altındadır ama \(3\) ile \(5\) yan yana durur, ne biri ötekinden önce gelir.

Kısmen sıralı kümelerde “en küçük eleman”, “üst sınır”, “en küçük üst sınır” gibi kavramlar tanımlanabilir. Bu kitapta bunları \((\mathbb{R}, \le)\) için ayrıntılı inceleyeceğiz; reel sayıların en önemli özelliği olan tamlık tam da bu dille söylenir: Üst Sınır, Supremum ve Tamlık Aksiyomu.

4.5 Alıştırmalar

Alıştırma 4.1 (Bağıntı Alıştırmaları)  

1. \(X = \{1, 2, 3, 4\}\) üzerinde \(R = \{(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (1, 3), (1, 4)\}\) bağıntısının dört özelliğini belirleyiniz. \(R\) bir kısmi sıralama mıdır, tam sıralama mıdır?

2. \(\mathbb{Z}\) üzerinde \(x \mathrel{R} y \Leftrightarrow x + y\) çift bağıntısının bir denklik bağıntısı olduğunu gösteriniz ve sınıflarını bulunuz.

3. \(\mathbb{R}^2\) üzerinde \((a, b) \sim (c, d) \Leftrightarrow a = c\) bağıntısının bir denklik bağıntısı olduğunu gösteriniz; \((a, b)\)’nin sınıfını geometrik olarak betimleyiniz.

4. Bölünebilirlik bağıntısı \(\mathbb{Z}\) üzerinde (\(k \in \mathbb{Z}\) alınarak) tanımlanırsa ters simetrik olmadığını gösteriniz.

5. \(\mathbb{N} \times \mathbb{N}\) üzerinde \((a, b) \preceq (c, d) \Leftrightarrow a \le c \text{ ve } b \le d\) bağıntısının bir kısmi sıralama olduğunu, ama tam sıralama olmadığını gösteriniz.

Çözüm

a) Yansımalı: \((1,1), (2,2), (3,3), (4,4)\) hepsi \(R\)’dedir; evet. Simetrik değil: \((1, 2) \in R\) ama \((2, 1) \notin R\). Ters simetrik: \(R\)’de hem \((x, y)\) hem \((y, x)\) bulunan çiftler yalnız \(x = y\) olanlardır (köşegen dışındaki \((1,2), (2,3), (1,3), (1,4)\)’ün tersleri \(R\)’de yoktur); evet. Geçişli: köşegen çiftleri içeren zincirler otomatik sağlanır; geriye \((1, 2), (2, 3) \to (1, 3) \in R\) kalır, başka zincir yoktur (\((2,3)\)’ten sonra yalnız \((3,3)\), \((1,3)\) ve \((1,4)\)’ten sonra yalnız köşegen gelir). Evet.

Yansımalı, ters simetrik ve geçişli olduğundan \(R\) bir kısmi sıralamadır. Tam değildir: \((2, 4) \notin R\) ve \((4, 2) \notin R\), yani \(2\) ile \(4\) karşılaştırılamaz (aynı biçimde \(3\) ile \(4\)).

b) Yansımalı: \(x + x = 2x\) çifttir. Simetrik: \(x + y = y + x\). Geçişli: \(x + y = 2k\) ve \(y + z = 2m\) olsun (\(k, m \in \mathbb{Z}\)). Taraf tarafa toplayıp \(2y\) çıkarınca \(x + z = 2k + 2m - 2y = 2(k + m - y)\), çift; yani \(x \mathrel{R} z\). \(R\) bir denklik bağıntısıdır.

Sınıflar: \([0] = \{y : y \text{ çift}\}\), çünkü \(0 + y = y\). \([1] = \{y : 1 + y \text{ çift}\} = \{y : y \text{ tek}\}\). Her tam sayı ya çift ya tek olduğundan \(\mathbb{Z} = [0] \cup [1]\) ve başka sınıf yoktur. Bu, mod \(2\) denkliğidir: \(x + y\)’nin çift olması, \(x - y = (x + y) - 2y\)’nin çift olmasına denktir.

c) Yansımalı: \(a = a\). Simetrik: \(a = c\) ise \(c = a\). Geçişli: \(a = c\) ve \(c = e\) ise \(a = e\). Özellikler, birinci bileşenlerin eşitliğinden devralınır. \((a, b)\)’nin sınıfı

\[[(a, b)] = \{(c, d) \in \mathbb{R}^2 : c = a\} = \{(a, d) : d \in \mathbb{R}\},\]

yani \(x = a\) düşey doğrusudur. Bölüm kümesi, düzlemdeki bütün düşey doğruların kümesidir; her doğru \(x\)-eksenini kestiği \(a\) noktasıyla adlandırılabilir, dolayısıyla bölüm kümesi \(\mathbb{R}\) ile birebir eşleşir.

d) \(\mathbb{Z}\) üzerinde \(a \mid b \Leftrightarrow b = ak\) olacak biçimde bir \(k \in \mathbb{Z}\) vardır. \(-2 = 2 \cdot (-1)\) olduğundan \(2 \mid -2\); \(2 = (-2) \cdot (-1)\) olduğundan \(-2 \mid 2\). Ama \(2 \neq -2\). Bu karşıt örnek ters simetrikliği bozar. (Yansımalılık ve geçişlilik hâlâ geçerlidir; yansımalı ve geçişli olan bağıntılara ön sıralama (preorder) denir.) \(\mathbb{N}\)’de sorun çıkmamasının nedeni, orada \(km = 1\) denkleminin tek çözümünün \(k = m = 1\) olmasıdır; \(\mathbb{Z}\)’de \(k = m = -1\) de çözümdür.

e) Yansımalı: \(a \le a\) ve \(b \le b\) olduğundan \((a, b) \preceq (a, b)\). Ters simetrik: \((a, b) \preceq (c, d)\) ve \((c, d) \preceq (a, b)\) ise \(a \le c\), \(c \le a\), \(b \le d\), \(d \le b\); \(\le\)’nin ters simetrikliğiyle \(a = c\) ve \(b = d\), yani \((a, b) = (c, d)\). Geçişli: \((a, b) \preceq (c, d)\) ve \((c, d) \preceq (e, f)\) ise \(a \le c \le e\) ve \(b \le d \le f\); \(\le\)’nin geçişliliğiyle \(a \le e\) ve \(b \le f\), yani \((a, b) \preceq (e, f)\). Her özellik bileşen bileşen \(\le\)’den gelir; \(\preceq\) bir kısmi sıralamadır.

Tam değil: \((1, 2)\) ile \((2, 1)\)’i ele alalım. \((1, 2) \preceq (2, 1)\) için \(2 \le 1\) gerekirdi; yanlış. \((2, 1) \preceq (1, 2)\) için \(2 \le 1\) gerekirdi; yine yanlış. İki ikili karşılaştırılamaz. (Düzlemde \((a, b) \preceq (c, d)\), “\((c, d)\) noktası \((a, b)\)’nin sağ üst çeyreğindedir” demektir; sol üst ya da sağ alt çeyrekteki noktalar karşılaştırılamaz.)

\(\blacksquare\)

Bağıntıların en özel türü, her elemanı tam olarak bir elemanla eşleyenlerdir; bunlara fonksiyon diyoruz: Fonksiyonlar.