Kripke semantiği - Kripke semantics

Kripke anlambilimi ( ilişkisel anlambilim veya çerçeve anlambilimi olarak da bilinir ve genellikle olası dünya anlambilimiyle karıştırılır ), 1950'lerin sonlarında ve 1960'ların başlarında Saul Kripke ve André Joyal tarafından oluşturulan klasik olmayan mantık sistemleri için biçimsel bir anlambilimdir . İlk önce modal mantık için tasarlandı ve daha sonra sezgisel mantığa ve diğer klasik olmayan sistemlere uyarlandı . Kripke semantiğinin gelişimi, klasik olmayan mantık teorisinde bir atılımdı, çünkü bu tür mantıkların model teorisi Kripke'den önce neredeyse yoktu (cebirsel anlambilim vardı, ancak 'kılık değiştirmiş sözdizimi' olarak kabul edildi).

Modal mantığın anlamı

Önermeler modal mantık dili oluşur sayılabilir sonsuz kümesinin ait önerme değişkenleri , gerçeği fonksiyonlu bir dizi önerme eklemlerinin (bu yazıda ve ) ve modal operatör ( "ille"). Kalıcı operatör ( "mümkün") 'dir (klasik) çift arasında ve tanımlanabilir şöyle gerekliliği açısından: ( "zorunlu değildir A" "muhtemelen bir" eşdeğer olarak tanımlanmıştır). ${\görüntüleme stili \ için }$${\görüntüleme stili \neg }$${\görüntüleme stili\Kutu }$${\ Displaystyle \ Elmas }$${\görüntüleme stili\Kutu }$${\displaystyle \Elmas A:=\neg \Box\neg A}$

Temel tanımlar

Bir Kripke çerçeve veya modal çerçeve bir çift , W, bir (boş) grubu olduğu ve R, a, ikili bir ilişki ile ilgili W . Unsurları W adı verilen düğümleri veya dünyalar ve R ' olarak bilinen erişilebilirlik ilişkisi . ${\displaystyle \langle W,R\rangle }$

Bir Kripke modeli bir üçlüdür , burada bir Kripke çerçevesidir ve W düğümleri ile mod formülleri arasındaki bir ilişkidir , öyle ki tüm w  ∈  W ve mod formülleri A ve B için : ${\ Displaystyle \ langle W,R,\Vdash \rangle }$${\displaystyle \langle W,R\rangle }$${\görüntüleme stili \Vdash }$

• ${\ Displaystyle w\Vdash \neg A}$ancak ve ancak ,${\görüntüleme stili w\nVdash A}$
• ${\ Displaystyle w\Vdash A\to B}$eğer ve sadece eğer veya ,${\görüntüleme stili w\nVdash A}$${\ Displaystyle w\Vdash B}$
• ${\ Displaystyle w\Vdash \Kutu A}$ancak ve ancak herkes için böyle .${\ Displaystyle u\Vdash A}$${\görüntüleme stili u}$${\ Displaystyle w\;R\;u}$

“ W A'yı tatmin eder ”, “ A , w'den memnundur ” veya “ w , A'yı zorlar ” şeklinde okuruz . İlişkiye tatmin ilişkisi , değerlendirme ya da zorlama ilişkisi denir . Memnuniyet ilişkisi, önermesel değişkenler üzerindeki değeri tarafından benzersiz bir şekilde belirlenir. ${\ Displaystyle w\Vdash A}$${\görüntüleme stili \Vdash }$

Bir formül A olduğu , geçerli olarak:

• bir model , eğer tüm w  ∈  W içinse ,${\ Displaystyle \ langle W,R,\Vdash \rangle }$${\ Displaystyle w\Vdash A}$
• bir çerçeve , olası tüm seçenekler için geçerliyse ,${\displaystyle \langle W,R\rangle }$${\ Displaystyle \ langle W,R,\Vdash \rangle }$${\görüntüleme stili \Vdash }$
• Bir sınıf C çerçeveleri veya modellerin, bu her üyesi de geçerli olup olmadığını C .

Thm( C ) 'yi C'de geçerli olan tüm formüllerin kümesi olarak tanımlarız . Tersine, X bir formüller kümesiyse, Mod( X ), X'ten gelen her formülü doğrulayan tüm çerçevelerin sınıfı olsun .

Kalıcı mantığı (formüller örneğin, bir dizi) L olan bir ses çerçevelerinin bir sınıfına göre Cı- , eğer L  ⊆ THM ( C ). L ise tam wrt Cı eğer L  ⊇ THM ( C ).

Yazışma ve eksiksizlik

Semantik, bir mantığı (yani bir türetme sistemini ) araştırmak için, yalnızca anlamsal sonuç ilişkisinin sözdizimsel karşılığı olan sözdizimsel sonuç ilişkisini ( türetilebilirlik ) yansıtıyorsa yararlıdır . Kripke çerçevelerinin bir sınıfına göre hangi modal mantığın sağlam ve eksiksiz olduğunu bilmek ve bunun hangi sınıf olduğunu belirlemek hayati önem taşır.

Kripke çerçevelerinin herhangi bir C sınıfı için , Thm( C ) bir normal modal mantıktır (özellikle, minimal normal modal mantığın teoremleri, K , her Kripke modelinde geçerlidir). Bununla birlikte, genel olarak bunun tersi geçerli değildir: incelenen mod sistemlerinin çoğu basit koşullarla tanımlanan çerçeve sınıflarının tam olmasına rağmen, Kripke eksik normal modal mantıkları mevcuttur. Böyle bir sistemin doğal bir örneği Japaridze'nin polimodal mantığıdır .

Normal bir modal lojik L karşılık kare bir sınıfına Cı , eğer C  = Mod ( L ). Başka bir deyişle, C , L' nin ses wrt C olduğu en büyük çerçeve sınıfıdır . O şöyle L onun karşılık gelen sınıfın tamamlandıktan ve ancak eğer Kripke tamamlandı.

T  : şemasını düşünün . T bir geçerlidir dönüşlü çerçeve : eğer , o zaman bu yana ağırlık R w . Öte yandan, T'yi doğrulayan bir çerçeve dönüşlü olmalıdır: w  ∈  W'yi sabitleyin ve bir önerme değişkeni p'nin tatminini aşağıdaki gibi tanımlayın: eğer ve sadece w R u ise . Daha sonra , bu şekilde tarafından T anlamına gelir, W R ağırlık tanımını kullanarak . T , dönüşlü Kripke çerçevelerinin sınıfına karşılık gelir. ${\ Displaystyle \ Kutu A\'dan A'ya}$${\displaystyle \langle W,R\rangle }$${\ Displaystyle w\Vdash \Kutu A}$${\ Displaystyle w\Vdash A}$  ${\displaystyle u\Vdash p}$  ${\ Displaystyle w\Vdash \Box p}$${\ Displaystyle w\Vdash p}$  ${\görüntüleme stili \Vdash }$

Karşılık gelen L sınıfını karakterize etmek , onun eksiksizliğini kanıtlamaktan genellikle çok daha kolaydır , bu nedenle yazışma, eksiksizlik kanıtları için bir kılavuz görevi görür. Yazışmalar da göstermek için kullanılan bir eksiklik kalıcı mantığın: varsayalım L ₁  ⊆  L ₂ aynı kare sınıfı, ancak uygun, normal mod mantık olan L ₁ her teoremi kanýtlamaz L ₂ . O halde L ₁ , Kripke eksiktir. Örneğin, şema , GL ile aynı çerçeve sınıfına (yani geçişli ve konvers sağlam temelli çerçeveler) karşılık geldiği için eksik bir mantık üretir , ancak GL- totolojisini kanıtlamaz . ${\displaystyle \Kutu (A\leftrightarrow \Kutu A)\to \Kutu A}$${\Displaystyle \Kutu A\'dan\Kutu A Kutusuna}$

Ortak mod aksiyom şemaları

Aşağıdaki tablo, ortak mod aksiyomlarını karşılık gelen sınıflarıyla birlikte listeler. Aksiyomların adlandırılması genellikle değişir.

İsim	aksiyom	çerçeve durumu
K	${\ Displaystyle \ Kutu (A\'dan B'ye)\to (\Kutu A\'dan \Kutu B'ye)}$	Yok
T	${\ Displaystyle \ Kutu A\'dan A'ya}$	dönüşlü :${\görüntüleme stili w\,R\,w}$
4	${\Displaystyle \Kutu A\'dan\Kutu A Kutusuna}$	geçişli :${\displaystyle w\,R\,v\wedge v\,R\,u\Rightarrow w\,R\,u}$
	${\ Displaystyle \ Kutu \ Kutu A\'dan \ Kutu A'ya}$	yoğun :${\displaystyle w\,R\,u\Rightarrow \vardır v\,(w\,R\,v\land v\,R\,u)}$
NS	${\ Displaystyle \ Kutu A\'dan Elmas A'ya}$ veya ${\ Displaystyle \ Elmas \ üst }$	seri :${\ Displaystyle \ forall w\,\vardır v\,(w\,R\,v)}$
B	${\ Displaystyle A\to \Box\Diamond A}$	simetrik  : ${\ Displaystyle w\,R\,v\Rightarrow v\,R\,w}$
5	${\displaystyle \Diamond A\to \Box\Diamond A}$	Öklid :${\displaystyle w\,R\,u\land w\,R\,v\Rightarrow u\,R\,v}$
GL	${\displaystyle \Kutu (\Kutu A\'dan A'ya)\Kutu A'ya}$	R geçişli, R -1 sağlam temelli
grz	${\displaystyle \Kutu (\Kutu (A\to \Kutu A)\to A)\to A}$	R dönüşlü ve geçişli, R -1 − Id sağlam temelli
H	${\Displaystyle \Kutu (\Kutu A\'dan B'ye)\lor \Kutu (\Kutu B\'den A'ya)}$	${\displaystyle w\,R\,u\land w\,R\,v\Rightarrow u\,R\,v\lor v\,R\,u}$
m	${\displaystyle \Kutu \Elmas A\to \Elmas\Kutu A}$	(karmaşık bir ikinci dereceden özellik)
G	${\displaystyle \Elmas \Kutu A\to \Kutu\Elmas A}$	yakınsak: ${\displaystyle w\,R\,u\land w\,R\,v\Rightarrow \var x\,(u\,R\,x\land v\,R\,x)}$
	${\ Displaystyle A\'dan A Kutusuna}$	ayrık: ${\ Displaystyle w\,R\,v\Rightarrow w=v}$
	${\ Displaystyle \ Elmas A\'dan A Kutusuna}$	kısmi fonksiyon : ${\displaystyle w\,R\,u\land w\,R\,v\Rightarrow u=v}$
	${\displaystyle \Elmas A\leftrightarrow \Kutu A}$	işlev: ${\displaystyle \forall w\,\vardır !u\,w\,R\,u}$
	${\görüntüleme stili \Kutu A}$ veya ${\ Displaystyle \ Kutu \ bot }$	boş: ${\displaystyle \forall w\,\forall u\,\neg (w\,R\,u)}$

Ortak mod sistemleri

Aşağıdaki tablo birkaç yaygın normal mod sistemini listeler. Bazı sistemler için çerçeve koşulları basitleştirilmiştir: tabloda verilen çerçeve sınıflarına göre mantıklar tamamlanmıştır , ancak bunlar daha büyük bir çerçeve sınıfına karşılık gelebilir .

İsim	aksiyomlar	çerçeve durumu
K	-	tüm çerçeveler
T	T	dönüşlü
K4	4	geçişli
S4	4	ön sipariş
S5	T, 5 veya D, B, 4	denklik bağıntısı
S4.3	T, 4, H	toplam ön sipariş
S4.1	T, 4, M	ön sipariş, ${\displaystyle \forall w\,\exist u\,(w\,R\,u\land \forall v\,(u\,R\,v\Rightarrow u=v))}$
S4.2	T, 4, G	yönlendirilmiş ön sipariş
GL , K4W	GL veya 4, GL	sonlu katı kısmi düzen
Grz, S4Grz	Grz veya T, 4, Grz	sonlu kısmi düzen
NS	NS	seri
D45	D, 4, 5	geçişli, seri ve Öklid

kanonik modeller

Herhangi bir normal modal mantık için, L , model olarak maksimal tutarlı kümelerin kullanılmasına ilişkin standart tekniğin uyarlanmasıyla, L'nin teorem olmayanlarını kesin olarak reddeden bir Kripke modeli ( kanonik model olarak adlandırılır ) oluşturulabilir . Kanonik Kripke modelleri , cebirsel anlambilimde Lindenbaum-Tarski cebir yapısına benzer bir rol oynar .

L ve Modus Ponens teoremleri kullanılarak herhangi bir çelişki elde edilemiyorsa , bir formül kümesi L - tutarlıdır . Bir maksimum L-tutarlı grubu (bir L - MCS kısaca) bir bir L herhangi bir uygun olan -Tutarlı grubu L -Tutarlı üst kümesini.

Kanonik modeli arasında L bir Kripke'nin modeli , W, tüm dizi L - MCS ve ilişkiler R ve aşağıdaki gibidir: ${\ Displaystyle \ langle W,R,\Vdash \rangle }$${\görüntüleme stili \Vdash }$

${\displaystyle X\;R\;Y}$eğer ve sadece her formül için , eğer öyleyse ,${\görüntüleme stili A}$${\displaystyle \Box A\in X}$${\görüntüleme stili A\Y'de}$

${\ Displaystyle X\Vdash A}$ancak ve ancak .${\displaystyle A\in X}$

Kanonik model, L' nin bir modelidir , çünkü her L - MCS , L'nin tüm teoremlerini içerir . Tarafından Zorn lemması , her bir L -Tutarlı grubu, bir içerdiği L - MCS , özellikle de kanıtlanamayan her formül, L standart model bir karşı örnek vardır.

Kanonik modellerin ana uygulaması, eksiksizlik kanıtlarıdır. K'nin kanonik modelinin özellikleri, hemen tüm Kripke çerçevelerinin sınıfına göre K'nin tamlığını ifade eder . Bu argüman yok değil keyfi için çalışmak L garantisi yoktur, çünkü o altta yatan çerçeve kanonik modeli tatmin çerçeve koşulları L .

Kripke çerçevelerinin bir P özelliğine göre bir formülün veya formüllerin X kümesinin kanonik olduğunu söylüyoruz , eğer

• X , P'yi sağlayan her çerçevede geçerlidir ,
• X içeren herhangi bir normal modal mantık L için , kanonik L modelinin temel çerçevesi P'yi karşılar .

Kurallı formül kümelerinin birleşimi kurallıdır. Önceki tartışmadan, kanonik bir formüller dizisi tarafından aksiyomlaştırılan herhangi bir mantığın Kripke tam ve kompakt olduğu sonucu çıkar .

T, 4, D, B, 5, H, G aksiyomları (ve dolayısıyla bunların herhangi bir kombinasyonu) kanoniktir. GL ve Grz kanonik değildir çünkü kompakt değildirler. M aksiyomu tek başına kurallı değildir (Goldblatt, 1991), ancak birleşik mantık S4.1 (aslında K4.1 bile) kurallıdır .

Genel olarak, verilen bir aksiyomun kanonik olup olmadığına karar verilemez . Yeterince güzel bir koşul biliyoruz: Henrik Sahlqvist geniş bir formül sınıfı tanımladı (şimdi Sahlqvist formülleri olarak adlandırılıyor ) öyle ki

• Sahlqvist formülü kurallıdır,
• Sahlqvist formülüne karşılık gelen çerçevelerin sınıfı birinci dereceden tanımlanabilir,
• belirli bir Sahlqvist formülüne karşılık gelen çerçeve koşulunu hesaplayan bir algoritma vardır.

Bu güçlü bir kriterdir: örneğin, yukarıda kanonik olarak listelenen tüm aksiyomlar Sahlqvist formülleridir (eşdeğerdir).

sonlu model özelliği

Bir mantık, bir sonlu çerçeve sınıfına göre tamamlanmışsa , sonlu model özelliğine (FMP) sahiptir. Bu kavramın bir uygulaması karar verilebilirlik sorusudur: Post'un teoreminden , belirli bir sonlu çerçevenin bir L modeli olup olmadığına karar verilebilir olması koşuluyla, FMP'ye sahip özyinelemeli olarak aksiyomatize edilmiş bir modal mantık L' nin karar verilebilir olduğu sonucu çıkar . Özellikle, FMP ile sonlu olarak aksiyomlaştırılabilen her mantık karar verilebilirdir.

Belirli bir mantık için FMP oluşturmak için çeşitli yöntemler vardır. Standart model yapısının iyileştirmeleri ve uzantıları, genellikle filtreleme veya çözme gibi araçlar kullanılarak çalışır . Diğer bir olasılık olarak, temel tamlık deliller kesme içermeyen SIRALI taşları , genellikle doğrudan sonlu modeller üretmek.

Pratikte kullanılan mod sistemlerinin çoğu (yukarıda listelenenlerin tümü dahil) FMP'ye sahiptir.

Bazı durumlarda, bir mantığın Kripke eksiksizliğini kanıtlamak için FMP'yi kullanabiliriz: her normal modal mantık, bir modal cebir sınıfına göre tamamlanır ve sonlu bir modal cebir, bir Kripke çerçevesine dönüştürülebilir. Örnek olarak, Robert Bull bu yöntemi kullanarak S4.3'ün her normal uzantısının FMP'ye sahip olduğunu ve Kripke'nin eksiksiz olduğunu kanıtladı .

çok modlu mantık

Kripke semantiği, birden fazla modaliteye sahip mantıklar için basit bir genellemeye sahiptir. Bir dil için bir Kripke çerçeve gerekliliği operatörlerinin grubu boş olmayan bir dizi oluşur olarak B ikili ilişkileri ile donatılmış R _i her biri için i  ∈  I . Memnuniyet ilişkisinin tanımı şu şekilde değiştirilir: ${\displaystyle \{\Box _{i}\mid \,i\ben\}}$

${\ Displaystyle w\Vdash \Box _ {i}A}$ ancak ve ancak ${\displaystyle \forall u\,(w\;R_{i}\;u\Rightarrow u\Vdash A).}$

Tim Carlson tarafından keşfedilen basitleştirilmiş bir semantik, genellikle polimodal kanıtlanabilirlik mantığı için kullanılır . Bir Carlson modeli , tek bir erişilebilirlik ilişkisi R olan ve her modalite için D _i  ⊆  W alt kümeleri olan bir yapıdır . Memnuniyet şu şekilde tanımlanır: ${\displaystyle \langle W,R,\{D_{i}\}_{i\in I},\Vdash \rangle }$

${\ Displaystyle w\Vdash \Box _ {i}A}$ ancak ve ancak ${\displaystyle \forall u\in D_{i}\,(w\;R\;u\Rightarrow u\Vdash A).}$

Carlson modellerini görselleştirmek ve kullanmak normal polimodal Kripke modellerinden daha kolaydır; bununla birlikte, Carlson'ın eksik olduğu Kripke tam polimodal mantıklar vardır.

Sezgisel mantığın anlamı

Sezgisel mantık için Kripke semantiği , modal mantığın semantiğiyle aynı ilkeleri takip eder, ancak farklı bir tatmin tanımı kullanır.

Bir sezgisel Kripke'nin modeli üçlü olup burada, a, önceden sipariş Kripke çerçeve ve biri aşağıdaki koşulları: ${\displaystyle \langle W,\leq ,\Vdash \rangle }$${\displaystyle \langle W,\leq \rangle }$${\görüntüleme stili \Vdash }$

• Eğer p bir önerme değişkendir, ve daha sonra ( kalıcılığı durumu (bakınız monotonicity )),${\ Displaystyle w\leq u}$${\ Displaystyle w\Vdash p}$${\displaystyle u\Vdash p}$
• ${\ Displaystyle w\Vdash A\land B}$eğer ve sadece eğer ve ,${\ Displaystyle w\Vdash A}$${\ Displaystyle w\Vdash B}$
• ${\ Displaystyle w\Vdash A\lor B}$eğer ve sadece eğer veya ,${\ Displaystyle w\Vdash A}$${\ Displaystyle w\Vdash B}$
• ${\ Displaystyle w\Vdash A\to B}$eğer ve sadece herkes için , ima ederse ,${\görüntüleme stili u\geq w}$${\ Displaystyle u\Vdash A}$${\ Displaystyle u\Vdash B}$
• değil .${\ Displaystyle w\Vdash \bot }$

A , ¬ A ' nın olumsuzlaması, A → ⊥ için bir kısaltma olarak tanımlanabilir . Eğer tüm u öyle ki w ≤ u değil, u ⊩ A , ardından w ⊩ A → ⊥ olduğunu vacuously doğrudur , yani w ⊩ ¬ A .

Sezgisel mantık, Kripke semantiğine göre sağlam ve eksiksizdir ve sonlu model özelliğine sahiptir .

Sezgisel birinci dereceden mantık

Let L bir olmak birinci dereceden dili. L' nin bir Kripke modeli bir üçlüdür , burada sezgisel bir Kripke çerçevesidir, M _w her w  ∈  W düğümü için bir (klasik) L yapısıdır ve u  ≤  v olduğunda aşağıdaki uyumluluk koşulları geçerlidir : ${\displaystyle \langle W,\leq ,\{M_{w}\}_{w\in W}\rangle}$${\displaystyle \langle W,\leq \rangle }$

• etki alanı M _u etki dahildir M _v ,
• İşlev sembollerin gerçekleşmeleri M _u ve M _v unsurları üzerinde anlaşmaya M _u ,
• her biri için , n -ary yüklem P ve elemanların bir ₁ , ..., bir _n  ∈  E _u : Eğer p ( bir ₁ , ..., bir _n ) tutan M _u , o zaman içinde tutar M _v .

Bir değerlendirme de e elemanları tarafından değişken M _w , biz tatmin ilişkiyi tanımlar : ${\displaystyle w\Vdash A[e]}$

• ${\displaystyle w\Vdash P(t_{1},\dots ,t_{n})[e]}$eğer ve sadece M _w içinde tutarsa ,${\displaystyle P(t_{1}[e],\dots ,t_{n}[e])}$
• ${\displaystyle w\Vdash (A\land B)[e]}$eğer ve sadece eğer ve ,${\displaystyle w\Vdash A[e]}$${\displaystyle w\Vdash B[e]}$
• ${\displaystyle w\Vdash (A\lor B)[e]}$eğer ve sadece eğer veya ,${\displaystyle w\Vdash A[e]}$${\displaystyle w\Vdash B[e]}$
• ${\displaystyle w\Vdash (A\to B)[e]}$eğer ve sadece herkes için , ima ederse ,${\görüntüleme stili u\geq w}$${\displaystyle u\Vdash A[e]}$${\displaystyle u\Vdash B[e]}$
• değil ,${\displaystyle w\Vdash \bot [e]}$
• ${\displaystyle w\Vdash (\vardır x\,A)[e]}$ancak ve ancak öyle bir şey varsa ,${\displaystyle a\in M_{w}}$${\displaystyle w\Vdash A[e(x\to a)]}$
• ${\displaystyle w\Vdash (\forall x\,A)[e]}$eğer ve sadece her ve her için , .${\görüntüleme stili u\geq w}$${\displaystyle a\in M_{u}}$${\displaystyle u\Vdash A[e(x\to a)]}$

Burada e ( x → a ), x'e a değerini veren ve aksi takdirde e ile uyumlu olan değerlendirmedir .

İçinde biraz farklı bir formalizasyon görün.

Kripke-Joyal semantiği

Demet kuramının bağımsız gelişiminin bir parçası olarak, 1965'te Kripke anlambiliminin topos kuramında varoluşsal nicelemenin ele alınmasıyla yakından ilişkili olduğu anlaşıldı . Yani, bir demetin bölümleri için varoluşun 'yerel' yönü, bir tür 'mümkün' mantığıydı. Bu gelişme birkaç kişinin eseri olsa da, Kripke-Joyal semantiği adı bu bağlamda sıklıkla kullanılır.

Model yapıları

Klasik model teorisinde olduğu gibi, diğer modellerden yeni bir Kripke modeli oluşturmak için yöntemler vardır.

Kripke semantiğindeki doğal homomorfizmlere p-morfizmler denir (bu, sözde epimorfizm için kısadır , ancak ikinci terim nadiren kullanılır). Kripke çerçevelerinin bir p-morfizmi ve öyle bir eşlemedir ki ${\displaystyle \langle W,R\rangle }$${\displaystyle \langle W',R'\rangle }$${\displaystyle f\kolon W\to W'}$

• f erişilebilirlik ilişkisini korur, yani u R v , f ( u )  R'  f ( v ) anlamına gelir ,
• ne zaman f ( u )  R'  v ', bir v  ∈  W vardır, öyle ki u R v ve f ( v ) =  v '.

Kripke modelleri p-morfizmanın ve bunların altında yatan çerçevelerin bir p-morfizmanın olup , tatmin ${\ Displaystyle \ langle W,R,\Vdash \rangle }$${\displaystyle \langle W',R',\Vdash '\rangle }$${\displaystyle f\kolon W\to W'}$

${\ Displaystyle w\Vdash p}$ancak ve ancak , herhangi bir önerme değişkeni için p .${\displaystyle f(w)\Vdash 'p}$

P-morfizmleri, bisimülasyonların özel bir türüdür . Genel olarak, bir ele almıştır kare arasında ve bir ilişkidir B ⊆ G x W , hangi biri aşağıdaki ‘zik-zak’ özelliği: ${\displaystyle \langle W,R\rangle }$${\displaystyle \langle W',R'\rangle }$

• Eğer U u B ' ve U Vr mevcut olup, v'  ∈  W , öyle ki v B v ' ve u 'R', V' ,
• Eğer U u B ' ve u' R 'V' mevcut olup, v  ∈  W , öyle ki v B v' ve u R v .

Atom formüllerinin zorlamasını korumak için ek olarak modellerin bisimülasyonu gereklidir :

eğer w B w' ise , o zaman ve ancak , herhangi bir önerme değişkeni için p .${\ Displaystyle w\Vdash p}$${\ Displaystyle w'\Vdash 'p}$

Bu tanımdan çıkan anahtar özellik, modellerin bisimülasyonlarının (dolayısıyla p-morfizmleri) yalnızca önerme değişkenlerinin değil , tüm formüllerin memnuniyetini korumasıdır .

Biz bir Kripke modeli dönüştürebilir ağacın kullanarak bir çözülmeye . Bir model ve sabit bir w ₀  ∈  W düğümü verildiğinde, bir model tanımlarız , burada W' tüm sonlu dizilerin kümesidir, öyle ki tüm ben  <  n için w _i  R w _i+1 ve eğer ve sadece bir önerme için ise değişken p . Erişilebilirlik ilişkisinin R' tanımı değişir; en basit durumda koyduğumuz ${\ Displaystyle \ langle W,R,\Vdash \rangle }$${\displaystyle \langle W',R',\Vdash '\rangle }$${\displaystyle s=\langle w_{0},w_{1},\dots ,w_{n}\rangle }$${\displaystyle s\Vdash p}$${\displaystyle w_{n}\Vdash p}$

${\displaystyle \langle w_{0},w_{1},\dots ,w_{n}\rangle \;R'\;\langle w_{0},w_{1},\dots ,w_{n}, w_{n+1}\rangle }$,

ancak birçok uygulama bu ilişkinin dönüşlü ve/veya geçişli olarak kapatılmasına veya benzeri değişikliklere ihtiyaç duyar.

Filtrasyon , birçok mantık için FMP'yi kanıtlamak için kullanılan kullanışlı bir yapıdır . X , alt formüller altında kapalı bir formüller kümesi olsun . Bir X, bir modelin -filtration bir eşleme f den W bir model olduğu gibi ${\ Displaystyle \ langle W,R,\Vdash \rangle }$${\displaystyle \langle W',R',\Vdash '\rangle }$

• f bir tahmindir ,
• f erişilebilirlik ilişkisini ve (her iki yönde) değişkenlerin memnuniyetini korur p  ∈  X ,
• eğer f ( u )  R'  f ( v ) ve nerede , o zaman .${\ Displaystyle u\Vdash \Kutu A}$${\displaystyle \Box A\in X}$${\displaystyle v\Vdash A}$

Buradan f'nin , X'ten gelen tüm formüllerin memnuniyetini koruduğu sonucu çıkar . Tipik uygulamalarda, f'yi , W'nin ilişki üzerinden bölümü üzerine izdüşüm olarak alırız.

u ≡ _X  v ancak ve ancak tüm A  ∈  X için ise , ancak ve ancak .${\ Displaystyle u\Vdash A}$${\displaystyle v\Vdash A}$

Çözülme durumunda olduğu gibi, bölüm üzerindeki erişilebilirlik ilişkisinin tanımı değişir.

Genel çerçeve semantiği

Kripke semantiğinin ana kusuru, Kripke eksik mantıklarının ve eksiksiz ancak kompakt olmayan mantıkların varlığıdır. Kripke çerçevelerini, cebirsel anlambilimden gelen fikirleri kullanarak olası değerleme setini kısıtlayan ekstra bir yapı ile donatarak düzeltilebilir. Bu, genel çerçeve anlambilimine yol açar .

Bilgisayar bilimi uygulamaları

Blackburn ve ark. (2001) bir ilişkisel yapı basitçe bir küme ve bu küme üzerindeki bir ilişkiler topluluğu olduğu için, ilişkisel yapıların hemen her yerde bulunmasının şaşırtıcı olmadığına işaret etmektedir. Teorik bilgisayar biliminden bir örnek olarak , programın yürütülmesini modelleyen etiketli geçiş sistemleri verirler . Blackburn ve ark. bu nedenle, bu bağlantı nedeniyle kipsel dillerin "ilişkisel yapılar üzerinde içsel, yerel perspektif" sağlamada ideal olarak uygun olduğunu iddia eder. (s. xii)

Tarih ve terminoloji

Kripke'nin devrim niteliğindeki anlamsal buluşlarından önce gelen benzer bir çalışma:

• Rudolf Carnap , değerleme işlevine Leibnizci olası dünyalar arasında değişen bir parametre vererek, zorunluluk ve olasılık kipleri için olası bir dünya semantiğinin verilebileceği fikrine sahip olan ilk kişi gibi görünüyor . Bayart bu fikri daha da geliştirmiştir, ancak hiçbiri Tarski'nin ortaya koyduğu tarzda yinelemeli tatmin tanımları vermemiştir;
• JCC McKinsey ve Alfred Tarski, modal mantığı modellemek için modern araştırmalarda hala etkili olan bir yaklaşım, yani operatörlerle Boole cebirlerinin model olarak kullanıldığı cebirsel yaklaşım geliştirdi. Bjarni Jónsson ve Tarski, Boole cebirlerinin operatörlerle çerçeveler açısından temsil edilebilirliğini belirledi. İki fikir bir araya getirilseydi, sonuç tam olarak çerçeve modelleri, yani Kripke'den yıllar önce Kripke modelleri olurdu. Ancak o sırada hiç kimse (Tarski bile) bağlantıyı görmedi.
• Arthur Prior , CA Meredith'in yayınlanmamış çalışmasına dayanarak , cümlesel modal mantığın klasik yüklem mantığına bir çevirisini geliştirdi; bu, klasik yüklem mantığına bir çeviri geliştirmiş olsaydı, bunu klasik yüklem mantığı için olağan model teorisiyle birleştirmiş olsaydı, Kripke modellerine eşdeğer bir model teorisi üretebilirdi. önceki. Ancak yaklaşımı kesinlikle sözdizimsel ve kuramsal model karşıtıydı.
• Stig Kanger , kipsel mantığın yorumuna oldukça daha karmaşık bir yaklaşım getirdi , ancak bu, Kripke'nin yaklaşımının anahtar fikirlerinin çoğunu içeren bir yaklaşımdı. İlk önce erişilebilirlik ilişkileri üzerindeki koşullar ile modal mantık için Lewis tarzı aksiyomlar arasındaki ilişkiyi kaydetti . Ancak Kanger, sistemi için bir tamlık kanıtı veremedi;
• Jaakko Hintikka , makalelerinde Kripke'nin semantiğinin basit bir varyasyonu olan epistemik mantığı tanıtan bir anlambilim verdi; bu, değerlemelerin maksimum tutarlı kümeler aracılığıyla karakterizasyonuna eşdeğerdir. O, epistemik mantık için çıkarım kuralları vermez ve dolayısıyla bir tamlık kanıtı da veremez;
• Richard Montague , Kripke'nin çalışmasında yer alan anahtar fikirlerin birçoğuna sahipti, ancak bunları önemli olarak görmedi, çünkü eksiksizlik kanıtı yoktu ve bu nedenle Kripke'nin makaleleri mantık camiasında bir sansasyon yaratana kadar yayınlamadı;
• Evert Willem Beth , daha hantal bir tatmin tanımı kullanmak dışında, Kripke semantiğine çok benzeyen ağaçlara dayalı bir sezgisel mantık semantiği sundu.

Ayrıca bakınız

• Alexandrov topolojisi
• Normal mod mantığı
• iki boyutluluk
• Çamurlu Çocuk Yapbozu

Notlar

a ^ Andrzej Grzegorczyk'ten sonra .

Referanslar

• Blackburn, P.; de Rijke, M .; Venema, Yde (2002). Modal Mantık . Cambridge Üniversitesi Yayınları. ISBN'si 978-1-316-10195-7.
• Boğa, Robert A.; Segerberg, K. (2012) [1984]. "Temel Modal Mantık" . Gabbay'da, DM; Günthner, F. (ed.). Klasik Mantığın Uzantıları . Felsefi Mantık El Kitabı. 2 . Springer. s. 1-88. ISBN'si 978-94-009-6259-0.
• Chagrov, A.; Zakharyaschev, M. (1997). Modal Mantık . Clarendon Basın. ISBN'si 978-0-19-853779-3.
• Dummett, Michael AE (2000). Sezgiselliğin Unsurları (2. baskı). Clarendon Basın. ISBN'si 978-0-19-850524-2.
• Uydurma, Melvin (1969). Sezgisel Mantık, Model Teorisi ve Zorlama . Kuzey Hollanda. ISBN'si 978-0-444-53418-7.
• Goldblatt, Robert (2006). "Matematiksel Modal Mantık: Evrimine Bir Bakış" (PDF) . Gabbay'da Dov M.; Woods, John (ed.). Yirminci Yüzyılda Mantık ve Modaliteler (PDF) . Mantık Tarihi El Kitabı. 7 . Elsevier. s. 1-98. ISBN'si 978-0-08-046303-2.
• Cresswell, MJ; Hughes, GE (2012) [1996]. Modal Mantığa Yeni Bir Giriş . Routledge. ISBN'si 978-1-134-80028-5.
• Mac Lane, Saunders ; Moerdijk, Ieke (2012) [1991]. Geometri ve Mantıkta Kasnaklar: Topos Teorisine İlk Giriş . Springer. ISBN'si 978-1-4612-0927-0.
• van Dalen, Dirk (2013) [1986]. "Sezgisel Mantık" . Gabbay'da Dov M.; Günthner, Franz (ed.). Klasik Mantığa Alternatifler . Felsefi Mantık El Kitabı. 3 . Springer. s. 225–339. ISBN'si 978-94-009-5203-4.

Dış bağlantılar

• Garson, James. "Kipli Mantık" . Stanford Felsefe Ansiklopedisi .
• Moschovakis, Joan (2018). "Sezgisel Mantık" . Stanford Felsefe Ansiklopedisi . Metafizik Araştırma Laboratuvarı, Stanford Üniversitesi.
• Detlovs, V.; Podnieks, K. "4.4 Yapıcı Önermeler Mantığı — Kripke Semantics" . Matematiksel Mantığa Giriş . Letonya Üniversitesi. Not: Yapıcı = sezgisel.
• Burgess, John P. "Kripke Modelleri" . Arşivlenmiş orijinal 2004-10-20 tarihinde.
• "Kripke modelleri" , Matematik Ansiklopedisi , EMS Press , 2001 [1994]