Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
309 kez görüntülendi
Cok temel bir soru ama muhendislik okudum affedin. Hangi kumeler uzerine tumevarim yapabiliriz?
Dogal sayilari kurarken peano aksyomlarinda gectigini hatirliyorum tumevarimin ama illa aksyom olarak mi vermek gerekiyor bunu?
Keza Cizgeler uzerine de tumevarim yaptigimizi hatirliyorum hayal meyal ama cizgeler kumesi ile dogal sayilar arasinda oyle organik bir baglanti da yok sanki (belki de tumevarimli ispat yaparken cizgelerin en fazla sayilabilir sonsuz kose/kenari oldugunu sart kosuyoruzdur  )
Az once ZFC aksyomlarini kontrol ettim tumevarima benzer bir sey goremedim.
Kisaca ne zaman tumevarim yapabiliriz ve neden yapabiliriz ?
Ne okuyayim bunun icin?
Lisans Matematik kategorisinde (1.6k puan) tarafından  | 309 kez görüntülendi
Aynı şeyleri mi merak ettik, anlamak için soruyorum: ne kadar genel kümeler üzerine tümevarım uygulayabiliriz? Yani tümevarım yapabilmemiz için $\mathbb{N}$ yerine ne kullanabiliriz?

Aklıma gelen ilk kısıtlama kümenin iyi sıralama olması gerektiği. Başka nasıl kısıtlar gerekir, bilen biri yazarsa güzel olur bence.

1 cevap

0 beğenilme 0 beğenilmeme

Lise öğrencisi olduğum yıllarda, tümevarım yöntemi kullanılan karşılaştığım ilk ispat sanırım $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ eşitliğinin ispatıdır. İspatlanacak ifadenin illa bir eşitlik olması gerekmez, eşitsizlik de olabilir. İzlenilmesi gereken ve iyi bildiğimiz algoritma şu şekildedir:

 

$\bullet$ $P(n)$ önermesini $n=1$ için ispatla.

$\bullet$ $P(n)$ önermesinin bir $n=k$ doğal sayısı için doğru olduğunu kabul et.

$\bullet$ $n=k+1$ için $P(k+1)$ önermesinin de doğru olduğunu ispatla.

O zaman her $n$ pozitif tam sayısı için $P(n)$ önermesi doğrudur, sonucuna varıyoruz.

 

Tümevarım bundan biraz daha fazlasıdır. İlk basamakta biraz değişikliğe gidip

$n=n_{0} $ gibi bir doğal sayı için $P(n)$ önermesinin doğru olduğunu ispatla

maddesini koyalım. Diğer kısımları aynı kalsın. O zaman da $P(n)$ önermesinin her $n\geq n_0$ doğal sayısı için doğru olduğunu göstermiş oluyoruz.

 

Örnek: Her $n \geq 3$ için $3^n >2^n + 2n^2$ olduğunu ispatlayınız.

Çözüme Giriş: Burada ilk basamak olarak $n=3$ için önermenin doğru olduğunu göstemeliyiz. Zaten $n=1$, $n=2$ için önerme yanlıştır. $n=3$ için $3^3 = 27$, $2^3 + 2\cdot 3^2 = 26$ olup $27>26$ dır, önerme doğrudur. Bundan sonraki adımlar, tümevarım basamaklarına devam edilebilir diye düşünüyorum ama biraz uğraştırıcı olacak gibi görünüyor. (Başka bir yerde soru olarak sorayım bunu.)

 

Bir de şunu kullanabiliyoruz:

$\bullet$ $P(n)$ önermesini $n=1$ için ispatla.

$\bullet$ $P(n)$ önermesinin $1 \leq n\leq k$ doğal sayıları için doğru olduğunu kabul et. ($k$ sabit bir pozitif tam sayı)

$\bullet$ $n=k+1$ için $P(k+1)$ önermesinin de doğru olduğunu ispatla.

O zaman, her $n$ pozitif tam sayısı için $P(n)$ önermesi doğrudur, sonucuna varıyoruz.

 

Buraya kadar olan kısım Zayıf Tümevarım Prensibi olarak isimlendiriliyor. Doğru hatırlıyorsam, Kuvvetli Tümevarım Prensibi şu şekildedir:

$\bullet$ $P(n)$ önermesini $n=1,2,\dots, m$ için ispatla. $m$ sabit bir pozitif tam sayı.

$\bullet$ $P(n)$ önermesinin bir $n=k, k+1, \dots, k+m-1$ doğal sayıları için doğru olduğunu kabul et.

$\bullet$ $n=k+m$ için $P(k+m)$ önermesinin de doğru olduğunu ispatla.

Bu durumda da, her $n$ pozitif tam sayısı için $P(n)$ önermesi doğrudur, sonucuna varıyoruz.

 

Ne zaman tümevarım kullanabiliriz sorusunun yanıtı: genel olarak bu adımları uygulayabileceğimiz herhangi bir problem türünde tümevarım kullanabiliriz, olur. Doğal sayıların sonsuz elemanlı bir alt kümesindeki bir önerme için tümevarım uygulamayı akla getirebiliriz. Cevap veriyor gibi görünüp, aslında çok fazla bir şey söylemeyen bir şey yazdığımın farkındayım. Çünkü, 'matematikte bir yöntemi şuralarda kullanabiliriz' demek insan zihnini biraz kısıtlayıcı bir söz gibi geliyor. Daha önce başkasının aklına gelmemiş bir şekilde de bu yöntemi kullanabilirsiniz.

Bir hikaye paylaşabilirim: Sylvester'in doğru problemi (Sylvester's Line Problem) ile ilgili biliyorum. Problem yaklaşık 50 yıl sonra, Ekstrem Değer Prensibi kullanılarak çözülüyor. Bu prensip basitçe, gerçel sayıların sonlu elemanlı (boş olmayan) bir alt kümesinde bir en büyük eleman vardır, bir en küçük eleman vardır, der. Bu basit prensibi birisi (Grünwald) uygulayıp Sylvester'in doğru problemini çözmeyi başarmıştır.

 

Tümevarım için de, hiç akla gelmemiş bir problem üzerinde bu yöntemin uygulaması keşfedilebilir.

(2.6k puan) tarafından 
tarafından düzenlendi
Her $n \geq 3$ için $3^n >2^n + 2n^2$ olduğunu tümevarım ile ispatlayınız
Yani asil merak ettigim nokta,
Peano aksyomlarinda tumevarim aksyom ama zfc den kurunca dogal sayilari  tumevarim aksyom degil ispatlanmasi gereken bir teorem (sanirim). Bu ispati ariyordum.

Tümevarım'ın bir teorem olarak ispatı sitede şurada (Salih Durhan'ın mesajında) verilmişti. Bu işinize yarayabilir belki.

20,282 soru
21,821 cevap
73,503 yorum
2,523,589 kullanıcı