14 Sonlu, Sonsuz ve Sayılabilir Kümeler
Önceki bölümde rasyonel sayıların da irrasyonel sayıların da sayı doğrusunda yoğun olduğunu gördük: her aralıkta ikisinden de sonsuz çoklukta eleman var. Peki bu iki sonsuz kümeden hangisi “daha kalabalık”? Sonlu kümelerde bu soruyu elemanları sayarak yanıtlarız; sonsuz kümelerde “kaç eleman var” sorusunun anlamı bile açık değildir. Georg Cantor 1874’te bu soruya kesin bir anlam kazandırdı ve şaşırtıcı bir yanıt buldu: doğal sayılar, tam sayılar ve rasyonel sayılar “aynı büyüklükte”dir; reel sayılar ise bunlardan kesinlikle daha büyüktür.
Bu bölümde önce iki kümenin ne zaman “aynı büyüklükte” sayılacağını tanımlayacak, sonra sonlu, sonsuz ve sayılabilir kümeleri inceleyecek, en sonunda Cantor’un teoremini ispatlayacağız.
14.1 Eşgüçlü Kümeler
Bir salondaki sandalyelerle öğrencileri karşılaştırmak için ikisini de saymak gerekmez: herkes bir sandalyeye otursun. Boş sandalye kalmamış ve ayakta kimse yoksa sandalye sayısı öğrenci sayısına eşittir. “Saymadan karşılaştırma”nın bu yolu, yani her elemanı öbür kümenin tam bir elemanıyla eşlemek, sonsuz kümelere de uygulanabilir. Matematikte bu eşleme birebir-örten fonksiyondur.
Tanım 14.1 (Eşgüçlü Kümeler) \(A\) ve \(B\) iki küme olsun. \(A\)’dan \(B\)’ye birebir-örten (bijektif) bir \(f\colon A \to B\) fonksiyonu varsa (bkz. Tanım 5.7) \(A\) ile \(B\) eşgüçlüdür (equinumerous) denir ve
\[A \sim B\]
yazılır. Boş küme yalnızca boş kümeyle eşgüçlüdür: boş olmayan bir kümeden boş kümeye hiç fonksiyon yoktur, boş kümeden boş olmayan bir kümeye giden tek fonksiyon (boş fonksiyon) ise örten değildir.
Eşgüçlülük, “kümelerin büyüklüğünü karşılaştırma” bağıntısıdır ve bir denklik bağıntısının üç özelliğini taşır.
Önerme 14.1 (Eşgüçlülüğün Özellikleri) \(A\), \(B\), \(C\) kümeleri için şunlar sağlanır:
- \(A \sim A\).
- \(A \sim B\) ise \(B \sim A\).
- \(A \sim B\) ve \(B \sim C\) ise \(A \sim C\).
İspat
(1) Birim fonksiyon \(I_A\colon A \to A\), \(I_A(x) = x\) birebir-örtendir.
(2) \(f\colon A \to B\) birebir-örten olsun. Teorem 5.5 gereği \(f\)’nin tersi \(f^{-1}\colon B \to A\) vardır; \(f^{-1}\)’in tersi de \(f\) olduğundan aynı teoremle \(f^{-1}\) birebir-örtendir. Dolayısıyla \(B \sim A\).
(3) \(f\colon A \to B\) ve \(g\colon B \to C\) birebir-örten olsun. Teorem 5.4 gereği birebir fonksiyonların bileşkesi birebir, örten fonksiyonların bileşkesi örtendir; o hâlde \(g \circ f\colon A \to C\) birebir-örtendir ve \(A \sim C\).
\(\blacksquare\)
Bu özellikler sayesinde eşgüçlülük zincirleme kullanılır: \(A \sim \mathbb{N}\) olduğunu göstermek için doğrudan bir eşleme bulmak yerine \(A \sim B\) ve \(B \sim \mathbb{N}\) göstermek yeter. Şimdi ilk şaşırtıcı örneğe bakalım.
Örnek 14.1 (Doğal Sayılar ve Çift Sayılar) \(2\mathbb{N} = \{2n : n \in \mathbb{N}\} = \{2, 4, 6, \dots\}\) çift doğal sayılar kümesi olsun. \(2\mathbb{N}\), \(\mathbb{N}\)’nin öz alt kümesi olduğu hâlde \(\mathbb{N} \sim 2\mathbb{N}\) olduğunu gösteriniz. Ayrıca \(\mathbb{N} \sim \mathbb{N} \setminus \{1\}\) olduğunu gösteriniz.
Çözüm
\(f\colon \mathbb{N} \to 2\mathbb{N}\), \(f(n) = 2n\) alalım. \(f(n) = f(m)\) ise \(2n = 2m\), sadeleştirme ile (Önerme 6.3) \(n = m\) olur; \(f\) birebirdir. Her çift doğal sayı tanım gereği bir \(n \in \mathbb{N}\) için \(2n\) biçimindedir, yani \(f(n)\)’dir; \(f\) örtendir. O hâlde \(\mathbb{N} \sim 2\mathbb{N}\).
İkinci iddia için \(g\colon \mathbb{N} \to \mathbb{N} \setminus \{1\}\), \(g(n) = n + 1\) alalım. \(n + 1 = m + 1\) ise \(n = m\); \(g\) birebirdir. \(k \in \mathbb{N} \setminus \{1\}\) ise Önerme 9.3 (2) gereği \(k - 1 \in \mathbb{N}\)’dir ve \(g(k - 1) = k\); \(g\) örtendir.
\(\blacksquare\)
Bu örnek Galileo’nun 1638’de dikkat çektiği “paradoks”tur: çift sayılar doğal sayıların “yarısı” gibi görünür, ama ikisi eşgüçlüdür. Sonlu kümelerde bir parça bütünle eşgüçlü olamaz; sonsuz kümelerde olabilir. Bunun sonsuzluğun tam da ayırt edici özelliği olduğunu birazdan göreceğiz.
Örnek 14.2 (Aralıklar ve Reel Sayılar Eşgüçlüdür)
\(a < b\) ve \(c < d\) ise \((a, b) \sim (c, d)\) olduğunu gösteriniz.
\((-1, 1) \sim \mathbb{R}\) olduğunu gösteriniz. Buradan her açık aralığın \(\mathbb{R}\) ile eşgüçlü olduğu sonucunu çıkarınız.
Çözüm
a) \(f\colon (a, b) \to (c, d)\) fonksiyonunu
\[f(x) = c + (d - c)\,\frac{x - a}{b - a}\]
ile tanımlayalım. \(x \in (a, b)\) ise \(0 < \dfrac{x - a}{b - a} < 1\), dolayısıyla \(c < f(x) < d\); \(f\) gerçekten \((c, d)\)’ye gider. \(d - c > 0\) ve \(b - a > 0\) olduğundan \(x < y\) iken \(f(x) < f(y)\) olur: \(f\) kesin artandır, dolayısıyla birebirdir. Örtenlik: \(y \in (c, d)\) verilsin,
\[x = a + (b - a)\,\frac{y - c}{d - c}\]
alalım. \(0 < \dfrac{y - c}{d - c} < 1\) olduğundan \(x \in (a, b)\)’dir ve yerine koyunca \(f(x) = y\) bulunur.
b) \(g\colon (-1, 1) \to \mathbb{R}\), \(g(x) = \dfrac{x}{1 - |x|}\) olsun; \(|x| < 1\) olduğundan payda pozitiftir. Tersini bulmak için \(h\colon \mathbb{R} \to (-1, 1)\), \(h(y) = \dfrac{y}{1 + |y|}\) tanımlayalım; \(|h(y)| = \dfrac{|y|}{1 + |y|} < 1\) olduğundan \(h\) gerçekten \((-1, 1)\)’e gider. Şimdi iki bileşkeyi hesaplayalım. \(|h(y)| = \dfrac{|y|}{1 + |y|}\) ve \(1 - |h(y)| = \dfrac{1}{1 + |y|}\) olduğundan
\[g(h(y)) = \frac{y/(1 + |y|)}{1/(1 + |y|)} = y \qquad (y \in \mathbb{R})\]
Benzer biçimde \(|g(x)| = \dfrac{|x|}{1 - |x|}\) ve \(1 + |g(x)| = \dfrac{1}{1 - |x|}\) olduğundan
\[h(g(x)) = \frac{x}{1 - |x|}\,(1 - |x|) = x \qquad (x \in (-1, 1))\]
Demek ki \(h \circ g = I_{(-1,1)}\) ve \(g \circ h = I_{\mathbb{R}}\); yani \(h\), \(g\)’nin ters fonksiyonudur. Teorem 5.5 gereği ters fonksiyonu olan \(g\) birebir-örtendir: \((-1, 1) \sim \mathbb{R}\).
Son olarak herhangi bir \((a, b)\) açık aralığı için (a) şıkkından \((a, b) \sim (-1, 1)\), (b) şıkkından \((-1, 1) \sim \mathbb{R}\); Önerme 14.1 ile \((a, b) \sim \mathbb{R}\).
\(\blacksquare\)
Uzunluğu ne kadar küçük olursa olsun her açık aralık, bütün sayı doğrusuyla eşgüçlüdür. “Büyüklük” kavramımız uzunlukla ilgili değildir; yalnızca eşlemeyle ilgilidir.
14.2 Sonlu ve Sonsuz Kümeler
Her \(n \in \mathbb{N}\) için
\[\mathbb{N}_n = \{1, 2, \dots, n\} = \{k \in \mathbb{N} : k \le n\}\]
yazalım. “Bir kümenin \(n\) elemanı var” demek, elemanlarını \(1\)’den \(n\)’ye kadar numaralayabilmek, yani kümeyi \(\mathbb{N}_n\) ile eşleyebilmek demektir. Ancak bu tanımın anlamlı olması için aynı kümenin hem \(\mathbb{N}_n\) hem de \(\mathbb{N}_m\) (\(m \ne n\)) ile eşgüçlü olamayacağını bilmemiz gerekir. Bunu garanti eden ilke, günlük dildeki adıyla “güvercin yuvası ilkesi”dir: \(n\) yuvaya \(n\)’den çok güvercin ancak en az bir yuvaya iki güvercin koyarak yerleştirilebilir.
Lemma 14.1 (Güvercin Yuvası İlkesi) \(m, n \in \mathbb{N}\) olsun. \(\mathbb{N}_m\)’den \(\mathbb{N}_n\)’ye birebir bir fonksiyon varsa \(m \le n\)’dir. Başka bir deyişle \(m > n\) ise \(\mathbb{N}_m\)’den \(\mathbb{N}_n\)’ye hiçbir fonksiyon birebir olamaz.
İspat
\(n\) üzerinden tümevarımla (Teorem 9.1) şu önermeyi ispatlayacağız: “Her \(m \in \mathbb{N}\) ve her birebir \(f\colon \mathbb{N}_m \to \mathbb{N}_n\) için \(m \le n\).”
Başlangıç (\(n = 1\)): \(f\colon \mathbb{N}_m \to \{1\}\) birebir olsun. \(m \ge 2\) olsaydı \(f(1) = f(2) = 1\) olurdu; oysa \(1 \ne 2\), bu birebirlikle çelişir. O hâlde \(m = 1 \le 1\).
Tümevarım adımı: Önerme \(n\) için doğru olsun; \(f\colon \mathbb{N}_m \to \mathbb{N}_{n+1}\) birebir olsun. \(m = 1\) ise \(m \le n + 1\) zaten sağlanır. \(m \ge 2\) olsun. Amacımız birebir bir \(g\colon \mathbb{N}_{m-1} \to \mathbb{N}_n\) kurmaktır; çünkü o zaman tümevarım varsayımı \(m - 1 \le n\), yani \(m \le n + 1\) verir. İki durum vardır.
\(n + 1\) değeri \(f(1), \dots, f(m-1)\) arasında yoksa: \(g = f|_{\mathbb{N}_{m-1}}\) alalım. Değerleri \(\mathbb{N}_{n+1} \setminus \{n+1\} = \mathbb{N}_n\) içindedir ve birebir fonksiyonun kısıtlaması birebirdir.
Bir \(j \le m - 1\) için \(f(j) = n + 1\) ise: \(f\) birebir olduğundan böyle bir \(j\) tektir ve \(f(m) \ne n + 1\)’dir (\(m \ne j\)). \(g\colon \mathbb{N}_{m-1} \to \mathbb{N}_n\) fonksiyonunu
\[g(i) = \begin{cases} f(i), & i \ne j \\ f(m), & i = j \end{cases}\]
ile tanımlayalım. \(i \ne j\) için \(f(i) \ne n + 1\) ve \(f(m) \ne n + 1\) olduğundan \(g\)’nin bütün değerleri \(\mathbb{N}_n\) içindedir. Birebirlik: \(i \ne i'\) olsun. İkisi de \(j\)’den farklıysa \(g(i) = f(i) \ne f(i') = g(i')\). Biri, diyelim \(i = j\) ise \(g(j) = f(m)\) ve \(g(i') = f(i')\); \(i' \le m - 1 < m\) olduğundan \(f(i') \ne f(m)\). Her durumda \(g(i) \ne g(i')\).
Her iki durumda da birebir \(g\colon \mathbb{N}_{m-1} \to \mathbb{N}_n\) bulundu; tümevarım varsayımıyla \(m - 1 \le n\), dolayısıyla \(m \le n + 1\). Tümevarım ilkesiyle önerme her \(n\) için doğrudur.
\(\blacksquare\)
Artık “eleman sayısı” kavramını güvenle tanımlayabiliriz.
Tanım 14.2 (Sonlu ve Sonsuz Kümeler) Bir \(A\) kümesi, \(A = \varnothing\) ise ya da bir \(n \in \mathbb{N}\) için \(A \sim \mathbb{N}_n\) ise sonlu (finite) kümedir. \(A \sim \mathbb{N}_n\) durumunda “\(A\)’nın \(n\) elemanı vardır” denir ve \(|A| = n\) yazılır; ayrıca \(|\varnothing| = 0\) alınır. Sonlu olmayan kümeye sonsuz (infinite) küme denir.
Sonuç 14.1 (Eleman Sayısı Tektir) \(m, n \in \mathbb{N}\) için \(\mathbb{N}_m \sim \mathbb{N}_n\) ise \(m = n\)’dir. Dolayısıyla sonlu bir kümenin eleman sayısı \(|A|\) iyi tanımlıdır.
İspat
\(f\colon \mathbb{N}_m \to \mathbb{N}_n\) birebir-örten olsun. \(f\) birebir olduğundan Lemma 14.1 ile \(m \le n\); \(f^{-1}\colon \mathbb{N}_n \to \mathbb{N}_m\) de birebir olduğundan (Teorem 5.5) \(n \le m\). O hâlde \(m = n\). \(A \sim \mathbb{N}_m\) ve \(A \sim \mathbb{N}_n\) ise Önerme 14.1 ile \(\mathbb{N}_m \sim \mathbb{N}_n\), yani \(m = n\) olur; eleman sayısı tektir.
\(\blacksquare\)
Sonuç 14.2 (Doğal Sayılar Kümesi Sonsuzdur) \(\mathbb{N}\) sonsuz bir kümedir.
İspat
\(\mathbb{N} \ne \varnothing\) açıktır. Bir \(n \in \mathbb{N}\) için \(f\colon \mathbb{N} \to \mathbb{N}_n\) birebir-örten olsaydı, \(\mathbb{N}_{n+1} \subseteq \mathbb{N}\) olduğundan kısıtlama \(f|_{\mathbb{N}_{n+1}}\colon \mathbb{N}_{n+1} \to \mathbb{N}_n\) birebir olurdu. Lemma 14.1 bu durumda \(n + 1 \le n\) verir; çelişki.
\(\blacksquare\)
Sonlu kümelerin en temel özelliği, alt kümelerinin de sonlu ve daha küçük olmasıdır.
Önerme 14.2 (Sonlu Kümenin Alt Kümesi Sonludur) \(A\) sonlu bir küme ve \(B \subseteq A\) olsun. O zaman \(B\) sonludur ve \(|B| \le |A|\)’dır. Karşıt tersiyle: sonsuz bir kümeyi kapsayan her küme sonsuzdur.
İspat
Adım 1: \(\mathbb{N}_n\)’nin her alt kümesi sonludur. \(n\) üzerinden tümevarım yapalım. \(n = 1\) için \(B \subseteq \{1\}\) ya \(\varnothing\) ya da \(\{1\} = \mathbb{N}_1\)’dir; ikisi de sonludur. Önerme \(n\) için doğru olsun ve \(B \subseteq \mathbb{N}_{n+1}\) alalım. \(n + 1 \notin B\) ise \(B \subseteq \mathbb{N}_n\)’dir ve varsayımla sonludur. \(n + 1 \in B\) ise \(B' = B \setminus \{n+1\} \subseteq \mathbb{N}_n\) sonludur. \(B' = \varnothing\) ise \(B = \{n+1\} \sim \mathbb{N}_1\). Değilse bir \(k\) için birebir-örten \(g\colon B' \to \mathbb{N}_k\) vardır; \(\tilde g\colon B \to \mathbb{N}_{k+1}\) fonksiyonunu \(B'\) üzerinde \(g\) ile, \(\tilde g(n+1) = k + 1\) ile tanımlayalım. \(g\), \(B'\)’yü \(\mathbb{N}_k\)’ye birebir-örten götürür ve yeni eleman \(n+1\) yeni değer \(k+1\)’e gider; dolayısıyla \(\tilde g\) birebir-örtendir ve \(B \sim \mathbb{N}_{k+1}\) sonludur.
Adım 2: Genel durum. \(A = \varnothing\) ise \(B = \varnothing\) sonludur. \(A \sim \mathbb{N}_n\) olsun, \(f\colon A \to \mathbb{N}_n\) birebir-örten olsun. \(f(B) \subseteq \mathbb{N}_n\) Adım 1 gereği sonludur. Kısıtlama \(f|_B\colon B \to f(B)\) birebirdir (birebir fonksiyonun kısıtlaması) ve görüntüsü üzerine örtendir; yani \(B \sim f(B)\). \(f(B)\) sonlu olduğundan \(B\) de sonludur.
Adım 3: \(|B| \le |A|\). \(B = \varnothing\) ise açık. \(B \sim \mathbb{N}_k\) ve \(A \sim \mathbb{N}_n\) olsun; \(\varphi\colon \mathbb{N}_k \to B\) ve \(f\colon A \to \mathbb{N}_n\) birebir-örten olsun. \(\mathbb{N}_k \xrightarrow{\varphi} B \subseteq A \xrightarrow{f} \mathbb{N}_n\) bileşkesi birebirdir; Lemma 14.1 ile \(k \le n\).
\(\blacksquare\)
Bu önerme sayesinde \(\mathbb{N}\)’yi kapsayan \(\mathbb{Z}\), \(\mathbb{Q}\) ve \(\mathbb{R}\) kümelerinin sonsuz olduğunu hemen söyleyebiliriz (Sonuç 14.2).
14.3 Sayılabilir Kümeler
Sonsuz kümeler arasında en “evcil” olanlar, elemanları bir dizi hâlinde \(a_1, a_2, a_3, \dots\) diye yazılabilenlerdir: her elemana bir sıra numarası verilebilir, hiçbir eleman atlanmaz. Bu tam olarak \(\mathbb{N}\) ile eşgüçlü olmak demektir.
Tanım 14.3 (Sayılabilir ve Sayılamaz Kümeler) \(A\) bir küme olsun.
- \(A \sim \mathbb{N}\) ise \(A\)’ya sayılabilir sonsuz (countably infinite) küme denir.
- \(A\) sonlu ya da sayılabilir sonsuz ise \(A\)’ya sayılabilir (countable) küme denir.
- Sayılabilir olmayan kümeye sayılamaz (uncountable) küme denir.
\(A\) sayılabilir sonsuz ve \(f\colon \mathbb{N} \to A\) birebir-örten ise \(a_n = f(n)\) yazarak \(A = \{a_1, a_2, a_3, \dots\}\) elde ederiz; burada \(a_n\)’ler birbirinden farklıdır ve \(A\)’nın her elemanı listede tam bir kez görünür. “Sayılabilir” sözcüğü buradan gelir: kümenin elemanları “sayılarak” bitirilemez ama “sayılmaya başlanabilir” ve her elemana sıra gelir.
Bazı kitaplar “sayılabilir” sözcüğünü yalnızca \(\mathbb{N}\) ile eşgüçlü kümeler için kullanır ve bizim “sayılabilir” dediğimize “en çok sayılabilir” (at most countable) der. Bu notlarda sonlu kümeler de sayılabilirdir; \(\mathbb{N}\) ile eşgüçlü olanları ayırt etmek istediğimizde açıkça “sayılabilir sonsuz” diyeceğiz.
İlk teoremimiz, \(\mathbb{N}\)’nin alt kümelerinin daha küçük bir sonsuzluk üretemeyeceğini söyler. İspatın anahtarı iyi sıralama ilkesidir: alt kümenin elemanlarını küçükten büyüğe sıralayarak numaralarız.
Teorem 14.1 (Doğal Sayıların Alt Kümeleri Sayılabilirdir) \(\mathbb{N}\)’nin her alt kümesi sayılabilirdir. Özel olarak \(\mathbb{N}\)’nin sonsuz her alt kümesi \(\mathbb{N}\) ile eşgüçlüdür.
İspat
\(A \subseteq \mathbb{N}\) olsun. \(A\) sonluysa tanım gereği sayılabilirdir. \(A\) sonsuz olsun; \(A \sim \mathbb{N}\) göstereceğiz.
Dizinin kuruluşu. \(A \ne \varnothing\) olduğundan Teorem 9.2 gereği \(A\)’nın en küçük elemanı vardır; \(a_1 = \min A\) diyelim. \(a_1, \dots, a_n\) seçilmiş olsun ve
\[A_n = A \setminus \{a_1, \dots, a_n\}\]
yazalım. Kuruluş gereği \(a_{k+1} \in A_k\), yani \(a_{k+1} \notin \{a_1, \dots, a_k\}\) olduğundan \(a_1, \dots, a_n\) birbirinden farklıdır ve \(i \mapsto a_i\) eşlemesiyle \(\{a_1, \dots, a_n\} \sim \mathbb{N}_n\) sonludur. \(A_n = \varnothing\) olsaydı \(A \subseteq \{a_1, \dots, a_n\}\) olur, Önerme 14.2 gereği \(A\) sonlu olurdu; demek ki \(A_n \ne \varnothing\) ve \(a_{n+1} = \min A_n\) tanımlanabilir. Böylece \(A\)’nın elemanlarından oluşan bir \((a_n)\) dizisi elde ettik; \(A_0 = A\) yazarsak her \(n\) için \(a_n = \min A_{n-1}\)’dir.
Dizi kesin artandır. \(a_{n+1} \in A_n \subseteq A_{n-1}\) ve \(a_n = \min A_{n-1}\) olduğundan \(a_n \le a_{n+1}\); ayrıca \(a_{n+1} \notin \{a_1, \dots, a_n\}\) olduğundan \(a_{n+1} \ne a_n\). O hâlde \(a_n < a_{n+1}\). Zincirleme uygulayınca \(n < m \Rightarrow a_n < a_m\) bulunur.
\(f(n) = a_n\) birebirdir. \(n \ne m\) ise, diyelim \(n < m\), \(a_n < a_m\) olduğundan \(f(n) \ne f(m)\).
\(a_n \ge n\) eşitsizliği. Tümevarımla: \(a_1 \in \mathbb{N}\) olduğundan \(a_1 \ge 1\). \(a_n \ge n\) ise \(a_{n+1} > a_n \ge n\), yani \(a_{n+1} > n\); \(n\) ile \(a_{n+1}\) doğal sayı olduğundan Önerme 9.3 (4) gereği \(a_{n+1} \ge n + 1\).
\(f\) örtendir. \(m \in A\) olsun; \(m\)’nin dizide göründüğünü gösterelim. Aksini varsayalım: her \(k\) için \(m \ne a_k\). O zaman özel olarak \(m \notin \{a_1, \dots, a_{m-1}\}\), yani \(m \in A_{m-1}\); buradan \(a_m = \min A_{m-1} \le m\). Öte yandan \(a_m \ge m\). Demek ki \(a_m = m\); bu, varsayımımızla çelişir. O hâlde her \(m \in A\) bir \(a_k\)’ye eşittir.
Sonuç olarak \(f\colon \mathbb{N} \to A\) birebir-örtendir ve \(A \sim \mathbb{N}\).
\(\blacksquare\)
Sonuç 14.3 (Sayılabilir Kümenin Alt Kümesi Sayılabilirdir) \(A\) sayılabilir ve \(B \subseteq A\) ise \(B\) de sayılabilirdir.
İspat
\(A\) sonluysa Önerme 14.2 gereği \(B\) sonlu, dolayısıyla sayılabilirdir. \(A \sim \mathbb{N}\) olsun ve \(f\colon A \to \mathbb{N}\) birebir-örten olsun. \(f(B) \subseteq \mathbb{N}\) olduğundan Teorem 14.1 gereği \(f(B)\) sayılabilirdir. \(f|_B\colon B \to f(B)\) birebir-örten olduğundan \(B \sim f(B)\): \(f(B)\) sonluysa \(B\) sonlu, \(f(B) \sim \mathbb{N}\) ise \(B \sim \mathbb{N}\)’dir.
\(\blacksquare\)
Bir kümenin sayılabilir olduğunu göstermek için her seferinde birebir-örten bir eşleme kurmak zahmetlidir. Aşağıdaki ölçüt işi çok kolaylaştırır: kümeyi \(\mathbb{N}\)’ye birebir gömmek ya da kümeyi (tekrarlara izin vererek) bir diziyle “kaplamak” yeterlidir.
Teorem 14.2 (Sayılabilirlik Ölçütleri) \(A \ne \varnothing\) bir küme olsun. Aşağıdakiler birbirine denktir:
- \(A\) sayılabilirdir.
- Birebir bir \(f\colon A \to \mathbb{N}\) fonksiyonu vardır.
- Örten bir \(g\colon \mathbb{N} \to A\) fonksiyonu vardır.
İspat
(1) \(\Rightarrow\) (2): \(A\) sonluysa bir \(n\) için birebir-örten \(f\colon A \to \mathbb{N}_n\) vardır; \(\mathbb{N}_n \subseteq \mathbb{N}\) olduğundan \(f\), \(A\)’dan \(\mathbb{N}\)’ye birebir bir fonksiyondur. \(A \sim \mathbb{N}\) ise birebir-örten eşleme zaten birebirdir.
(2) \(\Rightarrow\) (1): \(f\colon A \to \mathbb{N}\) birebir olsun. \(f(A) \subseteq \mathbb{N}\), Teorem 14.1 gereği sayılabilirdir ve \(f\colon A \to f(A)\) birebir-örten olduğundan \(A \sim f(A)\). O hâlde \(A\) da sayılabilirdir.
(2) \(\Rightarrow\) (3): \(f\colon A \to \mathbb{N}\) birebir olsun ve bir \(a_0 \in A\) sabitleyelim. \(g\colon \mathbb{N} \to A\) fonksiyonunu şöyle tanımlayalım: \(n \in f(A)\) ise \(g(n)\), \(f(a) = n\) eşitliğini sağlayan (birebirlik gereği tek olan) \(a\) elemanı olsun; \(n \notin f(A)\) ise \(g(n) = a_0\) olsun. Her \(a \in A\) için \(g(f(a)) = a\) olduğundan \(g\) örtendir.
(3) \(\Rightarrow\) (2): \(g\colon \mathbb{N} \to A\) örten olsun. Her \(a \in A\) için \(g^{-1}(\{a\}) = \{n \in \mathbb{N} : g(n) = a\}\) kümesi örtenlik gereği boş değildir; Teorem 9.2 ile en küçük elemanı vardır. \(f(a) = \min g^{-1}(\{a\})\) tanımlayalım. \(f(a) = f(b) = n\) ise \(g(n) = a\) ve \(g(n) = b\), yani \(a = b\); \(f\) birebirdir.
\(\blacksquare\)
Ölçütün gücü şuradadır: bir kümenin sayılabilir olduğunu göstermek için, elemanlarını tekrarlı ve düzensiz de olsa bir dizi hâlinde sıralamak yeter. Tam sayılarla başlayalım: \(\mathbb{Z}\)’yi “\(0, 1, -1, 2, -2, 3, -3, \dots\)” diye sıralayabiliriz.
Teorem 14.3 (Tam Sayılar Sayılabilirdir) \(\mathbb{Z}\) sayılabilir sonsuz bir kümedir.
İspat
\(f\colon \mathbb{N} \to \mathbb{Z}\) fonksiyonunu
\[f(n) = \begin{cases} \dfrac{n}{2}, & n \text{ çift} \\[6pt] -\dfrac{n - 1}{2}, & n \text{ tek} \end{cases}\]
ile tanımlayalım; \(n\) çiftse \(n/2 \in \mathbb{N}\), tekse \((n-1)/2 \in \mathbb{N} \cup \{0\}\) olduğundan değerler gerçekten \(\mathbb{Z}\)’dedir (Tanım 11.2, Tanım 11.1). İlk değerler \(f(1) = 0\), \(f(2) = 1\), \(f(3) = -1\), \(f(4) = 2\), \(f(5) = -2\), \(\dots\) biçimindedir.
Birebirlik. \(f(n) = f(m)\) olsun. \(n\) ve \(m\) ikisi de çiftse \(n/2 = m/2\), yani \(n = m\); ikisi de tekse \(-(n-1)/2 = -(m-1)/2\), yine \(n = m\). Biri çift, diğeri tek olamaz: \(n\) çiftse \(f(n) = n/2 \ge 1 > 0 \ge -(m-1)/2 = f(m)\) olurdu.
Örtenlik. \(k \in \mathbb{Z}\) verilsin. \(k \ge 1\) ise \(n = 2k\) çift bir doğal sayıdır ve \(f(n) = k\). \(k \le 0\) ise \(n = 1 - 2k = 2(-k) + 1\) tek bir doğal sayıdır (\(-k \ge 0\)) ve \(f(n) = -\dfrac{(1 - 2k) - 1}{2} = k\).
O hâlde \(f\) birebir-örtendir ve \(\mathbb{Z} \sim \mathbb{N}\).
\(\blacksquare\)
Şimdi bölüm başındaki Galileo gözlemini kesinleştirelim: sonsuz kümeler, kendi öz alt kümelerinden biriyle eşgüçlü olan kümelerdir. Önce her sonsuz kümenin içinde “bir kopya \(\mathbb{N}\)” bulunduğunu gösterelim.
Önerme 14.3 (Her Sonsuz Küme Sayılabilir Sonsuz Bir Alt Küme İçerir) \(A\) sonsuz bir küme ise \(A\)’nın \(\mathbb{N}\) ile eşgüçlü bir \(B \subseteq A\) alt kümesi vardır.
İspat
\(A \ne \varnothing\) olduğundan bir \(a_1 \in A\) seçelim. \(a_1, \dots, a_n\) birbirinden farklı elemanlar olarak seçilmiş olsun. \(A \setminus \{a_1, \dots, a_n\} = \varnothing\) olsaydı \(A = \{a_1, \dots, a_n\}\) olurdu ve elemanlar farklı olduğundan \(i \mapsto a_i\) eşlemesiyle \(A \sim \mathbb{N}_n\), yani \(A\) sonlu olurdu; demek ki bu küme boş değildir ve içinden bir \(a_{n+1}\) seçebiliriz. Bu seçim \(a_{n+1}\)’i öncekilerden farklı kılar. Böylece \(n \mapsto a_n\) kuralı birebir bir \(\varphi\colon \mathbb{N} \to A\) fonksiyonu tanımlar. \(B = \varphi(\mathbb{N}) = \{a_1, a_2, \dots\}\) alalım; \(\varphi\colon \mathbb{N} \to B\) birebir-örtendir, yani \(B \sim \mathbb{N}\).
\(\blacksquare\)
Yukarıdaki ispatta \(a_1, a_2, a_3, \dots\) elemanlarını “seçtik” ama seçim için belirli bir kural vermedik; sonsuz çoklukta böyle seçim yapılabileceği, küme kuramının seçim aksiyomu (axiom of choice) ile güvence altına alınır. Analizde bu aksiyom (çoğu zaman farkında olmadan) sürekli kullanılır; biz de kullanacağız. Teorem 14.1 ispatında ise seçim gerekmedi: her adımda “en küçük eleman” kuralını kullandık.
Teorem 14.4 (Dedekind: Sonsuzluğun Karakterizasyonu) Bir \(A\) kümesi sonsuzdur ancak ve ancak \(A\), bir öz alt kümesiyle eşgüçlüdür.
İspat
(\(\Rightarrow\) yönü) \(A\) sonsuz olsun. Önerme 14.3 gereği \(A\) içinde birbirinden farklı \(a_1, a_2, \dots\) elemanları vardır; \(B = \{a_1, a_2, \dots\}\) olsun. \(C = A \setminus \{a_1\}\) öz alt kümesini alalım ve \(f\colon A \to C\)’yi
\[f(x) = \begin{cases} a_{n+1}, & x = a_n \text{ (bir } n \in \mathbb{N} \text{ için)} \\ x, & x \notin B \end{cases}\]
ile tanımlayalım. \(f\)’nin değerleri \(a_1\)’den farklıdır, yani gerçekten \(C\)’ye gider. Birebirlik: \(B\) üzerinde \(a_n \mapsto a_{n+1}\) birebirdir, \(A \setminus B\) üzerinde \(f\) birim fonksiyondur ve bu iki parçanın görüntüleri (\(B \setminus \{a_1\}\) ile \(A \setminus B\)) ayrıktır. Örtenlik: \(y \in C\) ise ya \(y \notin B\) olup \(f(y) = y\), ya da \(y = a_{n}\) için \(n \ge 2\) olup \(f(a_{n-1}) = y\)’dir. O hâlde \(A \sim C\).
(\(\Leftarrow\) yönü) Karşıt tersini gösterelim: \(A\) sonluysa hiçbir öz alt kümesiyle eşgüçlü değildir. \(A = \varnothing\)’nin öz alt kümesi yoktur. \(|A| = n \ge 1\) ve \(C \subsetneq A\) olsun; bir \(a \in A \setminus C\) seçelim. Bir \(f\colon A \to C\) birebir-örten eşlemesi olduğunu varsayıp çelişki bulacağız.
\(n = 1\) ise \(A = \{a\}\) ve \(C = \varnothing\); boş olmayan bir kümeden boş kümeye fonksiyon yoktur. \(n \ge 2\) olsun. \(g\colon A \to \mathbb{N}_n\) birebir-örten olsun ve \(\sigma\colon \mathbb{N}_n \to \mathbb{N}_n\), \(g(a)\) ile \(n\) değerlerini birbiriyle değiştiren, diğer sayıları sabit bırakan fonksiyon olsun (\(g(a) = n\) ise \(\sigma\) birimdir); \(\sigma\) birebir-örtendir. \(h = \sigma \circ g\colon A \to \mathbb{N}_n\) birebir-örtendir ve \(h(a) = n\)’dir. \(h\) birebir-örten olduğundan \(h(A \setminus \{a\}) = \mathbb{N}_n \setminus \{n\} = \mathbb{N}_{n-1}\); yani \(h|_{A \setminus \{a\}}\colon A \setminus \{a\} \to \mathbb{N}_{n-1}\) birebir-örtendir. \(C \subseteq A \setminus \{a\}\) olduğundan
\[\mathbb{N}_n \xrightarrow{\;g^{-1}\;} A \xrightarrow{\;f\;} C \xrightarrow{\;h|_C\;} \mathbb{N}_{n-1}\]
bileşkesi birebirdir. Lemma 14.1 gereği \(n \le n - 1\); çelişki.
\(\blacksquare\)
Dedekind (1888) sonsuzluğu tam da bu özellikle tanımlamayı önermiştir; teorem, bizim “sonlu değil” tanımımızla Dedekind’in tanımının çakıştığını söyler. Pratik yararı da vardır: bir kümenin sonsuz olduğunu göstermek için onu bir öz alt kümesine birebir-örten eşlemek yeter.
14.4 Kartezyen Çarpım ve Birleşim
Sayılabilir kümelerden yeni sayılabilir kümeler üretmenin iki yolu vardır: kartezyen çarpım ve sayılabilir birleşim. İkisinin de anahtarı \(\mathbb{N} \times \mathbb{N}\) kümesidir. İlk bakışta bu küme \(\mathbb{N}\)’den “çok daha büyük” görünür: sonsuz satır, her satırda sonsuz eleman. Satır satır saymaya kalkarsak ilk satır bile bitmez; hile, satırları değil köşegenleri saymaktır.
Teorem 14.5 (N × N Sayılabilirdir) \(\mathbb{N} \times \mathbb{N} \sim \mathbb{N}\).
İspat
\((m, n) \in \mathbb{N} \times \mathbb{N}\) çiftlerini \(d = m + n\) toplamına göre köşegenlere ayıralım: \(d\)-inci köşegen (\(d \ge 2\))
\[(1, d-1),\; (2, d-2),\; \dots,\; (d-1, 1)\]
çiftlerinden oluşur; \(d - 1\) tane çift vardır. Köşegenleri \(d = 2, 3, 4, \dots\) sırasıyla, her köşegeni de \(m = 1, 2, \dots, d-1\) sırasıyla dolaşalım. \(d\)-inci köşegenden önce gelen çiftlerin sayısı
\[T(d) = 1 + 2 + \dots + (d - 2) = \frac{(d-2)(d-1)}{2} \qquad (d \ge 3), \qquad T(2) = 0\]
olur (toplam formülü için bkz. Örnek 9.2; \(T(d)\) doğal sayıların toplamı olduğundan bir tam sayıdır). Buna göre \((m, n)\) çiftinin sıra numarası
\[\pi(m, n) = T(m + n) + m = \frac{(m+n-2)(m+n-1)}{2} + m\]
olsun. İlk değerler: \(\pi(1,1) = 1\); \(\pi(1,2) = 2\), \(\pi(2,1) = 3\); \(\pi(1,3) = 4\), \(\pi(2,2) = 5\), \(\pi(3,1) = 6\); \(\pi(1,4) = 7\), \(\dots\)
\(\pi\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) fonksiyonunun birebir-örten olduğunu gösterelim. Önce \(T\)’nin davranışını not edelim: \(T(d+1) - T(d) = d - 1 \ge 1\) olduğundan \(T\) kesin artandır; ayrıca \(d \ge 2\) için \(T(d) \ge d - 2\)’dir (\(d = 2\) için eşitlik, \(d \ge 3\) için \((d-1)/2 \ge 1\)).
Birebirlik. \((m, n) \ne (m', n')\) olsun; \(d = m + n\), \(d' = m' + n'\) diyelim. \(d < d'\) ise, \(m \le d - 1\) olduğundan
\[\pi(m, n) = T(d) + m \le T(d) + (d - 1) = T(d+1) \le T(d') < T(d') + m' = \pi(m', n')\]
\(d > d'\) durumu simetriktir. \(d = d'\) ise \(m \ne m'\) olmak zorundadır (aksi hâlde \(n = d - m = d' - m' = n'\) olurdu) ve \(\pi(m, n) - \pi(m', n') = m - m' \ne 0\). Her durumda \(\pi(m, n) \ne \pi(m', n')\).
Örtenlik. \(N \in \mathbb{N}\) verilsin. \(D = \{d \in \mathbb{N} : d \ge 2,\ T(d) < N\}\) kümesini alalım. \(T(2) = 0 < N\) olduğundan \(2 \in D\); \(d \in D\) ise \(d - 2 \le T(d) < N\), yani \(d < N + 2\), dolayısıyla \(D\) üstten sınırlıdır. Teorem 11.2 gereği \(D\)’nin en büyük elemanı \(d\) vardır: \(T(d) < N\) ve \(d + 1 \notin D\) olduğundan \(T(d+1) \ge N\). Şimdi \(m = N - T(d)\) alalım. \(m \ge 1\) ve
\[m = N - T(d) \le T(d+1) - T(d) = d - 1\]
olduğundan \(n = d - m \ge 1\) bir doğal sayıdır. Böylece \((m, n) \in \mathbb{N} \times \mathbb{N}\) ve \(\pi(m, n) = T(d) + m = N\).
\(\blacksquare\)
Bu teoremin en sık kullanılan biçimi şudur.
Sonuç 14.4 (Sayılabilir Kümelerin Çarpımı Sayılabilirdir) \(A\) ve \(B\) sayılabilir kümeler ise \(A \times B\) de sayılabilirdir. Daha genel olarak sonlu sayıda sayılabilir kümenin kartezyen çarpımı \(A_1 \times \dots \times A_k\) sayılabilirdir.
İspat
\(A\) veya \(B\) boşsa \(A \times B = \varnothing\) sonludur. İkisi de boş değilse Teorem 14.2 ile birebir \(f\colon A \to \mathbb{N}\) ve \(g\colon B \to \mathbb{N}\) vardır. \(\pi\), Teorem 14.5 ispatındaki eşleme olmak üzere
\[F\colon A \times B \to \mathbb{N}, \qquad F(a, b) = \pi\big(f(a), g(b)\big)\]
tanımlayalım. \(F(a, b) = F(a', b')\) ise \(\pi\) birebir olduğundan \(f(a) = f(a')\) ve \(g(b) = g(b')\), buradan \(a = a'\) ve \(b = b'\). \(F\) birebirdir; ölçüt gereği \(A \times B\) sayılabilirdir. Genel durum \(k\) üzerinden tümevarımla çıkar: \(A_1 \times \dots \times A_{k+1}\), \((A_1 \times \dots \times A_k) \times A_{k+1}\) ile eşgüçlüdür (bir \(((a_1, \dots, a_k), a_{k+1}) \mapsto (a_1, \dots, a_{k+1})\) eşlemesiyle).
\(\blacksquare\)
Teorem 14.6 (Sayılabilir Birleşim Teoremi) Her \(n \in \mathbb{N}\) için \(A_n\) sayılabilir bir küme olsun. O zaman
\[A = \bigcup_{n=1}^{\infty} A_n\]
kümesi de sayılabilirdir. Kısaca: sayılabilir çoklukta sayılabilir kümenin birleşimi sayılabilirdir.
İspat
Bütün \(A_n\)’ler boşsa \(A = \varnothing\) sonludur. Değilse bir \(x_0 \in A\) sabitleyelim. Her \(n\) için bir \(g_n\colon \mathbb{N} \to A_n\) örten fonksiyonu seçelim: \(A_n \ne \varnothing\) ise Teorem 14.2 böyle bir \(g_n\) verir; \(A_n = \varnothing\) ise \(g_n\)’yi sabit \(x_0\) değerli fonksiyon olarak alalım (bu durumda \(g_n\)’nin değerleri \(A_n\)’de değil ama \(A\)’dadır; aşağıda yalnızca \(A\)’ya gitmesi gerekecek). Şimdi
\[G\colon \mathbb{N} \times \mathbb{N} \to A, \qquad G(n, k) = g_n(k)\]
tanımlayalım. \(G\) örtendir: \(x \in A\) ise bir \(n\) için \(x \in A_n\), bu \(A_n\) boş değildir ve \(g_n\) örten olduğundan bir \(k\) için \(x = g_n(k) = G(n, k)\). Teorem 14.5 ile birebir-örten bir \(\pi\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) vardır; \(G \circ \pi^{-1}\colon \mathbb{N} \to A\) örten fonksiyonların bileşkesi olarak örtendir. Teorem 14.2 gereği \(A\) sayılabilirdir.
\(\blacksquare\)
İspatta her \(n\) için bir \(g_n\) “seçtik”; bu yine seçim aksiyomunun (sayılabilir biçiminin) kullanımıdır.
Sonuç 14.5 (Sonlu Birleşim) \(A_1, \dots, A_k\) sayılabilir ise \(A_1 \cup \dots \cup A_k\) sayılabilirdir. Özel olarak iki sayılabilir kümenin birleşimi sayılabilirdir.
İspat
\(n > k\) için \(A_n = A_k\) alalım. O zaman \(\bigcup_{n=1}^{\infty} A_n = A_1 \cup \dots \cup A_k\) olur ve Teorem 14.6 uygulanır.
\(\blacksquare\)
Bu araçlarla rasyonel sayıların sayılabilir olduğunu göstermek artık birkaç satırdır. Sonuç ilk bakışta şaşırtıcıdır: \(\mathbb{Q}\) sayı doğrusunda yoğundur (Teorem 13.5), yani her aralıkta sonsuz çoklukta rasyonel sayı vardır; yine de rasyonel sayılar bir dizi hâlinde sıralanabilir.
Teorem 14.7 (Rasyonel Sayılar Sayılabilirdir) \(\mathbb{Q}\) sayılabilir sonsuz bir kümedir.
İspat
Her \(n \in \mathbb{N}\) için
\[B_n = \left\{ \frac{m}{n} : m \in \mathbb{Z} \right\}\]
olsun. \(h_n\colon \mathbb{Z} \to B_n\), \(h_n(m) = m/n\) fonksiyonu tanım gereği örtendir (üstelik birebirdir: \(m/n = m'/n\) ise \(m = m'\)). Teorem 14.3 ile \(\mathbb{Z} \sim \mathbb{N}\) olduğundan bir \(\varphi\colon \mathbb{N} \to \mathbb{Z}\) birebir-örten eşlemesi vardır ve \(h_n \circ \varphi\colon \mathbb{N} \to B_n\) örtendir; Teorem 14.2 gereği her \(B_n\) sayılabilirdir.
Şimdi \(\mathbb{Q} = \bigcup_{n=1}^{\infty} B_n\) olduğunu görelim. Her \(B_n \subseteq \mathbb{Q}\) açıktır. Tersine \(x \in \mathbb{Q}\) ise Tanım 11.6 gereği \(x = m/n\) olacak biçimde \(m, n \in \mathbb{Z}\), \(n \ne 0\) vardır; \(n < 0\) ise \(x = (-m)/(-n)\) yazarak paydayı pozitif alabiliriz. O hâlde \(n \in \mathbb{N}\) ve \(x \in B_n\).
Teorem 14.6 gereği \(\mathbb{Q}\) sayılabilirdir. \(\mathbb{N} \subseteq \mathbb{Q}\) olduğundan \(\mathbb{Q}\) sonsuzdur (Önerme 14.2); dolayısıyla sayılabilir sonsuzdur.
\(\blacksquare\)
İkinci bir ispat: her rasyonel sayı sadeleştirilmiş tek bir \(p/q\) (\(q \in \mathbb{N}\), \(p \in \mathbb{Z}\), \(p\) ile \(q\) aralarında asal) biçiminde yazılır; \(x \mapsto (p, q)\) kuralı \(\mathbb{Q}\)’yu \(\mathbb{Z} \times \mathbb{N}\) içine birebir gömer, Sonuç 14.4 ve ölçüt gereği \(\mathbb{Q}\) sayılabilirdir.
Bu iki teoremin ders verdiği şey şudur: yoğunluk bir büyüklük ölçüsü değildir. \(\mathbb{Q}\) doğruda her yere yayılmıştır ama “sayıca” \(\mathbb{N}\)’den fazla değildir.
Örnek 14.3 (Rasyonel Uçlu Aralıklar) Uçları rasyonel olan açık aralıkların kümesi
\[\mathcal{I} = \{(p, q) : p, q \in \mathbb{Q},\ p < q\}\]
sayılabilir midir?
Çözüm
Evet. \(\mathbb{Q} \times \mathbb{Q}\), Sonuç 14.4 gereği sayılabilirdir. \((p, q)\) aralığını \((p, q) \in \mathbb{Q} \times \mathbb{Q}\) sıralı ikilisine götüren kural birebirdir: iki açık aralık eşitse uçları eşittir, çünkü uçlar aralıktan geri okunabilir: \(\sup (p, q) = q\)’dur (\(q\) bir üst sınırdır ve her \(\varepsilon > 0\) için \(\max\{p, q - \varepsilon\} < q\) olduğundan Önerme 7.11 ile aralıkta \(q - \varepsilon\)’dan büyük bir nokta bulunur; Teorem 10.1), benzer biçimde \(\inf (p, q) = p\)’dir. O hâlde \(\mathcal{I}\), \(\mathbb{Q} \times \mathbb{Q}\)’nun bir alt kümesiyle eşgüçlüdür ve Sonuç 14.3 ile sayılabilirdir. Bu küme topolojide sık kullanılır: her açık küme, rasyonel uçlu aralıkların (sayılabilir çoklukta) birleşimi olarak yazılabilir.
\(\blacksquare\)
Örnek 14.4 (Tam Katsayılı Polinomlar) Katsayıları tam sayı olan bütün polinomların kümesi \(\mathcal{P}\) sayılabilir midir?
Çözüm
Bir polinomu katsayı listesiyle özdeşleştirelim: derecesi en çok \(k\) olan tam katsayılı \(a_0 + a_1 x + \dots + a_k x^k\) polinomu \((a_0, a_1, \dots, a_k) \in \mathbb{Z}^{k+1}\) listesine karşılık gelir ve farklı listeler farklı polinomlar verir. Bu polinomların kümesi \(\mathcal{P}_k\) olsun; \(\mathcal{P}_k \sim \mathbb{Z}^{k+1}\). Teorem 14.3 ve Sonuç 14.4 gereği \(\mathbb{Z}^{k+1} = \mathbb{Z} \times \dots \times \mathbb{Z}\) sayılabilirdir; dolayısıyla her \(\mathcal{P}_k\) sayılabilirdir. Her polinomun sonlu bir derecesi olduğundan
\[\mathcal{P} = \bigcup_{k=1}^{\infty} \mathcal{P}_k\]
ve Teorem 14.6 gereği \(\mathcal{P}\) sayılabilirdir.
\(\blacksquare\)
Sıfırdan farklı tam katsayılı bir polinomun kökü olan reel sayıya cebirsel sayı denir; \(\sqrt{2}\) (\(x^2 - 2\)’nin kökü), \(\sqrt[3]{5}\), \(\frac{1 + \sqrt{5}}{2}\) ve bütün rasyonel sayılar cebirseldir. Cebirden bilinen bir gerçek, derecesi \(k\) olan sıfırdan farklı bir polinomun en çok \(k\) kökü olduğudur. Sıfırdan farklı polinomlar, sayılabilir olduğunu gördüğümüz \(\mathcal{P}\) kümesinin (Örnek 14.4) bir alt kümesidir; Sonuç 14.3 gereği bunlar da sayılabilir çokluktadır ve her birinin kök kümesi sonludur. (Sıfır polinomunu dışarıda bırakmak şarttır: onun kök kümesi \(\mathbb{R}\)’nin tamamıdır.) Buna göre cebirsel sayılar kümesi, sayılabilir çoklukta sonlu kümenin birleşimidir, yani Teorem 14.6 gereği sayılabilirdir. Hemen aşağıda \(\mathbb{R}\)’nin sayılamaz olduğunu göreceğiz; o zaman cebirsel olmayan (aşkın, transcendental) reel sayıların var olduğu, üstelik sayılamaz çoklukta olduğu sonucu çıkar. Cantor’un 1874 tarihli bu argümanı, tek bir aşkın sayı bile yazmadan aşkın sayıların varlığını ispatlar. (\(e\) ve \(\pi\)’nin aşkın olduğu çok daha zor, ayrı teoremlerdir.)
14.5 Reel Sayılar Sayılamaz
Şimdiye dek gördüğümüz sonsuz kümelerin hepsi sayılabilir çıktı. Sayılamaz küme gerçekten var mıdır? Cantor’un teoremi bu soruya evet der: reel sayılar bir dizi hâlinde sıralanamaz. İspatta tamlık aksiyomunun sonuçlarından iç içe aralıklar teoremini (Teorem 10.5) kullanacağız; bu tesadüf değildir, çünkü \(\mathbb{Q}\) ile \(\mathbb{R}\)’yi ayıran tam da tamlıktır.
Teorem 14.8 (Cantor Teoremi: Reel Sayılar Sayılamaz) \(\mathbb{R}\) sayılamaz bir kümedir. Yani reel sayılar bir \(x_1, x_2, x_3, \dots\) listesi hâlinde sıralanamaz: her böyle liste için listede bulunmayan bir reel sayı vardır.
İspat
\(\mathbb{R}\)’nin sayılabilir olduğunu varsayalım. \(\mathbb{R} \ne \varnothing\) olduğundan Teorem 14.2 gereği örten bir \(g\colon \mathbb{N} \to \mathbb{R}\) vardır; \(x_n = g(n)\) yazalım. O zaman her reel sayı bir \(x_n\)’dir:
\[\mathbb{R} = \{x_1, x_2, x_3, \dots\}\]
Şimdi kapalı aralıklardan oluşan, iç içe bir \(I_1 \supseteq I_2 \supseteq I_3 \supseteq \dots\) dizisini, her \(n\) için \(x_n \notin I_n\) olacak biçimde kuracağız.
Kuruluş. \(I_1 = [x_1 + 1, x_1 + 2]\) alalım; açıkça \(x_1 \notin I_1\). \(I_n = [a_n, b_n]\) (\(a_n < b_n\)) kurulmuş olsun. \(h = \dfrac{b_n - a_n}{3} > 0\) diyelim ve \(I_n\)’nin iki uç üçte birlik parçasına bakalım:
\[L = [a_n,\ a_n + h], \qquad R = [a_n + 2h,\ b_n]\]
\(x_{n+1}\) bu iki aralığın ikisinde birden olamaz: olsaydı \(a_n + 2h \le x_{n+1} \le a_n + h\), yani \(h \le 0\) olurdu. O hâlde \(x_{n+1} \notin L\) ise \(I_{n+1} = L\), aksi hâlde \(I_{n+1} = R\) alalım. Her iki durumda da \(I_{n+1}\) kapalı ve sınırlı bir aralıktır, \(I_{n+1} \subseteq I_n\)’dir, uzunluğu pozitiftir ve \(x_{n+1} \notin I_{n+1}\)’dir.
Çelişki. \((I_n)\), kapalı ve sınırlı aralıkların iç içe bir dizisidir; Teorem 10.5 gereği
\[\bigcap_{n=1}^{\infty} I_n \ne \varnothing\]
Bu kesişimden bir \(x\) alalım. \(x\) bir reel sayı olduğundan bir \(k \in \mathbb{N}\) için \(x = x_k\)’dir. Ama \(x \in I_k\) (kesişimin elemanı) ve \(x_k \notin I_k\) (kuruluş gereği); çelişki. Demek ki \(\mathbb{R}\) sayılabilir değildir.
\(\blacksquare\)
Aynı teoremin daha ünlü bir ispatı ondalık açılımlarla yapılır. \((0, 1)\)’in sayılabilir olduğunu, \((0, 1) = \{x_1, x_2, \dots\}\) olduğunu varsayalım ve her \(x_n\)’yi ondalık açılımıyla yazalım:
\[x_n = 0{,}d_{n1}\,d_{n2}\,d_{n3}\,\dots\]
Yeni bir \(y = 0{,}e_1 e_2 e_3 \dots\) sayısını, \(d_{nn} \ne 5\) ise \(e_n = 5\), \(d_{nn} = 5\) ise \(e_n = 6\) kuralıyla tanımlayalım. \(y \in (0, 1)\)’dir ve her \(n\) için \(n\)-inci basamağı \(x_n\)’ninkinden farklıdır; \(y\)’nin açılımı yalnızca \(5\) ve \(6\) rakamlarını içerdiğinden (\(0{,}4999\ldots = 0{,}5000\ldots\) türünden) çift açılım sorunu da doğmaz. Dolayısıyla \(y\) listede yoktur; çelişki. Ondalık açılımların varlığını ve tekliğini henüz ispatlamadığımız için biz iç içe aralıklarla verilen ispatı esas aldık; iki ispatın fikri aynıdır: listedeki \(n\)-inci sayıyı \(n\)-inci adımda dışarıda bırakmak. Bu köşegen fikri, alıştırmalardaki (d) ve (e) şıklarında tam titizlikle karşımıza çıkacak.
Sonuç 14.6 (Aralıklar Sayılamaz) \(a < b\) olmak üzere \((a, b)\) açık aralığı sayılamazdır. Dolayısıyla \([a, b]\), \([a, b)\), \((a, b]\) ve genel olarak \((a, b)\)’yi kapsayan her küme sayılamazdır.
İspat
Örnek 14.2 gereği \((a, b) \sim \mathbb{R}\); \(\psi\colon (a, b) \to \mathbb{R}\) birebir-örten olsun. \((a, b)\) sayılabilir olsaydı, boş olmadığından Teorem 14.2 ile örten bir \(\varphi\colon \mathbb{N} \to (a, b)\) olurdu ve \(\psi \circ \varphi\colon \mathbb{N} \to \mathbb{R}\) örten fonksiyonların bileşkesi olarak örten olurdu (Teorem 5.4); yine ölçüt gereği \(\mathbb{R}\) sayılabilir olurdu. Bu Teorem 14.8 ile çelişir. Kapsayan kümeler için: \((a, b) \subseteq C\) ve \(C\) sayılabilir olsaydı Sonuç 14.3 gereği \((a, b)\) de sayılabilir olurdu.
\(\blacksquare\)
Sonuç 14.7 (İrrasyonel Sayılar Sayılamaz) İrrasyonel sayılar kümesi \(\mathbb{R} \setminus \mathbb{Q}\) sayılamazdır. Daha genel olarak \(A \subseteq \mathbb{R}\) sayılabilir ise \(\mathbb{R} \setminus A\) sayılamazdır.
İspat
\(A \subseteq \mathbb{R}\) sayılabilir olsun ve \(\mathbb{R} \setminus A\)’nın da sayılabilir olduğunu varsayalım. O zaman \(\mathbb{R} = A \cup (\mathbb{R} \setminus A)\) iki sayılabilir kümenin birleşimi olarak Sonuç 14.5 gereği sayılabilir olurdu; bu Teorem 14.8 ile çelişir. \(A = \mathbb{Q}\) almak (Teorem 14.7) irrasyonel sayılar (Tanım 13.1) için sonucu verir.
\(\blacksquare\)
Bu sonuç, bölüm başındaki soruyu yanıtlar: rasyoneller de irrasyoneller de yoğun, ama irrasyoneller “ezici çoğunluk”tur. Sayı doğrusundan rastgele bir nokta seçseniz, karşınıza çıkacak olan neredeyse kesinlikle irrasyoneldir. Dikkat çekici olan, bu sonucun tek bir irrasyonel sayıyı bile göstermeden elde edilebilmesidir: \(\mathbb{R}\) sayılamaz, \(\mathbb{Q}\) sayılabilir; o hâlde aradaki fark boş olamaz.
Cantor, eşgüçlü kümelere aynı kardinal sayıyı atar: \(\mathbb{N}\)’nin (dolayısıyla \(\mathbb{Z}\), \(\mathbb{Q}\) ve her sayılabilir sonsuz kümenin) kardinalitesi \(\aleph_0\) (“alef sıfır”), \(\mathbb{R}\)’nin (ve her aralığın) kardinalitesi \(\mathfrak{c}\) (süreklilik, continuum) ile gösterilir. \(A\)’dan \(B\)’ye birebir fonksiyon varsa \(|A| \le |B|\) yazılır; Cantor–Schröder–Bernstein teoremi \(|A| \le |B|\) ve \(|B| \le |A|\) ise \(A \sim B\) olduğunu söyler (ispatı bu dersin dışındadır). Bu bölümde \(\aleph_0 < \mathfrak{c}\) olduğunu ispatladık. Cantor’un “\(\aleph_0\) ile \(\mathfrak{c}\) arasında başka kardinal yoktur” biçimindeki süreklilik hipotezinin, küme kuramının olağan aksiyomlarından ne ispatlanabileceği (Gödel, 1940) ne de çürütülebileceği (Cohen, 1963) gösterilmiştir. Alıştırmalardaki (e) şıkkı ise sonsuzluğun sonsuz çeşidi olduğunu gösterir: hiçbir küme kendi alt kümeler kümesiyle eşgüçlü değildir.
14.6 Alıştırmalar
Alıştırma 14.1 (Sayılabilir ve Sayılamaz Kümeler)
\(\mathbb{N} \sim \mathbb{N} \cup \{0\}\) olduğunu gösteriniz. Buradan \(\mathbb{N} \cup \{0\}\)’ın sayılabilir sonsuz olduğu sonucunu çıkarınız.
\(f\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}\), \(f(m, n) = 2^{m-1}(2n - 1)\) fonksiyonunun birebir-örten olduğunu gösteriniz. (Bu, Teorem 14.5 için ikinci bir ispattır.)
\([0, 1] \sim (0, 1)\) olduğunu gösteriniz. Buradan \([0, 1] \sim \mathbb{R}\) sonucunu çıkarınız.
Terimleri \(0\) ve \(1\) olan bütün dizilerin kümesi \(\{0, 1\}^{\mathbb{N}} = \{s \mid s\colon \mathbb{N} \to \{0, 1\}\}\)’nin sayılamaz olduğunu gösteriniz.
(Cantor) \(A\) herhangi bir küme ve \(\mathcal{P}(A)\) onun bütün alt kümelerinin kümesi olsun. \(A\)’dan \(\mathcal{P}(A)\)’ya örten bir fonksiyon olmadığını gösteriniz. Buradan \(\mathcal{P}(\mathbb{N})\)’nin sayılamaz olduğu sonucunu çıkarınız.
Çözüm
a) \(g\colon \mathbb{N} \to \mathbb{N} \cup \{0\}\), \(g(n) = n - 1\) alalım; \(n = 1\) için \(g(1) = 0\), \(n \ge 2\) için Önerme 9.3 (2) gereği \(n - 1 \in \mathbb{N}\). Yani \(g\) gerçekten \(\mathbb{N} \cup \{0\}\)’a gider. \(n - 1 = m - 1\) ise \(n = m\); \(g\) birebirdir. \(k \in \mathbb{N} \cup \{0\}\) ise \(k + 1 \in \mathbb{N}\) ve \(g(k+1) = k\); \(g\) örtendir. O hâlde \(\mathbb{N} \cup \{0\} \sim \mathbb{N}\), yani sayılabilir sonsuzdur.
b) Önce bir hatırlatma: bir tam sayı hem çift hem tek olamaz (Önerme 11.2).
Birebirlik. \(f(m, n) = f(k, l)\), yani \(2^{m-1}(2n - 1) = 2^{k-1}(2l - 1)\) olsun; simetri gereği \(m \le k\) varsayabiliriz. \(2^{m-1} > 0\) ile sadeleştirip Teorem 11.3 uygulayınca
\[2n - 1 = 2^{k-m}(2l - 1)\]
bulunur. \(k > m\) olsaydı sağ taraf \(2 \cdot \big(2^{k-m-1}(2l - 1)\big)\) biçiminde çift, sol taraf tek olurdu; bu gözlemle çelişir. O hâlde \(k = m\) ve \(2n - 1 = 2l - 1\), yani \(n = l\).
Örtenlik. Olmayana ergi: \(f\)’nin görüntüsünde olmayan bir doğal sayı bulunsun. Teorem 9.2 gereği böyle sayıların en küçüğü \(N_0\) vardır. \(N_0 \ne 1\), çünkü \(1 = 2^0 \cdot 1 = f(1, 1)\). \(N_0\) tekse \(N_0 = 2n - 1\) olacak biçimde \(n = \dfrac{N_0 + 1}{2} \in \mathbb{N}\) vardır ve \(N_0 = f(1, n)\); çelişki. \(N_0\) çiftse \(N_0 = 2M\) ile \(M \in \mathbb{N}\) ve \(M < N_0\); \(N_0\)’ın en küçüklüğü gereği \(M = f(m, n) = 2^{m-1}(2n - 1)\) olacak \(m, n\) vardır, o zaman \(N_0 = 2^{m}(2n - 1) = f(m + 1, n)\); yine çelişki. Demek ki \(f\) örtendir.
c) \([0, 1]\) ile \((0, 1)\) yalnızca iki noktada, \(0\) ve \(1\)’de ayrılır; bu iki noktayı “içeriye sığdırmak” için sayılabilir bir alt kümeyi bir adım kaydıracağız (Hilbert’in oteli fikri). \(S = \{0, 1\} \cup \{1/n : n \ge 2\} \subseteq [0, 1]\) ve \(T = \{1/n : n \ge 2\} \subseteq (0, 1)\) olsun. \(F\colon [0, 1] \to (0, 1)\)’i
\[F(0) = \frac{1}{2}, \qquad F(1) = \frac{1}{3}, \qquad F\!\left(\frac{1}{n}\right) = \frac{1}{n + 2} \ (n \ge 2), \qquad F(x) = x \ (x \notin S)\]
ile tanımlayalım. \(F\), \(S\)’yi \(T\)’ye birebir-örten götürür: \(0 \mapsto 1/2\), \(1 \mapsto 1/3\) ve \(1/n \mapsto 1/(n+2)\) kuralı \(1/4, 1/5, \dots\) değerlerinin her birini tam bir kez alır. \(S\) dışında \(F\) birim fonksiyondur ve \([0, 1] \setminus S = (0, 1) \setminus T\)’dir. İki parçanın görüntüleri (\(T\) ile \((0, 1) \setminus T\)) ayrık olduğundan \(F\) birebirdir; görüntüleri birleşince \((0, 1)\)’in tamamı elde edildiğinden \(F\) örtendir. O hâlde \([0, 1] \sim (0, 1)\); Örnek 14.2 ve Önerme 14.1 ile \([0, 1] \sim \mathbb{R}\).
d) \(\{0, 1\}^{\mathbb{N}}\)’nin sayılabilir olduğunu varsayalım. Boş olmadığından Teorem 14.2 ile örten bir \(n \mapsto s_n\) eşlemesi, yani her dizinin bir \(s_n\) olduğu bir \(s_1, s_2, s_3, \dots\) listesi vardır. Yeni bir \(t\colon \mathbb{N} \to \{0, 1\}\) dizisini
\[t(n) = 1 - s_n(n) \qquad (n \in \mathbb{N})\]
ile tanımlayalım; \(s_n(n) \in \{0, 1\}\) olduğundan \(t(n) \in \{0, 1\}\)’dir. Her \(n\) için \(t(n) \ne s_n(n)\), dolayısıyla \(t \ne s_n\). Yani \(t\) listede yoktur; örtenlikle çelişir. Demek ki \(\{0, 1\}^{\mathbb{N}}\) sayılamazdır. (Bu, köşegen yönteminin en saf hâlidir: \(n\)-inci dizinin \(n\)-inci terimini değiştirdik.)
e) \(F\colon A \to \mathcal{P}(A)\) herhangi bir fonksiyon olsun. Her \(a \in A\) için \(F(a)\), \(A\)’nın bir alt kümesidir; \(a\) bu alt kümeye ait olabilir de olmayabilir de. Ait olmayanları toplayalım:
\[B = \{a \in A : a \notin F(a)\} \in \mathcal{P}(A)\]
\(F\)’nin örten olduğunu varsayalım; o zaman bir \(a_0 \in A\) için \(F(a_0) = B\)’dir. Şimdi \(a_0 \in B\) midir?
- \(a_0 \in B\) ise \(B\)’nin tanımı gereği \(a_0 \notin F(a_0) = B\); çelişki.
- \(a_0 \notin B\) ise \(a_0 \notin F(a_0)\), yani \(a_0\) tanım gereği \(B\)’nin elemanıdır; çelişki.
Her iki durum da çelişkili olduğundan \(F\) örten olamaz. Özel olarak \(\mathbb{N}\)’den \(\mathcal{P}(\mathbb{N})\)’ye örten fonksiyon yoktur; \(\mathcal{P}(\mathbb{N}) \ne \varnothing\) olduğundan Teorem 14.2 gereği \(\mathcal{P}(\mathbb{N})\) sayılamazdır. Aynı akıl yürütme \(A = \mathbb{R}\) için \(\mathcal{P}(\mathbb{R})\)’nin \(\mathbb{R}\)’den “daha büyük” olduğunu verir: kardinal sayıların sonu yoktur.
\(\blacksquare\)
Reel sayıların cebirsel ve sıralama yapısını, tamlığını ve büyüklüğünü tanıdık. Bundan sonra sayı doğrusuna başka bir gözle, “yakınlık” gözüyle bakacağız: bir noktanın çevresi, açık ve kapalı kümeler, yığılma noktaları. Bu yolculuk Komşuluklar ve Açık Kümeler bölümüyle başlıyor.