Aksiyomlanabilir Teorilerin Tam Tutarlı Uzantılarının Hesaplanabilirlik Dereceleri

Year 2018, Volume: 22 Issue: Special, 270 - 276, 05.10.2018

Ahmet Çevik

Abstract

Bu makalede matematiksel mantık ve temellerin bir dalı olan {\em hesaplanabilirlik kuramı} ile ilişkili $\Pi^0_1$ sınıfları (kümeleri) çalışılmıştır. ZFC kümeler kuramı veya Peano aritmetiği gibi aksiyomlanabilir herhangi bir teorinin tam tutarlı uzantılarının kümesi, bir $\Pi^0_1$ sınıfı olarak görülür. Benzer şekilde herhangi bir $\Pi^0_1$ sınıfı, aksiyomlanabilir bir teorinin tam tutarlı uzantılarının kümesi olarak ifade edilebilir. Aynı zamanda $\Pi^0_1$ sınıfları, doğal sayılar kümesi $\omega$ olarak gösterilirse, $2^\omega$ Cantor uzayının hesaplanabilir ve kapalı altkümeleri olarak görülebilir. Bu yüzden bir $\Pi^0_1$ sınıfı, sonlu sayıda dallanmaya sahip hesaplanabilir bir ağacın sonsuz yollarının kümesi olarak ele alınabilir. Kabaca tanımıyla, bir $A\subset\omega$ kümesinin hesaplanabilir olması demek, verilen herhangi bir $x\in\omega$ için $x\in A$ olup olmadığına algoritmik bir hesaplama sonucunda cevap verebilmek demektir. Hesaplamada ek olarak başka kümenin eleman bilgisi kullanıldığında hesaplanabilirlik kavramı göreceleştirilmiş olur. Herhangi bir $B\subset\omega$ kümesinin bir $A\subset\omega$ kümesini hesaplaması $A\leq_T B$ ifadesi ile gösterilsin. $A$ ve $B$ kümelerinin {\em katılımı} $A\oplus B=\{2i:i\in A\}\cup\{2i+1:i\in B\}$ olarak tanımlansın. $\emptyset'$ {\em durma kümesini} göstersin. Bu çalışmada kanıtlayacağımız teorem şudur: {\bf (Teorem 3.10). }Öyle bir aksiyomlanabilir teori $T$ vardır ki eğer $R$ ve $S$ kümeleri $T$'nin tam tutarlı olan herhangi iki uzantısı ise, $\emptyset'\not\leq_T R\oplus S$. Bu sonuç, Jockusch ve Soare'ın \cite{JS} kesişim baz teoreminin birleşim (katılım) için doğru olmadığını göstermektedir.

Keywords

Matematiksel mantık, Hesaplanabilirlik; Turing dereceleri; Aksiyomlanabilir teoriler; Cantor Uzayı; Pi^0_1 sınıfları

References

• [1] Cenzer, D. 1999. P01 Classes in Recursion Theory. Handbook of Computability Theory. North-Holland, Studies in Logic and the Foundations of Mathematics, 140, 37–89.
• [2] Cooper, S. B. 2004. Computability Theory. Chapman & Hall/CRC Mathematics.
• [3] Çevik, A. 2013. Antibasis theorems for P01 classes and the jump hierarchy. Archive for Mathematical Logic, 52, Sayı 1-2, 137-142.
• [4] Çevik, A. 2014. Degrees of members of P01 classes. University of Leeds, Doktora Tezi, 104s.
• [5] Çevik, A. 2012. Hesaplanabilirlik Kuramı ve Turing Derecelerine Giriş, Gaziosmanpaşa Üniversitesi Bilimsel Araştırma Dergisi 1, 1-20.
• [6] Downey, R., D. Hirshfeldt, D. 2010. Algorithmic Randomness and Complexity. Springer-Verlag, 855s.
• [7] Groszek, M. J., Slaman, T. A. 1997. P01 classes and minimal degrees. Annals of Pure and Applied Logic, 87(2), 117-144.
• [8] Jockusch, C., Soare, R. I. 1972. P01 classes and degrees of theories. Trans. Amer. Math. Soc. 173, 33–56.
• [9] Moss, L. S., Topal, S. (teslim edildi, 2017). Syllogistic Logic with Cardinality Comparisons, On Infinite Sets.
• [10] Odifreddi, P. 1999. Classical Recursion Theory Vol. I & Vol. II. North-Holland, Studies in Logic and the Foundations of Mathematics.
• [11] Soare, R. 1987. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 437s.
• [12] Topal, S. 2015. An Object-Oriented Approach to Counter-Model Constructions in a Fragment of Natural Language. Bitlis Eren Üniversitesi Fen Bilimleri Dergisi, 4(2), 103-111.
• [13] Topal, S. 2016. A Syllogistic Fragment of English with Ditransitive Verbs in Formal Semantics. Journal of Logic, Mathematics and Linguistics in Applied Sciences, 1(1), 1-23.
• [14] Topal, S. 2017. Bazı Sillojistik ve Kardinalite Karşılaştırmalı Lojiklerin Türetimlerinin Cebirsel ve Etiketli Çizge Teorik Özellikleri Üzerine. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi. DOI:10.19113/sdufbed.50072