Gödel's incompleteness properties and the guarded fragment: An algebraic approach
Gödel'in eksiklik özellikleri ve korumalı parça: Cebirsel bir yaklaşım
- Tez No: 847125
- Danışmanlar: PROF. ISTVÁN NÉMETI
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2016
- Dil: İngilizce
- Üniversite: Central European Unıversıty
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
H. Andreka, J. van Benthem ve I. Nemeti tarafından [AvBN98]'de tanıtılan korumalı parça (GF), iyi özellikleri nedeniyle bilgisayar bilimi, dilbilim ve diğerleri arasında geniş bir uygulama alanına sahip olan birinci derece mantığın karar verilebilir büyük bir parçasıdır. Mantıksal özellikleri birçok mantıkçı tarafından araştırılmıştır. GF, karar verilebilir olarak birinci dereceden mantığa göre ifade gücünden vazgeçer. Bir mantığın ifade gücünün bir ölçüsü, Godel'in Eksiklik Özelliğidir (Godel's Incompleteness Property - GIP). Eğer bu mantıkta, söz konusu mantığın özyinelemeli (sonlu olarak) belitselleştirilen bütün bir teoriye genişletilemeyen tatmin edici bir formül varsa, bir mantığın GIP'e (sırasıyla wGIP) sahip olduğu söylenir. Korunan parça için GIP başarısızdır, ancak GIP'in sonsuz dillerde GF için geçerli olurken, sonlu diller için wGIP'in de geçerli olmadığını kanıtlıyoruz. Öte yandan, GF'nin sözde solo korumalı parçasının sonlu dillerde de wGIP'e sahip olduğunu kanıtlıyoruz. Yukarıdakileri kanıtlamak için cebirsel yöntemler kullanıyoruz. Yani, [Nem86]'dan bir mantığın yalnızca ve ancak Lindenbaum-Tarski formül cebirleri atomik değilse wGIP'ye sahip olduğu teorisini kullanırız. GF durumunda ikincisi, yani Lindenbaum-Tarski formül cebirleri serbest silindirik göreli küme cebirleri ile yakından ilişkilidir. İlk olarak 1985 yılında sorulan ve daha sonra [Nem86], [AMN91] ve [AFN13] 'te yayınlanan uzun süredir çözülememiş bir açık problemi, serbest silindirik göreceli küme cebirlerinin çoğunun atomik olmadığını kanıtlayarak çözüyoruz. Aynı zamanda, bu serbest cebirlerin yapısal tanımlarını atomlar açısından da yapıyoruz.
Özet (Çeviri)
The guarded fragment (GF), introduced by H. Andr´eka, J. van Benthem and I. Nemeti in [AvBN98], is a large decidable fragment of first order logic that has a wide range of applications in computer science, linguistics, among others, because of its good properties. Its logical properties were investigated by many logicians. By being decidable, GF gives up some expres- sive power relative to first order logic. A measure of expressive power of a logic is Godel's Incompleteness Property (GIP). A logic is said to have GIP (wGIP, respectively) if there is a satisfiable formula in this logic which cannot be extended to a recursively (finitely, respectively) axiomatized complete theory of the logic in question. GIP fails for the guarded fragment, but we prove that wGIP holds for GF on infinite languages while for finite languages wGIP does not hold, either. On the other hand, we prove that the so-called solo-guarded fragment of GF has wGIP on finite languages, too. To prove the above, we use algebraic methods. Namely, we use the theorem from [Nem86] that a logic has wGIP if and only if its Lindenbaum-Tarski formula algebras are not atomic. The latter in the case of GF are closely related to the free cylindric relativized set algebras. We solve a long-standing open problem first asked in 1985 and then published in [Nem86], [AMN91] and [AFN13] by proving that most of the free cylindric relativized set algebras are non-atomic. We also give structural descriptions of these free algebras from the point of view of atoms.
Benzer Tezler
- Gödel makinelerinde öğrenme sorunu
Learning problem in Gödel machines
ABDULLAH HANZALE KORKMAZ
Yüksek Lisans
Türkçe
2024
İstanbul ÜniversitesiSistematik Felsefe ve Mantık Ana Bilim Dalı
Yükleniyor...
- An Introduction to the ontological foundations of Gödel`s incompleteness theorems
Başlık çevirisi yok
AHMET AYHAN ÇİTİL
- On the role of diagonalization in Gödel's incompleteness and Tarski's theorems
Gödel ve Tarski teoremlerinde köşegenleştirmenin rolü üzerine
MEHMET BUDAK
- Gödel'in aksiyomatik sistemlerin tam olmamasına dair teoremi ve paradokslar
Godel's axiomatic system's incompleteness theorem and paradoxes
TUFAN TAŞKESEN
