추이성

transitivity / 推移性

통상적으로 이항 관계에 대하여 정의되는 수학적 특성으로, 동일한 이항 관계의 연쇄 적용이 단일한 적용으로 '압축'될 수 있는 성질을 말한다. 이행성(移行性)이라고도 한다.

조금 더 풀어서 말하면, 제1의 대상과 제2의 대상, 제2의 대상과 제3의 대상이 각각 동일한 이항 관계를 띰으로써 이 세 대상이 연쇄되어 있다면 제1의 대상과 제3의 대상 사이에도 동일한 이항 관계가 성립한다는 것이다. 즉, 이행성을 생각하기 위해서는 적어도 세 개의 대상을 고려해야 한다. 쉽고 직관적인 이해를 위해서는 아래 '예시' 문단을 보자.

조금만 더 확장해서 생각해 보면 세 대상의 연쇄를 압축할 수 있는 이상 그보다 많은 대상의 연쇄 역시 단일한 이항 관계로 무조건 압축될 수 있음을 알 수 있다. 즉, 3 이상의 자연수 $n$에 대하여, 제1의 대상과 제2의 대상, 제2의 대상과 제3의 대상, ... , 제$(n-1)$의 대상과 제$n$의 대상이 각각 동일한 이항 관계를 띰으로써 이 $n$개의 대상이 연쇄되어 있다면, 제1의 대상과 제$n$의 대상 역시 동일한 이항 관계를 갖는다는 것이다.

추이성을 갖는 것을 추이적(推移的, transitive)이라고 하며, 이행적(移行的)이라고도 한다. 수학적으로 엄밀히 정의되어 다뤄지지만 수학에서만 사용되는 것은 아니며 수학이 응용되는 경제학, 대상의 속성을 논하는 철학에서도 등장하는, 다분히 철학적인 개념이다.

가장 일반적으로는 이항 술어 등이 지닐 수 있으며, 이하 문단에서는 편의상 집합 범위의 이항 관계를 위주로 설명한다.

집합 $X$ 위의 동종 이항 관계 $R \sub X \times X$를 생각하자. $x$와 $y$가 이항 관계 $R$을 갖는다는 것을 $R(x,y)$로 표기할 수 있다. $R$이 추이적(transitive) 관계라 함은 집합 $X$의 임의의 세 원소 $x$, $y$, $z$에 대하여 다음이 성립함을 의미한다.

$$( R(x, y) \land R(y, z) )\longrightarrow R(x, z)$$
반대로 $R$이 비추이적(intransitive) 관계라 함은 집합 $X$의 임의의 세 원소 $x$, $y$, $z$에 대하여 다음이 성립함을 의미한다.

$$( R(x, y) \land R(y, z) ) \longrightarrow \neg R(x, z)$$
즉, 추이성은 이항 관계 $R$ 자체에 주어지는 성질이 아니라, 이항 관계를 적용할 원소들을 모아놓은 집합 $X$도 전제되어야 하는 성질이다. 즉 추이성은 단일한 대상의 속성이 아니며, 이항 관계 $R$과 집합 $X$의 관계로서 나타난다. 그래서 $R$ 자체는 동일하더라도 $X$가 달라지면 추이성 여부는 달라질 수 있다. 그러나 편의상 '이항 관계 $R$이 추이적이다'라고 말하는 것은 무리가 없는데, 이 경우에도 암묵적으로는 어떤 집합 $X$가 전제되어 있음을 알아야 한다. 예를 들어 아래 예시에서 '조상/자손 관계'가 추이적이라고 할 때, 별도로 집합이 명시되어 있지 않더라도 암묵적으로는 '모든 사람의 집합'을 사용하고 있음이 전제된 것이다.

순서 관계의 경우, 추이성과 순환(cycle)이 양립할 수 없다. 이때 추이성은 순서 관계의 정의상 순서 관계에 포함되는 속성으로, 순서 관계는 순환할 수 없다고 바꾸어 말할 수 있다. 엄격한 순서(strict order)는 순환이 개입하면 반사성과 충돌하며, 부분 순서(partial order)는 순환이 개입하면 반대칭성과 충돌한다. 각 성질들 및 순서들의 개념은 이항 관계의 5문단 참고.

순서 관계가 아닌 경우, 추이성과 순환이 양립할 수 있다. 아래 예시 중 동치 관계/동일성이 좋은 예시이다. 요컨대 순서 관계에서는 정의상 반대칭성을 전제하기 때문에 대칭성이 금지되지만, 동치 관계는 대칭성을 오히려 당연한 것으로 받아들이는 개념이라는 차이가 있는 것이다.

한편, 추이성은 조건문으로 정의되므로, 공허참(vacuous truth)으로서 추이성이 성립하는 재미있는 경우도 생각할 수 있다. 추이성의 정의는 이항 관계 $R$에 대하여 $aRb$이고 $bRc$이면 $aRc$인 것인데, 이때 전건 자체가 참이 될 수 없다면 이 조건문은 참이 되며 이를 논리학에서는 '공허참' 또는 '공허한 참'이라고 한다. 공허참도 참이므로 이 경우 $R$은 엄연히 추이적이다. 예를 들어, 모든 사람의 집합 $X$에 대하여 "$a$가 $b$를 임신시켰다"라는 이항 관계를 $aRb$로 표시하자. $aRb$가 성립한다면 $a$는 남성이고 $b$는 여성이 된다. 여성은 다른 사람을 임신시킬 수 없으므로, 또 다른 대상 $c$의 값에 관계없이 $bRc$는 항상 거짓이다. 따라서 전건 '$aRb$이고 $bRc$' 전체가 항상 거짓이 되므로, 추이성의 조건은 공허한 참으로서 항상 충족된다. 이항 관계의 연쇄를 압축하는 것이 추이성의 직관이므로, 이 연쇄 자체가 불가능한 경우에는 일견 추이성이 성립하지 않는 것처럼 보이지만 적어도 형식논리적으로는 엄연히 $R$은 추이적이다. 단 일반적인 경우와는 매우 다른 것이 사실이며, 표현에 따라서는 '공허하게 추이적', '공허한 추이성'이라고 말할 수 있을 것이다.

또한 같은 이치로, 위 정의에서 $X=\varnothing$이면 모든 이항 관계 $R$은 공허한 추이성을 가지며, 집합 $X$의 어느 두 원소도 이항 관계 $R$을 갖지 않는 경우에도 그 $R$은 공허한 추이성을 갖는다. 후자의 경우를 공집합 관계(empty relation)라고 한다. 다음 예를 보자.

'친구이다'라는 이항 관계 $R$을 생각하자. 이때, 모든 사람은 자기 자신과 친구가 아니라고 해석하자. 어느 두 사람도 친구가 아닌 30명의 사람을 모은 집합 $X$를 생각하면, $R$은 $X$에 대하여 공허한 추이성을 갖는다. 이항 관계 $R$이 적용될 대상 자체가 없기 때문이다. 한편, $R$의 부정 $\neg R$은 '친구가 아니다'라는 또 다른 이항 관계인데, $\neg R$ 역시 $X$에 대하여 추이성을 갖지만 공허한 추이성은 아니다. $R$ 자체와는 달리 $\neg R$은 $X$의 원소들에 적용될 수 있으며, 그 적용의 결과 어느 두 사람을 뽑더라도 서로 친구가 아님을 알 수 있기 때문이다. 결국 동일한 상황에 대하여 '이항 관계의 부정'을 따로 도입하는 방식과, 이항 관계 자체를 '공집합 관계'로 해석하는 방식이 있는 것이다.