어떤 집합 \(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에서 이 글 보기: 링크
- 끝 -
No comments:
Post a Comment