집합 위에 정의된 이항관계(binary relation)

주어진 집합 $A$에 대하여 $A$ 위에서 정의된 이항관계(binary relation)이란, $A$의 원소들로 이루어진 순서쌍들의 모임이다. 즉, 곱집합 $A\times A$의 부분집합으로 이해할 수 있다. 이제부터 $R$을 집합 $A$ 위의 이항관계라 하자. 그러면 $R$의 원소 $(x,y)$를 보통 $xRy$, $R(x,y)$, 또는 간단히 $x\sim y$와 같이 나타낸다.

$$

집합 $A$ 위의 이항관계 $R$에는 여러가지 유형이 있는데, 이 중 몇 가지 중요한 유형은 다음과 같다.

1. 반사관계(reflexive relation): 모든 $x\in A$에 대하여, $x\sim x$.
2. 대칭관계(symmetric relation): 모든 $x,y\in A$에 대하여, $x\sim y$이면 $y\sim x$.
3. 추이관계(transitive relation): 모든 $x,y,z\in A$에 대하여, $x\sim y$이고 $y\sim z$이면 $x\sim z$.
4. 반대칭관계(antisymmetric relation): 모든 $x,y\in A$에 대하여, $x\sim y$이고 $y\sim x$이면 $x=y$.

만약 주어진 이항관계 $R$이 반사적, 대칭적, 추이적이면, $R$을 동치관계(equivalence relation)이라 한다. 또한 $R$이 반사적, 반대칭적, 추이적이면, $R$을 부분순서(partial order)라 한다.

^[각주:1]

$$

예제 0. $A=\mathbb{R}$이라 하자. 그러면 $\mathbb{R}$ 위에서 정의된 등호관계 $=$는 동치관계임을 간단히 확인할 수 있다. 또한 부등호관계 $\le$는 부분순서(partial order)이면서 전순서(total order)이다.

$$

이항관계 유형들의 독립성

위에서 언급한 이항관계의 여러가지 유형들은 각각 독립적이다. 예를 들어 어떤 이항관계 $R$이 동시에 반사적이고 대칭적이라 하더라도 (반사적, 대칭적이라는 사실로부터 추이적이라는 결론을 이끌어 낼 수 없기 때문에) 동치관계라는 결론을 내릴 수 없다. 이와 같은 이항관계의 유형들의 독립성을 하나씩 예를 통해서 알아 보자.

^[각주:2]

$$

예제 1. 반사적, 대칭적이지만, 추이적이 아닌 관계: 집합 $A=\mathbb{R}$에 대하여, 이항관계 $R$을 다음과 같이 정의하자. $$R=\left\{(x,y)\in {\mathbb{R}}^2\right|\left|x-y\right|\le 1\}.$$ 임의의 $x\in \mathbb{R}$에 대하여, $\left|x-x\right|=0\le 1$이 성립하므로, $R$은 반사적이다. 또한 임의의 $x,y\in \mathbb{R}$에 대하여, $\left|x-y\right|\le 1$이면 $\left|y-x\right|\le 1$이 성립하므로, $R$은 대칭적이다. 하지만 $x=-1$, $y=0$, $z=1$이라 하면, $\left|x-y\right|=1$이고 $\left|y-z\right|=1$이지만, $\left|x-z\right|=2\nleqq 1$이 되어 $R$은 추이적이지 않다.

$$

예제 2. 반사적, 추이적이지만, 대칭적이 아닌 관계: 집합 $A=\mathbb{R}$에 대하여, 이항관계 $R$을 다음과 같이 정의하자. $$R=\left\{(x,y)\in {\mathbb{R}}^2\right|x\le y\}$$ 임의의 $x\in \mathbb{R}$에 대하여, $x\le x$가 성립하므로, $R$은 반사적이다. 또한 임의의 $x,y,z$에 대하여, $x\le y$이고 $y\le z$이면 $x\le z$임은 자명하므로 $R$은 추이적임을 알 수 있다. 하지만 $x=-1$, $y=1$이라 하면, $x\le y$이지만 $y\nleqq x$이므로 $R$은 대칭적이지 않다.

$$

예제 3. 대칭적, 추이적이지만, 반사적이 아닌 관계: 집합 $A=\mathbb{R}$에 대하여, 이항관계 $R$을 다음과 같이 정의하자. $$R=\left\{(x,y)\in {\mathbb{R}}^2\right|xy>0\}$$ 우선 임의의 $x,y\in \mathbb{R}$에 대하여 $xy>0$이면 $yx>0$이므로, $R$은 대칭적이다. 또한 임의의 $x,y,z\in \mathbb{R}$에 대하여 $xy>0$, $yz>0$이 성립한다고 가정하면, $x{y}^{2}z>0$이고 $y\ne 0$이므로 $xz>0$을 얻는다. 따라서 $R$은 추이적임이다. 한 편, $x=0$이라 하면 $x^2=0\ngtr 0$이므로 $R$은 반사적이지 않다.

$$

예제 4. 반사적, 반대칭적이지만, 추이적이 아닌 관계: 집합 $A=\mathbb{R}$에 대하여, 이항관계 $R$을 다음과 같이 정의하자. $$R=\left\{(x,y)\in {\mathbb{R}}^2\right|x\le y\text{and}\left|x-y\right|\le 1\}.$$ 이미 예제 1에서 $R$이 반사적이지만 추이적이 아님을 살펴 보았기 때문에, $R$이 반대칭적임을 보이면 충분하다.

^[각주:3] 이제 임의의 $x,y\in \mathbb{R}$에 대하여, 동시에 $x\sim y$이고 $y\sim x$이면, 특히 $x\le y$이고 $y\le x$이기 때문에 $x=y$를 얻는다. 따라서 $R$은 반대칭적임을 알 수 있다.

$$

예제 5. 반사적, 추이적이지만, 반대칭적이 아닌 관계: 집합 $A=\mathbb{R}$에 대하여, 이항관계 $R$을 다음과 같이 정의하자. $$R=\left\{(x,y)\in {\mathbb{R}}^2\right|\left|x\right|\le \left|y\right|\}$$ 임의의 $x\in \mathbb{R}$에 대하여, $\left|x\right|\le \left|x\right|$가 성립하므로, $R$은 반사적이다. 또한 임의의 $x,y,z$에 대하여, $\left|x\right|\le \left|y\right|$이고 $\left|y\right|\le \left|z\right|$라 하면, $\left|x\right|\le \left|z\right|$가 성립하기 때문에, $R$은 추이적임을 알 수 있다. 마지막으로 임의의 $x=1$, $y=-1$이라 하면, $\left|x\right|\le \left|y\right|$이고 $\left|y\right|\le \left|x\right|$이지만 $x\ne y$이므로 $R$은 반대칭적이 아니다.

$$

예제 6. 반대칭적, 추이적이지만, 반사적이 아닌 관계: 집합 $A=\mathbb{R}$에 대하여, 이항관계 $R$을 다음과 같이 정의하자. $$R=\left\{(x,y)\in {\mathbb{R}}^2\right|\left|x\right|\le y\}$$ 임의의 $x,y\in \mathbb{R}$에 대하여, $\left|x\right|\le y$이고 $\left|y\right|\le x$라 하자. 그러면 $x,y\ge 0$이기 때문에, $\left|x\right|=x$, $\left|y\right|=y$임을 알 수 있고, 이로부터 $x=y$를 이끌어 낼 수 있다. 따라서 $R$은 반대칭적이다. 또한 임의의 $x,y,z\in \mathbb{R}$에 대하여, $\left|x\right|\le y$이고 $\left|y\right|\le z$라 하자. 그러면 $y\ge 0$이므로 $\left|x\right|\le y=\left|y\right|\le z$를 얻는다. 따라서 $R$은 추이적이다. 한 편, $x=-1$이라 하면 $\left|x\right|=1\nleqq x$이므로 $R$은 반사적이지 않다.

1. 모든 $x,y\in A$에 대하여 $x\sim y$이거나 $y\sim x$가 성립하는 이항관계 $R$을 완전관계(total relation)라 하는데, 만약 부분순서 $R$이 완전성까지 만족하면, $R$을 전순서(total order)라 한다. [본문으로]
2. 참고: http://www.mathcounterexamples.net/around-binary-relations-on-sets/ [본문으로]
3. 조건 $x\le y$가 추가되긴 했지만, 예제 1과 동일한 방법으로 증명 가능하다. [본문으로]