10 Doğal Sayılar ve Tümevarım
Şimdiye kadar reel sayıların cebirsel ve sıralama aksiyomlarını kullandık; \(0\) ve \(1\) sayıları aksiyomlarla verildi, \(1 + 1\), \(1 + 1 + 1\) gibi sayıları da elde edebiliyoruz. Ama “doğal sayılar” dediğimiz \(1, 2, 3, \dots\) kümesi aksiyomlarda yoktur. Üç nokta “böyle devam eder” der; matematiksel bir tanım ise üç noktaya izin vermez. Bu bölümde doğal sayıları reel sayıların içinde kesin olarak tanımlayacak, ardından onların en önemli özelliğini — tümevarım ilkesini — bir teorem olarak ispatlayacağız. Tümevarım, “her \(n\) için” biçimindeki sonsuz sayıda önermeyi iki adımda ispatlamanın yoludur ve mutlak değer bölümünde ertelediğimiz genel üçgen eşitsizliği dâhil, ileride sayısız yerde kullanılacaktır.
Bölüm boyunca Bölüm 6.2 ve Bölüm 7.1 altındaki aksiyomları ve önceki bölümlerin sonuçlarını kullanacağız. Tamlık Aksiyomu’na (Bölüm 9.4) yalnızca bölümün sonunda, doğal sayıların üstten sınırlı olmadığını ve iç içe aralıklar teoremini kanıtlarken başvuracağız.
10.1 Tümevarımsal Kümeler ve Doğal Sayılar
Doğal sayıları sezgisel olarak şöyle üretiriz: \(1\)’den başla, sürekli \(1\) ekle. Bu üretim kuralını bir kümenin özelliği olarak yazalım: küme \(1\)’i içermeli ve içerdiği her sayının bir fazlasını da içermeli.
Tanım 10.1 (Tümevarımsal Küme) \(A \subset \mathbb{R}\) olsun. Aşağıdaki iki koşul sağlanıyorsa \(A\) kümesine tümevarımsal (inductive) denir:
- \(1 \in A\);
- her \(x \in A\) için \(x + 1 \in A\).
Bu tanımı sağlayan pek çok küme vardır; bir kısmı doğal sayılardan “fazlasını” içerir.
Örnek 10.1 (Tümevarımsal Olan ve Olmayan Kümeler) Aşağıdaki kümelerin tümevarımsal olup olmadığını belirleyiniz: \(\mathbb{R}\), \(\ \mathbb{R}^{+} = (0, \infty)\), \(\ [1, \infty)\), \(\ \{1\} \cup [2, \infty)\), \(\ (1, \infty)\), \(\ [0, 5]\).
Çözüm
\(\mathbb{R}\): \(1 \in \mathbb{R}\) ve toplama \(\mathbb{R}\)’de tanımlı olduğundan \(x \in \mathbb{R}\) için \(x + 1 \in \mathbb{R}\). Tümevarımsaldır.
\((0, \infty)\): Önerme 7.7 gereği \(0 < 1\), yani \(1 \in (0, \infty)\). \(x > 0\) ise (O3) ile \(x + 1 > 0 + 1 = 1 > 0\); dolayısıyla \(x + 1 \in (0, \infty)\). Tümevarımsaldır.
\([1, \infty)\): \(1 \ge 1\). \(x \ge 1\) ise \(x + 1 \ge 2 > 1\). Tümevarımsaldır.
\(\{1\} \cup [2, \infty)\): \(1\) kümededir. \(x = 1\) ise \(x + 1 = 2 \in [2, \infty)\); \(x \ge 2\) ise \(x + 1 \ge 3 \ge 2\). Tümevarımsaldır. Dikkat: bu küme \((1, 2)\) aralığındaki hiçbir sayıyı içermez ama \(\frac{5}{2}\) gibi “doğal olmayan” sayıları içerir.
\((1, \infty)\): \(1 \notin (1, \infty)\) olduğundan birinci koşul bozulur. Tümevarımsal değildir.
\([0, 5]\): \(1 \in [0, 5]\) ama \(5 \in [0, 5]\) iken \(5 + 1 = 6 \notin [0, 5]\). İkinci koşul bozulur; tümevarımsal değildir.
\(\blacksquare\)
Örnek, aradığımız kümeyi işaret ediyor: doğal sayılar kümesi tümevarımsal olmalı, ama “fazlalık” içermemeli — yani tümevarımsal kümelerin en küçüğü olmalı. En küçük kümeyi elde etmenin standart yolu, adayların hepsini kesiştirmektir.
Tanım 10.2 (Doğal Sayılar Kümesi) \(\mathcal{T}\), \(\mathbb{R}\)’nin bütün tümevarımsal alt kümelerinin ailesi olsun (\(\mathbb{R} \in \mathcal{T}\) olduğundan aile boş değildir). Bu ailenin kesişimine (Tanım 3.8) doğal sayılar kümesi denir ve \(\mathbb{N}\) ile gösterilir:
\[\mathbb{N} = \bigcap_{A \in \mathcal{T}} A = \{x \in \mathbb{R} : \text{her tümevarımsal } A \subset \mathbb{R} \text{ için } x \in A\}.\]
\(\mathbb{N}\)’nin elemanlarına doğal sayı denir.
Tanım gereği bir \(x\) reel sayısı ancak ve ancak her tümevarımsal kümede bulunuyorsa doğal sayıdır. Bu tanımın işe yaradığını hemen görelim: \(\mathbb{N}\) kendisi tümevarımsaldır ve gerçekten en küçüğüdür.
Önerme 10.1 (Doğal Sayılar En Küçük Tümevarımsal Kümedir)
- \(\mathbb{N}\) tümevarımsal bir kümedir.
- \(A \subset \mathbb{R}\) tümevarımsal ise \(\mathbb{N} \subset A\)’dır.
İspat
Madde (1). Her tümevarımsal \(A\) için \(1 \in A\) olduğundan \(1\) kesişimdedir: \(1 \in \mathbb{N}\). Şimdi \(x \in \mathbb{N}\) olsun. Kesişimin tanımı gereği \(x\) her tümevarımsal \(A\)’nın elemanıdır; her böyle \(A\) tümevarımsal olduğundan \(x + 1 \in A\)’dır. Demek ki \(x + 1\) her tümevarımsal kümede bulunur, yani \(x + 1 \in \mathbb{N}\).
Madde (2). \(A\) tümevarımsal ise \(A \in \mathcal{T}\)’dir ve bir ailenin kesişimi ailenin her üyesinin alt kümesidir (Teorem 3.2 (1)); dolayısıyla \(\mathbb{N} \subset A\).
\(\blacksquare\)
\(1 \in \mathbb{N}\) olduğundan \(2 := 1 + 1\), \(3 := 2 + 1\), \(4 := 3 + 1\), … sayıları da \(\mathbb{N}\)’dedir. Bunlar gerçekten farklı sayılardır: Önerme 7.7 ile \(0 < 1\), (O3) ile \(1 = 1 + 0 < 1 + 1 = 2\); aynı yolla \(2 < 3 < 4 < \cdots\). Ayrıca Örnek 10.1’ndeki \(\{1\} \cup [2, \infty)\) kümesi tümevarımsal olduğundan \(\mathbb{N}\) onun alt kümesidir: \(1\) ile \(2\) arasında doğal sayı yoktur. Bu gözlemi aşağıda genelleştireceğiz.
10.2 Tümevarım İlkesi
“Her doğal sayı için \(P(n)\) doğrudur” türünden bir iddiayı ispatlamak istiyoruz. Sonsuz tane önerme var; teker teker kontrol edemeyiz. Ama doğal sayılar en küçük tümevarımsal küme olduğu için şu strateji işler: \(P\)’nin doğru olduğu sayıların kümesinin tümevarımsal olduğunu göster; o zaman bu küme \(\mathbb{N}\)’nin tamamını kapsar.
Teorem 10.1 (Tümevarım İlkesi)
- Küme biçimi. \(A \subset \mathbb{N}\) tümevarımsal ise \(A = \mathbb{N}\)’dir.
- Önerme biçimi. Her \(n \in \mathbb{N}\) için bir \(P(n)\) önermesi verilmiş olsun. Eğer
- \(P(1)\) doğruysa (temel adım) ve
- her \(k \in \mathbb{N}\) için “\(P(k)\) doğru \(\Rightarrow\) \(P(k+1)\) doğru” ise (tümevarım adımı),
İspat
Madde (1). \(A\) tümevarımsal olduğundan Önerme 10.1 (2) ile \(\mathbb{N} \subset A\). Varsayımla \(A \subset \mathbb{N}\). İki kapsama birlikte \(A = \mathbb{N}\) verir.
Madde (2). \(A = \{n \in \mathbb{N} : P(n) \text{ doğru}\}\) kümesini alalım; açıkça \(A \subset \mathbb{N}\). Temel adım \(1 \in A\) der. Tümevarım adımı şunu der: \(k \in A\) ise (\(P(k)\) doğruysa) \(P(k+1)\) doğrudur; Önerme 10.1 (1) ile \(k + 1 \in \mathbb{N}\) olduğundan \(k + 1 \in A\). Demek ki \(A\) tümevarımsaldır. Madde (1) ile \(A = \mathbb{N}\), yani her \(n \in \mathbb{N}\) için \(P(n)\) doğrudur.
\(\blacksquare\)
Domino benzetmesi tam olarak budur: ilk taşı devirmek (temel adım) ve her taşın bir sonrakini devireceğinden emin olmak (tümevarım adımı), bütün taşların devrileceğini garantiler. Tümevarım adımında “\(P(k)\) doğru” varsayımına tümevarım hipotezi denir; ispatlanan şey \(P(k)\)’nin doğruluğu değil, \(P(k)\)’den \(P(k+1)\)’e geçilebildiğidir.
- İspatlanacak önermeyi \(n\)’ye bağlı olarak açıkça yaz: “\(P(n)\): …”.
- Temel adım: \(P(1)\)’in doğru olduğunu göster (çoğunlukla doğrudan hesap).
- Tümevarım hipotezi: “Bir \(k \in \mathbb{N}\) için \(P(k)\)’nin doğru olduğunu varsayalım.”
- Tümevarım adımı: Bu varsayımdan \(P(k+1)\)’i çıkar. Hipotezi tam olarak nerede kullandığını belirt.
- Sonuç: “Teorem 10.1 gereği \(P(n)\) her \(n \in \mathbb{N}\) için doğrudur.”
Temel adım olmadan tümevarım adımı hiçbir şey kanıtlamaz: “\(P(n)\): \(n \ge 2\)” önermesi için \(P(k) \Rightarrow P(k+1)\) doğrudur (\(k \ge 2\) ise \(k + 1 \ge 2\)) ama \(P(1)\) yanlıştır. Tersine, “\(P(n)\): \(n = 1\)” için temel adım doğru, tümevarım adımı yanlıştır (\(P(1)\) doğru ama \(P(2)\) yanlış). İki adımın da yazılması ve her \(k \in \mathbb{N}\) için geçerli olması gerekir.
İlk örneklerimiz klasik toplam formülleridir. Şimdilik toplamları \(1 + 2 + \cdots + n\) biçiminde yazıyoruz; toplam sembolünün kesin tanımını biraz sonra vereceğiz.
Örnek 10.2 (Ardışık Doğal Sayıların Toplamı) Her \(n \in \mathbb{N}\) için
\[1 + 2 + \cdots + n = \frac{n(n+1)}{2}\]
olduğunu gösteriniz.
Çözüm
\(P(n)\), yukarıdaki eşitlik olsun.
Temel adım. \(n = 1\) için sol taraf \(1\), sağ taraf \(\frac{1 \cdot 2}{2} = 1\). \(P(1)\) doğrudur.
Tümevarım adımı. Bir \(k \in \mathbb{N}\) için \(P(k)\) doğru olsun: \(1 + 2 + \cdots + k = \frac{k(k+1)}{2}\). \(P(k+1)\)’in sol tarafını yazıp hipotezi kullanalım:
\[1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}.\]
Sağdaki ifade, \(P(k+1)\)’in sağ tarafı \(\frac{(k+1)\big((k+1)+1\big)}{2}\) ile aynıdır. Demek ki \(P(k) \Rightarrow P(k+1)\).
Teorem 10.1 gereği \(P(n)\) her \(n \in \mathbb{N}\) için doğrudur.
\(\blacksquare\)
Örnek 10.3 (İlk n Tek Sayının Toplamı) Her \(n \in \mathbb{N}\) için \(1 + 3 + 5 + \cdots + (2n - 1) = n^2\) olduğunu gösteriniz.
Çözüm
Temel adım. \(n = 1\): sol taraf \(2 \cdot 1 - 1 = 1\), sağ taraf \(1^2 = 1\).
Tümevarım adımı. \(1 + 3 + \cdots + (2k - 1) = k^2\) olsun. Bir sonraki tek sayı \(2(k+1) - 1 = 2k + 1\)’dir; onu ekleyelim:
\[1 + 3 + \cdots + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2.\]
Burada ilk eşitlikte tümevarım hipotezi, ikincisinde dağılma aksiyomuyla açılan \((k+1)^2 = k^2 + 2k + 1\) özdeşliği kullanıldı. Böylece \(P(k+1)\) doğrudur ve Teorem 10.1 ile iddia her \(n\) için geçerlidir.
\(\blacksquare\)
10.3 Doğal Sayıların Temel Özellikleri
Doğal sayılar hakkında “bilinen” her şey artık ispat gerektirir; ispatların hepsi tümevarımla yapılır. Önce toplama ve çarpma altında kapalılık.
Önerme 10.2 (Doğal Sayılar Toplama ve Çarpma Altında Kapalıdır) \(m, n \in \mathbb{N}\) ise \(m + n \in \mathbb{N}\) ve \(mn \in \mathbb{N}\)’dir.
İspat
\(m \in \mathbb{N}\) sabit olsun; \(n\) üzerinden tümevarım yapacağız.
Toplama. \(A = \{n \in \mathbb{N} : m + n \in \mathbb{N}\}\) olsun. \(\mathbb{N}\) tümevarımsal olduğundan \(m + 1 \in \mathbb{N}\), yani \(1 \in A\). \(n \in A\) ise \(m + n \in \mathbb{N}\); yine tümevarımsallıkla \((m + n) + 1 \in \mathbb{N}\) ve (A2) ile \((m + n) + 1 = m + (n + 1)\), yani \(n + 1 \in A\). \(A\) tümevarımsaldır; Teorem 10.1 (1) ile \(A = \mathbb{N}\).
Çarpma. \(B = \{n \in \mathbb{N} : mn \in \mathbb{N}\}\) olsun. (M3) ile \(m \cdot 1 = m \in \mathbb{N}\), yani \(1 \in B\). \(n \in B\) ise \(mn \in \mathbb{N}\); (D) ile \(m(n + 1) = mn + m\) ve toplama altında kapalılıkla \(mn + m \in \mathbb{N}\), yani \(n + 1 \in B\). \(B\) tümevarımsaldır, dolayısıyla \(B = \mathbb{N}\).
\(\blacksquare\)
Çıkarma ve bölme için kapalılık yoktur: \(1 - 2\) ve \(\frac{1}{2}\) doğal sayı değildir; ikisi de \(1\)’den küçüktür, oysa aşağıdaki önerme gereği hiçbir doğal sayı \(1\)’den küçük olamaz. Bu eksikler sırasıyla tam sayılar (Tanım 11.1) ve rasyonel sayılarla (Tanım 11.6) giderilecektir.
Şimdi doğal sayıların sayı doğrusundaki dizilişini kesinleştirelim: \(1\) en küçüktür, ardışık iki doğal sayı arasında başka doğal sayı yoktur ve büyük olandan küçüğü çıkarınca yine doğal sayı elde edilir.
Önerme 10.3 (Doğal Sayıların Dizilişi) \(m, n \in \mathbb{N}\) olsun.
- \(n \ge 1\)’dir. Dolayısıyla \(1\), \(\mathbb{N}\)’nin en küçük elemanıdır ve her doğal sayı pozitiftir.
- \(n \ne 1\) ise \(n - 1 \in \mathbb{N}\)’dir; dolayısıyla \(n \ge 2\)’dir.
- \(n < x < n + 1\) koşulunu sağlayan bir \(x \in \mathbb{N}\) yoktur: ardışık iki doğal sayı arasında doğal sayı bulunmaz.
- \(m < n\) ise \(m + 1 \le n\) ve \(n - m \in \mathbb{N}\)’dir.
İspat
Madde (1). \(A = \{n \in \mathbb{N} : n \ge 1\}\) olsun. \(1 \ge 1\) olduğundan \(1 \in A\). \(n \in A\) ise \(n \ge 1\) ve (O3) ile \(n + 1 \ge 1 + 1 = 2 > 1\); dolayısıyla \(n + 1 \in A\). Teorem 10.1 (1) ile \(A = \mathbb{N}\). Pozitiflik \(n \ge 1 > 0\)’dan çıkar.
Madde (2). \(A = \{1\} \cup \{n \in \mathbb{N} : n - 1 \in \mathbb{N}\}\) olsun; \(A \subset \mathbb{N}\)’dir. \(1 \in A\). \(n \in A\) olsun; \(n \in \mathbb{N}\) olduğundan \(n + 1 \in \mathbb{N}\) ve \((n + 1) - 1 = n \in \mathbb{N}\), yani \(n + 1 \in A\). Böylece \(A\) tümevarımsal ve \(A = \mathbb{N}\): her doğal sayı ya \(1\)’dir ya da bir eksiği doğal sayı olan bir sayıdır. \(n \ne 1\) ise \(n - 1 \in \mathbb{N}\), madde (1) ile \(n - 1 \ge 1\), yani \(n \ge 2\).
Madde (3). \(P(n)\): “\(n < x < n + 1\) olan \(x \in \mathbb{N}\) yoktur” önermesi için tümevarım yapalım.
Temel adım. \(1 < x < 2\) olan bir \(x \in \mathbb{N}\) olsaydı \(x \ne 1\) olurdu ve madde (2) ile \(x \ge 2\) gelirdi; bu \(x < 2\) ile çelişir. \(P(1)\) doğrudur.
Tümevarım adımı. \(P(k)\) doğru olsun ve \(k + 1 < x < k + 2\) olan bir \(x \in \mathbb{N}\) bulunduğunu varsayalım. \(x > k + 1 \ge 2 > 1\) olduğundan \(x \ne 1\), madde (2) ile \(x - 1 \in \mathbb{N}\). Eşitsizliklerden \(1\) çıkarınca \(k < x - 1 < k + 1\); bu, \(P(k)\) ile çelişir. Demek ki böyle \(x\) yoktur ve \(P(k+1)\) doğrudur.
Madde (4). Önce \(m + 1 \le n\): üçlem yasası (O1) gereği ya \(m + 1 \le n\) ya da \(n < m + 1\)’dir. İkincisi \(m < n\) ile birleşince \(m < n < m + 1\) verir; madde (3) bunu yasaklar. O hâlde \(m + 1 \le n\).
Şimdi \(n - m \in \mathbb{N}\) olduğunu \(m\) üzerinden tümevarımla gösterelim; \(Q(m)\): “her \(n \in \mathbb{N}\) için, \(m < n\) ise \(n - m \in \mathbb{N}\)”.
Temel adım. \(1 < n\) ise \(n \ne 1\) ve madde (2) ile \(n - 1 \in \mathbb{N}\).
Tümevarım adımı. \(Q(k)\) doğru olsun ve \(n \in \mathbb{N}\), \(k + 1 < n\) olsun. \(k < k + 1 < n\) olduğundan \(Q(k)\) ile \(n - k \in \mathbb{N}\). Ayrıca \(n - k > 1\) olduğundan \(n - k \ne 1\); madde (2) ile \((n - k) - 1 = n - (k + 1) \in \mathbb{N}\). \(Q(k+1)\) doğrudur.
\(\blacksquare\)
Bu önerme ne işe yarar? Doğal sayıların “ayrık” durduğunu söyler: bir doğal sayıya \(1\)’den daha az yaklaşan başka bir doğal sayı yoktur. İleride aynı olguyu tam sayılar için de göstereceğiz — ardışık iki tam sayı arasında tam sayı yoktur (Lemma 11.1, Bölüm 11) — ve Arşimet özelliği (Bölüm 12) buna dayanacaktır.
Önermenin (4). maddesi, bir doğal sayıdan büyük doğal sayıların en küçüğünün tam olarak bir sonraki sayı olduğunu söyler. Bu gözlemi ve iki kullanışlı sonucunu ayrıca kaydedelim.
Sonuç 10.1 (Bir Doğal Sayıyı Aşanların En Küçüğü) \(m, n \in \mathbb{N}\) olsun.
- \(\{k \in \mathbb{N} : n < k\}\) kümesinin en küçük elemanı \(n + 1\)’dir.
- \(n < m + 1\) olması için gerek ve yeter koşul \(n \le m\) olmasıdır.
- \(m \le n \le m + 1\) ise \(n = m\) ya da \(n = m + 1\)’dir.
İspat
Madde (1). \(0 < 1\) olduğundan (Önerme 7.7) (O3) ile \(n < n + 1\); ayrıca \(n + 1 \in \mathbb{N}\)’dir. Demek ki \(n + 1\) kümenin bir elemanıdır. Kümeden herhangi bir \(k\) alalım; \(n < k\) olduğundan Önerme 10.3 (4) ile \(n + 1 \le k\). Kümenin her elemanından küçük ya da ona eşit olan ve kümeye ait olan \(n + 1\), kümenin en küçük elemanıdır.
Madde (2). (\(\Rightarrow\)) \(n < m + 1\) olsun. \(n \le m\) olmadığını varsayalım; üçlem yasası (O1) gereği \(m < n\) olur ve Önerme 10.3 (4) ile \(m + 1 \le n\) çıkar. Bu, \(n < m + 1\) ile çelişir. O hâlde \(n \le m\). (\(\Leftarrow\)) \(n \le m\) ise \(m < m + 1\) olduğundan \(n < m + 1\).
Madde (3). \(n = m + 1\) ise iş biter. Değilse \(n \le m + 1\) eşitsizliği kesindir: \(n < m + 1\). Madde (2) ile \(n \le m\); bunu \(m \le n\) ile birleştirince \(n = m\) bulunur.
\(\blacksquare\)
Örneğin \(n = 5\) için \(\{k \in \mathbb{N} : 5 < k\} = \{6, 7, 8, \dots\}\) ve bu kümenin en küçük elemanı \(6\)’dır. Kümede \(n\) sabit tutulur, \(k\) değişir; her \(n\) için ayrı bir küme elde edilir ve sonucun söylediği, bu kümelerin hepsinin en küçük elemanının var olduğu ve \(n + 1\)’e eşit olduğudur.
Doğal sayıların ikinci büyük özelliği, tümevarım ilkesine denk olan iyi sıralama ilkesidir: doğal sayılardan oluşan boş olmayan her kümenin bir en küçük elemanı vardır. Reel sayılarda bu doğru değildir; \((0, 1)\) aralığının en küçük elemanı yoktur.
Teorem 10.2 (İyi Sıralama İlkesi) \(S \subset \mathbb{N}\) boş olmayan bir küme olsun. \(S\)’nin bir en küçük elemanı vardır: öyle bir \(m \in S\) bulunur ki her \(s \in S\) için \(m \le s\). Bu eleman tektir.
İspat
Teklik kolaydır: \(m\) ve \(m'\) ikisi de en küçük eleman olsa \(m \le m'\) ve \(m' \le m\), dolayısıyla (O1) ile \(m = m'\) olur.
Varlık için olmayana ergi yöntemini kullanalım: \(S\)’nin en küçük elemanı olmasın; \(S = \varnothing\) olduğunu göstereceğiz. Bunun için
\[A = \{n \in \mathbb{N} : k \le n \text{ olan her } k \in \mathbb{N} \text{ için } k \notin S\}\]
kümesinin tümevarımsal olduğunu gösterelim; \(A\), “\(S\)’nin \(n\)’ye kadar hiçbir elemanı olmayan” \(n\)’lerden oluşur.
Temel adım: \(1 \in A\). \(1 \in S\) olsaydı, Önerme 10.3 (1) gereği her \(s \in S\) için \(1 \le s\) olurdu; yani \(1\), \(S\)’nin en küçük elemanı olurdu. Bu, varsayımımızla çelişir; demek ki \(1 \notin S\). \(k \le 1\) olan tek doğal sayı \(k = 1\) olduğundan (\(k \ge 1\)) \(1 \in A\).
Tümevarım adımı. \(n \in A\) olsun; \(n + 1 \in A\) olduğunu gösterelim. Önce \(n + 1 \notin S\): aksi hâlde \(n + 1\) en küçük eleman olurdu. Gerçekten, \(s \in S\) ise \(n \in A\) nedeniyle \(s \le n\) olamaz, yani \(n < s\); Önerme 10.3 (4) ile \(n + 1 \le s\). Bu her \(s \in S\) için geçerli olduğundan \(n + 1 \in S\) olsaydı en küçük eleman olurdu — çelişki. Şimdi \(k \le n + 1\) olan bir \(k \in \mathbb{N}\) alalım. Ya \(k = n + 1\)’dir, o zaman az önce gördüğümüz gibi \(k \notin S\); ya da \(k < n + 1\)’dir, o zaman Önerme 10.3 (4) ile \(k + 1 \le n + 1\), yani \(k \le n\) ve \(n \in A\) nedeniyle \(k \notin S\). Her iki hâlde de \(k \notin S\); demek ki \(n + 1 \in A\).
Teorem 10.1 (1) ile \(A = \mathbb{N}\). Şimdi \(s \in S\) olsa \(s \in \mathbb{N} = A\) olur; \(k = s \le s\) alınca \(s \notin S\) çıkar — çelişki. Demek ki \(S = \varnothing\). Bu, \(S\)’nin boş olmadığı varsayımıyla çelişir; o hâlde \(S\)’nin en küçük elemanı vardır.
\(\blacksquare\)
İyi sıralama ilkesi ne işe yarar? “Bir özelliği sağlayan en küçük doğal sayıyı al” adımına izin verir. Bu adım, Bölüm 12’de taban fonksiyonunun varlığında ve “en küçük karşı örnek” tekniğinde kullanılır: bir iddia bazı doğal sayılar için yanlışsa, yanlış olduğu en küçük \(n\) vardır ve bu \(n\) ile çalışmak çoğu zaman çelişki üretir. Bölüm sonu alıştırmasında iyi sıralamadan tümevarım ilkesinin geri çıktığını göstereceğiz; iki ilke birbirine denktir.
İyi sıralama ilkesi en küçük elemandan söz eder. En büyük eleman için bir koşul gerekir, çünkü \(\mathbb{N}\)’nin kendisinin en büyük elemanı yoktur: her \(n\)’yi \(n + 1\) geçer. Koşul, kümenin bir doğal sayıyı aşmamasıdır.
Teorem 10.3 (Doğal Sayılarda Maksimum İlkesi) \(S \subset \mathbb{N}\) boş olmayan bir küme olsun ve her \(s \in S\) için \(s \le b\) olacak biçimde bir \(b \in \mathbb{N}\) bulunsun. O zaman \(S\)’nin bir en büyük elemanı vardır: öyle bir \(k \in S\) bulunur ki her \(s \in S\) için \(s \le k\).
İspat
\(S\)’yi aşmayan doğal sayıların kümesine bakalım:
\[B = \{n \in \mathbb{N} : \text{her } s \in S \text{ için } s \le n\}.\]
\(b \in B\) olduğundan \(B\) boş değildir. Teorem 10.2 ile \(B\)’nin en küçük elemanı vardır; ona \(k\) diyelim. \(k \in B\) olduğundan her \(s \in S\) için \(s \le k\)’dır. Geriye \(k \in S\) olduğunu göstermek kalıyor.
\(k = 1\) hâli. \(S\) boş olmadığından bir \(s \in S\) vardır. \(s \le k = 1\) ve Önerme 10.3 (1) ile \(s \ge 1\); dolayısıyla \(s = 1 = k\) ve \(k \in S\).
\(k \ne 1\) hâli. Önerme 10.3 (2) ile \(k - 1 \in \mathbb{N}\)’dir. \(k - 1 < k\) ve \(k\), \(B\)’nin en küçük elemanı olduğundan \(k - 1 \notin B\); yani \(k - 1 < s_0\) olan bir \(s_0 \in S\) vardır. Öte yandan \(s_0 \le k = (k - 1) + 1\). Sonuç 10.1 (3)’ü \(m = k - 1\) ile uygularsak \(s_0 = k - 1\) ya da \(s_0 = k\) bulunur; \(k - 1 < s_0\) olduğundan \(s_0 = k\)’dır. Demek ki \(k \in S\).
Her iki hâlde \(k\) hem \(S\)’nin elemanı hem de bütün elemanlarından büyük ya da onlara eşittir; \(k\), \(S\)’nin en büyük elemanıdır.
\(\blacksquare\)
Teoremde \(b\)’nin doğal sayı olması istendi. Bölümün sonunda \(\mathbb{N}\)’nin üstten sınırlı olmadığını göstereceğiz (Teorem 10.9). O zaman \(b\) herhangi bir reel sayı da olabilir, çünkü her reel sayıyı aşan bir doğal sayı vardır. Aynı ilkenin tam sayılar için biçimi Teorem 11.2’dir.
Maksimum kavramına ilişkin bir başka temel olgu, sonlu kümelerle ilgilidir. Supremum bölümünde ifade edip ispatını tümevarıma ertelemiştik.
Önerme 10.4 (Sonlu Kümelerde Maksimum ve Minimum) \(n \in \mathbb{N}\) olsun. Elemanları \(a_1, a_2, \dots, a_n\) olan her \(A = \{a_1, \dots, a_n\} \subset \mathbb{R}\) kümesinin maksimumu ve minimumu vardır.
İspat
\(n\) üzerinden tümevarım yapalım (Teorem 10.1). \(n = 1\) için \(A = \{a_1\}\) ve \(\max A = \min A = a_1\)’dir.
İddia \(n\) elemanlı kümeler için doğru olsun; \(A = \{a_1, \dots, a_n, a_{n+1}\}\) alalım. \(A' = \{a_1, \dots, a_n\}\) kümesinin tümevarım varsayımıyla bir maksimumu vardır, buna \(M'\) diyelim. \(M = \max\{M', a_{n+1}\}\) olsun (Tanım 7.4). \(M\), \(A\)’nın elemanıdır, çünkü ya \(M'\) ya da \(a_{n+1}\)’e eşittir. Ayrıca \(M\) bir üst sınırdır: \(a_i \in A'\) için \(a_i \le M' \le M\) ve \(a_{n+1} \le M\). Demek ki \(M = \max A\). Minimum için aynı akıl yürütme \(\min\{m', a_{n+1}\}\) ile yapılır.
\(\blacksquare\)
10.4 Peano Aksiyomları
Doğal sayıları reel sayıların içinde, en küçük tümevarımsal küme olarak bulduk. Doğal sayılara ikinci klasik yaklaşım bunun tersidir: \(\mathbb{N}\) hiçbir sayı sisteminden yararlanmadan, birkaç basit aksiyomla doğrudan betimlenir. Bu aksiyomları İtalyan matematikçi Giuseppe Peano (1858–1932) 1889’da yayımlamıştır. Aksiyomlar sayma eyleminin özünü yakalar: bir başlangıç vardır ve her sayının bir “sonraki”si vardır.
Tanım 10.3 (Peano Aksiyomları) Bir \(\mathbb{N}\) kümesi, bir \(1\) elemanı ve her \(n \in \mathbb{N}\)’ye \(n^{+}\) ile gösterilen bir ardıl (successor) eleman karşılık getiren bir kural verilmiş olsun. Aşağıdaki beş özelliğe Peano aksiyomları (Peano axioms) denir.
(P1) \(1 \in \mathbb{N}\).
(P2) Her \(n \in \mathbb{N}\) için ardıl \(n^{+}\) tek türlü belirlidir ve \(n^{+} \in \mathbb{N}\)’dir.
(P3) \(m, n \in \mathbb{N}\) ve \(m^{+} = n^{+}\) ise \(m = n\)’dir.
(P4) Her \(n \in \mathbb{N}\) için \(n^{+} \ne 1\)’dir.
(P5) (Tümevarım aksiyomu) Bir \(A \subset \mathbb{N}\) kümesi için \(1 \in A\) ise ve her \(n \in A\) için \(n^{+} \in A\) ise \(A = \mathbb{N}\)’dir.
Yani her aksiyom saymanın bir özelliğini dile getirir:
- (P1) sayma bir yerden başlar;
- (P2) her sayıdan sonra bir sayı gelir;
- (P3) farklı iki sayının ardılları farklıdır, yani iki ayrı sayma kolu aynı sayıda birleşmez;
- (P4) sayma hiçbir zaman \(1\)’e geri dönmez;
- (P5) \(1\)’den başlayıp ardıl alarak ulaşılamayan “yabancı” bir eleman yoktur.
Aşağıdaki şekil, aksiyomlardan biri bozulunca neler olabileceğini gösteriyor.
Şekildeki üç yapıyı tek tek inceleyelim; her birinde yalnızca bir aksiyom bozuluyor.
Örnek 10.4 (İki Okun Aynı Sayıya Vardığı Yapı) \(X = \{1, 2, 3\}\) kümesinde ardıl kuralı \(1^{+} = 2\), \(2^{+} = 3\), \(3^{+} = 3\) olsun. Peano aksiyomlarından hangilerinin sağlandığını belirleyiniz.
Çözüm
(P1): \(1 \in X\). (P2): her elemanın tek bir ardılı vardır ve ardıllar \(2, 3, 3\) olup hepsi \(X\)’tedir.
(P4): ardıllar \(2, 3, 3\)’tür ve hiçbiri \(1\) değildir; sağlanır.
(P5): \(A \subset X\), \(1 \in A\) ve \(A\) ardıl almaya kapalı olsun. \(1 \in A\) olduğundan \(1^{+} = 2 \in A\), buradan \(2^{+} = 3 \in A\); demek ki \(A = X\). Sağlanır.
(P3) ise bozulur: \(2^{+} = 3 = 3^{+}\) ama \(2 \ne 3\). Bu yapıda sayma \(3\)’te takılır kalır.
\(\blacksquare\)
Örnek 10.5 (Başa Dönen Sayma) \(X = \{1, 2, 3\}\) kümesinde ardıl kuralı \(1^{+} = 2\), \(2^{+} = 3\), \(3^{+} = 1\) olsun. Peano aksiyomlarından hangilerinin sağlandığını belirleyiniz.
Çözüm
(P1) ve (P2) açıktır. (P3): ardıllar \(2, 3, 1\) birbirinden farklıdır; farklı elemanların ardılları farklı olduğundan sağlanır. (P5): bir önceki örnekteki gibi \(1 \in A\) ise \(2 \in A\) ve \(3 \in A\) olur, yani \(A = X\); sağlanır.
(P4) bozulur: \(3^{+} = 1\). Sayma \(1, 2, 3\)’ten sonra yeniden \(1\)’e döner; böyle bir yapıda “sonsuz sayıda sayı” yoktur.
\(\blacksquare\)
Örnek 10.6 (Ulaşılamayan Bir Kol) \(X = \mathbb{N} \cup \left\{\dfrac{1}{2}, \dfrac{3}{2}, \dfrac{5}{2}, \dots\right\}\), yani \(X = \mathbb{N} \cup \left\{n - \dfrac{1}{2} : n \in \mathbb{N}\right\}\) olsun ve her \(x \in X\) için ardıl \(x^{+} = x + 1\) ile tanımlansın. Peano aksiyomlarından hangilerinin sağlandığını belirleyiniz.
Çözüm
(P1): \(1 \in \mathbb{N} \subset X\).
(P2): \(x \in \mathbb{N}\) ise \(x + 1 \in \mathbb{N}\); \(x = n - \dfrac{1}{2}\) ise \(x + 1 = (n + 1) - \dfrac{1}{2}\) ve \(n + 1 \in \mathbb{N}\). Her iki hâlde \(x + 1 \in X\).
(P3): \(x + 1 = y + 1\) ise Önerme 6.3 ile \(x = y\).
(P4): \(x + 1 = 1\) olsaydı \(x = 0\) olurdu. Ama \(X\)’in her elemanı pozitiftir: doğal sayılar \(1\)’den büyük ya da \(1\)’e eşittir ve \(n - \dfrac{1}{2} \ge 1 - \dfrac{1}{2} = \dfrac{1}{2}\). Demek ki \(0 \notin X\) ve (P4) sağlanır.
(P5) bozulur: \(A = \mathbb{N}\) alalım. \(1 \in A\) ve her \(n \in A\) için \(n + 1 \in A\)’dır; ama \(A \ne X\), çünkü \(\dfrac{1}{2} \in X\) ve her doğal sayı \(1\)’den büyük ya da ona eşit olduğundan \(\dfrac{1}{2} \notin \mathbb{N}\). \(\dfrac{1}{2}, \dfrac{3}{2}, \dots\) elemanlarına \(1\)’den başlayıp ardıl alarak hiçbir zaman ulaşılamaz.
\(\blacksquare\)
Örnekler, beş aksiyomun her birinin gerçekten bir iş gördüğünü gösteriyor. Şimdi bizim kurduğumuz \(\mathbb{N}\)’nin beşini de sağladığını görelim.
Önerme 10.5 (Doğal Sayılar Peano Aksiyomlarını Sağlar) Tanım 10.2 ile tanımlanan \(\mathbb{N}\) kümesi, \(1\) elemanı ve \(n^{+} = n + 1\) ardıl kuralıyla (P1)–(P5) aksiyomlarını sağlar.
İspat
(P1) Önerme 10.1 (1) gereği \(1 \in \mathbb{N}\).
(P2) Toplama bir işlem olduğundan \(n + 1\) tek türlü belirlidir. Aynı önermenin (1). maddesi gereği \(n \in \mathbb{N}\) ise \(n + 1 \in \mathbb{N}\).
(P3) \(m + 1 = n + 1\) ise Önerme 6.3 ile \(m = n\).
(P4) Önerme 10.3 (1) gereği \(n \ge 1 > 0\). (O3) ile \(n + 1 > 0 + 1 = 1\); dolayısıyla \(n + 1 \ne 1\).
(P5) \(A \subset \mathbb{N}\), \(1 \in A\) ve her \(n \in A\) için \(n + 1 \in A\) ise \(A\) tümevarımsaldır. Teorem 10.1 (1) ile \(A = \mathbb{N}\).
\(\blacksquare\)
Böylece iki yaklaşım aynı yere varır. Peano yolunda (P1)–(P5) aksiyom olarak kabul edilir. Toplama, çarpma ve sıralama ardıl kuralıyla özyineli olarak tanımlanır. Ardından tam sayılar, rasyonel sayılar ve reel sayılar adım adım inşa edilir. Biz ters yönden gittik: reel sayıları aksiyomlarla verdik ve doğal sayıları onların içinde bulduk. Bu yüzden Peano’nun aksiyomları bizim için ispatlanmış birer teoremdir. (P5)’in tümevarım ilkesinin ta kendisi olduğuna dikkat edelim: tümevarımla yapılan her ispat, son kertede bu aksiyoma dayanır.
10.5 Özyineli Tanımlar
Tümevarım yalnızca ispat aracı değil, tanım aracıdır da. “\(a^n\): \(a\)’nın \(n\) kez kendisiyle çarpımı” ifadesindeki “\(n\) kez” gizli bir üç noktadır. Kesin tanım, \(n = 1\) için değeri verip \(n\)’den \(n + 1\)’e geçiş kuralını söyler; tümevarım ilkesi bu kuralın her \(n\) için tek bir değer belirlediğini garantiler.
Tanım 10.4 (Kuvvet, Faktöriyel, Toplam ve Çarpım Sembolleri) \(a \in \mathbb{R}\) ve her \(k \in \mathbb{N}\) için bir \(a_k \in \mathbb{R}\) verilmiş olsun.
- Doğal kuvvet: \(a^1 = a\) ve her \(n \in \mathbb{N}\) için \(a^{n+1} = a^n \cdot a\). Ayrıca \(a \ne 0\) için \(a^0 = 1\) kabul edilir.
- Faktöriyel: \(0! = 1\), \(1! = 1\) ve her \(n \in \mathbb{N}\) için \((n + 1)! = (n + 1) \cdot n!\).
- Toplam ve çarpım sembolleri:
\[\sum_{k=1}^{1} a_k = a_1, \qquad \sum_{k=1}^{n+1} a_k = \left(\sum_{k=1}^{n} a_k\right) + a_{n+1}; \qquad \prod_{k=1}^{1} a_k = a_1, \qquad \prod_{k=1}^{n+1} a_k = \left(\prod_{k=1}^{n} a_k\right) \cdot a_{n+1}.\]
\(\sum_{k=1}^{n} a_k\) yerine \(a_1 + a_2 + \cdots + a_n\), \(\prod_{k=1}^{n} a_k\) yerine \(a_1 a_2 \cdots a_n\) da yazılır.
Bu tür tanımlara özyineli (recursive) tanım denir. Örneğin \(a^3 = a^2 \cdot a = (a \cdot a) \cdot a\), \(4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2 \cdot 1 = 24\) ve \(n! = \prod_{k=1}^{n} k\)’dır. Kuvvetlerin \(a^m a^n = a^{m+n}\) gibi kuralları tümevarımla ispatlanır; bunları üs tam sayı olacak biçimde genişlettikten sonra Teorem 11.3 olarak vereceğiz. Aşağıdaki hesaplarda yalnızca tanımın kendisini, yani \(a^{n+1} = a^n \cdot a\) eşitliğini kullanacağız. Bir de tanımdan tümevarımla çıkan şu olguyu kaydedelim: \(a > 0\) ise her \(n \in \mathbb{N}\) için \(a^n > 0\), \(a \ge 0\) ise \(a^n \ge 0\)’dır (temel adım \(a^1 = a\); adımda \(a^{n+1} = a^n \cdot a\) çarpımına Önerme 7.5 (1) ya da Önerme 6.9 uygulanır). Aşağıda bunu \(2^{k-1} > 0\) ve \(x^k \ge 0\) biçiminde kullanacağız.
“\(a^n\) her \(n\) için tanımlıdır” iddiası, \(A = \{n \in \mathbb{N} : a^n \text{ tanımlı}\}\) kümesinin tümevarımsal olmasından çıkar: \(a^1\) tanımlıdır ve \(a^n\) tanımlıysa \(a^{n+1} = a^n \cdot a\) da tanımlıdır. Tanımlanan değerin tek olduğu da benzer bir tümevarımla görülür. Bu iki gözlemin genel biçimine özyineleme teoremi denir; biz onu bu düzeyde verilmiş kabul edeceğiz.
Artık daha zengin tümevarım örnekleri yapabiliriz.
Örnek 10.7 (Üstel Büyüme Doğrusalı Geçer) Her \(n \in \mathbb{N}\) için \(2^n > n\) olduğunu gösteriniz.
Çözüm
Temel adım. \(2^1 = 2 > 1\).
Tümevarım adımı. \(2^k > k\) olsun. Tanımla \(2^{k+1} = 2^k \cdot 2 = 2^k + 2^k\). Hipotezle \(2^k > k\) ve Önerme 10.3 (1) ile \(2^k > k \ge 1\); ikisini taraf tarafa toplayalım:
\[2^{k+1} = 2^k + 2^k > k + 1.\]
\(P(k+1)\) doğrudur; Teorem 10.1 ile iddia her \(n\) için geçerlidir.
\(\blacksquare\)
Örnek 10.8 (Faktöriyel Üstelden Hızlı Büyür) Her \(n \in \mathbb{N}\) için \(n! \ge 2^{\,n-1}\) olduğunu gösteriniz.
Çözüm
Temel adım. \(n = 1\): \(1! = 1\) ve \(2^{0} = 1\); \(1 \ge 1\).
Tümevarım adımı. \(k! \ge 2^{k-1}\) olsun. Tanımla \((k+1)! = (k+1) \cdot k!\). Hipotezi pozitif sayı \(k + 1\) ile çarparsak (O4) \((k+1)! \ge (k+1) \cdot 2^{k-1}\). Öte yandan \(k \ge 1\) olduğundan \(k + 1 \ge 2\); bunu pozitif sayı \(2^{k-1}\) ile çarpınca \((k + 1) \cdot 2^{k-1} \ge 2 \cdot 2^{k-1} = 2^{k}\). Geçişlilikle \((k+1)! \ge 2^{k} = 2^{(k+1)-1}\).
(Burada \(k = 1\) için \(2^{k-1} = 2^0 = 1\) kabulü ve \(2^0 \cdot 2 = 2^1\) eşitliği kullanıldı; \(k \ge 2\) için \(2^{k-1} \cdot 2 = 2^k\) doğrudan tanımdır.)
\(\blacksquare\)
Örnek 10.9 (Bir Bölünebilme Özelliği) Her \(n \in \mathbb{N}\) için \(8^n - 1 = 7m\) olacak biçimde bir \(m \in \mathbb{N}\) bulunduğunu gösteriniz. (Bölünebilme dilinde: \(8^n - 1\), \(7\)’ye bölünür; bkz. Tanım 11.3.)
Çözüm
Temel adım. \(8^1 - 1 = 7 = 7 \cdot 1\); \(m = 1\) işe yarar.
Tümevarım adımı. \(8^k - 1 = 7m\) olacak bir \(m \in \mathbb{N}\) bulunsun; yani \(8^k = 7m + 1\). O zaman
\[8^{k+1} - 1 = 8^k \cdot 8 - 1 = (7m + 1) \cdot 8 - 1 = 56m + 8 - 1 = 56m + 7 = 7(8m + 1).\]
Önerme 10.2 ile \(8m + 1 \in \mathbb{N}\); demek ki \(m' = 8m + 1\) istenen özelliktedir. Teorem 10.1 ile iddia her \(n\) için doğrudur.
\(\blacksquare\)
Analizde en sık karşılaşılan sonlu toplam, ardışık terimleri aynı oranla büyüyen ya da küçülen toplamdır. Formülü ileride dizilerde ve serilerde tekrar tekrar kullanacağız.
Örnek 10.10 (Geometrik Toplam Formülü) \(r \ne 1\) bir reel sayı olsun. Her \(n \in \mathbb{N}\) için
\[1 + r + r^2 + \cdots + r^n = \frac{1 - r^{n+1}}{1 - r}\]
olduğunu gösteriniz.
Çözüm
Soldaki ilk terim \(1\), \(r^0\)’ın yerini tutar; \(r = 0\) hâlinde de iki taraf \(1\)’e eşittir. \(r \ne 1\) olduğundan \(1 - r \ne 0\)’dır ve sağ taraf tanımlıdır.
Temel adım. \(n = 1\) için sol taraf \(1 + r\)’dir. Sağ taraf, \(1 - r^2 = (1 - r)(1 + r)\) olduğundan
\[\frac{1 - r^2}{1 - r} = \frac{(1 - r)(1 + r)}{1 - r} = 1 + r\]
olur. \(P(1)\) doğrudur.
Tümevarım adımı. Bir \(k \in \mathbb{N}\) için \(1 + r + \cdots + r^k = \dfrac{1 - r^{k+1}}{1 - r}\) olsun. Toplama bir sonraki terim olan \(r^{k+1}\)’i ekleyip hipotezi kullanalım:
\[ \begin{aligned} 1 + r + \cdots + r^k + r^{k+1} &= \frac{1 - r^{k+1}}{1 - r} + r^{k+1} \\[1mm] &= \frac{1 - r^{k+1} + r^{k+1}(1 - r)}{1 - r} \\[1mm] &= \frac{1 - r^{k+2}}{1 - r}. \end{aligned} \]
Son adımda \(r^{k+1} \cdot r = r^{k+2}\) eşitliği, yani kuvvetin tanımı kullanıldı. Elde edilen ifade \(P(k+1)\)’in sağ tarafıdır. Teorem 10.1 gereği formül her \(n \in \mathbb{N}\) için doğrudur.
Bir sağlama yapalım. \(r = \dfrac{1}{2}\), \(n = 3\) için sol taraf \(1 + \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{1}{8} = \dfrac{15}{8}\)’dir. Sağ taraf \(\dfrac{1 - \frac{1}{16}}{1 - \frac{1}{2}} = \dfrac{15}{16} \cdot 2 = \dfrac{15}{8}\)’dir. \(r = 2\), \(n = 3\) için ise \(1 + 2 + 4 + 8 = 15 = \dfrac{1 - 16}{1 - 2}\) bulunur.
\(\blacksquare\)
\(r = 1\) hâli formülün dışında kalır, çünkü payda sıfır olur. O durumda toplamdaki \(n + 1\) terimin hepsi \(1\)’dir ve toplam \(n + 1\)’e eşittir.
10.6 Tümevarımın Değişik Biçimleri
Bazı iddialar ancak belli bir \(n_0\)’dan sonra doğrudur; bazılarında ise \(P(k+1)\)’i göstermek için yalnızca \(P(k)\) değil, öncekilerin tamamı gerekir. Tümevarım ilkesi her iki duruma da uyarlanır.
Teorem 10.4 (Bir n₀’dan Başlayan Tümevarım) \(n_0 \in \mathbb{N}\) ve her \(n \ge n_0\) doğal sayısı için bir \(P(n)\) önermesi verilmiş olsun. Eğer \(P(n_0)\) doğruysa ve \(n_0 \le k\) olan her \(k \in \mathbb{N}\) için \(P(k) \Rightarrow P(k+1)\) ise, \(n \ge n_0\) olan her \(n \in \mathbb{N}\) için \(P(n)\) doğrudur.
İspat
Her \(m \in \mathbb{N}\) için \(Q(m) := P(n_0 + m - 1)\) diyelim. Bu tanımlıdır: \(m = 1\) için \(n_0 + m - 1 = n_0\); \(m \ge 2\) için Önerme 10.3 (2) ile \(m - 1 \in \mathbb{N}\), Önerme 10.2 ile \(n_0 + (m - 1) \in \mathbb{N}\) ve \(m - 1 \ge 1\) olduğundan \(n_0 + m - 1 \ge n_0\). \(Q(1) = P(n_0)\) doğrudur. \(Q(m)\) doğruysa \(k = n_0 + m - 1 \ge n_0\) için \(P(k)\) doğrudur, varsayımla \(P(k+1) = P(n_0 + (m+1) - 1) = Q(m+1)\) doğrudur. Teorem 10.1 ile her \(m \in \mathbb{N}\) için \(Q(m)\) doğrudur.
Şimdi \(n \ge n_0\) olsun. \(n = n_0\) ise \(P(n) = Q(1)\) doğrudur. \(n > n_0\) ise Önerme 10.3 (4) ile \(n - n_0 \in \mathbb{N}\); \(m = (n - n_0) + 1 \in \mathbb{N}\) alınca \(n_0 + m - 1 = n\), yani \(P(n) = Q(m)\) doğrudur.
\(\blacksquare\)
Örnek 10.11 (Bir Yerden Sonra Doğru Olan Eşitsizlik) \(n \ge 3\) olan her \(n \in \mathbb{N}\) için \(n^2 > 2n + 1\) olduğunu gösteriniz.
Çözüm
\(n = 1\) ve \(n = 2\) için iddia yanlıştır (\(1 < 3\), \(4 < 5\)); bu yüzden \(n_0 = 3\)’ten başlıyoruz.
Temel adım. \(3^2 = 9 > 7 = 2 \cdot 3 + 1\).
Tümevarım adımı. \(k \ge 3\) ve \(k^2 > 2k + 1\) olsun. O zaman
\[(k+1)^2 = k^2 + 2k + 1 > (2k + 1) + 2k + 1 = 4k + 2 = 2(k+1) + 2k \ge 2(k+1) + 1,\]
çünkü \(k \ge 1\) nedeniyle \(2k \ge 2 > 1\). Böylece \((k+1)^2 > 2(k+1) + 1\) ve Teorem 10.4 ile iddia her \(n \ge 3\) için doğrudur.
\(\blacksquare\)
Teorem 10.5 (Güçlü Tümevarım) Her \(n \in \mathbb{N}\) için bir \(P(n)\) önermesi verilmiş olsun. Eğer \(P(1)\) doğruysa ve her \(k \in \mathbb{N}\) için
\[P(1), P(2), \dots, P(k) \text{ doğru} \ \Longrightarrow\ P(k+1) \text{ doğru}\]
ise, her \(n \in \mathbb{N}\) için \(P(n)\) doğrudur.
İspat
\(Q(n)\): “\(j \le n\) olan her \(j \in \mathbb{N}\) için \(P(j)\) doğru” önermesini alalım ve \(Q\) için sıradan tümevarım yapalım. \(j \le 1\) olan tek doğal sayı \(1\)’dir; \(P(1)\) doğru olduğundan \(Q(1)\) doğrudur. \(Q(k)\) doğru olsun: \(P(1), \dots, P(k)\) doğrudur. Varsayımla \(P(k+1)\) doğrudur. \(j \le k + 1\) olan bir \(j \in \mathbb{N}\) ya \(j = k + 1\)’dir ya da \(j < k + 1\), yani Önerme 10.3 (4) ile \(j \le k\)’dır; her iki hâlde \(P(j)\) doğrudur. Demek ki \(Q(k+1)\) doğrudur. Teorem 10.1 ile her \(n\) için \(Q(n)\), özel olarak \(P(n)\) doğrudur.
\(\blacksquare\)
Güçlü tümevarım, sıradan tümevarımdan daha güçlü bir ilke değildir — ispat gösteriyor ki ondan çıkar — ama tümevarım adımında bütün önceki durumları kullanabilmek bazı ispatları çok kolaylaştırır. Tipik örnek, her terimi önceki iki terime bağlı olan dizilerdir.
Örnek 10.12 (Fibonacci Sayıları) \(F_1 = 1\), \(F_2 = 1\) ve her \(n \in \mathbb{N}\) için \(F_{n+2} = F_{n+1} + F_n\) olsun (özyineli tanım: \(1, 1, 2, 3, 5, 8, 13, \dots\)). Her \(n \in \mathbb{N}\) için \(F_n < 2^n\) olduğunu gösteriniz.
Çözüm
Güçlü tümevarım kullanacağız, çünkü \(F_{k+1}\)’i sınırlamak için hem \(F_k\) hem \(F_{k-1}\) gerekir.
Temel adımlar. \(F_1 = 1 < 2 = 2^1\) ve \(F_2 = 1 < 4 = 2^2\).
Tümevarım adımı. \(k \ge 2\) olsun ve \(j \le k\) olan her \(j\) için \(F_j < 2^j\) doğru olsun. \(k \ge 2\) olduğundan \(k - 1 \in \mathbb{N}\) ve \(F_{k+1} = F_k + F_{k-1}\) yazılabilir. Hipotezle
\[F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} < 2^k + 2^k = 2^k \cdot 2 = 2^{k+1}.\]
Ortadaki adımda \(2^{k-1} < 2^{k-1} \cdot 2 = 2^k\) kullanıldı (\(2^{k-1} > 0\) olduğundan). Adımı \(k \ge 2\) için yazmamız yeterlidir: güçlü tümevarımın \(k = 1\) için istediği “\(P(1) \Rightarrow P(2)\)” koşulu, \(P(2)\) temel adımda doğrudan gösterildiği için zaten sağlanır. Teorem 10.5 ile iddia her \(n\) için doğrudur.
\(\blacksquare\)
10.7 Bernoulli Eşitsizliği
Bir kuvvetin alttan basit bir sınırı, analizde sürekli lazım olur: \((1 + x)^n\) ifadesi \(1 + nx\)’ten küçük değildir. Sezgi, \(x \ge 0\) için binom açılımından gelir (\(1 + nx\) açılımın ilk iki terimidir); ama eşitsizlik \(x \ge -1\) için de doğrudur.
Teorem 10.6 (Bernoulli Eşitsizliği) \(x \ge -1\) ve \(n \in \mathbb{N}\) ise
\[(1 + x)^n \ge 1 + nx.\]
İspat
\(n\) üzerinden tümevarım.
Temel adım. \((1 + x)^1 = 1 + x = 1 + 1 \cdot x\); eşitlik vardır.
Tümevarım adımı. \((1 + x)^k \ge 1 + kx\) olsun. \(x \ge -1\) olduğundan \(1 + x \ge 0\)’dır. \(1 + x = 0\) ise \((1+x)^{k+1} = 0 \ge 1 + (k+1)(-1) = -k\), doğrudur. \(1 + x > 0\) ise hipotezi bu pozitif sayıyla çarpabiliriz (O4):
\[(1 + x)^{k+1} = (1 + x)^k (1 + x) \ge (1 + kx)(1 + x) = 1 + (k + 1)x + kx^2.\]
Önerme 7.12 (1) ile \(x^2 \ge 0\) ve \(k > 0\) olduğundan \(kx^2 \ge 0\); dolayısıyla \(1 + (k+1)x + kx^2 \ge 1 + (k+1)x\). Geçişlilikle \((1 + x)^{k+1} \ge 1 + (k+1)x\).
\(\blacksquare\)
Bernoulli eşitsizliği ne işe yarar? \(x > 0\) için \((1 + x)^n \ge 1 + nx\) sağ tarafı \(n\) büyüdükçe her sınırı aşar (bunu bir sonraki bölümde, doğal sayıların üstten sınırsızlığıyla kanıtlayacağız); dolayısıyla \(1\)’den büyük bir sayının kuvvetleri de her sınırı aşar. \(x = 1\) için \(2^n \ge 1 + n\), Örnek 10.7’nin başka bir ispatıdır. Dizilerde \(q^n \to 0\) (\(|q| < 1\)) ve \(\sqrt[n]{a} \to 1\) sonuçları doğrudan bu eşitsizlikle kanıtlanacaktır.
\(x > -1\), \(x \ne 0\) ve \(n \ge 2\) ise eşitsizlik kesindir: \((1+x)^n > 1 + nx\). İspat aynıdır; \(n = 2\) temel adımında \((1+x)^2 = 1 + 2x + x^2 > 1 + 2x\) (\(x^2 > 0\)) ve tümevarım adımında \(kx^2 > 0\) kullanılır.
10.8 Binom Teoremi
\((a + b)^2 = a^2 + 2ab + b^2\) ve \((a+b)^3 = a^3 + 3a^2 b + 3ab^2 + b^3\) açılımlarını biliyoruz. Genel \(n\) için katsayıları veren sayılar binom katsayılarıdır.
Tanım 10.5 (Binom Katsayısı) \(n \in \mathbb{N}\) ve \(k \in \{0, 1, \dots, n\}\) için
\[\binom{n}{k} = \frac{n!}{k!\,(n-k)!}\]
sayısına binom katsayısı denir ve “\(n\)’nin \(k\)’lısı” diye okunur. (\(k < n\) iken \(n - k \in \mathbb{N}\), \(k = n\) iken \(n - k = 0\) olduğundan payda tanımlıdır.)
Tanımdan hemen çıkan değerler: \(\binom{n}{0} = \binom{n}{n} = 1\), \(\binom{n}{1} = \binom{n}{n-1} = n\) ve simetri \(\binom{n}{k} = \binom{n}{n-k}\) (payda aynı iki çarpandan oluşur). Binom katsayılarını satır satır dizince Pascal üçgeni ortaya çıkar; her sayı, üstündeki iki sayının toplamıdır:
\[\begin{array}{ccccccccc} & & & & 1 & & & & \\ & & & 1 & & 1 & & & \\ & & 1 & & 2 & & 1 & & \\ & 1 & & 3 & & 3 & & 1 & \\ 1 & & 4 & & 6 & & 4 & & 1 \end{array}\]
Bu “üstündeki ikisinin toplamı” kuralı, binom teoreminin ispatındaki temel adımdır.
Lemma 10.1 (Pascal Özdeşliği) \(n \in \mathbb{N}\) ve \(1 \le k \le n\) için
\[\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}.\]
İspat
Faktöriyelin özyineli tanımıyla \(k! = k \cdot (k-1)!\) ve \((n - k + 1)! = (n - k + 1) \cdot (n - k)!\)’dir (\(k = 1\) ve \(k = n\) hâllerinde bu eşitlikler \(1! = 1 \cdot 0!\) biçimini alır; iki yan da \(1\)’dir). Ortak paydaya getirelim:
\[\binom{n}{k-1} + \binom{n}{k} = \frac{n!}{(k-1)!\,(n-k+1)!} + \frac{n!}{k!\,(n-k)!} = \frac{n! \cdot k}{k!\,(n-k+1)!} + \frac{n! \cdot (n-k+1)}{k!\,(n-k+1)!}.\]
Payları toplayınca \(n!\,\big(k + (n - k + 1)\big) = n!\,(n+1) = (n+1)!\) olur; dolayısıyla toplam
\[\frac{(n+1)!}{k!\,\big((n+1)-k\big)!} = \binom{n+1}{k}.\]
\(\blacksquare\)
Teorem 10.7 (Binom Teoremi) \(a, b \in \mathbb{R}\) ve \(n \in \mathbb{N}\) için
\[(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{\,n-k} b^{\,k} = a^n + \binom{n}{1} a^{n-1} b + \binom{n}{2} a^{n-2} b^2 + \cdots + \binom{n}{n-1} a\, b^{n-1} + b^n.\]
Burada \(a^0\) ve \(b^0\) çarpanları, \(a\) ya da \(b\) sıfır olsa bile \(1\) olarak okunur; toplam da \(k = 0\)’dan başladığı için Tanım 10.4 (3)’ün \(k = 0\) terimi eklenmiş biçimidir.
İspat
\(n\) üzerinden tümevarım.
Temel adım. \(n = 1\): sağ taraf \(\binom{1}{0} a + \binom{1}{1} b = a + b = (a+b)^1\).
Tümevarım adımı. Eşitlik \(n = k\) için doğru olsun. Kuvvetin tanımı ve dağılma aksiyomuyla
\[(a+b)^{k+1} = (a+b)^k (a+b) = \left(\sum_{j=0}^{k} \binom{k}{j} a^{k-j} b^{j}\right) a + \left(\sum_{j=0}^{k} \binom{k}{j} a^{k-j} b^{j}\right) b = \sum_{j=0}^{k} \binom{k}{j} a^{k+1-j} b^{j} + \sum_{j=0}^{k} \binom{k}{j} a^{k-j} b^{j+1}.\]
İkinci toplamda \(j + 1 = i\) diyerek indisi kaydıralım; \(j\), \(0\)’dan \(k\)’ya giderken \(i\), \(1\)’den \(k+1\)’e gider:
\[\sum_{j=0}^{k} \binom{k}{j} a^{k-j} b^{j+1} = \sum_{i=1}^{k+1} \binom{k}{i-1} a^{k+1-i} b^{i}.\]
Şimdi iki toplamı, ortak \(a^{k+1-i} b^{i}\) terimlerine göre birleştirelim. Birinci toplamın \(i = 0\) terimi \(\binom{k}{0} a^{k+1} = a^{k+1}\), ikincinin \(i = k+1\) terimi \(\binom{k}{k} b^{k+1} = b^{k+1}\) tektir; \(1 \le i \le k\) için iki toplamdan birer terim gelir:
\[(a+b)^{k+1} = a^{k+1} + \sum_{i=1}^{k} \left[\binom{k}{i} + \binom{k}{i-1}\right] a^{k+1-i} b^{i} + b^{k+1}.\]
Lemma 10.1 ile köşeli parantez \(\binom{k+1}{i}\)’dir; ayrıca \(a^{k+1} = \binom{k+1}{0} a^{k+1} b^0\) ve \(b^{k+1} = \binom{k+1}{k+1} a^0 b^{k+1}\) yazılabilir. Böylece
\[(a+b)^{k+1} = \sum_{i=0}^{k+1} \binom{k+1}{i} a^{k+1-i} b^{i},\]
yani eşitlik \(n = k + 1\) için doğrudur.
\(\blacksquare\)
Örnek 10.13 (Binom Teoreminin Uygulamaları)
\((a + b)^4\) açılımını yazınız.
Her \(n \in \mathbb{N}\) için \(\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n\) ve \(\displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0\) olduğunu gösteriniz.
\(x \ge 0\) için Bernoulli eşitsizliğini binom teoreminden elde ediniz.
Çözüm
a) Pascal üçgeninin beşinci satırı \(1, 4, 6, 4, 1\) olduğundan
\[(a+b)^4 = a^4 + 4a^3 b + 6a^2 b^2 + 4ab^3 + b^4.\]
b) Teorem 10.7 içinde \(a = b = 1\) alınca \((1+1)^n = \sum_{k=0}^{n} \binom{n}{k} \cdot 1 \cdot 1\), yani \(2^n = \sum_{k=0}^{n} \binom{n}{k}\). \(a = 1\), \(b = -1\) alınca \((1 + (-1))^n = 0^n = 0\) (çünkü \(n \ge 1\)) ve sağ taraf \(\sum_{k=0}^{n} \binom{n}{k} (-1)^k\) olur.
c) \(a = 1\), \(b = x \ge 0\) alalım: \((1+x)^n = 1 + nx + \sum_{k=2}^{n} \binom{n}{k} x^k\) (\(n = 1\) için son toplam yoktur). Binom katsayıları pozitif (alıştırma (d)) ve \(x^k \ge 0\) olduğundan son toplam negatif değildir; dolayısıyla \((1+x)^n \ge 1 + nx\).
\(\blacksquare\)
10.9 Genel Üçgen Eşitsizliği
Bölüm 8’de ertelediğimiz ispatı artık yapabiliriz.
Teorem 10.8 (Sonlu Toplamlar İçin Üçgen Eşitsizliği) \(n \in \mathbb{N}\) ve \(a_1, a_2, \dots, a_n \in \mathbb{R}\) olsun.
- \(\displaystyle \left|\sum_{k=1}^{n} a_k\right| \le \sum_{k=1}^{n} |a_k|\), yani \(|a_1 + a_2 + \cdots + a_n| \le |a_1| + |a_2| + \cdots + |a_n|\).
- \(\displaystyle \left|\prod_{k=1}^{n} a_k\right| = \prod_{k=1}^{n} |a_k|\); özel olarak her \(a \in \mathbb{R}\) için \(|a^n| = |a|^n\).
İspat
Madde (1). \(n\) üzerinden tümevarım. \(n = 1\) için iki taraf da \(|a_1|\)’dir. Eşitsizlik \(n = k\) için (her \(k\) terimli toplam için) doğru olsun ve \(a_1, \dots, a_{k+1}\) verilsin. Toplam sembolünün özyineli tanımı, Teorem 8.2 ve tümevarım hipoteziyle
\[\left|\sum_{i=1}^{k+1} a_i\right| = \left|\left(\sum_{i=1}^{k} a_i\right) + a_{k+1}\right| \le \left|\sum_{i=1}^{k} a_i\right| + |a_{k+1}| \le \sum_{i=1}^{k} |a_i| + |a_{k+1}| = \sum_{i=1}^{k+1} |a_i|.\]
Madde (2). Aynı tümevarım, bu kez Teorem 8.1 (5) ile:
\[\left|\prod_{i=1}^{k+1} a_i\right| = \left|\left(\prod_{i=1}^{k} a_i\right) \cdot a_{k+1}\right| = \left|\prod_{i=1}^{k} a_i\right| \cdot |a_{k+1}| = \left(\prod_{i=1}^{k} |a_i|\right) |a_{k+1}| = \prod_{i=1}^{k+1} |a_i|.\]
Bütün \(a_i\)’ler \(a\)’ya eşit alınırsa \(|a^n| = |a|^n\) çıkar.
\(\blacksquare\)
Bu teorem sayesinde sonlu toplamların büyüklüğünü terim terim sınırlayabileceğiz; seriler ve kısmi toplamlar söz konusu olduğunda vazgeçilmez olacaktır.
10.10 Doğal Sayılar Üstten Sınırlı Değildir
Doğal sayıları kurduğumuza göre Tamlık Aksiyomu’nun (Bölüm 9.4) ilk büyük sonucunu kanıtlayabiliriz. Sezgisel olarak apaçık ama aksiyomlardan çıkarılması gereken bir olgudur bu: \(1, 2, 3, \dots\) sayılarının hepsini geçen bir reel sayı yoktur. Bu, cebirsel ve sıralama aksiyomlarından çıkmaz; ispatta tamlık gerçekten kullanılır.
Teorem 10.9 (Doğal Sayılar Kümesi Üstten Sınırlı Değildir) \(\mathbb{N}\) kümesi üstten sınırlı değildir. Başka bir deyişle, her \(x \in \mathbb{R}\) için \(n > x\) olan bir \(n \in \mathbb{N}\) vardır.
İspat
Olmayana ergi yöntemini kullanalım: \(\mathbb{N}\) üstten sınırlı olsun. \(\mathbb{N} \ne \varnothing\) olduğundan Tamlık Aksiyomu gereği \(s = \sup \mathbb{N}\) vardır. Teorem 9.1’i \(\varepsilon = 1\) ile uygulayalım: \(s - 1 < n\) olan bir \(n \in \mathbb{N}\) vardır. Her iki tarafa \(1\) ekleyince \(s < n + 1\) olur. Ama Önerme 10.2 gereği \(n + 1 \in \mathbb{N}\)’dir; yani \(\mathbb{N}\)’nin bir elemanı, üst sınır olan \(s\)’yi geçmiştir. Bu bir çelişkidir. O hâlde \(\mathbb{N}\) üstten sınırlı değildir.
İkinci ifade birincisinin yeniden yazılışıdır: \(x \in \mathbb{R}\) verilsin; \(\mathbb{N}\) üstten sınırlı olmadığından \(x\) bir üst sınır değildir, yani \(n > x\) olan bir \(n \in \mathbb{N}\) vardır.
\(\blacksquare\)
Bu teorem, “her pozitif \(\varepsilon\) için \(\dfrac{1}{n} < \varepsilon\) olacak kadar büyük bir \(n\) vardır” biçimindeki sayısız limit hesabının temelidir. Sonraki bölümlerde aynı olgu Arşimet özelliği adıyla genelleştirilecek (Teorem 12.1); burada teoremi doğrudan kullanarak iki temel kümenin supremum ve infimumunu bulalım.
Örnek 10.14 (Bir Eksi Bir Bölü n Kümesi) \(A = \left\{ 1 - \dfrac{1}{n} : n \in \mathbb{N} \right\} = \left\{ 0, \dfrac{1}{2}, \dfrac{2}{3}, \dfrac{3}{4}, \dots \right\}\) kümesi için \(\inf A = \min A = 0\) ve \(\sup A = 1\) olduğunu gösterelim.
Çözüm
İnfimum. Her \(n \in \mathbb{N}\) için \(\dfrac{1}{n} \le 1\) olduğundan (\(n \ge 1\)’dir; \(n = 1\) ise eşitlik, \(n > 1\) ise Önerme 7.10) \(1 - \dfrac{1}{n} \ge 0\); yani \(0\) bir alt sınırdır. \(n = 1\) için \(1 - \dfrac{1}{1} = 0 \in A\). Kümeye ait bir alt sınır minimumdur: \(\min A = 0\) ve Önerme 9.3 gereği \(\inf A = 0\).
Supremum. Teorem 9.1’in iki koşulunu denetleyelim.
Üst sınır: Her \(n\) için \(\dfrac{1}{n} > 0\) olduğundan \(1 - \dfrac{1}{n} < 1\). Demek ki \(1\) bir üst sınırdır.
Epsilon koşulu: \(\varepsilon > 0\) verilsin. \(1 - \varepsilon < 1 - \dfrac{1}{n}\) olacak bir \(n\) arıyoruz; bu eşitsizlik \(\dfrac{1}{n} < \varepsilon\) ile denktir. Teorem 10.9 gereği \(n > \dfrac{1}{\varepsilon}\) olan bir \(n \in \mathbb{N}\) vardır. \(n\) ve \(\varepsilon\) pozitif olduğundan her iki tarafı \(\dfrac{\varepsilon}{n} > 0\) ile çarpmak \(\varepsilon > \dfrac{1}{n}\) verir. Bu \(n\) için \(1 - \dfrac{1}{n} \in A\) ve \(1 - \varepsilon < 1 - \dfrac{1}{n}\) olur.
Her iki koşul sağlandığından \(\sup A = 1\). \(1 \notin A\)’dır, çünkü \(1 - \dfrac{1}{n} = 1\) olması \(\dfrac{1}{n} = 0\) gerektirir; dolayısıyla \(\max A\) yoktur.
Şekil, durumu özetliyor: kümenin elemanları \(1\)’e soldan yığılır, \(1\)’in sağındaki her sayı üst sınırdır ve \(1\)’in hemen solundaki her \((1 - \varepsilon, 1]\) penceresi kümeden en az bir eleman içerir.
\(\blacksquare\)
Örnek 10.15 (Bir Bölü n Kümesinin İnfimumu) \(B = \left\{ \dfrac{1}{n} : n \in \mathbb{N} \right\}\) kümesi için \(\sup B = \max B = 1\) ve \(\inf B = 0\) olduğunu gösterelim.
Çözüm
Örnek 9.1’nde \(1\)’in kümeye ait bir üst sınır olduğunu görmüştük; dolayısıyla \(\max B = \sup B = 1\).
\(\inf B = 0\) için Teorem 9.2’i kullanalım. \(0\) bir alt sınırdır, çünkü her \(n\) için \(\dfrac{1}{n} > 0\). \(\varepsilon > 0\) verilsin; \(\dfrac{1}{n} < 0 + \varepsilon\) olan bir \(n\) gerekiyor. Bir önceki örnekteki gibi Teorem 10.9 ile \(n > \dfrac{1}{\varepsilon}\) seçilir ve \(\dfrac{1}{n} < \varepsilon\) elde edilir. O hâlde \(\inf B = 0\); \(0 \notin B\) olduğundan \(\min B\) yoktur.
\(\blacksquare\)
10.11 İç İçe Aralıklar
Tamlık Aksiyomu’nun geometrik bir yüzü vardır: reel doğru üzerinde giderek daralan kapalı aralıklar alırsak, hepsinin içinde kalan en az bir nokta bulunur. Sezgi şöyledir: \([a_1, b_1] \supset [a_2, b_2] \supset [a_3, b_3] \supset \cdots\) aralıklarının sol uçları sağa, sağ uçları sola doğru ilerler; sol uçlar hiçbir sağ ucu geçemez. Sol uçların “ulaştığı en sağ nokta” olan \(\sup\{a_n\}\) bütün aralıklarda kalır.
Tanım 10.6 (İç İçe Aralıklar) Her \(n \in \mathbb{N}\) için \(a_n \le b_n\) olmak üzere \(I_n = [a_n, b_n]\) kapalı ve sınırlı bir aralık olsun (Tanım 7.3). Her \(n \in \mathbb{N}\) için \(I_{n+1} \subset I_n\) sağlanıyorsa \((I_n)_{n \in \mathbb{N}}\) indisli ailesine (Tanım 3.8) iç içe aralıklar (nested intervals) denir.
İç içe olma koşulu uç noktalar cinsinden şöyle okunur: \(a_{n+1} \in I_{n+1} \subset I_n\) olduğundan \(a_n \le a_{n+1}\); benzer biçimde \(b_{n+1} \le b_n\). Yani
\[a_1 \le a_2 \le a_3 \le \cdots \le b_3 \le b_2 \le b_1.\]
Teorem 10.10 (İç İçe Aralıklar Teoremi (Cantor)) \((I_n)_{n \in \mathbb{N}}\), \(I_n = [a_n, b_n]\) biçiminde iç içe kapalı aralıklar olsun.
Bu aralıkların kesişimi boş değildir. Daha kesin olarak \(a = \sup\{a_n : n \in \mathbb{N}\}\) ve \(b = \inf\{b_n : n \in \mathbb{N}\}\) vardır, \(a \le b\)’dir ve
\[\bigcap_{n=1}^{\infty} I_n = [a, b].\]
Ayrıca aralıkların uzunlukları istenildiği kadar küçülüyorsa — yani her \(\varepsilon > 0\) için \(b_n - a_n < \varepsilon\) olan bir \(n \in \mathbb{N}\) varsa — kesişim tek noktadan oluşur:
\[\bigcap_{n=1}^{\infty} I_n = \{a\}.\]
İspat
Adım 1: Her sol uç, her sağ ucun solundadır. \(n, m \in \mathbb{N}\) için \(a_n \le b_m\) olduğunu gösterelim. Önce \(n \le m\) ise \(a_n \le a_m\) olduğunu görelim. \(n\) sabit olmak üzere \(k \in \mathbb{N}\) üzerinden tümevarımla (Teorem 10.1) \(a_n \le a_{n+k}\) elde edilir: \(k = 1\) için bu, \(a_n \le a_{n+1}\) eşitsizliğidir; \(a_n \le a_{n+k}\) ise \(a_{n+k} \le a_{n+k+1}\) ile birlikte (O2) \(a_n \le a_{n+k+1}\) verir. Şimdi \(n \le m\) olsun: \(n = m\) ise \(a_n \le a_m\) açıktır; \(n < m\) ise Önerme 10.3 (4) ile \(k = m - n \in \mathbb{N}\) ve \(a_n \le a_{n+k} = a_m\). Aynı biçimde \(n \le m\) için \(b_m \le b_n\). Şimdi:
- \(n \le m\) ise \(a_n \le a_m \le b_m\);
- \(m < n\) ise \(a_n \le b_n \le b_m\).
Her iki hâlde \(a_n \le b_m\).
Adım 2: \(a\) ve \(b\) vardır ve \(a \le b\). \(A = \{a_n : n \in \mathbb{N}\}\) boş değildir ve Adım 1 gereği \(b_1\) (aslında her \(b_m\)) bir üst sınırıdır. Tamlık Aksiyomu ile \(a = \sup A\) vardır. Benzer biçimde \(B = \{b_n : n \in \mathbb{N}\}\) boş değildir ve her \(a_n\) bir alt sınırıdır; Teorem 9.3 ile \(b = \inf B\) vardır. Her \(m\) için \(b_m\), \(A\)’nın üst sınırı olduğundan (S2) ile \(a \le b_m\); yani \(a\), \(B\)’nin bir alt sınırıdır ve (I2) ile \(a \le b\).
Adım 3: Kesişim \([a, b]\)’dir. \(x \in \mathbb{R}\) olsun.
\[x \in \bigcap_{n=1}^{\infty} I_n \iff \text{her } n \text{ için } a_n \le x \le b_n.\]
“Her \(n\) için \(a_n \le x\)” demek, \(x\)’in \(A\)’nın bir üst sınırı olması demektir; bu da (S1)–(S2) gereği \(a \le x\) ile denktir (bir yönü: \(a\) en küçük üst sınırdır; diğer yönü: \(a_n \le a \le x\)). Aynı biçimde “her \(n\) için \(x \le b_n\)”, \(x \le b\) ile denktir. Dolayısıyla \(x\) kesişimdedir ancak ve ancak \(a \le x \le b\) ise; kesişim \([a, b]\)’dir ve \(a \le b\) olduğundan boş değildir (\(a\) bu kümededir).
Adım 4: Uzunluklar küçülüyorsa tek nokta. \(a < b\) olsa \(\varepsilon = b - a > 0\) alalım. Hipotez gereği \(b_n - a_n < \varepsilon\) olan bir \(n\) vardır. Ama Adım 3’e göre \(a_n \le a \le b \le b_n\), dolayısıyla
\[b - a \le b_n - a_n < \varepsilon = b - a\]
olur; bu bir çelişkidir. O hâlde \(a = b\) ve kesişim \([a, a] = \{a\}\)’dır.
\(\blacksquare\)
Teorem, “reel doğruda boşluk yoktur” cümlesinin en somut hâlidir: aralıkları daraltarak bir noktayı sıkıştırdığımızda o nokta gerçekten oradadır. İleride bu teoremle Bolzano–Weierstrass teoremini (Teorem 24.5) ve Heine–Borel teoremini (Teorem 18.5) kanıtlayacağız; dizilerin limitini öğrendikten sonra hipotezdeki “her \(\varepsilon\) için \(b_n - a_n < \varepsilon\) olan \(n\) var” koşulu, monoton yakınsaklık teoremi (Teorem 23.1) yardımıyla \(\lim (b_n - a_n) = 0\) biçiminde yeniden yazılacak ve teorem bu dille yeniden ispatlanacaktır (Teorem 24.7).
Teoremdeki “kapalı” sözcüğü süs değildir. \(J_n = \left(0, \dfrac{1}{n}\right)\) açık aralıkları da iç içedir (\(\dfrac{1}{n+1} < \dfrac{1}{n}\)) ve uzunlukları \(\dfrac{1}{n}\) küçülür; ama kesişimleri boştur. Gerçekten, bir \(x\) bütün \(J_n\)’lerde olsaydı \(x > 0\) ve her \(n\) için \(x < \dfrac{1}{n}\) olurdu. İkinci eşitsizliği \(\dfrac{n}{x} > 0\) ile çarpınca her \(n \in \mathbb{N}\) için \(n < \dfrac{1}{x}\) elde edilir; yani \(\dfrac{1}{x}\), \(\mathbb{N}\)’nin bir üst sınırı olurdu. Bu, Teorem 10.9 ile çelişir.
Sınırlılık da gereklidir: \([n, \infty)\) kapalı ama sınırsız aralıkları iç içedir ve kesişimleri yine boştur. Gerçekten, bir \(x\) bütün \([n, \infty)\) aralıklarında olsaydı her \(n \in \mathbb{N}\) için \(n \le x\) olur, yani \(x\), \(\mathbb{N}\)’nin bir üst sınırı olurdu; bu, Teorem 10.9 ile çelişir. Bu tür kesişim ve birleşimleri sonraki bölümlerde Arşimet özelliğiyle daha ayrıntılı inceleyeceğiz.
Örnek 10.16 (Sıfıra Daralan Aralıklar) \(I_n = \left[-\dfrac{1}{n}, \dfrac{1}{n}\right]\) aralıklarının iç içe olduğunu gösterelim ve kesişimlerini bulalım.
Çözüm
\(n < n + 1\) olduğundan \(\dfrac{1}{n+1} < \dfrac{1}{n}\) ve \(-\dfrac{1}{n} < -\dfrac{1}{n+1}\); dolayısıyla \(I_{n+1} \subset I_n\)’dir. Aralıklar kapalı ve sınırlıdır.
Uzunluk koşulunu denetleyelim: \(b_n - a_n = \dfrac{2}{n}\). \(\varepsilon > 0\) verilsin; Teorem 10.9 ile \(n > \dfrac{2}{\varepsilon}\) olan bir \(n\) seçersek \(\dfrac{2}{n} < \varepsilon\) olur. Teorem 10.10 gereği kesişim tek bir noktadır: \(\{a\}\), \(a = \sup\left\{-\dfrac{1}{n}\right\}\).
\(a\)’yı bulalım. Örnek 10.15’da \(\inf\left\{\dfrac{1}{n}\right\} = 0\) bulmuştuk; Önerme 9.5 (aynalama) ile \(\sup\left\{-\dfrac{1}{n}\right\} = -\inf\left\{\dfrac{1}{n}\right\} = 0\). O hâlde
\[\bigcap_{n=1}^{\infty} \left[-\frac{1}{n}, \frac{1}{n}\right] = \{0\}.\]
Doğrudan da görülebilir: \(0\) her aralıktadır; \(x \ne 0\) ise \(|x| > 0\) ve \(n > \dfrac{1}{|x|}\) seçildiğinde \(\dfrac{1}{n} < |x|\) olduğundan \(x \notin I_n\).
\(\blacksquare\)
10.12 Alıştırmalar
Alıştırma 10.1 (Tümevarım Alıştırmaları)
Her \(n \in \mathbb{N}\) için \(1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}\) olduğunu gösteriniz.
Her \(n \in \mathbb{N}\) için \(\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n(n+1)} = \dfrac{n}{n+1}\) olduğunu gösteriniz.
\(n \ge 4\) olan her \(n \in \mathbb{N}\) için \(2^n \ge n^2\) olduğunu gösteriniz.
Her \(n \in \mathbb{N}\) ve \(k \in \{0, 1, \dots, n\}\) için \(\dbinom{n}{k} \in \mathbb{N}\) olduğunu gösteriniz.
İyi sıralama ilkesini (Teorem 10.2) kullanarak tümevarım ilkesinin önerme biçimini ispatlayınız: \(P(1)\) doğru ve her \(k\) için \(P(k) \Rightarrow P(k+1)\) ise her \(n \in \mathbb{N}\) için \(P(n)\) doğrudur.
Çözüm
a) \(n = 1\): sol taraf \(1\), sağ taraf \(\frac{1 \cdot 2 \cdot 3}{6} = 1\). Tümevarım adımı: eşitlik \(k\) için doğruysa
\[1^2 + \cdots + k^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} = \frac{(k+1)(2k^2 + 7k + 6)}{6}.\]
\(2k^2 + 7k + 6 = (k+2)(2k+3)\) olduğundan sağ taraf \(\frac{(k+1)(k+2)(2k+3)}{6}\), yani formülün \(n = k+1\) hâlidir.
b) \(n = 1\): \(\frac{1}{1 \cdot 2} = \frac{1}{2} = \frac{1}{1+1}\). Tümevarım adımı: hipotezle
\[\frac{1}{1 \cdot 2} + \cdots + \frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} = \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} = \frac{k(k+2) + 1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2}.\]
Bu, formülün \(n = k + 1\) hâlidir.
c) Teorem 10.4 ile \(n_0 = 4\)’ten başlayalım. Temel adım: \(2^4 = 16 = 4^2\). Tümevarım adımı: \(k \ge 4\) ve \(2^k \ge k^2\) olsun. O zaman \(2^{k+1} = 2 \cdot 2^k \ge 2k^2 = k^2 + k^2\). \(k \ge 4 \ge 3\) olduğundan Örnek 10.11 ile \(k^2 > 2k + 1\); dolayısıyla
\[2^{k+1} \ge k^2 + k^2 > k^2 + 2k + 1 = (k+1)^2.\]
d) \(n\) üzerinden tümevarım; \(P(n)\): “her \(k \in \{0, \dots, n\}\) için \(\binom{n}{k} \in \mathbb{N}\)”. \(n = 1\): \(\binom{1}{0} = \binom{1}{1} = 1 \in \mathbb{N}\). \(P(n)\) doğru olsun. \(\binom{n+1}{0} = \binom{n+1}{n+1} = 1 \in \mathbb{N}\); \(1 \le k \le n\) için Lemma 10.1 ile \(\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}\), hipotezle iki toplanan da doğal sayıdır ve Önerme 10.2 ile toplamları da doğal sayıdır. \(P(n+1)\) doğrudur.
e) \(P(1)\) doğru ve her \(k\) için \(P(k) \Rightarrow P(k+1)\) olsun. \(S = \{n \in \mathbb{N} : P(n) \text{ yanlış}\}\) kümesini alalım ve \(S \ne \varnothing\) varsayalım. Teorem 10.2 ile \(S\)’nin en küçük elemanı \(m\) vardır. \(P(1)\) doğru olduğundan \(m \ne 1\); Önerme 10.3 (2) ile \(m - 1 \in \mathbb{N}\). \(m - 1 < m\) ve \(m\) en küçük olduğundan \(m - 1 \notin S\), yani \(P(m-1)\) doğrudur. Varsayımla \(P((m-1)+1) = P(m)\) doğrudur; bu \(m \in S\) ile çelişir. Demek ki \(S = \varnothing\): her \(n\) için \(P(n)\) doğrudur. (Bu, iyi sıralama ilkesinin tümevarım ilkesine denk olduğunu gösterir; diğer yön Teorem 10.2’nın ispatıdır.)
\(\blacksquare\)
Alıştırma 10.2 (Bir Kesir Dizisinin Değerleri) \(A = \left\{ \dfrac{n}{n+1} : n \in \mathbb{N} \right\}\) kümesinin supremumunu ve infimumunu bulunuz; maksimum ve minimumunun olup olmadığını belirleyiniz.
Çözüm
\(\dfrac{n}{n+1} = 1 - \dfrac{1}{n+1}\) yazalım.
İnfimum: \(n = 1\) için \(\dfrac{1}{2} \in A\). Her \(n \in \mathbb{N}\) için \(\dfrac{1}{2} \le \dfrac{n}{n+1}\) olduğunu görelim: paydalar pozitif olduğundan bu eşitsizlik \(n + 1 \le 2n\), yani \(1 \le n\) ile denktir ve doğrudur. Demek ki \(\dfrac{1}{2}\) kümeye ait bir alt sınırdır: \(\min A = \inf A = \dfrac{1}{2}\).
Supremum: \(\dfrac{1}{n+1} > 0\) olduğundan her eleman \(1\)’den küçüktür; \(1\) üst sınırdır. \(\varepsilon > 0\) verilsin. Teorem 10.9 ile \(n > \dfrac{1}{\varepsilon}\) olan bir \(n\) seçelim; \(n + 1 > n\) olduğundan \(\dfrac{1}{n+1} < \dfrac{1}{n} < \varepsilon\) ve \(1 - \varepsilon < 1 - \dfrac{1}{n+1} \in A\). Teorem 9.1 gereği \(\sup A = 1\). \(\dfrac{n}{n+1} = 1\) olması \(n = n + 1\), yani \(0 = 1\) gerektirdiğinden \(1 \notin A\); maksimum yoktur.
\(\blacksquare\)
Alıştırma 10.3 (İki Kesrin Toplamlarının Kümesi) \(B = \left\{ \dfrac{1}{n} + \dfrac{1}{m} : n, m \in \mathbb{N} \right\}\) kümesi için \(\sup B\) ve \(\inf B\) değerlerini ispatlayarak bulunuz.
Çözüm
Supremum: \(n, m \ge 1\) olduğundan \(\dfrac{1}{n} \le 1\) ve \(\dfrac{1}{m} \le 1\); toplam en çok \(2\)’dir. \(n = m = 1\) için \(2 \in B\). O hâlde \(\max B = \sup B = 2\).
İnfimum: Bütün elemanlar pozitif olduğundan \(0\) bir alt sınırdır. \(\varepsilon > 0\) verilsin; \(n > \dfrac{2}{\varepsilon}\) olan bir \(n \in \mathbb{N}\) alıp \(m = n\) seçelim:
\[\frac{1}{n} + \frac{1}{n} = \frac{2}{n} < \varepsilon = 0 + \varepsilon.\]
Teorem 9.2 gereği \(\inf B = 0\). Pozitif sayıların toplamı \(0\) olamayacağından \(0 \notin B\); minimum yoktur.
\(\blacksquare\)
Doğal sayılar artık elimizde: “her \(n\) için” tümcelerini ispatlayabiliyor ve Tamlık Aksiyomu’nu doğal sayılarla birlikte kullanabiliyoruz. Ne var ki \(\mathbb{N}\) çıkarmaya ve bölmeye izin vermez. Bir sonraki bölümde onu iki adımda genişletiyoruz: Tam Sayılar ve Rasyonel Sayılar.