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

주어진 집합 $A$에 대하여 $A$ 위에서 정의된 이항관계(binary relation)이란, $A$의 원소들로 이루어진 순서쌍들의 모임이다. 즉, 곱집합 $A \times A$의 부분집합으로 이해할 수 있다. 이제부터 $R$을 집합 $A$ 위의 이항관계라 하자. 그러면 $R$의 원소 $(x,\,y)$를 보통 $x \, R \, y$, $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 = \R$이라 하자. 그러면 $\R$ 위에서 정의된 등호관계 $=$는 동치관계임을 간단히 확인할 수 있다. 또한 부등호관계 $\leq$는 부분순서(partial order)이면서 전순서(total order)이다.

$ $

이항관계 유형들의 독립성

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

$ $

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

$ $

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

$ $

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

$ $

예제 4. 반사적, 반대칭적이지만, 추이적이 아닌 관계: 집합 $A = \R$에 대하여, 이항관계 $R$을 다음과 같이 정의하자. \[ R = \set{(x,\,y) \in \R^2}{x \leq y \; \text{and} \; \abs{x - y} \leq 1}. \] 이미 예제 1에서 $R$이 반사적이지만 추이적이 아님을 살펴 보았기 때문에, $R$이 반대칭적임을 보이면 충분하다.^[각주:3] 이제 임의의 $x,\, y \in \R$에 대하여, 동시에 $x \sim y$이고 $y \sim x$이면, 특히 $x \leq y$이고 $y \leq x$이기 때문에 $x=y$를 얻는다. 따라서 $R$은 반대칭적임을 알 수 있다.

$ $

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

$ $

예제 6. 반대칭적, 추이적이지만, 반사적이 아닌 관계: 집합 $A = \R$에 대하여, 이항관계 $R$을 다음과 같이 정의하자. \[ R = \set{(x,\,y) \in \R^2}{\abs{x} \leq y} \] 임의의 $x,\, y \in \R$에 대하여, $\abs{x} \leq y$이고 $\abs{y} \leq x$라 하자. 그러면 $x,\, y \geq 0$이기 때문에, $\abs{x} = x$, $\abs{y} = y$임을 알 수 있고, 이로부터 $x = y$를 이끌어 낼 수 있다. 따라서 $R$은 반대칭적이다. 또한 임의의 $x,\, y,\, z \in \R$에 대하여, $\abs{x} \leq y$이고 $\abs{y} \leq z$라 하자. 그러면 $y \geq 0$이므로 $\abs{x} \leq y = \abs{y} \leq z$를 얻는다. 따라서 $R$은 추이적이다. 한 편, $x = -1$이라 하면 $\abs{x} = 1 \not\leq 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 \leq y$가 추가되긴 했지만, 예제 1과 동일한 방법으로 증명 가능하다. [본문으로]