Kompaktlık teoremi - Compactness theorem

Gelen matematiksel mantık , kompakt teoremi bir belirtmektedir seti arasında birinci dereceden cümle bir sahiptir modeli ise her yalnızca sonlu alt kümesi bunun bir model var. Bu teorem, model teorisinde önemli bir araçtır , çünkü son derece tutarlı olan herhangi bir cümle kümesinin modellerini oluşturmak için yararlı (ancak genellikle etkili olmayan) bir yöntem sağlar .

İçin kompakt teoremi önermeler mantığı bir sonucudur Tychonoff teoremi (söylüyor ürünün bir kompakt boşluk kompakt uygulanan kompakt) Taş boşluklar , dolayısıyla teoremi adı. Benzer şekilde, topolojik uzaylarda kompaktlığın sonlu kesişim özelliği karakterizasyonuna benzer : kompakt bir uzaydaki kapalı kümeler topluluğu, eğer her sonlu alt koleksiyonun boş olmayan bir kesişim noktası varsa, boş olmayan bir kesişim vardır.

Kompaktlık teoremi, Lindström teoreminde birinci dereceden mantığı karakterize etmek için kullanılan aşağı doğru Löwenheim-Skolem teoremi ile birlikte iki temel özellikten biridir . Kompaktlık teoreminin birinci mertebeden olmayan mantığa bazı genellemeleri olmasına rağmen, kompaktlık teoreminin kendisi, çok sınırlı sayıda örnek dışında, bunlarda geçerli değildir.

Tarih

Kurt Gödel sayılabilir kompaktlık teoremini 1930'da kanıtladı . Anatoly Maltsev sayılamaz durumu 1936'da kanıtladı.

Başvurular

Kompaktlık teoreminin model teorisinde birçok uygulaması vardır; birkaç tipik sonuç burada özetlenmiştir.

Yoğunluk teoremi ima Robinson'un prensibi : birinci dereceden bir cümle her tutarsa alan bir karakteristik sıfır, sonra sabit vardır p cümle karakteristik daha büyük her alan için tutar, öyle ki p . Bu şu şekilde görülebilir: varsayalım ki φ, karakteristik sıfırın her alanında tutan bir cümle. O halde, aksiyomlar ve sonsuz cümle dizisi 1 + 1 ≠ 0, 1 + 1 + 1 ≠ 0,… ile birlikte ¬φ olumsuzlaması tatmin edici değildir (çünkü ¬φ'nin geçerli olduğu hiçbir özellik 0 alanı yoktur. ve sonsuz cümle dizisi, herhangi bir modelin karakteristik 0) alanı olmasını sağlar. Bu nedenle, bu cümlelerin tatmin edici olmayan sonlu bir A alt kümesi vardır . A'nın ¬φ alan aksiyomlarını ve bazı k için 1 + 1 + ... + 1 ≠ 0 biçiminin ilk k cümlelerini içerdiğini varsayabiliriz (çünkü daha fazla cümle eklemek, tatmin edici olmayışı değiştirmez). Let B Herşeyden cümleler içeren A ¬φ hariç. Daha sonra daha küçük karakteristik bir daha sonra ile herhangi bir alan k bir modeldir B ve ¬φ birlikte B karşılanabilir değildir. Φ her modelinde sahip olması gerekir, bu araçlar B φ daha karakteristik Greater her alanında tutar tam anlamı, k .

Kompaktlık teoreminin ikinci bir uygulaması, keyfi olarak büyük sonlu modellere veya tek bir sonsuz modele sahip herhangi bir teorinin, keyfi büyük kardinalite modellerine sahip olduğunu gösterir (bu, Yukarı Löwenheim-Skolem teoremidir ). Dolayısıyla, örneğin, sayılamayacak kadar çok 'doğal sayıya' sahip standart olmayan Peano aritmetiği modelleri vardır . Bunu başarmak için, T başlangıç ​​teorisi ve κ herhangi bir kardinal sayı olsun . Her κ elemanı için T diline bir sabit sembol ekleyin . Sonra T'ye , yeni koleksiyondaki herhangi iki farklı sabit sembolle gösterilen nesnelerin farklı olduğunu söyleyen bir cümle koleksiyonu ekleyin (bu, κ ² cümleden oluşan bir koleksiyondur ). Bu yeni teorinin her sonlu alt kümesi, yeterince büyük sonlu bir T modeli veya herhangi bir sonsuz model tarafından tatmin edilebilir olduğundan, genişletilmiş teorinin tamamı tatmin edilebilirdir. Ancak genişletilmiş teorinin herhangi bir modeli en azından

Kompaktlık teoreminin üçüncü uygulaması , gerçek sayıların standart olmayan modellerinin oluşturulmasıdır, yani "sonsuz küçük" sayıları içeren gerçek sayılar teorisinin tutarlı uzantılarıdır. Bunu görmek için, gerçek sayılar teorisinin birinci dereceden aksiyomatizasyonu Σ olsun. Aksiyomuna ε> 0 ve aksiyomlar ε <1 / dile yeni bir sabit sembol £ değenni ekleyerek ve s için bitişik elde teoriyi düşünün n tüm pozitif tamsayılar için n . Açıkça, standart gerçek sayılar R , bu aksiyomların her sonlu alt kümesi için bir modeldir, çünkü gerçek sayılar Σ'daki her şeyi karşılar ve uygun ε seçimiyle, ε ile ilgili aksiyomların herhangi bir sonlu alt kümesini karşılamak için yapılabilir. Kompaktlık teoremine göre, Σ'yi karşılayan ve aynı zamanda sonsuz küçük bir eleman contains içeren bir * R modeli vardır . Benzer bir argüman, ω> 0, ω> 1, vb. Aksiyomlarla bitişiktir, sonsuz büyük tamsayıların varlığının, gerçeklerin herhangi bir aksiyomatizasyonu by ile göz ardı edilemeyeceğini gösterir.

Kanıtlar

Gödel'in tamlık teoremi kullanılarak kompaktlık teoremi kanıtlanabilir; bu teorem , bir dizi cümlenin ancak ve ancak ondan herhangi bir çelişki kanıtlanamazsa tatmin edilebilir olduğunu belirler. İspatlar her zaman sonlu olduğundan ve bu nedenle verilen cümlelerin yalnızca sonlu çoğunu içerdiğinden, kompaktlık teoremi takip eder. Aslında, kompaktlık teoremi Gödel'in tamlık teoremine eşdeğerdir ve her ikisi de , seçim aksiyomunun zayıf bir biçimi olan Boolean asal ideal teoremine eşdeğerdir .

Gödel başlangıçta kompaktlık teoremini tam olarak bu şekilde kanıtladı, ancak daha sonra kompaktlık teoreminin bazı "tamamen anlamsal" ispatları, yani ispatlanabilirliğe değil gerçeğe atıfta bulunan ispatlar bulundu . Bu kanıtlardan biri, aşağıdaki gibi seçim aksiyomuna dayanan ultra ürünlere dayanmaktadır :

İspat: Birinci dereceden bir L dilini düzeltin ve Σ, L-cümlelerinin her sonlu alt koleksiyonu olan i  ⊆ Σ bir modele sahip olacak şekilde bir L-cümleleri koleksiyonu olsun . Ayrıca yapıların doğrudan çarpımı olsun ve ben Σ'nin sonlu altkümelerinin toplamı olacağım . Her biri için I içinde I A izin _i  : = { j ∈ I  : j ⊇ i }. Tüm bu A _i kümelerinin ailesi uygun bir filtre oluşturur , bu nedenle A _i biçiminin tüm kümelerini içeren bir ultra filtre U vardır . ${\ displaystyle {\ mathcal {M}} _ {i}}$${\ displaystyle \ prod _ {i \ subseteq \ Sigma} {\ mathcal {M}} _ {i}}$

Şimdi her in Σ formülü için elimizde:

• grubu A _{φ} olan U
• ne zaman j  ∈ A _{φ} , sonra φ ∈  j , dolayısıyla φ tutar ${\ displaystyle {\ mathcal {M}} _ {j}}$
• φ özelliğine sahip tüm j kümesi, A _{{φ} '} nın bir üst kümesidir , dolayısıyla U${\ displaystyle {\ mathcal {M}} _ {j}}$

Łoś teoremini kullanarak ultrapüründe φ değerinin geçerli olduğunu görürüz . Dolayısıyla bu ultra ürün, Σ 'deki tüm formülleri karşılar. ${\ displaystyle \ prod _ {i \ subseteq \ Sigma} {\ mathcal {M}} _ {i} / U}$

Ayrıca bakınız

• Barwise kompaktlık teoremi
• Herbrand teoremi
• Boole cebri konularının  listesi - Wikimedia liste makalesi
• Löwenheim-Skolem teoremi  - Matematiksel teorem

Notlar

Referanslar

• Boolos, George; Jeffrey, Richard; Burgess, John (2004). Hesaplanabilirlik ve Mantık (dördüncü baskı). Cambridge University Press.
• Chang, CC; Keisler, H. Jerome (1989). Model Teorisi (üçüncü baskı). Elsevier. ISBN   0-7204-0692-7 .
• Dawson, John W. junior (1993). "Birinci dereceden mantığın kompaktlığı: Gödel'den Lindström'e". Mantık Tarihi ve Felsefesi . 14 : 15–37. doi : 10.1080 / 01445349308837208 .
• Hodges, Wilfrid (1993). Model teorisi . Cambridge University Press. ISBN   0-521-30442-3 .
• Marker, David (2002). Model Teorisi: Giriş . Matematikte Lisansüstü Metinler 217. Springer. ISBN   0-387-98760-6 .
• Kafes, John K. (1997). Matematiksel Analizin Temelleri . Oxford University Press. ISBN   0-19-853375-6 .