關係語義

克里普克語義(也叫做關係語義或框架語義，並經常混淆於可能世界語義)是模態邏輯系統的形式語義，於 1950 年代晚期和 1960 年代早期由索爾·阿倫·克里普克建立。它後來為另一個非經典邏輯，最重要的直覺邏輯所接受。克里普克語義的發現是非經典邏輯開發中重大突破，因為這種邏輯的模型論在克里普克之前實際上是不存在的。模態邏輯的語義.對於我們的目的，模態邏輯的語言由命題變數，讀者喜歡的布林連結詞的完備集合(比如 {→,¬} 或 {∨,∧,¬})，和模態運算元 formula_1 (“必然性”)構成。對偶的模態運算元 formula_2 (“可能性”) 定義為一個簡寫: formula_3。更多背景請態邏輯。基本定義.克里普克框架或模態框架是  對，這裡的 "W" 是非空集合，"R" 是在 "W" 上的二元關係。"W" 的元素叫做節點或世界，而 "R" 叫做可及關係。克里普克模型是 formula_4 三元組，這裡的 formula_5 是克里普克框架，而 formula_6 是在 "W" 的節點和模態公式之間的如下關係:我們把 formula_14 讀做 “"w" 滿足 "A"”，“"A" 滿足於 "w"”，或 “"w" 力迫 "A"”。關係 formula_6 叫做“滿足關係”、“求值關係”或“力迫關係”。注意滿足關係由它在命題變數上的值唯一確定。公式 "A" 在下列之中是有效的:我們定義 "Thm(C)" 為在 "C" 中有效的所有公式的集合。反過來說，如果 "X" 是公式的集合，則設 "Mod(X)" 是使來自 "X" 的所有公式有效的所有框架的類。一個模態邏輯(就是說一個公式的集合) "L" 關於框架的類 "C" 是可靠的，如果 "L"⊆"Thm(C)"。"L" 關於"C" 是完備的，如果 "L"⊇"Thm(C)"。對應性和完備性.語義對於邏輯(就是推理系統)研究是有用的，條件是在語義"蘊涵"關係忠實的反映語法對應物 -- "推論"關係("可推導性")。所以知道哪個模態邏輯關於哪類克里普克框架是可靠的和完備的，併為它們確定這種類是關鍵性的。對於克里普克框架的任何類 "C"，"Thm(C)" 是正規模態邏輯；特別是，最小化正規模態邏輯 "K" 的定理，在所有克里普克模型中都是有效的。不幸的是，逆命題不是一般性成立的: 有克里普克不完備的正規模態邏輯。事實上這不是問題，因為實際中研究的多數模態系統關於由簡單條件所描述的框架類是完備的。正規模態邏輯 "L" 對應於框架類 "C"，條件是 "C"="Mod(L)"。換句話說，"C" 是 "L" 關於 "C" 是可靠的最大的框架類；隨後 "L" 是克里普克完備的當且僅當它關於它所對應的類是完備的。作為一個例子，考慮模式 "T" : formula_1"A" → "A"。"T" 在任何自反的框架  中是有效的: 如果 "w" formula_21"A"，則 "w" formula_6"A"，因為 "w" "R" "w"。在另一方面，使 "T" 有效的框架必須是自反的: 固定 "w" ∈"W"，並定義命題變數 "p" 的滿足為如下:"u" formula_6"p" 當且僅當 "w" "R" "u"。那麼 "w" formula_21"p"，所以 "w" formula_6"p" 於 "T"，這意味著 "w" "R" "w" 使用了 formula_6 的定義。我們見到 "T" 對應於自反的克里普克框架的類。特徵化 "L" 的對應類經常比證明它的完備性要容易許多，所以對應性充當完備性證明的指導。對應性還用於證實模態邏輯的"不完備性":假定 "L"1⊆"L"2 是對應於同一個框架類的正規模態邏輯，"L"1 不證明 "L"2 的所有定理。那麼 "L"1 是克里普克不完備的。例如，模式 formula_27 生成一個不完備的邏輯，因為它對應於同 "GL" 一樣的框架類(viz. 傳遞性和逆良基的框架)，但是它不證明 formula_28。在下表中給出常見模態公理和它們對應的類的列表。注意: 公理的名字經常是多變的。下面是一些常見正規模態邏輯系統的列表。對於其中一些的框架條件是簡化了的: 邏輯關於在表中給出的框架類是"完備的"，但是它們可能"對應"於更大的一類框架。典範模型.對於任何正規模態邏輯 "L"，我們可以構造一個克里普克模型(稱為典範模型)，它且只有它使 "L" 的定理有效，透過接納使用極大一致集合作為模型的標準技術。典範克里普克模型扮演的角色類似於在代數語義中的 Lindenbaum–Tarski代數構造。公式集合 "L"是"一致的"，如果從它們、"L" 的公理和肯定前件中不能推匯出矛盾。"極大 L一致的集合"(簡寫為 "L"-"MCS")是沒有真"L"一致的超集的 "L"一致的集合。"L" 的典範模型是克里普克模型 ，這裡的 "W" 是所有"L"-"MCS"，而關係 "R" 和 formula_6 為如下:formula_31 當且僅當對所有的公式 formula_32，如果 formula_33 則 formula_34，formula_35 當且僅當 formula_36。典範模型是 "L" 的模型，因為所有的 "L"-"MCS" 包含 "L" 的所有定理。透過佐恩引理，每個 "L"一致的集合都包含在一個 "L"-"MCS" 中，特別是在 "L" 中不可證明的所有公式都在典範模型中有一個反例。典範模型的主要應用是完備性證明。例如，"K" 的典範模型的性質直接蘊含 "K" 關於所有克里普克框架類的完備性。這個論證"不"適合任意的 "L"，因為沒有對典範模型的底層"框架"滿足 "L" 的框架條件的擔保。我們說一個公式或公式的集合 "X" 關於克里普克的一個性質 "P" 是典範的，如果明顯的，公式的典範集合的並集自身是典範的。服從前面的討論，由公式的典範集合公理化的任何邏輯是克里普克完備的和緊緻的。公理 "T"、"4"、"D"、"B"、"5"、"H"、"G"(和它們的任意組合)都是典範的。"GL" 和 "Grz" 不是典範的，因為他們不是緊湊的。公理 "M" 自身不是規範的(Goldblatt, 1991)，但是組合的邏輯 "S4.1"(事實上甚至 "K4.1") 是典範的。一般的，給定的公理是否是典範的是不可判定的。不過我們知道一個好的充分條件: H。Sahlqvist 識別瞭如下廣泛的一類公式(現在叫做Sahlqvist公式)這是一個非常強力的準則；例如，上面列出的典範的所有公理是實際上的(等價於) Sahlqvist 公式。有限模型性質.邏輯擁有有限模型性質(FMP)，如果它關於有限框架的類是完備的。這個概念的主要應用之一是可判定性問題: 它服從 Post定理，有 FMP 的遞迴公理化的模態邏輯 "L" 是可判定的，倘若給定的有限框架是否是 "L" 的模型是可判定的。特別是，有 FMP 的所有的有限可公理化的邏輯都是可判定的。有各種方法為給定的邏輯建立 FMP。精練並擴充套件規範模型構造通常就行了，使用工具如過濾或拆分。還有一種可能性，給予免切的相繼式演算的完備性證明通常直接產生有限模型。多數實際上使用的模態系統(包括所有上面列出的)都有 FMP。在某些情況下，我們可以使用 FMP 來證明邏輯的克里普克完備性: 所有正規模態邏輯關於模態代數的類都是完備的，而"有限的"模態代數可以變換成克里普克框架。作為例子，Robert Bull 使用這個方法證明了 "S4.3" 的所有普通擴充套件都有 FMP，並且是 克里普克完備的。多模態邏輯.克里普克語義對有多於一個模態的邏輯有直接的推廣。帶有 formula_37 作為必然性運算元的集合的語言的 克里普克框架，由對每個 "i" ∈"I" 裝備上二元關係 "Ri" 一個非空集合 "W"構成。滿足關係的定義修改為如下:formula_38 當且僅當 formula_39。由 Tim Carlson 發現的簡化的語義，經常用於多模態可證明性邏輯。Carlson 模型是結構 ，帶有一個單一的可及關係 "R"，和給每個模態的子集 "Di" ⊆ "W"。滿足性定義為formula_38 當且僅當 formula_41。Carlson 模型比通常的多模態克里普克模型易於形象化和使用；但是，克里普克完備的多模態邏輯是 Carlson 不完備的。直覺邏輯的語義.直覺邏輯的克里普克語義服從和模態邏輯的語義同樣的原理，但是它使用了滿足的不同的定義。直覺克里普克模型是一個三元組 formula_42，這裡的 formula_43 是偏序(也有說是預序) 克里普克框架，而 formula_6 滿足下列條件:直覺邏輯關於它的克里普克語義是可靠的和完備的，並且它有 FMP。直覺一階邏輯.設 "L" 是一階語言。"L" 的克里普克模型是三元組  是直覺克里普克框架，"Mw" 是 "w" ∈"W" 每個節點的(經典) "L"-結構，而下列相容性條件只要在 "u" ≤ "v" 時都是成立的:給出經由 "Mw" 的元素的變數求值 "e"，我們定義滿足關係 "w" formula_6"A"["e"]:這裡的 "e"("x"→"a") 是給予 "x" 值 "a" 的求值，在其他方面一致於 "e"。Kripke-Joyal 語義.作為獨立開發的層論的一部分，在 1965 年左右認識到克里普克語義密切相關於在 topos論中對存在量化的處理。就是對一個層的截面的存在性的'區域性'示象是一種'可能性'的邏輯。因為這種開發是很多人的工作，比之於理論更合於概念上洞察的天性，歸與榮譽不是很容易的。Kripke-Joyal 語義這個名稱經常用做這種聯絡。模型構造.同在經典的模型論中一樣，有從其他模型構造一個新的克里普克模型的方法。在克里普克語義中天然的同態叫做p-態射(它是"偽滿射"的簡寫，但這個術語很少用)。克里普克框架  的 p-態射是一個對映"f":"W" → "W’" 滿足克里普克模型  的 p-態射是它們的底層框架的 p-態射 "f":"W" → "W’"，它滿足對於任何命題變數 "p"，"w" formula_6"p" 當且僅當 "f(w)" formula_6’"p"。P-態射是特殊種類的雙仿(bisimulation)。一般的說，在框架  之間的雙仿是關係 "B ⊆ W × W’"，它滿足下列 “zig-zag” 性質:模型的雙仿是對保持原子公式的力迫的補充要求:對於任何命題變數 "p"，如果 "w B w’"，則 "w" formula_6"p" 當且僅當 "w’" formula_6’"p"。從這個定義我們得到的關鍵性質是模型的雙仿(所以也是 p-態射)保持"所有"公式的滿足性，而不只是命題變數。我可以使用拆分(unravelling)把克里普克模型變換成樹。給出一個模型  的集合，使得對於所有 "i"&lt;"n" 和 "s" formula_6"p"，"wi" "R" "wi+1" 當且僅當對於所有變數 "p"，"wn" formula_6"p"。定義可及關係 "R’" 變化；在最簡單的情況下我們置,但是很多應用需要這個關係的自反與/或傳遞閉包，或類似的變更。過濾是 p-態射的一個變種。設 "X" 是在採納子公式(subformulas)下閉合的公式的集合。模型  的對映 "f"，使得得到了 "f" 保持來自 "X" 的所有公式的滿足性。在典型的應用中，我們把 "f" 採納為在"W" 在下列關係上對份額的投影"u ≡X v" 當且僅當對於所有 "A" ∈"X"，"u" formula_6"A" 當且僅當 "v" formula_6"A"。同在拆分的情況下一樣，定義可及關係在份額變化上。一般框架語義.克里普克語義的主要缺陷是存在克里普克不完備邏輯和完備但不緊緻的邏輯。可以使用來代數語義的想法，透過對克里普克裝備限制可能求值的集合的額外結構來修正。這引發了一般框架語義。歷史和術語.克里普克語義不是克里普克首創的，以上述方式給出的基於使求值相對於節點的語義早於克里普克的工作許久:儘管克里普克語義的根本思想在克里普克首次發表之前就廣為流傳了，克里普克 關於模態邏輯的工作仍可恰當的當作是開拓性的。最重要的是，克里普克是第一個為模態邏輯證明了完備性定理的人，並且克里普克識別了最弱的正規模態邏輯。儘管克里普克的工作有開創性貢獻，很多模態邏輯學家反對術語 克里普克語義，因為這是對先驅們做的重要貢獻的失禮。反對另一個最廣泛使用的術語可能世界語義的理由是它不適合應用於不是可能性和必然性的模態，比如在認識或道義邏輯中。他們喜歡術語關係語義或框架語義。