Niceleyicilerin elenmesi yöntemi üzerine
Küçük Resim Yok
Tarih
1995
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Ege Üniversitesi
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
Matematik Lojike smtaktik( dizin ) ve semantik( anlam ) olmak üzere iki yolla yaklaşmak mümkündür. Gödel' in Tanrılık Teoremine göre bu iki yaklaşım mantıksal olarak denktir. Sembollerle kurallara uygun yazılan bir deyime formül denir. Bir formül açık ya da kapalı olabilir, içerdiği serbest değişkenlere atanan değerlere göre bir açık formül doğru ya da yanlış olabilir, özel formüllerden( aksiyomlardan ) oluşan türetime kapalı bir kümeye teori adı verilir. Bir teorinin tam, saptanabilir olması türünden kavramlar tezin birinci bölümünde açıklanmıştır. Bir teorinin saptanabilir olması için onun aksiyomatize edilebilir ve tam olması gereklidir. Böyle bir özelliğin gösterilebilmesi için teorinin dilinde yazılmış herhangi bir önermenin bu teoriye ait olup olmadığını belirleyen bir etkin yöntemin ( algoritmanın ) bulunması zorunludur. Algoritmik yaklaşım Matematik Lojikin uygulamalı alanına girmektedir. Bu yüzden saptanabilirliğin bir dolaysız kanıtı, niceleyicilerin elenmesi adı verilen bir yöntemle yapılmaktadır. 1920 li yıllara kadar uzanan bu yöntemin ana düşüncesi çok basittir. İkinci Bölümde bu yöntem açıklanmış, izomorfîzma ve alt izomorfîzma koşullarını gerçekleyen her teoriye uygulanabildiği kanıtlanmıştır. Genelde matematikte, özelde cisimler teorisinde oluğu gibi Matematik Lojikte de yapıların sürekli genişletilmeleri söz konusudur, verilen bir yapı niceleyicilerin elenmesini hemen kabul etmeyebilir. Bu nedenle yapının dili uygun parametrelerle genişletilir. Böyle bir geleneği Presburger ve Skolem Toplama Teorisi için geliştirmişlerdir. Tezin üçüncü bölümünde bu iki matematikçinin izledikleri farklı yollar teoremler altında verilmiş ve kanıtlanmıştır. Aynı bölümde Cegielskrnin Çarpım Teorisi için verdiği eleme yöntemine kısaca değinilmiştir. Aritmetikte çarpma özel bir toplama işlemi olduğundan, Çarpım Teorisinin saptanabilir bir teori olması Toplama Teorisinin saptanabilirliğinden elde edilmiştir. Bir yöntemin etkinliği uygulamada kazandırdığı çabuklukla da ölçülür. Tezin bu son bölümünde iki örnekle, yöntemimizin algoritmik yaklaşıma oranla daha pratik olduğunu gösterdik. Ok örnek sayılar teorisinin alt teorisi Th( w, S, 0 ) ile ikincisi ise ilk ve son elemanlı yoğun sıralı yapılarla ilgilidir. 35
It is possible to approach to Mathematical Logic by syntactical and semantical ways. In view of Gödel's Completeness Theorem, these two ways are equivalent. An expression written according to logical rules is called a formula. A formula can be open or closed; after assignment of values to free-variables contained in a formula, the latter becomes true or false. A set consisting of special formulae( axioms ) and closed under deduction is called a theory. Notions such as complete theory, decidable theory etc. are given in the first chapter of the thesis. For a theory to be decidable it is necessary that it be axiomatizable and complete. In order to show this property one must find an effective procedure ( algorithm ) which determines whether or not a given sentence written in the same language belongs to the theory. Algorithmic approach falls in the field of Applied Logic. That is why a short and direct proof of decidability is carried out by a procedure called " elimination of quantifiers ". The idea of this method which goes back to 1920 is very simple. In this second chapter of the thesis, the elimination procedure is explained and it is proved that it applies to all theories satisfying the isomorphism and subisomorphism conditions. As in mathematics in general and in theory of fields in particular, structures in Mathematical Logic are often subject to extension, for a given structure may not permit elimination procedure. Because of this fact the language of given structure is extented by adding adequate parameters. Such a tradition has been developed by Presburger and Skolem for the Addition Theory. These two different procedures considered by them are given in the form of theorems and are proved in the third chapter. In the same chapter we briefly recall Cegielski's elimination procedure for the Theory of Multiplication. As the multiplication is a particular addition operation in Arithmetic, the decidability of the Multiplication Theory is deducible from that of Addition Theory. Effectiveness of a procedure can be also measured by the fact that it permits a quick approach to the problem. In the last chapter of the thesis, we showed by 36means of two examples that our method is more practical than algorithmic approach. While the first example concerns the subtheory of Th( w, S, 0 ), the second one relates to the structures densry ordered with first and last elements. 37
It is possible to approach to Mathematical Logic by syntactical and semantical ways. In view of Gödel's Completeness Theorem, these two ways are equivalent. An expression written according to logical rules is called a formula. A formula can be open or closed; after assignment of values to free-variables contained in a formula, the latter becomes true or false. A set consisting of special formulae( axioms ) and closed under deduction is called a theory. Notions such as complete theory, decidable theory etc. are given in the first chapter of the thesis. For a theory to be decidable it is necessary that it be axiomatizable and complete. In order to show this property one must find an effective procedure ( algorithm ) which determines whether or not a given sentence written in the same language belongs to the theory. Algorithmic approach falls in the field of Applied Logic. That is why a short and direct proof of decidability is carried out by a procedure called " elimination of quantifiers ". The idea of this method which goes back to 1920 is very simple. In this second chapter of the thesis, the elimination procedure is explained and it is proved that it applies to all theories satisfying the isomorphism and subisomorphism conditions. As in mathematics in general and in theory of fields in particular, structures in Mathematical Logic are often subject to extension, for a given structure may not permit elimination procedure. Because of this fact the language of given structure is extented by adding adequate parameters. Such a tradition has been developed by Presburger and Skolem for the Addition Theory. These two different procedures considered by them are given in the form of theorems and are proved in the third chapter. In the same chapter we briefly recall Cegielski's elimination procedure for the Theory of Multiplication. As the multiplication is a particular addition operation in Arithmetic, the decidability of the Multiplication Theory is deducible from that of Addition Theory. Effectiveness of a procedure can be also measured by the fact that it permits a quick approach to the problem. In the last chapter of the thesis, we showed by 36means of two examples that our method is more practical than algorithmic approach. While the first example concerns the subtheory of Th( w, S, 0 ), the second one relates to the structures densry ordered with first and last elements. 37
Açıklama
Bu tezin, veri tabanı üzerinden yayınlanma izni bulunmamaktadır. Yayınlanma izni olmayan tezlerin basılı kopyalarına Üniversite kütüphaneniz aracılığıyla (TÜBESS üzerinden) erişebilirsiniz.
Anahtar Kelimeler
Matematik, Mathematics, Niceleyici, Quantizer
