제도 (논리학)

수리논리학과 컴퓨터 과학에서 제도(制度, 영어: institution 인스티튜션^[*])는 문법과 모형 이론이 부여된 논리 체계의 추상화이다.

정의

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

$\operatorname {Ob} ^{\operatorname {op} }\colon \operatorname {Cat} ^{\operatorname {op} }\to \operatorname {Set} ^{\operatorname {op} }$

와 멱집합 함자

${\mathcal {P}}\colon \operatorname {Set} \to \operatorname {Set} ^{\operatorname {op} }$

${\mathcal {P}}\colon X\mapsto {\mathcal {P}}(X)$

${\mathcal {P}}\colon (f\colon X\to Y)\mapsto (f^{-1}\colon {\mathcal {P}}(Y)\to {\mathcal {P}}(X))$

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

${\mathcal {I}}=\operatorname {Ob} ^{\operatorname {op} }\downarrow {\mathcal {P}}$

를 생각할 수 있다. 즉, ${\mathcal {I}}$는 구체적으로 다음과 같다.

• ${\mathcal {I}}$의 대상 $(S,{\mathcal {M}},\models )$은 다음과 같은 순서쌍이다.
  • 집합 $S$. $S$를 문장의 집합이라고 한다.
  • 작은 범주 ${\mathcal {M}}$. ${\mathcal {M}}$의 원소를 모형이라고 한다.
  • 함수 ${\models }\colon \operatorname {Ob} ({\mathcal {M}})\to {\mathcal {P}}(S)$. 이를 만족 관계(영어: satisfaction relation)라고 한다. 보통, $\phi \in S$ 및 $M\in {\mathcal {M}}$에 대하여, $\phi \in \operatorname {\models } (M)$를 이항 관계 $M\models \phi$로 표기한다.
• ${\mathcal {I}}$의 사상 $(f,G)\colon (S,{\mathcal {M}},\models )\to (S',{\mathcal {M}}',\models ')$은 다음과 같은 데이터로 구성된다.
  • $f\colon S\to S'$는 함수이다.
  • $G\colon {\mathcal {M}}'\to {\mathcal {M}}$는 함자이다.
  • 이들은 다음 조건을 만족시켜야 한다.

    임의의 모형 $M'\in {\mathcal {M}}'$ 및 문장 $\phi \in S$에 대하여, $M'\models 'f_{S}(\phi )\iff G(M')\models \phi$이다. 즉, 다음 그림이 가환 그림이다.

    ${\begin{matrix}\operatorname {Ob} ({\mathcal {M}}')&{\overset {\operatorname {Ob} (G)}{\to }}&\operatorname {Ob} ({\mathcal {M}})\\{\scriptstyle \models '}\downarrow {}{\color {White}\scriptstyle \models '}&&{\color {White}\scriptstyle \models }\downarrow {}\scriptstyle \models \\{\mathcal {P}}(S')&{\underset {f_{S}^{-1}}{\to }}&{\mathcal {P}}(S)\\\end{matrix}}$

범주 ${\mathcal {L}}$에 대하여, ${\mathcal {L}}$ 위의 제도(영어: institution)는 함자 $I\colon {\mathcal {L}}\to {\mathcal {I}}$이다. 이 경우, ${\mathcal {L}}$을 제도 $I$의 언어들의 범주라고 한다. 같은 언어 위의 두 제도 사이의 사상은 자연 변환이다.

종류

불 제도

제도 $I\colon {\mathcal {L}}\to {\mathcal {I}}$가 다음 두 성질을 만족시킨다면, $(S,\models )$가 불 제도(영어: Boolean institution)라고 한다.

• (부정의 존재) 임의의 언어 $L\in {\mathcal {L}}$ 및 모형 $M\in {\mathcal {M}}(L)$ 및 문장 $\phi \in S(L)$에 대하여, $M\models \phi \iff M\not \models \chi$가 되는 문장 $\chi \in S(L)$이 존재한다.
• (논리곱의 존재) 임의의 언어 $L\in {\mathcal {L}}$ 및 모형 $M\in \operatorname {Model} (L)$ 및 두 문장 $\phi ,\chi \in S(L)$에 대하여, $M\models \psi \iff (M\models \phi \land M\models \psi )$가 되는 문장 $\psi \in S(L)$이 존재한다.

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

콤팩트성

기수 $\kappa$가 주어졌다고 하자. 제도 $I\colon {\mathcal {L}}\to {\mathcal {I}}$가 다음 조건을 만족시킨다면, $\kappa$-콤팩트 제도(영어: compact institution)라고 한다.

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

  $\left(\exists M\in {\mathcal {M}}(L)\colon M\models A\right)\iff \left(\forall A'\in {\mathcal {P}}_{<\kappa }(A)\exists M\in {\mathcal {M}}(L)\colon M\models A'\right)$

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

$\forall \phi \in A\colon M\models \phi$

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

예

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

역사

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

각주

• Diaconescu, Răzvan (2008). 《Institution-independent model theory》. Studies in Universal Logic (영어). Birkhäuser. doi:10.1007/978-3-7643-8708-2. ISBN 978-3-7643-8707-5. ISSN 2297-0282. Zbl 1144.03001. 
• Diaconescu, Răzvan (2007). 〈Institutions, Madhyamaka, and universal model theory〉. Béziau, Jean-Yves; Costa-Leite, Alexandre. 《Perspectives on universal logic》 (PDF) (영어). Polimetrica International Scientific Publisher. 41–65쪽. 2012년 2월 9일에 원본 문서 (PDF)에서 보존된 문서. 2016년 7월 31일에 확인함. 

외부 링크

• “Abstract model theory”. 《nLab》 (영어). 
• Diaconescu, Răzvan. “Institution theory”. 《Internet Encyclopedia of Philosophy》 (영어). ISSN 2161-0002. 
• Goguen, Joseph A. (2006년 1월 6일). “Institutions” (영어). 
• Goguen, Joseph A. “Institutions and Peirce's triadic semiotics” (영어).