분지 유형 이론

논리학에서 '''분지 유형 이론'''(分枝類型理論, , 약자 RTT) 또는 '''복잡 유형 이론'''(複雜類型理論)은 단순 유형 이론보다 더 세분된 유형을 사용하는 논리 체계이다.
다음과 같은 데이터가 주어졌다고 하자. (여기서 은 음이 아닌 정수의 집합이다.)
* 최대 원소를 갖지 않는 가산 무한 정렬 전순서 집합 . 그 원소를 '''변수'''(變數, )라고 한다.
* 집합 . 그 원소를 '''개체'''(個體, )라고 한다.
* 집합  및 함수 . 각 에 대하여, 의 원소를 '''항 관계'''(項關係, )라고 한다.
그렇다면, 에 대한 분지 유형 이론은 다음과 같다.
=== 분지 유형 ===
분지 유형 이론에서 사용되는 '''분지 유형'''(分枝類型, )과 이들의 '''차수'''(次數, )는 다음과 같다.
* 은 0차 분지 유형이다.
* 차 분지 유형  및 자연수 에 대하여, 는 차 분지 유형이다.
이들 가운데, '''술어적 분지 유형'''(述語的分枝類型, )은 다음과 같다.
* 은 술어적 분지 유형이다.
* 차 술어적 분지 유형 에 대하여, 는 술어적 분지 유형이다. (일 경우, 은 술어적 분지 유형이다.)
술어적 분지 유형은 차수를 생략한 채 와 으로 쓸 수 있다.
분지 유형 이론의 '''문맥'''(文脈, )은 유한 개의 변수의 집합과 분지 유형의 집합 사이의 함수이다. 문맥은 변수 와 분지 유형 의 순서쌍 들의 유한 집합으로 여길 수 있다. 이 경우, 문맥 의 '''정의역'''(定義域, )은 다음과 같이 나타낼 수 있다.
:
=== 논리식 ===
분지 유형 이론의 '''유사 논리식'''(類似論理式, )은 다음과 같다.
* 항 관계  및 변수 또는 개체 에 대하여, 은 유사 논리식이다.
** 일 경우 유사 논리식 은 0항 관계 와 구분되어야 한다. 분지 유형 이론에서 항 관계는 유사 논리식이 아니다.
* 변수  및 유한 개의 변수 또는 개체 또는 유사 논리식 에 대하여, 는 유사 논리식이다.
** 일 경우 유사 논리식 은 변수 와 구분되어야 한다. 분지 유형 이론에서 변수나 개체는 유사 논리식이 아니다.
* 유사 논리식 에 대하여, 와 는 유사 논리식이다.
* 유사 논리식  및 그 자유 변수  및 분지 유형 에 대하여, 는 유사 논리식이다.
유사 논리식의 집합을 라고 하자. 또한 각 유사 논리식 에 대하여, 가  속에 등장하는 모든 변수의 집합이라고 하고,
:
가 의 모든 자유 변수라고 하자.
문맥 에서 개체 또는 유사 논리식 가 분지 유형 를 갖는다는 것은 로 표기하며, 다음과 같이 재귀적으로 정의된다. (여기서 는 를 뜻한다.)
* 개체 에 대하여, 이다.
* 항 관계  및 개체 에 대하여, 이다.
* (논리 연산) 문맥  및 유사 논리식  및 분지 유형 에 대하여, 만약 이며, 이며, 라면,이다.
* (한정) 문맥  및 유사 논리식  및  및 분지 유형 에 대하여, 만약 라면,이다.
* (매개 변수에 대한 추상화) 문맥  및 유사 논리식  및 그 개체이거나 유사 논리식인 매개 변수  및 분지 유형  및 변수 에 대하여, 만약 이며 이라면,이다. 여기서 는 에 등장하는 와 αΓ-동치인 각 매개 변수 를 로 대체하여 얻는 유사 논리식이다. (《수학 원리》에서 이는 가 술어적 분지 유형인 경우로 제한된다.)
* (논리식에 대한 추상화) 문맥  및 유사 논리식  및 분지 유형  및 변수 에 대하여, 만약 이라면,이다. (이 경우 반드시 임을 보일 수 있다.) (《수학 원리》에서 이는 가 술어적 분지 유형인 경우로 제한된다.)
* (치환) 문맥  및 자유 변수를 갖는 유사 논리식  및 개체 또는 유사 논리식  및 분지 유형 에 대하여, 만약 이며, 라면,이다. (이 경우 는 반드시 정의됨을 보일 수 있다.)
* (약화) 문맥  및 유사 논리식  및 분지 유형 에 대하여, 만약 이며, 라면, 이다.
* (순열) 문맥  및 유사 논리식  및  및 분지 유형  및 변수 에 대하여, 만약 라면,이다.
주어진 문맥 속에서, 유사 논리식의 분지 유형은 존재하지 않을 수 있으나, 만약 존재한다면 이는 유일하다. 주어진 유사 논리식은 서로 다른 문맥 속에서 서로 다른 분지 유형을 가질 수 있다. 유사 논리식 에 대하여, 인 문맥 과 가 존재한다면, 를 '''논리식'''(論理式, )이라고 한다.
=== 자유 변수, 매개 변수, 재귀 매개 변수 ===
분지 유형 이론의 각 유사 논리식 의 '''자유 변수'''(自由變數, )의 집합 , '''매개 변수'''(媒介變數, )의 집합 , '''재귀 매개 변수'''(再歸媒介變數, )의 집합 은 다음과 같이 재귀적으로 정의된다. (매개 변수와 재귀 매개 변수는 이름과 달리 변수가 아닐 수 있다.)
* 항 관계  및 변수 또는 개체 에 대하여,
* 변수  및 유한 개의 변수 또는 개체 또는 유사 논리식 에 대하여,
* 유사 논리식 에 대하여,
* 유사 논리식  및 그 자유 변수 에 대하여,
=== 치환 ===
변수 또는 개체 또는 유사 논리식  및 서로 다른 변수 에 대하여,
:
이라고 하자.
유사 논리식  및 변수 또는 개체 또는 유사 논리식  및 서로 다른 변수 에 대하여, '''치환 실례'''(置換實例, ) 는 다음과 같이 재귀적으로 정의된다.
* 항 관계  및 변수 또는 개체  및 서로 다른 변수 에 대하여,
* 변수  및 및 변수 또는 개체 또는 유사 논리식  및 서로 다른 변수 에 대하여,
* 유사 논리식  및 변수 또는 개체 또는 유사 논리식  및 서로 다른 변수 에 대하여,
* 유사 논리식  및 그 자유 변수  및 분지 유형  및 변수 또는 개체 또는 유사 논리식  및 서로 다른 변수 에 대하여,
위 경우에 속하지 않는 치환 실례는 정의되지 않는다. 예를 들어, 변수 또는 개체 또는 유사 논리식  및 서로 다른 변수 에 대하여, 만약 이거나, 이며 의 자유 변수가 정확히 개가 아닐 경우, 는 정의되지 않는다.
=== α-동치 ===
두 유사 논리식 에 대하여, 다음 조건을 만족시키는 전단사 함수 가 존재한다면, 가 서로 '''α-순열 동치'''(α-順列同値, )라고 한다.
* 는 에 등장하는 각 변수 를 로 대체하여 얻는다. (특히, 이다.)
두 유사 논리식 에 대하여, 다음 두 조건을 만족시키는 전단사 함수 가 존재한다면, 가 서로 '''α-동치'''(α-同値, )라고 한다.
* 는 에 등장하는 각 변수 를 로 대체하여 얻는다. (특히, 이다.)
* 는 증가 함수이다. 즉, 임의의 에 대하여, 
두 유사 논리식  및 문맥 에 대하여, 다음 세 조건을 만족시키는 전단사 함수 가 존재한다면, 가 서로 '''αΓ-동치'''(αΓ-同値, )라고 한다.
* 는 에 등장하는 각 변수 를 로 대체하여 얻는다. (특히, 이다.)
* 는 증가 함수이다. 즉, 임의의 에 대하여, 
* 임의의  및 분지 유형 에 대하여, 
버트런드 러셀이 《수학 원리》에서 제시하였다.
* 
* 
* 
분류:유형 이론