제도 (논리학)

수리논리학과 컴퓨터 과학에서 제도(制度, )는 문법과 모형 이론이 부여된 논리 체계의 추상화이다.

 정의 
작은 범주의 범주의 반대 범주 에서 집합의 범주의 반대 범주로 가는, 사상을 잊는 망각 함자

와 멱집합 함자

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

를 생각할 수 있다. 즉, 는 구체적으로 다음과 같다.
 의 대상 은 다음과 같은 순서쌍이다.
 집합 . 를 문장의 집합이라고 한다.
 작은 범주 . 의 원소를 모형이라고 한다.
 함수 . 이를 만족 관계()라고 한다. 보통,  및 에 대하여, 를 이항 관계 로 표기한다.
 의 사상 은 다음과 같은 데이터로 구성된다.
 는 함수이다.
 는 함자이다.
 이들은 다음 조건을 만족시켜야 한다.
 임의의 모형  및 문장 에 대하여, 이다. 즉, 다음 그림이 가환 그림이다.


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

 종류 
 불 제도 
제도 가 다음 두 성질을 만족시킨다면, 가 불 제도()라고 한다.
 (부정의 존재) 임의의 언어  및 모형  및 문장 에 대하여, 가 되는 문장 이 존재한다.
 (논리곱의 존재) 임의의 언어  및 모형  및 두 문장 에 대하여, 가 되는 문장 이 존재한다.
이 경우, 부정과 논리곱을 사용하여 고전 명제 논리의 연산(논리합, 함의, 동치 등)들을 정의할 수 있다.

 콤팩트성 
기수 가 주어졌다고 하자.
제도 가 다음 조건을 만족시킨다면, -콤팩트 제도()라고 한다.
 임의의 언어  및 임의의 부분 집합 에 대하여, 다음이 성립한다.

여기서, 문장들의 집합  및 모형 에 대하여 는

를 뜻한다. 는 의, 크기가  미만의 부분 집합들의 족이다.

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

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

 각주 




 외부 링크 





분류:수리논리학
분류:이론 컴퓨터 과학