Gerçek aritmetik - True arithmetic

Gelen matematiksel mantık , gerçek aritmetik hepsi doğrudur kümesidir birinci dereceden ilgili tabloların aritmetik ait doğal sayılar . Bu teori ilişkili olan standart modelin içinde Peano aksiyomları içinde dilin sayıların aksiyomatik birinci düzenin. Gerçek aritmetik bazen Skolem aritmetiği olarak adlandırılır, ancak bu terim genellikle çarpma ile doğal sayıların farklı teorisine atıfta bulunur.

Tanım

İmza ait Peano aritmetik ait (iyi biçimli) formülleri toplama, çarpma ve halefi işlev simgelerini, eşitlik ve ilişki sembolleri Küçüktür ve 0. için sabit bir sembolü içeren birinci dereceden aritmetik dilinin inşa edilmiştir Bu sembollerden mantıksal sembollerle birlikte birinci dereceden mantığın olağan şekilde .

Yapı , aşağıdaki gibi Peano aritmetik bir modeli olarak tanımlanır. ${\görüntüleme stili {\matematiksel {N}}}$

• Söylem alanı kümesidir , doğal sayılar${\displaystyle \mathbb {N} }$
• 0 sembolü 0 sayısı olarak yorumlanır,
• İşlev sembolleri, üzerinde olağan aritmetik işlemler olarak yorumlanır ,${\displaystyle \mathbb {N} }$
• Eşitlik ve daha az ilişki sembolleri, üzerinde olağan eşitlik ve düzen ilişkisi olarak yorumlanır .${\displaystyle \mathbb {N} }$

Bu yapı, birinci dereceden aritmetiğin standart modeli veya amaçlanan yorumu olarak bilinir .

Birinci mertebeden aritmetik dilinde bir cümle , az önce tanımlanan yapıda doğruysa, doğru olduğu söylenir . Notasyon , cümlenin doğru olduğunu belirtmek için kullanılır .${\görüntüleme stili {\matematiksel {N}}}$${\displaystyle {\mathcal {N}}\models \varphi }$${\görüntüleme stili \varphi }$${\görüntüleme stili {\matematiksel {N}}.}$

Gerçek aritmetik , birinci dereceden aritmetik dilinde Th( ) ile yazılmış doğru olan tüm cümlelerin kümesi olarak tanımlanır . Bu küme, eşdeğer olarak, yapının (tam) teorisidir . ${\görüntüleme stili {\matematiksel {N}}}$${\görüntüleme stili {\matematiksel {N}}}$${\görüntüleme stili {\matematiksel {N}}}$

aritmetik tanımlanamazlık

Gerçek aritmetik merkez sonucudur undefinability teoremi ait Alfred Tarski (1936). Th( )${\görüntüleme stili {\matematiksel {N}}}$ kümesinin aritmetik olarak tanımlanamayacağını belirtir . Bu , birinci dereceden aritmetik dilinde, bu dilde her θ tümcesi için , ${\görüntüleme stili \varphi (x)}$

${\displaystyle {\mathcal {N}}\models \theta \qquad }$ ancak ve ancak ${\displaystyle {\mathcal {N}}\models \varphi ({\underline {\#(\theta )}}).}$

İşte θ cümlesinin kanonik Gödel sayısının rakamı . ${\displaystyle {\altı çizili {\#(\theta )}}}$

Post'un teoremi undefinability teoreminin keskin versiyonudur gösterileri Bunun tanımlanabilirlik arasında bir ilişki Th ( )${\görüntüleme stili {\matematiksel {N}}}$ ve Turing derece kullanarak, aritmetik hiyerarşiyi . Her doğal sayı n için , Th _n ( )${\görüntüleme stili {\matematiksel {N}}}$ , yalnızca aritmetik hiyerarşide veya daha düşük olan tümcelerden oluşan Th( )'${\görüntüleme stili {\matematiksel {N}}}$ nin alt kümesi olsun . Post'un teoremi, her n için , Th _n ( )' nin aritmetik olarak tanımlanabilir olduğunu, ancak yalnızca 'den daha yüksek bir karmaşıklık formülüyle tanımlanabileceğini gösterir . Böylece tek bir formül Th( ) tanımlayamaz , çünkü ${\displaystyle \Sigma _{n}^{0}}$${\görüntüleme stili {\matematiksel {N}}}$${\displaystyle \Sigma _{n}^{0}}$${\görüntüleme stili {\matematiksel {N}}}$

${\displaystyle {\mbox{Th}}({\mathcal {N}})=\bigcup _{n\in \mathbb {N} }{\mbox{Th}}_{n}({\mathcal {N }})}$

ancak hiçbir formül keyfi olarak büyük n için Th _n ( )${\görüntüleme stili {\matematiksel {N}}}$ tanımlayamaz .

hesaplanabilirlik özellikleri

Yukarıda tartışıldığı gibi, Th( )${\görüntüleme stili {\matematiksel {N}}}$ Tarski teoremi ile aritmetik olarak tanımlanamaz. Bir o Post'un teoremi kurar tabii sonucu Turing derecesi arasında Th ( )${\görüntüleme stili {\matematiksel {N}}}$ ise 0 ^(ω) ve benzeri Th ( )${\görüntüleme stili {\matematiksel {N}}}$ değil Karar verilebilen ne de ardışık enumerable .

Th ( )${\görüntüleme stili {\matematiksel {N}}}$ yakın teori ile ilgilidir th ( )${\görüntüleme stili {\matematiksel {R}}}$ arasında ardışık enumerable Turing derece arasında imza, kısmi siparişler . Özellikle, hesaplanabilir fonksiyonlar S ve T vardır, öyle ki:

• Birinci mertebeden aritmetiğin imzasındaki her φ tümcesi için, φ Th( )' ${\görüntüleme stili {\matematiksel {N}}}$dedir , ancak ve ancak S ( φ ) Th( )' deyse${\görüntüleme stili {\matematiksel {R}}}$ .
• Her bir cümle için ψ kısmi siparişlerin imza, ψ olan Th ( )${\görüntüleme stili {\matematiksel {R}}}$ , ancak ve ancak , T ( ψ ) olan Th ( )${\görüntüleme stili {\matematiksel {N}}}$ .

Model-teorik özellikler

Gerçek aritmetik kararsız bir teoridir ve sayılamayan her kardinal için modelleri vardır . Bulunmadığından sürekli birçok çeşit boş kümesi üzerinden, gerçek aritmetik da vardır sayılabilen modelleri. Teori tamamlanmış olduğundan , tüm modelleri temel olarak eşdeğerdir . ${\ Displaystyle 2^{\kappa }}$${\görüntüleme stili \kappa }$${\ Displaystyle 2^{\aleph _{0}}}$

İkinci dereceden aritmetiğin gerçek teorisi

İkinci dereceden aritmetik gerçek teorisi dilinde bütün cümlelerin oluşuyor ikinci dereceden aritmetik kimin birinci dereceden kısmı ikinci dereceden aritmetik standart modelin, memnunlar ve yapıdır olan ikinci dereceden kısmı oluşur ve her alt kümesi . ${\görüntüleme stili {\matematiksel {N}}}$${\displaystyle \mathbb {N} }$

Birinci mertebeden aritmetiğin gerçek teorisi, Th( )${\görüntüleme stili {\matematiksel {N}}}$ , ikinci mertebeden aritmetiğin gerçek teorisinin bir alt kümesidir ve Th( )${\görüntüleme stili {\matematiksel {N}}}$ ikinci mertebeden aritmetikte tanımlanabilir. Bununla birlikte, Post'un teoreminin analitik hiyerarşiye genelleştirilmesi, ikinci dereceden aritmetiğin gerçek teorisinin, ikinci dereceden aritmetikte tek bir formülle tanımlanamayacağını göstermektedir.

Simpson (1977) , ikinci mertebeden aritmetiğin gerçek teorisinin, kısmi mertebelerin imzasında tüm Turing derecelerinin kısmi mertebesi teorisi ile hesaplanabilir şekilde yorumlanabileceğini ve bunun tersi olduğunu göstermiştir .

Notlar

Referanslar

• Boolo, George ; Burgess, John P. ; Jeffrey, Richard C. (2002), Hesaplanabilirlik ve mantık (4. baskı), Cambridge University Press, ISBN 978-0-521-00758-0.
• Bovykin, Andrey; Zhang, Yi (ed.), İçinde "aritmetik modelleri sırası-tipleri Üzerine" Kaye, Richard (2001), Mantık ve cebir , Çağdaş Matematik, 302 , American Mathematical Society, s. 275-285, ISBN 978-0-8218-2984-4.
• Shore, Richard (2011), "Yinelemeli olarak sayılabilir dereceler", Griffor, ER (ed.), Handbook of Computability Theory , Studies in Logic and the Foundations of Mathematics, 140 , North-Holland (yayınlanmış 1999), s. 169 -197, ISBN 978-0-444-54701-9.
• Simpson, Stephen G. (1977), "Yinelemeli çözülemezlik derecelerinin birinci derece teorisi", Annals of Mathematics , Second Series, Annals of Mathematics, 105 (1): 121–139, doi : 10.2307/1971028 , ISSN  0003 -486X , JSTOR  1971028 , MR  0432435
• Tarski, Alfred (1936), "Der Wahrheitsbegriff in den formalisierten Sprachen". İngilizce çevirisi "Formalized Languages'de Hakikat Kavramı" Corcoran, J., ed. (1983), Logic, Semantics and Metamathematics: 1923'ten 1938'e kadar olan makaleler (2. baskı), Hackett Publishing Company, Inc., ISBN 978-0-915144-75-4

Dış bağlantılar

• Weisstein, Eric W. "Aritmetik" . Matematik Dünyası .
• Weisstein, Eric W. "Peano Aritmetiği" . Matematik Dünyası .
• Weisstein, Eric W. "Tarski Teoremi" . Matematik Dünyası .