Aritmetize edilmiş tamlık teoremi
Kikuchi'nin makalesi Kolmogorov karmaşıklığı ve ikinci eksiklik teoreminde , "aritmetize edilmiş tamlık teoremi" ni şu şekilde ifade eder:
İzin Vermek $T$ bir dilde yinelemeli olarak aksiyomlaştırılabilir bir teori olmak $\mathcal{L}$, $C$ bir dizi yeni sabit olmak ve $\overline{\mathcal{L}}=\mathcal{L}\cup C$. Bir formül diyoruz$\phi(x)$ içinde $\mathcal{L}_{A}$ bir model tanımlar $T$ bir teoride $S$ içinde $\mathcal{L}_{A}$ eğer içinde ispatlayabilirsek $S$ bu set
$$ \{ \sigma : \text{$\ sigma$ is a sentence in $\ overline {\ mathcal {L}}$ that satisfies $\ phi (\ ulcorner \ sigma \ urcorner)$} \} $$
bir modelin temel diyagramını oluşturur $T$ bir evrenle $C$.
Teorem 4.1. (Aritmetize edilmiş tamlık teoremi). Bir formül var$\text{Tr}_{T}({\ulcorner}x{\urcorner})$ içinde $\mathcal{L}_{A}$ bir model tanımlayan [aritmetik dili] $T$ içinde $\text{PA} + \text{Con}(T)$ , nerede $\text{Con}(T)$ içinde bir cümle $\mathcal{L}_{A}$ bunun anlamı $T$ tutarlıdır.
Bu teoremin anlamadığım birkaç yönü var:
Bir model tanımlayan bir formül kavramı $T$ içinde $\text{PA} + \text{Con}(T)$ seti içerir $ \{ \sigma : \text{$\ sigma$ is a sentence in $\ overline {\ mathcal {L}}$ that satisfies $\ phi (\ ulcorner \ sigma \ urcorner)$} \} $. Bunu nasıl resmileştireceğimi bilmiyorum$\text{PA}$, bununla ilgili bir şeyi kanıtlamak şöyle dursun.
Aynı şey şu modellerin modelleri hakkında $T$. Söyle$T = \text{ZFC}$, o zaman aritmetik dilinde bir modelin olduğunu nasıl söyleyebilirsiniz? $T$ Bu ve benzeri özelliklerle (temel diyagramı yukarıdaki küme ve evrenidir)?
Farklı bir soru türü: bu teoremin kullanımı nedir (genel anlamda, bahsedilen makalenin ötesinde)? Neden aritmetik tamlık teoremi olarak adlandırılıyor?
Yanıtlar
Yeniden: $(1)$Burada göründüğünden daha azı var. Kilit nokta, bir formül hazırlayabilmemizdir.$\theta$ Godel sayılarının kümesini tanımlayan $\overline{\mathcal{L}}$cümle; bu eldeyken, sadece bakıyoruz$$S=\{x: \theta(x)\wedge\phi(x)\}.$$ Bu oldukça sıkıcı bir şekilde tanımlanabilir.
Şimdi bunu söylediğimizde $S$ etki alanına sahip bazı yapıların temel diyagramıdır $C$bunu kastediyoruz $S$ temel bir diyagramın olağan özelliklerini karşılar - ve bunlar sözdizimsel özellikler olduğundan, Gödel numaralandırma yoluyla şunu ifade edebiliriz: $S$var ya da yok. Örneğin, aşağıdakilerin her birini isteyeceğiz:
Eğer $\ulcorner\sigma_0\urcorner$, $\ulcorner\sigma_1\urcorner\in S$ sonra $\ulcorner\sigma_0\wedge\sigma_1\urcorner\in S$.
Eğer $\ulcorner \exists x\sigma(x)\urcorner\in S$ o zaman bazıları için $c\in C$ sahibiz $\ulcorner\sigma(c)\urcorner\in S$. (Bu, "evren ile"$C$"bit.)
$\ulcorner\perp\urcorner\not\in S$.
Biraz daha doğru olarak, bazı sabit değişkenlere göre örneğin birleşme ve varoluşsal nicelemeye karşılık gelen ilkel özyinelemeli fonksiyonlara sahibiz ve yukarıdaki ilk iki madde işareti, uygun kapanma / varoluş koşullarını ifade eder. $S$bu işlevlerle ilgili olarak. Üçüncü mermi bu arada önemsizliği önler.
Temel olarak, nokta, etki alanına sahip bazı yapıların temel diyagramı olma özelliğidir. $\mathbb{N}$ birinci dereceden ifade edilebilirdir (çünkü yukarıdakilere göre "yerel kapanma / varlık / yokluk koşulları" anlamına gelir).
Yeniden: $(2)$, sezgisel olarak konuşursak, mesele şu ki, örneğin keyfi modellerden bahsetmiyoruz. $\mathsf{ZFC}$, ancak yalnızca etki alanına sahip olanlar $\mathbb{N}$. Etki alanına sahip bir yapı$\mathbb{N}$ tamamen tek bir doğal sayı kümesiyle tanımlanır $X$, ve "$X$ bir modelin atomik diyagramıdır $\mathsf{ZFC}$"yukarıdaki birinci dereceden ifade edilebilir: sadece"$X$ yukarıdaki temel sözdizimsel özelliklere sahiptir ve her biri $\mathsf{ZFC}$-axioms içinde $X$. "
Bunun daha gizemli hale getirilebileceğini düşünüyorum çünkü genellikle $\mathsf{ZFC}$oldukça karmaşık ve kesinlikle etki alanına sahip olmadığı için$\mathbb{N}$. Ama aşağı doğru Lowenheim-Skolem,$\mathsf{ZFC}$(hiç de tutarlı olduğunu varsayarak) ayrıca etki alanı olan birçok modele sahiptir.$\mathbb{N}$. Bunlar, bu yaklaşımda ele alabileceğimiz modellerdir.
Yeniden: $(3)$mesele, tamlık teoreminin olağan ifadesinin
her tutarlı teorinin bir modeli vardır
aritmetik bağlamında tamamen çılgın. Temel olarak, yalnızca aritmetik dilindeki sonlu kümeler hakkında doğrudan konuşabiliriz , bu nedenle "Presburger aritmetiğinin modelleri yoktur" cümlesini saf bir şekilde "aritmetik olarak ifade edersek" doğru bir şey elde ederiz.
(Örneğin Ackermann yorumuna bakın . (Diyelim)$\mathsf{PA}$ uygun bir şekilde eşdeğer kümeler teorisine, ancak bu teori "Her küme sonludur" u kanıtlıyor.
Öyleyse, tamlık teoreminin bir versiyonunun bir aritmetik teorisinde geçerli olmasını istiyorsak, onun "modelleri" tüm evren üzerindeki ilişkilerden oluşmalıdır; ve tabii ki tanımlanabilir ilişkilerden oluşmaları gerekecek , çünkü içsel olarak tanımlanamayan ilişkiler hakkında konuşamayız.
Diğer bir seçenek ise, sonsuz kümeler hakkında doğrudan konuşabilen muhafazakar uzantılar kullanmak olabilir; bu, örneğin burada alınan yaklaşımdır . Oynadığım tüm bağlamlarda bu yaklaşım işe yarıyor ve bu yüzden genellikle tercih ediyorum. Bahsedilen,$(i)$ Doğru hatırlıyorsam, bu yaklaşımın can sıkıcı bir şekilde kötü olduğu veya değerli bilgileri gizlediği durumlar vardır (bence bu, çok zayıf aritmetik teorileriyle gerçekleşir) ve $(ii)$ Sadece birinci dereceden aritmetik dilinde bir tamlık teoremi elde edebilmemiz kendi başına ilginçtir.