제도 (논리학)

틀:위키데이터 속성 추적 수리논리학과 컴퓨터 과학에서 제도(制度, 틀:Llang)는 문법과 모형 이론이 부여된 논리 체계의 추상화이다.

정의

작은 범주의 범주의 반대 범주 ${\mathrm{Cat}}^{\mathrm{op}}$에서 집합의 범주의 반대 범주로 가는, 사상을 잊는 망각 함자

${\mathrm{Ob}}^{\mathrm{op}}:{\mathrm{Cat}}^{\mathrm{op}}\to {\mathrm{Set}}^{\mathrm{op}}$

와 멱집합 함자

$𝒫:\mathrm{Set}\to {\mathrm{Set}}^{\mathrm{op}}$

$𝒫:X\mapsto 𝒫(X)$

$𝒫:(f:X\to Y)\mapsto (f^{-1}:𝒫(Y)\to 𝒫(X))$

를 생각하자. 그렇다면 쉼표 범주

$ℐ={\mathrm{Ob}}^{\mathrm{op}}\downarrow 𝒫$

를 생각할 수 있다. 즉, $ℐ$는 구체적으로 다음과 같다.

• $ℐ$의 대상 $(S,ℳ,\models )$은 다음과 같은 순서쌍이다.
  • 집합 $S$. $S$를 문장의 집합이라고 한다.
  • 작은 범주 $ℳ$. $ℳ$의 원소를 모형이라고 한다.
  • 함수 $\models :\mathrm{Ob}(ℳ)\to 𝒫(S)$. 이를 만족 관계(틀:Llang)라고 한다. 보통, $\varphi \in S$ 및 $M\in ℳ$에 대하여, $\varphi \in \mathrm{\models }(M)$를 이항 관계 $M\models \varphi$로 표기한다.
• $ℐ$의 사상 $(f,G):(S,ℳ,\models )\to (S^{\prime },{ℳ}^{\prime },{\models }^{\prime })$은 다음과 같은 데이터로 구성된다.
  • $f:S\to S^{\prime }$는 함수이다.
  • $G:{ℳ}^{\prime }\to ℳ$는 함자이다.
  • 이들은 다음 조건을 만족시켜야 한다.

    임의의 모형 $M^{\prime }\in {ℳ}^{\prime }$ 및 문장 $\varphi \in S$에 대하여, $M^{\prime }{\models }^{\prime }{f}_S(\varphi )⟺G(M^{\prime })\models \varphi$이다. 즉, 다음 그림이 가환 그림이다.

    $\begin{array}{ccc}\mathrm{Ob}({ℳ}^{\prime })& \stackrel{\mathrm{Ob}(G)}{\to }& \mathrm{Ob}(ℳ)\\ {\models }^{\prime }\downarrow {\models }^{\prime }& & \models \downarrow \models \\ 𝒫(S^{\prime })& \to f_S^{-1}& 𝒫(S)\end{array}$

범주 $ℒ$에 대하여, $ℒ$ 위의 제도(틀:Llang)는 함자 $I:ℒ\to ℐ$이다. 이 경우, $ℒ$을 제도 $I$의 언어들의 범주라고 한다. 같은 언어 위의 두 제도 사이의 사상은 자연 변환이다.

종류

불 제도

제도 $I:ℒ\to ℐ$가 다음 두 성질을 만족시킨다면, $(S,\models )$가 불 제도(틀:Llang)라고 한다.

• (부정의 존재) 임의의 언어 $L\in ℒ$ 및 모형 $M\in ℳ(L)$ 및 문장 $\varphi \in S(L)$에 대하여, $M\models \varphi ⟺M\models ̸\chi$가 되는 문장 $\chi \in S(L)$이 존재한다.
• (논리곱의 존재) 임의의 언어 $L\in ℒ$ 및 모형 $M\in \mathrm{Model}(L)$ 및 두 문장 $\varphi ,\chi \in S(L)$에 대하여, $M\models \psi ⟺(M\models \varphi \wedge M\models \psi )$가 되는 문장 $\psi \in S(L)$이 존재한다.

이 경우, 부정과 논리곱을 사용하여 고전 명제 논리의 연산(논리합, 함의, 동치 등)들을 정의할 수 있다.

콤팩트성

기수 $\kappa$가 주어졌다고 하자. 제도 $I:ℒ\to ℐ$가 다음 조건을 만족시킨다면, $\kappa$-콤팩트 제도(틀:Llang)라고 한다.

• 임의의 언어 $L\in ℒ$ 및 임의의 부분 집합 $A\subseteq S(L)$에 대하여, 다음이 성립한다.

  $(\mathrm{\exists }M\in ℳ(L):M\models A)⟺(\mathrm{\forall }{A}^{\prime }\in {𝒫}_{<\kappa }(A)\mathrm{\exists }M\in ℳ(L):M\models A^{\prime })$

여기서, 문장들의 집합 $A$ 및 모형 $M$에 대하여 $M\models A$는

$\mathrm{\forall }\varphi \in A:M\models \varphi$

를 뜻한다. ${𝒫}_{<\kappa }(A)$는 $A$의, 크기가 $\kappa$ 미만의 부분 집합들의 족이다.

예

1차 논리와 그 표준적 모형은 제도를 이룬다. 이 밖에도, 다른 많은 논리 체계들을 제도로 나타낼 수 있다.

역사

제도의 개념은 1970년대에 조지프 애머디 고겐(틀:Llang, 1941~2006)과 로드니 마티노 버스톨(틀:Llang, 1934~)이 도입하였다.

각주

• 틀:서적 인용
• 틀:서적 인용

외부 링크

• 틀:Nlab
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용