Polytropy

Ders ev sayfası

Giriş

Kümeler kuramı, Öklid’in geometrisi gibidir:

• Öğeler’de ortak kavramları kullanarak postulatlardan diğer önermeleri kanıtlarız.

• Kümeler kuramında ise mantığın kurallarını kullanarak aksiyomlardan diğer teoremleri kanıtlarız.

Kümeler kuramında her küme bir sınıftır; aslında her a kümesi, {x: x ∈ a} sınıfıdır. Bazı sınıflar küme değildir; örneğin {x: x ∉ x} sınıfı bir küme olamaz. Aksiyomlara göre bazı sınıflar kümedir. Boş sınıf hariç her sınıfın elemanı veya elemanları vardır, ve bunların hepsi bir kümedir.

Aşağıdaki özetin verdiğinden daha fazla ayrıntı görmek istiyorsanız, ders kitabına bakın veya bana sorun! Ya matematikte ya da Türkçe’de hatalar görürseniz, benimle haberleşin.

Aşağıdaki ve kitaptaki numaralar farklıdır:

İçerik

• Formüller, Cümleler, ve Doğruluk
• Sağlama ve Sınıflar
• Kümeler
• Doğal Sayılar
• Ordinaller

Formüller, Cümleler, ve Doğruluk

Biçimsel bir dil tanımlayacağız, ve kümeler kuramının her teoremi, dilimizin bir cümlesi olacak. Bir cümle, serbest değişkeni olmayan bir formül olacak.

Resmi dilimizde sabitler ve değişkenler vardır, ve her biri bir terimdir.

• Bir sabit, bir kümenin adıdır.
• Bir değişken, bir zamir gibidir.

Formüllerin örneklerini yazarken

• sabit olarak a, b, c, A, B, C, 𝒜, ℬ, 𝒞, α, β, γ gibi harfler;

• değişken olarak x, y, z, X, Y, Z, ξ, η, ζ gibi harfler;

• terim olarak s, t, u gibi harfler

kullanacağız. Dikkat edin: A, B, C gibi siyah harfler, terim değildir. Yunan harflerini sadece ordinaller için kullanacağız; bir ordinal, çok özel bir kümedir.

Formüllerimizi, terimlerden ve başka simgelerden oluşturuz. Formüllerin örnekleri olarak φ, ψ, ve χ gibi harflerini kullanacağız. Formüllerin dört çeşidi vardır ve bunların aşağıdaki resmi tanımı özyinelidir.

1. t ∈ s bir içermedir.

2. ¬φ bir değillemedir, ve tek bileşeni φ olur.

3. (φ ∧ ψ) bir tümel evetlemedir, ve bileşenleri φ ve ψ olur.

4. ∃x φ bir örneklemedir, ve tek bileşeni φ formülüdür.

Bir içerme, bölünemez bir formüldür; diğer formüller, bileşiktir.

Formüllerin tanımı özyineli olduğundan formüllerin bazı özellikleri tümevarım ile gösterilebilir. İlk teorem bir örnektir.

Teorem 1. Eğer en az bir simge

• ya bir formülün sonuna eklenirse
• ya da formülün sonundan çıkarılırsa,

o zaman kalan simgeler bir formül oluşturmaz.

Kanıt.

1. t ∈ s için iddia doğrudur.
2. İddia φ için doğru ise ¬φ için de doğrudur.
3. İddia φ ve ψ için doğru ise (φ ∧ ψ) için de doğrudur.
4. İddia φ için doğru ise ∃x φ için de doğrudur. ∎

Teorem 2. Her formül tek bir şekilde bir formül olur. ∎

Bu ilk iki teorem kümeler kuramının teoremi değil, kümeler kuramının teoremlerini biçimsel cümle olarak yazmak mümkün kılacak.

Teorem 2’den dolayı değişkenlerin serbest geçişlerinin tanımı özyineli olabilir:

1. Bir içermede bir değişkenin her geçişi, serbesttir.
2. Bir değillemenin bileşeninde bir değişkenin her serbest geçişi, değillemenin kendisinde serbesttir.
3. Bir tümel evetlemenin bir bileşeninde bir değişkenin her serbest geçişi, tümel evetlemenin kendisinde serbesttir.
4. Bir ∃x φ örneklemesinde
   • x’ten farklı olan bir değişkenin φ’deki her serbest geçişi serbesttir;
   • x’in hiç serbest geçişi yoktur.

Bir değişkenin serbest olmayan geçişi bağlıdır. Bir formülde bir değişkenin serbest geçişi varsa, bu değişken, formülün bir serbest değişkenidir. Serbest değişkeni olmayan bir formül, bir cümledir. Cümlelerin örnekleri için σ ve τ gibi harfler kullanacağız.

φ’nin tek serbest değişkeni x olmak üzere eğer φ’de

• x’in her serbest geçişinin yerine a konulursa

  φ(a)

  cümlesi çıkar;

• x’in serbest olduğu yerlerde y bağlı değilse ve x’in her serbest geçişinin yerine y konulursa

  φ(y)

  formülü çıkar.

Bir cümle doğru veya yanlıştır, ikisi değildir.

1. Bir a bir b’nin bir elemanı ise a ∈ b doğrudur.
2. Bir σ yanlış ise ¬σ doğrudur.
3. Hem σ hem de τ doğru ise (σ ∧ τ) doğrudur.
4. Bir a için φ(a) doğru ise ∃x φ(x) doğrudur.

“σ doğrudur” ifadesinin yerine “σ” ifadesini yazabiliriz.

Resmi formüllerimiz için bazı kısaltmaları kullanırız.

Bir formülün en dış ayraçlarını yazmayabiliriz. İç ayraçlar silmek için ∧ ve ∨ bağlayıcısının ⇒ ve ⇔ bağlayıcısından daha güçlü olduğunu anlayabiliriz; örneğin φ ∧ ψ ⇒ χ ifadesinin anlamı (φ ∧ ψ) ⇒ χ olur.

Sağlama ve Sınıflar

Eğer φ(a) doğru bir cümle ise, o zaman a, φ’yi sağlar. Tek-değişkenli bir formülün sağlayanları, bir sınıf oluşturur. Bu durumda

• formül, sınıfı tanımlar;
• formülün sağlayanları, sınıfın elemanlarıdır.

Tek serbest değişkeni x olan bir φ formülünün tanımladığı sınıfı

olarak yazarız. Ayrıca A, B, C gibi siyah harfler sınıf olarak kullanırız.

Örneğin bir {x: φ} sınıfını A olarak yazalım. O zaman bir φ(t) formülünün yerine

yazabiliriz. Eğer ayrıca bir {x: ψ} sınıfını B olarak yazarsak, o zaman

cümlesini

olarak yazabiliriz. Bunun gibi bir cümle, bir kapsamadır. Genelde eğer

• a ∈ B ise, o zaman B, a’yı içerir;

• A ⊆ B ise, o zaman B, A’yı kapsar.

Kapsamalardan başka kısaltmalar elde ederiz:

Şimdi bazı teoremler saf mantıktan (yani hiçbir aksiyom kullanmadan) kanıtlayabiliriz.

Teorem 3. Eşitlik yansımalı, simetrik, ve geçişlidir, yani her durumda

Bundan dolayı eşitlik bir denklik bağıntısıdır.

Teorem 4. Kapsama yansımasızdır, yani her durumda

ayrıca geçişlidir, dolayısıyla bir sıralamadır.

Verilmiş sınıflardan aşağıdaki sınıflar elde edilir.

Yukarıdakiler ile aynı fikir cümleler veya sınıflar ile ifade edilebilir, örneğin de Morgan kuralları ya

ya da

biçiminde yazılabilir.

Kümeler

Her a kümesinden {x: x ∈ a} sınıfını elde edebiliriz. Kümeyi sınıf ile aynı olarak sayacağız. Böylece her küme bir sınıftır. Eşitliğin tanımından her durumda

Eşitlik Aksiyomu. Her durumda

Teorem 5. Her tek-serbest-değişkenli φ formülü için

Tanıma göre

bu sınıf A’nın kuvvet sınıfıdır. Örneğin

Kümelerden aşağıdaki sınıflar elde edilebilir. Burada φ, tek serbest değişkeni x olan bir formüldür.

Teorem 6.

Teorem 7 (Russell Paradoksu). {x: x ∉ x} sınıfı küme değildir. ∎

Ayırma Aksiyomu. Her {x ∈ a: φ} sınıfı bir kümedir.

Teorem 8. V bir küme değildir, ama her boş olmayan sınıfın kesişimi bir kümedir. ∎

Boş Küme Aksiyomu. 0 bir kümedir.

Bitiştirme Aksiyomu. Her durumda a ∪ {b} bir kümedir.

Özel olarak a′ sınıfı her zaman bir kümedir. Genelde herhangi ∃x (x = A ∧ φ) cümlesi

olarak yazılabilir.

Doğal Sayılar

Şimdi

ifadesi bir formülün kısaltmasıdır. Bu formülü sağlayan bir küme, tümevarımlıdır.

Sonsuzluk Aksiyomu. Tümevarımlı bir küme vardır.

Tümevarımlı kümeler T sınıfını oluşturduğunda ⋂T kesişimi

(omega, oo, uzun o) olarak yazalım. O zaman ω bir kümedir. Elemanları, doğal sayılardır.

Teorem 9 (Tümevarım). ω tümevarımlıdır ve onun hiç tümevarımlı özaltkümesi yoktur. ∎

Teorem 10. ω’nın her elemanı ya 0 ya da bir elemanın ardılıdır.

Kanıt. Alıştırma 1. ∎

Bir A sınıfı için eğer

(kısaca ∀y (y ∈ A ⇒ y ⊆ A)) ise, o zaman A geçişlidir.

Teorem 11. ω geçişlidir.

Kanıt. Alıştırma 2. ∎

Teorem 12. ω’nın her k ve n elemanı için k ∈ n ⇒ k ⊂ n.

Kanıt. n üzerinde tümevarım kullanacağız.

1. ω’da her k için k ∉ 0, dolayısıyla k ∈ 0 ⇒ k ⊂ 0.

2. ω’da bir m için her k için k ∈ m ⇒ k ⊂ m olsun. Şimdi bir k için k ∈ m ′ olsun. O zaman k ∈ m ∨ k = m.

   1. Eğer k ∈ m ise, o zaman hipoteze göre k ⊂ m, dolayısıyla m ⊆ m ′ olduğundan k ⊂ m ′.

   2. Eğer k = m ise, o zaman k ⊆ m; ayrıca m ⊄ m olduğundan hipotez sayesinde m ∉ m, dolayısıyla m ⊂ m ′, ve sonuç olarak tekrar k ⊂ m ′.

Tümevarım tamamlanmıştır. ∎

Teorem 13. ω’da her k ve n için k ′ = n ′ ⇒ k = n.

Kanıt. Alıştırma 3. ∎

Sonuç olarak aşağıdaki Peano Aksiyomları denilen önermeler teoremdir:

1. 0 hiç doğal sayının ardılı değildir.
2. Doğal sayıların ardılları eşit ise, sayılar da eşittir.
3. 0’ı iceren ve her elemanının ardılını da iceren bir küme, her doğal sayıyı icerir.

Tanıma göre her durumda

Böyle bir küme, bir sıralı ikilidir.

Teorem 14. (a, b) = (c, d) ⇒ a = c ∧ b = d.

Kanıt. Alıştırma 4. ∎

İki-konumlu bir bağıntı, elemanları sıralı ikili olan bir sınıftır. B bir örnek olduğunda (a, c) ∈ B ifadesinin yerine

yazılır. Bu şekilde ∈, =, ⊆, ⊂, ve herhangi sıralama, iki-konumlu bağıntıdır.

Alıştırma 5. ∈ bir sıralama değildir.

B iki-konumlu bir bağıntı olduğunda eğer bir D sınıfının her a, c, ve e elemanı için

ise B, D’yi sıralar (veya D’de bir sıralamadır). Eğer ayrıca D’nin her a ve c elemanı için

ise B, D’de sıralama olarak doğrusaldır. Eğer ayrıca

• D’nin her a elemanı için {x: x ∈ D ∧ x B a} bir küme,
• D’nin her boş olmayan altkümesinin (B’ye göre) en küçük elemanı var

ise, o zaman B, D’yi iyisıralar.

Alıştırma 6. ⊂ sıralaması evrende doğrusal değildir.

Teorem 15. ω’nın her k ve n elemanı için k ⊂ n ⇒ k ∈ n. ∎

Sonuç olarak ⊂ bir sıralama olduğundan ω’da ∈ bir sıralamadır.

Teorem 16. ω’nın her k ve n elemanı için k ⊆ n ∨ n ⊂ k. ∎

Sonuç olarak ω’da ⊂ gibi ∈ doğrusal bir sıralamadır.

Teorem 17. ω’nın her elemanı ∈ tarafından iyisıralanır. ∎

Teorem 18. ω, ∈ tarafından iyisıralanır.

Kanıt. Alıştırma 7. ∎

Alıştırma 8 (Güçlü Tümevarım). Her A kümesi için, ω’nın her n elemanı için n ⊆ A ⇒ n ∈ A ise ω ⊆ A.

Eğer iki-konumlu bir F bağıntısı için

ise F bir göndermedir, ve

• {x: ∃y x F y}, F’nin tanım sınıfı;

• {y: ∃x x F y}, F’nin değer sınıfıdır;

ayrıca

• a F b ise b’yi F(a) olarak,

• F’nin kendisini x ↦ F(x) olarak

yazarız. “F, tanım sınıfı A olan ve değer sınıfı B tarafından kapsanan bir göndermedir” cümlesini

olarak yazarız. Bu durumda C ⊆ A ise {y: ∃x (x ∈ C ∧ F (x) = y)} sınıfını kısaca

olarak yazarız. Bu sınıf, F altında C’nin imgesidir.

Yerleştirme Aksiyomu. Bir gönderme altında bir kümenin imgesi de bir kümedir.

Tanım sınıfı küme olan bir göndermenin kendisi bir kümedir.

Eğer F : A → A ise, o zaman A’da F  bir işlemdir.

Teorem 19 (Özyineleme). Her A kümesi için, A’nın her b elemanı ve f işlemi için öyle bir ve tek bir g göndermesi vardır ki g: ω → A ve

1. g(0) = b,

2. her durumda g(k′) = f(g(k)). ∎

Örneğin her A kümesi için, tanım kümesi ω olan bir ve tek bir x ↦ A + x göndermesi vardır ki

Birleşme Aksiyomu. Her kümenin birleşimi de bir kümedir.

Tanıma göre

olsun. O zaman tanım kümesi ω olan bir ve tek bir x ↦ ω ⋅ x göndermesi vardır ki

Tanıma göre

olsun. Bu kümede ∈ ve ⊂ bağlantısı aynıdır, ve bağlantı kümeyi iyisıralar. Kümenin ω ⋅ k′ elemanları ne 0 ne ardıl ama limittir.

İyisıralanmış bir A sınıfının her boş olmayan B altsınıfının en küçük elemanı vardır. Bu elemanı

olarak yazarız. Şimdi

1. A ≠ 0 ise min A vardır;

2. b ∈ A ama A’nın en büyük elemanı değilse A’nın b’den büyük olan elemanlarının en küçüğü, b’nin ardılıdır;

3. A’nın ne en küçük ne ardıl olan elemanları, limittir.

Burada b’nin ardılı ard(b) olarak yazalım.

Teorem 20 (İyisıralanmış Tümevarım). İyisıralanmış bir A sınıfı bir B sınıfını kapsasın.

1. A ≠ 0 ise min(A) ∈ B olsun.

2. Eğer B’nin bir c elemanı A’nın en büyük elemanı değilse ard(b) ∈ B olsun.

3. A’nın herhangi bir c limiti için eğer B, A’nın c’den küçük olan elemanlarını içerirse c ∈ B olsun.

O zaman B = A. ∎

Teorem 21 (İyisıralanmış Özyineleme). A bir < bağlantısı tarafından iyisıralanmış olsun; b bir küme olsun; F ve G, gönderme olsun. O zaman tanım sınıfı A olan, öyle bir ve tek bir H göndermesi vardır ki

1. A ≠ 0 ise H(min(A)) = b,

2. c ∈ A ama A’nın en büyük elemanı değilse H(ard(c)) = F(H(c)),

3. A’nın her c limiti için H(c) = G({H(x): x ∈ A ∧ x < c}). ∎

Örneğin b = 0 ve her durumda F(a) = a′ ve G(a) = a olsun. O zaman her H(a) kümesi bir ordinaldir.

Ordinaller

Alıştırma 9.

1. ∈ bağıntısının geçişli olduğu, geçişli olmayan bir küme vardır.

2. ∈ bağıntısının geçişli olmadığı, geçişli olan bir küme vardır.

Bir ordinal,

1. geçişli,

2. ∈ tarafından iyisıralanmış

bir kümedir. Ordinaller ON sınıfını oluşturur. Örneğin ω ∈ ON ve ω ⊂ ON.

α, β, γ, δ, ε, θ harfleri, ordinal sabittir; ξ, η, ζ harfleri, ordinal değişkendir.

Teorem 22. ON geçişlidir. ∎

Lemma 1. ON’de ∈ bir sıralamadır. ∎

Lemma 2. ON’de ∈ ve ⊂ aynı bağıntıdır. ∎

Teorem 23. Her ordinalde ∈ ve ⊂ aynı bağıntıdır.

Kanıt. Alıştırma 10. ∎

ON’nin ∈ veya ⊂ sıralaması < ile gösterilebilir.

Lemma 3. ON’nin < sıralaması doğrusaldır. ∎

Teorem 24. ON’nin < doğrusal sıralaması iyidir. ∎

Teorem 25 (Burali-Forti Paradoksu). ON bir küme değildir. ∎

Teorem 26. Her α’nın ardılı

• başka bir ordinaldir,

• α’dan daha büyük olan ordinallerin en küçüğüdür, kısaca

  α ′ = min {ξ: α < ξ}.

Kanıt. Alıştırma 11. ∎