Question

İyi sıralama prensibini nasıl ispatlarız?

Comments

http://matkafasi.com/891/iyi-siralama-ilkesi

Bu linkte daha güzel cevaplar varmış, yeni gördüm.

Answer 1

Teorem: $\emptyset \neq A \subset \mathbb N$ ise $A$'nin en kucuk elemani vardir.

Ispat: Olmadigini varsayalim. $B=\mathbb N - A$ olsun. $0 \in A$ olamaz, o zaman $B$'de olmali. (olursa en kucuk elemani olmus olur.)

Simdi $0,1,\cdots, n \in B$ is $n+1 \in B$ olmali: (ispat) Eger $n+1 \not \in B$ ise $n+1\in A$ en kucuk eleman olur. (kabulumuz ile celisir.)

O halde (tumevarimdan) $B=\mathbb N$ olmali,  yani $A=\emptyset$. Bu da celiski getirir.

Comments

sifiri da eleman olarak almisim ama cozumu etkilemiyor.

---

Neyle celistin? $A$'nin bos kume olmadigini kabul etmemistin ki? Contrapositive ile ispat ettin, contradiction ile degil :)

---

$\emptyset \neq A \subset \mathbb{N}$ olsun ve $A$'nin en kucuk elemani olmasin.

..olarak baslamistim. 

---

O zaman olur.

Answer 2

Madem sorulmuş, başka yerde olmasına karşın yine de yanıtlayalım.

İyi sıralama ilkesini ispatlayamayız. Zira iyi sıralama ilkesi kimi kümelerde doğru kimi kümelerde yanlıştır. Doğal sayılarda doğrudur ama tamsayılarda, rasyonel sayılarda yanlıştır. Ancak seçme aksiyomu sayesinde şöyle bir teorem vardır:

Her küme üzerinde iyi bir sıralama vardır. Yani, öyle bir sıralama vardır ki boş olmayan her kümenin en küçük elemanı vardır.

Doğal sayılarda iyi sıralama ilkesinin doğru olması nedeniyle tümevarım ispat yöntemi diye bir ispat yöntemi vardır. Seçme aksiyomunun yukarıda sözünü ettiğim getirisi nedeniyle de transfinite tümevarım denen bir nane vardır. Türkçe'de transfinite karşılık ne geliyor ne yazık ki bilmiyorum.

Comments

Transfinite induction/recursion= Sonlu ötesi tümevarım/özyineleme.

İyi sıralama ilkesi derken zaten çoğunlukla (implicit olarak) doğal sayılar kastedildiğinden iyi sıralama ilkesini ispatlayamayız demek biraz fazla olmuş sanki :)

---

Boşver abartmaktan zarar gelmez. Bu arada çeviri için sağol. (Bu arada olasılık sorusu aklımda, yapamayacam diye bakmaya çekindiğimden sesim çıkmadı hala)

---

Bütün cevaplar için teşekkür ediyorum. Sorumu "sonlu ötesi tümevarım nasıl çalışır?" diye değiştiriyorum.

---

Sonluötesi tümevarımı, doğal sayılardaki tümevarımın rastgele iyi sıralı kümelere genelleştirilmiş hali olarak düşünebilirsiniz. $C$ ordinal sayılardan oluşan bir sınıf olsun ve şu üç özellik sağlansın:

- $0 \in C$

-Her $\alpha \in C$ ordinali için $\alpha + 1 \in C$

-Eğer $\alpha$ bir limit ordinalse ve her $\beta < \alpha$ için $\beta \in C$ ise, o zaman $\alpha \in C$.

Bu durumda $C$ sınıfı ordinal sayılar sınıfına eşittir.

Her iyi sıralı küme bir ordinalle sıralı küme olarak eş yapısal olduğundan dolayı bu prensibi rastgele iyi sıralı kümeler ve başlangıç parçaları (initial segment) üzerinden ifade etmek de mümkün. Yani bir iyi sıralı $A$ kümesinin bir $B$ alt kümesini aldığınızda, $B$ kümesi $A$'nın minimal elemanını içeriyorsa ve her eleman için o elemanın öncüllerinin (predecessor) $B$'de olması o elemanın da $B$'de olmasını gerektiriyorsa o zaman $A=B$ olmalı.

---

Bunlarla alakalı olarak "well-founded induction" (iyi-temellendirilmiş tümevarım) ve "$\in$-induction" ($\in$-tümevarımı) kavramlarına da bakabilirsiniz. Hatta belki zamanım olursa burada bunlarla ilgili bir başlık açarım. Öte yandan yakın zamanda işlerim olduğundan vakti olanlara bırakıyorum!

---

Teşekkür ediyorum.  "Sonlu ötesi tümevarım nasıl çalışır?" diye bir başlık açtım.