Sonlu model teorisi - Finite model theory

Sonlu model teorisi (FMT) bir alt alanıdır model teorisi (MT). MT, şubesi matematiksel mantık biçimsel bir dil (sözdizimi) ve yorumları (anlambilim) arasındaki ilişkiyi ele alır. FMT, MT'nin bir kısıtlamasıdır yorumlar sonlu yapılar, sonlu bir evrene sahip olan.

• MT'nin birçok merkezi teoremi sonlu yapılarla sınırlandırıldığında geçerli olmadığından, FMT ispat yöntemlerinde MT'den oldukça farklıdır. FMT altında sonlu yapılar için başarısız olan klasik model teorisinin merkezi sonuçları şunları içerir: kompaktlık teoremi, Gödel'in tamlık teoremi ve yöntemi ultraproducts için birinci dereceden mantık (FO).
• MT yakından ilişkili olduğu için matematiksel cebir FMT "alışılmadık derecede etkili" oldu^[1] bilgisayar biliminde alet. Başka bir deyişle: "Matematiksel mantık tarihinde en çok ilgi sonsuz yapılar üzerinde yoğunlaşmıştır ... Yine de, bilgisayarların sahip olduğu ve tuttuğu nesneler her zaman sonludur. Hesaplamayı incelemek için sonlu yapılar teorisine ihtiyacımız var."^[2] Dolayısıyla, FMT'nin ana uygulama alanları şunlardır: tanımlayıcı karmaşıklık teorisi, veritabanı teorisi ve resmi dil teorisi.
• FMT, temelde yapıların ayrımcılığı ile ilgilidir. Genel motive edici soru, belirli bir yapı sınıfının tanımlanıp tanımlanamayacağıdır ( izomorfizm ) belirli bir dilde. Örneğin, tüm döngüsel grafikler birinci dereceden bir cümle ile (döngüsel olmayanlardan) ayırt edilebilir mi? grafiklerin mantığı ? Bu aynı zamanda şu şekilde de ifade edilebilir: "döngüsel" FO özelliği ifade edilebilir mi?

Temel zorluklar

Tek bir sonlu yapı her zaman birinci dereceden mantıkta aksiyomatize edilebilir, burada aksiyomatlı bir dilde L tek bir izomorfizmaya kadar benzersiz bir şekilde tanımlanan anlamına gelir Lcümle. Benzer şekilde, sonlu yapıların herhangi bir sonlu koleksiyonu her zaman birinci dereceden mantıkta aksiyomatize edilebilir. Hepsi olmasa da bazıları, sonlu yapıların sonsuz koleksiyonları, tek bir birinci dereceden cümle ile aksiyomatize edilebilir.

Tek bir yapının karakterizasyonu

Bir dil L tek bir sonlu yapıyı aksiyomatize edecek kadar ifade edici S?

Ortak özelliklere sahip tek grafikler (1) ve (1 ').

Sorun

Şekildeki (1) gibi bir yapı, grafiklerin mantığı sevmek

1. Her düğümün başka bir düğüme bir kenarı vardır: ${ displaystyle forall _ {x} var _ {y} G (x, y).}$
2. Hiçbir düğümün kendisi için bir kenarı yoktur: ${ displaystyle forall _ {x, y} (G (x, y) Sağa x neq y).}$
3. Diğerlerine bağlı en az bir düğüm vardır: ${ displaystyle var _ {x} forall _ {y} (x neq y Rightarrow G (x, y)).}$

Bununla birlikte, bu özellikler yapıyı aksiyomatize etmez, çünkü yapı (1 ') için yukarıdaki özellikler de geçerlidir, ancak yapılar (1) ve (1') izomorfik değildir.

Gayri resmi olarak soru, yeterli özellik ekleyerek, bu özelliklerin birlikte tam olarak (1) tanımlayıp tanımlamadığı ve başka hiçbir yapı için (izomorfizme kadar) geçerli olup olmadığıdır (hep birlikte).

Yaklaşmak

Tek bir sonlu yapı için, yapıyı tek bir FO cümlesiyle tam olarak tanımlamak her zaman mümkündür. İlke burada tek ikili ilişkiye sahip bir yapı için gösterilmektedir. ${ displaystyle R}$ ve sabitler olmadan:

1. en azından olduğunu söyle ${ displaystyle n}$ elementler: ${ displaystyle varphi _ {1} = bigwedge _ {i neq j} neg (x_ {i} = x_ {j})}$
2. en fazla olduğunu söyle ${ displaystyle n}$ elementler: ${ displaystyle varphi _ {2} = forall _ {y} bigvee _ {i} (x_ {i} = y)}$
3. ilişkinin her unsurunu belirtin ${ displaystyle R}$: ${ displaystyle varphi _ {3} = bigwedge _ {(a_ {i}, a_ {j}) içinde R} R (x_ {i}, x_ {j})}$
4. ilişkinin tüm unsurlarını belirtin ${ displaystyle R}$: ${ displaystyle varphi _ {4} = bigwedge _ {(a_ {i}, a_ {j}) notin R} neg R (x_ {i}, x_ {j})}$

hepsi aynı demet için ${ displaystyle x_ {1} .. x_ {n}}$FO cümlesini veren ${ displaystyle var _ {x_ {1}} noktalar var _ {x_ {n}} ( varphi _ {1} land varphi _ {2} land varphi _ {3} land varphi _ {4})}$.

Sabit sayıda yapıya genişletme

Birinci dereceden bir cümle aracılığıyla tek bir yapıyı açıklama yöntemi, herhangi bir sabit sayıdaki yapı için kolayca genişletilebilir. Her yapı için açıklamaların ayrılmasıyla benzersiz bir açıklama elde edilebilir. Örneğin iki yapı için ${ displaystyle A}$ ve ${ displaystyle B}$ cümleleri tanımlayarak ${ displaystyle varphi _ {A}}$ ve ${ displaystyle varphi _ {B}}$ bu olabilir

${ displaystyle varphi _ {A} lor varphi _ {B}.}$

Sonsuz bir yapıya uzatma

Tanım olarak, sonsuz bir yapı içeren bir küme, FMT'nin ilgilendiği alanın dışında kalmaktadır. Sonsuz yapıların FO'da asla ayırt edilemeyeceğine dikkat edin, çünkü Löwenheim-Skolem teoremi Bu, sonsuz modelli hiçbir birinci dereceden teorinin izomorfizme kadar benzersiz bir modele sahip olamayacağı anlamına gelir.

En ünlü örnek muhtemelen Skolem teoremi, sayılabilir standart olmayan bir aritmetik modeli vardır.

Bir yapı sınıfının karakterizasyonu

Bir dil L Belirli özelliklere sahip sonlu yapıları tam olarak (izomorfizme kadar) tanımlayacak kadar anlamlı P?

Kadar set n yapılar.

Sorun

Şimdiye kadar verilen açıklamaların tümü, evrenin elementlerinin sayısını belirtir. Ne yazık ki en ilginç yapı grupları, ağaç olan, bağlantılı veya çevrimsiz olan tüm grafikler gibi belirli bir boyutla sınırlı değildir. Bu nedenle, sınırlı sayıda yapıyı ayırt etmek özel bir önem taşır.

Yaklaşmak

Aşağıda, genel bir ifade yerine, ayırt edilebilen ve edilemeyen yapılar arasında ayrım yapmak için bir metodoloji taslağı verilmiştir.

1. Ana fikir, ne zaman bir mülk olup olmadığını görmek istendiğinde P FO olarak ifade edilebilir, yapıları seçer Bir ve B, nerede Bir var mı P ve B değil. Eğer için Bir ve B aynı FO cümleleri geçerli, o zaman P FO ile ifade edilemez. Kısacası:

${ displaystyle A P’de, B P’de değil}$ ve ${ displaystyle A eşdeğeri B,}$

nerede ${ displaystyle A eşdeğeri B}$ kısaltmasıdır ${ displaystyle A modelleri alpha Leftrightarrow B modelleri alpha}$ tüm FO cümleleri için α, ve P özelliği olan yapıların sınıfını temsil eder P.

2. Metodoloji, birliği dilin kendisini oluşturan dilin birçok alt kümesini dikkate alır. Örneğin, FO için FO [m] her biri için m. Her biri için m yukarıdaki ana fikir daha sonra gösterilmelidir. Yani:

${ displaystyle A P’de, B P’de değil}$ ve ${ displaystyle A eşdeğeri _ {m} B}$

bir çift ile ${ displaystyle A, B}$ her biri için ${ displaystyle m}$ ve α (≡ cinsinden) FO'dan [m]. FO sınıflarını seçmek uygun olabilir [m] dilin bir bölümünü oluşturmak için.

3. FO'yı tanımlamanın yaygın bir yolu [m] vasıtasıyla nicelik belirteci sıralaması α FO formülünün qr (α) 'nın derinliğini ifade eder. nicelik belirteci yuvalama. Örneğin, içindeki bir formül için prenex normal formu qr, basitçe niceleyicilerin toplam sayısıdır. Sonra FO [m], qr (α) ≤ ile tüm FO formülleri α olarak tanımlanabilir m (veya bir bölüm istenirse, niceleyici sıralaması şuna eşit olan FO formülleri m).

4. Böylece her şey gösteriliyor ${ displaystyle A modelleri alpha Leftrightarrow B modelleri alpha}$ FO alt kümelerinde [m]. Buradaki ana yaklaşım, aşağıdaki cebirsel karakterizasyonu kullanmaktır. Ehrenfeucht – Fraïssé oyunları. Gayri resmi olarak, bunlar üzerinde tek bir kısmi izomorfizm alır Bir ve B ve uzat m kanıtlamak ya da çürütmek için ${ displaystyle A eşdeğeri _ {m} B}$, oyunu kimin kazandığına bağlı.

Misal

Özelliğin sıralı bir yapının boyutunun olduğunu göstermek istiyoruz. Bir = (A, ≤) çifttir, FO olarak ifade edilemez.

1. Fikir seçmek Bir ∈ EVEN ve B ∉ EVEN, eşit büyüklükteki tüm yapıların sınıfı olduğunda EVEN.

2. İki sıralı yapı ile başlıyoruz Bir₂ ve B₂ A evrenleriyle₂ = {1, 2, 3, 4} ve B₂ = {1, 2, 3}. Açıkça Bir₂ ∈ EVEN ve B₂ ∉ EŞİT.

3. İçin m = 2, şimdi * bunu 2 hamlede gösterebiliriz Ehrenfeucht – Fraïssé oyunu açık Bir₂ ve B₂ çoğaltan her zaman kazanır ve böylece Bir₂ ve B₂ FO [2] 'de ayrım yapılamaz, yani Bir₂ ${ displaystyle modelleri}$ α ⇔ B₂ ${ displaystyle modelleri}$ Her α ∈ FO [2] için α.

4. Daha sonra yapıları artırarak ölçeklendirmeliyiz m. Örneğin, m = 3 bulmalıyız Bir₃ ve B₃ böylece çoğaltıcı her zaman 3 hamle oyunu kazanır. Bu, A ile başarılabilir₃ = {1, ..., 8} ve B₃ = {1, ..., 7}. Daha genel olarak, A'yı seçebiliriz_m = {1, ..., 2^m} ve B_m = {1, ..., 2^m-1}; herhangi m çoğaltan her zaman kazanır m-bu yapı çifti için hareket oyunu *.

5. Bu nedenle, sonlu sıralı yapılar üzerinde EVEN FO ile ifade edilemez.

(*) Sonucun kanıtının Ehrenfeucht – Fraïssé oyunu burada ana odak noktası olmadığı için ihmal edilmiştir.

Başvurular

Veritabanı teorisi

Önemli bir parçası SQL (yani etkili olan ilişkisel cebir ) birinci dereceden mantığa dayanır (daha kesin olarak tercüme edilebilir alan ilişkisel hesabı vasıtasıyla Codd teoremi ), aşağıdaki örnekte gösterildiği gibi: "FIRST_NAME" ve "LAST_NAME" sütunlarına sahip bir "GIRLS" veritabanı tablosu düşünün. Bu, FIRST_NAME X LAST_NAME üzerindeki G (f, l) gibi bir ikili ilişkiye karşılık gelir. FO sorgusu {l: G ('Judy', l)}İlk adın 'Judy' olduğu tüm soyadları döndüren, SQL'de şu şekilde görünür:

GIRLSwhere FIRST_NAME = 'Judy' arasından LAST_NAME seçin

Dikkat edin, burada tüm soyadların yalnızca bir kez göründüğünü varsayıyoruz (veya ilişkilerin ve yanıtların çanta değil setler olduğunu varsaydığımız için SELECT DISTINCT kullanmalıyız).

Sonra daha karmaşık bir açıklama yapmak istiyoruz. Bu nedenle, "GIRLS" tablosuna ek olarak "FIRST_NAME" ve "LAST_NAME" sütunlarıyla birlikte "BOYS" tablosuna da sahibiz. Şimdi en az bir erkekle aynı soyadına sahip tüm kızların soyadlarını sorgulamak istiyoruz. FO sorgusu {(f, l): ∃h (G (f, l) ∧ B (h, l))}ve karşılık gelen SQL ifadesi:

GIRLSwhere LAST_NAME IN'den FIRST_NAME, LAST_NAME'i seçin (BOYS'den LAST_NAME'i seçin);

"∧" harfini ifade etmek için yeni dil öğesi "IN" yi sonraki bir select ifadesiyle birlikte sunduğumuza dikkat edin. Bu, öğrenmesi ve uygulaması zorluğunun yüksek olması karşılığında dili daha anlamlı kılar. Bu, resmi dil tasarımında yaygın bir değiş tokuş. Yukarıda gösterilen yol ("IN"), dili genişleten tek yol değildir. Alternatif bir yol, örn. "JOIN" operatörü tanıtmak için, yani:

GIRLS g'den farklı g.FIRST_NAME, g.LAST_NAME seçin g, BOYS, g.LAST_NAME = b.LAST_NAME;

Birinci dereceden mantık, örneğin ifade edilememesi nedeniyle bazı veritabanı uygulamaları için çok kısıtlayıcıdır. Geçişli kapatma. Bu, veritabanı sorgu dillerine daha güçlü yapıların eklenmesine yol açtı. İLE özyinelemeli içinde SQL: 1999. Daha etkileyici mantık sabit nokta mantığı Bu nedenle, veritabanı teorisi ve uygulamaları ile olan ilgisi nedeniyle sonlu model teorisinde çalışılmıştır.

Sorgulama ve arama

Anlatı verileri tanımlanmış ilişkiler içermez. Böylece, metin arama sorgularının mantıksal yapısı şu şekilde ifade edilebilir: önerme mantığı, gibi:

("Java" VE "ada" DEĞİL) VEYA ("C #" VE "müzik" DEĞİL)

Tam metin aramadaki zorlukların, sonuçların sıralaması gibi veritabanı sorgulamasından farklı olduğunu unutmayın.

Tarih

• Trakhtenbrot 1950: birinci dereceden mantıkta tamlık teoreminin başarısızlığı
• Scholz 1952: birinci dereceden mantıkta spektrumların karakterizasyonu
• Fagin 1974: varoluşsal ikinci dereceden mantıkta ifade edilebilen tüm özellikler kümesi, tam olarak karmaşıklık sınıfı NP'dir
• Chandra, Harel 1979/80: geçişli kapanışı ifade edebilen veritabanı sorgu dilleri için sabit noktalı birinci dereceden mantık uzantısı -> FMT'nin merkezi nesneleri olarak sorgular
• Immerman, Vardi 1982: sıralı yapılar üzerindeki sabit nokta mantığı, PTIME -> tanımlayıcı karmaşıklığı (Immerman-Szelepcsényi teoremi )
• Ebbinghaus, Flum 1995: ilk kapsamlı kitap "Sonlu Model Teorisi"
• Abiteboul, Hull, Vianu 1995: "Veritabanlarının Temelleri" kitabı
• Immerman 1999: kitap "Tanımlayıcı Karmaşıklık "
• Kuper, Libkin, Paredaens 2000: "Kısıtlama Veritabanları" kitabı
• Darmstadt 2005 / Aachen 2006: "Algoritmik Model Teorisi" üzerine ilk uluslararası çalıştaylar

Alıntılar

Referanslar

• Ebbinghaus, Heinz-Dieter; Flum, Jörg (1995). Sonlu Model Teorisi. Springer. ISBN  978-3-540-60149-4.

• Libkin, Leonid (2004). Sonlu Model Teorisinin Elemanları. Springer. ISBN  3-540-21202-7.

• Abiteboul, Serge; Hull, Richard; Vianu Victor (1995). Veritabanlarının Temelleri. Addison-Wesley. ISBN  0-201-53771-0.

• Immerman, Neil (1999). Tanımlayıcı Karmaşıklık. New York: Springer. ISBN  0-387-98600-6.

daha fazla okuma

• Grädel, Erich; Kolaitis, Phokion G .; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Sonlu model teorisi ve uygulamaları. Teorik Bilgisayar Bilimleri Metinleri. Bir EATCS Serisi. Berlin: Springer-Verlag. ISBN  978-3-540-00428-8. Zbl  1133.03001.

Dış bağlantılar

• Libkin, Leonid (2009). "Bir veritabanı teorisyeninin sonlu model teorisi araç kutusu". PODS 2009: Veritabanı sistemlerinin İlkeleri üzerine yirmi sekizinci ACM SIGACT-SIGMOD sempozyumunun bildirileri. s. 65–76. doi:10.1145/1559795.1559807. Genel bir giriş ve genel bakış olarak da uygundur.
• Leonid Libkin. "Sonlu Model Teorisinin Öğeleri" nin giriş bölümü. Üç ana uygulama alanını motive eder: veritabanları, karmaşıklık ve resmi diller.
• Jouko Väänänen. Sonlu Model Teorisi Üzerine Kısa Bir Ders. Matematik Bölümü, Helsinki Üniversitesi. 1993-1994 arasındaki derslere dayanmaktadır.
• Anuj Dawar. Sonsuz ve Sonlu Model Teorisi, slaytlar, Cambridge Üniversitesi, 2002.
• "Algoritmik Model Teorisi". RWTH Aachen. Arşivlenen orijinal 17 Temmuz 2012'de. Alındı 7 Kasım 2013. Açık FMT sorunlarının bir listesini içerir.