02.01.04 — Ardıl İlkesi, Doğal Sayıların Yapısı ve Tümevarım Fikri

1. Birim kartı

Dünya: 2 — Sayılar, Aritmetik ve Temel Sayı Yapıları
Bölüm: 2.01 — Sayma ve Doğal Sayılar
Seviye: Ana Matematik Gövdesi
Ön koşullar: 02.01.02 — Doğal sayılar ve sayı doğrusu; 02.01.03 — Sıfır; Dünya 1'in temel mantık bölümü
Temel soru: Doğal sayıların sonsuza kadar aynı kuralla devam eden yapısını nasıl matematiksel olarak ifade ederiz?
Ana bağlantı: 01.06.08 — Matematiksel tümevarım

Bu birimin ana fikri

Doğal sayılar yalnızca

0,1,2,3,4,\ldots

diye yazdığımız sonsuz bir liste değildir.

Onların altında çok daha güçlü bir yapı vardır:

Bir başlangıç vardır.
Her doğal sayıdan bir sonraki doğal sayıya geçmenin belirli bir yolu vardır.
Bu işlem tekrarlandığında bütün doğal sayılar üretilir.

Bu yapı, matematiksel tümevarımın neden doğal sayılar üzerinde bu kadar doğal bir ispat yöntemi olduğunu açıklayacaktır.

2. Başlangıç problemi: Üç noktanın içinde ne saklı?

Doğal sayıları genellikle şöyle yazarız:

0,1,2,3,4,5,\ldots

Buradaki ilk birkaç sayının ne anlama geldiğini biliyoruz.

Fakat sondaki

\ldots

işareti aslında oldukça büyük bir iddiayı gizliyor.

Üç noktayla şunu söylemek istiyoruz:

“Aynı biçimde devam et.”

Ama hangi biçimde?

Şu sonlu listeyi verirsem:

0,1,2,3,4,5

bundan sonra ne geleceğini yalnızca bu altı terime bakarak mantıksal olarak kesinleştiremezsin.

Belki:

0,1,2,3,4,5,6,7,8,\ldots

diye devam edecektir.

Ama biri şu diziyi de yazabilir:

0,1,2,3,4,5,100,1000,\ldots

İlk altı terim aynı olduğu hâlde devam kuralı farklıdır.

Asıl problem

Doğal sayıları tek tek sonsuza kadar yazamayacağımıza göre,

bütün doğal sayı sistemini sonlu sayıda kuralla nasıl tarif edebiliriz?

Bu soru artık yalnızca “sayı saymak” sorusu değildir.

Doğal sayıların yapısını arıyoruz.

3. Eski araç neden yetmedi?

Önceki birimde doğal sayıları sayı doğrusu üzerinde gördük:

0 ─── 1 ─── 2 ─── 3 ─── 4 ─── 5 ─── ...

Bu bize sıralamayı gösterir.

Ama hâlâ şu üç noktanın anlamını matematiksel olarak açıklamış değiliz.

“Ve böyle devam eder” gündelik dil için yeterlidir.

Matematik içinse şu sorular ortaya çıkar:

“Böyle” tam olarak ne demektir?
Her sayıdan sonra gerçekten başka bir doğal sayı var mıdır?
Bu süreç bir yerde durabilir mi?
Aynı sayıya geri dönebilir miyiz?
Sistemde bu süreçle ulaşılamayan başka nesneler bulunabilir mi?
Sonsuz sayıda doğal sayı hakkındaki bir iddiayı nasıl kanıtlayabiliriz?

Bütün bunları cevaplamak için doğal sayıların üretim kuralını açık hâle getirmemiz gerekir.

4. Tarihsel gelişim

Doğal sayılardan doğal sayıların aksiyomlarına

İnsanlar binlerce yıldır doğal sayılarla hesap yapıyordu. Fakat doğal sayıları kullanmak başka, onların hangi temel ilkeler üzerine kurulduğunu açıklamak başka bir problemdir.

Özellikle 19. yüzyılda matematiğin temellerini daha kesin biçimde kurma çabaları güçlendi. Doğal sayıların hangi özelliklerinin gerçekten temel kabul edilmesi gerektiği araştırıldı.

Richard Dedekind ve Giuseppe Peano bu gelişimin önemli isimlerindendir. Peano'nun 1889'da yayımladığı çalışmayla ilişkilendirilen aksiyomatik yaklaşım, doğal sayıların başlangıç elemanı, ardıl ve tümevarım gibi birkaç temel özellik üzerinden tarif edilmesini çok açık bir biçime kavuşturdu.

Burada önemli bir ayrım vardır:

Peano doğal sayıları veya tümevarımı “icat etmiş” değildir.

Doğal sayılar çok daha eskidir ve tümevarımsal akıl yürütmenin örnekleri de Peano'dan önce kullanılıyordu. Peano'nun önemli katkısı, doğal sayıların yapısını az sayıda açık ilkeyle sistematik biçimde ifade eden modern aksiyomatik yaklaşımın gelişmesindeki rolüdür.

Bu birimde tam biçimsel sayı kuramına girmeyeceğiz. Peano yaklaşımını, doğal sayıların neden böyle davrandığını anlamamızı sağlayan sezgisel bir yapı modeli olarak kullanacağız.

5. Ardıl fikri

Bir doğal sayı düşünelim.

Örneğin:

4

Bu sayının hemen ardından gelen doğal sayı:

5

olur.

Benzer biçimde:

$0$ 'ın ardından $1$ ,
$1$ 'in ardından $2$ ,
$2$ 'nin ardından $3$ gelir.

Bu “hemen sonraki sayı” fikrine ardıl (successor) denir.

Ardıl

Bir doğal sayı $n$ 'nin ardılı, doğal sayı dizisinde $n$ 'den hemen sonra gelen doğal sayıdır.

Ardıl işlemini

S(n)

ile göstereceğiz.

Buradaki $S$ , İngilizce successor sözcüğünden gelen yaygın bir gösterimdir.

Örneğin:

S(0)=1

S(1)=2

S(2)=3

S(3)=4

Daha sonra toplama işlemini kurduğumuzda bunu alışılmış biçimde

S(n)=n+1

olarak da yazabileceğiz.

Fakat şimdilik ardılı “1 ekleme işlemi” üzerinden değil, bir sonraki doğal sayıya geçiş üzerinden düşünmek daha temeldir.

6. Doğal sayıların zincir yapısı

Ardıl zinciri

0 ──S──▶ 1 ──S──▶ 2 ──S──▶ 3 ──S──▶ 4 ──S──▶ 5 ──S──▶ ...

Sıfırdan başlanır ve ardıl işlemi tekrar tekrar uygulanarak 1, 2, 3, 4 ve sonraki doğal sayılara ulaşılır.

Bu şemada doğal sayıların önemli bir özelliği görünür hâle gelir.

Her sayı bağımsız biçimde gökten düşmüyor.

Bir başlangıçtan hareket ediyoruz:

0

sonra ardıl alıyoruz:

S(0)=1

bir kez daha:

S(S(0))=2

bir kez daha:

S(S(S(0)))=3.

Yani doğal sayıların yapısında iki temel malzeme var:

\boxed{\text{başlangıç}+\text{tekrarlanabilir geçiş}}

Doğal sayıları liste değil, üretim sistemi olarak düşün

Doğal sayıları hazır bir liste olarak düşünmek yerine bir üretim mekanizması olarak düşün:

$0$ ile başla.
Elindeki sayının ardılını üret.
Aynı işlemi yeniden uygula.
İstediğin kadar devam et.

Her tekil doğal sayıya sonlu sayıda adımda ulaşılır.

Fakat bütün doğal sayıların oluşturduğu sistemin bir son elemanı yoktur.

Bu son cümle özellikle önemlidir:

Her doğal sayı sonludur; fakat doğal sayıların kümesi sonsuzdur.

Örneğin $10^{100}$ olağanüstü büyük bir doğal sayıdır ama yine de belirli ve sonlu bir sayıdır.

Onun da ardılı vardır.

7. Neden en büyük doğal sayı yoktur?

Ardıl fikrinin ilk güçlü sonucunu hemen görebiliriz.

En büyük doğal sayı olamaz

Bir an için en büyük doğal sayının var olduğunu düşünelim ve ona $M$ diyelim.

$M$ bir doğal sayıysa ardıl ilkesi gereği:

S(M)

de bir doğal sayıdır.

Fakat $S(M)$ , $M$ 'den sonra gelen sayıdır.

Dolayısıyla:

M<S(M).

Bu durumda $M$ en büyük doğal sayı olamaz.

Demek ki doğal sayıların bir son elemanı yoktur.

Burada sonsuzluğu tuhaf bir “sonsuz sayısı” ekleyerek elde etmedik.

Tam tersine:

Hangi doğal sayıya ulaşırsan ulaş, sistem sana bir sonraki adımı üretme imkânı verir.

Doğal sayıların sonsuzluğu bu yapının içinden doğar.

8. Özyinelemeli yapı ne demektir?

Bu yapı matematikte çok sık karşılaşacağımız bir fikrin ilk örneğidir:

özyineleme (recursion).

Özyinelemeli yapı

Bir nesne veya süreç, daha önce oluşturulmuş durumdan aynı kural tekrar uygulanarak üretilebiliyorsa yapıda özyinelemeli bir özellik vardır.

Doğal sayılarda:

başlangıç nesnesi $0$ ,
tekrar edilen işlem ise ardıl alma işlemidir.

Şematik olarak:

0 \longrightarrow S(0) \longrightarrow S(S(0)) \longrightarrow S(S(S(0))) \longrightarrow\cdots

Çok önemli ayrım

Özyineleme bize sonsuz sayıda şeyi tek tek tanımlamak zorunda kalmadan, sonlu bir kuralla sonsuz bir yapı tarif etme imkânı verir.

İleride aynı fikirle:

diziler,
toplama ve çarpma,
faktöriyel,
algoritmalar,
ağaç yapıları,
bazı fonksiyonlar

tanımlanabilecektir.

9. Doğal sayıların “en küçük kapalı yapı” olarak görülmesi

Şimdi fikri biraz daha kesinleştirelim.

Bir kümenin:

$0$ 'ı içerdiğini,
içerdiği her $n$ ile birlikte $S(n)$ 'yi de içerdiğini

düşünelim.

Buna ardıl işlemine göre kapalı bir yapı diyebiliriz.

Örneğin $0$ içerideyse ikinci koşul yüzünden $1$ de içeride olmak zorunda.

$1$ içerideyse:

2

de içeride.

Sonra $3$ , sonra $4$ , sonra $5$ ...

Bu zincir duramaz.

Doğal sayıların yapısal karakteri

Doğal sayılar kümesini sezgisel olarak:

$0$ 'ı içeren ve ardıl alma işlemine kapalı olan en küçük yapı

şeklinde düşünebiliriz.

“En küçük” sözcüğü önemlidir.

Çünkü yalnızca

“ $0$ 'ı içerir ve ardıla kapalıdır.”

dersek, doğal sayılardan başka nesnelerin de bulunduğu daha büyük bir küme bu koşulu sağlayabilir.

Biz yalnızca bu işlemle üretilmesi gereken elemanları istiyoruz.

İşte tümevarım ilkesi bu “başka gereksiz eleman kalmasın” fikrini matematiksel olarak çok güçlü biçimde ifade eder.

10. Peano yaklaşımının sezgisel iskeleti

Doğal sayıların yapısını birkaç temel ilkeye ayırabiliriz.

Bu bölüm tam biçimsel Peano aritmetiği değildir; yapının neden çalıştığını görebilmek için kullanılan sezgisel bir versiyondur.

1. Bir başlangıç doğal sayımız vardır

Bu derste kullandığımız gösterimle:

0\in\mathbb N.

Burada $\mathbb N$ doğal sayılar kümesidir.

Bazı kitaplar doğal sayıları

\{1,2,3,\ldots\}

ile başlatır.

Bazıları ise

\{0,1,2,3,\ldots\}

kullanır.

Bu projede sıfırı doğal sayıların başlangıç elemanı olarak kullanıyoruz.

Bu bir matematiksel çelişki değil, gösterim tercihidir. Kullanılan tanımın açıkça belirtilmesi yeterlidir.

2. Her doğal sayının ardılı yine doğal sayıdır

n\in\mathbb N \quad\Longrightarrow\quad S(n)\in\mathbb N.

Bu, zincirin devam etmesini sağlar.

3. Sıfır hiçbir doğal sayının ardılı değildir

Hiçbir $n\in\mathbb N$ için:

S(n)=0

olmaz.

Yani zincir geriye kıvrılıp başlangıca dönmez.

4. Farklı doğal sayılar aynı ardıla sahip değildir

S(a)=S(b) \quad\Longrightarrow\quad a=b.

Başka bir ifadeyle ardıl işlemi geçmişi birbirine karıştırmaz.

Örneğin aynı sayının hem $4$ 'ün hem $7$ 'nin hemen ardından geldiğini söyleyemeyiz.

5. Başlangıçtan ardıl yoluyla yayılan özellik bütün doğal sayılara ulaşır

İşte bu son fikir bizi tümevarıma götürür.

11. Tümevarım fikri neden burada ortaya çıkıyor?

Bir özellik düşünelim.

Bu özelliğe:

P(n)

diyelim.

$P(n)$ şu anlama gelir:

“ $n$ doğal sayısı için belirli bir iddia doğrudur.”

Şimdi iki şeyi bildiğimizi varsayalım.

Başlangıç

Özellik $0$ için doğru:

P(0).

Ardıl geçişi

Her doğal sayı $n$ için:

P(n)\Longrightarrow P(S(n)).

Yani özellik bir sayıda doğruysa onun ardılında da doğrudur.

Şimdi neler olur?

Doğruluğun ardıl zinciri boyunca yayılması

P(0)
 │
 │ ardıl adımı
 ▼
P(1)
 │
 │ ardıl adımı
 ▼
P(2)
 │
 ▼
P(3)
 │
 ▼
P(4)
 │
 ▼
...

P sıfır için doğrudur ve bir doğal sayıda doğru olduğunda ardılında da doğruysa P birden, ikiden, üçten ve bütün doğal sayılardan geçerek yayılır.

İlk bilgiden:

P(0)

doğru.

Geçiş kuralından:

P(0)\Rightarrow P(1),

dolayısıyla $P(1)$ doğru.

Aynı kural yeniden:

P(1)\Rightarrow P(2).

Dolayısıyla $P(2)$ doğru.

Sonra:

P(2)\Rightarrow P(3).

Bu süreç herhangi bir doğal sayıda durmaz.

Tümevarımın yapısal kökeni

Matematiksel tümevarım doğaüstü bir ispat hilesi değildir.

Doğal sayıların şu yapısının doğrudan yansımasıdır:

0\rightarrow1\rightarrow2\rightarrow3\rightarrow\cdots

Bir iddia:

başlangıçta doğruysa,
her doğru adımdan bir sonraki adıma taşınabiliyorsa,

doğal sayı zincirinin tamamına yayılır.

Biçimsel olarak:

P(0) \quad\text{ve}\quad \forall n\in\mathbb N\, \bigl(P(n)\Rightarrow P(S(n))\bigr)

ise:

\forall n\in\mathbb N\,P(n).

Bu, matematiksel tümevarım ilkesidir.

Tümevarımla nasıl ispat yazılacağını ayrıntılı biçimde 01.06.08 — Matematiksel Tümevarım biriminde ele alacağız.

Buradaki amacımız şimdilik yöntemin neden doğal sayılardan doğduğunu anlamaktır.

12. “Bir sürü örnek doğru çıktı” ile tümevarım aynı şey değildir

Burada çok önemli bir ayrım yapalım.

Bir iddiayı:

n=0,1,2,3,4,5

için kontrol etmiş olalım.

Hepsinde doğru çıktı.

Bu bize:

\forall n\in\mathbb N\,P(n)

sonucunu vermez.

Çünkü yalnızca sonlu sayıda örnek kontrol ettik.

Doğal sayılar ise bitmiyor.

Çok örnek görmek ispat değildir

Bir kuralın ilk bin doğal sayı için doğru çıkması, $1001$ . veya çok daha sonraki bir doğal sayıda bozulmayacağını tek başına göstermez.

Tümevarımda farklı bir bilgi vardır:

P(n)\Rightarrow P(S(n))

ilişkisi her doğal sayı için kanıtlanır.

Bu nedenle tek tek sonsuz örnek kontrol etmeye gerek kalmaz.

Bu fark çok önemlidir:

Örnek kontrolü:

0 için doğru.
1 için doğru.
2 için doğru.
3 için doğru...

Tümevarım:

Başlangıç doğru ve doğruluk hangi doğal sayıya ulaşırsa ulaşsın bir sonraki sayıya geçmek zorunda.

İkinci ifade bütün sonsuz zinciri kapsar.

13. Neden iki parçaya da ihtiyacımız var?

Tümevarımın iki temel ayağı vardır:

başlangıç durumu,
ardıl geçişi.

İkisinden biri eksikse sonuç çıkmaz.

Başlangıç var, geçiş yok

Diyelim yalnızca:

P(0)

biliyoruz.

Bu bize $P(1)$ hakkında hiçbir şey söylemez.

“ $n=0$ 'dır” özelliğini düşün.

Bu özellik $0$ için doğrudur.

Ama:

1,2,3,\ldots

için doğru değildir.

Demek ki yalnız başlangıcın doğru olması yetmez.

Geçiş var, başlangıç yok

Şimdi:

P(n)\Rightarrow P(S(n))

geçişinin doğru olduğunu düşün.

Fakat hiçbir başlangıç noktasında $P$ 'nin doğru olduğunu bilmiyorsak zinciri harekete geçiremeyiz.

Ardıl adımı bir iletim mekanizmasıdır.

Ama iletilecek doğruluk başlangıçta hiç yoksa mekanizma kendi başına bir şey üretmez.

Bu nedenle matematiksel tümevarımda:

\boxed{\text{başlangıç}+\text{geçiş}}

birlikte gerekir.

14. Doğal sayıların yapısını gösteren bir örnek

Şu özelliği ele alalım:

Her doğal sayı ya $0$ 'dır ya da başka bir doğal sayının ardılıdır.

Bunu:

P(n): \quad n=0 \quad\text{veya}\quad \exists m\in\mathbb N\; n=S(m)

şeklinde yazabiliriz.

Başlangıç

$n=0$ için iddia açıktır:

P(0)

doğrudur, çünkü $0=0$ .

Ardıl adımı

Herhangi bir doğal sayı $n$ düşünelim.

Onun ardılı:

S(n)

zaten tanım gereği bir doğal sayının — yani $n$ 'nin — ardılıdır.

Dolayısıyla:

P(S(n))

doğrudur.

Tümevarım ilkesi bize bütün doğal sayılar için:

n=0 \quad\text{veya}\quad n=S(m)

sonucunu verir.

Bu küçük örnek, doğal sayıların yapısının neden:

başlangıç
   │
   ▼
 ardıl
   │
   ▼
 ardıl
   │
   ▼
 ardıl
   │
   ▼
  ...

şeklinde düşünülmesinin güçlü olduğunu gösterir.

15. “Bütün doğal sayılar başlangıçtan gerçekten ulaşılabilir mi?”

Şimdi doğal sayıların yapısını başka bir açıdan düşünelim.

$A$ diye bir küme oluşturalım.

$A$ şu elemanlardan oluşsun:

$0$ 'dan başlayıp ardıl işlemini sonlu sayıda uygulayarak ulaşabildiğimiz bütün sayılar.

Kesinlikle:

0\in A.

Ayrıca:

n\in A

ise, $n$ 'ye ulaşmışız demektir.

Bir kez daha ardıl alırsak:

S(n)\in A.

Yani $A$ :

başlangıç elemanını içeriyor,
ardıl işlemine kapalı.

Tümevarım ilkesi tam burada devreye girer:

A=\mathbb N.

Bu bize doğal sayılar hakkında çok güçlü bir yorum verir:

Doğal sayılar, başlangıçtan sonlu sayıda ardıl adımıyla üretilebilen elemanların tamamıdır.

Sistemde başlangıç ve ardıl mekanizmasından tamamen kopuk “gizli doğal sayılar” yoktur.

16. İyi sıralama fikri

Doğal sayıların bir başka temel özelliği daha vardır.

Şu kümeye bakalım:

A=\{4,7,15,28,\ldots\}.

Boş olmadığını varsayalım.

Bu kümede en küçük bir doğal sayı bulunur.

Burada örneğin:

4

en küçük elemandır.

Bu yalnızca sonlu kümelerde olmaz.

Örneğin çift doğal sayılardan oluşan sonsuz bir kümenin de en küçük elemanı vardır:

0.

Doğal sayıların iyi sıralama ilkesi

Doğal sayıların boş olmayan her alt kümesinin bir en küçük elemanı vardır.

Yani:

A\subseteq\mathbb N,\qquad A\neq\varnothing

ise, bir $m\in A$ vardır ve her $a\in A$ için:

m\leq a.

Bu özellik doğal sayıların sayı doğrusu üzerindeki ayrık ve başlangıçlı yapısıyla yakından ilişkilidir.

17. İyi sıralama ile tümevarım arasındaki şaşırtıcı bağ

İyi sıralama bize tümevarımı başka bir gözle görme imkânı verir.

Bir $P(n)$ iddiasını bütün doğal sayılar için ispatlamak istediğimizi düşünelim.

Şunları biliyoruz:

$P(0)$ doğru.
$P(n)$ doğruysa $P(S(n))$ de doğru.

Ama yine de bir doğal sayıda iddianın yanlış olduğunu varsayalım.

Yanlış olduğu doğal sayıları bir kümeye toplayalım:

C=\{n\in\mathbb N:P(n)\text{ yanlış}\}.

Eğer gerçekten karşı örnek varsa:

C\neq\varnothing.

İyi sıralama ilkesine göre $C$ 'nin en küçük elemanı vardır.

Ona $m$ diyelim.

En küçük karşı örnek neden mümkün değildir?

$m$ karşı örnek olduğuna göre $P(m)$ yanlıştır.

Fakat $P(0)$ doğru olduğu için:

m\neq0.

Dolayısıyla $m$ bir önceki doğal sayıdan gelen bir ardıldır:

m=S(k)

olacak biçimde bir $k$ doğal sayısı vardır.

$m$ en küçük karşı örnek olduğundan $k$ , $m$ 'den önce gelir ve $P(k)$ yanlış olamaz.

Yani:

P(k)

doğrudur.

Fakat tümevarım adımı:

P(k)\Rightarrow P(S(k))

diyordu.

Dolayısıyla:

P(m)

doğru olmalıdır.

Bu, $m$ 'nin karşı örnek olduğu varsayımıyla çelişir.

Demek ki karşı örneklerin oluşturduğu $C$ kümesi aslında boş olmak zorundadır.

Sonuç:

\forall n\in\mathbb N\;P(n).

Bu düşünme biçimine ileride en küçük karşı örnek yöntemi olarak yeniden rastlayacağız.

Doğal sayıların:

ardıl yapısı,
matematiksel tümevarım ilkesi,
iyi sıralama özelliği

birbirinden kopuk üç rastgele gerçek değildir.

Aynı ayrık ve başlangıçlı doğal sayı yapısının farklı yönlerini ifade ederler.

18. Tümevarım neden özellikle doğal sayılarda bu kadar doğal?

Tümevarımın mantığını başka sayı türlerine gelişigüzel taşıyamayız.

Örneğin sayı doğrusu üzerindeki bütün noktaları ele aldığımızı düşün.

$0$ 'dan başlayıp her seferinde “bir sonraki” noktaya geçmeye çalışalım.

Sorun şu:

0 \qquad\text{ile}\qquad 1

arasında bile:

\frac12

vardır.

Hatta $0$ ile $\frac12$ arasında da başka sayılar vardır.

Dolayısıyla sürekli sayı doğrusunda:

“Bu sayıdan hemen sonra gelen sayı”

fikri doğal sayılardaki gibi çalışmaz.

Doğal sayılarda ise:

0,1,2,3,\ldots

arasında ardıl ilişkisi belirgindir.

Başlangıç + 1 adımı bütün sayı doğrusunu kapsamaz

$0$ 'dan başla ve her adımda:

x\longmapsto x+1

yap.

Şunlara ulaşırsın:

0,1,2,3,\ldots

Ama örneğin:

\frac12

noktasına hiçbir zaman ulaşamazsın.

Dolayısıyla bu mekanizma doğal sayıları tarar; sürekli sayı doğrusunun tamamını taramaz.

Tümevarımın doğal sayılar üzerindeki gücünün nedeni tam olarak budur:

Doğal sayılar ayrık, başlangıçlı ve ardıl yoluyla üretilen bir yapı oluşturur.

19. Tümevarım “sonsuz sayıda işlem yapmak” değildir

Burada sık karşılaşılan başka bir yanılgıyı düzeltelim.

Tümevarımla ispat yaparken:

önce $P(0)$ ,
sonra gerçekten $P(1)$ ,
sonra gerçekten $P(2)$ ,
sonra gerçekten $P(3)$ ,
sonsuza kadar...

kanıtlamıyoruz.

Böyle yapmaya çalışsaydık hiçbir zaman bitiremezdik.

Yaptığımız şey iki sonlu ispat vermektir:

P(0)

ve:

\forall n\in\mathbb N\; (P(n)\Rightarrow P(S(n))).

İkinci ifade tek bir sayıyı değil, rastgele seçilmiş herhangi bir doğal sayıyı kapsadığı için sonsuz zincirin tamamını kontrol eder.

Niceleyiciye dikkat

Tümevarım adımındaki:

\forall n\in\mathbb N

ifadesi çok önemlidir.

Yalnızca:

“ $P(3)$ doğruysa $P(4)$ doğrudur.”

göstermek yeterli değildir.

Geçişin her doğal sayı için çalıştığı gösterilmelidir.

Bu nokta Dünya 1'de öğrendiğimiz niceleyicilerin burada neden gerçek matematik yaptığını gösterir.

20. Ardıl yapısından aritmetiğe doğru

Şu ana kadar doğal sayıları kullanarak işlem yapmadık.

Onların yapısını kurduk.

Fakat ardıl ve özyineleme fikri daha sonra işlemlerin kendisini bile tanımlamamıza imkân verir.

İleriye bakış: toplama bile özyinelemeli kurulabilir

İleride toplama işlemini bildiğimiz bir kural olarak kabul etmek yerine şu biçimde kurabiliriz:

a+0=a

ve:

a+S(n)=S(a+n).

İkinci satır şunu söylüyor:

$a$ ile $n$ 'yi nasıl toplayacağımı biliyorsam, $n$ 'nin ardılıyla toplamayı da bundan üretebilirim.

Örneğin toplamanın kendisi bile doğal sayıların ardıl yapısı üzerinde inşa edilebilir.

Bu konu ayrıntılı biçimde sonraki birim olan 02.02.01 — Toplama ve çıkarma içinde geliştirilecektir.

Bu örnek çok önemli bir zihinsel dönüşümü gösterir:

Doğal sayılar yalnızca işlemlerin üzerinde yapıldığı nesneler değildir; işlemlerin kendisini kurabileceğimiz bir yapıya sahiptir.

21. Bilgisayar bilimindeki aynı fikir

Doğal sayıların bu biçimde kurulması yalnızca matematik temellerinde kalan soyut bir fikir değildir.

Özyineleme ve programlama

Bir programlama dilinde doğal sayıyı kavramsal olarak iki yapı taşıyla temsil ettiğimizi düşün:

Natural
├── Zero
└── Successor(Natural)

Bu şunu ifade eder:

Zero bir doğal sayıdır.
Bir doğal sayı varsa onun Successor'ı da doğal sayıdır.

Böylece:

Zero
Successor(Zero)
Successor(Successor(Zero))
Successor(Successor(Successor(Zero)))
...

oluşur.

Bu, matematikte gördüğümüz:

0,\quad S(0),\quad S(S(0)),\quad S(S(S(0))),\ldots

yapısının doğrudan karşılığıdır.

Aynı nedenle bir algoritmanın her doğal sayı büyüklüğündeki girdi için doğru olduğunu göstermek istediğimizde tümevarımsal ispatlar son derece doğal biçimde ortaya çıkar.

Benzer yapı ileride:

özyinelemeli algoritmalarda,
veri yapılarında,
döngülerin doğruluk ispatlarında,
kombinatorikte,
dizi tanımlarında

yeniden karşımıza çıkacaktır.

22. Ardıl ile “sonraki sembol” aynı şey değildir

Ardıl kavramı sayıların yapısıyla ilgilidir; yazılış biçimleriyle değil.

Örneğin onluk sistemde:

9

sayısının ardılı:

10

olur.

Burada yalnızca son rakamı değiştirmedik; sayı gösteriminin basamak yapısı değişti.

Benzer şekilde:

99\longrightarrow100.

Ardıl, “rakamın yanındaki sonraki sembol” anlamına gelmez.

Ardıl, doğal sayı sıralamasındaki bir sonraki sayıdır.

Sayı ile onu yazdığımız gösterimi birbirinden ayırmayı sürdürmeliyiz.

Bu ayrım, 02.01.01'de öğrendiğimiz:

sayı ≠ sayı sembolü

fikrinin devamıdır.

23. Sık yapılan hatalar

Hata 1 — Üç noktayı matematiksel tanım sanmak

0,1,2,3,\ldots

yazımı kullanışlıdır ama tek başına yapının tam açıklaması değildir.

Üç noktanın anlamını ardıl kuralı verir.

Hata 2 — “Sonsuz”u son doğal sayı sanmak

Doğal sayıların sonunda:

\infty

adında son bir doğal sayı yoktur.

Her doğal sayının ardılı vardır.

Hata 3 — Tümevarımı çok sayıda örnek kontrolü sanmak

İlk milyon örneği kontrol etmek bile:

\forall n\in\mathbb N

iddiasının ispatı değildir.

Hata 4 — Tümevarım adımında kanıtlamak istediğimiz şeyi baştan varsaymak

Tümevarım adımında:

P(n)

ifadesi geçici bir varsayım olarak alınır ve bundan:

P(S(n))

çıkarılır.

“Bütün $n$ 'ler için $P(n)$ zaten doğru” varsayılmaz.

Aksi hâlde ispat döngüsel olur.

Hata 5 — Başlangıç durumunu unutmak

Geçiş mekanizmasının çalışması tek başına yeterli değildir.

Doğruluğun zincire girdiği bir başlangıç noktası gerekir.

Hata 6 — Ardıl fikrini bütün sayı sistemlerine aynen taşımak

Doğal sayılar ayrık bir zincirdir.

Sürekli sayı doğrusunda herhangi iki farklı sayı arasında başka sayılar bulunabileceğinden “hemen sonraki sayı” kavramı aynı biçimde çalışmaz.

24. Neden bu fikir matematikte bu kadar önemlidir?

Bu birimde henüz toplama, çarpma veya denklem çözmedik.

Buna rağmen matematiğin çok temel bir mekanizmasını kurduk:

\boxed{ \text{başlangıç} + \text{üretim kuralı} + \text{bütün yapıya yayılma} }

Bu üçlü ileride tekrar tekrar karşımıza çıkacak.

Matematik içindeki kullanımlar

İspatlar

Doğal sayılara bağlı sonsuz sayıda iddia, matematiksel tümevarımla ispatlanabilir.

Özyinelemeli tanımlar

Bir nesnenin $n$ . durumu önceki durumdan üretilebilir.

Diziler

Bir dizinin ilk terimi verilip sonraki terimler önceki terimlerden tanımlanabilir.

Sayı teorisi

Bölünebilme, toplamlar ve sayıların çeşitli özellikleri doğal sayı yapısı üzerinde incelenir.

Kombinatorik

$n$ nesne için doğru olan bir yapının $n+1$ nesne için nasıl genişlediği araştırılır.

Algoritmalar

Girdi büyüklüğü $n$ olan algoritmaların doğruluğu veya çalışma yapısı tümevarımla incelenebilir.

Bu yüzden tümevarım, doğal sayıların üzerine sonradan yapıştırılmış bir teknik değildir.

Doğal sayıların iç yapısından çıkar.

25. Matematik haritasındaki bağlantı

Nereden geldik?

02.01.01 — Sayı neden ortaya çıktı?

“Kaç tane?” sorusundan soyut sayıya geçtik.

02.01.02 — Doğal sayılar ve sayı doğrusu

Doğal sayıların sıralı ve sınırsız bir yapı oluşturduğunu gördük.

02.01.03 — Sıfır

Doğal sayı zincirimiz için bir başlangıç elemanı elde ettik.

Şimdi bunları bir araya getirdik:

0 \overset{S}{\longrightarrow} 1 \overset{S}{\longrightarrow} 2 \overset{S}{\longrightarrow} 3 \overset{S}{\longrightarrow} \cdots

Başlangıç + ardıl = doğal sayıların temel yapısı

Bu yapı iki kapı açıyor.

Nereye gidiyoruz?

01.06.08 — Matematiksel tümevarım

Artık tümevarımın neden çalışması gerektiğini biliyoruz. O birimde bu fikri gerçek teoremleri ispatlamak için sistematik bir yönteme dönüştüreceğiz.

02.02.01 — Toplama ve çıkarma

Doğal sayıların ardıl yapısından sonra artık sayılar üzerinde işlemlerin nasıl kurulabileceğine geçebiliriz.

26. Kısa sentez

Neden vardı?

Sonsuz doğal sayı listesini tek tek yazamayız. “ $0,1,2,3,\ldots$ ” ifadesindeki devam kuralını matematiksel olarak açıklamamız gerekiyordu.

Ne öğrendik?

Doğal sayıların bir başlangıç elemanı ve ardıl işlemiyle oluşturulan özyinelemeli bir yapıya sahip olduğunu gördük:

0\rightarrow1\rightarrow2\rightarrow3\rightarrow\cdots

Her doğal sayının ardılı vardır; dolayısıyla en büyük doğal sayı yoktur.

Doğal sayıların boş olmayan alt kümelerinin en küçük elemanı bulunması, iyi sıralama fikrini verir.

Neyi artık yapabiliyoruz?

Sonsuz doğal sayı sistemini sonlu sayıda yapısal ilkeyle tarif edebiliyor ve:

P(0), \qquad P(n)\Rightarrow P(S(n))

bilgisinin neden:

\forall n\in\mathbb N\;P(n)

sonucuna götürdüğünü kavramsal olarak açıklayabiliyoruz.

Sırada ne var?

Bu yapısal fikir artık gerçek bir ispat yöntemine dönüşebilir:

matematiksel tümevarım.

Aynı doğal sayı yapısı üzerinde toplama ve diğer aritmetik işlemleri de kurmaya başlayacağız.

27. Öğrenme kontrolü

Kavrama

Doğal sayıları yalnızca
$0,1,2,3,\ldots$
biçiminde yazmak neden onların yapısını tam olarak açıklamaz?
Ardıl kavramını kendi sözlerinle açıkla.
“Her doğal sayı sonludur ama doğal sayıların kümesi sonsuzdur.” cümlesinde bir çelişki olmadığını açıkla.
Doğal sayıların neden özyinelemeli bir yapı olduğunu anlat.

Teknik

Ardıl gösterimini kullanarak $0$ , $1$ , $2$ ve $3$ sayılarını yalnızca $0$ ve $S$ sembolü yardımıyla yaz.
$S(S(S(S(0))))$ hangi doğal sayıyı gösterir?
Bir özellik için:
$P(0)$
doğru ve
$\forall n\in\mathbb N\, \bigl(P(n)\Rightarrow P(S(n))\bigr)$
doğruysa hangi genel sonuca ulaşırız?

Gerekçelendirme

“En büyük doğal sayı vardır.” iddiasının ardıl fikriyle neden çeliştiğini açıklayarak göster.
Yalnızca:
$P(0)$
bilgisinin bütün doğal sayılar için $P(n)$ sonucunu vermediğini bir karşı örnekle açıkla.
Yalnızca:
$P(n)\Rightarrow P(S(n))$
geçişinin bulunmasının neden yeterli olmadığını açıkla.
Tümevarımla ilk bir milyon doğal sayıyı tek tek kontrol etmek arasındaki mantıksal fark nedir?

Transfer

$A$ , doğal sayıların bir alt kümesi olsun. Şunları biliyoruz:
$0\in A$
ve her $n\in A$ için:
$S(n)\in A.$
$A$ kümesinin örneğin $57$ sayısını içermeyebileceğini iddia eden birine nasıl cevap verirsin?
Birisi gerçek sayı doğrusu üzerinde de “ $0$ için doğruysa ve $x$ için doğru olduğunda $x+1$ için de doğruysa bütün sayılar için doğrudur” diyor. $\frac12$ sayısını düşünerek bu akıl yürütmenin neden çalışmadığını açıkla.
Bir bilgisayar programında yalnızca iki yapı taşı olduğunu düşün:
```
Zero
Successor(...)
```
Bu iki yapı taşıyla doğal sayıların nasıl temsil edilebileceğini açıkla. Bunun bu dersteki hangi matematiksel fikirle aynı yapıya sahip olduğunu belirt.