이항 관계(Binary relations)의 개념과 몇 가지 성질

어떤 집합 $A$에서 정의되는 이항 관계(binary relation), 혹은 단순히 관계(relation) $\mathrm{R}$는, 그 집합의 원소들의 순서쌍 $(x,y)$들을 원소로 갖는 어떤 집합이다.

이런 것을 왜 정의하는가? 일상 언어에서의 '관계가 있다'라는 말을 집합의 언어로 형식화한다고 생각하면 이해가 쉽다. 세 원소 $a,b,c \in A$ 가 만드는 순서쌍 중, 예를 들어서 $(a,b)$는 특정한 관계를 만족하지만, $(a,c)$는 그러한 관계를 만족하지 않는 상황을 얼마든지 생각할 수 있다. 이를 $(a,b)\in\mathrm{R}$, $(a,c)\notin\mathrm{R}$로 하여, '관계를 만족한다(만족하지 않는다)'는 것을 '집합 $\mathrm{R}$의 원소이다(원소가 아니다)'라고 형식화하는 것이다.

이때 이항 관계 $\mathrm{R}$에 별다른 조건은 없다. 즉 사람 눈으로 보기에 이게 정확히 어떤 관계인지 의미를 부여하기 어렵더라도 상관이 없다. 마치 함수(실제로 이항 관계는 함수의 일반화이다)가 반드시 우리가 아는 어떤 식 $f(\cdot)$를 이용하여 $y=f(x)$ 꼴로 간결하게 나타내어지거나 일상 언어로 의미가 부여될 필요는 없는 것과 같다.

이를 간단히 $a\mathrm{R}b$라고 표기하기도 한다. 이렇게 표기하면 상당히 생소해 보이지만, 결국 집합에 대한 이야기이므로 너무 낯설어하지 않아도 되며, 공부하다가 확실하지 않은 것은 집합의 언어로 풀어 쓰면서 확인하고 이해해 볼 수 있다. 그렇지만 이항 관계들을 능숙하게 다루기 위해서는 그렇게 매번 집합의 언어로 바꾸어서 다루기보다는, 이항 관계의 주요 성질들을 숙지한 뒤 $a\mathrm{R}b$와 같은 표기법을 바탕으로 다룰 줄 아는 것도 필요할테다.

이하에서는 주어진 이항 관계가 만족하거나 만족하지 않는 몇 가지 주요 성질들(비대칭성, (비)반사성, 반대칭성 등)을 소개하고, 집합과 논리를 연습할 겸 간단한 정리 1개의 증명을 다룬다.

1. 비대칭성(asymmetry)

$$\forall x,y \in A,\, (x,y)\in\mathrm{R} \Rightarrow (y,x)\notin\mathrm{R}.$$

이항관계 $\mathrm{R}$이 비대칭적(asymmetric)이라는 것은, $(x,y)$가 그 관계를 만족할 경우 이것을 뒤집은 $(y,x)$는 그 관계를 만족하지 않는다는 뜻이다. 집합의 원소를 점으로 표현하고 관계를 화살표로 표현하면, 이를 어떤 두 점 사이에도 화살표가 한 방향으로만 있어야 한다(혹은 아예 없거나)고 말할 수 있다. 그림을 통한 이해는 최하단 사진에서 볼 수 있다.

2. 반사성(reflexive)와 비반사성(irreflexive)

(1) 반사성

$$\forall a\in A, (a,a)\in\mathrm{R}.$$

이항관계 $\mathrm{R}$이 반사적이라는 말의 정의는, $A$의 모든 원소 $a$에 대해 $a$에서 출발해서 바로 자기 자신으로 돌아가는 화살표가 있어야 한다는 것이다 (여러 점을 거쳐서 다시 들어가는 것은 가능하다. 이항(binary), 즉 두 원소 사이의 관계이므로 이런 것은 고려의 대상이 아니다).

(2) 비반사성

$$\forall a\in A, (a,a)\notin\mathrm{R}.$$

이항관계 $\mathrm{R}$이 비반사적이라는 것은, $A$의 어떤 원소 $a$에 대해서도, $a$에서 출발해서 바로 자기 자신으로 돌아가는 화살표가 없어야 한다는 뜻이다. 이러한 비반사성은 단순히 '반사적이지 않다'는 것과는 다르다.

3. 반대칭성(antisymmetry)

$$\forall x,y\in A, \quad (x,y)\,\mathrm{and}\,(y,x)\in\mathrm{R}\,\,\Rightarrow\,\, x=y.$$

이항관계 $\mathrm{R}$이 반대칭적(antisymmetric)이라는 것은, 두 순서쌍 $(x,y),(y,x)$가 모두 $\mathrm{R}$을 만족하는 경우는 $x,y$가 사실 같은 원소인 경우뿐이라는 뜻이다. 이를 반대로 생각하면(대우명제) 더 쉬운데, $x,y$가 다른 원소일 경우에는 양쪽 화살표 둘 모두가 존재해서는 안 되고, 한쪽만 있거나 아예 없어야 한다는 뜻이다. 자기 자신에서 나와서 자기 자신으로 들어가는 화살표는 가능하다.

이상의 정의로부터, 어떤 이항관계가 반대칭인데, 자기 자신에서 나와서 자기 자신으로 들어가는 화살표까지 없으면, 그 이항관계는 비대칭이라는 것은 직관에 따라 비교적 명확하다. 실제로 다음이 성립한다. 즉 비대칭성과, '반대칭성 & 비반사성'은 서로 필요충분조건이다.

$$\textrm{R is asymmetric}\,\,\Leftrightarrow\,\,\textrm{R is irreflexive and antisymmetric}$$

이를 집합의 언어로 증명해 보자. 증명 과정을 명료하게 써 보는 일, 그러면서도 그림을 통한 직관적인 이해와 align시켜 보는 일은 생각보다 재미있다.

① $(\Rightarrow)$

i) asymmetric $\Rightarrow$ irreflexive

이항관계 $\mathrm{R}$이 비대칭일 때,

만약 어떤 $a_1,a_2\in A$가 존재하여 $a_1=a_2\,(=a)$이고 $(a_1,a_2)\in\mathrm{R}$이라면 (가정)

비대칭성의 정의에 의하여, 순서를 바꾼 순서쌍 $(a_2,a_1)$ 은 $\mathrm{R}$의 원소가 아니다.

그러나 $a_1=a_2$이므로 실제로는 이는 원래 순서쌍과 동일하며 따라서 $\mathrm{R}$의 원소여야 한다는 결론이 나온다. 이는 모순이다. 따라서 가정은 잘못되었다.

즉, 어떠한 $a\in A$에 대해서도 $(a,a)\notin\mathrm{R}$이다. 곧, $\mathrm{R}$은 비반사적이다.

ii) asymmetric $\Rightarrow$ antisymmetric

이항관계 $\mathrm{R}$이 비대칭일 때,

$(x,y)\in\mathrm{R}\,\,\Rightarrow\,\,(y,x)\notin\mathrm{R}$이므로,

반대칭 여부를 판단하기 위한 조건인 $(x,y)\,\mathrm{and}\,(y,x)\,\in\mathrm{R}$을 만족하는 순서쌍 자체가 존재하지 않는다. 따라서 $x=y$는 vacuously true이다. 곧, $\mathrm{R}$은 반대칭이다.

② $(\Leftarrow)$

이항관계 $\mathrm{R}$이 비반사적이고 반대칭일 때,

만약 어떤 $(x,y)\in\mathrm{R}$에 대해 $(y,x)\in\mathrm{R}$이라면 (가정)

$x,y$의 관계는 같거나 다르거나 둘 중 하나인데,

$x=y$라면 $(x,x)\in\mathrm{R}$이므로 비반사성에 모순이고,

$x\neq y$라면, $(x,y)\,\mathrm{and}\,(y,x)\,\in\mathrm{R}$인데 $x\neq y$이므로 반대칭성에 모순이다.

따라서 어떤 경우에도 가정은 잘못되었다.

즉 모든 $(x,y)\in\mathrm{R}$에 대해 $(y,x)\notin\mathrm{R}$이다. 곧, $\mathrm{R}$은 비대칭이다.

①, ②를 종합하면, 증명하고자 했던 정리가 참임을 알 수 있다.

Facebook에서 이 글 보기: 링크

- 끝 -